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 55static void 56nandfs_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 63static void 64nandfs_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 75static void 76init_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 86int 87nandfs_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; 106restart: 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 179found: 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 189int 190nandfs_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 228static __inline void 229nandfs_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 243int 244nandfs_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 282int 283nandfs_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 320void 321nandfs_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 329int 330nandfs_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} 367