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