usr.sbin/makefs/ffs/ffs_balloc.c

   1 /*      $NetBSD: ffs_balloc.c,v 1.21 2015/03/29 05:52:59 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.21 2015/03/29 05:52:59 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[UFS_NIADDR + 2];
  92         daddr_t newb, pref;
  93         int32_t *bap;
  94         int osize, nsize, num, i, error;
  95         int32_t *allocblk, allociblk[UFS_NIADDR + 1];
  96         int32_t *allocib;
  97         const int needswap = UFS_FSNEEDSWAP(fs);
  98
  99         lbn = ffs_lblkno(fs, offset);
 100         size = ffs_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 = ffs_lblkno(fs, ip->i_ffs1_size);
 116         if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
 117                 nb = lastlbn;
 118                 osize = ffs_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 UFS_NDADDR blocks are direct blocks
 127          */
 128
 129         if (lbn < UFS_NDADDR) {
 130                 nb = ufs_rw32(ip->i_ffs1_db[lbn], needswap);
 131                 if (nb != 0 && ip->i_ffs1_size >= ffs_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_devvp, lbn, fs->fs_bsize,
 142                                     0, bpp);
 143                                 if (error) {
 144                                         brelse(*bpp, 0);
 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 = ffs_fragroundup(fs, ffs_blkoff(fs, ip->i_ffs1_size));
 157                         nsize = ffs_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_devvp, lbn, osize,
 168                                             0, bpp);
 169                                         if (error) {
 170                                                 brelse(*bpp, 0);
 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 < ffs_lblktosize(fs, lbn + 1))
 187                                 nsize = ffs_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_devvp, lbn, nsize, 0, 0);
 198                                 bp->b_blkno = FFS_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_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0);
 236                 bp->b_blkno = FFS_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_devvp, indirs[i].in_lbn, fs->fs_bsize,
 254                     0, &bp);
 255                 if (error) {
 256                         brelse(bp, 0);
 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, 0);
 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, 0);
 273                         return error;
 274                 }
 275                 nb = newb;
 276                 *allocblk++ = nb;
 277                 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0);
 278                 nbp->b_blkno = FFS_FSBTODB(fs, nb);
 279                 clrbuf(nbp);
 280                 /*
 281                  * Write synchronously so that indirect blocks
 282                  * never point at garbage.
 283                  */
 284
 285                 if ((error = bwrite(nbp)) != 0) {
 286                         brelse(bp, 0);
 287                         return error;
 288                 }
 289                 bap[indirs[i - 1].in_off] = ufs_rw32(nb, needswap);
 290
 291                 bwrite(bp);
 292         }
 293
 294         /*
 295          * Get the data block, allocating if necessary.
 296          */
 297
 298         if (nb == 0) {
 299                 pref = ffs_blkpref_ufs1(ip, lbn, indirs[num].in_off, &bap[0]);
 300                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 301                 if (error) {
 302                         brelse(bp, 0);
 303                         return error;
 304                 }
 305                 nb = newb;
 306                 *allocblk++ = nb;
 307                 if (bpp != NULL) {
 308                         nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0);
 309                         nbp->b_blkno = FFS_FSBTODB(fs, nb);
 310                         clrbuf(nbp);
 311                         *bpp = nbp;
 312                 }
 313                 bap[indirs[num].in_off] = ufs_rw32(nb, needswap);
 314
 315                 /*
 316                  * If required, write synchronously, otherwise use
 317                  * delayed write.
 318                  */
 319                 bwrite(bp);
 320                 return (0);
 321         }
 322         brelse(bp, 0);
 323         if (bpp != NULL) {
 324                 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, 0, &nbp);
 325                 if (error) {
 326                         brelse(nbp, 0);
 327                         return error;
 328                 }
 329                 *bpp = nbp;
 330         }
 331         return (0);
 332 }
 333
 334 static int
 335 ffs_balloc_ufs2(struct inode *ip, off_t offset, int bufsize, struct buf **bpp)
 336 {
 337         daddr_t lbn, lastlbn;
 338         int size;
 339         struct 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 = ffs_lblkno(fs, offset);
 350         size = ffs_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 = ffs_lblkno(fs, ip->i_ffs2_size);
 366         if (lastlbn < UFS_NDADDR && lastlbn < lbn) {
 367                 nb = lastlbn;
 368                 osize = ffs_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 >= ffs_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(ip->i_devvp, lbn, fs->fs_bsize,
 392                                     0, bpp);
 393                                 if (error) {
 394                                         brelse(*bpp, 0);
 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 = ffs_fragroundup(fs, ffs_blkoff(fs, ip->i_ffs2_size));
 407                         nsize = ffs_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(ip->i_devvp, lbn, osize,
 418                                             0, bpp);
 419                                         if (error) {
 420                                                 brelse(*bpp, 0);
 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 < ffs_lblktosize(fs, lbn + 1))
 437                                 nsize = ffs_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(ip->i_devvp, lbn, nsize, 0, 0);
 448                                 bp->b_blkno = FFS_FSBTODB(fs, newb);
 449                                 clrbuf(bp);
 450                                 *bpp = bp;
 451                         }
 452                 }
 453                 ip->i_ffs2_db[lbn] = ufs_rw64(newb, needswap);
 454                 return (0);
 455         }
 456
 457         /*
 458          * Determine the number of levels of indirection.
 459          */
 460
 461         pref = 0;
 462         if ((error = ufs_getlbns(ip, lbn, indirs, &num)) != 0)
 463                 return (error);
 464
 465         if (num < 1) {
 466                 warnx("ffs_balloc: ufs_getlbns returned indirect block");
 467                 abort();
 468         }
 469
 470         /*
 471          * Fetch the first indirect block allocating if necessary.
 472          */
 473
 474         --num;
 475         nb = ufs_rw64(ip->i_ffs2_ib[indirs[0].in_off], needswap);
 476         allocib = NULL;
 477         allocblk = allociblk;
 478         if (nb == 0) {
 479                 pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
 480                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 481                 if (error)
 482                         return error;
 483                 nb = newb;
 484                 *allocblk++ = nb;
 485                 bp = getblk(ip->i_devvp, indirs[1].in_lbn, fs->fs_bsize, 0, 0);
 486                 bp->b_blkno = FFS_FSBTODB(fs, nb);
 487                 clrbuf(bp);
 488                 /*
 489                  * Write synchronously so that indirect blocks
 490                  * never point at garbage.
 491                  */
 492                 if ((error = bwrite(bp)) != 0)
 493                         return error;
 494                 allocib = &ip->i_ffs2_ib[indirs[0].in_off];
 495                 *allocib = ufs_rw64(nb, needswap);
 496         }
 497
 498         /*
 499          * Fetch through the indirect blocks, allocating as necessary.
 500          */
 501
 502         for (i = 1;;) {
 503                 error = bread(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize,
 504                     0, &bp);
 505                 if (error) {
 506                         brelse(bp, 0);
 507                         return error;
 508                 }
 509                 bap = (int64_t *)bp->b_data;
 510                 nb = ufs_rw64(bap[indirs[i].in_off], needswap);
 511                 if (i == num)
 512                         break;
 513                 i++;
 514                 if (nb != 0) {
 515                         brelse(bp, 0);
 516                         continue;
 517                 }
 518                 if (pref == 0)
 519                         pref = ffs_blkpref_ufs2(ip, lbn, 0, (int64_t *)0);
 520                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 521                 if (error) {
 522                         brelse(bp, 0);
 523                         return error;
 524                 }
 525                 nb = newb;
 526                 *allocblk++ = nb;
 527                 nbp = getblk(ip->i_devvp, indirs[i].in_lbn, fs->fs_bsize, 0, 0);
 528                 nbp->b_blkno = FFS_FSBTODB(fs, nb);
 529                 clrbuf(nbp);
 530                 /*
 531                  * Write synchronously so that indirect blocks
 532                  * never point at garbage.
 533                  */
 534
 535                 if ((error = bwrite(nbp)) != 0) {
 536                         brelse(bp, 0);
 537                         return error;
 538                 }
 539                 bap[indirs[i - 1].in_off] = ufs_rw64(nb, needswap);
 540
 541                 bwrite(bp);
 542         }
 543
 544         /*
 545          * Get the data block, allocating if necessary.
 546          */
 547
 548         if (nb == 0) {
 549                 pref = ffs_blkpref_ufs2(ip, lbn, indirs[num].in_off, &bap[0]);
 550                 error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize, &newb);
 551                 if (error) {
 552                         brelse(bp, 0);
 553                         return error;
 554                 }
 555                 nb = newb;
 556                 *allocblk++ = nb;
 557                 if (bpp != NULL) {
 558                         nbp = getblk(ip->i_devvp, lbn, fs->fs_bsize, 0, 0);
 559                         nbp->b_blkno = FFS_FSBTODB(fs, nb);
 560                         clrbuf(nbp);
 561                         *bpp = nbp;
 562                 }
 563                 bap[indirs[num].in_off] = ufs_rw64(nb, needswap);
 564
 565                 /*
 566                  * If required, write synchronously, otherwise use
 567                  * delayed write.
 568                  */
 569                 bwrite(bp);
 570                 return (0);
 571         }
 572         brelse(bp, 0);
 573         if (bpp != NULL) {
 574                 error = bread(ip->i_devvp, lbn, (int)fs->fs_bsize, 0,
 575                     &nbp);
 576                 if (error) {
 577                         brelse(nbp, 0);
 578                         return error;
 579                 }
 580                 *bpp = nbp;
 581         }
 582         return (0);
 583 }