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