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, groups_per_desc_block;
 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         groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode);
 527
 528         for (i = 0; i < ngroups; i += n) {
 529                 if (group >= ngroups) {
 530                         /* wrap around */
 531                         group = 0;
 532                         maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
 533                                                       &maxgroup_offset) - 1;
 534                 }
 535                 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
 536                 if (ret < 0)
 537                         return ret;
 538                 desc_kaddr = kmap(desc_bh->b_page);
 539                 desc = nilfs_palloc_block_get_group_desc(
 540                         inode, group, desc_bh, desc_kaddr);
 541                 n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
 542                                                            maxgroup);
 543                 for (j = 0; j < n; j++, desc++, group++) {
 544                         lock = nilfs_mdt_bgl_lock(inode, group);
 545                         if (nilfs_palloc_group_desc_nfrees(desc, lock) > 0) {
 546                                 ret = nilfs_palloc_get_bitmap_block(
 547                                         inode, group, 1, &bitmap_bh);
 548                                 if (ret < 0)
 549                                         goto out_desc;
 550                                 bitmap_kaddr = kmap(bitmap_bh->b_page);
 551                                 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
 552                                 pos = nilfs_palloc_find_available_slot(
 553                                         bitmap, group_offset,
 554                                         entries_per_group, lock);
 555                                 if (pos >= 0) {
 556                                         /* found a free entry */
 557                                         nilfs_palloc_group_desc_add_entries(
 558                                                 desc, lock, -1);
 559                                         req->pr_entry_nr =
 560                                                 entries_per_group * group + pos;
 561                                         kunmap(desc_bh->b_page);
 562                                         kunmap(bitmap_bh->b_page);
 563
 564                                         req->pr_desc_bh = desc_bh;
 565                                         req->pr_bitmap_bh = bitmap_bh;
 566                                         return 0;
 567                                 }
 568                                 kunmap(bitmap_bh->b_page);
 569                                 brelse(bitmap_bh);
 570                         }
 571
 572                         group_offset = 0;
 573                 }
 574
 575                 kunmap(desc_bh->b_page);
 576                 brelse(desc_bh);
 577         }
 578
 579         /* no entries left */
 580         return -ENOSPC;
 581
 582  out_desc:
 583         kunmap(desc_bh->b_page);
 584         brelse(desc_bh);
 585         return ret;
 586 }
 587
 588 /**
 589  * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object
 590  * @inode: inode of metadata file using this allocator
 591  * @req: nilfs_palloc_req structure exchanged for the allocation
 592  */
 593 void nilfs_palloc_commit_alloc_entry(struct inode *inode,
 594                                      struct nilfs_palloc_req *req)
 595 {
 596         mark_buffer_dirty(req->pr_bitmap_bh);
 597         mark_buffer_dirty(req->pr_desc_bh);
 598         nilfs_mdt_mark_dirty(inode);
 599
 600         brelse(req->pr_bitmap_bh);
 601         brelse(req->pr_desc_bh);
 602 }
 603
 604 /**
 605  * nilfs_palloc_commit_free_entry - finish deallocating a persistent object
 606  * @inode: inode of metadata file using this allocator
 607  * @req: nilfs_palloc_req structure exchanged for the removal
 608  */
 609 void nilfs_palloc_commit_free_entry(struct inode *inode,
 610                                     struct nilfs_palloc_req *req)
 611 {
 612         struct nilfs_palloc_group_desc *desc;
 613         unsigned long group, group_offset;
 614         unsigned char *bitmap;
 615         void *desc_kaddr, *bitmap_kaddr;
 616         spinlock_t *lock;
 617
 618         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 619         desc_kaddr = kmap(req->pr_desc_bh->b_page);
 620         desc = nilfs_palloc_block_get_group_desc(inode, group,
 621                                                  req->pr_desc_bh, desc_kaddr);
 622         bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
 623         bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
 624         lock = nilfs_mdt_bgl_lock(inode, group);
 625
 626         if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
 627                 nilfs_warning(inode->i_sb, __func__,
 628                               "entry number %llu already freed: ino=%lu\n",
 629                               (unsigned long long)req->pr_entry_nr,
 630                               (unsigned long)inode->i_ino);
 631         else
 632                 nilfs_palloc_group_desc_add_entries(desc, lock, 1);
 633
 634         kunmap(req->pr_bitmap_bh->b_page);
 635         kunmap(req->pr_desc_bh->b_page);
 636
 637         mark_buffer_dirty(req->pr_desc_bh);
 638         mark_buffer_dirty(req->pr_bitmap_bh);
 639         nilfs_mdt_mark_dirty(inode);
 640
 641         brelse(req->pr_bitmap_bh);
 642         brelse(req->pr_desc_bh);
 643 }
 644
 645 /**
 646  * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object
 647  * @inode: inode of metadata file using this allocator
 648  * @req: nilfs_palloc_req structure exchanged for the allocation
 649  */
 650 void nilfs_palloc_abort_alloc_entry(struct inode *inode,
 651                                     struct nilfs_palloc_req *req)
 652 {
 653         struct nilfs_palloc_group_desc *desc;
 654         void *desc_kaddr, *bitmap_kaddr;
 655         unsigned char *bitmap;
 656         unsigned long group, group_offset;
 657         spinlock_t *lock;
 658
 659         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 660         desc_kaddr = kmap(req->pr_desc_bh->b_page);
 661         desc = nilfs_palloc_block_get_group_desc(inode, group,
 662                                                  req->pr_desc_bh, desc_kaddr);
 663         bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
 664         bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
 665         lock = nilfs_mdt_bgl_lock(inode, group);
 666
 667         if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
 668                 nilfs_warning(inode->i_sb, __func__,
 669                               "entry number %llu already freed: ino=%lu\n",
 670                               (unsigned long long)req->pr_entry_nr,
 671                               (unsigned long)inode->i_ino);
 672         else
 673                 nilfs_palloc_group_desc_add_entries(desc, lock, 1);
 674
 675         kunmap(req->pr_bitmap_bh->b_page);
 676         kunmap(req->pr_desc_bh->b_page);
 677
 678         brelse(req->pr_bitmap_bh);
 679         brelse(req->pr_desc_bh);
 680
 681         req->pr_entry_nr = 0;
 682         req->pr_bitmap_bh = NULL;
 683         req->pr_desc_bh = NULL;
 684 }
 685
 686 /**
 687  * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object
 688  * @inode: inode of metadata file using this allocator
 689  * @req: nilfs_palloc_req structure exchanged for the removal
 690  */
 691 int nilfs_palloc_prepare_free_entry(struct inode *inode,
 692                                     struct nilfs_palloc_req *req)
 693 {
 694         struct buffer_head *desc_bh, *bitmap_bh;
 695         unsigned long group, group_offset;
 696         int ret;
 697
 698         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 699         ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
 700         if (ret < 0)
 701                 return ret;
 702         ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
 703         if (ret < 0) {
 704                 brelse(desc_bh);
 705                 return ret;
 706         }
 707
 708         req->pr_desc_bh = desc_bh;
 709         req->pr_bitmap_bh = bitmap_bh;
 710         return 0;
 711 }
 712
 713 /**
 714  * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object
 715  * @inode: inode of metadata file using this allocator
 716  * @req: nilfs_palloc_req structure exchanged for the removal
 717  */
 718 void nilfs_palloc_abort_free_entry(struct inode *inode,
 719                                    struct nilfs_palloc_req *req)
 720 {
 721         brelse(req->pr_bitmap_bh);
 722         brelse(req->pr_desc_bh);
 723
 724         req->pr_entry_nr = 0;
 725         req->pr_bitmap_bh = NULL;
 726         req->pr_desc_bh = NULL;
 727 }
 728
 729 /**
 730  * nilfs_palloc_freev - deallocate a set of persistent objects
 731  * @inode: inode of metadata file using this allocator
 732  * @entry_nrs: array of entry numbers to be deallocated
 733  * @nitems: number of entries stored in @entry_nrs
 734  */
 735 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
 736 {
 737         struct buffer_head *desc_bh, *bitmap_bh;
 738         struct nilfs_palloc_group_desc *desc;
 739         unsigned char *bitmap;
 740         void *desc_kaddr, *bitmap_kaddr;
 741         unsigned long group, group_offset;
 742         __u64 group_min_nr, last_nrs[8];
 743         const unsigned long epg = nilfs_palloc_entries_per_group(inode);
 744         const unsigned epb = NILFS_MDT(inode)->mi_entries_per_block;
 745         unsigned entry_start, end, pos;
 746         spinlock_t *lock;
 747         int i, j, k, ret;
 748         u32 nfree;
 749
 750         for (i = 0; i < nitems; i = j) {
 751                 int change_group = false;
 752                 int nempties = 0, n = 0;
 753
 754                 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
 755                 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
 756                 if (ret < 0)
 757                         return ret;
 758                 ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
 759                                                     &bitmap_bh);
 760                 if (ret < 0) {
 761                         brelse(desc_bh);
 762                         return ret;
 763                 }
 764
 765                 /* Get the first entry number of the group */
 766                 group_min_nr = (__u64)group * epg;
 767
 768                 bitmap_kaddr = kmap(bitmap_bh->b_page);
 769                 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
 770                 lock = nilfs_mdt_bgl_lock(inode, group);
 771
 772                 j = i;
 773                 entry_start = rounddown(group_offset, epb);
 774                 do {
 775                         if (!nilfs_clear_bit_atomic(lock, group_offset,
 776                                                     bitmap)) {
 777                                 nilfs_warning(inode->i_sb, __func__,
 778                                               "entry number %llu already freed: ino=%lu\n",
 779                                               (unsigned long long)entry_nrs[j],
 780                                               (unsigned long)inode->i_ino);
 781                         } else {
 782                                 n++;
 783                         }
 784
 785                         j++;
 786                         if (j >= nitems || entry_nrs[j] < group_min_nr ||
 787                             entry_nrs[j] >= group_min_nr + epg) {
 788                                 change_group = true;
 789                         } else {
 790                                 group_offset = entry_nrs[j] - group_min_nr;
 791                                 if (group_offset >= entry_start &&
 792                                     group_offset < entry_start + epb) {
 793                                         /* This entry is in the same block */
 794                                         continue;
 795                                 }
 796                         }
 797
 798                         /* Test if the entry block is empty or not */
 799                         end = entry_start + epb;
 800                         pos = nilfs_find_next_bit(bitmap, end, entry_start);
 801                         if (pos >= end) {
 802                                 last_nrs[nempties++] = entry_nrs[j - 1];
 803                                 if (nempties >= ARRAY_SIZE(last_nrs))
 804                                         break;
 805                         }
 806
 807                         if (change_group)
 808                                 break;
 809
 810                         /* Go on to the next entry block */
 811                         entry_start = rounddown(group_offset, epb);
 812                 } while (true);
 813
 814                 kunmap(bitmap_bh->b_page);
 815                 mark_buffer_dirty(bitmap_bh);
 816                 brelse(bitmap_bh);
 817
 818                 for (k = 0; k < nempties; k++) {
 819                         ret = nilfs_palloc_delete_entry_block(inode,
 820                                                               last_nrs[k]);
 821                         if (ret && ret != -ENOENT) {
 822                                 nilfs_warning(inode->i_sb, __func__,
 823                                               "failed to delete block of entry %llu: ino=%lu, err=%d\n",
 824                                               (unsigned long long)last_nrs[k],
 825                                               (unsigned long)inode->i_ino, ret);
 826                         }
 827                 }
 828
 829                 desc_kaddr = kmap_atomic(desc_bh->b_page);
 830                 desc = nilfs_palloc_block_get_group_desc(
 831                         inode, group, desc_bh, desc_kaddr);
 832                 nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n);
 833                 kunmap_atomic(desc_kaddr);
 834                 mark_buffer_dirty(desc_bh);
 835                 nilfs_mdt_mark_dirty(inode);
 836                 brelse(desc_bh);
 837
 838                 if (nfree == nilfs_palloc_entries_per_group(inode)) {
 839                         ret = nilfs_palloc_delete_bitmap_block(inode, group);
 840                         if (ret && ret != -ENOENT) {
 841                                 nilfs_warning(inode->i_sb, __func__,
 842                                               "failed to delete bitmap block of group %lu: ino=%lu, err=%d\n",
 843                                               group,
 844                                               (unsigned long)inode->i_ino, ret);
 845                         }
 846                 }
 847         }
 848         return 0;
 849 }
 850
 851 void nilfs_palloc_setup_cache(struct inode *inode,
 852                               struct nilfs_palloc_cache *cache)
 853 {
 854         NILFS_MDT(inode)->mi_palloc_cache = cache;
 855         spin_lock_init(&cache->lock);
 856 }
 857
 858 void nilfs_palloc_clear_cache(struct inode *inode)
 859 {
 860         struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
 861
 862         spin_lock(&cache->lock);
 863         brelse(cache->prev_desc.bh);
 864         brelse(cache->prev_bitmap.bh);
 865         brelse(cache->prev_entry.bh);
 866         cache->prev_desc.bh = NULL;
 867         cache->prev_bitmap.bh = NULL;
 868         cache->prev_entry.bh = NULL;
 869         spin_unlock(&cache->lock);
 870 }
 871
 872 void nilfs_palloc_destroy_cache(struct inode *inode)
 873 {
 874         nilfs_palloc_clear_cache(inode);
 875         NILFS_MDT(inode)->mi_palloc_cache = NULL;
 876 }