usr.sbin/makefs/ffs/ffs_balloc.c

   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 buf **);
  60 static int ffs_balloc_ufs2(struct inode *, off_t, int, struct 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 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, struct buf **bpp)
  81 {
  82         daddr_t lbn, lastlbn;
  83         int size;
  84         int32_t nb;
  85         struct buf *bp, *nbp;
  86         struct fs *fs = ip->i_fs;
  87         struct indir indirs[UFS_NIADDR + 2];
  88         daddr_t newb, pref;
  89         int32_t *bap;
  90         int osize, nsize, num, i, error;
  91         int32_t *allocblk, allociblk[UFS_NIADDR + 1];
  92         int32_t *allocib;
  93         const int needswap = UFS_FSNEEDSWAP(fs);
  94
  95         lbn = lblkno(fs, offset);
  96         size = blkoff(fs, offset) + bufsize;
  97         if (bpp != NULL) {
  98                 *bpp = NULL;
  99         }
 100
 101         assert(size <= fs->fs_bsize);
 102         if (lbn < 0)
 103                 return (EFBIG);
 104
 105         /*
 106          * If the next write will extend the file into a new block,
 107          * and the file is currently composed of a fragment
 108          * this fragment has to be extended to be a full block.
 109          */
 110
 111         lastlbn = lblkno(fs, ip->i_ffs1_size);
 112         if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
 113                 nb = lastlbn;
 114                 osize = blksize(fs, ip, nb);
 115                 if (osize < fs->fs_bsize && osize > 0) {
 116                         warnx("need to ffs_realloccg; not supported!");
 117                         abort();
 118                 }
 119         }
 120
 121         /*
 122          * The first UFS_NDADDR blocks are direct blocks
 123          */
 124
 125         if (lbn < UFS_NDADDR) {
 126                 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
 127                 if (nb != 0 && ip->i_ffs1_size >=
 128                     (uint64_t)lblktosize(fs, lbn + 1)) {
 129
 130                         /*
 131                          * The block is an already-allocated direct block
 132                          * and the file already extends past this block,
 133                          * thus this must be a whole block.
 134                          * Just read the block (if requested).
 135                          */
 136
 137                         if (bpp != NULL) {
 138                                 error = bread(ip->i_devvp, lbn, fs->fs_bsize,
 139                                     NULL, bpp);
 140                                 if (error) {
 141                                         brelse(*bpp);
 142                                         return (error);
 143                                 }
 144                         }
 145                         return (0);
 146                 }
 147                 if (nb != 0) {
 148
 149                         /*
 150                          * Consider need to reallocate a fragment.
 151                          */
 152
 153                         osize = fragroundup(fs, blkoff(fs, ip->i_ffs1_size));
 154                         nsize = fragroundup(fs, size);
 155                         if (nsize <= osize) {
 156
 157                                 /*
 158                                  * The existing block is already
 159                                  * at least as big as we want.
 160                                  * Just read the block (if requested).
 161                                  */
 162
 163                                 if (bpp != NULL) {
 164                                         error = bread(ip->i_devvp, lbn, osize,
 165                                             NULL, bpp);
 166                                         if (error) {
 167                                                 brelse(*bpp);
 168                                                 return (error);
 169                                         }
 170                                 }
 171                                 return 0;
 172                         } else {
 173                                 warnx("need to ffs_realloccg; not supported!");
 174                                 abort();
 175                         }
 176                 } else {
 177
 178                         /*
 179                          * the block was not previously allocated,
 180                          * allocate a new block or fragment.
 181                          */
 182
 183                         if (ip->i_ffs1_size < (uint64_t)lblktosize(fs, lbn + 1))
 184                                 nsize = fragroundup(fs, size);
 185                         else
 186                                 nsize = fs->fs_bsize;
 187                         error = ffs_alloc(ip, lbn,
 188                             ffs_blkpref_ufs1(ip, lbn, (int)lbn,
 189                                 &ip->i_ffs1_db[0]),
 190                                 nsize, &newb);
 191                         if (error)
 192                                 return (error);
 193                         if (bpp != NULL) {
 194                                 bp = getblk(ip->i_devvp, lbn, nsize, 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(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, 0);
 233                 bp->b_blkno = fsbtodb(fs, nb);
 234                 clrbuf(bp);
 235                 /*
 236                  * Write synchronously so that indirect blocks
 237                  * never point at garbage.
 238                  */
 239                 if ((error = bwrite(bp)) != 0)
 240                         return error;
 241                 allocib = &ip->i_ffs1_ib[indirs[0].in_off];
 242                 *allocib = ufs_rw32((int32_t)nb, needswap);
 243         }
 244
 245         /*
 246          * Fetch through the indirect blocks, allocating as necessary.
 247          */
 248
 249         for (i = 1;;) {
 250                 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize,
 251                     NULL, &bp);
 252                 if (error) {
 253                         brelse(bp);
 254                         return error;
 255                 }
 256                 bap = (int32_t *)bp->b_data;
 257                 nb = ufs_rw32(bap[indirs[i].in_off], needswap);
 258                 if (i == num)
 259                         break;
 260                 i++;
 261                 if (nb != 0) {
 262                         brelse(bp);
 263                         continue;
 264                 }
 265                 if (pref == 0)
 266                         pref = ffs_blkpref_ufs1(ip, lbn, 0, (int32_t *)0);
 267                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 268                 if (error) {
 269                         brelse(bp);
 270                         return error;
 271                 }
 272                 nb = newb;
 273                 *allocblk++ = nb;
 274                 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, 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(ip->i_devvp, lbn, fs->fs_bsize, 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(ip->i_devvp, lbn, (int)fs->fs_bsize, NULL, &nbp);
 322                 if (error) {
 323                         brelse(nbp);
 324                         return error;
 325                 }
 326                 *bpp = nbp;
 327         }
 328         return (0);
 329 }
 330
 331 static int
 332 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
 333 {
 334         daddr_t lbn, lastlbn;
 335         int size;
 336         struct buf *bp, *nbp;
 337         struct fs *fs = ip->i_fs;
 338         struct indir indirs[UFS_NIADDR + 2];
 339         daddr_t newb, pref, nb;
 340         int64_t *bap;
 341         int osize, nsize, num, i, error;
 342         int64_t *allocblk, allociblk[UFS_NIADDR + 1];
 343         int64_t *allocib;
 344         const int needswap = UFS_FSNEEDSWAP(fs);
 345
 346         lbn = lblkno(fs, offset);
 347         size = blkoff(fs, offset) + bufsize;
 348         if (bpp != NULL) {
 349                 *bpp = NULL;
 350         }
 351
 352         assert(size <= fs->fs_bsize);
 353         if (lbn < 0)
 354                 return (EFBIG);
 355
 356         /*
 357          * If the next write will extend the file into a new block,
 358          * and the file is currently composed of a fragment
 359          * this fragment has to be extended to be a full block.
 360          */
 361
 362         lastlbn = lblkno(fs, ip->i_ffs2_size);
 363         if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
 364                 nb = lastlbn;
 365                 osize = blksize(fs, ip, nb);
 366                 if (osize < fs->fs_bsize && osize > 0) {
 367                         warnx("need to ffs_realloccg; not supported!");
 368                         abort();
 369                 }
 370         }
 371
 372         /*
 373          * The first UFS_NDADDR blocks are direct blocks
 374          */
 375
 376         if (lbn < UFS_NDADDR) {
 377                 nb = ufs_rw64(ip->i_ffs2_db[lbn], needswap);
 378                 if (nb != 0 && ip->i_ffs2_size >=
 379                     (uint64_t)lblktosize(fs, lbn + 1)) {
 380
 381                         /*
 382                          * The block is an already-allocated direct block
 383                          * and the file already extends past this block,
 384                          * thus this must be a whole block.
 385                          * Just read the block (if requested).
 386                          */
 387
 388                         if (bpp != NULL) {
 389                                 error = bread(ip->i_devvp, lbn, fs->fs_bsize,
 390                                     NULL, bpp);
 391                                 if (error) {
 392                                         brelse(*bpp);
 393                                         return (error);
 394                                 }
 395                         }
 396                         return (0);
 397                 }
 398                 if (nb != 0) {
 399
 400                         /*
 401                          * Consider need to reallocate a fragment.
 402                          */
 403
 404                         osize = fragroundup(fs, blkoff(fs, ip->i_ffs2_size));
 405                         nsize = fragroundup(fs, size);
 406                         if (nsize <= osize) {
 407
 408                                 /*
 409                                  * The existing block is already
 410                                  * at least as big as we want.
 411                                  * Just read the block (if requested).
 412                                  */
 413
 414                                 if (bpp != NULL) {
 415                                         error = bread(ip->i_devvp, lbn, osize,
 416                                             NULL, bpp);
 417                                         if (error) {
 418                                                 brelse(*bpp);
 419                                                 return (error);
 420                                         }
 421                                 }
 422                                 return 0;
 423                         } else {
 424                                 warnx("need to ffs_realloccg; not supported!");
 425                                 abort();
 426                         }
 427                 } else {
 428
 429                         /*
 430                          * the block was not previously allocated,
 431                          * allocate a new block or fragment.
 432                          */
 433
 434                         if (ip->i_ffs2_size < (uint64_t)lblktosize(fs, lbn + 1))
 435                                 nsize = fragroundup(fs, size);
 436                         else
 437                                 nsize = fs->fs_bsize;
 438                         error = ffs_alloc(ip, lbn,
 439                             ffs_blkpref_ufs2(ip, lbn, (int)lbn,
 440                                 &ip->i_ffs2_db[0]),
 441                                 nsize, &newb);
 442                         if (error)
 443                                 return (error);
 444                         if (bpp != NULL) {
 445                                 bp = getblk(ip->i_devvp, lbn, nsize, 0, 0, 0);
 446                                 bp->b_blkno = fsbtodb(fs, newb);
 447                                 clrbuf(bp);
 448                                 *bpp = bp;
 449                         }
 450                 }
 451                 ip->i_ffs2_db[lbn] = ufs_rw64(newb, needswap);
 452                 return (0);
 453         }
 454
 455         /*
 456          * Determine the number of levels of indirection.
 457          */
 458
 459         pref = 0;
 460         if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
 461                 return (error);
 462
 463         if (num < 1) {
 464                 warnx("ffs_balloc: ufs_getlbns returned indirect block");
 465                 abort();
 466         }
 467
 468         /*
 469          * Fetch the first indirect block allocating if necessary.
 470          */
 471
 472         --num;
 473         nb = ufs_rw64(ip->i_ffs2_ib[indirs[0].in_off], needswap);
 474         allocib = NULL;
 475         allocblk = allociblk;
 476         if (nb == 0) {
 477                 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
 478                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 479                 if (error)
 480                         return error;
 481                 nb = newb;
 482                 *allocblk++ = nb;
 483                 bp = getblk(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0, 0);
 484                 bp->b_blkno = fsbtodb(fs, nb);
 485                 clrbuf(bp);
 486                 /*
 487                  * Write synchronously so that indirect blocks
 488                  * never point at garbage.
 489                  */
 490                 if ((error = bwrite(bp)) != 0)
 491                         return error;
 492                 allocib = &ip->i_ffs2_ib[indirs[0].in_off];
 493                 *allocib = ufs_rw64(nb, needswap);
 494         }
 495
 496         /*
 497          * Fetch through the indirect blocks, allocating as necessary.
 498          */
 499
 500         for (i = 1;;) {
 501                 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize,
 502                     NULL, &bp);
 503                 if (error) {
 504                         brelse(bp);
 505                         return error;
 506                 }
 507                 bap = (int64_t *)bp->b_data;
 508                 nb = ufs_rw64(bap[indirs[i].in_off], needswap);
 509                 if (i == num)
 510                         break;
 511                 i++;
 512                 if (nb != 0) {
 513                         brelse(bp);
 514                         continue;
 515                 }
 516                 if (pref == 0)
 517                         pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
 518                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 519                 if (error) {
 520                         brelse(bp);
 521                         return error;
 522                 }
 523                 nb = newb;
 524                 *allocblk++ = nb;
 525                 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0, 0);
 526                 nbp->b_blkno = fsbtodb(fs, nb);
 527                 clrbuf(nbp);
 528                 /*
 529                  * Write synchronously so that indirect blocks
 530                  * never point at garbage.
 531                  */
 532
 533                 if ((error = bwrite(nbp)) != 0) {
 534                         brelse(bp);
 535                         return error;
 536                 }
 537                 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap);
 538
 539                 bwrite(bp);
 540         }
 541
 542         /*
 543          * Get the data block, allocating if necessary.
 544          */
 545
 546         if (nb == 0) {
 547                 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]);
 548                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 549                 if (error) {
 550                         brelse(bp);
 551                         return error;
 552                 }
 553                 nb = newb;
 554                 *allocblk++ = nb;
 555                 if (bpp != NULL) {
 556                         nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0, 0);
 557                         nbp->b_blkno = fsbtodb(fs, nb);
 558                         clrbuf(nbp);
 559                         *bpp = nbp;
 560                 }
 561                 bap[indirs[num].in_off] = ufs_rw64(nb, needswap);
 562
 563                 /*
 564                  * If required, write synchronously, otherwise use
 565                  * delayed write.
 566                  */
 567                 bwrite(bp);
 568                 return (0);
 569         }
 570         brelse(bp);
 571         if (bpp != NULL) {
 572                 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, NULL, &nbp);
 573                 if (error) {
 574                         brelse(nbp);
 575                         return error;
 576                 }
 577                 *bpp = nbp;
 578         }
 579         return (0);
 580 }