1// SPDX-License-Identifier: GPL-2.0+ 2/* 3 * NILFS dat/inode allocator 4 * 5 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation. 6 * 7 * Originally written by Koji Sato. 8 * Two allocators were unified by Ryusuke Konishi and Amagai Yoshiji. 9 */ 10 11#include <linux/types.h> 12#include <linux/buffer_head.h> 13#include <linux/fs.h> 14#include <linux/bitops.h> 15#include <linux/slab.h> 16#include "mdt.h" 17#include "alloc.h" 18 19 20/** 21 * nilfs_palloc_groups_per_desc_block - get the number of groups that a group 22 * descriptor block can maintain 23 * @inode: inode of metadata file using this allocator 24 */ 25static inline unsigned long 26nilfs_palloc_groups_per_desc_block(const struct inode *inode) 27{ 28 return i_blocksize(inode) / 29 sizeof(struct nilfs_palloc_group_desc); 30} 31 32/** 33 * nilfs_palloc_groups_count - get maximum number of groups 34 * @inode: inode of metadata file using this allocator 35 */ 36static inline unsigned long 37nilfs_palloc_groups_count(const struct inode *inode) 38{ 39 return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */)); 40} 41 42/** 43 * nilfs_palloc_init_blockgroup - initialize private variables for allocator 44 * @inode: inode of metadata file using this allocator 45 * @entry_size: size of the persistent object 46 */ 47int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned int entry_size) 48{ 49 struct nilfs_mdt_info *mi = NILFS_MDT(inode); 50 51 mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS); 52 if (!mi->mi_bgl) 53 return -ENOMEM; 54 55 bgl_lock_init(mi->mi_bgl); 56 57 nilfs_mdt_set_entry_size(inode, entry_size, 0); 58 59 mi->mi_blocks_per_group = 60 DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode), 61 mi->mi_entries_per_block) + 1; 62 /* 63 * Number of blocks in a group including entry blocks 64 * and a bitmap block 65 */ 66 mi->mi_blocks_per_desc_block = 67 nilfs_palloc_groups_per_desc_block(inode) * 68 mi->mi_blocks_per_group + 1; 69 /* 70 * Number of blocks per descriptor including the 71 * descriptor block 72 */ 73 return 0; 74} 75 76/** 77 * nilfs_palloc_group - get group number and offset from an entry number 78 * @inode: inode of metadata file using this allocator 79 * @nr: serial number of the entry (e.g. inode number) 80 * @offset: pointer to store offset number in the group 81 */ 82static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr, 83 unsigned long *offset) 84{ 85 __u64 group = nr; 86 87 *offset = do_div(group, nilfs_palloc_entries_per_group(inode)); 88 return group; 89} 90 91/** 92 * nilfs_palloc_desc_blkoff - get block offset of a group descriptor block 93 * @inode: inode of metadata file using this allocator 94 * @group: group number 95 * 96 * nilfs_palloc_desc_blkoff() returns block offset of the descriptor 97 * block which contains a descriptor of the specified group. 98 */ 99static unsigned long 100nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group) 101{ 102 unsigned long desc_block = 103 group / nilfs_palloc_groups_per_desc_block(inode); 104 return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block; 105} 106 107/** 108 * nilfs_palloc_bitmap_blkoff - get block offset of a bitmap block 109 * @inode: inode of metadata file using this allocator 110 * @group: group number 111 * 112 * nilfs_palloc_bitmap_blkoff() returns block offset of the bitmap 113 * block used to allocate/deallocate entries in the specified group. 114 */ 115static unsigned long 116nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group) 117{ 118 unsigned long desc_offset = 119 group % nilfs_palloc_groups_per_desc_block(inode); 120 return nilfs_palloc_desc_blkoff(inode, group) + 1 + 121 desc_offset * NILFS_MDT(inode)->mi_blocks_per_group; 122} 123 124/** 125 * nilfs_palloc_group_desc_nfrees - get the number of free entries in a group 126 * @desc: pointer to descriptor structure for the group 127 * @lock: spin lock protecting @desc 128 */ 129static unsigned long 130nilfs_palloc_group_desc_nfrees(const struct nilfs_palloc_group_desc *desc, 131 spinlock_t *lock) 132{ 133 unsigned long nfree; 134 135 spin_lock(lock); 136 nfree = le32_to_cpu(desc->pg_nfrees); 137 spin_unlock(lock); 138 return nfree; 139} 140 141/** 142 * nilfs_palloc_group_desc_add_entries - adjust count of free entries 143 * @desc: pointer to descriptor structure for the group 144 * @lock: spin lock protecting @desc 145 * @n: delta to be added 146 */ 147static u32 148nilfs_palloc_group_desc_add_entries(struct nilfs_palloc_group_desc *desc, 149 spinlock_t *lock, u32 n) 150{ 151 u32 nfree; 152 153 spin_lock(lock); 154 le32_add_cpu(&desc->pg_nfrees, n); 155 nfree = le32_to_cpu(desc->pg_nfrees); 156 spin_unlock(lock); 157 return nfree; 158} 159 160/** 161 * nilfs_palloc_entry_blkoff - get block offset of an entry block 162 * @inode: inode of metadata file using this allocator 163 * @nr: serial number of the entry (e.g. inode number) 164 */ 165static unsigned long 166nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr) 167{ 168 unsigned long group, group_offset; 169 170 group = nilfs_palloc_group(inode, nr, &group_offset); 171 172 return nilfs_palloc_bitmap_blkoff(inode, group) + 1 + 173 group_offset / NILFS_MDT(inode)->mi_entries_per_block; 174} 175 176/** 177 * nilfs_palloc_desc_block_init - initialize buffer of a group descriptor block 178 * @inode: inode of metadata file 179 * @bh: buffer head of the buffer to be initialized 180 * @kaddr: kernel address mapped for the page including the buffer 181 */ 182static void nilfs_palloc_desc_block_init(struct inode *inode, 183 struct buffer_head *bh, void *kaddr) 184{ 185 struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh); 186 unsigned long n = nilfs_palloc_groups_per_desc_block(inode); 187 __le32 nfrees; 188 189 nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode)); 190 while (n-- > 0) { 191 desc->pg_nfrees = nfrees; 192 desc++; 193 } 194} 195 196static int nilfs_palloc_get_block(struct inode *inode, unsigned long blkoff, 197 int create, 198 void (*init_block)(struct inode *, 199 struct buffer_head *, 200 void *), 201 struct buffer_head **bhp, 202 struct nilfs_bh_assoc *prev, 203 spinlock_t *lock) 204{ 205 int ret; 206 207 spin_lock(lock); 208 if (prev->bh && blkoff == prev->blkoff && 209 likely(buffer_uptodate(prev->bh))) { 210 get_bh(prev->bh); 211 *bhp = prev->bh; 212 spin_unlock(lock); 213 return 0; 214 } 215 spin_unlock(lock); 216 217 ret = nilfs_mdt_get_block(inode, blkoff, create, init_block, bhp); 218 if (!ret) { 219 spin_lock(lock); 220 /* 221 * The following code must be safe for change of the 222 * cache contents during the get block call. 223 */ 224 brelse(prev->bh); 225 get_bh(*bhp); 226 prev->bh = *bhp; 227 prev->blkoff = blkoff; 228 spin_unlock(lock); 229 } 230 return ret; 231} 232 233/** 234 * nilfs_palloc_delete_block - delete a block on the persistent allocator file 235 * @inode: inode of metadata file using this allocator 236 * @blkoff: block offset 237 * @prev: nilfs_bh_assoc struct of the last used buffer 238 * @lock: spin lock protecting @prev 239 */ 240static int nilfs_palloc_delete_block(struct inode *inode, unsigned long blkoff, 241 struct nilfs_bh_assoc *prev, 242 spinlock_t *lock) 243{ 244 spin_lock(lock); 245 if (prev->bh && blkoff == prev->blkoff) { 246 brelse(prev->bh); 247 prev->bh = NULL; 248 } 249 spin_unlock(lock); 250 return nilfs_mdt_delete_block(inode, blkoff); 251} 252 253/** 254 * nilfs_palloc_get_desc_block - get buffer head of a group descriptor block 255 * @inode: inode of metadata file using this allocator 256 * @group: group number 257 * @create: create flag 258 * @bhp: pointer to store the resultant buffer head 259 */ 260static int nilfs_palloc_get_desc_block(struct inode *inode, 261 unsigned long group, 262 int create, struct buffer_head **bhp) 263{ 264 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 265 266 return nilfs_palloc_get_block(inode, 267 nilfs_palloc_desc_blkoff(inode, group), 268 create, nilfs_palloc_desc_block_init, 269 bhp, &cache->prev_desc, &cache->lock); 270} 271 272/** 273 * nilfs_palloc_get_bitmap_block - get buffer head of a bitmap block 274 * @inode: inode of metadata file using this allocator 275 * @group: group number 276 * @create: create flag 277 * @bhp: pointer to store the resultant buffer head 278 */ 279static int nilfs_palloc_get_bitmap_block(struct inode *inode, 280 unsigned long group, 281 int create, struct buffer_head **bhp) 282{ 283 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 284 285 return nilfs_palloc_get_block(inode, 286 nilfs_palloc_bitmap_blkoff(inode, group), 287 create, NULL, bhp, 288 &cache->prev_bitmap, &cache->lock); 289} 290 291/** 292 * nilfs_palloc_delete_bitmap_block - delete a bitmap block 293 * @inode: inode of metadata file using this allocator 294 * @group: group number 295 */ 296static int nilfs_palloc_delete_bitmap_block(struct inode *inode, 297 unsigned long group) 298{ 299 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 300 301 return nilfs_palloc_delete_block(inode, 302 nilfs_palloc_bitmap_blkoff(inode, 303 group), 304 &cache->prev_bitmap, &cache->lock); 305} 306 307/** 308 * nilfs_palloc_get_entry_block - get buffer head of an entry block 309 * @inode: inode of metadata file using this allocator 310 * @nr: serial number of the entry (e.g. inode number) 311 * @create: create flag 312 * @bhp: pointer to store the resultant buffer head 313 */ 314int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr, 315 int create, struct buffer_head **bhp) 316{ 317 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 318 319 return nilfs_palloc_get_block(inode, 320 nilfs_palloc_entry_blkoff(inode, nr), 321 create, NULL, bhp, 322 &cache->prev_entry, &cache->lock); 323} 324 325/** 326 * nilfs_palloc_delete_entry_block - delete an entry block 327 * @inode: inode of metadata file using this allocator 328 * @nr: serial number of the entry 329 */ 330static int nilfs_palloc_delete_entry_block(struct inode *inode, __u64 nr) 331{ 332 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 333 334 return nilfs_palloc_delete_block(inode, 335 nilfs_palloc_entry_blkoff(inode, nr), 336 &cache->prev_entry, &cache->lock); 337} 338 339/** 340 * nilfs_palloc_block_get_group_desc - get kernel address of a group descriptor 341 * @inode: inode of metadata file using this allocator 342 * @group: group number 343 * @bh: buffer head of the buffer storing the group descriptor block 344 * @kaddr: kernel address mapped for the page including the buffer 345 */ 346static struct nilfs_palloc_group_desc * 347nilfs_palloc_block_get_group_desc(const struct inode *inode, 348 unsigned long group, 349 const struct buffer_head *bh, void *kaddr) 350{ 351 return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) + 352 group % nilfs_palloc_groups_per_desc_block(inode); 353} 354 355/** 356 * nilfs_palloc_block_get_entry - get kernel address of an entry 357 * @inode: inode of metadata file using this allocator 358 * @nr: serial number of the entry (e.g. inode number) 359 * @bh: buffer head of the buffer storing the entry block 360 * @kaddr: kernel address mapped for the page including the buffer 361 */ 362void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr, 363 const struct buffer_head *bh, void *kaddr) 364{ 365 unsigned long entry_offset, group_offset; 366 367 nilfs_palloc_group(inode, nr, &group_offset); 368 entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block; 369 370 return kaddr + bh_offset(bh) + 371 entry_offset * NILFS_MDT(inode)->mi_entry_size; 372} 373 374/** 375 * nilfs_palloc_find_available_slot - find available slot in a group 376 * @bitmap: bitmap of the group 377 * @target: offset number of an entry in the group (start point) 378 * @bsize: size in bits 379 * @lock: spin lock protecting @bitmap 380 */ 381static int nilfs_palloc_find_available_slot(unsigned char *bitmap, 382 unsigned long target, 383 unsigned int bsize, 384 spinlock_t *lock) 385{ 386 int pos, end = bsize; 387 388 if (likely(target < bsize)) { 389 pos = target; 390 do { 391 pos = nilfs_find_next_zero_bit(bitmap, end, pos); 392 if (pos >= end) 393 break; 394 if (!nilfs_set_bit_atomic(lock, pos, bitmap)) 395 return pos; 396 } while (++pos < end); 397 398 end = target; 399 } 400 401 /* wrap around */ 402 for (pos = 0; pos < end; pos++) { 403 pos = nilfs_find_next_zero_bit(bitmap, end, pos); 404 if (pos >= end) 405 break; 406 if (!nilfs_set_bit_atomic(lock, pos, bitmap)) 407 return pos; 408 } 409 410 return -ENOSPC; 411} 412 413/** 414 * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups 415 * in a group descriptor block 416 * @inode: inode of metadata file using this allocator 417 * @curr: current group number 418 * @max: maximum number of groups 419 */ 420static unsigned long 421nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode, 422 unsigned long curr, unsigned long max) 423{ 424 return min_t(unsigned long, 425 nilfs_palloc_groups_per_desc_block(inode) - 426 curr % nilfs_palloc_groups_per_desc_block(inode), 427 max - curr + 1); 428} 429 430/** 431 * nilfs_palloc_count_desc_blocks - count descriptor blocks number 432 * @inode: inode of metadata file using this allocator 433 * @desc_blocks: descriptor blocks number [out] 434 */ 435static int nilfs_palloc_count_desc_blocks(struct inode *inode, 436 unsigned long *desc_blocks) 437{ 438 __u64 blknum; 439 int ret; 440 441 ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum); 442 if (likely(!ret)) 443 *desc_blocks = DIV_ROUND_UP( 444 (unsigned long)blknum, 445 NILFS_MDT(inode)->mi_blocks_per_desc_block); 446 return ret; 447} 448 449/** 450 * nilfs_palloc_mdt_file_can_grow - check potential opportunity for 451 * MDT file growing 452 * @inode: inode of metadata file using this allocator 453 * @desc_blocks: known current descriptor blocks count 454 */ 455static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode, 456 unsigned long desc_blocks) 457{ 458 return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) < 459 nilfs_palloc_groups_count(inode); 460} 461 462/** 463 * nilfs_palloc_count_max_entries - count max number of entries that can be 464 * described by descriptor blocks count 465 * @inode: inode of metadata file using this allocator 466 * @nused: current number of used entries 467 * @nmaxp: max number of entries [out] 468 */ 469int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp) 470{ 471 unsigned long desc_blocks = 0; 472 u64 entries_per_desc_block, nmax; 473 int err; 474 475 err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks); 476 if (unlikely(err)) 477 return err; 478 479 entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) * 480 nilfs_palloc_groups_per_desc_block(inode); 481 nmax = entries_per_desc_block * desc_blocks; 482 483 if (nused == nmax && 484 nilfs_palloc_mdt_file_can_grow(inode, desc_blocks)) 485 nmax += entries_per_desc_block; 486 487 if (nused > nmax) 488 return -ERANGE; 489 490 *nmaxp = nmax; 491 return 0; 492} 493 494/** 495 * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object 496 * @inode: inode of metadata file using this allocator 497 * @req: nilfs_palloc_req structure exchanged for the allocation 498 */ 499int nilfs_palloc_prepare_alloc_entry(struct inode *inode, 500 struct nilfs_palloc_req *req) 501{ 502 struct buffer_head *desc_bh, *bitmap_bh; 503 struct nilfs_palloc_group_desc *desc; 504 unsigned char *bitmap; 505 void *desc_kaddr, *bitmap_kaddr; 506 unsigned long group, maxgroup, ngroups; 507 unsigned long group_offset, maxgroup_offset; 508 unsigned long n, entries_per_group; 509 unsigned long i, j; 510 spinlock_t *lock; 511 int pos, ret; 512 513 ngroups = nilfs_palloc_groups_count(inode); 514 maxgroup = ngroups - 1; 515 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 516 entries_per_group = nilfs_palloc_entries_per_group(inode); 517 518 for (i = 0; i < ngroups; i += n) { 519 if (group >= ngroups) { 520 /* wrap around */ 521 group = 0; 522 maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr, 523 &maxgroup_offset) - 1; 524 } 525 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 526 if (ret < 0) 527 return ret; 528 desc_kaddr = kmap_local_page(desc_bh->b_page); 529 desc = nilfs_palloc_block_get_group_desc( 530 inode, group, desc_bh, desc_kaddr); 531 n = nilfs_palloc_rest_groups_in_desc_block(inode, group, 532 maxgroup); 533 for (j = 0; j < n; j++, desc++, group++, group_offset = 0) { 534 lock = nilfs_mdt_bgl_lock(inode, group); 535 if (nilfs_palloc_group_desc_nfrees(desc, lock) == 0) 536 continue; 537 538 kunmap_local(desc_kaddr); 539 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, 540 &bitmap_bh); 541 if (unlikely(ret < 0)) { 542 brelse(desc_bh); 543 return ret; 544 } 545 546 desc_kaddr = kmap_local_page(desc_bh->b_page); 547 desc = nilfs_palloc_block_get_group_desc( 548 inode, group, desc_bh, desc_kaddr); 549 550 bitmap_kaddr = kmap_local_page(bitmap_bh->b_page); 551 bitmap = bitmap_kaddr + bh_offset(bitmap_bh); 552 pos = nilfs_palloc_find_available_slot( 553 bitmap, group_offset, entries_per_group, lock); 554 kunmap_local(bitmap_kaddr); 555 if (pos >= 0) 556 goto found; 557 558 brelse(bitmap_bh); 559 } 560 561 kunmap_local(desc_kaddr); 562 brelse(desc_bh); 563 } 564 565 /* no entries left */ 566 return -ENOSPC; 567 568found: 569 /* found a free entry */ 570 nilfs_palloc_group_desc_add_entries(desc, lock, -1); 571 req->pr_entry_nr = entries_per_group * group + pos; 572 kunmap_local(desc_kaddr); 573 574 req->pr_desc_bh = desc_bh; 575 req->pr_bitmap_bh = bitmap_bh; 576 return 0; 577} 578 579/** 580 * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object 581 * @inode: inode of metadata file using this allocator 582 * @req: nilfs_palloc_req structure exchanged for the allocation 583 */ 584void nilfs_palloc_commit_alloc_entry(struct inode *inode, 585 struct nilfs_palloc_req *req) 586{ 587 mark_buffer_dirty(req->pr_bitmap_bh); 588 mark_buffer_dirty(req->pr_desc_bh); 589 nilfs_mdt_mark_dirty(inode); 590 591 brelse(req->pr_bitmap_bh); 592 brelse(req->pr_desc_bh); 593} 594 595/** 596 * nilfs_palloc_commit_free_entry - finish deallocating a persistent object 597 * @inode: inode of metadata file using this allocator 598 * @req: nilfs_palloc_req structure exchanged for the removal 599 */ 600void nilfs_palloc_commit_free_entry(struct inode *inode, 601 struct nilfs_palloc_req *req) 602{ 603 struct nilfs_palloc_group_desc *desc; 604 unsigned long group, group_offset; 605 unsigned char *bitmap; 606 void *desc_kaddr, *bitmap_kaddr; 607 spinlock_t *lock; 608 609 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 610 desc_kaddr = kmap_local_page(req->pr_desc_bh->b_page); 611 desc = nilfs_palloc_block_get_group_desc(inode, group, 612 req->pr_desc_bh, desc_kaddr); 613 bitmap_kaddr = kmap_local_page(req->pr_bitmap_bh->b_page); 614 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh); 615 lock = nilfs_mdt_bgl_lock(inode, group); 616 617 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap)) 618 nilfs_warn(inode->i_sb, 619 "%s (ino=%lu): entry number %llu already freed", 620 __func__, inode->i_ino, 621 (unsigned long long)req->pr_entry_nr); 622 else 623 nilfs_palloc_group_desc_add_entries(desc, lock, 1); 624 625 kunmap_local(bitmap_kaddr); 626 kunmap_local(desc_kaddr); 627 628 mark_buffer_dirty(req->pr_desc_bh); 629 mark_buffer_dirty(req->pr_bitmap_bh); 630 nilfs_mdt_mark_dirty(inode); 631 632 brelse(req->pr_bitmap_bh); 633 brelse(req->pr_desc_bh); 634} 635 636/** 637 * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object 638 * @inode: inode of metadata file using this allocator 639 * @req: nilfs_palloc_req structure exchanged for the allocation 640 */ 641void nilfs_palloc_abort_alloc_entry(struct inode *inode, 642 struct nilfs_palloc_req *req) 643{ 644 struct nilfs_palloc_group_desc *desc; 645 void *desc_kaddr, *bitmap_kaddr; 646 unsigned char *bitmap; 647 unsigned long group, group_offset; 648 spinlock_t *lock; 649 650 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 651 desc_kaddr = kmap_local_page(req->pr_desc_bh->b_page); 652 desc = nilfs_palloc_block_get_group_desc(inode, group, 653 req->pr_desc_bh, desc_kaddr); 654 bitmap_kaddr = kmap_local_page(req->pr_bitmap_bh->b_page); 655 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh); 656 lock = nilfs_mdt_bgl_lock(inode, group); 657 658 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap)) 659 nilfs_warn(inode->i_sb, 660 "%s (ino=%lu): entry number %llu already freed", 661 __func__, inode->i_ino, 662 (unsigned long long)req->pr_entry_nr); 663 else 664 nilfs_palloc_group_desc_add_entries(desc, lock, 1); 665 666 kunmap_local(bitmap_kaddr); 667 kunmap_local(desc_kaddr); 668 669 brelse(req->pr_bitmap_bh); 670 brelse(req->pr_desc_bh); 671 672 req->pr_entry_nr = 0; 673 req->pr_bitmap_bh = NULL; 674 req->pr_desc_bh = NULL; 675} 676 677/** 678 * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object 679 * @inode: inode of metadata file using this allocator 680 * @req: nilfs_palloc_req structure exchanged for the removal 681 */ 682int nilfs_palloc_prepare_free_entry(struct inode *inode, 683 struct nilfs_palloc_req *req) 684{ 685 struct buffer_head *desc_bh, *bitmap_bh; 686 unsigned long group, group_offset; 687 int ret; 688 689 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 690 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 691 if (ret < 0) 692 return ret; 693 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh); 694 if (ret < 0) { 695 brelse(desc_bh); 696 return ret; 697 } 698 699 req->pr_desc_bh = desc_bh; 700 req->pr_bitmap_bh = bitmap_bh; 701 return 0; 702} 703 704/** 705 * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object 706 * @inode: inode of metadata file using this allocator 707 * @req: nilfs_palloc_req structure exchanged for the removal 708 */ 709void nilfs_palloc_abort_free_entry(struct inode *inode, 710 struct nilfs_palloc_req *req) 711{ 712 brelse(req->pr_bitmap_bh); 713 brelse(req->pr_desc_bh); 714 715 req->pr_entry_nr = 0; 716 req->pr_bitmap_bh = NULL; 717 req->pr_desc_bh = NULL; 718} 719 720/** 721 * nilfs_palloc_freev - deallocate a set of persistent objects 722 * @inode: inode of metadata file using this allocator 723 * @entry_nrs: array of entry numbers to be deallocated 724 * @nitems: number of entries stored in @entry_nrs 725 */ 726int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems) 727{ 728 struct buffer_head *desc_bh, *bitmap_bh; 729 struct nilfs_palloc_group_desc *desc; 730 unsigned char *bitmap; 731 void *desc_kaddr, *bitmap_kaddr; 732 unsigned long group, group_offset; 733 __u64 group_min_nr, last_nrs[8]; 734 const unsigned long epg = nilfs_palloc_entries_per_group(inode); 735 const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block; 736 unsigned int entry_start, end, pos; 737 spinlock_t *lock; 738 int i, j, k, ret; 739 u32 nfree; 740 741 for (i = 0; i < nitems; i = j) { 742 int change_group = false; 743 int nempties = 0, n = 0; 744 745 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset); 746 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh); 747 if (ret < 0) 748 return ret; 749 ret = nilfs_palloc_get_bitmap_block(inode, group, 0, 750 &bitmap_bh); 751 if (ret < 0) { 752 brelse(desc_bh); 753 return ret; 754 } 755 756 /* Get the first entry number of the group */ 757 group_min_nr = (__u64)group * epg; 758 759 bitmap_kaddr = kmap_local_page(bitmap_bh->b_page); 760 bitmap = bitmap_kaddr + bh_offset(bitmap_bh); 761 lock = nilfs_mdt_bgl_lock(inode, group); 762 763 j = i; 764 entry_start = rounddown(group_offset, epb); 765 do { 766 if (!nilfs_clear_bit_atomic(lock, group_offset, 767 bitmap)) { 768 nilfs_warn(inode->i_sb, 769 "%s (ino=%lu): entry number %llu already freed", 770 __func__, inode->i_ino, 771 (unsigned long long)entry_nrs[j]); 772 } else { 773 n++; 774 } 775 776 j++; 777 if (j >= nitems || entry_nrs[j] < group_min_nr || 778 entry_nrs[j] >= group_min_nr + epg) { 779 change_group = true; 780 } else { 781 group_offset = entry_nrs[j] - group_min_nr; 782 if (group_offset >= entry_start && 783 group_offset < entry_start + epb) { 784 /* This entry is in the same block */ 785 continue; 786 } 787 } 788 789 /* Test if the entry block is empty or not */ 790 end = entry_start + epb; 791 pos = nilfs_find_next_bit(bitmap, end, entry_start); 792 if (pos >= end) { 793 last_nrs[nempties++] = entry_nrs[j - 1]; 794 if (nempties >= ARRAY_SIZE(last_nrs)) 795 break; 796 } 797 798 if (change_group) 799 break; 800 801 /* Go on to the next entry block */ 802 entry_start = rounddown(group_offset, epb); 803 } while (true); 804 805 kunmap_local(bitmap_kaddr); 806 mark_buffer_dirty(bitmap_bh); 807 brelse(bitmap_bh); 808 809 for (k = 0; k < nempties; k++) { 810 ret = nilfs_palloc_delete_entry_block(inode, 811 last_nrs[k]); 812 if (ret && ret != -ENOENT) 813 nilfs_warn(inode->i_sb, 814 "error %d deleting block that object (entry=%llu, ino=%lu) belongs to", 815 ret, (unsigned long long)last_nrs[k], 816 inode->i_ino); 817 } 818 819 desc_kaddr = kmap_local_page(desc_bh->b_page); 820 desc = nilfs_palloc_block_get_group_desc( 821 inode, group, desc_bh, desc_kaddr); 822 nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n); 823 kunmap_local(desc_kaddr); 824 mark_buffer_dirty(desc_bh); 825 nilfs_mdt_mark_dirty(inode); 826 brelse(desc_bh); 827 828 if (nfree == nilfs_palloc_entries_per_group(inode)) { 829 ret = nilfs_palloc_delete_bitmap_block(inode, group); 830 if (ret && ret != -ENOENT) 831 nilfs_warn(inode->i_sb, 832 "error %d deleting bitmap block of group=%lu, ino=%lu", 833 ret, group, inode->i_ino); 834 } 835 } 836 return 0; 837} 838 839void nilfs_palloc_setup_cache(struct inode *inode, 840 struct nilfs_palloc_cache *cache) 841{ 842 NILFS_MDT(inode)->mi_palloc_cache = cache; 843 spin_lock_init(&cache->lock); 844} 845 846void nilfs_palloc_clear_cache(struct inode *inode) 847{ 848 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 849 850 spin_lock(&cache->lock); 851 brelse(cache->prev_desc.bh); 852 brelse(cache->prev_bitmap.bh); 853 brelse(cache->prev_entry.bh); 854 cache->prev_desc.bh = NULL; 855 cache->prev_bitmap.bh = NULL; 856 cache->prev_entry.bh = NULL; 857 spin_unlock(&cache->lock); 858} 859 860void nilfs_palloc_destroy_cache(struct inode *inode) 861{ 862 nilfs_palloc_clear_cache(inode); 863 NILFS_MDT(inode)->mi_palloc_cache = NULL; 864} 865