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 */ 25 static inline unsigned long 26 nilfs_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 */ 36 static inline unsigned long 37 nilfs_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 */ 47 int 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 */ 82 static 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 */ 99 static unsigned long 100 nilfs_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 */ 115 static unsigned long 116 nilfs_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 */ 129 static unsigned long 130 nilfs_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 */ 147 static u32 148 nilfs_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 */ 165 static unsigned long 166 nilfs_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 * @from: kernel address mapped for a chunk of the block 181 * 182 * This function does not yet support the case where block size > PAGE_SIZE. 183 */ 184 static void nilfs_palloc_desc_block_init(struct inode *inode, 185 struct buffer_head *bh, void *from) 186 { 187 struct nilfs_palloc_group_desc *desc = from; 188 unsigned long n = nilfs_palloc_groups_per_desc_block(inode); 189 __le32 nfrees; 190 191 nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode)); 192 while (n-- > 0) { 193 desc->pg_nfrees = nfrees; 194 desc++; 195 } 196 } 197 198 static int nilfs_palloc_get_block(struct inode *inode, unsigned long blkoff, 199 int create, 200 void (*init_block)(struct inode *, 201 struct buffer_head *, 202 void *), 203 struct buffer_head **bhp, 204 struct nilfs_bh_assoc *prev, 205 spinlock_t *lock) 206 { 207 int ret; 208 209 spin_lock(lock); 210 if (prev->bh && blkoff == prev->blkoff && 211 likely(buffer_uptodate(prev->bh))) { 212 get_bh(prev->bh); 213 *bhp = prev->bh; 214 spin_unlock(lock); 215 return 0; 216 } 217 spin_unlock(lock); 218 219 ret = nilfs_mdt_get_block(inode, blkoff, create, init_block, bhp); 220 if (!ret) { 221 spin_lock(lock); 222 /* 223 * The following code must be safe for change of the 224 * cache contents during the get block call. 225 */ 226 brelse(prev->bh); 227 get_bh(*bhp); 228 prev->bh = *bhp; 229 prev->blkoff = blkoff; 230 spin_unlock(lock); 231 } 232 return ret; 233 } 234 235 /** 236 * nilfs_palloc_delete_block - delete a block on the persistent allocator file 237 * @inode: inode of metadata file using this allocator 238 * @blkoff: block offset 239 * @prev: nilfs_bh_assoc struct of the last used buffer 240 * @lock: spin lock protecting @prev 241 */ 242 static int nilfs_palloc_delete_block(struct inode *inode, unsigned long blkoff, 243 struct nilfs_bh_assoc *prev, 244 spinlock_t *lock) 245 { 246 spin_lock(lock); 247 if (prev->bh && blkoff == prev->blkoff) { 248 brelse(prev->bh); 249 prev->bh = NULL; 250 } 251 spin_unlock(lock); 252 return nilfs_mdt_delete_block(inode, blkoff); 253 } 254 255 /** 256 * nilfs_palloc_get_desc_block - get buffer head of a group descriptor block 257 * @inode: inode of metadata file using this allocator 258 * @group: group number 259 * @create: create flag 260 * @bhp: pointer to store the resultant buffer head 261 */ 262 static int nilfs_palloc_get_desc_block(struct inode *inode, 263 unsigned long group, 264 int create, struct buffer_head **bhp) 265 { 266 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 267 268 return nilfs_palloc_get_block(inode, 269 nilfs_palloc_desc_blkoff(inode, group), 270 create, nilfs_palloc_desc_block_init, 271 bhp, &cache->prev_desc, &cache->lock); 272 } 273 274 /** 275 * nilfs_palloc_get_bitmap_block - get buffer head of a bitmap block 276 * @inode: inode of metadata file using this allocator 277 * @group: group number 278 * @create: create flag 279 * @bhp: pointer to store the resultant buffer head 280 */ 281 static int nilfs_palloc_get_bitmap_block(struct inode *inode, 282 unsigned long group, 283 int create, struct buffer_head **bhp) 284 { 285 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 286 287 return nilfs_palloc_get_block(inode, 288 nilfs_palloc_bitmap_blkoff(inode, group), 289 create, NULL, bhp, 290 &cache->prev_bitmap, &cache->lock); 291 } 292 293 /** 294 * nilfs_palloc_delete_bitmap_block - delete a bitmap block 295 * @inode: inode of metadata file using this allocator 296 * @group: group number 297 */ 298 static int nilfs_palloc_delete_bitmap_block(struct inode *inode, 299 unsigned long group) 300 { 301 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 302 303 return nilfs_palloc_delete_block(inode, 304 nilfs_palloc_bitmap_blkoff(inode, 305 group), 306 &cache->prev_bitmap, &cache->lock); 307 } 308 309 /** 310 * nilfs_palloc_get_entry_block - get buffer head of an entry block 311 * @inode: inode of metadata file using this allocator 312 * @nr: serial number of the entry (e.g. inode number) 313 * @create: create flag 314 * @bhp: pointer to store the resultant buffer head 315 */ 316 int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr, 317 int create, struct buffer_head **bhp) 318 { 319 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 320 321 return nilfs_palloc_get_block(inode, 322 nilfs_palloc_entry_blkoff(inode, nr), 323 create, NULL, bhp, 324 &cache->prev_entry, &cache->lock); 325 } 326 327 /** 328 * nilfs_palloc_delete_entry_block - delete an entry block 329 * @inode: inode of metadata file using this allocator 330 * @nr: serial number of the entry 331 */ 332 static int nilfs_palloc_delete_entry_block(struct inode *inode, __u64 nr) 333 { 334 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 335 336 return nilfs_palloc_delete_block(inode, 337 nilfs_palloc_entry_blkoff(inode, nr), 338 &cache->prev_entry, &cache->lock); 339 } 340 341 /** 342 * nilfs_palloc_group_desc_offset - calculate the byte offset of a group 343 * descriptor in the folio containing it 344 * @inode: inode of metadata file using this allocator 345 * @group: group number 346 * @bh: buffer head of the group descriptor block 347 * 348 * Return: Byte offset in the folio of the group descriptor for @group. 349 */ 350 static size_t nilfs_palloc_group_desc_offset(const struct inode *inode, 351 unsigned long group, 352 const struct buffer_head *bh) 353 { 354 return offset_in_folio(bh->b_folio, bh->b_data) + 355 sizeof(struct nilfs_palloc_group_desc) * 356 (group % nilfs_palloc_groups_per_desc_block(inode)); 357 } 358 359 /** 360 * nilfs_palloc_bitmap_offset - calculate the byte offset of a bitmap block 361 * in the folio containing it 362 * @bh: buffer head of the bitmap block 363 * 364 * Return: Byte offset in the folio of the bitmap block for @bh. 365 */ 366 static size_t nilfs_palloc_bitmap_offset(const struct buffer_head *bh) 367 { 368 return offset_in_folio(bh->b_folio, bh->b_data); 369 } 370 371 /** 372 * nilfs_palloc_entry_offset - calculate the byte offset of an entry in the 373 * folio containing it 374 * @inode: inode of metadata file using this allocator 375 * @nr: serial number of the entry (e.g. inode number) 376 * @bh: buffer head of the entry block 377 * 378 * Return: Byte offset in the folio of the entry @nr. 379 */ 380 size_t nilfs_palloc_entry_offset(const struct inode *inode, __u64 nr, 381 const struct buffer_head *bh) 382 { 383 unsigned long entry_index_in_group, entry_index_in_block; 384 385 nilfs_palloc_group(inode, nr, &entry_index_in_group); 386 entry_index_in_block = entry_index_in_group % 387 NILFS_MDT(inode)->mi_entries_per_block; 388 389 return offset_in_folio(bh->b_folio, bh->b_data) + 390 entry_index_in_block * NILFS_MDT(inode)->mi_entry_size; 391 } 392 393 /** 394 * nilfs_palloc_find_available_slot - find available slot in a group 395 * @bitmap: bitmap of the group 396 * @target: offset number of an entry in the group (start point) 397 * @bsize: size in bits 398 * @lock: spin lock protecting @bitmap 399 * @wrap: whether to wrap around 400 */ 401 static int nilfs_palloc_find_available_slot(unsigned char *bitmap, 402 unsigned long target, 403 unsigned int bsize, 404 spinlock_t *lock, bool wrap) 405 { 406 int pos, end = bsize; 407 408 if (likely(target < bsize)) { 409 pos = target; 410 do { 411 pos = nilfs_find_next_zero_bit(bitmap, end, pos); 412 if (pos >= end) 413 break; 414 if (!nilfs_set_bit_atomic(lock, pos, bitmap)) 415 return pos; 416 } while (++pos < end); 417 418 end = target; 419 } 420 if (!wrap) 421 return -ENOSPC; 422 423 /* wrap around */ 424 for (pos = 0; pos < end; pos++) { 425 pos = nilfs_find_next_zero_bit(bitmap, end, pos); 426 if (pos >= end) 427 break; 428 if (!nilfs_set_bit_atomic(lock, pos, bitmap)) 429 return pos; 430 } 431 432 return -ENOSPC; 433 } 434 435 /** 436 * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups 437 * in a group descriptor block 438 * @inode: inode of metadata file using this allocator 439 * @curr: current group number 440 * @max: maximum number of groups 441 */ 442 static unsigned long 443 nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode, 444 unsigned long curr, unsigned long max) 445 { 446 return min_t(unsigned long, 447 nilfs_palloc_groups_per_desc_block(inode) - 448 curr % nilfs_palloc_groups_per_desc_block(inode), 449 max - curr + 1); 450 } 451 452 /** 453 * nilfs_palloc_count_desc_blocks - count descriptor blocks number 454 * @inode: inode of metadata file using this allocator 455 * @desc_blocks: descriptor blocks number [out] 456 */ 457 static int nilfs_palloc_count_desc_blocks(struct inode *inode, 458 unsigned long *desc_blocks) 459 { 460 __u64 blknum; 461 int ret; 462 463 ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum); 464 if (likely(!ret)) 465 *desc_blocks = DIV_ROUND_UP( 466 (unsigned long)blknum, 467 NILFS_MDT(inode)->mi_blocks_per_desc_block); 468 return ret; 469 } 470 471 /** 472 * nilfs_palloc_mdt_file_can_grow - check potential opportunity for 473 * MDT file growing 474 * @inode: inode of metadata file using this allocator 475 * @desc_blocks: known current descriptor blocks count 476 */ 477 static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode, 478 unsigned long desc_blocks) 479 { 480 return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) < 481 nilfs_palloc_groups_count(inode); 482 } 483 484 /** 485 * nilfs_palloc_count_max_entries - count max number of entries that can be 486 * described by descriptor blocks count 487 * @inode: inode of metadata file using this allocator 488 * @nused: current number of used entries 489 * @nmaxp: max number of entries [out] 490 */ 491 int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp) 492 { 493 unsigned long desc_blocks = 0; 494 u64 entries_per_desc_block, nmax; 495 int err; 496 497 err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks); 498 if (unlikely(err)) 499 return err; 500 501 entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) * 502 nilfs_palloc_groups_per_desc_block(inode); 503 nmax = entries_per_desc_block * desc_blocks; 504 505 if (nused == nmax && 506 nilfs_palloc_mdt_file_can_grow(inode, desc_blocks)) 507 nmax += entries_per_desc_block; 508 509 if (nused > nmax) 510 return -ERANGE; 511 512 *nmaxp = nmax; 513 return 0; 514 } 515 516 /** 517 * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object 518 * @inode: inode of metadata file using this allocator 519 * @req: nilfs_palloc_req structure exchanged for the allocation 520 * @wrap: whether to wrap around 521 */ 522 int nilfs_palloc_prepare_alloc_entry(struct inode *inode, 523 struct nilfs_palloc_req *req, bool wrap) 524 { 525 struct buffer_head *desc_bh, *bitmap_bh; 526 struct nilfs_palloc_group_desc *desc; 527 unsigned char *bitmap; 528 size_t doff, boff; 529 unsigned long group, maxgroup, ngroups; 530 unsigned long group_offset, maxgroup_offset; 531 unsigned long n, entries_per_group; 532 unsigned long i, j; 533 spinlock_t *lock; 534 int pos, ret; 535 536 ngroups = nilfs_palloc_groups_count(inode); 537 maxgroup = ngroups - 1; 538 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 539 entries_per_group = nilfs_palloc_entries_per_group(inode); 540 541 for (i = 0; i < ngroups; i += n) { 542 if (group >= ngroups && wrap) { 543 /* wrap around */ 544 group = 0; 545 maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr, 546 &maxgroup_offset) - 1; 547 } 548 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 549 if (ret < 0) 550 return ret; 551 552 doff = nilfs_palloc_group_desc_offset(inode, group, desc_bh); 553 desc = kmap_local_folio(desc_bh->b_folio, doff); 554 n = nilfs_palloc_rest_groups_in_desc_block(inode, group, 555 maxgroup); 556 for (j = 0; j < n; j++, group++, group_offset = 0) { 557 lock = nilfs_mdt_bgl_lock(inode, group); 558 if (nilfs_palloc_group_desc_nfrees(&desc[j], lock) == 0) 559 continue; 560 561 kunmap_local(desc); 562 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, 563 &bitmap_bh); 564 if (unlikely(ret < 0)) { 565 brelse(desc_bh); 566 return ret; 567 } 568 569 /* 570 * Re-kmap the folio containing the first (and 571 * subsequent) group descriptors. 572 */ 573 desc = kmap_local_folio(desc_bh->b_folio, doff); 574 575 boff = nilfs_palloc_bitmap_offset(bitmap_bh); 576 bitmap = kmap_local_folio(bitmap_bh->b_folio, boff); 577 pos = nilfs_palloc_find_available_slot( 578 bitmap, group_offset, entries_per_group, lock, 579 wrap); 580 /* 581 * Since the search for a free slot in the second and 582 * subsequent bitmap blocks always starts from the 583 * beginning, the wrap flag only has an effect on the 584 * first search. 585 */ 586 kunmap_local(bitmap); 587 if (pos >= 0) 588 goto found; 589 590 brelse(bitmap_bh); 591 } 592 593 kunmap_local(desc); 594 brelse(desc_bh); 595 } 596 597 /* no entries left */ 598 return -ENOSPC; 599 600 found: 601 /* found a free entry */ 602 nilfs_palloc_group_desc_add_entries(&desc[j], lock, -1); 603 req->pr_entry_nr = entries_per_group * group + pos; 604 kunmap_local(desc); 605 606 req->pr_desc_bh = desc_bh; 607 req->pr_bitmap_bh = bitmap_bh; 608 return 0; 609 } 610 611 /** 612 * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object 613 * @inode: inode of metadata file using this allocator 614 * @req: nilfs_palloc_req structure exchanged for the allocation 615 */ 616 void nilfs_palloc_commit_alloc_entry(struct inode *inode, 617 struct nilfs_palloc_req *req) 618 { 619 mark_buffer_dirty(req->pr_bitmap_bh); 620 mark_buffer_dirty(req->pr_desc_bh); 621 nilfs_mdt_mark_dirty(inode); 622 623 brelse(req->pr_bitmap_bh); 624 brelse(req->pr_desc_bh); 625 } 626 627 /** 628 * nilfs_palloc_commit_free_entry - finish deallocating a persistent object 629 * @inode: inode of metadata file using this allocator 630 * @req: nilfs_palloc_req structure exchanged for the removal 631 */ 632 void nilfs_palloc_commit_free_entry(struct inode *inode, 633 struct nilfs_palloc_req *req) 634 { 635 unsigned long group, group_offset; 636 size_t doff, boff; 637 struct nilfs_palloc_group_desc *desc; 638 unsigned char *bitmap; 639 spinlock_t *lock; 640 641 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 642 doff = nilfs_palloc_group_desc_offset(inode, group, req->pr_desc_bh); 643 desc = kmap_local_folio(req->pr_desc_bh->b_folio, doff); 644 645 boff = nilfs_palloc_bitmap_offset(req->pr_bitmap_bh); 646 bitmap = kmap_local_folio(req->pr_bitmap_bh->b_folio, boff); 647 lock = nilfs_mdt_bgl_lock(inode, group); 648 649 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap)) 650 nilfs_warn(inode->i_sb, 651 "%s (ino=%lu): entry number %llu already freed", 652 __func__, inode->i_ino, 653 (unsigned long long)req->pr_entry_nr); 654 else 655 nilfs_palloc_group_desc_add_entries(desc, lock, 1); 656 657 kunmap_local(bitmap); 658 kunmap_local(desc); 659 660 mark_buffer_dirty(req->pr_desc_bh); 661 mark_buffer_dirty(req->pr_bitmap_bh); 662 nilfs_mdt_mark_dirty(inode); 663 664 brelse(req->pr_bitmap_bh); 665 brelse(req->pr_desc_bh); 666 } 667 668 /** 669 * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object 670 * @inode: inode of metadata file using this allocator 671 * @req: nilfs_palloc_req structure exchanged for the allocation 672 */ 673 void nilfs_palloc_abort_alloc_entry(struct inode *inode, 674 struct nilfs_palloc_req *req) 675 { 676 struct nilfs_palloc_group_desc *desc; 677 size_t doff, boff; 678 unsigned char *bitmap; 679 unsigned long group, group_offset; 680 spinlock_t *lock; 681 682 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 683 doff = nilfs_palloc_group_desc_offset(inode, group, req->pr_desc_bh); 684 desc = kmap_local_folio(req->pr_desc_bh->b_folio, doff); 685 686 boff = nilfs_palloc_bitmap_offset(req->pr_bitmap_bh); 687 bitmap = kmap_local_folio(req->pr_bitmap_bh->b_folio, boff); 688 lock = nilfs_mdt_bgl_lock(inode, group); 689 690 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap)) 691 nilfs_warn(inode->i_sb, 692 "%s (ino=%lu): entry number %llu already freed", 693 __func__, inode->i_ino, 694 (unsigned long long)req->pr_entry_nr); 695 else 696 nilfs_palloc_group_desc_add_entries(desc, lock, 1); 697 698 kunmap_local(bitmap); 699 kunmap_local(desc); 700 701 brelse(req->pr_bitmap_bh); 702 brelse(req->pr_desc_bh); 703 704 req->pr_entry_nr = 0; 705 req->pr_bitmap_bh = NULL; 706 req->pr_desc_bh = NULL; 707 } 708 709 /** 710 * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object 711 * @inode: inode of metadata file using this allocator 712 * @req: nilfs_palloc_req structure exchanged for the removal 713 */ 714 int nilfs_palloc_prepare_free_entry(struct inode *inode, 715 struct nilfs_palloc_req *req) 716 { 717 struct buffer_head *desc_bh, *bitmap_bh; 718 unsigned long group, group_offset; 719 int ret; 720 721 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 722 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 723 if (ret < 0) 724 return ret; 725 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh); 726 if (ret < 0) { 727 brelse(desc_bh); 728 return ret; 729 } 730 731 req->pr_desc_bh = desc_bh; 732 req->pr_bitmap_bh = bitmap_bh; 733 return 0; 734 } 735 736 /** 737 * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object 738 * @inode: inode of metadata file using this allocator 739 * @req: nilfs_palloc_req structure exchanged for the removal 740 */ 741 void nilfs_palloc_abort_free_entry(struct inode *inode, 742 struct nilfs_palloc_req *req) 743 { 744 brelse(req->pr_bitmap_bh); 745 brelse(req->pr_desc_bh); 746 747 req->pr_entry_nr = 0; 748 req->pr_bitmap_bh = NULL; 749 req->pr_desc_bh = NULL; 750 } 751 752 /** 753 * nilfs_palloc_freev - deallocate a set of persistent objects 754 * @inode: inode of metadata file using this allocator 755 * @entry_nrs: array of entry numbers to be deallocated 756 * @nitems: number of entries stored in @entry_nrs 757 */ 758 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems) 759 { 760 struct buffer_head *desc_bh, *bitmap_bh; 761 struct nilfs_palloc_group_desc *desc; 762 unsigned char *bitmap; 763 size_t doff, boff; 764 unsigned long group, group_offset; 765 __u64 group_min_nr, last_nrs[8]; 766 const unsigned long epg = nilfs_palloc_entries_per_group(inode); 767 const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block; 768 unsigned int entry_start, end, pos; 769 spinlock_t *lock; 770 int i, j, k, ret; 771 u32 nfree; 772 773 for (i = 0; i < nitems; i = j) { 774 int change_group = false; 775 int nempties = 0, n = 0; 776 777 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset); 778 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh); 779 if (ret < 0) 780 return ret; 781 ret = nilfs_palloc_get_bitmap_block(inode, group, 0, 782 &bitmap_bh); 783 if (ret < 0) { 784 brelse(desc_bh); 785 return ret; 786 } 787 788 /* Get the first entry number of the group */ 789 group_min_nr = (__u64)group * epg; 790 791 boff = nilfs_palloc_bitmap_offset(bitmap_bh); 792 bitmap = kmap_local_folio(bitmap_bh->b_folio, boff); 793 lock = nilfs_mdt_bgl_lock(inode, group); 794 795 j = i; 796 entry_start = rounddown(group_offset, epb); 797 do { 798 if (!nilfs_clear_bit_atomic(lock, group_offset, 799 bitmap)) { 800 nilfs_warn(inode->i_sb, 801 "%s (ino=%lu): entry number %llu already freed", 802 __func__, inode->i_ino, 803 (unsigned long long)entry_nrs[j]); 804 } else { 805 n++; 806 } 807 808 j++; 809 if (j >= nitems || entry_nrs[j] < group_min_nr || 810 entry_nrs[j] >= group_min_nr + epg) { 811 change_group = true; 812 } else { 813 group_offset = entry_nrs[j] - group_min_nr; 814 if (group_offset >= entry_start && 815 group_offset < entry_start + epb) { 816 /* This entry is in the same block */ 817 continue; 818 } 819 } 820 821 /* Test if the entry block is empty or not */ 822 end = entry_start + epb; 823 pos = nilfs_find_next_bit(bitmap, end, entry_start); 824 if (pos >= end) { 825 last_nrs[nempties++] = entry_nrs[j - 1]; 826 if (nempties >= ARRAY_SIZE(last_nrs)) 827 break; 828 } 829 830 if (change_group) 831 break; 832 833 /* Go on to the next entry block */ 834 entry_start = rounddown(group_offset, epb); 835 } while (true); 836 837 kunmap_local(bitmap); 838 mark_buffer_dirty(bitmap_bh); 839 brelse(bitmap_bh); 840 841 for (k = 0; k < nempties; k++) { 842 ret = nilfs_palloc_delete_entry_block(inode, 843 last_nrs[k]); 844 if (ret && ret != -ENOENT) 845 nilfs_warn(inode->i_sb, 846 "error %d deleting block that object (entry=%llu, ino=%lu) belongs to", 847 ret, (unsigned long long)last_nrs[k], 848 inode->i_ino); 849 } 850 851 doff = nilfs_palloc_group_desc_offset(inode, group, desc_bh); 852 desc = kmap_local_folio(desc_bh->b_folio, doff); 853 nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n); 854 kunmap_local(desc); 855 mark_buffer_dirty(desc_bh); 856 nilfs_mdt_mark_dirty(inode); 857 brelse(desc_bh); 858 859 if (nfree == nilfs_palloc_entries_per_group(inode)) { 860 ret = nilfs_palloc_delete_bitmap_block(inode, group); 861 if (ret && ret != -ENOENT) 862 nilfs_warn(inode->i_sb, 863 "error %d deleting bitmap block of group=%lu, ino=%lu", 864 ret, group, inode->i_ino); 865 } 866 } 867 return 0; 868 } 869 870 void nilfs_palloc_setup_cache(struct inode *inode, 871 struct nilfs_palloc_cache *cache) 872 { 873 NILFS_MDT(inode)->mi_palloc_cache = cache; 874 spin_lock_init(&cache->lock); 875 } 876 877 void nilfs_palloc_clear_cache(struct inode *inode) 878 { 879 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 880 881 spin_lock(&cache->lock); 882 brelse(cache->prev_desc.bh); 883 brelse(cache->prev_bitmap.bh); 884 brelse(cache->prev_entry.bh); 885 cache->prev_desc.bh = NULL; 886 cache->prev_bitmap.bh = NULL; 887 cache->prev_entry.bh = NULL; 888 spin_unlock(&cache->lock); 889 } 890 891 void nilfs_palloc_destroy_cache(struct inode *inode) 892 { 893 nilfs_palloc_clear_cache(inode); 894 NILFS_MDT(inode)->mi_palloc_cache = NULL; 895 } 896