1 /* $NetBSD: ffs_balloc.c,v 1.23 2023/03/13 22:17:24 christos Exp $ */ 2 /* From NetBSD: ffs_balloc.c,v 1.25 2001/08/08 08:36:36 lukem Exp */ 3 4 /* 5 * Copyright (c) 1982, 1986, 1989, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * @(#)ffs_balloc.c 8.8 (Berkeley) 6/16/95 33 */ 34 35 #if HAVE_NBTOOL_CONFIG_H 36 #include "nbtool_config.h" 37 #endif 38 39 #include <sys/cdefs.h> 40 #if defined(__RCSID) && !defined(__lint) 41 __RCSID("$NetBSD: ffs_balloc.c,v 1.23 2023/03/13 22:17:24 christos Exp $"); 42 #endif /* !__lint */ 43 44 #include <sys/param.h> 45 #include <sys/time.h> 46 47 #include <assert.h> 48 #include <errno.h> 49 #include <stdio.h> 50 #include <stdlib.h> 51 #include <string.h> 52 53 #include "makefs.h" 54 55 #include <ufs/ufs/dinode.h> 56 #include <ufs/ufs/ufs_bswap.h> 57 #include <ufs/ffs/fs.h> 58 59 #include "ffs/buf.h" 60 #include "ffs/ufs_inode.h" 61 #include "ffs/ffs_extern.h" 62 63 static int ffs_balloc_ufs1(struct inode *, off_t, int, struct buf **); 64 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct buf **); 65 66 /* 67 * Balloc defines the structure of file system storage 68 * by allocating the physical blocks on a device given 69 * the inode and the logical block number in a file. 70 * 71 * Assume: flags == B_SYNC | B_CLRBUF 72 */ 73 74 int 75 ffs_balloc(struct inode *ip, off_t offset, int bufsize, struct buf **bpp) 76 { 77 if (ip->i_fs->fs_magic == FS_UFS2_MAGIC || 78 ip->i_fs->fs_magic == FS_UFS2EA_MAGIC) 79 return ffs_balloc_ufs2(ip, offset, bufsize, bpp); 80 else 81 return ffs_balloc_ufs1(ip, offset, bufsize, bpp); 82 } 83 84 static int 85 ffs_balloc_ufs1(struct inode *ip, off_t offset, int bufsize, struct buf **bpp) 86 { 87 daddr_t lbn, lastlbn; 88 int size; 89 int32_t nb; 90 struct buf *bp, *nbp; 91 struct fs *fs = ip->i_fs; 92 struct indir indirs[UFS_NIADDR + 2]; 93 daddr_t newb, pref; 94 int32_t *bap; 95 int osize, nsize, num, i, error; 96 int32_t *allocblk, allociblk[UFS_NIADDR + 1]; 97 int32_t *allocib; 98 const int needswap = UFS_FSNEEDSWAP(fs); 99 100 lbn = ffs_lblkno(fs, offset); 101 size = ffs_blkoff(fs, offset) + bufsize; 102 if (bpp != NULL) { 103 *bpp = NULL; 104 } 105 106 assert(size <= fs->fs_bsize); 107 if (lbn < 0) 108 return (EFBIG); 109 110 /* 111 * If the next write will extend the file into a new block, 112 * and the file is currently composed of a fragment 113 * this fragment has to be extended to be a full block. 114 */ 115 116 lastlbn = ffs_lblkno(fs, ip->i_ffs1_size); 117 if (lastlbn < UFS_NDADDR && lastlbn < lbn) { 118 nb = lastlbn; 119 osize = ffs_blksize(fs, ip, nb); 120 if (osize < fs->fs_bsize && osize > 0) { 121 warnx("need to ffs_realloccg; not supported!"); 122 abort(); 123 } 124 } 125 126 /* 127 * The first UFS_NDADDR blocks are direct blocks 128 */ 129 130 if (lbn < UFS_NDADDR) { 131 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap); 132 if (nb != 0 && ip->i_ffs1_size >= ffs_lblktosize(fs, lbn + 1)) { 133 134 /* 135 * The block is an already-allocated direct block 136 * and the file already extends past this block, 137 * thus this must be a whole block. 138 * Just read the block (if requested). 139 */ 140 141 if (bpp != NULL) { 142 error = bread(ip->i_devvp, lbn, fs->fs_bsize, 143 0, bpp); 144 if (error) { 145 return (error); 146 } 147 } 148 return (0); 149 } 150 if (nb != 0) { 151 152 /* 153 * Consider need to reallocate a fragment. 154 */ 155 156 osize = ffs_fragroundup(fs, ffs_blkoff(fs, ip->i_ffs1_size)); 157 nsize = ffs_fragroundup(fs, size); 158 if (nsize <= osize) { 159 160 /* 161 * The existing block is already 162 * at least as big as we want. 163 * Just read the block (if requested). 164 */ 165 166 if (bpp != NULL) { 167 error = bread(ip->i_devvp, lbn, osize, 168 0, bpp); 169 if (error) { 170 return error; 171 } 172 } 173 return 0; 174 } else { 175 warnx("need to ffs_realloccg; not supported!"); 176 abort(); 177 } 178 } else { 179 180 /* 181 * the block was not previously allocated, 182 * allocate a new block or fragment. 183 */ 184 185 if (ip->i_ffs1_size < ffs_lblktosize(fs, lbn + 1)) 186 nsize = ffs_fragroundup(fs, size); 187 else 188 nsize = fs->fs_bsize; 189 error = ffs_alloc(ip, lbn, 190 ffs_blkpref_ufs1(ip, lbn, (int)lbn, 191 &ip->i_ffs1_db[0]), 192 nsize, &newb); 193 if (error) 194 return (error); 195 if (bpp != NULL) { 196 bp = getblk(ip->i_devvp, lbn, nsize, 0, 0); 197 bp->b_blkno = FFS_FSBTODB(fs, newb); 198 clrbuf(bp); 199 *bpp = bp; 200 } 201 } 202 ip->i_ffs1_db[lbn] = ufs_rw32((int32_t)newb, needswap); 203 return (0); 204 } 205 206 /* 207 * Determine the number of levels of indirection. 208 */ 209 210 pref = 0; 211 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0) 212 return (error); 213 214 if (num < 1) { 215 warnx("ffs_balloc: ufs_getlbns returned indirect block"); 216 abort(); 217 } 218 219 /* 220 * Fetch the first indirect block allocating if necessary. 221 */ 222 223 --num; 224 nb = ufs_rw32(ip->i_ffs1_ib[indirs[0].in_off], needswap); 225 allocib = NULL; 226 allocblk = allociblk; 227 if (nb == 0) { 228 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0); 229 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 230 if (error) 231 return error; 232 nb = newb; 233 *allocblk++ = nb; 234 bp = getblk(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0); 235 bp->b_blkno = FFS_FSBTODB(fs, nb); 236 clrbuf(bp); 237 /* 238 * Write synchronously so that indirect blocks 239 * never point at garbage. 240 */ 241 if ((error = bwrite(bp)) != 0) 242 return error; 243 allocib = &ip->i_ffs1_ib[indirs[0].in_off]; 244 *allocib = ufs_rw32((int32_t)nb, needswap); 245 } 246 247 /* 248 * Fetch through the indirect blocks, allocating as necessary. 249 */ 250 251 for (i = 1;;) { 252 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 253 0, &bp); 254 if (error) { 255 return error; 256 } 257 bap = (int32_t *)bp->b_data; 258 nb = ufs_rw32(bap[indirs[i].in_off], needswap); 259 if (i == num) 260 break; 261 i++; 262 if (nb != 0) { 263 brelse(bp, 0); 264 continue; 265 } 266 if (pref == 0) 267 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0); 268 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 269 if (error) { 270 brelse(bp, 0); 271 return error; 272 } 273 nb = newb; 274 *allocblk++ = nb; 275 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0); 276 nbp->b_blkno = FFS_FSBTODB(fs, nb); 277 clrbuf(nbp); 278 /* 279 * Write synchronously so that indirect blocks 280 * never point at garbage. 281 */ 282 283 if ((error = bwrite(nbp)) != 0) { 284 brelse(bp, 0); 285 return error; 286 } 287 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap); 288 289 bwrite(bp); 290 } 291 292 /* 293 * Get the data block, allocating if necessary. 294 */ 295 296 if (nb == 0) { 297 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]); 298 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 299 if (error) { 300 brelse(bp, 0); 301 return error; 302 } 303 nb = newb; 304 *allocblk++ = nb; 305 if (bpp != NULL) { 306 nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0); 307 nbp->b_blkno = FFS_FSBTODB(fs, nb); 308 clrbuf(nbp); 309 *bpp = nbp; 310 } 311 bap[indirs[num].in_off] = ufs_rw32(nb, needswap); 312 313 /* 314 * If required, write synchronously, otherwise use 315 * delayed write. 316 */ 317 bwrite(bp); 318 return (0); 319 } 320 brelse(bp, 0); 321 if (bpp != NULL) { 322 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, 0, &nbp); 323 if (error) { 324 return error; 325 } 326 *bpp = nbp; 327 } 328 return (0); 329 } 330 331 static int 332 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, struct buf **bpp) 333 { 334 daddr_t lbn, lastlbn; 335 int size; 336 struct buf *bp, *nbp; 337 struct fs *fs = ip->i_fs; 338 struct indir indirs[UFS_NIADDR + 2]; 339 daddr_t newb, pref, nb; 340 int64_t *bap; 341 int osize, nsize, num, i, error; 342 int64_t *allocblk, allociblk[UFS_NIADDR + 1]; 343 int64_t *allocib; 344 const int needswap = UFS_FSNEEDSWAP(fs); 345 346 lbn = ffs_lblkno(fs, offset); 347 size = ffs_blkoff(fs, offset) + bufsize; 348 if (bpp != NULL) { 349 *bpp = NULL; 350 } 351 352 assert(size <= fs->fs_bsize); 353 if (lbn < 0) 354 return (EFBIG); 355 356 /* 357 * If the next write will extend the file into a new block, 358 * and the file is currently composed of a fragment 359 * this fragment has to be extended to be a full block. 360 */ 361 362 lastlbn = ffs_lblkno(fs, ip->i_ffs2_size); 363 if (lastlbn < UFS_NDADDR && lastlbn < lbn) { 364 nb = lastlbn; 365 osize = ffs_blksize(fs, ip, nb); 366 if (osize < fs->fs_bsize && osize > 0) { 367 warnx("need to ffs_realloccg; not supported!"); 368 abort(); 369 } 370 } 371 372 /* 373 * The first UFS_NDADDR blocks are direct blocks 374 */ 375 376 if (lbn < UFS_NDADDR) { 377 nb = ufs_rw64(ip->i_ffs2_db[lbn], needswap); 378 if (nb != 0 && ip->i_ffs2_size >= ffs_lblktosize(fs, lbn + 1)) { 379 380 /* 381 * The block is an already-allocated direct block 382 * and the file already extends past this block, 383 * thus this must be a whole block. 384 * Just read the block (if requested). 385 */ 386 387 if (bpp != NULL) { 388 error = bread(ip->i_devvp, lbn, fs->fs_bsize, 389 0, bpp); 390 if (error) { 391 return (error); 392 } 393 } 394 return (0); 395 } 396 if (nb != 0) { 397 398 /* 399 * Consider need to reallocate a fragment. 400 */ 401 402 osize = ffs_fragroundup(fs, ffs_blkoff(fs, ip->i_ffs2_size)); 403 nsize = ffs_fragroundup(fs, size); 404 if (nsize <= osize) { 405 406 /* 407 * The existing block is already 408 * at least as big as we want. 409 * Just read the block (if requested). 410 */ 411 412 if (bpp != NULL) { 413 error = bread(ip->i_devvp, lbn, osize, 414 0, bpp); 415 if (error) { 416 return (error); 417 } 418 } 419 return 0; 420 } else { 421 warnx("need to ffs_realloccg; not supported!"); 422 abort(); 423 } 424 } else { 425 426 /* 427 * the block was not previously allocated, 428 * allocate a new block or fragment. 429 */ 430 431 if (ip->i_ffs2_size < ffs_lblktosize(fs, lbn + 1)) 432 nsize = ffs_fragroundup(fs, size); 433 else 434 nsize = fs->fs_bsize; 435 error = ffs_alloc(ip, lbn, 436 ffs_blkpref_ufs2(ip, lbn, (int)lbn, 437 &ip->i_ffs2_db[0]), 438 nsize, &newb); 439 if (error) 440 return (error); 441 if (bpp != NULL) { 442 bp = getblk(ip->i_devvp, lbn, nsize, 0, 0); 443 bp->b_blkno = FFS_FSBTODB(fs, newb); 444 clrbuf(bp); 445 *bpp = bp; 446 } 447 } 448 ip->i_ffs2_db[lbn] = ufs_rw64(newb, needswap); 449 return (0); 450 } 451 452 /* 453 * Determine the number of levels of indirection. 454 */ 455 456 pref = 0; 457 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0) 458 return (error); 459 460 if (num < 1) { 461 warnx("ffs_balloc: ufs_getlbns returned indirect block"); 462 abort(); 463 } 464 465 /* 466 * Fetch the first indirect block allocating if necessary. 467 */ 468 469 --num; 470 nb = ufs_rw64(ip->i_ffs2_ib[indirs[0].in_off], needswap); 471 allocib = NULL; 472 allocblk = allociblk; 473 if (nb == 0) { 474 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0); 475 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 476 if (error) 477 return error; 478 nb = newb; 479 *allocblk++ = nb; 480 bp = getblk(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0); 481 bp->b_blkno = FFS_FSBTODB(fs, nb); 482 clrbuf(bp); 483 /* 484 * Write synchronously so that indirect blocks 485 * never point at garbage. 486 */ 487 if ((error = bwrite(bp)) != 0) 488 return error; 489 allocib = &ip->i_ffs2_ib[indirs[0].in_off]; 490 *allocib = ufs_rw64(nb, needswap); 491 } 492 493 /* 494 * Fetch through the indirect blocks, allocating as necessary. 495 */ 496 497 for (i = 1;;) { 498 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 499 0, &bp); 500 if (error) { 501 return error; 502 } 503 bap = (int64_t *)bp->b_data; 504 nb = ufs_rw64(bap[indirs[i].in_off], needswap); 505 if (i == num) 506 break; 507 i++; 508 if (nb != 0) { 509 brelse(bp, 0); 510 continue; 511 } 512 if (pref == 0) 513 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0); 514 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 515 if (error) { 516 brelse(bp, 0); 517 return error; 518 } 519 nb = newb; 520 *allocblk++ = nb; 521 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0); 522 nbp->b_blkno = FFS_FSBTODB(fs, nb); 523 clrbuf(nbp); 524 /* 525 * Write synchronously so that indirect blocks 526 * never point at garbage. 527 */ 528 529 if ((error = bwrite(nbp)) != 0) { 530 brelse(bp, 0); 531 return error; 532 } 533 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap); 534 535 bwrite(bp); 536 } 537 538 /* 539 * Get the data block, allocating if necessary. 540 */ 541 542 if (nb == 0) { 543 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]); 544 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 545 if (error) { 546 brelse(bp, 0); 547 return error; 548 } 549 nb = newb; 550 *allocblk++ = nb; 551 if (bpp != NULL) { 552 nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0); 553 nbp->b_blkno = FFS_FSBTODB(fs, nb); 554 clrbuf(nbp); 555 *bpp = nbp; 556 } 557 bap[indirs[num].in_off] = ufs_rw64(nb, needswap); 558 559 /* 560 * If required, write synchronously, otherwise use 561 * delayed write. 562 */ 563 bwrite(bp); 564 return (0); 565 } 566 brelse(bp, 0); 567 if (bpp != NULL) { 568 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, 0, 569 &nbp); 570 if (error) { 571 brelse(nbp, 0); 572 return error; 573 } 574 *bpp = nbp; 575 } 576 return (0); 577 } 578
Indexes created Sun Sep 21 20:09:37 GMT 2025