1 /* 2 * bmap.c - NILFS block mapping. 3 * 4 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation. 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 19 * 20 * Written by Koji Sato <koji@osrg.net>. 21 */ 22 23 #include <linux/fs.h> 24 #include <linux/string.h> 25 #include <linux/errno.h> 26 #include "nilfs.h" 27 #include "bmap.h" 28 #include "sb.h" 29 #include "btree.h" 30 #include "direct.h" 31 #include "btnode.h" 32 #include "mdt.h" 33 #include "dat.h" 34 #include "alloc.h" 35 36 struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap) 37 { 38 return nilfs_dat_inode(NILFS_I_NILFS(bmap->b_inode)); 39 } 40 41 /** 42 * nilfs_bmap_lookup_at_level - find a data block or node block 43 * @bmap: bmap 44 * @key: key 45 * @level: level 46 * @ptrp: place to store the value associated to @key 47 * 48 * Description: nilfs_bmap_lookup_at_level() finds a record whose key 49 * matches @key in the block at @level of the bmap. 50 * 51 * Return Value: On success, 0 is returned and the record associated with @key 52 * is stored in the place pointed by @ptrp. On error, one of the following 53 * negative error codes is returned. 54 * 55 * %-EIO - I/O error. 56 * 57 * %-ENOMEM - Insufficient amount of memory available. 58 * 59 * %-ENOENT - A record associated with @key does not exist. 60 */ 61 int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level, 62 __u64 *ptrp) 63 { 64 sector_t blocknr; 65 int ret; 66 67 down_read(&bmap->b_sem); 68 ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp); 69 if (ret < 0) 70 goto out; 71 if (NILFS_BMAP_USE_VBN(bmap)) { 72 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), *ptrp, 73 &blocknr); 74 if (!ret) 75 *ptrp = blocknr; 76 } 77 78 out: 79 up_read(&bmap->b_sem); 80 return ret; 81 } 82 83 int nilfs_bmap_lookup_contig(struct nilfs_bmap *bmap, __u64 key, __u64 *ptrp, 84 unsigned maxblocks) 85 { 86 int ret; 87 88 down_read(&bmap->b_sem); 89 ret = bmap->b_ops->bop_lookup_contig(bmap, key, ptrp, maxblocks); 90 up_read(&bmap->b_sem); 91 return ret; 92 } 93 94 static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr) 95 { 96 __u64 keys[NILFS_BMAP_SMALL_HIGH + 1]; 97 __u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1]; 98 int ret, n; 99 100 if (bmap->b_ops->bop_check_insert != NULL) { 101 ret = bmap->b_ops->bop_check_insert(bmap, key); 102 if (ret > 0) { 103 n = bmap->b_ops->bop_gather_data( 104 bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1); 105 if (n < 0) 106 return n; 107 ret = nilfs_btree_convert_and_insert( 108 bmap, key, ptr, keys, ptrs, n); 109 if (ret == 0) 110 bmap->b_u.u_flags |= NILFS_BMAP_LARGE; 111 112 return ret; 113 } else if (ret < 0) 114 return ret; 115 } 116 117 return bmap->b_ops->bop_insert(bmap, key, ptr); 118 } 119 120 /** 121 * nilfs_bmap_insert - insert a new key-record pair into a bmap 122 * @bmap: bmap 123 * @key: key 124 * @rec: record 125 * 126 * Description: nilfs_bmap_insert() inserts the new key-record pair specified 127 * by @key and @rec into @bmap. 128 * 129 * Return Value: On success, 0 is returned. On error, one of the following 130 * negative error codes is returned. 131 * 132 * %-EIO - I/O error. 133 * 134 * %-ENOMEM - Insufficient amount of memory available. 135 * 136 * %-EEXIST - A record associated with @key already exist. 137 */ 138 int nilfs_bmap_insert(struct nilfs_bmap *bmap, 139 unsigned long key, 140 unsigned long rec) 141 { 142 int ret; 143 144 down_write(&bmap->b_sem); 145 ret = nilfs_bmap_do_insert(bmap, key, rec); 146 up_write(&bmap->b_sem); 147 return ret; 148 } 149 150 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key) 151 { 152 __u64 keys[NILFS_BMAP_LARGE_LOW + 1]; 153 __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1]; 154 int ret, n; 155 156 if (bmap->b_ops->bop_check_delete != NULL) { 157 ret = bmap->b_ops->bop_check_delete(bmap, key); 158 if (ret > 0) { 159 n = bmap->b_ops->bop_gather_data( 160 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1); 161 if (n < 0) 162 return n; 163 ret = nilfs_direct_delete_and_convert( 164 bmap, key, keys, ptrs, n); 165 if (ret == 0) 166 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE; 167 168 return ret; 169 } else if (ret < 0) 170 return ret; 171 } 172 173 return bmap->b_ops->bop_delete(bmap, key); 174 } 175 176 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, unsigned long *key) 177 { 178 __u64 lastkey; 179 int ret; 180 181 down_read(&bmap->b_sem); 182 ret = bmap->b_ops->bop_last_key(bmap, &lastkey); 183 if (!ret) 184 *key = lastkey; 185 up_read(&bmap->b_sem); 186 return ret; 187 } 188 189 /** 190 * nilfs_bmap_delete - delete a key-record pair from a bmap 191 * @bmap: bmap 192 * @key: key 193 * 194 * Description: nilfs_bmap_delete() deletes the key-record pair specified by 195 * @key from @bmap. 196 * 197 * Return Value: On success, 0 is returned. On error, one of the following 198 * negative error codes is returned. 199 * 200 * %-EIO - I/O error. 201 * 202 * %-ENOMEM - Insufficient amount of memory available. 203 * 204 * %-ENOENT - A record associated with @key does not exist. 205 */ 206 int nilfs_bmap_delete(struct nilfs_bmap *bmap, unsigned long key) 207 { 208 int ret; 209 210 down_write(&bmap->b_sem); 211 ret = nilfs_bmap_do_delete(bmap, key); 212 up_write(&bmap->b_sem); 213 return ret; 214 } 215 216 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, unsigned long key) 217 { 218 __u64 lastkey; 219 int ret; 220 221 ret = bmap->b_ops->bop_last_key(bmap, &lastkey); 222 if (ret < 0) { 223 if (ret == -ENOENT) 224 ret = 0; 225 return ret; 226 } 227 228 while (key <= lastkey) { 229 ret = nilfs_bmap_do_delete(bmap, lastkey); 230 if (ret < 0) 231 return ret; 232 ret = bmap->b_ops->bop_last_key(bmap, &lastkey); 233 if (ret < 0) { 234 if (ret == -ENOENT) 235 ret = 0; 236 return ret; 237 } 238 } 239 return 0; 240 } 241 242 /** 243 * nilfs_bmap_truncate - truncate a bmap to a specified key 244 * @bmap: bmap 245 * @key: key 246 * 247 * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are 248 * greater than or equal to @key from @bmap. 249 * 250 * Return Value: On success, 0 is returned. On error, one of the following 251 * negative error codes is returned. 252 * 253 * %-EIO - I/O error. 254 * 255 * %-ENOMEM - Insufficient amount of memory available. 256 */ 257 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, unsigned long key) 258 { 259 int ret; 260 261 down_write(&bmap->b_sem); 262 ret = nilfs_bmap_do_truncate(bmap, key); 263 up_write(&bmap->b_sem); 264 return ret; 265 } 266 267 /** 268 * nilfs_bmap_clear - free resources a bmap holds 269 * @bmap: bmap 270 * 271 * Description: nilfs_bmap_clear() frees resources associated with @bmap. 272 */ 273 void nilfs_bmap_clear(struct nilfs_bmap *bmap) 274 { 275 down_write(&bmap->b_sem); 276 if (bmap->b_ops->bop_clear != NULL) 277 bmap->b_ops->bop_clear(bmap); 278 up_write(&bmap->b_sem); 279 } 280 281 /** 282 * nilfs_bmap_propagate - propagate dirty state 283 * @bmap: bmap 284 * @bh: buffer head 285 * 286 * Description: nilfs_bmap_propagate() marks the buffers that directly or 287 * indirectly refer to the block specified by @bh dirty. 288 * 289 * Return Value: On success, 0 is returned. On error, one of the following 290 * negative error codes is returned. 291 * 292 * %-EIO - I/O error. 293 * 294 * %-ENOMEM - Insufficient amount of memory available. 295 */ 296 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh) 297 { 298 int ret; 299 300 down_write(&bmap->b_sem); 301 ret = bmap->b_ops->bop_propagate(bmap, bh); 302 up_write(&bmap->b_sem); 303 return ret; 304 } 305 306 /** 307 * nilfs_bmap_lookup_dirty_buffers - 308 * @bmap: bmap 309 * @listp: pointer to buffer head list 310 */ 311 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap, 312 struct list_head *listp) 313 { 314 if (bmap->b_ops->bop_lookup_dirty_buffers != NULL) 315 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp); 316 } 317 318 /** 319 * nilfs_bmap_assign - assign a new block number to a block 320 * @bmap: bmap 321 * @bhp: pointer to buffer head 322 * @blocknr: block number 323 * @binfo: block information 324 * 325 * Description: nilfs_bmap_assign() assigns the block number @blocknr to the 326 * buffer specified by @bh. 327 * 328 * Return Value: On success, 0 is returned and the buffer head of a newly 329 * create buffer and the block information associated with the buffer are 330 * stored in the place pointed by @bh and @binfo, respectively. On error, one 331 * of the following negative error codes is returned. 332 * 333 * %-EIO - I/O error. 334 * 335 * %-ENOMEM - Insufficient amount of memory available. 336 */ 337 int nilfs_bmap_assign(struct nilfs_bmap *bmap, 338 struct buffer_head **bh, 339 unsigned long blocknr, 340 union nilfs_binfo *binfo) 341 { 342 int ret; 343 344 down_write(&bmap->b_sem); 345 ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo); 346 up_write(&bmap->b_sem); 347 return ret; 348 } 349 350 /** 351 * nilfs_bmap_mark - mark block dirty 352 * @bmap: bmap 353 * @key: key 354 * @level: level 355 * 356 * Description: nilfs_bmap_mark() marks the block specified by @key and @level 357 * as dirty. 358 * 359 * Return Value: On success, 0 is returned. On error, one of the following 360 * negative error codes is returned. 361 * 362 * %-EIO - I/O error. 363 * 364 * %-ENOMEM - Insufficient amount of memory available. 365 */ 366 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level) 367 { 368 int ret; 369 370 if (bmap->b_ops->bop_mark == NULL) 371 return 0; 372 373 down_write(&bmap->b_sem); 374 ret = bmap->b_ops->bop_mark(bmap, key, level); 375 up_write(&bmap->b_sem); 376 return ret; 377 } 378 379 /** 380 * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state 381 * @bmap: bmap 382 * 383 * Description: nilfs_test_and_clear() is the atomic operation to test and 384 * clear the dirty state of @bmap. 385 * 386 * Return Value: 1 is returned if @bmap is dirty, or 0 if clear. 387 */ 388 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap) 389 { 390 int ret; 391 392 down_write(&bmap->b_sem); 393 ret = nilfs_bmap_dirty(bmap); 394 nilfs_bmap_clear_dirty(bmap); 395 up_write(&bmap->b_sem); 396 return ret; 397 } 398 399 400 /* 401 * Internal use only 402 */ 403 404 void nilfs_bmap_add_blocks(const struct nilfs_bmap *bmap, int n) 405 { 406 inode_add_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n); 407 } 408 409 void nilfs_bmap_sub_blocks(const struct nilfs_bmap *bmap, int n) 410 { 411 inode_sub_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n); 412 } 413 414 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap, 415 const struct buffer_head *bh) 416 { 417 struct buffer_head *pbh; 418 __u64 key; 419 420 key = page_index(bh->b_page) << (PAGE_CACHE_SHIFT - 421 bmap->b_inode->i_blkbits); 422 for (pbh = page_buffers(bh->b_page); pbh != bh; pbh = pbh->b_this_page) 423 key++; 424 425 return key; 426 } 427 428 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key) 429 { 430 __s64 diff; 431 432 diff = key - bmap->b_last_allocated_key; 433 if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) && 434 (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) && 435 (bmap->b_last_allocated_ptr + diff > 0)) 436 return bmap->b_last_allocated_ptr + diff; 437 else 438 return NILFS_BMAP_INVALID_PTR; 439 } 440 441 #define NILFS_BMAP_GROUP_DIV 8 442 __u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap) 443 { 444 struct inode *dat = nilfs_bmap_get_dat(bmap); 445 unsigned long entries_per_group = nilfs_palloc_entries_per_group(dat); 446 unsigned long group = bmap->b_inode->i_ino / entries_per_group; 447 448 return group * entries_per_group + 449 (bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) * 450 (entries_per_group / NILFS_BMAP_GROUP_DIV); 451 } 452 453 static struct lock_class_key nilfs_bmap_dat_lock_key; 454 static struct lock_class_key nilfs_bmap_mdt_lock_key; 455 456 /** 457 * nilfs_bmap_read - read a bmap from an inode 458 * @bmap: bmap 459 * @raw_inode: on-disk inode 460 * 461 * Description: nilfs_bmap_read() initializes the bmap @bmap. 462 * 463 * Return Value: On success, 0 is returned. On error, the following negative 464 * error code is returned. 465 * 466 * %-ENOMEM - Insufficient amount of memory available. 467 */ 468 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode) 469 { 470 if (raw_inode == NULL) 471 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE); 472 else 473 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE); 474 475 init_rwsem(&bmap->b_sem); 476 bmap->b_state = 0; 477 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode; 478 switch (bmap->b_inode->i_ino) { 479 case NILFS_DAT_INO: 480 bmap->b_ptr_type = NILFS_BMAP_PTR_P; 481 bmap->b_last_allocated_key = 0; 482 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT; 483 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key); 484 break; 485 case NILFS_CPFILE_INO: 486 case NILFS_SUFILE_INO: 487 bmap->b_ptr_type = NILFS_BMAP_PTR_VS; 488 bmap->b_last_allocated_key = 0; 489 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR; 490 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key); 491 break; 492 case NILFS_IFILE_INO: 493 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key); 494 /* Fall through */ 495 default: 496 bmap->b_ptr_type = NILFS_BMAP_PTR_VM; 497 bmap->b_last_allocated_key = 0; 498 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR; 499 break; 500 } 501 502 return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ? 503 nilfs_btree_init(bmap) : nilfs_direct_init(bmap); 504 } 505 506 /** 507 * nilfs_bmap_write - write back a bmap to an inode 508 * @bmap: bmap 509 * @raw_inode: on-disk inode 510 * 511 * Description: nilfs_bmap_write() stores @bmap in @raw_inode. 512 */ 513 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode) 514 { 515 down_write(&bmap->b_sem); 516 memcpy(raw_inode->i_bmap, bmap->b_u.u_data, 517 NILFS_INODE_BMAP_SIZE * sizeof(__le64)); 518 if (bmap->b_inode->i_ino == NILFS_DAT_INO) 519 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT; 520 521 up_write(&bmap->b_sem); 522 } 523 524 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap) 525 { 526 memset(&bmap->b_u, 0, NILFS_BMAP_SIZE); 527 init_rwsem(&bmap->b_sem); 528 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode; 529 bmap->b_ptr_type = NILFS_BMAP_PTR_U; 530 bmap->b_last_allocated_key = 0; 531 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR; 532 bmap->b_state = 0; 533 nilfs_btree_init_gc(bmap); 534 } 535 536 void nilfs_bmap_init_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap) 537 { 538 memcpy(gcbmap, bmap, sizeof(*bmap)); 539 init_rwsem(&gcbmap->b_sem); 540 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key); 541 gcbmap->b_inode = &NILFS_BMAP_I(gcbmap)->vfs_inode; 542 } 543 544 void nilfs_bmap_commit_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap) 545 { 546 memcpy(bmap, gcbmap, sizeof(*bmap)); 547 init_rwsem(&bmap->b_sem); 548 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key); 549 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode; 550 } 551