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