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