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 "mdt.h"
  30 #include "alloc.h"
  31
  32
  33 static inline unsigned long
  34 nilfs_palloc_groups_per_desc_block(const struct inode *inode)
  35 {
  36         return (1UL << inode->i_blkbits) /
  37                 sizeof(struct nilfs_palloc_group_desc);
  38 }
  39
  40 static inline unsigned long
  41 nilfs_palloc_groups_count(const struct inode *inode)
  42 {
  43         return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
  44 }
  45
  46 int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size)
  47 {
  48         struct nilfs_mdt_info *mi = NILFS_MDT(inode);
  49
  50         mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS);
  51         if (!mi->mi_bgl)
  52                 return -ENOMEM;
  53
  54         bgl_lock_init(mi->mi_bgl);
  55
  56         nilfs_mdt_set_entry_size(inode, entry_size, 0);
  57
  58         mi->mi_blocks_per_group =
  59                 DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode),
  60                              mi->mi_entries_per_block) + 1;
  61                 /* Number of blocks in a group including entry blocks and
  62                    a bitmap block */
  63         mi->mi_blocks_per_desc_block =
  64                 nilfs_palloc_groups_per_desc_block(inode) *
  65                 mi->mi_blocks_per_group + 1;
  66                 /* Number of blocks per descriptor including the
  67                    descriptor block */
  68         return 0;
  69 }
  70
  71 static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr,
  72                                         unsigned long *offset)
  73 {
  74         __u64 group = nr;
  75
  76         *offset = do_div(group, nilfs_palloc_entries_per_group(inode));
  77         return group;
  78 }
  79
  80 static unsigned long
  81 nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group)
  82 {
  83         unsigned long desc_block =
  84                 group / nilfs_palloc_groups_per_desc_block(inode);
  85         return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block;
  86 }
  87
  88 static unsigned long
  89 nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group)
  90 {
  91         unsigned long desc_offset =
  92                 group % nilfs_palloc_groups_per_desc_block(inode);
  93         return nilfs_palloc_desc_blkoff(inode, group) + 1 +
  94                 desc_offset * NILFS_MDT(inode)->mi_blocks_per_group;
  95 }
  96
  97 static unsigned long
  98 nilfs_palloc_group_desc_nfrees(struct inode *inode, unsigned long group,
  99                                const struct nilfs_palloc_group_desc *desc)
 100 {
 101         unsigned long nfree;
 102
 103         spin_lock(nilfs_mdt_bgl_lock(inode, group));
 104         nfree = le32_to_cpu(desc->pg_nfrees);
 105         spin_unlock(nilfs_mdt_bgl_lock(inode, group));
 106         return nfree;
 107 }
 108
 109 static void
 110 nilfs_palloc_group_desc_add_entries(struct inode *inode,
 111                                     unsigned long group,
 112                                     struct nilfs_palloc_group_desc *desc,
 113                                     u32 n)
 114 {
 115         spin_lock(nilfs_mdt_bgl_lock(inode, group));
 116         le32_add_cpu(&desc->pg_nfrees, n);
 117         spin_unlock(nilfs_mdt_bgl_lock(inode, group));
 118 }
 119
 120 static unsigned long
 121 nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr)
 122 {
 123         unsigned long group, group_offset;
 124
 125         group = nilfs_palloc_group(inode, nr, &group_offset);
 126
 127         return nilfs_palloc_bitmap_blkoff(inode, group) + 1 +
 128                 group_offset / NILFS_MDT(inode)->mi_entries_per_block;
 129 }
 130
 131 static void nilfs_palloc_desc_block_init(struct inode *inode,
 132                                          struct buffer_head *bh, void *kaddr)
 133 {
 134         struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh);
 135         unsigned long n = nilfs_palloc_groups_per_desc_block(inode);
 136         __le32 nfrees;
 137
 138         nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode));
 139         while (n-- > 0) {
 140                 desc->pg_nfrees = nfrees;
 141                 desc++;
 142         }
 143 }
 144
 145 static int nilfs_palloc_get_block(struct inode *inode, unsigned long blkoff,
 146                                   int create,
 147                                   void (*init_block)(struct inode *,
 148                                                      struct buffer_head *,
 149                                                      void *),
 150                                   struct buffer_head **bhp,
 151                                   struct nilfs_bh_assoc *prev,
 152                                   spinlock_t *lock)
 153 {
 154         int ret;
 155
 156         spin_lock(lock);
 157         if (prev->bh && blkoff == prev->blkoff) {
 158                 get_bh(prev->bh);
 159                 *bhp = prev->bh;
 160                 spin_unlock(lock);
 161                 return 0;
 162         }
 163         spin_unlock(lock);
 164
 165         ret = nilfs_mdt_get_block(inode, blkoff, create, init_block, bhp);
 166         if (!ret) {
 167                 spin_lock(lock);
 168                 /*
 169                  * The following code must be safe for change of the
 170                  * cache contents during the get block call.
 171                  */
 172                 brelse(prev->bh);
 173                 get_bh(*bhp);
 174                 prev->bh = *bhp;
 175                 prev->blkoff = blkoff;
 176                 spin_unlock(lock);
 177         }
 178         return ret;
 179 }
 180
 181 static int nilfs_palloc_get_desc_block(struct inode *inode,
 182                                        unsigned long group,
 183                                        int create, struct buffer_head **bhp)
 184 {
 185         struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
 186
 187         return nilfs_palloc_get_block(inode,
 188                                       nilfs_palloc_desc_blkoff(inode, group),
 189                                       create, nilfs_palloc_desc_block_init,
 190                                       bhp, &cache->prev_desc, &cache->lock);
 191 }
 192
 193 static int nilfs_palloc_get_bitmap_block(struct inode *inode,
 194                                          unsigned long group,
 195                                          int create, struct buffer_head **bhp)
 196 {
 197         struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
 198
 199         return nilfs_palloc_get_block(inode,
 200                                       nilfs_palloc_bitmap_blkoff(inode, group),
 201                                       create, NULL, bhp,
 202                                       &cache->prev_bitmap, &cache->lock);
 203 }
 204
 205 int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
 206                                  int create, struct buffer_head **bhp)
 207 {
 208         struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
 209
 210         return nilfs_palloc_get_block(inode,
 211                                       nilfs_palloc_entry_blkoff(inode, nr),
 212                                       create, NULL, bhp,
 213                                       &cache->prev_entry, &cache->lock);
 214 }
 215
 216 static struct nilfs_palloc_group_desc *
 217 nilfs_palloc_block_get_group_desc(const struct inode *inode,
 218                                   unsigned long group,
 219                                   const struct buffer_head *bh, void *kaddr)
 220 {
 221         return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
 222                 group % nilfs_palloc_groups_per_desc_block(inode);
 223 }
 224
 225 void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr,
 226                                    const struct buffer_head *bh, void *kaddr)
 227 {
 228         unsigned long entry_offset, group_offset;
 229
 230         nilfs_palloc_group(inode, nr, &group_offset);
 231         entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;
 232
 233         return kaddr + bh_offset(bh) +
 234                 entry_offset * NILFS_MDT(inode)->mi_entry_size;
 235 }
 236
 237 static int nilfs_palloc_find_available_slot(struct inode *inode,
 238                                             unsigned long group,
 239                                             unsigned long target,
 240                                             unsigned char *bitmap,
 241                                             int bsize)  /* size in bits */
 242 {
 243         int curr, pos, end, i;
 244
 245         if (target > 0) {
 246                 end = (target + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1);
 247                 if (end > bsize)
 248                         end = bsize;
 249                 pos = nilfs_find_next_zero_bit(bitmap, end, target);
 250                 if (pos < end &&
 251                     !nilfs_set_bit_atomic(
 252                             nilfs_mdt_bgl_lock(inode, group), pos, bitmap))
 253                         return pos;
 254         } else
 255                 end = 0;
 256
 257         for (i = 0, curr = end;
 258              i < bsize;
 259              i += BITS_PER_LONG, curr += BITS_PER_LONG) {
 260                 /* wrap around */
 261                 if (curr >= bsize)
 262                         curr = 0;
 263                 while (*((unsigned long *)bitmap + curr / BITS_PER_LONG)
 264                        != ~0UL) {
 265                         end = curr + BITS_PER_LONG;
 266                         if (end > bsize)
 267                                 end = bsize;
 268                         pos = nilfs_find_next_zero_bit(bitmap, end, curr);
 269                         if ((pos < end) &&
 270                             !nilfs_set_bit_atomic(
 271                                     nilfs_mdt_bgl_lock(inode, group), pos,
 272                                     bitmap))
 273                                 return pos;
 274                 }
 275         }
 276         return -ENOSPC;
 277 }
 278
 279 static unsigned long
 280 nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
 281                                        unsigned long curr, unsigned long max)
 282 {
 283         return min_t(unsigned long,
 284                      nilfs_palloc_groups_per_desc_block(inode) -
 285                      curr % nilfs_palloc_groups_per_desc_block(inode),
 286                      max - curr + 1);
 287 }
 288
 289 int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
 290                                      struct nilfs_palloc_req *req)
 291 {
 292         struct buffer_head *desc_bh, *bitmap_bh;
 293         struct nilfs_palloc_group_desc *desc;
 294         unsigned char *bitmap;
 295         void *desc_kaddr, *bitmap_kaddr;
 296         unsigned long group, maxgroup, ngroups;
 297         unsigned long group_offset, maxgroup_offset;
 298         unsigned long n, entries_per_group, groups_per_desc_block;
 299         unsigned long i, j;
 300         int pos, ret;
 301
 302         ngroups = nilfs_palloc_groups_count(inode);
 303         maxgroup = ngroups - 1;
 304         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 305         entries_per_group = nilfs_palloc_entries_per_group(inode);
 306         groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode);
 307
 308         for (i = 0; i < ngroups; i += n) {
 309                 if (group >= ngroups) {
 310                         /* wrap around */
 311                         group = 0;
 312                         maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
 313                                                       &maxgroup_offset) - 1;
 314                 }
 315                 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
 316                 if (ret < 0)
 317                         return ret;
 318                 desc_kaddr = kmap(desc_bh->b_page);
 319                 desc = nilfs_palloc_block_get_group_desc(
 320                         inode, group, desc_bh, desc_kaddr);
 321                 n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
 322                                                            maxgroup);
 323                 for (j = 0; j < n; j++, desc++, group++) {
 324                         if (nilfs_palloc_group_desc_nfrees(inode, group, desc)
 325                             > 0) {
 326                                 ret = nilfs_palloc_get_bitmap_block(
 327                                         inode, group, 1, &bitmap_bh);
 328                                 if (ret < 0)
 329                                         goto out_desc;
 330                                 bitmap_kaddr = kmap(bitmap_bh->b_page);
 331                                 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
 332                                 pos = nilfs_palloc_find_available_slot(
 333                                         inode, group, group_offset, bitmap,
 334                                         entries_per_group);
 335                                 if (pos >= 0) {
 336                                         /* found a free entry */
 337                                         nilfs_palloc_group_desc_add_entries(
 338                                                 inode, group, desc, -1);
 339                                         req->pr_entry_nr =
 340                                                 entries_per_group * group + pos;
 341                                         kunmap(desc_bh->b_page);
 342                                         kunmap(bitmap_bh->b_page);
 343
 344                                         req->pr_desc_bh = desc_bh;
 345                                         req->pr_bitmap_bh = bitmap_bh;
 346                                         return 0;
 347                                 }
 348                                 kunmap(bitmap_bh->b_page);
 349                                 brelse(bitmap_bh);
 350                         }
 351
 352                         group_offset = 0;
 353                 }
 354
 355                 kunmap(desc_bh->b_page);
 356                 brelse(desc_bh);
 357         }
 358
 359         /* no entries left */
 360         return -ENOSPC;
 361
 362  out_desc:
 363         kunmap(desc_bh->b_page);
 364         brelse(desc_bh);
 365         return ret;
 366 }
 367
 368 void nilfs_palloc_commit_alloc_entry(struct inode *inode,
 369                                      struct nilfs_palloc_req *req)
 370 {
 371         nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
 372         nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
 373         nilfs_mdt_mark_dirty(inode);
 374
 375         brelse(req->pr_bitmap_bh);
 376         brelse(req->pr_desc_bh);
 377 }
 378
 379 void nilfs_palloc_commit_free_entry(struct inode *inode,
 380                                     struct nilfs_palloc_req *req)
 381 {
 382         struct nilfs_palloc_group_desc *desc;
 383         unsigned long group, group_offset;
 384         unsigned char *bitmap;
 385         void *desc_kaddr, *bitmap_kaddr;
 386
 387         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 388         desc_kaddr = kmap(req->pr_desc_bh->b_page);
 389         desc = nilfs_palloc_block_get_group_desc(inode, group,
 390                                                  req->pr_desc_bh, desc_kaddr);
 391         bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
 392         bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
 393
 394         if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
 395                                     group_offset, bitmap))
 396                 printk(KERN_WARNING "%s: entry number %llu already freed\n",
 397                        __func__, (unsigned long long)req->pr_entry_nr);
 398
 399         nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);
 400
 401         kunmap(req->pr_bitmap_bh->b_page);
 402         kunmap(req->pr_desc_bh->b_page);
 403
 404         nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
 405         nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
 406         nilfs_mdt_mark_dirty(inode);
 407
 408         brelse(req->pr_bitmap_bh);
 409         brelse(req->pr_desc_bh);
 410 }
 411
 412 void nilfs_palloc_abort_alloc_entry(struct inode *inode,
 413                                     struct nilfs_palloc_req *req)
 414 {
 415         struct nilfs_palloc_group_desc *desc;
 416         void *desc_kaddr, *bitmap_kaddr;
 417         unsigned char *bitmap;
 418         unsigned long group, group_offset;
 419
 420         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 421         desc_kaddr = kmap(req->pr_desc_bh->b_page);
 422         desc = nilfs_palloc_block_get_group_desc(inode, group,
 423                                                  req->pr_desc_bh, desc_kaddr);
 424         bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
 425         bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
 426         if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
 427                                     group_offset, bitmap))
 428                 printk(KERN_WARNING "%s: entry numer %llu already freed\n",
 429                        __func__, (unsigned long long)req->pr_entry_nr);
 430
 431         nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);
 432
 433         kunmap(req->pr_bitmap_bh->b_page);
 434         kunmap(req->pr_desc_bh->b_page);
 435
 436         brelse(req->pr_bitmap_bh);
 437         brelse(req->pr_desc_bh);
 438
 439         req->pr_entry_nr = 0;
 440         req->pr_bitmap_bh = NULL;
 441         req->pr_desc_bh = NULL;
 442 }
 443
 444 int nilfs_palloc_prepare_free_entry(struct inode *inode,
 445                                     struct nilfs_palloc_req *req)
 446 {
 447         struct buffer_head *desc_bh, *bitmap_bh;
 448         unsigned long group, group_offset;
 449         int ret;
 450
 451         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 452         ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
 453         if (ret < 0)
 454                 return ret;
 455         ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
 456         if (ret < 0) {
 457                 brelse(desc_bh);
 458                 return ret;
 459         }
 460
 461         req->pr_desc_bh = desc_bh;
 462         req->pr_bitmap_bh = bitmap_bh;
 463         return 0;
 464 }
 465
 466 void nilfs_palloc_abort_free_entry(struct inode *inode,
 467                                    struct nilfs_palloc_req *req)
 468 {
 469         brelse(req->pr_bitmap_bh);
 470         brelse(req->pr_desc_bh);
 471
 472         req->pr_entry_nr = 0;
 473         req->pr_bitmap_bh = NULL;
 474         req->pr_desc_bh = NULL;
 475 }
 476
 477 static int
 478 nilfs_palloc_group_is_in(struct inode *inode, unsigned long group, __u64 nr)
 479 {
 480         __u64 first, last;
 481
 482         first = group * nilfs_palloc_entries_per_group(inode);
 483         last = first + nilfs_palloc_entries_per_group(inode) - 1;
 484         return (nr >= first) && (nr <= last);
 485 }
 486
 487 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
 488 {
 489         struct buffer_head *desc_bh, *bitmap_bh;
 490         struct nilfs_palloc_group_desc *desc;
 491         unsigned char *bitmap;
 492         void *desc_kaddr, *bitmap_kaddr;
 493         unsigned long group, group_offset;
 494         int i, j, n, ret;
 495
 496         for (i = 0; i < nitems; i += n) {
 497                 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
 498                 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
 499                 if (ret < 0)
 500                         return ret;
 501                 ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
 502                                                     &bitmap_bh);
 503                 if (ret < 0) {
 504                         brelse(desc_bh);
 505                         return ret;
 506                 }
 507                 desc_kaddr = kmap(desc_bh->b_page);
 508                 desc = nilfs_palloc_block_get_group_desc(
 509                         inode, group, desc_bh, desc_kaddr);
 510                 bitmap_kaddr = kmap(bitmap_bh->b_page);
 511                 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
 512                 for (j = i, n = 0;
 513                      (j < nitems) && nilfs_palloc_group_is_in(inode, group,
 514                                                               entry_nrs[j]);
 515                      j++, n++) {
 516                         nilfs_palloc_group(inode, entry_nrs[j], &group_offset);
 517                         if (!nilfs_clear_bit_atomic(
 518                                     nilfs_mdt_bgl_lock(inode, group),
 519                                     group_offset, bitmap)) {
 520                                 printk(KERN_WARNING
 521                                        "%s: entry number %llu already freed\n",
 522                                        __func__,
 523                                        (unsigned long long)entry_nrs[j]);
 524                         }
 525                 }
 526                 nilfs_palloc_group_desc_add_entries(inode, group, desc, n);
 527
 528                 kunmap(bitmap_bh->b_page);
 529                 kunmap(desc_bh->b_page);
 530
 531                 nilfs_mdt_mark_buffer_dirty(desc_bh);
 532                 nilfs_mdt_mark_buffer_dirty(bitmap_bh);
 533                 nilfs_mdt_mark_dirty(inode);
 534
 535                 brelse(bitmap_bh);
 536                 brelse(desc_bh);
 537         }
 538         return 0;
 539 }
 540
 541 void nilfs_palloc_setup_cache(struct inode *inode,
 542                               struct nilfs_palloc_cache *cache)
 543 {
 544         NILFS_MDT(inode)->mi_palloc_cache = cache;
 545         spin_lock_init(&cache->lock);
 546 }
 547
 548 void nilfs_palloc_clear_cache(struct inode *inode)
 549 {
 550         struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
 551
 552         spin_lock(&cache->lock);
 553         brelse(cache->prev_desc.bh);
 554         brelse(cache->prev_bitmap.bh);
 555         brelse(cache->prev_entry.bh);
 556         cache->prev_desc.bh = NULL;
 557         cache->prev_bitmap.bh = NULL;
 558         cache->prev_entry.bh = NULL;
 559         spin_unlock(&cache->lock);
 560 }
 561
 562 void nilfs_palloc_destroy_cache(struct inode *inode)
 563 {
 564         nilfs_palloc_clear_cache(inode);
 565         NILFS_MDT(inode)->mi_palloc_cache = NULL;
 566 }