sys/fs/nandfs/nandfs_alloc.c

   1 /*-
   2  * Copyright (c) 2010-2012 Semihalf.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <sys/cdefs.h>
  28 __FBSDID("$FreeBSD$");
  29
  30 #include <sys/param.h>
  31 #include <sys/systm.h>
  32 #include <sys/conf.h>
  33 #include <sys/kernel.h>
  34 #include <sys/lock.h>
  35 #include <sys/malloc.h>
  36 #include <sys/mount.h>
  37 #include <sys/mutex.h>
  38 #include <sys/namei.h>
  39 #include <sys/sysctl.h>
  40 #include <sys/vnode.h>
  41 #include <sys/buf.h>
  42 #include <sys/bio.h>
  43
  44 #include <vm/vm.h>
  45 #include <vm/vm_param.h>
  46 #include <vm/vm_kern.h>
  47 #include <vm/vm_page.h>
  48
  49 #include <fs/nandfs/nandfs_mount.h>
  50 #include <fs/nandfs/nandfs.h>
  51 #include <fs/nandfs/nandfs_subr.h>
  52
  53 static void
  54 nandfs_get_desc_block_nr(struct nandfs_mdt *mdt, uint64_t desc,
  55     uint64_t *desc_block)
  56 {
  57
  58         *desc_block = desc * mdt->blocks_per_desc_block;
  59 }
  60
  61 static void
  62 nandfs_get_group_block_nr(struct nandfs_mdt *mdt, uint64_t group,
  63     uint64_t *group_block)
  64 {
  65         uint64_t desc, group_off;
  66
  67         desc = group / mdt->groups_per_desc_block;
  68         group_off = group % mdt->groups_per_desc_block;
  69         *group_block = desc * mdt->blocks_per_desc_block +
  70             1 + group_off * mdt->blocks_per_group;
  71 }
  72
  73 static void
  74 init_desc_block(struct nandfs_mdt *mdt, uint8_t *block_data)
  75 {
  76         struct nandfs_block_group_desc *desc;
  77         uint32_t i;
  78
  79         desc = (struct nandfs_block_group_desc *) block_data;
  80         for (i = 0; i < mdt->groups_per_desc_block; i++)
  81                 desc[i].bg_nfrees = mdt->entries_per_group;
  82 }
  83
  84 int
  85 nandfs_find_free_entry(struct nandfs_mdt *mdt, struct nandfs_node *node,
  86     struct nandfs_alloc_request *req)
  87 {
  88         nandfs_daddr_t desc, group, maxgroup, maxdesc, pos = 0;
  89         nandfs_daddr_t start_group, start_desc;
  90         nandfs_daddr_t desc_block, group_block;
  91         nandfs_daddr_t file_blocks;
  92         struct nandfs_block_group_desc *descriptors;
  93         struct buf *bp, *bp2;
  94         uint32_t *mask, i, mcount, msize;
  95         int error;
  96
  97         file_blocks = node->nn_inode.i_blocks;
  98         maxgroup = 0x100000000ull / mdt->entries_per_group;
  99         maxdesc = maxgroup / mdt->groups_per_desc_block;
 100         start_group = req->entrynum / mdt->entries_per_group;
 101         start_desc = start_group / mdt->groups_per_desc_block;
 102
 103         bp = bp2 = NULL;
 104 restart:
 105         for (desc = start_desc; desc < maxdesc; desc++) {
 106                 nandfs_get_desc_block_nr(mdt, desc, &desc_block);
 107
 108                 if (bp)
 109                         brelse(bp);
 110                 if (desc_block < file_blocks) {
 111                         error = nandfs_bread(node, desc_block, NOCRED, 0, &bp);
 112                         if (error) {
 113                                 brelse(bp);
 114                                 return (error);
 115                         }
 116                 } else {
 117                         error = nandfs_bcreate(node, desc_block, NOCRED, 0,
 118                             &bp);
 119                         if (error)
 120                                 return (error);
 121                         file_blocks++;
 122                         init_desc_block(mdt, bp->b_data);
 123                 }
 124
 125                 descriptors = (struct nandfs_block_group_desc *) bp->b_data;
 126                 for (group = start_group; group < mdt->groups_per_desc_block;
 127                     group++) {
 128                         if (descriptors[group].bg_nfrees > 0) {
 129                                 nandfs_get_group_block_nr(mdt, group,
 130                                     &group_block);
 131
 132                                 if (bp2)
 133                                         brelse(bp2);
 134                                 if (group_block < file_blocks) {
 135                                         error = nandfs_bread(node, group_block,
 136                                             NOCRED, 0, &bp2);
 137                                         if (error) {
 138                                                 brelse(bp);
 139                                                 return (error);
 140                                         }
 141                                 } else {
 142                                         error = nandfs_bcreate(node,
 143                                             group_block, NOCRED, 0, &bp2);
 144                                         if (error)
 145                                                 return (error);
 146                                         file_blocks++;
 147                                 }
 148                                 mask = (uint32_t *)bp2->b_data;
 149                                 msize = (sizeof(uint32_t) * __CHAR_BIT);
 150                                 mcount = mdt->entries_per_group / msize;
 151                                 for (i = 0; i < mcount; i++) {
 152                                         if (mask[i] == UINT32_MAX)
 153                                                 continue;
 154
 155                                         pos = ffs(~mask[i]) - 1;
 156                                         pos += (msize * i);
 157                                         pos += (group * mdt->entries_per_group);
 158                                         pos += desc * group *
 159                                             mdt->groups_per_desc_block *
 160                                             mdt->entries_per_group;
 161                                         goto found;
 162                                 }
 163                         }
 164                 }
 165                 start_group = 0;
 166         }
 167
 168         if (start_desc != 0) {
 169                 maxdesc = start_desc;
 170                 start_desc = 0;
 171                 req->entrynum = 0;
 172                 goto restart;
 173         }
 174
 175         return (ENOENT);
 176
 177 found:
 178         req->entrynum = pos;
 179         req->bp_desc = bp;
 180         req->bp_bitmap = bp2;
 181         DPRINTF(ALLOC, ("%s: desc: %p bitmap: %p entry: %#jx\n",
 182             __func__, req->bp_desc, req->bp_bitmap, (uintmax_t)pos));
 183
 184         return (0);
 185 }
 186
 187 int
 188 nandfs_find_entry(struct nandfs_mdt* mdt, struct nandfs_node *nnode,
 189     struct nandfs_alloc_request *req)
 190 {
 191         uint64_t dblock, bblock, eblock;
 192         uint32_t offset;
 193         int error;
 194
 195         nandfs_mdt_trans_blk(mdt, req->entrynum, &dblock, &bblock, &eblock,
 196             &offset);
 197
 198         error = nandfs_bread(nnode, dblock, NOCRED, 0, &req->bp_desc);
 199         if (error) {
 200                 brelse(req->bp_desc);
 201                 return (error);
 202         }
 203
 204         error = nandfs_bread(nnode, bblock, NOCRED, 0, &req->bp_bitmap);
 205         if (error) {
 206                 brelse(req->bp_desc);
 207                 brelse(req->bp_bitmap);
 208                 return (error);
 209         }
 210
 211         error = nandfs_bread(nnode, eblock, NOCRED, 0, &req->bp_entry);
 212         if (error) {
 213                 brelse(req->bp_desc);
 214                 brelse(req->bp_bitmap);
 215                 brelse(req->bp_entry);
 216                 return (error);
 217         }
 218
 219         DPRINTF(ALLOC,
 220             ("%s: desc_buf: %p bitmap_buf %p entry_buf %p offset %x\n",
 221             __func__, req->bp_desc, req->bp_bitmap, req->bp_entry, offset));
 222
 223         return (0);
 224 }
 225
 226 static __inline void
 227 nandfs_calc_idx_entry(struct nandfs_mdt* mdt, uint32_t entrynum,
 228     uint64_t *group, uint64_t *bitmap_idx, uint64_t *bitmap_off)
 229 {
 230
 231         /* Find group_desc index */
 232         entrynum = entrynum %
 233             (mdt->entries_per_group * mdt->groups_per_desc_block);
 234         *group = entrynum / mdt->entries_per_group;
 235         /* Find bitmap index and bit offset */
 236         entrynum = entrynum % mdt->entries_per_group;
 237         *bitmap_idx = entrynum / (sizeof(uint32_t) * __CHAR_BIT);
 238         *bitmap_off = entrynum % (sizeof(uint32_t) * __CHAR_BIT);
 239 }
 240
 241 int
 242 nandfs_free_entry(struct nandfs_mdt* mdt, struct nandfs_alloc_request *req)
 243 {
 244         struct nandfs_block_group_desc *descriptors;
 245         uint64_t bitmap_idx, bitmap_off;
 246         uint64_t group;
 247         uint32_t *mask, maskrw;
 248
 249         nandfs_calc_idx_entry(mdt, req->entrynum, &group, &bitmap_idx,
 250             &bitmap_off);
 251
 252         DPRINTF(ALLOC, ("nandfs_free_entry: req->entrynum=%jx bitmap_idx=%jx"
 253            " bitmap_off=%jx group=%jx\n", (uintmax_t)req->entrynum,
 254            (uintmax_t)bitmap_idx, (uintmax_t)bitmap_off, (uintmax_t)group));
 255
 256         /* Update counter of free entries for group */
 257         descriptors = (struct nandfs_block_group_desc *) req->bp_desc->b_data;
 258         descriptors[group].bg_nfrees++;
 259
 260         /* Set bit to indicate that entry is taken */
 261         mask = (uint32_t *)req->bp_bitmap->b_data;
 262         maskrw = mask[bitmap_idx];
 263         KASSERT(maskrw & (1 << bitmap_off), ("freeing unallocated vblock"));
 264         maskrw &= ~(1 << bitmap_off);
 265         mask[bitmap_idx] = maskrw;
 266
 267         /* Make descriptor, bitmap and entry buffer dirty */
 268         if (nandfs_dirty_buf(req->bp_desc, 0) == 0) {
 269                 nandfs_dirty_buf(req->bp_bitmap, 1);
 270                 nandfs_dirty_buf(req->bp_entry, 1);
 271         } else {
 272                 brelse(req->bp_bitmap);
 273                 brelse(req->bp_entry);
 274                 return (-1);
 275         }
 276
 277         return (0);
 278 }
 279
 280 int
 281 nandfs_alloc_entry(struct nandfs_mdt* mdt, struct nandfs_alloc_request *req)
 282 {
 283         struct nandfs_block_group_desc *descriptors;
 284         uint64_t bitmap_idx, bitmap_off;
 285         uint64_t group;
 286         uint32_t *mask, maskrw;
 287
 288         nandfs_calc_idx_entry(mdt, req->entrynum, &group, &bitmap_idx,
 289             &bitmap_off);
 290
 291         DPRINTF(ALLOC, ("nandfs_alloc_entry: req->entrynum=%jx bitmap_idx=%jx"
 292             " bitmap_off=%jx group=%jx\n", (uintmax_t)req->entrynum,
 293             (uintmax_t)bitmap_idx, (uintmax_t)bitmap_off, (uintmax_t)group));
 294
 295         /* Update counter of free entries for group */
 296         descriptors = (struct nandfs_block_group_desc *) req->bp_desc->b_data;
 297         descriptors[group].bg_nfrees--;
 298
 299         /* Clear bit to indicate that entry is free */
 300         mask = (uint32_t *)req->bp_bitmap->b_data;
 301         maskrw = mask[bitmap_idx];
 302         maskrw |= 1 << bitmap_off;
 303         mask[bitmap_idx] = maskrw;
 304
 305         /* Make descriptor, bitmap and entry buffer dirty */
 306         if (nandfs_dirty_buf(req->bp_desc, 0) == 0) {
 307                 nandfs_dirty_buf(req->bp_bitmap, 1);
 308                 nandfs_dirty_buf(req->bp_entry, 1);
 309         } else {
 310                 brelse(req->bp_bitmap);
 311                 brelse(req->bp_entry);
 312                 return (-1);
 313         }
 314
 315         return (0);
 316 }
 317
 318 void
 319 nandfs_abort_entry(struct nandfs_alloc_request *req)
 320 {
 321
 322         brelse(req->bp_desc);
 323         brelse(req->bp_bitmap);
 324         brelse(req->bp_entry);
 325 }
 326
 327 int
 328 nandfs_get_entry_block(struct nandfs_mdt *mdt, struct nandfs_node *node,
 329     struct nandfs_alloc_request *req, uint32_t *entry, int create)
 330 {
 331         struct buf *bp;
 332         nandfs_lbn_t blocknr;
 333         int     error;
 334
 335         /* Find buffer number for given entry */
 336         nandfs_mdt_trans(mdt, req->entrynum, &blocknr, entry);
 337         DPRINTF(ALLOC, ("%s: ino %#jx entrynum:%#jx block:%#jx entry:%x\n",
 338             __func__, (uintmax_t)node->nn_ino, (uintmax_t)req->entrynum,
 339             (uintmax_t)blocknr, *entry));
 340
 341         /* Read entry block or create if 'create' parameter is not zero */
 342         bp = NULL;
 343
 344         if (blocknr < node->nn_inode.i_blocks)
 345                 error = nandfs_bread(node, blocknr, NOCRED, 0, &bp);
 346         else if (create)
 347                 error = nandfs_bcreate(node, blocknr, NOCRED, 0, &bp);
 348         else
 349                 error = E2BIG;
 350
 351         if (error) {
 352                 DPRINTF(ALLOC, ("%s: ino %#jx block %#jx entry %x error %d\n",
 353                     __func__, (uintmax_t)node->nn_ino, (uintmax_t)blocknr,
 354                     *entry, error));
 355                 if (bp)
 356                         brelse(bp);
 357                 return (error);
 358         }
 359
 360         MPASS(nandfs_vblk_get(bp) != 0 || node->nn_ino == NANDFS_DAT_INO);
 361
 362         req->bp_entry = bp;
 363         return (0);
 364 }