sys/fs/nandfs/nandfs_alloc.c

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