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