usr.sbin/makefs/ffs/ffs_balloc.c

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