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