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 * @kaddr: kernel address mapped for the page including the buffer 181 */ 182 static 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 196 static 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 */ 240 static 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 */ 260 static 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 */ 279 static 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 */ 296 static 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 */ 314 int 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 */ 330 static 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 */ 346 static struct nilfs_palloc_group_desc * 347 nilfs_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 */ 362 void *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 * @wrap: whether to wrap around 381 */ 382 static int nilfs_palloc_find_available_slot(unsigned char *bitmap, 383 unsigned long target, 384 unsigned int bsize, 385 spinlock_t *lock, bool wrap) 386 { 387 int pos, end = bsize; 388 389 if (likely(target < bsize)) { 390 pos = target; 391 do { 392 pos = nilfs_find_next_zero_bit(bitmap, end, pos); 393 if (pos >= end) 394 break; 395 if (!nilfs_set_bit_atomic(lock, pos, bitmap)) 396 return pos; 397 } while (++pos < end); 398 399 end = target; 400 } 401 if (!wrap) 402 return -ENOSPC; 403 404 /* wrap around */ 405 for (pos = 0; pos < end; pos++) { 406 pos = nilfs_find_next_zero_bit(bitmap, end, pos); 407 if (pos >= end) 408 break; 409 if (!nilfs_set_bit_atomic(lock, pos, bitmap)) 410 return pos; 411 } 412 413 return -ENOSPC; 414 } 415 416 /** 417 * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups 418 * in a group descriptor block 419 * @inode: inode of metadata file using this allocator 420 * @curr: current group number 421 * @max: maximum number of groups 422 */ 423 static unsigned long 424 nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode, 425 unsigned long curr, unsigned long max) 426 { 427 return min_t(unsigned long, 428 nilfs_palloc_groups_per_desc_block(inode) - 429 curr % nilfs_palloc_groups_per_desc_block(inode), 430 max - curr + 1); 431 } 432 433 /** 434 * nilfs_palloc_count_desc_blocks - count descriptor blocks number 435 * @inode: inode of metadata file using this allocator 436 * @desc_blocks: descriptor blocks number [out] 437 */ 438 static int nilfs_palloc_count_desc_blocks(struct inode *inode, 439 unsigned long *desc_blocks) 440 { 441 __u64 blknum; 442 int ret; 443 444 ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum); 445 if (likely(!ret)) 446 *desc_blocks = DIV_ROUND_UP( 447 (unsigned long)blknum, 448 NILFS_MDT(inode)->mi_blocks_per_desc_block); 449 return ret; 450 } 451 452 /** 453 * nilfs_palloc_mdt_file_can_grow - check potential opportunity for 454 * MDT file growing 455 * @inode: inode of metadata file using this allocator 456 * @desc_blocks: known current descriptor blocks count 457 */ 458 static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode, 459 unsigned long desc_blocks) 460 { 461 return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) < 462 nilfs_palloc_groups_count(inode); 463 } 464 465 /** 466 * nilfs_palloc_count_max_entries - count max number of entries that can be 467 * described by descriptor blocks count 468 * @inode: inode of metadata file using this allocator 469 * @nused: current number of used entries 470 * @nmaxp: max number of entries [out] 471 */ 472 int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp) 473 { 474 unsigned long desc_blocks = 0; 475 u64 entries_per_desc_block, nmax; 476 int err; 477 478 err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks); 479 if (unlikely(err)) 480 return err; 481 482 entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) * 483 nilfs_palloc_groups_per_desc_block(inode); 484 nmax = entries_per_desc_block * desc_blocks; 485 486 if (nused == nmax && 487 nilfs_palloc_mdt_file_can_grow(inode, desc_blocks)) 488 nmax += entries_per_desc_block; 489 490 if (nused > nmax) 491 return -ERANGE; 492 493 *nmaxp = nmax; 494 return 0; 495 } 496 497 /** 498 * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object 499 * @inode: inode of metadata file using this allocator 500 * @req: nilfs_palloc_req structure exchanged for the allocation 501 * @wrap: whether to wrap around 502 */ 503 int nilfs_palloc_prepare_alloc_entry(struct inode *inode, 504 struct nilfs_palloc_req *req, bool wrap) 505 { 506 struct buffer_head *desc_bh, *bitmap_bh; 507 struct nilfs_palloc_group_desc *desc; 508 unsigned char *bitmap; 509 void *desc_kaddr, *bitmap_kaddr; 510 unsigned long group, maxgroup, ngroups; 511 unsigned long group_offset, maxgroup_offset; 512 unsigned long n, entries_per_group; 513 unsigned long i, j; 514 spinlock_t *lock; 515 int pos, ret; 516 517 ngroups = nilfs_palloc_groups_count(inode); 518 maxgroup = ngroups - 1; 519 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 520 entries_per_group = nilfs_palloc_entries_per_group(inode); 521 522 for (i = 0; i < ngroups; i += n) { 523 if (group >= ngroups && wrap) { 524 /* wrap around */ 525 group = 0; 526 maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr, 527 &maxgroup_offset) - 1; 528 } 529 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 530 if (ret < 0) 531 return ret; 532 desc_kaddr = kmap_local_page(desc_bh->b_page); 533 desc = nilfs_palloc_block_get_group_desc( 534 inode, group, desc_bh, desc_kaddr); 535 n = nilfs_palloc_rest_groups_in_desc_block(inode, group, 536 maxgroup); 537 for (j = 0; j < n; j++, desc++, group++, group_offset = 0) { 538 lock = nilfs_mdt_bgl_lock(inode, group); 539 if (nilfs_palloc_group_desc_nfrees(desc, lock) == 0) 540 continue; 541 542 kunmap_local(desc_kaddr); 543 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, 544 &bitmap_bh); 545 if (unlikely(ret < 0)) { 546 brelse(desc_bh); 547 return ret; 548 } 549 550 desc_kaddr = kmap_local_page(desc_bh->b_page); 551 desc = nilfs_palloc_block_get_group_desc( 552 inode, group, desc_bh, desc_kaddr); 553 554 bitmap_kaddr = kmap_local_page(bitmap_bh->b_page); 555 bitmap = bitmap_kaddr + bh_offset(bitmap_bh); 556 pos = nilfs_palloc_find_available_slot( 557 bitmap, group_offset, entries_per_group, lock, 558 wrap); 559 /* 560 * Since the search for a free slot in the second and 561 * subsequent bitmap blocks always starts from the 562 * beginning, the wrap flag only has an effect on the 563 * first search. 564 */ 565 kunmap_local(bitmap_kaddr); 566 if (pos >= 0) 567 goto found; 568 569 brelse(bitmap_bh); 570 } 571 572 kunmap_local(desc_kaddr); 573 brelse(desc_bh); 574 } 575 576 /* no entries left */ 577 return -ENOSPC; 578 579 found: 580 /* found a free entry */ 581 nilfs_palloc_group_desc_add_entries(desc, lock, -1); 582 req->pr_entry_nr = entries_per_group * group + pos; 583 kunmap_local(desc_kaddr); 584 585 req->pr_desc_bh = desc_bh; 586 req->pr_bitmap_bh = bitmap_bh; 587 return 0; 588 } 589 590 /** 591 * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object 592 * @inode: inode of metadata file using this allocator 593 * @req: nilfs_palloc_req structure exchanged for the allocation 594 */ 595 void nilfs_palloc_commit_alloc_entry(struct inode *inode, 596 struct nilfs_palloc_req *req) 597 { 598 mark_buffer_dirty(req->pr_bitmap_bh); 599 mark_buffer_dirty(req->pr_desc_bh); 600 nilfs_mdt_mark_dirty(inode); 601 602 brelse(req->pr_bitmap_bh); 603 brelse(req->pr_desc_bh); 604 } 605 606 /** 607 * nilfs_palloc_commit_free_entry - finish deallocating a persistent object 608 * @inode: inode of metadata file using this allocator 609 * @req: nilfs_palloc_req structure exchanged for the removal 610 */ 611 void nilfs_palloc_commit_free_entry(struct inode *inode, 612 struct nilfs_palloc_req *req) 613 { 614 struct nilfs_palloc_group_desc *desc; 615 unsigned long group, group_offset; 616 unsigned char *bitmap; 617 void *desc_kaddr, *bitmap_kaddr; 618 spinlock_t *lock; 619 620 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 621 desc_kaddr = kmap_local_page(req->pr_desc_bh->b_page); 622 desc = nilfs_palloc_block_get_group_desc(inode, group, 623 req->pr_desc_bh, desc_kaddr); 624 bitmap_kaddr = kmap_local_page(req->pr_bitmap_bh->b_page); 625 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh); 626 lock = nilfs_mdt_bgl_lock(inode, group); 627 628 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap)) 629 nilfs_warn(inode->i_sb, 630 "%s (ino=%lu): entry number %llu already freed", 631 __func__, inode->i_ino, 632 (unsigned long long)req->pr_entry_nr); 633 else 634 nilfs_palloc_group_desc_add_entries(desc, lock, 1); 635 636 kunmap_local(bitmap_kaddr); 637 kunmap_local(desc_kaddr); 638 639 mark_buffer_dirty(req->pr_desc_bh); 640 mark_buffer_dirty(req->pr_bitmap_bh); 641 nilfs_mdt_mark_dirty(inode); 642 643 brelse(req->pr_bitmap_bh); 644 brelse(req->pr_desc_bh); 645 } 646 647 /** 648 * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object 649 * @inode: inode of metadata file using this allocator 650 * @req: nilfs_palloc_req structure exchanged for the allocation 651 */ 652 void nilfs_palloc_abort_alloc_entry(struct inode *inode, 653 struct nilfs_palloc_req *req) 654 { 655 struct nilfs_palloc_group_desc *desc; 656 void *desc_kaddr, *bitmap_kaddr; 657 unsigned char *bitmap; 658 unsigned long group, group_offset; 659 spinlock_t *lock; 660 661 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 662 desc_kaddr = kmap_local_page(req->pr_desc_bh->b_page); 663 desc = nilfs_palloc_block_get_group_desc(inode, group, 664 req->pr_desc_bh, desc_kaddr); 665 bitmap_kaddr = kmap_local_page(req->pr_bitmap_bh->b_page); 666 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh); 667 lock = nilfs_mdt_bgl_lock(inode, group); 668 669 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap)) 670 nilfs_warn(inode->i_sb, 671 "%s (ino=%lu): entry number %llu already freed", 672 __func__, inode->i_ino, 673 (unsigned long long)req->pr_entry_nr); 674 else 675 nilfs_palloc_group_desc_add_entries(desc, lock, 1); 676 677 kunmap_local(bitmap_kaddr); 678 kunmap_local(desc_kaddr); 679 680 brelse(req->pr_bitmap_bh); 681 brelse(req->pr_desc_bh); 682 683 req->pr_entry_nr = 0; 684 req->pr_bitmap_bh = NULL; 685 req->pr_desc_bh = NULL; 686 } 687 688 /** 689 * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object 690 * @inode: inode of metadata file using this allocator 691 * @req: nilfs_palloc_req structure exchanged for the removal 692 */ 693 int nilfs_palloc_prepare_free_entry(struct inode *inode, 694 struct nilfs_palloc_req *req) 695 { 696 struct buffer_head *desc_bh, *bitmap_bh; 697 unsigned long group, group_offset; 698 int ret; 699 700 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 701 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 702 if (ret < 0) 703 return ret; 704 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh); 705 if (ret < 0) { 706 brelse(desc_bh); 707 return ret; 708 } 709 710 req->pr_desc_bh = desc_bh; 711 req->pr_bitmap_bh = bitmap_bh; 712 return 0; 713 } 714 715 /** 716 * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object 717 * @inode: inode of metadata file using this allocator 718 * @req: nilfs_palloc_req structure exchanged for the removal 719 */ 720 void nilfs_palloc_abort_free_entry(struct inode *inode, 721 struct nilfs_palloc_req *req) 722 { 723 brelse(req->pr_bitmap_bh); 724 brelse(req->pr_desc_bh); 725 726 req->pr_entry_nr = 0; 727 req->pr_bitmap_bh = NULL; 728 req->pr_desc_bh = NULL; 729 } 730 731 /** 732 * nilfs_palloc_freev - deallocate a set of persistent objects 733 * @inode: inode of metadata file using this allocator 734 * @entry_nrs: array of entry numbers to be deallocated 735 * @nitems: number of entries stored in @entry_nrs 736 */ 737 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems) 738 { 739 struct buffer_head *desc_bh, *bitmap_bh; 740 struct nilfs_palloc_group_desc *desc; 741 unsigned char *bitmap; 742 void *desc_kaddr, *bitmap_kaddr; 743 unsigned long group, group_offset; 744 __u64 group_min_nr, last_nrs[8]; 745 const unsigned long epg = nilfs_palloc_entries_per_group(inode); 746 const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block; 747 unsigned int entry_start, end, pos; 748 spinlock_t *lock; 749 int i, j, k, ret; 750 u32 nfree; 751 752 for (i = 0; i < nitems; i = j) { 753 int change_group = false; 754 int nempties = 0, n = 0; 755 756 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset); 757 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh); 758 if (ret < 0) 759 return ret; 760 ret = nilfs_palloc_get_bitmap_block(inode, group, 0, 761 &bitmap_bh); 762 if (ret < 0) { 763 brelse(desc_bh); 764 return ret; 765 } 766 767 /* Get the first entry number of the group */ 768 group_min_nr = (__u64)group * epg; 769 770 bitmap_kaddr = kmap_local_page(bitmap_bh->b_page); 771 bitmap = bitmap_kaddr + bh_offset(bitmap_bh); 772 lock = nilfs_mdt_bgl_lock(inode, group); 773 774 j = i; 775 entry_start = rounddown(group_offset, epb); 776 do { 777 if (!nilfs_clear_bit_atomic(lock, group_offset, 778 bitmap)) { 779 nilfs_warn(inode->i_sb, 780 "%s (ino=%lu): entry number %llu already freed", 781 __func__, inode->i_ino, 782 (unsigned long long)entry_nrs[j]); 783 } else { 784 n++; 785 } 786 787 j++; 788 if (j >= nitems || entry_nrs[j] < group_min_nr || 789 entry_nrs[j] >= group_min_nr + epg) { 790 change_group = true; 791 } else { 792 group_offset = entry_nrs[j] - group_min_nr; 793 if (group_offset >= entry_start && 794 group_offset < entry_start + epb) { 795 /* This entry is in the same block */ 796 continue; 797 } 798 } 799 800 /* Test if the entry block is empty or not */ 801 end = entry_start + epb; 802 pos = nilfs_find_next_bit(bitmap, end, entry_start); 803 if (pos >= end) { 804 last_nrs[nempties++] = entry_nrs[j - 1]; 805 if (nempties >= ARRAY_SIZE(last_nrs)) 806 break; 807 } 808 809 if (change_group) 810 break; 811 812 /* Go on to the next entry block */ 813 entry_start = rounddown(group_offset, epb); 814 } while (true); 815 816 kunmap_local(bitmap_kaddr); 817 mark_buffer_dirty(bitmap_bh); 818 brelse(bitmap_bh); 819 820 for (k = 0; k < nempties; k++) { 821 ret = nilfs_palloc_delete_entry_block(inode, 822 last_nrs[k]); 823 if (ret && ret != -ENOENT) 824 nilfs_warn(inode->i_sb, 825 "error %d deleting block that object (entry=%llu, ino=%lu) belongs to", 826 ret, (unsigned long long)last_nrs[k], 827 inode->i_ino); 828 } 829 830 desc_kaddr = kmap_local_page(desc_bh->b_page); 831 desc = nilfs_palloc_block_get_group_desc( 832 inode, group, desc_bh, desc_kaddr); 833 nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n); 834 kunmap_local(desc_kaddr); 835 mark_buffer_dirty(desc_bh); 836 nilfs_mdt_mark_dirty(inode); 837 brelse(desc_bh); 838 839 if (nfree == nilfs_palloc_entries_per_group(inode)) { 840 ret = nilfs_palloc_delete_bitmap_block(inode, group); 841 if (ret && ret != -ENOENT) 842 nilfs_warn(inode->i_sb, 843 "error %d deleting bitmap block of group=%lu, ino=%lu", 844 ret, group, inode->i_ino); 845 } 846 } 847 return 0; 848 } 849 850 void nilfs_palloc_setup_cache(struct inode *inode, 851 struct nilfs_palloc_cache *cache) 852 { 853 NILFS_MDT(inode)->mi_palloc_cache = cache; 854 spin_lock_init(&cache->lock); 855 } 856 857 void nilfs_palloc_clear_cache(struct inode *inode) 858 { 859 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache; 860 861 spin_lock(&cache->lock); 862 brelse(cache->prev_desc.bh); 863 brelse(cache->prev_bitmap.bh); 864 brelse(cache->prev_entry.bh); 865 cache->prev_desc.bh = NULL; 866 cache->prev_bitmap.bh = NULL; 867 cache->prev_entry.bh = NULL; 868 spin_unlock(&cache->lock); 869 } 870 871 void nilfs_palloc_destroy_cache(struct inode *inode) 872 { 873 nilfs_palloc_clear_cache(inode); 874 NILFS_MDT(inode)->mi_palloc_cache = NULL; 875 } 876