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_desc_block(struct inode *inode,
 146                                        unsigned long group,
 147                                        int create, struct buffer_head **bhp)
 148 {
 149         return nilfs_mdt_get_block(inode,
 150                                    nilfs_palloc_desc_blkoff(inode, group),
 151                                    create, nilfs_palloc_desc_block_init, bhp);
 152 }
 153
 154 static int nilfs_palloc_get_bitmap_block(struct inode *inode,
 155                                          unsigned long group,
 156                                          int create, struct buffer_head **bhp)
 157 {
 158         return nilfs_mdt_get_block(inode,
 159                                    nilfs_palloc_bitmap_blkoff(inode, group),
 160                                    create, NULL, bhp);
 161 }
 162
 163 int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
 164                                  int create, struct buffer_head **bhp)
 165 {
 166         return nilfs_mdt_get_block(inode, nilfs_palloc_entry_blkoff(inode, nr),
 167                                    create, NULL, bhp);
 168 }
 169
 170 static struct nilfs_palloc_group_desc *
 171 nilfs_palloc_block_get_group_desc(const struct inode *inode,
 172                                   unsigned long group,
 173                                   const struct buffer_head *bh, void *kaddr)
 174 {
 175         return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
 176                 group % nilfs_palloc_groups_per_desc_block(inode);
 177 }
 178
 179 void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr,
 180                                    const struct buffer_head *bh, void *kaddr)
 181 {
 182         unsigned long entry_offset, group_offset;
 183
 184         nilfs_palloc_group(inode, nr, &group_offset);
 185         entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;
 186
 187         return kaddr + bh_offset(bh) +
 188                 entry_offset * NILFS_MDT(inode)->mi_entry_size;
 189 }
 190
 191 static int nilfs_palloc_find_available_slot(struct inode *inode,
 192                                             unsigned long group,
 193                                             unsigned long target,
 194                                             unsigned char *bitmap,
 195                                             int bsize)  /* size in bits */
 196 {
 197         int curr, pos, end, i;
 198
 199         if (target > 0) {
 200                 end = (target + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1);
 201                 if (end > bsize)
 202                         end = bsize;
 203                 pos = nilfs_find_next_zero_bit(bitmap, end, target);
 204                 if (pos < end &&
 205                     !nilfs_set_bit_atomic(
 206                             nilfs_mdt_bgl_lock(inode, group), pos, bitmap))
 207                         return pos;
 208         } else
 209                 end = 0;
 210
 211         for (i = 0, curr = end;
 212              i < bsize;
 213              i += BITS_PER_LONG, curr += BITS_PER_LONG) {
 214                 /* wrap around */
 215                 if (curr >= bsize)
 216                         curr = 0;
 217                 while (*((unsigned long *)bitmap + curr / BITS_PER_LONG)
 218                        != ~0UL) {
 219                         end = curr + BITS_PER_LONG;
 220                         if (end > bsize)
 221                                 end = bsize;
 222                         pos = nilfs_find_next_zero_bit(bitmap, end, curr);
 223                         if ((pos < end) &&
 224                             !nilfs_set_bit_atomic(
 225                                     nilfs_mdt_bgl_lock(inode, group), pos,
 226                                     bitmap))
 227                                 return pos;
 228                 }
 229         }
 230         return -ENOSPC;
 231 }
 232
 233 static unsigned long
 234 nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
 235                                        unsigned long curr, unsigned long max)
 236 {
 237         return min_t(unsigned long,
 238                      nilfs_palloc_groups_per_desc_block(inode) -
 239                      curr % nilfs_palloc_groups_per_desc_block(inode),
 240                      max - curr + 1);
 241 }
 242
 243 int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
 244                                      struct nilfs_palloc_req *req)
 245 {
 246         struct buffer_head *desc_bh, *bitmap_bh;
 247         struct nilfs_palloc_group_desc *desc;
 248         unsigned char *bitmap;
 249         void *desc_kaddr, *bitmap_kaddr;
 250         unsigned long group, maxgroup, ngroups;
 251         unsigned long group_offset, maxgroup_offset;
 252         unsigned long n, entries_per_group, groups_per_desc_block;
 253         unsigned long i, j;
 254         int pos, ret;
 255
 256         ngroups = nilfs_palloc_groups_count(inode);
 257         maxgroup = ngroups - 1;
 258         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 259         entries_per_group = nilfs_palloc_entries_per_group(inode);
 260         groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode);
 261
 262         for (i = 0; i < ngroups; i += n) {
 263                 if (group >= ngroups) {
 264                         /* wrap around */
 265                         group = 0;
 266                         maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
 267                                                       &maxgroup_offset) - 1;
 268                 }
 269                 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
 270                 if (ret < 0)
 271                         return ret;
 272                 desc_kaddr = kmap(desc_bh->b_page);
 273                 desc = nilfs_palloc_block_get_group_desc(
 274                         inode, group, desc_bh, desc_kaddr);
 275                 n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
 276                                                            maxgroup);
 277                 for (j = 0; j < n; j++, desc++, group++) {
 278                         if (nilfs_palloc_group_desc_nfrees(inode, group, desc)
 279                             > 0) {
 280                                 ret = nilfs_palloc_get_bitmap_block(
 281                                         inode, group, 1, &bitmap_bh);
 282                                 if (ret < 0)
 283                                         goto out_desc;
 284                                 bitmap_kaddr = kmap(bitmap_bh->b_page);
 285                                 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
 286                                 pos = nilfs_palloc_find_available_slot(
 287                                         inode, group, group_offset, bitmap,
 288                                         entries_per_group);
 289                                 if (pos >= 0) {
 290                                         /* found a free entry */
 291                                         nilfs_palloc_group_desc_add_entries(
 292                                                 inode, group, desc, -1);
 293                                         req->pr_entry_nr =
 294                                                 entries_per_group * group + pos;
 295                                         kunmap(desc_bh->b_page);
 296                                         kunmap(bitmap_bh->b_page);
 297
 298                                         req->pr_desc_bh = desc_bh;
 299                                         req->pr_bitmap_bh = bitmap_bh;
 300                                         return 0;
 301                                 }
 302                                 kunmap(bitmap_bh->b_page);
 303                                 brelse(bitmap_bh);
 304                         }
 305
 306                         group_offset = 0;
 307                 }
 308
 309                 kunmap(desc_bh->b_page);
 310                 brelse(desc_bh);
 311         }
 312
 313         /* no entries left */
 314         return -ENOSPC;
 315
 316  out_desc:
 317         kunmap(desc_bh->b_page);
 318         brelse(desc_bh);
 319         return ret;
 320 }
 321
 322 void nilfs_palloc_commit_alloc_entry(struct inode *inode,
 323                                      struct nilfs_palloc_req *req)
 324 {
 325         nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
 326         nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
 327         nilfs_mdt_mark_dirty(inode);
 328
 329         brelse(req->pr_bitmap_bh);
 330         brelse(req->pr_desc_bh);
 331 }
 332
 333 void nilfs_palloc_commit_free_entry(struct inode *inode,
 334                                     struct nilfs_palloc_req *req)
 335 {
 336         struct nilfs_palloc_group_desc *desc;
 337         unsigned long group, group_offset;
 338         unsigned char *bitmap;
 339         void *desc_kaddr, *bitmap_kaddr;
 340
 341         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 342         desc_kaddr = kmap(req->pr_desc_bh->b_page);
 343         desc = nilfs_palloc_block_get_group_desc(inode, group,
 344                                                  req->pr_desc_bh, desc_kaddr);
 345         bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
 346         bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
 347
 348         if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
 349                                     group_offset, bitmap))
 350                 printk(KERN_WARNING "%s: entry number %llu already freed\n",
 351                        __func__, (unsigned long long)req->pr_entry_nr);
 352
 353         nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);
 354
 355         kunmap(req->pr_bitmap_bh->b_page);
 356         kunmap(req->pr_desc_bh->b_page);
 357
 358         nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
 359         nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
 360         nilfs_mdt_mark_dirty(inode);
 361
 362         brelse(req->pr_bitmap_bh);
 363         brelse(req->pr_desc_bh);
 364 }
 365
 366 void nilfs_palloc_abort_alloc_entry(struct inode *inode,
 367                                     struct nilfs_palloc_req *req)
 368 {
 369         struct nilfs_palloc_group_desc *desc;
 370         void *desc_kaddr, *bitmap_kaddr;
 371         unsigned char *bitmap;
 372         unsigned long group, group_offset;
 373
 374         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 375         desc_kaddr = kmap(req->pr_desc_bh->b_page);
 376         desc = nilfs_palloc_block_get_group_desc(inode, group,
 377                                                  req->pr_desc_bh, desc_kaddr);
 378         bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
 379         bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
 380         if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
 381                                     group_offset, bitmap))
 382                 printk(KERN_WARNING "%s: entry numer %llu already freed\n",
 383                        __func__, (unsigned long long)req->pr_entry_nr);
 384
 385         nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);
 386
 387         kunmap(req->pr_bitmap_bh->b_page);
 388         kunmap(req->pr_desc_bh->b_page);
 389
 390         brelse(req->pr_bitmap_bh);
 391         brelse(req->pr_desc_bh);
 392
 393         req->pr_entry_nr = 0;
 394         req->pr_bitmap_bh = NULL;
 395         req->pr_desc_bh = NULL;
 396 }
 397
 398 int nilfs_palloc_prepare_free_entry(struct inode *inode,
 399                                     struct nilfs_palloc_req *req)
 400 {
 401         struct buffer_head *desc_bh, *bitmap_bh;
 402         unsigned long group, group_offset;
 403         int ret;
 404
 405         group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
 406         ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
 407         if (ret < 0)
 408                 return ret;
 409         ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
 410         if (ret < 0) {
 411                 brelse(desc_bh);
 412                 return ret;
 413         }
 414
 415         req->pr_desc_bh = desc_bh;
 416         req->pr_bitmap_bh = bitmap_bh;
 417         return 0;
 418 }
 419
 420 void nilfs_palloc_abort_free_entry(struct inode *inode,
 421                                    struct nilfs_palloc_req *req)
 422 {
 423         brelse(req->pr_bitmap_bh);
 424         brelse(req->pr_desc_bh);
 425
 426         req->pr_entry_nr = 0;
 427         req->pr_bitmap_bh = NULL;
 428         req->pr_desc_bh = NULL;
 429 }
 430
 431 static int
 432 nilfs_palloc_group_is_in(struct inode *inode, unsigned long group, __u64 nr)
 433 {
 434         __u64 first, last;
 435
 436         first = group * nilfs_palloc_entries_per_group(inode);
 437         last = first + nilfs_palloc_entries_per_group(inode) - 1;
 438         return (nr >= first) && (nr <= last);
 439 }
 440
 441 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
 442 {
 443         struct buffer_head *desc_bh, *bitmap_bh;
 444         struct nilfs_palloc_group_desc *desc;
 445         unsigned char *bitmap;
 446         void *desc_kaddr, *bitmap_kaddr;
 447         unsigned long group, group_offset;
 448         int i, j, n, ret;
 449
 450         for (i = 0; i < nitems; i += n) {
 451                 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
 452                 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
 453                 if (ret < 0)
 454                         return ret;
 455                 ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
 456                                                     &bitmap_bh);
 457                 if (ret < 0) {
 458                         brelse(desc_bh);
 459                         return ret;
 460                 }
 461                 desc_kaddr = kmap(desc_bh->b_page);
 462                 desc = nilfs_palloc_block_get_group_desc(
 463                         inode, group, desc_bh, desc_kaddr);
 464                 bitmap_kaddr = kmap(bitmap_bh->b_page);
 465                 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
 466                 for (j = i, n = 0;
 467                      (j < nitems) && nilfs_palloc_group_is_in(inode, group,
 468                                                               entry_nrs[j]);
 469                      j++, n++) {
 470                         nilfs_palloc_group(inode, entry_nrs[j], &group_offset);
 471                         if (!nilfs_clear_bit_atomic(
 472                                     nilfs_mdt_bgl_lock(inode, group),
 473                                     group_offset, bitmap)) {
 474                                 printk(KERN_WARNING
 475                                        "%s: entry number %llu already freed\n",
 476                                        __func__,
 477                                        (unsigned long long)entry_nrs[j]);
 478                         }
 479                 }
 480                 nilfs_palloc_group_desc_add_entries(inode, group, desc, n);
 481
 482                 kunmap(bitmap_bh->b_page);
 483                 kunmap(desc_bh->b_page);
 484
 485                 nilfs_mdt_mark_buffer_dirty(desc_bh);
 486                 nilfs_mdt_mark_buffer_dirty(bitmap_bh);
 487                 nilfs_mdt_mark_dirty(inode);
 488
 489                 brelse(bitmap_bh);
 490                 brelse(desc_bh);
 491         }
 492         return 0;
 493 }
 494
 495 void nilfs_palloc_setup_cache(struct inode *inode,
 496                               struct nilfs_palloc_cache *cache)
 497 {
 498         NILFS_MDT(inode)->mi_palloc_cache = cache;
 499         spin_lock_init(&cache->lock);
 500 }
 501
 502 void nilfs_palloc_clear_cache(struct inode *inode)
 503 {
 504         struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
 505
 506         spin_lock(&cache->lock);
 507         brelse(cache->prev_desc.bh);
 508         brelse(cache->prev_bitmap.bh);
 509         brelse(cache->prev_entry.bh);
 510         cache->prev_desc.bh = NULL;
 511         cache->prev_bitmap.bh = NULL;
 512         cache->prev_entry.bh = NULL;
 513         spin_unlock(&cache->lock);
 514 }
 515
 516 void nilfs_palloc_destroy_cache(struct inode *inode)
 517 {
 518         nilfs_palloc_clear_cache(inode);
 519         NILFS_MDT(inode)->mi_palloc_cache = NULL;
 520 }