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 #include <sys/param.h> 39 #include <sys/time.h> 40 41 #include <assert.h> 42 #include <errno.h> 43 #include <stdio.h> 44 #include <stdlib.h> 45 #include <string.h> 46 47 #include "makefs.h" 48 49 #include <ufs/ufs/dinode.h> 50 #include <ufs/ffs/fs.h> 51 52 #include "ffs/ufs_bswap.h" 53 #include "ffs/buf.h" 54 #include "ffs/ufs_inode.h" 55 #include "ffs/ffs_extern.h" 56 57 static int ffs_balloc_ufs1(struct inode *, off_t, int, struct m_buf **); 58 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct m_buf **); 59 60 /* 61 * Balloc defines the structure of file system storage 62 * by allocating the physical blocks on a device given 63 * the inode and the logical block number in a file. 64 * 65 * Assume: flags == B_SYNC | B_CLRBUF 66 */ 67 68 int 69 ffs_balloc(struct inode *ip, off_t offset, int bufsize, struct m_buf **bpp) 70 { 71 if (ip->i_fs->fs_magic == FS_UFS2_MAGIC) 72 return ffs_balloc_ufs2(ip, offset, bufsize, bpp); 73 else 74 return ffs_balloc_ufs1(ip, offset, bufsize, bpp); 75 } 76 77 static int 78 ffs_balloc_ufs1(struct inode *ip, off_t offset, int bufsize, 79 struct m_buf **bpp) 80 { 81 daddr_t lbn, lastlbn; 82 int size; 83 int32_t nb; 84 struct m_buf *bp, *nbp; 85 struct fs *fs = ip->i_fs; 86 struct indir indirs[UFS_NIADDR + 2]; 87 daddr_t newb, pref; 88 int32_t *bap; 89 int osize, nsize, num, i, error; 90 int32_t *allocblk, allociblk[UFS_NIADDR + 1]; 91 int32_t *allocib; 92 const int needswap = UFS_FSNEEDSWAP(fs); 93 94 lbn = lblkno(fs, offset); 95 size = blkoff(fs, offset) + bufsize; 96 if (bpp != NULL) { 97 *bpp = NULL; 98 } 99 100 assert(size <= fs->fs_bsize); 101 if (lbn < 0) 102 return (EFBIG); 103 104 /* 105 * If the next write will extend the file into a new block, 106 * and the file is currently composed of a fragment 107 * this fragment has to be extended to be a full block. 108 */ 109 110 lastlbn = lblkno(fs, ip->i_ffs1_size); 111 if (lastlbn < UFS_NDADDR && lastlbn < lbn) { 112 nb = lastlbn; 113 osize = blksize(fs, ip, nb); 114 if (osize < fs->fs_bsize && osize > 0) { 115 warnx("need to ffs_realloccg; not supported!"); 116 abort(); 117 } 118 } 119 120 /* 121 * The first UFS_NDADDR blocks are direct blocks 122 */ 123 124 if (lbn < UFS_NDADDR) { 125 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap); 126 if (nb != 0 && ip->i_ffs1_size >= 127 (uint64_t)lblktosize(fs, lbn + 1)) { 128 129 /* 130 * The block is an already-allocated direct block 131 * and the file already extends past this block, 132 * thus this must be a whole block. 133 * Just read the block (if requested). 134 */ 135 136 if (bpp != NULL) { 137 error = bread((void *)ip->i_devvp, lbn, 138 fs->fs_bsize, NULL, bpp); 139 if (error) { 140 brelse(*bpp); 141 return (error); 142 } 143 } 144 return (0); 145 } 146 if (nb != 0) { 147 148 /* 149 * Consider need to reallocate a fragment. 150 */ 151 152 osize = fragroundup(fs, blkoff(fs, ip->i_ffs1_size)); 153 nsize = fragroundup(fs, size); 154 if (nsize <= osize) { 155 156 /* 157 * The existing block is already 158 * at least as big as we want. 159 * Just read the block (if requested). 160 */ 161 162 if (bpp != NULL) { 163 error = bread((void *)ip->i_devvp, lbn, 164 osize, NULL, bpp); 165 if (error) { 166 brelse(*bpp); 167 return (error); 168 } 169 } 170 return 0; 171 } else { 172 warnx("need to ffs_realloccg; not supported!"); 173 abort(); 174 } 175 } else { 176 177 /* 178 * the block was not previously allocated, 179 * allocate a new block or fragment. 180 */ 181 182 if (ip->i_ffs1_size < (uint64_t)lblktosize(fs, lbn + 1)) 183 nsize = fragroundup(fs, size); 184 else 185 nsize = fs->fs_bsize; 186 error = ffs_alloc(ip, lbn, 187 ffs_blkpref_ufs1(ip, lbn, (int)lbn, 188 &ip->i_ffs1_db[0]), 189 nsize, &newb); 190 if (error) 191 return (error); 192 if (bpp != NULL) { 193 bp = getblk((void *)ip->i_devvp, lbn, nsize, 194 0, 0, 0); 195 bp->b_blkno = fsbtodb(fs, newb); 196 clrbuf(bp); 197 *bpp = bp; 198 } 199 } 200 ip->i_ffs1_db[lbn] = ufs_rw32((int32_t)newb, needswap); 201 return (0); 202 } 203 204 /* 205 * Determine the number of levels of indirection. 206 */ 207 208 pref = 0; 209 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0) 210 return (error); 211 212 if (num < 1) { 213 warnx("ffs_balloc: ufs_getlbns returned indirect block"); 214 abort(); 215 } 216 217 /* 218 * Fetch the first indirect block allocating if necessary. 219 */ 220 221 --num; 222 nb = ufs_rw32(ip->i_ffs1_ib[indirs[0].in_off], needswap); 223 allocib = NULL; 224 allocblk = allociblk; 225 if (nb == 0) { 226 pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0); 227 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 228 if (error) 229 return error; 230 nb = newb; 231 *allocblk++ = nb; 232 bp = getblk((void *)ip->i_devvp, indirs[1].in_lbn, 233 fs->fs_bsize, 0, 0, 0); 234 bp->b_blkno = fsbtodb(fs, nb); 235 clrbuf(bp); 236 /* 237 * Write synchronously so that indirect blocks 238 * never point at garbage. 239 */ 240 if ((error = bwrite(bp)) != 0) 241 return error; 242 allocib = &ip->i_ffs1_ib[indirs[0].in_off]; 243 *allocib = ufs_rw32((int32_t)nb, needswap); 244 } 245 246 /* 247 * Fetch through the indirect blocks, allocating as necessary. 248 */ 249 250 for (i = 1;;) { 251 error = bread((void *)ip->i_devvp, indirs[i].in_lbn, 252 fs->fs_bsize, NULL, &bp); 253 if (error) { 254 brelse(bp); 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); 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); 271 return error; 272 } 273 nb = newb; 274 *allocblk++ = nb; 275 nbp = getblk((void *)ip->i_devvp, indirs[i].in_lbn, 276 fs->fs_bsize, 0, 0, 0); 277 nbp->b_blkno = fsbtodb(fs, nb); 278 clrbuf(nbp); 279 /* 280 * Write synchronously so that indirect blocks 281 * never point at garbage. 282 */ 283 284 if ((error = bwrite(nbp)) != 0) { 285 brelse(bp); 286 return error; 287 } 288 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap); 289 290 bwrite(bp); 291 } 292 293 /* 294 * Get the data block, allocating if necessary. 295 */ 296 297 if (nb == 0) { 298 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]); 299 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 300 if (error) { 301 brelse(bp); 302 return error; 303 } 304 nb = newb; 305 *allocblk++ = nb; 306 if (bpp != NULL) { 307 nbp = getblk((void *)ip->i_devvp, lbn, fs->fs_bsize, 308 0, 0, 0); 309 nbp->b_blkno = fsbtodb(fs, nb); 310 clrbuf(nbp); 311 *bpp = nbp; 312 } 313 bap[indirs[num].in_off] = ufs_rw32(nb, needswap); 314 315 /* 316 * If required, write synchronously, otherwise use 317 * delayed write. 318 */ 319 bwrite(bp); 320 return (0); 321 } 322 brelse(bp); 323 if (bpp != NULL) { 324 error = bread((void *)ip->i_devvp, lbn, (int)fs->fs_bsize, 325 NULL, &nbp); 326 if (error) { 327 brelse(nbp); 328 return error; 329 } 330 *bpp = nbp; 331 } 332 return (0); 333 } 334 335 static int 336 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, 337 struct m_buf **bpp) 338 { 339 daddr_t lbn, lastlbn; 340 int size; 341 struct m_buf *bp, *nbp; 342 struct fs *fs = ip->i_fs; 343 struct indir indirs[UFS_NIADDR + 2]; 344 daddr_t newb, pref, nb; 345 int64_t *bap; 346 int osize, nsize, num, i, error; 347 int64_t *allocblk, allociblk[UFS_NIADDR + 1]; 348 int64_t *allocib; 349 const int needswap = UFS_FSNEEDSWAP(fs); 350 351 lbn = lblkno(fs, offset); 352 size = blkoff(fs, offset) + bufsize; 353 if (bpp != NULL) { 354 *bpp = NULL; 355 } 356 357 assert(size <= fs->fs_bsize); 358 if (lbn < 0) 359 return (EFBIG); 360 361 /* 362 * If the next write will extend the file into a new block, 363 * and the file is currently composed of a fragment 364 * this fragment has to be extended to be a full block. 365 */ 366 367 lastlbn = lblkno(fs, ip->i_ffs2_size); 368 if (lastlbn < UFS_NDADDR && lastlbn < lbn) { 369 nb = lastlbn; 370 osize = blksize(fs, ip, nb); 371 if (osize < fs->fs_bsize && osize > 0) { 372 warnx("need to ffs_realloccg; not supported!"); 373 abort(); 374 } 375 } 376 377 /* 378 * The first UFS_NDADDR blocks are direct blocks 379 */ 380 381 if (lbn < UFS_NDADDR) { 382 nb = ufs_rw64(ip->i_ffs2_db[lbn], needswap); 383 if (nb != 0 && ip->i_ffs2_size >= 384 (uint64_t)lblktosize(fs, lbn + 1)) { 385 386 /* 387 * The block is an already-allocated direct block 388 * and the file already extends past this block, 389 * thus this must be a whole block. 390 * Just read the block (if requested). 391 */ 392 393 if (bpp != NULL) { 394 error = bread((void *)ip->i_devvp, lbn, 395 fs->fs_bsize, NULL, bpp); 396 if (error) { 397 brelse(*bpp); 398 return (error); 399 } 400 } 401 return (0); 402 } 403 if (nb != 0) { 404 405 /* 406 * Consider need to reallocate a fragment. 407 */ 408 409 osize = fragroundup(fs, blkoff(fs, ip->i_ffs2_size)); 410 nsize = fragroundup(fs, size); 411 if (nsize <= osize) { 412 413 /* 414 * The existing block is already 415 * at least as big as we want. 416 * Just read the block (if requested). 417 */ 418 419 if (bpp != NULL) { 420 error = bread((void *)ip->i_devvp, lbn, 421 osize, NULL, bpp); 422 if (error) { 423 brelse(*bpp); 424 return (error); 425 } 426 } 427 return 0; 428 } else { 429 warnx("need to ffs_realloccg; not supported!"); 430 abort(); 431 } 432 } else { 433 434 /* 435 * the block was not previously allocated, 436 * allocate a new block or fragment. 437 */ 438 439 if (ip->i_ffs2_size < (uint64_t)lblktosize(fs, lbn + 1)) 440 nsize = fragroundup(fs, size); 441 else 442 nsize = fs->fs_bsize; 443 error = ffs_alloc(ip, lbn, 444 ffs_blkpref_ufs2(ip, lbn, (int)lbn, 445 &ip->i_ffs2_db[0]), 446 nsize, &newb); 447 if (error) 448 return (error); 449 if (bpp != NULL) { 450 bp = getblk((void *)ip->i_devvp, lbn, nsize, 451 0, 0, 0); 452 bp->b_blkno = fsbtodb(fs, newb); 453 clrbuf(bp); 454 *bpp = bp; 455 } 456 } 457 ip->i_ffs2_db[lbn] = ufs_rw64(newb, needswap); 458 return (0); 459 } 460 461 /* 462 * Determine the number of levels of indirection. 463 */ 464 465 pref = 0; 466 if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0) 467 return (error); 468 469 if (num < 1) { 470 warnx("ffs_balloc: ufs_getlbns returned indirect block"); 471 abort(); 472 } 473 474 /* 475 * Fetch the first indirect block allocating if necessary. 476 */ 477 478 --num; 479 nb = ufs_rw64(ip->i_ffs2_ib[indirs[0].in_off], needswap); 480 allocib = NULL; 481 allocblk = allociblk; 482 if (nb == 0) { 483 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0); 484 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 485 if (error) 486 return error; 487 nb = newb; 488 *allocblk++ = nb; 489 bp = getblk((void *)ip->i_devvp, indirs[1].in_lbn, 490 fs->fs_bsize, 0, 0, 0); 491 bp->b_blkno = fsbtodb(fs, nb); 492 clrbuf(bp); 493 /* 494 * Write synchronously so that indirect blocks 495 * never point at garbage. 496 */ 497 if ((error = bwrite(bp)) != 0) 498 return error; 499 allocib = &ip->i_ffs2_ib[indirs[0].in_off]; 500 *allocib = ufs_rw64(nb, needswap); 501 } 502 503 /* 504 * Fetch through the indirect blocks, allocating as necessary. 505 */ 506 507 for (i = 1;;) { 508 error = bread((void *)ip->i_devvp, indirs[i].in_lbn, 509 fs->fs_bsize, NULL, &bp); 510 if (error) { 511 brelse(bp); 512 return error; 513 } 514 bap = (int64_t *)bp->b_data; 515 nb = ufs_rw64(bap[indirs[i].in_off], needswap); 516 if (i == num) 517 break; 518 i++; 519 if (nb != 0) { 520 brelse(bp); 521 continue; 522 } 523 if (pref == 0) 524 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0); 525 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 526 if (error) { 527 brelse(bp); 528 return error; 529 } 530 nb = newb; 531 *allocblk++ = nb; 532 nbp = getblk((void *)ip->i_devvp, indirs[i].in_lbn, 533 fs->fs_bsize, 0, 0, 0); 534 nbp->b_blkno = fsbtodb(fs, nb); 535 clrbuf(nbp); 536 /* 537 * Write synchronously so that indirect blocks 538 * never point at garbage. 539 */ 540 541 if ((error = bwrite(nbp)) != 0) { 542 brelse(bp); 543 return error; 544 } 545 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap); 546 547 bwrite(bp); 548 } 549 550 /* 551 * Get the data block, allocating if necessary. 552 */ 553 554 if (nb == 0) { 555 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]); 556 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb); 557 if (error) { 558 brelse(bp); 559 return error; 560 } 561 nb = newb; 562 *allocblk++ = nb; 563 if (bpp != NULL) { 564 nbp = getblk((void *)ip->i_devvp, lbn, fs->fs_bsize, 565 0, 0, 0); 566 nbp->b_blkno = fsbtodb(fs, nb); 567 clrbuf(nbp); 568 *bpp = nbp; 569 } 570 bap[indirs[num].in_off] = ufs_rw64(nb, needswap); 571 572 /* 573 * If required, write synchronously, otherwise use 574 * delayed write. 575 */ 576 bwrite(bp); 577 return (0); 578 } 579 brelse(bp); 580 if (bpp != NULL) { 581 error = bread((void *)ip->i_devvp, lbn, (int)fs->fs_bsize, 582 NULL, &nbp); 583 if (error) { 584 brelse(nbp); 585 return error; 586 } 587 *bpp = nbp; 588 } 589 return (0); 590 } 591