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