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