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