fs/nilfs2/alloc.c

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