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