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