fs/jfs/jfs_dmap.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  *   Copyright (C) International Business Machines Corp., 2000-2004
   4  *   Portions Copyright (C) Tino Reichardt, 2012
   5  */
   6
   7 #include <linux/fs.h>
   8 #include <linux/slab.h>
   9 #include "jfs_incore.h"
  10 #include "jfs_superblock.h"
  11 #include "jfs_dmap.h"
  12 #include "jfs_imap.h"
  13 #include "jfs_lock.h"
  14 #include "jfs_metapage.h"
  15 #include "jfs_debug.h"
  16 #include "jfs_discard.h"
  17
  18 /*
  19  *      SERIALIZATION of the Block Allocation Map.
  20  *
  21  *      the working state of the block allocation map is accessed in
  22  *      two directions:
  23  *
  24  *      1) allocation and free requests that start at the dmap
  25  *         level and move up through the dmap control pages (i.e.
  26  *         the vast majority of requests).
  27  *
  28  *      2) allocation requests that start at dmap control page
  29  *         level and work down towards the dmaps.
  30  *
  31  *      the serialization scheme used here is as follows.
  32  *
  33  *      requests which start at the bottom are serialized against each
  34  *      other through buffers and each requests holds onto its buffers
  35  *      as it works it way up from a single dmap to the required level
  36  *      of dmap control page.
  37  *      requests that start at the top are serialized against each other
  38  *      and request that start from the bottom by the multiple read/single
  39  *      write inode lock of the bmap inode. requests starting at the top
  40  *      take this lock in write mode while request starting at the bottom
  41  *      take the lock in read mode.  a single top-down request may proceed
  42  *      exclusively while multiple bottoms-up requests may proceed
  43  *      simultaneously (under the protection of busy buffers).
  44  *
  45  *      in addition to information found in dmaps and dmap control pages,
  46  *      the working state of the block allocation map also includes read/
  47  *      write information maintained in the bmap descriptor (i.e. total
  48  *      free block count, allocation group level free block counts).
  49  *      a single exclusive lock (BMAP_LOCK) is used to guard this information
  50  *      in the face of multiple-bottoms up requests.
  51  *      (lock ordering: IREAD_LOCK, BMAP_LOCK);
  52  *
  53  *      accesses to the persistent state of the block allocation map (limited
  54  *      to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
  55  */
  56
  57 #define BMAP_LOCK_INIT(bmp)     mutex_init(&bmp->db_bmaplock)
  58 #define BMAP_LOCK(bmp)          mutex_lock(&bmp->db_bmaplock)
  59 #define BMAP_UNLOCK(bmp)        mutex_unlock(&bmp->db_bmaplock)
  60
  61 /*
  62  * forward references
  63  */
  64 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
  65                         int nblocks);
  66 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval);
  67 static int dbBackSplit(dmtree_t * tp, int leafno);
  68 static int dbJoin(dmtree_t * tp, int leafno, int newval);
  69 static void dbAdjTree(dmtree_t * tp, int leafno, int newval);
  70 static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc,
  71                     int level);
  72 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results);
  73 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
  74                        int nblocks);
  75 static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno,
  76                        int nblocks,
  77                        int l2nb, s64 * results);
  78 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
  79                        int nblocks);
  80 static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks,
  81                           int l2nb,
  82                           s64 * results);
  83 static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb,
  84                      s64 * results);
  85 static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno,
  86                       s64 * results);
  87 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks);
  88 static int dbFindBits(u32 word, int l2nb);
  89 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno);
  90 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx);
  91 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
  92                       int nblocks);
  93 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
  94                       int nblocks);
  95 static int dbMaxBud(u8 * cp);
  96 static int blkstol2(s64 nb);
  97
  98 static int cntlz(u32 value);
  99 static int cnttz(u32 word);
 100
 101 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
 102                          int nblocks);
 103 static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks);
 104 static int dbInitDmapTree(struct dmap * dp);
 105 static int dbInitTree(struct dmaptree * dtp);
 106 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i);
 107 static int dbGetL2AGSize(s64 nblocks);
 108
 109 /*
 110  *      buddy table
 111  *
 112  * table used for determining buddy sizes within characters of
 113  * dmap bitmap words.  the characters themselves serve as indexes
 114  * into the table, with the table elements yielding the maximum
 115  * binary buddy of free bits within the character.
 116  */
 117 static const s8 budtab[256] = {
 118         3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 119         2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 120         2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 121         2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 122         2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 123         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 124         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 125         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 126         2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 127         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 128         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 129         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 130         2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 131         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 132         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 133         2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
 134 };
 135
 136 /*
 137  * NAME:        dbMount()
 138  *
 139  * FUNCTION:    initializate the block allocation map.
 140  *
 141  *              memory is allocated for the in-core bmap descriptor and
 142  *              the in-core descriptor is initialized from disk.
 143  *
 144  * PARAMETERS:
 145  *      ipbmap  - pointer to in-core inode for the block map.
 146  *
 147  * RETURN VALUES:
 148  *      0       - success
 149  *      -ENOMEM - insufficient memory
 150  *      -EIO    - i/o error
 151  *      -EINVAL - wrong bmap data
 152  */
 153 int dbMount(struct inode *ipbmap)
 154 {
 155         struct bmap *bmp;
 156         struct dbmap_disk *dbmp_le;
 157         struct metapage *mp;
 158         int i, err;
 159
 160         /*
 161          * allocate/initialize the in-memory bmap descriptor
 162          */
 163         /* allocate memory for the in-memory bmap descriptor */
 164         bmp = kmalloc(sizeof(struct bmap), GFP_KERNEL);
 165         if (bmp == NULL)
 166                 return -ENOMEM;
 167
 168         /* read the on-disk bmap descriptor. */
 169         mp = read_metapage(ipbmap,
 170                            BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
 171                            PSIZE, 0);
 172         if (mp == NULL) {
 173                 err = -EIO;
 174                 goto err_kfree_bmp;
 175         }
 176
 177         /* copy the on-disk bmap descriptor to its in-memory version. */
 178         dbmp_le = (struct dbmap_disk *) mp->data;
 179         bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize);
 180         bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree);
 181
 182         bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage);
 183         if (bmp->db_l2nbperpage > L2PSIZE - L2MINBLOCKSIZE) {
 184                 err = -EINVAL;
 185                 goto err_release_metapage;
 186         }
 187
 188         bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag);
 189         if (!bmp->db_numag) {
 190                 err = -EINVAL;
 191                 goto err_release_metapage;
 192         }
 193
 194         bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel);
 195         bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag);
 196         bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref);
 197         bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel);
 198         bmp->db_agheight = le32_to_cpu(dbmp_le->dn_agheight);
 199         bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth);
 200         bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart);
 201         bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size);
 202         if (bmp->db_agl2size > L2MAXL2SIZE - L2MAXAG ||
 203             bmp->db_agl2size < 0) {
 204                 err = -EINVAL;
 205                 goto err_release_metapage;
 206         }
 207
 208         if (((bmp->db_mapsize - 1) >> bmp->db_agl2size) > MAXAG) {
 209                 err = -EINVAL;
 210                 goto err_release_metapage;
 211         }
 212
 213         for (i = 0; i < MAXAG; i++)
 214                 bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]);
 215         bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize);
 216         bmp->db_maxfreebud = dbmp_le->dn_maxfreebud;
 217
 218         /* release the buffer. */
 219         release_metapage(mp);
 220
 221         /* bind the bmap inode and the bmap descriptor to each other. */
 222         bmp->db_ipbmap = ipbmap;
 223         JFS_SBI(ipbmap->i_sb)->bmap = bmp;
 224
 225         memset(bmp->db_active, 0, sizeof(bmp->db_active));
 226
 227         /*
 228          * allocate/initialize the bmap lock
 229          */
 230         BMAP_LOCK_INIT(bmp);
 231
 232         return (0);
 233
 234 err_release_metapage:
 235         release_metapage(mp);
 236 err_kfree_bmp:
 237         kfree(bmp);
 238         return err;
 239 }
 240
 241
 242 /*
 243  * NAME:        dbUnmount()
 244  *
 245  * FUNCTION:    terminate the block allocation map in preparation for
 246  *              file system unmount.
 247  *
 248  *              the in-core bmap descriptor is written to disk and
 249  *              the memory for this descriptor is freed.
 250  *
 251  * PARAMETERS:
 252  *      ipbmap  - pointer to in-core inode for the block map.
 253  *
 254  * RETURN VALUES:
 255  *      0       - success
 256  *      -EIO    - i/o error
 257  */
 258 int dbUnmount(struct inode *ipbmap, int mounterror)
 259 {
 260         struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
 261
 262         if (!(mounterror || isReadOnly(ipbmap)))
 263                 dbSync(ipbmap);
 264
 265         /*
 266          * Invalidate the page cache buffers
 267          */
 268         truncate_inode_pages(ipbmap->i_mapping, 0);
 269
 270         /* free the memory for the in-memory bmap. */
 271         kfree(bmp);
 272
 273         return (0);
 274 }
 275
 276 /*
 277  *      dbSync()
 278  */
 279 int dbSync(struct inode *ipbmap)
 280 {
 281         struct dbmap_disk *dbmp_le;
 282         struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
 283         struct metapage *mp;
 284         int i;
 285
 286         /*
 287          * write bmap global control page
 288          */
 289         /* get the buffer for the on-disk bmap descriptor. */
 290         mp = read_metapage(ipbmap,
 291                            BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
 292                            PSIZE, 0);
 293         if (mp == NULL) {
 294                 jfs_err("dbSync: read_metapage failed!");
 295                 return -EIO;
 296         }
 297         /* copy the in-memory version of the bmap to the on-disk version */
 298         dbmp_le = (struct dbmap_disk *) mp->data;
 299         dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize);
 300         dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree);
 301         dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage);
 302         dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag);
 303         dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel);
 304         dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag);
 305         dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref);
 306         dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel);
 307         dbmp_le->dn_agheight = cpu_to_le32(bmp->db_agheight);
 308         dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth);
 309         dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart);
 310         dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size);
 311         for (i = 0; i < MAXAG; i++)
 312                 dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]);
 313         dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize);
 314         dbmp_le->dn_maxfreebud = bmp->db_maxfreebud;
 315
 316         /* write the buffer */
 317         write_metapage(mp);
 318
 319         /*
 320          * write out dirty pages of bmap
 321          */
 322         filemap_write_and_wait(ipbmap->i_mapping);
 323
 324         diWriteSpecial(ipbmap, 0);
 325
 326         return (0);
 327 }
 328
 329 /*
 330  * NAME:        dbFree()
 331  *
 332  * FUNCTION:    free the specified block range from the working block
 333  *              allocation map.
 334  *
 335  *              the blocks will be free from the working map one dmap
 336  *              at a time.
 337  *
 338  * PARAMETERS:
 339  *      ip      - pointer to in-core inode;
 340  *      blkno   - starting block number to be freed.
 341  *      nblocks - number of blocks to be freed.
 342  *
 343  * RETURN VALUES:
 344  *      0       - success
 345  *      -EIO    - i/o error
 346  */
 347 int dbFree(struct inode *ip, s64 blkno, s64 nblocks)
 348 {
 349         struct metapage *mp;
 350         struct dmap *dp;
 351         int nb, rc;
 352         s64 lblkno, rem;
 353         struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
 354         struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
 355         struct super_block *sb = ipbmap->i_sb;
 356
 357         IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
 358
 359         /* block to be freed better be within the mapsize. */
 360         if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) {
 361                 IREAD_UNLOCK(ipbmap);
 362                 printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
 363                        (unsigned long long) blkno,
 364                        (unsigned long long) nblocks);
 365                 jfs_error(ip->i_sb, "block to be freed is outside the map\n");
 366                 return -EIO;
 367         }
 368
 369         /**
 370          * TRIM the blocks, when mounted with discard option
 371          */
 372         if (JFS_SBI(sb)->flag & JFS_DISCARD)
 373                 if (JFS_SBI(sb)->minblks_trim <= nblocks)
 374                         jfs_issue_discard(ipbmap, blkno, nblocks);
 375
 376         /*
 377          * free the blocks a dmap at a time.
 378          */
 379         mp = NULL;
 380         for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
 381                 /* release previous dmap if any */
 382                 if (mp) {
 383                         write_metapage(mp);
 384                 }
 385
 386                 /* get the buffer for the current dmap. */
 387                 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
 388                 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
 389                 if (mp == NULL) {
 390                         IREAD_UNLOCK(ipbmap);
 391                         return -EIO;
 392                 }
 393                 dp = (struct dmap *) mp->data;
 394
 395                 /* determine the number of blocks to be freed from
 396                  * this dmap.
 397                  */
 398                 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
 399
 400                 /* free the blocks. */
 401                 if ((rc = dbFreeDmap(bmp, dp, blkno, nb))) {
 402                         jfs_error(ip->i_sb, "error in block map\n");
 403                         release_metapage(mp);
 404                         IREAD_UNLOCK(ipbmap);
 405                         return (rc);
 406                 }
 407         }
 408
 409         /* write the last buffer. */
 410         if (mp)
 411                 write_metapage(mp);
 412
 413         IREAD_UNLOCK(ipbmap);
 414
 415         return (0);
 416 }
 417
 418
 419 /*
 420  * NAME:        dbUpdatePMap()
 421  *
 422  * FUNCTION:    update the allocation state (free or allocate) of the
 423  *              specified block range in the persistent block allocation map.
 424  *
 425  *              the blocks will be updated in the persistent map one
 426  *              dmap at a time.
 427  *
 428  * PARAMETERS:
 429  *      ipbmap  - pointer to in-core inode for the block map.
 430  *      free    - 'true' if block range is to be freed from the persistent
 431  *                map; 'false' if it is to be allocated.
 432  *      blkno   - starting block number of the range.
 433  *      nblocks - number of contiguous blocks in the range.
 434  *      tblk    - transaction block;
 435  *
 436  * RETURN VALUES:
 437  *      0       - success
 438  *      -EIO    - i/o error
 439  */
 440 int
 441 dbUpdatePMap(struct inode *ipbmap,
 442              int free, s64 blkno, s64 nblocks, struct tblock * tblk)
 443 {
 444         int nblks, dbitno, wbitno, rbits;
 445         int word, nbits, nwords;
 446         struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
 447         s64 lblkno, rem, lastlblkno;
 448         u32 mask;
 449         struct dmap *dp;
 450         struct metapage *mp;
 451         struct jfs_log *log;
 452         int lsn, difft, diffp;
 453         unsigned long flags;
 454
 455         /* the blocks better be within the mapsize. */
 456         if (blkno + nblocks > bmp->db_mapsize) {
 457                 printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
 458                        (unsigned long long) blkno,
 459                        (unsigned long long) nblocks);
 460                 jfs_error(ipbmap->i_sb, "blocks are outside the map\n");
 461                 return -EIO;
 462         }
 463
 464         /* compute delta of transaction lsn from log syncpt */
 465         lsn = tblk->lsn;
 466         log = (struct jfs_log *) JFS_SBI(tblk->sb)->log;
 467         logdiff(difft, lsn, log);
 468
 469         /*
 470          * update the block state a dmap at a time.
 471          */
 472         mp = NULL;
 473         lastlblkno = 0;
 474         for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) {
 475                 /* get the buffer for the current dmap. */
 476                 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
 477                 if (lblkno != lastlblkno) {
 478                         if (mp) {
 479                                 write_metapage(mp);
 480                         }
 481
 482                         mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE,
 483                                            0);
 484                         if (mp == NULL)
 485                                 return -EIO;
 486                         metapage_wait_for_io(mp);
 487                 }
 488                 dp = (struct dmap *) mp->data;
 489
 490                 /* determine the bit number and word within the dmap of
 491                  * the starting block.  also determine how many blocks
 492                  * are to be updated within this dmap.
 493                  */
 494                 dbitno = blkno & (BPERDMAP - 1);
 495                 word = dbitno >> L2DBWORD;
 496                 nblks = min(rem, (s64)BPERDMAP - dbitno);
 497
 498                 /* update the bits of the dmap words. the first and last
 499                  * words may only have a subset of their bits updated. if
 500                  * this is the case, we'll work against that word (i.e.
 501                  * partial first and/or last) only in a single pass.  a
 502                  * single pass will also be used to update all words that
 503                  * are to have all their bits updated.
 504                  */
 505                 for (rbits = nblks; rbits > 0;
 506                      rbits -= nbits, dbitno += nbits) {
 507                         /* determine the bit number within the word and
 508                          * the number of bits within the word.
 509                          */
 510                         wbitno = dbitno & (DBWORD - 1);
 511                         nbits = min(rbits, DBWORD - wbitno);
 512
 513                         /* check if only part of the word is to be updated. */
 514                         if (nbits < DBWORD) {
 515                                 /* update (free or allocate) the bits
 516                                  * in this word.
 517                                  */
 518                                 mask =
 519                                     (ONES << (DBWORD - nbits) >> wbitno);
 520                                 if (free)
 521                                         dp->pmap[word] &=
 522                                             cpu_to_le32(~mask);
 523                                 else
 524                                         dp->pmap[word] |=
 525                                             cpu_to_le32(mask);
 526
 527                                 word += 1;
 528                         } else {
 529                                 /* one or more words are to have all
 530                                  * their bits updated.  determine how
 531                                  * many words and how many bits.
 532                                  */
 533                                 nwords = rbits >> L2DBWORD;
 534                                 nbits = nwords << L2DBWORD;
 535
 536                                 /* update (free or allocate) the bits
 537                                  * in these words.
 538                                  */
 539                                 if (free)
 540                                         memset(&dp->pmap[word], 0,
 541                                                nwords * 4);
 542                                 else
 543                                         memset(&dp->pmap[word], (int) ONES,
 544                                                nwords * 4);
 545
 546                                 word += nwords;
 547                         }
 548                 }
 549
 550                 /*
 551                  * update dmap lsn
 552                  */
 553                 if (lblkno == lastlblkno)
 554                         continue;
 555
 556                 lastlblkno = lblkno;
 557
 558                 LOGSYNC_LOCK(log, flags);
 559                 if (mp->lsn != 0) {
 560                         /* inherit older/smaller lsn */
 561                         logdiff(diffp, mp->lsn, log);
 562                         if (difft < diffp) {
 563                                 mp->lsn = lsn;
 564
 565                                 /* move bp after tblock in logsync list */
 566                                 list_move(&mp->synclist, &tblk->synclist);
 567                         }
 568
 569                         /* inherit younger/larger clsn */
 570                         logdiff(difft, tblk->clsn, log);
 571                         logdiff(diffp, mp->clsn, log);
 572                         if (difft > diffp)
 573                                 mp->clsn = tblk->clsn;
 574                 } else {
 575                         mp->log = log;
 576                         mp->lsn = lsn;
 577
 578                         /* insert bp after tblock in logsync list */
 579                         log->count++;
 580                         list_add(&mp->synclist, &tblk->synclist);
 581
 582                         mp->clsn = tblk->clsn;
 583                 }
 584                 LOGSYNC_UNLOCK(log, flags);
 585         }
 586
 587         /* write the last buffer. */
 588         if (mp) {
 589                 write_metapage(mp);
 590         }
 591
 592         return (0);
 593 }
 594
 595
 596 /*
 597  * NAME:        dbNextAG()
 598  *
 599  * FUNCTION:    find the preferred allocation group for new allocations.
 600  *
 601  *              Within the allocation groups, we maintain a preferred
 602  *              allocation group which consists of a group with at least
 603  *              average free space.  It is the preferred group that we target
 604  *              new inode allocation towards.  The tie-in between inode
 605  *              allocation and block allocation occurs as we allocate the
 606  *              first (data) block of an inode and specify the inode (block)
 607  *              as the allocation hint for this block.
 608  *
 609  *              We try to avoid having more than one open file growing in
 610  *              an allocation group, as this will lead to fragmentation.
 611  *              This differs from the old OS/2 method of trying to keep
 612  *              empty ags around for large allocations.
 613  *
 614  * PARAMETERS:
 615  *      ipbmap  - pointer to in-core inode for the block map.
 616  *
 617  * RETURN VALUES:
 618  *      the preferred allocation group number.
 619  */
 620 int dbNextAG(struct inode *ipbmap)
 621 {
 622         s64 avgfree;
 623         int agpref;
 624         s64 hwm = 0;
 625         int i;
 626         int next_best = -1;
 627         struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
 628
 629         BMAP_LOCK(bmp);
 630
 631         /* determine the average number of free blocks within the ags. */
 632         avgfree = (u32)bmp->db_nfree / bmp->db_numag;
 633
 634         /*
 635          * if the current preferred ag does not have an active allocator
 636          * and has at least average freespace, return it
 637          */
 638         agpref = bmp->db_agpref;
 639         if ((atomic_read(&bmp->db_active[agpref]) == 0) &&
 640             (bmp->db_agfree[agpref] >= avgfree))
 641                 goto unlock;
 642
 643         /* From the last preferred ag, find the next one with at least
 644          * average free space.
 645          */
 646         for (i = 0 ; i < bmp->db_numag; i++, agpref++) {
 647                 if (agpref == bmp->db_numag)
 648                         agpref = 0;
 649
 650                 if (atomic_read(&bmp->db_active[agpref]))
 651                         /* open file is currently growing in this ag */
 652                         continue;
 653                 if (bmp->db_agfree[agpref] >= avgfree) {
 654                         /* Return this one */
 655                         bmp->db_agpref = agpref;
 656                         goto unlock;
 657                 } else if (bmp->db_agfree[agpref] > hwm) {
 658                         /* Less than avg. freespace, but best so far */
 659                         hwm = bmp->db_agfree[agpref];
 660                         next_best = agpref;
 661                 }
 662         }
 663
 664         /*
 665          * If no inactive ag was found with average freespace, use the
 666          * next best
 667          */
 668         if (next_best != -1)
 669                 bmp->db_agpref = next_best;
 670         /* else leave db_agpref unchanged */
 671 unlock:
 672         BMAP_UNLOCK(bmp);
 673
 674         /* return the preferred group.
 675          */
 676         return (bmp->db_agpref);
 677 }
 678
 679 /*
 680  * NAME:        dbAlloc()
 681  *
 682  * FUNCTION:    attempt to allocate a specified number of contiguous free
 683  *              blocks from the working allocation block map.
 684  *
 685  *              the block allocation policy uses hints and a multi-step
 686  *              approach.
 687  *
 688  *              for allocation requests smaller than the number of blocks
 689  *              per dmap, we first try to allocate the new blocks
 690  *              immediately following the hint.  if these blocks are not
 691  *              available, we try to allocate blocks near the hint.  if
 692  *              no blocks near the hint are available, we next try to
 693  *              allocate within the same dmap as contains the hint.
 694  *
 695  *              if no blocks are available in the dmap or the allocation
 696  *              request is larger than the dmap size, we try to allocate
 697  *              within the same allocation group as contains the hint. if
 698  *              this does not succeed, we finally try to allocate anywhere
 699  *              within the aggregate.
 700  *
 701  *              we also try to allocate anywhere within the aggregate
 702  *              for allocation requests larger than the allocation group
 703  *              size or requests that specify no hint value.
 704  *
 705  * PARAMETERS:
 706  *      ip      - pointer to in-core inode;
 707  *      hint    - allocation hint.
 708  *      nblocks - number of contiguous blocks in the range.
 709  *      results - on successful return, set to the starting block number
 710  *                of the newly allocated contiguous range.
 711  *
 712  * RETURN VALUES:
 713  *      0       - success
 714  *      -ENOSPC - insufficient disk resources
 715  *      -EIO    - i/o error
 716  */
 717 int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results)
 718 {
 719         int rc, agno;
 720         struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
 721         struct bmap *bmp;
 722         struct metapage *mp;
 723         s64 lblkno, blkno;
 724         struct dmap *dp;
 725         int l2nb;
 726         s64 mapSize;
 727         int writers;
 728
 729         /* assert that nblocks is valid */
 730         assert(nblocks > 0);
 731
 732         /* get the log2 number of blocks to be allocated.
 733          * if the number of blocks is not a log2 multiple,
 734          * it will be rounded up to the next log2 multiple.
 735          */
 736         l2nb = BLKSTOL2(nblocks);
 737
 738         bmp = JFS_SBI(ip->i_sb)->bmap;
 739
 740         mapSize = bmp->db_mapsize;
 741
 742         /* the hint should be within the map */
 743         if (hint >= mapSize) {
 744                 jfs_error(ip->i_sb, "the hint is outside the map\n");
 745                 return -EIO;
 746         }
 747
 748         /* if the number of blocks to be allocated is greater than the
 749          * allocation group size, try to allocate anywhere.
 750          */
 751         if (l2nb > bmp->db_agl2size) {
 752                 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
 753
 754                 rc = dbAllocAny(bmp, nblocks, l2nb, results);
 755
 756                 goto write_unlock;
 757         }
 758
 759         /*
 760          * If no hint, let dbNextAG recommend an allocation group
 761          */
 762         if (hint == 0)
 763                 goto pref_ag;
 764
 765         /* we would like to allocate close to the hint.  adjust the
 766          * hint to the block following the hint since the allocators
 767          * will start looking for free space starting at this point.
 768          */
 769         blkno = hint + 1;
 770
 771         if (blkno >= bmp->db_mapsize)
 772                 goto pref_ag;
 773
 774         agno = blkno >> bmp->db_agl2size;
 775
 776         /* check if blkno crosses over into a new allocation group.
 777          * if so, check if we should allow allocations within this
 778          * allocation group.
 779          */
 780         if ((blkno & (bmp->db_agsize - 1)) == 0)
 781                 /* check if the AG is currently being written to.
 782                  * if so, call dbNextAG() to find a non-busy
 783                  * AG with sufficient free space.
 784                  */
 785                 if (atomic_read(&bmp->db_active[agno]))
 786                         goto pref_ag;
 787
 788         /* check if the allocation request size can be satisfied from a
 789          * single dmap.  if so, try to allocate from the dmap containing
 790          * the hint using a tiered strategy.
 791          */
 792         if (nblocks <= BPERDMAP) {
 793                 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
 794
 795                 /* get the buffer for the dmap containing the hint.
 796                  */
 797                 rc = -EIO;
 798                 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
 799                 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
 800                 if (mp == NULL)
 801                         goto read_unlock;
 802
 803                 dp = (struct dmap *) mp->data;
 804
 805                 /* first, try to satisfy the allocation request with the
 806                  * blocks beginning at the hint.
 807                  */
 808                 if ((rc = dbAllocNext(bmp, dp, blkno, (int) nblocks))
 809                     != -ENOSPC) {
 810                         if (rc == 0) {
 811                                 *results = blkno;
 812                                 mark_metapage_dirty(mp);
 813                         }
 814
 815                         release_metapage(mp);
 816                         goto read_unlock;
 817                 }
 818
 819                 writers = atomic_read(&bmp->db_active[agno]);
 820                 if ((writers > 1) ||
 821                     ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) {
 822                         /*
 823                          * Someone else is writing in this allocation
 824                          * group.  To avoid fragmenting, try another ag
 825                          */
 826                         release_metapage(mp);
 827                         IREAD_UNLOCK(ipbmap);
 828                         goto pref_ag;
 829                 }
 830
 831                 /* next, try to satisfy the allocation request with blocks
 832                  * near the hint.
 833                  */
 834                 if ((rc =
 835                      dbAllocNear(bmp, dp, blkno, (int) nblocks, l2nb, results))
 836                     != -ENOSPC) {
 837                         if (rc == 0)
 838                                 mark_metapage_dirty(mp);
 839
 840                         release_metapage(mp);
 841                         goto read_unlock;
 842                 }
 843
 844                 /* try to satisfy the allocation request with blocks within
 845                  * the same dmap as the hint.
 846                  */
 847                 if ((rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results))
 848                     != -ENOSPC) {
 849                         if (rc == 0)
 850                                 mark_metapage_dirty(mp);
 851
 852                         release_metapage(mp);
 853                         goto read_unlock;
 854                 }
 855
 856                 release_metapage(mp);
 857                 IREAD_UNLOCK(ipbmap);
 858         }
 859
 860         /* try to satisfy the allocation request with blocks within
 861          * the same allocation group as the hint.
 862          */
 863         IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
 864         if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC)
 865                 goto write_unlock;
 866
 867         IWRITE_UNLOCK(ipbmap);
 868
 869
 870       pref_ag:
 871         /*
 872          * Let dbNextAG recommend a preferred allocation group
 873          */
 874         agno = dbNextAG(ipbmap);
 875         IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
 876
 877         /* Try to allocate within this allocation group.  if that fails, try to
 878          * allocate anywhere in the map.
 879          */
 880         if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC)
 881                 rc = dbAllocAny(bmp, nblocks, l2nb, results);
 882
 883       write_unlock:
 884         IWRITE_UNLOCK(ipbmap);
 885
 886         return (rc);
 887
 888       read_unlock:
 889         IREAD_UNLOCK(ipbmap);
 890
 891         return (rc);
 892 }
 893
 894 /*
 895  * NAME:        dbReAlloc()
 896  *
 897  * FUNCTION:    attempt to extend a current allocation by a specified
 898  *              number of blocks.
 899  *
 900  *              this routine attempts to satisfy the allocation request
 901  *              by first trying to extend the existing allocation in
 902  *              place by allocating the additional blocks as the blocks
 903  *              immediately following the current allocation.  if these
 904  *              blocks are not available, this routine will attempt to
 905  *              allocate a new set of contiguous blocks large enough
 906  *              to cover the existing allocation plus the additional
 907  *              number of blocks required.
 908  *
 909  * PARAMETERS:
 910  *      ip          -  pointer to in-core inode requiring allocation.
 911  *      blkno       -  starting block of the current allocation.
 912  *      nblocks     -  number of contiguous blocks within the current
 913  *                     allocation.
 914  *      addnblocks  -  number of blocks to add to the allocation.
 915  *      results -      on successful return, set to the starting block number
 916  *                     of the existing allocation if the existing allocation
 917  *                     was extended in place or to a newly allocated contiguous
 918  *                     range if the existing allocation could not be extended
 919  *                     in place.
 920  *
 921  * RETURN VALUES:
 922  *      0       - success
 923  *      -ENOSPC - insufficient disk resources
 924  *      -EIO    - i/o error
 925  */
 926 int
 927 dbReAlloc(struct inode *ip,
 928           s64 blkno, s64 nblocks, s64 addnblocks, s64 * results)
 929 {
 930         int rc;
 931
 932         /* try to extend the allocation in place.
 933          */
 934         if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) {
 935                 *results = blkno;
 936                 return (0);
 937         } else {
 938                 if (rc != -ENOSPC)
 939                         return (rc);
 940         }
 941
 942         /* could not extend the allocation in place, so allocate a
 943          * new set of blocks for the entire request (i.e. try to get
 944          * a range of contiguous blocks large enough to cover the
 945          * existing allocation plus the additional blocks.)
 946          */
 947         return (dbAlloc
 948                 (ip, blkno + nblocks - 1, addnblocks + nblocks, results));
 949 }
 950
 951
 952 /*
 953  * NAME:        dbExtend()
 954  *
 955  * FUNCTION:    attempt to extend a current allocation by a specified
 956  *              number of blocks.
 957  *
 958  *              this routine attempts to satisfy the allocation request
 959  *              by first trying to extend the existing allocation in
 960  *              place by allocating the additional blocks as the blocks
 961  *              immediately following the current allocation.
 962  *
 963  * PARAMETERS:
 964  *      ip          -  pointer to in-core inode requiring allocation.
 965  *      blkno       -  starting block of the current allocation.
 966  *      nblocks     -  number of contiguous blocks within the current
 967  *                     allocation.
 968  *      addnblocks  -  number of blocks to add to the allocation.
 969  *
 970  * RETURN VALUES:
 971  *      0       - success
 972  *      -ENOSPC - insufficient disk resources
 973  *      -EIO    - i/o error
 974  */
 975 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks)
 976 {
 977         struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
 978         s64 lblkno, lastblkno, extblkno;
 979         uint rel_block;
 980         struct metapage *mp;
 981         struct dmap *dp;
 982         int rc;
 983         struct inode *ipbmap = sbi->ipbmap;
 984         struct bmap *bmp;
 985
 986         /*
 987          * We don't want a non-aligned extent to cross a page boundary
 988          */
 989         if (((rel_block = blkno & (sbi->nbperpage - 1))) &&
 990             (rel_block + nblocks + addnblocks > sbi->nbperpage))
 991                 return -ENOSPC;
 992
 993         /* get the last block of the current allocation */
 994         lastblkno = blkno + nblocks - 1;
 995
 996         /* determine the block number of the block following
 997          * the existing allocation.
 998          */
 999         extblkno = lastblkno + 1;
1000
1001         IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
1002
1003         /* better be within the file system */
1004         bmp = sbi->bmap;
1005         if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) {
1006                 IREAD_UNLOCK(ipbmap);
1007                 jfs_error(ip->i_sb, "the block is outside the filesystem\n");
1008                 return -EIO;
1009         }
1010
1011         /* we'll attempt to extend the current allocation in place by
1012          * allocating the additional blocks as the blocks immediately
1013          * following the current allocation.  we only try to extend the
1014          * current allocation in place if the number of additional blocks
1015          * can fit into a dmap, the last block of the current allocation
1016          * is not the last block of the file system, and the start of the
1017          * inplace extension is not on an allocation group boundary.
1018          */
1019         if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize ||
1020             (extblkno & (bmp->db_agsize - 1)) == 0) {
1021                 IREAD_UNLOCK(ipbmap);
1022                 return -ENOSPC;
1023         }
1024
1025         /* get the buffer for the dmap containing the first block
1026          * of the extension.
1027          */
1028         lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage);
1029         mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
1030         if (mp == NULL) {
1031                 IREAD_UNLOCK(ipbmap);
1032                 return -EIO;
1033         }
1034
1035         dp = (struct dmap *) mp->data;
1036
1037         /* try to allocate the blocks immediately following the
1038          * current allocation.
1039          */
1040         rc = dbAllocNext(bmp, dp, extblkno, (int) addnblocks);
1041
1042         IREAD_UNLOCK(ipbmap);
1043
1044         /* were we successful ? */
1045         if (rc == 0)
1046                 write_metapage(mp);
1047         else
1048                 /* we were not successful */
1049                 release_metapage(mp);
1050
1051         return (rc);
1052 }
1053
1054
1055 /*
1056  * NAME:        dbAllocNext()
1057  *
1058  * FUNCTION:    attempt to allocate the blocks of the specified block
1059  *              range within a dmap.
1060  *
1061  * PARAMETERS:
1062  *      bmp     -  pointer to bmap descriptor
1063  *      dp      -  pointer to dmap.
1064  *      blkno   -  starting block number of the range.
1065  *      nblocks -  number of contiguous free blocks of the range.
1066  *
1067  * RETURN VALUES:
1068  *      0       - success
1069  *      -ENOSPC - insufficient disk resources
1070  *      -EIO    - i/o error
1071  *
1072  * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1073  */
1074 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
1075                        int nblocks)
1076 {
1077         int dbitno, word, rembits, nb, nwords, wbitno, nw;
1078         int l2size;
1079         s8 *leaf;
1080         u32 mask;
1081
1082         if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1083                 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1084                 return -EIO;
1085         }
1086
1087         /* pick up a pointer to the leaves of the dmap tree.
1088          */
1089         leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1090
1091         /* determine the bit number and word within the dmap of the
1092          * starting block.
1093          */
1094         dbitno = blkno & (BPERDMAP - 1);
1095         word = dbitno >> L2DBWORD;
1096
1097         /* check if the specified block range is contained within
1098          * this dmap.
1099          */
1100         if (dbitno + nblocks > BPERDMAP)
1101                 return -ENOSPC;
1102
1103         /* check if the starting leaf indicates that anything
1104          * is free.
1105          */
1106         if (leaf[word] == NOFREE)
1107                 return -ENOSPC;
1108
1109         /* check the dmaps words corresponding to block range to see
1110          * if the block range is free.  not all bits of the first and
1111          * last words may be contained within the block range.  if this
1112          * is the case, we'll work against those words (i.e. partial first
1113          * and/or last) on an individual basis (a single pass) and examine
1114          * the actual bits to determine if they are free.  a single pass
1115          * will be used for all dmap words fully contained within the
1116          * specified range.  within this pass, the leaves of the dmap
1117          * tree will be examined to determine if the blocks are free. a
1118          * single leaf may describe the free space of multiple dmap
1119          * words, so we may visit only a subset of the actual leaves
1120          * corresponding to the dmap words of the block range.
1121          */
1122         for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
1123                 /* determine the bit number within the word and
1124                  * the number of bits within the word.
1125                  */
1126                 wbitno = dbitno & (DBWORD - 1);
1127                 nb = min(rembits, DBWORD - wbitno);
1128
1129                 /* check if only part of the word is to be examined.
1130                  */
1131                 if (nb < DBWORD) {
1132                         /* check if the bits are free.
1133                          */
1134                         mask = (ONES << (DBWORD - nb) >> wbitno);
1135                         if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask)
1136                                 return -ENOSPC;
1137
1138                         word += 1;
1139                 } else {
1140                         /* one or more dmap words are fully contained
1141                          * within the block range.  determine how many
1142                          * words and how many bits.
1143                          */
1144                         nwords = rembits >> L2DBWORD;
1145                         nb = nwords << L2DBWORD;
1146
1147                         /* now examine the appropriate leaves to determine
1148                          * if the blocks are free.
1149                          */
1150                         while (nwords > 0) {
1151                                 /* does the leaf describe any free space ?
1152                                  */
1153                                 if (leaf[word] < BUDMIN)
1154                                         return -ENOSPC;
1155
1156                                 /* determine the l2 number of bits provided
1157                                  * by this leaf.
1158                                  */
1159                                 l2size =
1160                                     min_t(int, leaf[word], NLSTOL2BSZ(nwords));
1161
1162                                 /* determine how many words were handled.
1163                                  */
1164                                 nw = BUDSIZE(l2size, BUDMIN);
1165
1166                                 nwords -= nw;
1167                                 word += nw;
1168                         }
1169                 }
1170         }
1171
1172         /* allocate the blocks.
1173          */
1174         return (dbAllocDmap(bmp, dp, blkno, nblocks));
1175 }
1176
1177
1178 /*
1179  * NAME:        dbAllocNear()
1180  *
1181  * FUNCTION:    attempt to allocate a number of contiguous free blocks near
1182  *              a specified block (hint) within a dmap.
1183  *
1184  *              starting with the dmap leaf that covers the hint, we'll
1185  *              check the next four contiguous leaves for sufficient free
1186  *              space.  if sufficient free space is found, we'll allocate
1187  *              the desired free space.
1188  *
1189  * PARAMETERS:
1190  *      bmp     -  pointer to bmap descriptor
1191  *      dp      -  pointer to dmap.
1192  *      blkno   -  block number to allocate near.
1193  *      nblocks -  actual number of contiguous free blocks desired.
1194  *      l2nb    -  log2 number of contiguous free blocks desired.
1195  *      results -  on successful return, set to the starting block number
1196  *                 of the newly allocated range.
1197  *
1198  * RETURN VALUES:
1199  *      0       - success
1200  *      -ENOSPC - insufficient disk resources
1201  *      -EIO    - i/o error
1202  *
1203  * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1204  */
1205 static int
1206 dbAllocNear(struct bmap * bmp,
1207             struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results)
1208 {
1209         int word, lword, rc;
1210         s8 *leaf;
1211
1212         if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1213                 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1214                 return -EIO;
1215         }
1216
1217         leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1218
1219         /* determine the word within the dmap that holds the hint
1220          * (i.e. blkno).  also, determine the last word in the dmap
1221          * that we'll include in our examination.
1222          */
1223         word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
1224         lword = min(word + 4, LPERDMAP);
1225
1226         /* examine the leaves for sufficient free space.
1227          */
1228         for (; word < lword; word++) {
1229                 /* does the leaf describe sufficient free space ?
1230                  */
1231                 if (leaf[word] < l2nb)
1232                         continue;
1233
1234                 /* determine the block number within the file system
1235                  * of the first block described by this dmap word.
1236                  */
1237                 blkno = le64_to_cpu(dp->start) + (word << L2DBWORD);
1238
1239                 /* if not all bits of the dmap word are free, get the
1240                  * starting bit number within the dmap word of the required
1241                  * string of free bits and adjust the block number with the
1242                  * value.
1243                  */
1244                 if (leaf[word] < BUDMIN)
1245                         blkno +=
1246                             dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb);
1247
1248                 /* allocate the blocks.
1249                  */
1250                 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1251                         *results = blkno;
1252
1253                 return (rc);
1254         }
1255
1256         return -ENOSPC;
1257 }
1258
1259
1260 /*
1261  * NAME:        dbAllocAG()
1262  *
1263  * FUNCTION:    attempt to allocate the specified number of contiguous
1264  *              free blocks within the specified allocation group.
1265  *
1266  *              unless the allocation group size is equal to the number
1267  *              of blocks per dmap, the dmap control pages will be used to
1268  *              find the required free space, if available.  we start the
1269  *              search at the highest dmap control page level which
1270  *              distinctly describes the allocation group's free space
1271  *              (i.e. the highest level at which the allocation group's
1272  *              free space is not mixed in with that of any other group).
1273  *              in addition, we start the search within this level at a
1274  *              height of the dmapctl dmtree at which the nodes distinctly
1275  *              describe the allocation group's free space.  at this height,
1276  *              the allocation group's free space may be represented by 1
1277  *              or two sub-trees, depending on the allocation group size.
1278  *              we search the top nodes of these subtrees left to right for
1279  *              sufficient free space.  if sufficient free space is found,
1280  *              the subtree is searched to find the leftmost leaf that
1281  *              has free space.  once we have made it to the leaf, we
1282  *              move the search to the next lower level dmap control page
1283  *              corresponding to this leaf.  we continue down the dmap control
1284  *              pages until we find the dmap that contains or starts the
1285  *              sufficient free space and we allocate at this dmap.
1286  *
1287  *              if the allocation group size is equal to the dmap size,
1288  *              we'll start at the dmap corresponding to the allocation
1289  *              group and attempt the allocation at this level.
1290  *
1291  *              the dmap control page search is also not performed if the
1292  *              allocation group is completely free and we go to the first
1293  *              dmap of the allocation group to do the allocation.  this is
1294  *              done because the allocation group may be part (not the first
1295  *              part) of a larger binary buddy system, causing the dmap
1296  *              control pages to indicate no free space (NOFREE) within
1297  *              the allocation group.
1298  *
1299  * PARAMETERS:
1300  *      bmp     -  pointer to bmap descriptor
1301  *      agno    - allocation group number.
1302  *      nblocks -  actual number of contiguous free blocks desired.
1303  *      l2nb    -  log2 number of contiguous free blocks desired.
1304  *      results -  on successful return, set to the starting block number
1305  *                 of the newly allocated range.
1306  *
1307  * RETURN VALUES:
1308  *      0       - success
1309  *      -ENOSPC - insufficient disk resources
1310  *      -EIO    - i/o error
1311  *
1312  * note: IWRITE_LOCK(ipmap) held on entry/exit;
1313  */
1314 static int
1315 dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results)
1316 {
1317         struct metapage *mp;
1318         struct dmapctl *dcp;
1319         int rc, ti, i, k, m, n, agperlev;
1320         s64 blkno, lblkno;
1321         int budmin;
1322
1323         /* allocation request should not be for more than the
1324          * allocation group size.
1325          */
1326         if (l2nb > bmp->db_agl2size) {
1327                 jfs_error(bmp->db_ipbmap->i_sb,
1328                           "allocation request is larger than the allocation group size\n");
1329                 return -EIO;
1330         }
1331
1332         /* determine the starting block number of the allocation
1333          * group.
1334          */
1335         blkno = (s64) agno << bmp->db_agl2size;
1336
1337         /* check if the allocation group size is the minimum allocation
1338          * group size or if the allocation group is completely free. if
1339          * the allocation group size is the minimum size of BPERDMAP (i.e.
1340          * 1 dmap), there is no need to search the dmap control page (below)
1341          * that fully describes the allocation group since the allocation
1342          * group is already fully described by a dmap.  in this case, we
1343          * just call dbAllocCtl() to search the dmap tree and allocate the
1344          * required space if available.
1345          *
1346          * if the allocation group is completely free, dbAllocCtl() is
1347          * also called to allocate the required space.  this is done for
1348          * two reasons.  first, it makes no sense searching the dmap control
1349          * pages for free space when we know that free space exists.  second,
1350          * the dmap control pages may indicate that the allocation group
1351          * has no free space if the allocation group is part (not the first
1352          * part) of a larger binary buddy system.
1353          */
1354         if (bmp->db_agsize == BPERDMAP
1355             || bmp->db_agfree[agno] == bmp->db_agsize) {
1356                 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1357                 if ((rc == -ENOSPC) &&
1358                     (bmp->db_agfree[agno] == bmp->db_agsize)) {
1359                         printk(KERN_ERR "blkno = %Lx, blocks = %Lx\n",
1360                                (unsigned long long) blkno,
1361                                (unsigned long long) nblocks);
1362                         jfs_error(bmp->db_ipbmap->i_sb,
1363                                   "dbAllocCtl failed in free AG\n");
1364                 }
1365                 return (rc);
1366         }
1367
1368         /* the buffer for the dmap control page that fully describes the
1369          * allocation group.
1370          */
1371         lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel);
1372         mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1373         if (mp == NULL)
1374                 return -EIO;
1375         dcp = (struct dmapctl *) mp->data;
1376         budmin = dcp->budmin;
1377
1378         if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1379                 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n");
1380                 release_metapage(mp);
1381                 return -EIO;
1382         }
1383
1384         /* search the subtree(s) of the dmap control page that describes
1385          * the allocation group, looking for sufficient free space.  to begin,
1386          * determine how many allocation groups are represented in a dmap
1387          * control page at the control page level (i.e. L0, L1, L2) that
1388          * fully describes an allocation group. next, determine the starting
1389          * tree index of this allocation group within the control page.
1390          */
1391         agperlev =
1392             (1 << (L2LPERCTL - (bmp->db_agheight << 1))) / bmp->db_agwidth;
1393         ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1));
1394
1395         /* dmap control page trees fan-out by 4 and a single allocation
1396          * group may be described by 1 or 2 subtrees within the ag level
1397          * dmap control page, depending upon the ag size. examine the ag's
1398          * subtrees for sufficient free space, starting with the leftmost
1399          * subtree.
1400          */
1401         for (i = 0; i < bmp->db_agwidth; i++, ti++) {
1402                 /* is there sufficient free space ?
1403                  */
1404                 if (l2nb > dcp->stree[ti])
1405                         continue;
1406
1407                 /* sufficient free space found in a subtree. now search down
1408                  * the subtree to find the leftmost leaf that describes this
1409                  * free space.
1410                  */
1411                 for (k = bmp->db_agheight; k > 0; k--) {
1412                         for (n = 0, m = (ti << 2) + 1; n < 4; n++) {
1413                                 if (l2nb <= dcp->stree[m + n]) {
1414                                         ti = m + n;
1415                                         break;
1416                                 }
1417                         }
1418                         if (n == 4) {
1419                                 jfs_error(bmp->db_ipbmap->i_sb,
1420                                           "failed descending stree\n");
1421                                 release_metapage(mp);
1422                                 return -EIO;
1423                         }
1424                 }
1425
1426                 /* determine the block number within the file system
1427                  * that corresponds to this leaf.
1428                  */
1429                 if (bmp->db_aglevel == 2)
1430                         blkno = 0;
1431                 else if (bmp->db_aglevel == 1)
1432                         blkno &= ~(MAXL1SIZE - 1);
1433                 else            /* bmp->db_aglevel == 0 */
1434                         blkno &= ~(MAXL0SIZE - 1);
1435
1436                 blkno +=
1437                     ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin;
1438
1439                 /* release the buffer in preparation for going down
1440                  * the next level of dmap control pages.
1441                  */
1442                 release_metapage(mp);
1443
1444                 /* check if we need to continue to search down the lower
1445                  * level dmap control pages.  we need to if the number of
1446                  * blocks required is less than maximum number of blocks
1447                  * described at the next lower level.
1448                  */
1449                 if (l2nb < budmin) {
1450
1451                         /* search the lower level dmap control pages to get
1452                          * the starting block number of the dmap that
1453                          * contains or starts off the free space.
1454                          */
1455                         if ((rc =
1456                              dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1,
1457                                        &blkno))) {
1458                                 if (rc == -ENOSPC) {
1459                                         jfs_error(bmp->db_ipbmap->i_sb,
1460                                                   "control page inconsistent\n");
1461                                         return -EIO;
1462                                 }
1463                                 return (rc);
1464                         }
1465                 }
1466
1467                 /* allocate the blocks.
1468                  */
1469                 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1470                 if (rc == -ENOSPC) {
1471                         jfs_error(bmp->db_ipbmap->i_sb,
1472                                   "unable to allocate blocks\n");
1473                         rc = -EIO;
1474                 }
1475                 return (rc);
1476         }
1477
1478         /* no space in the allocation group.  release the buffer and
1479          * return -ENOSPC.
1480          */
1481         release_metapage(mp);
1482
1483         return -ENOSPC;
1484 }
1485
1486
1487 /*
1488  * NAME:        dbAllocAny()
1489  *
1490  * FUNCTION:    attempt to allocate the specified number of contiguous
1491  *              free blocks anywhere in the file system.
1492  *
1493  *              dbAllocAny() attempts to find the sufficient free space by
1494  *              searching down the dmap control pages, starting with the
1495  *              highest level (i.e. L0, L1, L2) control page.  if free space
1496  *              large enough to satisfy the desired free space is found, the
1497  *              desired free space is allocated.
1498  *
1499  * PARAMETERS:
1500  *      bmp     -  pointer to bmap descriptor
1501  *      nblocks  -  actual number of contiguous free blocks desired.
1502  *      l2nb     -  log2 number of contiguous free blocks desired.
1503  *      results -  on successful return, set to the starting block number
1504  *                 of the newly allocated range.
1505  *
1506  * RETURN VALUES:
1507  *      0       - success
1508  *      -ENOSPC - insufficient disk resources
1509  *      -EIO    - i/o error
1510  *
1511  * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1512  */
1513 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results)
1514 {
1515         int rc;
1516         s64 blkno = 0;
1517
1518         /* starting with the top level dmap control page, search
1519          * down the dmap control levels for sufficient free space.
1520          * if free space is found, dbFindCtl() returns the starting
1521          * block number of the dmap that contains or starts off the
1522          * range of free space.
1523          */
1524         if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno)))
1525                 return (rc);
1526
1527         /* allocate the blocks.
1528          */
1529         rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1530         if (rc == -ENOSPC) {
1531                 jfs_error(bmp->db_ipbmap->i_sb, "unable to allocate blocks\n");
1532                 return -EIO;
1533         }
1534         return (rc);
1535 }
1536
1537
1538 /*
1539  * NAME:        dbDiscardAG()
1540  *
1541  * FUNCTION:    attempt to discard (TRIM) all free blocks of specific AG
1542  *
1543  *              algorithm:
1544  *              1) allocate blocks, as large as possible and save them
1545  *                 while holding IWRITE_LOCK on ipbmap
1546  *              2) trim all these saved block/length values
1547  *              3) mark the blocks free again
1548  *
1549  *              benefit:
1550  *              - we work only on one ag at some time, minimizing how long we
1551  *                need to lock ipbmap
1552  *              - reading / writing the fs is possible most time, even on
1553  *                trimming
1554  *
1555  *              downside:
1556  *              - we write two times to the dmapctl and dmap pages
1557  *              - but for me, this seems the best way, better ideas?
1558  *              /TR 2012
1559  *
1560  * PARAMETERS:
1561  *      ip      - pointer to in-core inode
1562  *      agno    - ag to trim
1563  *      minlen  - minimum value of contiguous blocks
1564  *
1565  * RETURN VALUES:
1566  *      s64     - actual number of blocks trimmed
1567  */
1568 s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen)
1569 {
1570         struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
1571         struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
1572         s64 nblocks, blkno;
1573         u64 trimmed = 0;
1574         int rc, l2nb;
1575         struct super_block *sb = ipbmap->i_sb;
1576
1577         struct range2trim {
1578                 u64 blkno;
1579                 u64 nblocks;
1580         } *totrim, *tt;
1581
1582         /* max blkno / nblocks pairs to trim */
1583         int count = 0, range_cnt;
1584         u64 max_ranges;
1585
1586         /* prevent others from writing new stuff here, while trimming */
1587         IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
1588
1589         nblocks = bmp->db_agfree[agno];
1590         max_ranges = nblocks;
1591         do_div(max_ranges, minlen);
1592         range_cnt = min_t(u64, max_ranges + 1, 32 * 1024);
1593         totrim = kmalloc_array(range_cnt, sizeof(struct range2trim), GFP_NOFS);
1594         if (totrim == NULL) {
1595                 jfs_error(bmp->db_ipbmap->i_sb, "no memory for trim array\n");
1596                 IWRITE_UNLOCK(ipbmap);
1597                 return 0;
1598         }
1599
1600         tt = totrim;
1601         while (nblocks >= minlen) {
1602                 l2nb = BLKSTOL2(nblocks);
1603
1604                 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */
1605                 rc = dbAllocAG(bmp, agno, nblocks, l2nb, &blkno);
1606                 if (rc == 0) {
1607                         tt->blkno = blkno;
1608                         tt->nblocks = nblocks;
1609                         tt++; count++;
1610
1611                         /* the whole ag is free, trim now */
1612                         if (bmp->db_agfree[agno] == 0)
1613                                 break;
1614
1615                         /* give a hint for the next while */
1616                         nblocks = bmp->db_agfree[agno];
1617                         continue;
1618                 } else if (rc == -ENOSPC) {
1619                         /* search for next smaller log2 block */
1620                         l2nb = BLKSTOL2(nblocks) - 1;
1621                         nblocks = 1LL << l2nb;
1622                 } else {
1623                         /* Trim any already allocated blocks */
1624                         jfs_error(bmp->db_ipbmap->i_sb, "-EIO\n");
1625                         break;
1626                 }
1627
1628                 /* check, if our trim array is full */
1629                 if (unlikely(count >= range_cnt - 1))
1630                         break;
1631         }
1632         IWRITE_UNLOCK(ipbmap);
1633
1634         tt->nblocks = 0; /* mark the current end */
1635         for (tt = totrim; tt->nblocks != 0; tt++) {
1636                 /* when mounted with online discard, dbFree() will
1637                  * call jfs_issue_discard() itself */
1638                 if (!(JFS_SBI(sb)->flag & JFS_DISCARD))
1639                         jfs_issue_discard(ip, tt->blkno, tt->nblocks);
1640                 dbFree(ip, tt->blkno, tt->nblocks);
1641                 trimmed += tt->nblocks;
1642         }
1643         kfree(totrim);
1644
1645         return trimmed;
1646 }
1647
1648 /*
1649  * NAME:        dbFindCtl()
1650  *
1651  * FUNCTION:    starting at a specified dmap control page level and block
1652  *              number, search down the dmap control levels for a range of
1653  *              contiguous free blocks large enough to satisfy an allocation
1654  *              request for the specified number of free blocks.
1655  *
1656  *              if sufficient contiguous free blocks are found, this routine
1657  *              returns the starting block number within a dmap page that
1658  *              contains or starts a range of contiqious free blocks that
1659  *              is sufficient in size.
1660  *
1661  * PARAMETERS:
1662  *      bmp     -  pointer to bmap descriptor
1663  *      level   -  starting dmap control page level.
1664  *      l2nb    -  log2 number of contiguous free blocks desired.
1665  *      *blkno  -  on entry, starting block number for conducting the search.
1666  *                 on successful return, the first block within a dmap page
1667  *                 that contains or starts a range of contiguous free blocks.
1668  *
1669  * RETURN VALUES:
1670  *      0       - success
1671  *      -ENOSPC - insufficient disk resources
1672  *      -EIO    - i/o error
1673  *
1674  * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1675  */
1676 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno)
1677 {
1678         int rc, leafidx, lev;
1679         s64 b, lblkno;
1680         struct dmapctl *dcp;
1681         int budmin;
1682         struct metapage *mp;
1683
1684         /* starting at the specified dmap control page level and block
1685          * number, search down the dmap control levels for the starting
1686          * block number of a dmap page that contains or starts off
1687          * sufficient free blocks.
1688          */
1689         for (lev = level, b = *blkno; lev >= 0; lev--) {
1690                 /* get the buffer of the dmap control page for the block
1691                  * number and level (i.e. L0, L1, L2).
1692                  */
1693                 lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev);
1694                 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1695                 if (mp == NULL)
1696                         return -EIO;
1697                 dcp = (struct dmapctl *) mp->data;
1698                 budmin = dcp->budmin;
1699
1700                 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1701                         jfs_error(bmp->db_ipbmap->i_sb,
1702                                   "Corrupt dmapctl page\n");
1703                         release_metapage(mp);
1704                         return -EIO;
1705                 }
1706
1707                 /* search the tree within the dmap control page for
1708                  * sufficient free space.  if sufficient free space is found,
1709                  * dbFindLeaf() returns the index of the leaf at which
1710                  * free space was found.
1711                  */
1712                 rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx);
1713
1714                 /* release the buffer.
1715                  */
1716                 release_metapage(mp);
1717
1718                 /* space found ?
1719                  */
1720                 if (rc) {
1721                         if (lev != level) {
1722                                 jfs_error(bmp->db_ipbmap->i_sb,
1723                                           "dmap inconsistent\n");
1724                                 return -EIO;
1725                         }
1726                         return -ENOSPC;
1727                 }
1728
1729                 /* adjust the block number to reflect the location within
1730                  * the dmap control page (i.e. the leaf) at which free
1731                  * space was found.
1732                  */
1733                 b += (((s64) leafidx) << budmin);
1734
1735                 /* we stop the search at this dmap control page level if
1736                  * the number of blocks required is greater than or equal
1737                  * to the maximum number of blocks described at the next
1738                  * (lower) level.
1739                  */
1740                 if (l2nb >= budmin)
1741                         break;
1742         }
1743
1744         *blkno = b;
1745         return (0);
1746 }
1747
1748
1749 /*
1750  * NAME:        dbAllocCtl()
1751  *
1752  * FUNCTION:    attempt to allocate a specified number of contiguous
1753  *              blocks starting within a specific dmap.
1754  *
1755  *              this routine is called by higher level routines that search
1756  *              the dmap control pages above the actual dmaps for contiguous
1757  *              free space.  the result of successful searches by these
1758  *              routines are the starting block numbers within dmaps, with
1759  *              the dmaps themselves containing the desired contiguous free
1760  *              space or starting a contiguous free space of desired size
1761  *              that is made up of the blocks of one or more dmaps. these
1762  *              calls should not fail due to insufficent resources.
1763  *
1764  *              this routine is called in some cases where it is not known
1765  *              whether it will fail due to insufficient resources.  more
1766  *              specifically, this occurs when allocating from an allocation
1767  *              group whose size is equal to the number of blocks per dmap.
1768  *              in this case, the dmap control pages are not examined prior
1769  *              to calling this routine (to save pathlength) and the call
1770  *              might fail.
1771  *
1772  *              for a request size that fits within a dmap, this routine relies
1773  *              upon the dmap's dmtree to find the requested contiguous free
1774  *              space.  for request sizes that are larger than a dmap, the
1775  *              requested free space will start at the first block of the
1776  *              first dmap (i.e. blkno).
1777  *
1778  * PARAMETERS:
1779  *      bmp     -  pointer to bmap descriptor
1780  *      nblocks  -  actual number of contiguous free blocks to allocate.
1781  *      l2nb     -  log2 number of contiguous free blocks to allocate.
1782  *      blkno    -  starting block number of the dmap to start the allocation
1783  *                  from.
1784  *      results -  on successful return, set to the starting block number
1785  *                 of the newly allocated range.
1786  *
1787  * RETURN VALUES:
1788  *      0       - success
1789  *      -ENOSPC - insufficient disk resources
1790  *      -EIO    - i/o error
1791  *
1792  * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1793  */
1794 static int
1795 dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results)
1796 {
1797         int rc, nb;
1798         s64 b, lblkno, n;
1799         struct metapage *mp;
1800         struct dmap *dp;
1801
1802         /* check if the allocation request is confined to a single dmap.
1803          */
1804         if (l2nb <= L2BPERDMAP) {
1805                 /* get the buffer for the dmap.
1806                  */
1807                 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
1808                 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1809                 if (mp == NULL)
1810                         return -EIO;
1811                 dp = (struct dmap *) mp->data;
1812
1813                 /* try to allocate the blocks.
1814                  */
1815                 rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results);
1816                 if (rc == 0)
1817                         mark_metapage_dirty(mp);
1818
1819                 release_metapage(mp);
1820
1821                 return (rc);
1822         }
1823
1824         /* allocation request involving multiple dmaps. it must start on
1825          * a dmap boundary.
1826          */
1827         assert((blkno & (BPERDMAP - 1)) == 0);
1828
1829         /* allocate the blocks dmap by dmap.
1830          */
1831         for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) {
1832                 /* get the buffer for the dmap.
1833                  */
1834                 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
1835                 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1836                 if (mp == NULL) {
1837                         rc = -EIO;
1838                         goto backout;
1839                 }
1840                 dp = (struct dmap *) mp->data;
1841
1842                 /* the dmap better be all free.
1843                  */
1844                 if (dp->tree.stree[ROOT] != L2BPERDMAP) {
1845                         release_metapage(mp);
1846                         jfs_error(bmp->db_ipbmap->i_sb,
1847                                   "the dmap is not all free\n");
1848                         rc = -EIO;
1849                         goto backout;
1850                 }
1851
1852                 /* determine how many blocks to allocate from this dmap.
1853                  */
1854                 nb = min_t(s64, n, BPERDMAP);
1855
1856                 /* allocate the blocks from the dmap.
1857                  */
1858                 if ((rc = dbAllocDmap(bmp, dp, b, nb))) {
1859                         release_metapage(mp);
1860                         goto backout;
1861                 }
1862
1863                 /* write the buffer.
1864                  */
1865                 write_metapage(mp);
1866         }
1867
1868         /* set the results (starting block number) and return.
1869          */
1870         *results = blkno;
1871         return (0);
1872
1873         /* something failed in handling an allocation request involving
1874          * multiple dmaps.  we'll try to clean up by backing out any
1875          * allocation that has already happened for this request.  if
1876          * we fail in backing out the allocation, we'll mark the file
1877          * system to indicate that blocks have been leaked.
1878          */
1879       backout:
1880
1881         /* try to backout the allocations dmap by dmap.
1882          */
1883         for (n = nblocks - n, b = blkno; n > 0;
1884              n -= BPERDMAP, b += BPERDMAP) {
1885                 /* get the buffer for this dmap.
1886                  */
1887                 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
1888                 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1889                 if (mp == NULL) {
1890                         /* could not back out.  mark the file system
1891                          * to indicate that we have leaked blocks.
1892                          */
1893                         jfs_error(bmp->db_ipbmap->i_sb,
1894                                   "I/O Error: Block Leakage\n");
1895                         continue;
1896                 }
1897                 dp = (struct dmap *) mp->data;
1898
1899                 /* free the blocks is this dmap.
1900                  */
1901                 if (dbFreeDmap(bmp, dp, b, BPERDMAP)) {
1902                         /* could not back out.  mark the file system
1903                          * to indicate that we have leaked blocks.
1904                          */
1905                         release_metapage(mp);
1906                         jfs_error(bmp->db_ipbmap->i_sb, "Block Leakage\n");
1907                         continue;
1908                 }
1909
1910                 /* write the buffer.
1911                  */
1912                 write_metapage(mp);
1913         }
1914
1915         return (rc);
1916 }
1917
1918
1919 /*
1920  * NAME:        dbAllocDmapLev()
1921  *
1922  * FUNCTION:    attempt to allocate a specified number of contiguous blocks
1923  *              from a specified dmap.
1924  *
1925  *              this routine checks if the contiguous blocks are available.
1926  *              if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1927  *              returned.
1928  *
1929  * PARAMETERS:
1930  *      mp      -  pointer to bmap descriptor
1931  *      dp      -  pointer to dmap to attempt to allocate blocks from.
1932  *      l2nb    -  log2 number of contiguous block desired.
1933  *      nblocks -  actual number of contiguous block desired.
1934  *      results -  on successful return, set to the starting block number
1935  *                 of the newly allocated range.
1936  *
1937  * RETURN VALUES:
1938  *      0       - success
1939  *      -ENOSPC - insufficient disk resources
1940  *      -EIO    - i/o error
1941  *
1942  * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1943  *      IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1944  */
1945 static int
1946 dbAllocDmapLev(struct bmap * bmp,
1947                struct dmap * dp, int nblocks, int l2nb, s64 * results)
1948 {
1949         s64 blkno;
1950         int leafidx, rc;
1951
1952         /* can't be more than a dmaps worth of blocks */
1953         assert(l2nb <= L2BPERDMAP);
1954
1955         /* search the tree within the dmap page for sufficient
1956          * free space.  if sufficient free space is found, dbFindLeaf()
1957          * returns the index of the leaf at which free space was found.
1958          */
1959         if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx))
1960                 return -ENOSPC;
1961
1962         if (leafidx < 0)
1963                 return -EIO;
1964
1965         /* determine the block number within the file system corresponding
1966          * to the leaf at which free space was found.
1967          */
1968         blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD);
1969
1970         /* if not all bits of the dmap word are free, get the starting
1971          * bit number within the dmap word of the required string of free
1972          * bits and adjust the block number with this value.
1973          */
1974         if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN)
1975                 blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb);
1976
1977         /* allocate the blocks */
1978         if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1979                 *results = blkno;
1980
1981         return (rc);
1982 }
1983
1984
1985 /*
1986  * NAME:        dbAllocDmap()
1987  *
1988  * FUNCTION:    adjust the disk allocation map to reflect the allocation
1989  *              of a specified block range within a dmap.
1990  *
1991  *              this routine allocates the specified blocks from the dmap
1992  *              through a call to dbAllocBits(). if the allocation of the
1993  *              block range causes the maximum string of free blocks within
1994  *              the dmap to change (i.e. the value of the root of the dmap's
1995  *              dmtree), this routine will cause this change to be reflected
1996  *              up through the appropriate levels of the dmap control pages
1997  *              by a call to dbAdjCtl() for the L0 dmap control page that
1998  *              covers this dmap.
1999  *
2000  * PARAMETERS:
2001  *      bmp     -  pointer to bmap descriptor
2002  *      dp      -  pointer to dmap to allocate the block range from.
2003  *      blkno   -  starting block number of the block to be allocated.
2004  *      nblocks -  number of blocks to be allocated.
2005  *
2006  * RETURN VALUES:
2007  *      0       - success
2008  *      -EIO    - i/o error
2009  *
2010  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2011  */
2012 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2013                        int nblocks)
2014 {
2015         s8 oldroot;
2016         int rc;
2017
2018         /* save the current value of the root (i.e. maximum free string)
2019          * of the dmap tree.
2020          */
2021         oldroot = dp->tree.stree[ROOT];
2022
2023         /* allocate the specified (blocks) bits */
2024         dbAllocBits(bmp, dp, blkno, nblocks);
2025
2026         /* if the root has not changed, done. */
2027         if (dp->tree.stree[ROOT] == oldroot)
2028                 return (0);
2029
2030         /* root changed. bubble the change up to the dmap control pages.
2031          * if the adjustment of the upper level control pages fails,
2032          * backout the bit allocation (thus making everything consistent).
2033          */
2034         if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0)))
2035                 dbFreeBits(bmp, dp, blkno, nblocks);
2036
2037         return (rc);
2038 }
2039
2040
2041 /*
2042  * NAME:        dbFreeDmap()
2043  *
2044  * FUNCTION:    adjust the disk allocation map to reflect the allocation
2045  *              of a specified block range within a dmap.
2046  *
2047  *              this routine frees the specified blocks from the dmap through
2048  *              a call to dbFreeBits(). if the deallocation of the block range
2049  *              causes the maximum string of free blocks within the dmap to
2050  *              change (i.e. the value of the root of the dmap's dmtree), this
2051  *              routine will cause this change to be reflected up through the
2052  *              appropriate levels of the dmap control pages by a call to
2053  *              dbAdjCtl() for the L0 dmap control page that covers this dmap.
2054  *
2055  * PARAMETERS:
2056  *      bmp     -  pointer to bmap descriptor
2057  *      dp      -  pointer to dmap to free the block range from.
2058  *      blkno   -  starting block number of the block to be freed.
2059  *      nblocks -  number of blocks to be freed.
2060  *
2061  * RETURN VALUES:
2062  *      0       - success
2063  *      -EIO    - i/o error
2064  *
2065  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2066  */
2067 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2068                       int nblocks)
2069 {
2070         s8 oldroot;
2071         int rc = 0, word;
2072
2073         /* save the current value of the root (i.e. maximum free string)
2074          * of the dmap tree.
2075          */
2076         oldroot = dp->tree.stree[ROOT];
2077
2078         /* free the specified (blocks) bits */
2079         rc = dbFreeBits(bmp, dp, blkno, nblocks);
2080
2081         /* if error or the root has not changed, done. */
2082         if (rc || (dp->tree.stree[ROOT] == oldroot))
2083                 return (rc);
2084
2085         /* root changed. bubble the change up to the dmap control pages.
2086          * if the adjustment of the upper level control pages fails,
2087          * backout the deallocation.
2088          */
2089         if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) {
2090                 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
2091
2092                 /* as part of backing out the deallocation, we will have
2093                  * to back split the dmap tree if the deallocation caused
2094                  * the freed blocks to become part of a larger binary buddy
2095                  * system.
2096                  */
2097                 if (dp->tree.stree[word] == NOFREE)
2098                         dbBackSplit((dmtree_t *) & dp->tree, word);
2099
2100                 dbAllocBits(bmp, dp, blkno, nblocks);
2101         }
2102
2103         return (rc);
2104 }
2105
2106
2107 /*
2108  * NAME:        dbAllocBits()
2109  *
2110  * FUNCTION:    allocate a specified block range from a dmap.
2111  *
2112  *              this routine updates the dmap to reflect the working
2113  *              state allocation of the specified block range. it directly
2114  *              updates the bits of the working map and causes the adjustment
2115  *              of the binary buddy system described by the dmap's dmtree
2116  *              leaves to reflect the bits allocated.  it also causes the
2117  *              dmap's dmtree, as a whole, to reflect the allocated range.
2118  *
2119  * PARAMETERS:
2120  *      bmp     -  pointer to bmap descriptor
2121  *      dp      -  pointer to dmap to allocate bits from.
2122  *      blkno   -  starting block number of the bits to be allocated.
2123  *      nblocks -  number of bits to be allocated.
2124  *
2125  * RETURN VALUES: none
2126  *
2127  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2128  */
2129 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2130                         int nblocks)
2131 {
2132         int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
2133         dmtree_t *tp = (dmtree_t *) & dp->tree;
2134         int size;
2135         s8 *leaf;
2136
2137         /* pick up a pointer to the leaves of the dmap tree */
2138         leaf = dp->tree.stree + LEAFIND;
2139
2140         /* determine the bit number and word within the dmap of the
2141          * starting block.
2142          */
2143         dbitno = blkno & (BPERDMAP - 1);
2144         word = dbitno >> L2DBWORD;
2145
2146         /* block range better be within the dmap */
2147         assert(dbitno + nblocks <= BPERDMAP);
2148
2149         /* allocate the bits of the dmap's words corresponding to the block
2150          * range. not all bits of the first and last words may be contained
2151          * within the block range.  if this is the case, we'll work against
2152          * those words (i.e. partial first and/or last) on an individual basis
2153          * (a single pass), allocating the bits of interest by hand and
2154          * updating the leaf corresponding to the dmap word. a single pass
2155          * will be used for all dmap words fully contained within the
2156          * specified range.  within this pass, the bits of all fully contained
2157          * dmap words will be marked as free in a single shot and the leaves
2158          * will be updated. a single leaf may describe the free space of
2159          * multiple dmap words, so we may update only a subset of the actual
2160          * leaves corresponding to the dmap words of the block range.
2161          */
2162         for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
2163                 /* determine the bit number within the word and
2164                  * the number of bits within the word.
2165                  */
2166                 wbitno = dbitno & (DBWORD - 1);
2167                 nb = min(rembits, DBWORD - wbitno);
2168
2169                 /* check if only part of a word is to be allocated.
2170                  */
2171                 if (nb < DBWORD) {
2172                         /* allocate (set to 1) the appropriate bits within
2173                          * this dmap word.
2174                          */
2175                         dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
2176                                                       >> wbitno);
2177
2178                         /* update the leaf for this dmap word. in addition
2179                          * to setting the leaf value to the binary buddy max
2180                          * of the updated dmap word, dbSplit() will split
2181                          * the binary system of the leaves if need be.
2182                          */
2183                         dbSplit(tp, word, BUDMIN,
2184                                 dbMaxBud((u8 *) & dp->wmap[word]));
2185
2186                         word += 1;
2187                 } else {
2188                         /* one or more dmap words are fully contained
2189                          * within the block range.  determine how many
2190                          * words and allocate (set to 1) the bits of these
2191                          * words.
2192                          */
2193                         nwords = rembits >> L2DBWORD;
2194                         memset(&dp->wmap[word], (int) ONES, nwords * 4);
2195
2196                         /* determine how many bits.
2197                          */
2198                         nb = nwords << L2DBWORD;
2199
2200                         /* now update the appropriate leaves to reflect
2201                          * the allocated words.
2202                          */
2203                         for (; nwords > 0; nwords -= nw) {
2204                                 if (leaf[word] < BUDMIN) {
2205                                         jfs_error(bmp->db_ipbmap->i_sb,
2206                                                   "leaf page corrupt\n");
2207                                         break;
2208                                 }
2209
2210                                 /* determine what the leaf value should be
2211                                  * updated to as the minimum of the l2 number
2212                                  * of bits being allocated and the l2 number
2213                                  * of bits currently described by this leaf.
2214                                  */
2215                                 size = min_t(int, leaf[word],
2216                                              NLSTOL2BSZ(nwords));
2217
2218                                 /* update the leaf to reflect the allocation.
2219                                  * in addition to setting the leaf value to
2220                                  * NOFREE, dbSplit() will split the binary
2221                                  * system of the leaves to reflect the current
2222                                  * allocation (size).
2223                                  */
2224                                 dbSplit(tp, word, size, NOFREE);
2225
2226                                 /* get the number of dmap words handled */
2227                                 nw = BUDSIZE(size, BUDMIN);
2228                                 word += nw;
2229                         }
2230                 }
2231         }
2232
2233         /* update the free count for this dmap */
2234         le32_add_cpu(&dp->nfree, -nblocks);
2235
2236         BMAP_LOCK(bmp);
2237
2238         /* if this allocation group is completely free,
2239          * update the maximum allocation group number if this allocation
2240          * group is the new max.
2241          */
2242         agno = blkno >> bmp->db_agl2size;
2243         if (agno > bmp->db_maxag)
2244                 bmp->db_maxag = agno;
2245
2246         /* update the free count for the allocation group and map */
2247         bmp->db_agfree[agno] -= nblocks;
2248         bmp->db_nfree -= nblocks;
2249
2250         BMAP_UNLOCK(bmp);
2251 }
2252
2253
2254 /*
2255  * NAME:        dbFreeBits()
2256  *
2257  * FUNCTION:    free a specified block range from a dmap.
2258  *
2259  *              this routine updates the dmap to reflect the working
2260  *              state allocation of the specified block range. it directly
2261  *              updates the bits of the working map and causes the adjustment
2262  *              of the binary buddy system described by the dmap's dmtree
2263  *              leaves to reflect the bits freed.  it also causes the dmap's
2264  *              dmtree, as a whole, to reflect the deallocated range.
2265  *
2266  * PARAMETERS:
2267  *      bmp     -  pointer to bmap descriptor
2268  *      dp      -  pointer to dmap to free bits from.
2269  *      blkno   -  starting block number of the bits to be freed.
2270  *      nblocks -  number of bits to be freed.
2271  *
2272  * RETURN VALUES: 0 for success
2273  *
2274  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2275  */
2276 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2277                        int nblocks)
2278 {
2279         int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
2280         dmtree_t *tp = (dmtree_t *) & dp->tree;
2281         int rc = 0;
2282         int size;
2283
2284         /* determine the bit number and word within the dmap of the
2285          * starting block.
2286          */
2287         dbitno = blkno & (BPERDMAP - 1);
2288         word = dbitno >> L2DBWORD;
2289
2290         /* block range better be within the dmap.
2291          */
2292         assert(dbitno + nblocks <= BPERDMAP);
2293
2294         /* free the bits of the dmaps words corresponding to the block range.
2295          * not all bits of the first and last words may be contained within
2296          * the block range.  if this is the case, we'll work against those
2297          * words (i.e. partial first and/or last) on an individual basis
2298          * (a single pass), freeing the bits of interest by hand and updating
2299          * the leaf corresponding to the dmap word. a single pass will be used
2300          * for all dmap words fully contained within the specified range.
2301          * within this pass, the bits of all fully contained dmap words will
2302          * be marked as free in a single shot and the leaves will be updated. a
2303          * single leaf may describe the free space of multiple dmap words,
2304          * so we may update only a subset of the actual leaves corresponding
2305          * to the dmap words of the block range.
2306          *
2307          * dbJoin() is used to update leaf values and will join the binary
2308          * buddy system of the leaves if the new leaf values indicate this
2309          * should be done.
2310          */
2311         for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
2312                 /* determine the bit number within the word and
2313                  * the number of bits within the word.
2314                  */
2315                 wbitno = dbitno & (DBWORD - 1);
2316                 nb = min(rembits, DBWORD - wbitno);
2317
2318                 /* check if only part of a word is to be freed.
2319                  */
2320                 if (nb < DBWORD) {
2321                         /* free (zero) the appropriate bits within this
2322                          * dmap word.
2323                          */
2324                         dp->wmap[word] &=
2325                             cpu_to_le32(~(ONES << (DBWORD - nb)
2326                                           >> wbitno));
2327
2328                         /* update the leaf for this dmap word.
2329                          */
2330                         rc = dbJoin(tp, word,
2331                                     dbMaxBud((u8 *) & dp->wmap[word]));
2332                         if (rc)
2333                                 return rc;
2334
2335                         word += 1;
2336                 } else {
2337                         /* one or more dmap words are fully contained
2338                          * within the block range.  determine how many
2339                          * words and free (zero) the bits of these words.
2340                          */
2341                         nwords = rembits >> L2DBWORD;
2342                         memset(&dp->wmap[word], 0, nwords * 4);
2343
2344                         /* determine how many bits.
2345                          */
2346                         nb = nwords << L2DBWORD;
2347
2348                         /* now update the appropriate leaves to reflect
2349                          * the freed words.
2350                          */
2351                         for (; nwords > 0; nwords -= nw) {
2352                                 /* determine what the leaf value should be
2353                                  * updated to as the minimum of the l2 number
2354                                  * of bits being freed and the l2 (max) number
2355                                  * of bits that can be described by this leaf.
2356                                  */
2357                                 size =
2358                                     min(LITOL2BSZ
2359                                         (word, L2LPERDMAP, BUDMIN),
2360                                         NLSTOL2BSZ(nwords));
2361
2362                                 /* update the leaf.
2363                                  */
2364                                 rc = dbJoin(tp, word, size);
2365                                 if (rc)
2366                                         return rc;
2367
2368                                 /* get the number of dmap words handled.
2369                                  */
2370                                 nw = BUDSIZE(size, BUDMIN);
2371                                 word += nw;
2372                         }
2373                 }
2374         }
2375
2376         /* update the free count for this dmap.
2377          */
2378         le32_add_cpu(&dp->nfree, nblocks);
2379
2380         BMAP_LOCK(bmp);
2381
2382         /* update the free count for the allocation group and
2383          * map.
2384          */
2385         agno = blkno >> bmp->db_agl2size;
2386         bmp->db_nfree += nblocks;
2387         bmp->db_agfree[agno] += nblocks;
2388
2389         /* check if this allocation group is not completely free and
2390          * if it is currently the maximum (rightmost) allocation group.
2391          * if so, establish the new maximum allocation group number by
2392          * searching left for the first allocation group with allocation.
2393          */
2394         if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) ||
2395             (agno == bmp->db_numag - 1 &&
2396              bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) {
2397                 while (bmp->db_maxag > 0) {
2398                         bmp->db_maxag -= 1;
2399                         if (bmp->db_agfree[bmp->db_maxag] !=
2400                             bmp->db_agsize)
2401                                 break;
2402                 }
2403
2404                 /* re-establish the allocation group preference if the
2405                  * current preference is right of the maximum allocation
2406                  * group.
2407                  */
2408                 if (bmp->db_agpref > bmp->db_maxag)
2409                         bmp->db_agpref = bmp->db_maxag;
2410         }
2411
2412         BMAP_UNLOCK(bmp);
2413
2414         return 0;
2415 }
2416
2417
2418 /*
2419  * NAME:        dbAdjCtl()
2420  *
2421  * FUNCTION:    adjust a dmap control page at a specified level to reflect
2422  *              the change in a lower level dmap or dmap control page's
2423  *              maximum string of free blocks (i.e. a change in the root
2424  *              of the lower level object's dmtree) due to the allocation
2425  *              or deallocation of a range of blocks with a single dmap.
2426  *
2427  *              on entry, this routine is provided with the new value of
2428  *              the lower level dmap or dmap control page root and the
2429  *              starting block number of the block range whose allocation
2430  *              or deallocation resulted in the root change.  this range
2431  *              is respresented by a single leaf of the current dmapctl
2432  *              and the leaf will be updated with this value, possibly
2433  *              causing a binary buddy system within the leaves to be
2434  *              split or joined.  the update may also cause the dmapctl's
2435  *              dmtree to be updated.
2436  *
2437  *              if the adjustment of the dmap control page, itself, causes its
2438  *              root to change, this change will be bubbled up to the next dmap
2439  *              control level by a recursive call to this routine, specifying
2440  *              the new root value and the next dmap control page level to
2441  *              be adjusted.
2442  * PARAMETERS:
2443  *      bmp     -  pointer to bmap descriptor
2444  *      blkno   -  the first block of a block range within a dmap.  it is
2445  *                 the allocation or deallocation of this block range that
2446  *                 requires the dmap control page to be adjusted.
2447  *      newval  -  the new value of the lower level dmap or dmap control
2448  *                 page root.
2449  *      alloc   -  'true' if adjustment is due to an allocation.
2450  *      level   -  current level of dmap control page (i.e. L0, L1, L2) to
2451  *                 be adjusted.
2452  *
2453  * RETURN VALUES:
2454  *      0       - success
2455  *      -EIO    - i/o error
2456  *
2457  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2458  */
2459 static int
2460 dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level)
2461 {
2462         struct metapage *mp;
2463         s8 oldroot;
2464         int oldval;
2465         s64 lblkno;
2466         struct dmapctl *dcp;
2467         int rc, leafno, ti;
2468
2469         /* get the buffer for the dmap control page for the specified
2470          * block number and control page level.
2471          */
2472         lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level);
2473         mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
2474         if (mp == NULL)
2475                 return -EIO;
2476         dcp = (struct dmapctl *) mp->data;
2477
2478         if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
2479                 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n");
2480                 release_metapage(mp);
2481                 return -EIO;
2482         }
2483
2484         /* determine the leaf number corresponding to the block and
2485          * the index within the dmap control tree.
2486          */
2487         leafno = BLKTOCTLLEAF(blkno, dcp->budmin);
2488         ti = leafno + le32_to_cpu(dcp->leafidx);
2489
2490         /* save the current leaf value and the current root level (i.e.
2491          * maximum l2 free string described by this dmapctl).
2492          */
2493         oldval = dcp->stree[ti];
2494         oldroot = dcp->stree[ROOT];
2495
2496         /* check if this is a control page update for an allocation.
2497          * if so, update the leaf to reflect the new leaf value using
2498          * dbSplit(); otherwise (deallocation), use dbJoin() to update
2499          * the leaf with the new value.  in addition to updating the
2500          * leaf, dbSplit() will also split the binary buddy system of
2501          * the leaves, if required, and bubble new values within the
2502          * dmapctl tree, if required.  similarly, dbJoin() will join
2503          * the binary buddy system of leaves and bubble new values up
2504          * the dmapctl tree as required by the new leaf value.
2505          */
2506         if (alloc) {
2507                 /* check if we are in the middle of a binary buddy
2508                  * system.  this happens when we are performing the
2509                  * first allocation out of an allocation group that
2510                  * is part (not the first part) of a larger binary
2511                  * buddy system.  if we are in the middle, back split
2512                  * the system prior to calling dbSplit() which assumes
2513                  * that it is at the front of a binary buddy system.
2514                  */
2515                 if (oldval == NOFREE) {
2516                         rc = dbBackSplit((dmtree_t *) dcp, leafno);
2517                         if (rc) {
2518                                 release_metapage(mp);
2519                                 return rc;
2520                         }
2521                         oldval = dcp->stree[ti];
2522                 }
2523                 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval);
2524         } else {
2525                 rc = dbJoin((dmtree_t *) dcp, leafno, newval);
2526                 if (rc) {
2527                         release_metapage(mp);
2528                         return rc;
2529                 }
2530         }
2531
2532         /* check if the root of the current dmap control page changed due
2533          * to the update and if the current dmap control page is not at
2534          * the current top level (i.e. L0, L1, L2) of the map.  if so (i.e.
2535          * root changed and this is not the top level), call this routine
2536          * again (recursion) for the next higher level of the mapping to
2537          * reflect the change in root for the current dmap control page.
2538          */
2539         if (dcp->stree[ROOT] != oldroot) {
2540                 /* are we below the top level of the map.  if so,
2541                  * bubble the root up to the next higher level.
2542                  */
2543                 if (level < bmp->db_maxlevel) {
2544                         /* bubble up the new root of this dmap control page to
2545                          * the next level.
2546                          */
2547                         if ((rc =
2548                              dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc,
2549                                       level + 1))) {
2550                                 /* something went wrong in bubbling up the new
2551                                  * root value, so backout the changes to the
2552                                  * current dmap control page.
2553                                  */
2554                                 if (alloc) {
2555                                         dbJoin((dmtree_t *) dcp, leafno,
2556                                                oldval);
2557                                 } else {
2558                                         /* the dbJoin() above might have
2559                                          * caused a larger binary buddy system
2560                                          * to form and we may now be in the
2561                                          * middle of it.  if this is the case,
2562                                          * back split the buddies.
2563                                          */
2564                                         if (dcp->stree[ti] == NOFREE)
2565                                                 dbBackSplit((dmtree_t *)
2566                                                             dcp, leafno);
2567                                         dbSplit((dmtree_t *) dcp, leafno,
2568                                                 dcp->budmin, oldval);
2569                                 }
2570
2571                                 /* release the buffer and return the error.
2572                                  */
2573                                 release_metapage(mp);
2574                                 return (rc);
2575                         }
2576                 } else {
2577                         /* we're at the top level of the map. update
2578                          * the bmap control page to reflect the size
2579                          * of the maximum free buddy system.
2580                          */
2581                         assert(level == bmp->db_maxlevel);
2582                         if (bmp->db_maxfreebud != oldroot) {
2583                                 jfs_error(bmp->db_ipbmap->i_sb,
2584                                           "the maximum free buddy is not the old root\n");
2585                         }
2586                         bmp->db_maxfreebud = dcp->stree[ROOT];
2587                 }
2588         }
2589
2590         /* write the buffer.
2591          */
2592         write_metapage(mp);
2593
2594         return (0);
2595 }
2596
2597
2598 /*
2599  * NAME:        dbSplit()
2600  *
2601  * FUNCTION:    update the leaf of a dmtree with a new value, splitting
2602  *              the leaf from the binary buddy system of the dmtree's
2603  *              leaves, as required.
2604  *
2605  * PARAMETERS:
2606  *      tp      - pointer to the tree containing the leaf.
2607  *      leafno  - the number of the leaf to be updated.
2608  *      splitsz - the size the binary buddy system starting at the leaf
2609  *                must be split to, specified as the log2 number of blocks.
2610  *      newval  - the new value for the leaf.
2611  *
2612  * RETURN VALUES: none
2613  *
2614  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2615  */
2616 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval)
2617 {
2618         int budsz;
2619         int cursz;
2620         s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2621
2622         /* check if the leaf needs to be split.
2623          */
2624         if (leaf[leafno] > tp->dmt_budmin) {
2625                 /* the split occurs by cutting the buddy system in half
2626                  * at the specified leaf until we reach the specified
2627                  * size.  pick up the starting split size (current size
2628                  * - 1 in l2) and the corresponding buddy size.
2629                  */
2630                 cursz = leaf[leafno] - 1;
2631                 budsz = BUDSIZE(cursz, tp->dmt_budmin);
2632
2633                 /* split until we reach the specified size.
2634                  */
2635                 while (cursz >= splitsz) {
2636                         /* update the buddy's leaf with its new value.
2637                          */
2638                         dbAdjTree(tp, leafno ^ budsz, cursz);
2639
2640                         /* on to the next size and buddy.
2641                          */
2642                         cursz -= 1;
2643                         budsz >>= 1;
2644                 }
2645         }
2646
2647         /* adjust the dmap tree to reflect the specified leaf's new
2648          * value.
2649          */
2650         dbAdjTree(tp, leafno, newval);
2651 }
2652
2653
2654 /*
2655  * NAME:        dbBackSplit()
2656  *
2657  * FUNCTION:    back split the binary buddy system of dmtree leaves
2658  *              that hold a specified leaf until the specified leaf
2659  *              starts its own binary buddy system.
2660  *
2661  *              the allocators typically perform allocations at the start
2662  *              of binary buddy systems and dbSplit() is used to accomplish
2663  *              any required splits.  in some cases, however, allocation
2664  *              may occur in the middle of a binary system and requires a
2665  *              back split, with the split proceeding out from the middle of
2666  *              the system (less efficient) rather than the start of the
2667  *              system (more efficient).  the cases in which a back split
2668  *              is required are rare and are limited to the first allocation
2669  *              within an allocation group which is a part (not first part)
2670  *              of a larger binary buddy system and a few exception cases
2671  *              in which a previous join operation must be backed out.
2672  *
2673  * PARAMETERS:
2674  *      tp      - pointer to the tree containing the leaf.
2675  *      leafno  - the number of the leaf to be updated.
2676  *
2677  * RETURN VALUES: none
2678  *
2679  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2680  */
2681 static int dbBackSplit(dmtree_t * tp, int leafno)
2682 {
2683         int budsz, bud, w, bsz, size;
2684         int cursz;
2685         s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2686
2687         /* leaf should be part (not first part) of a binary
2688          * buddy system.
2689          */
2690         assert(leaf[leafno] == NOFREE);
2691
2692         /* the back split is accomplished by iteratively finding the leaf
2693          * that starts the buddy system that contains the specified leaf and
2694          * splitting that system in two.  this iteration continues until
2695          * the specified leaf becomes the start of a buddy system.
2696          *
2697          * determine maximum possible l2 size for the specified leaf.
2698          */
2699         size =
2700             LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs),
2701                       tp->dmt_budmin);
2702
2703         /* determine the number of leaves covered by this size.  this
2704          * is the buddy size that we will start with as we search for
2705          * the buddy system that contains the specified leaf.
2706          */
2707         budsz = BUDSIZE(size, tp->dmt_budmin);
2708
2709         /* back split.
2710          */
2711         while (leaf[leafno] == NOFREE) {
2712                 /* find the leftmost buddy leaf.
2713                  */
2714                 for (w = leafno, bsz = budsz;; bsz <<= 1,
2715                      w = (w < bud) ? w : bud) {
2716                         if (bsz >= le32_to_cpu(tp->dmt_nleafs)) {
2717                                 jfs_err("JFS: block map error in dbBackSplit");
2718                                 return -EIO;
2719                         }
2720
2721                         /* determine the buddy.
2722                          */
2723                         bud = w ^ bsz;
2724
2725                         /* check if this buddy is the start of the system.
2726                          */
2727                         if (leaf[bud] != NOFREE) {
2728                                 /* split the leaf at the start of the
2729                                  * system in two.
2730                                  */
2731                                 cursz = leaf[bud] - 1;
2732                                 dbSplit(tp, bud, cursz, cursz);
2733                                 break;
2734                         }
2735                 }
2736         }
2737
2738         if (leaf[leafno] != size) {
2739                 jfs_err("JFS: wrong leaf value in dbBackSplit");
2740                 return -EIO;
2741         }
2742         return 0;
2743 }
2744
2745
2746 /*
2747  * NAME:        dbJoin()
2748  *
2749  * FUNCTION:    update the leaf of a dmtree with a new value, joining
2750  *              the leaf with other leaves of the dmtree into a multi-leaf
2751  *              binary buddy system, as required.
2752  *
2753  * PARAMETERS:
2754  *      tp      - pointer to the tree containing the leaf.
2755  *      leafno  - the number of the leaf to be updated.
2756  *      newval  - the new value for the leaf.
2757  *
2758  * RETURN VALUES: none
2759  */
2760 static int dbJoin(dmtree_t * tp, int leafno, int newval)
2761 {
2762         int budsz, buddy;
2763         s8 *leaf;
2764
2765         /* can the new leaf value require a join with other leaves ?
2766          */
2767         if (newval >= tp->dmt_budmin) {
2768                 /* pickup a pointer to the leaves of the tree.
2769                  */
2770                 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2771
2772                 /* try to join the specified leaf into a large binary
2773                  * buddy system.  the join proceeds by attempting to join
2774                  * the specified leafno with its buddy (leaf) at new value.
2775                  * if the join occurs, we attempt to join the left leaf
2776                  * of the joined buddies with its buddy at new value + 1.
2777                  * we continue to join until we find a buddy that cannot be
2778                  * joined (does not have a value equal to the size of the
2779                  * last join) or until all leaves have been joined into a
2780                  * single system.
2781                  *
2782                  * get the buddy size (number of words covered) of
2783                  * the new value.
2784                  */
2785                 budsz = BUDSIZE(newval, tp->dmt_budmin);
2786
2787                 /* try to join.
2788                  */
2789                 while (budsz < le32_to_cpu(tp->dmt_nleafs)) {
2790                         /* get the buddy leaf.
2791                          */
2792                         buddy = leafno ^ budsz;
2793
2794                         /* if the leaf's new value is greater than its
2795                          * buddy's value, we join no more.
2796                          */
2797                         if (newval > leaf[buddy])
2798                                 break;
2799
2800                         /* It shouldn't be less */
2801                         if (newval < leaf[buddy])
2802                                 return -EIO;
2803
2804                         /* check which (leafno or buddy) is the left buddy.
2805                          * the left buddy gets to claim the blocks resulting
2806                          * from the join while the right gets to claim none.
2807                          * the left buddy is also eligible to participate in
2808                          * a join at the next higher level while the right
2809                          * is not.
2810                          *
2811                          */
2812                         if (leafno < buddy) {
2813                                 /* leafno is the left buddy.
2814                                  */
2815                                 dbAdjTree(tp, buddy, NOFREE);
2816                         } else {
2817                                 /* buddy is the left buddy and becomes
2818                                  * leafno.
2819                                  */
2820                                 dbAdjTree(tp, leafno, NOFREE);
2821                                 leafno = buddy;
2822                         }
2823
2824                         /* on to try the next join.
2825                          */
2826                         newval += 1;
2827                         budsz <<= 1;
2828                 }
2829         }
2830
2831         /* update the leaf value.
2832          */
2833         dbAdjTree(tp, leafno, newval);
2834
2835         return 0;
2836 }
2837
2838
2839 /*
2840  * NAME:        dbAdjTree()
2841  *
2842  * FUNCTION:    update a leaf of a dmtree with a new value, adjusting
2843  *              the dmtree, as required, to reflect the new leaf value.
2844  *              the combination of any buddies must already be done before
2845  *              this is called.
2846  *
2847  * PARAMETERS:
2848  *      tp      - pointer to the tree to be adjusted.
2849  *      leafno  - the number of the leaf to be updated.
2850  *      newval  - the new value for the leaf.
2851  *
2852  * RETURN VALUES: none
2853  */
2854 static void dbAdjTree(dmtree_t * tp, int leafno, int newval)
2855 {
2856         int lp, pp, k;
2857         int max;
2858
2859         /* pick up the index of the leaf for this leafno.
2860          */
2861         lp = leafno + le32_to_cpu(tp->dmt_leafidx);
2862
2863         /* is the current value the same as the old value ?  if so,
2864          * there is nothing to do.
2865          */
2866         if (tp->dmt_stree[lp] == newval)
2867                 return;
2868
2869         /* set the new value.
2870          */
2871         tp->dmt_stree[lp] = newval;
2872
2873         /* bubble the new value up the tree as required.
2874          */
2875         for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) {
2876                 /* get the index of the first leaf of the 4 leaf
2877                  * group containing the specified leaf (leafno).
2878                  */
2879                 lp = ((lp - 1) & ~0x03) + 1;
2880
2881                 /* get the index of the parent of this 4 leaf group.
2882                  */
2883                 pp = (lp - 1) >> 2;
2884
2885                 /* determine the maximum of the 4 leaves.
2886                  */
2887                 max = TREEMAX(&tp->dmt_stree[lp]);
2888
2889                 /* if the maximum of the 4 is the same as the
2890                  * parent's value, we're done.
2891                  */
2892                 if (tp->dmt_stree[pp] == max)
2893                         break;
2894
2895                 /* parent gets new value.
2896                  */
2897                 tp->dmt_stree[pp] = max;
2898
2899                 /* parent becomes leaf for next go-round.
2900                  */
2901                 lp = pp;
2902         }
2903 }
2904
2905
2906 /*
2907  * NAME:        dbFindLeaf()
2908  *
2909  * FUNCTION:    search a dmtree_t for sufficient free blocks, returning
2910  *              the index of a leaf describing the free blocks if
2911  *              sufficient free blocks are found.
2912  *
2913  *              the search starts at the top of the dmtree_t tree and
2914  *              proceeds down the tree to the leftmost leaf with sufficient
2915  *              free space.
2916  *
2917  * PARAMETERS:
2918  *      tp      - pointer to the tree to be searched.
2919  *      l2nb    - log2 number of free blocks to search for.
2920  *      leafidx - return pointer to be set to the index of the leaf
2921  *                describing at least l2nb free blocks if sufficient
2922  *                free blocks are found.
2923  *
2924  * RETURN VALUES:
2925  *      0       - success
2926  *      -ENOSPC - insufficient free blocks.
2927  */
2928 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx)
2929 {
2930         int ti, n = 0, k, x = 0;
2931
2932         /* first check the root of the tree to see if there is
2933          * sufficient free space.
2934          */
2935         if (l2nb > tp->dmt_stree[ROOT])
2936                 return -ENOSPC;
2937
2938         /* sufficient free space available. now search down the tree
2939          * starting at the next level for the leftmost leaf that
2940          * describes sufficient free space.
2941          */
2942         for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2943              k > 0; k--, ti = ((ti + n) << 2) + 1) {
2944                 /* search the four nodes at this level, starting from
2945                  * the left.
2946                  */
2947                 for (x = ti, n = 0; n < 4; n++) {
2948                         /* sufficient free space found.  move to the next
2949                          * level (or quit if this is the last level).
2950                          */
2951                         if (l2nb <= tp->dmt_stree[x + n])
2952                                 break;
2953                 }
2954
2955                 /* better have found something since the higher
2956                  * levels of the tree said it was here.
2957                  */
2958                 assert(n < 4);
2959         }
2960
2961         /* set the return to the leftmost leaf describing sufficient
2962          * free space.
2963          */
2964         *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
2965
2966         return (0);
2967 }
2968
2969
2970 /*
2971  * NAME:        dbFindBits()
2972  *
2973  * FUNCTION:    find a specified number of binary buddy free bits within a
2974  *              dmap bitmap word value.
2975  *
2976  *              this routine searches the bitmap value for (1 << l2nb) free
2977  *              bits at (1 << l2nb) alignments within the value.
2978  *
2979  * PARAMETERS:
2980  *      word    -  dmap bitmap word value.
2981  *      l2nb    -  number of free bits specified as a log2 number.
2982  *
2983  * RETURN VALUES:
2984  *      starting bit number of free bits.
2985  */
2986 static int dbFindBits(u32 word, int l2nb)
2987 {
2988         int bitno, nb;
2989         u32 mask;
2990
2991         /* get the number of bits.
2992          */
2993         nb = 1 << l2nb;
2994         assert(nb <= DBWORD);
2995
2996         /* complement the word so we can use a mask (i.e. 0s represent
2997          * free bits) and compute the mask.
2998          */
2999         word = ~word;
3000         mask = ONES << (DBWORD - nb);
3001
3002         /* scan the word for nb free bits at nb alignments.
3003          */
3004         for (bitno = 0; mask != 0; bitno += nb, mask >>= nb) {
3005                 if ((mask & word) == mask)
3006                         break;
3007         }
3008
3009         ASSERT(bitno < 32);
3010
3011         /* return the bit number.
3012          */
3013         return (bitno);
3014 }
3015
3016
3017 /*
3018  * NAME:        dbMaxBud(u8 *cp)
3019  *
3020  * FUNCTION:    determine the largest binary buddy string of free
3021  *              bits within 32-bits of the map.
3022  *
3023  * PARAMETERS:
3024  *      cp      -  pointer to the 32-bit value.
3025  *
3026  * RETURN VALUES:
3027  *      largest binary buddy of free bits within a dmap word.
3028  */
3029 static int dbMaxBud(u8 * cp)
3030 {
3031         signed char tmp1, tmp2;
3032
3033         /* check if the wmap word is all free. if so, the
3034          * free buddy size is BUDMIN.
3035          */
3036         if (*((uint *) cp) == 0)
3037                 return (BUDMIN);
3038
3039         /* check if the wmap word is half free. if so, the
3040          * free buddy size is BUDMIN-1.
3041          */
3042         if (*((u16 *) cp) == 0 || *((u16 *) cp + 1) == 0)
3043                 return (BUDMIN - 1);
3044
3045         /* not all free or half free. determine the free buddy
3046          * size thru table lookup using quarters of the wmap word.
3047          */
3048         tmp1 = max(budtab[cp[2]], budtab[cp[3]]);
3049         tmp2 = max(budtab[cp[0]], budtab[cp[1]]);
3050         return (max(tmp1, tmp2));
3051 }
3052
3053
3054 /*
3055  * NAME:        cnttz(uint word)
3056  *
3057  * FUNCTION:    determine the number of trailing zeros within a 32-bit
3058  *              value.
3059  *
3060  * PARAMETERS:
3061  *      value   -  32-bit value to be examined.
3062  *
3063  * RETURN VALUES:
3064  *      count of trailing zeros
3065  */
3066 static int cnttz(u32 word)
3067 {
3068         int n;
3069
3070         for (n = 0; n < 32; n++, word >>= 1) {
3071                 if (word & 0x01)
3072                         break;
3073         }
3074
3075         return (n);
3076 }
3077
3078
3079 /*
3080  * NAME:        cntlz(u32 value)
3081  *
3082  * FUNCTION:    determine the number of leading zeros within a 32-bit
3083  *              value.
3084  *
3085  * PARAMETERS:
3086  *      value   -  32-bit value to be examined.
3087  *
3088  * RETURN VALUES:
3089  *      count of leading zeros
3090  */
3091 static int cntlz(u32 value)
3092 {
3093         int n;
3094
3095         for (n = 0; n < 32; n++, value <<= 1) {
3096                 if (value & HIGHORDER)
3097                         break;
3098         }
3099         return (n);
3100 }
3101
3102
3103 /*
3104  * NAME:        blkstol2(s64 nb)
3105  *
3106  * FUNCTION:    convert a block count to its log2 value. if the block
3107  *              count is not a l2 multiple, it is rounded up to the next
3108  *              larger l2 multiple.
3109  *
3110  * PARAMETERS:
3111  *      nb      -  number of blocks
3112  *
3113  * RETURN VALUES:
3114  *      log2 number of blocks
3115  */
3116 static int blkstol2(s64 nb)
3117 {
3118         int l2nb;
3119         s64 mask;               /* meant to be signed */
3120
3121         mask = (s64) 1 << (64 - 1);
3122
3123         /* count the leading bits.
3124          */
3125         for (l2nb = 0; l2nb < 64; l2nb++, mask >>= 1) {
3126                 /* leading bit found.
3127                  */
3128                 if (nb & mask) {
3129                         /* determine the l2 value.
3130                          */
3131                         l2nb = (64 - 1) - l2nb;
3132
3133                         /* check if we need to round up.
3134                          */
3135                         if (~mask & nb)
3136                                 l2nb++;
3137
3138                         return (l2nb);
3139                 }
3140         }
3141         assert(0);
3142         return 0;               /* fix compiler warning */
3143 }
3144
3145
3146 /*
3147  * NAME:        dbAllocBottomUp()
3148  *
3149  * FUNCTION:    alloc the specified block range from the working block
3150  *              allocation map.
3151  *
3152  *              the blocks will be alloc from the working map one dmap
3153  *              at a time.
3154  *
3155  * PARAMETERS:
3156  *      ip      -  pointer to in-core inode;
3157  *      blkno   -  starting block number to be freed.
3158  *      nblocks -  number of blocks to be freed.
3159  *
3160  * RETURN VALUES:
3161  *      0       - success
3162  *      -EIO    - i/o error
3163  */
3164 int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks)
3165 {
3166         struct metapage *mp;
3167         struct dmap *dp;
3168         int nb, rc;
3169         s64 lblkno, rem;
3170         struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
3171         struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
3172
3173         IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
3174
3175         /* block to be allocated better be within the mapsize. */
3176         ASSERT(nblocks <= bmp->db_mapsize - blkno);
3177
3178         /*
3179          * allocate the blocks a dmap at a time.
3180          */
3181         mp = NULL;
3182         for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
3183                 /* release previous dmap if any */
3184                 if (mp) {
3185                         write_metapage(mp);
3186                 }
3187
3188                 /* get the buffer for the current dmap. */
3189                 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
3190                 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
3191                 if (mp == NULL) {
3192                         IREAD_UNLOCK(ipbmap);
3193                         return -EIO;
3194                 }
3195                 dp = (struct dmap *) mp->data;
3196
3197                 /* determine the number of blocks to be allocated from
3198                  * this dmap.
3199                  */
3200                 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
3201
3202                 /* allocate the blocks. */
3203                 if ((rc = dbAllocDmapBU(bmp, dp, blkno, nb))) {
3204                         release_metapage(mp);
3205                         IREAD_UNLOCK(ipbmap);
3206                         return (rc);
3207                 }
3208         }
3209
3210         /* write the last buffer. */
3211         write_metapage(mp);
3212
3213         IREAD_UNLOCK(ipbmap);
3214
3215         return (0);
3216 }
3217
3218
3219 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
3220                          int nblocks)
3221 {
3222         int rc;
3223         int dbitno, word, rembits, nb, nwords, wbitno, agno;
3224         s8 oldroot;
3225         struct dmaptree *tp = (struct dmaptree *) & dp->tree;
3226
3227         /* save the current value of the root (i.e. maximum free string)
3228          * of the dmap tree.
3229          */
3230         oldroot = tp->stree[ROOT];
3231
3232         /* determine the bit number and word within the dmap of the
3233          * starting block.
3234          */
3235         dbitno = blkno & (BPERDMAP - 1);
3236         word = dbitno >> L2DBWORD;
3237
3238         /* block range better be within the dmap */
3239         assert(dbitno + nblocks <= BPERDMAP);
3240
3241         /* allocate the bits of the dmap's words corresponding to the block
3242          * range. not all bits of the first and last words may be contained
3243          * within the block range.  if this is the case, we'll work against
3244          * those words (i.e. partial first and/or last) on an individual basis
3245          * (a single pass), allocating the bits of interest by hand and
3246          * updating the leaf corresponding to the dmap word. a single pass
3247          * will be used for all dmap words fully contained within the
3248          * specified range.  within this pass, the bits of all fully contained
3249          * dmap words will be marked as free in a single shot and the leaves
3250          * will be updated. a single leaf may describe the free space of
3251          * multiple dmap words, so we may update only a subset of the actual
3252          * leaves corresponding to the dmap words of the block range.
3253          */
3254         for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
3255                 /* determine the bit number within the word and
3256                  * the number of bits within the word.
3257                  */
3258                 wbitno = dbitno & (DBWORD - 1);
3259                 nb = min(rembits, DBWORD - wbitno);
3260
3261                 /* check if only part of a word is to be allocated.
3262                  */
3263                 if (nb < DBWORD) {
3264                         /* allocate (set to 1) the appropriate bits within
3265                          * this dmap word.
3266                          */
3267                         dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
3268                                                       >> wbitno);
3269
3270                         word++;
3271                 } else {
3272                         /* one or more dmap words are fully contained
3273                          * within the block range.  determine how many
3274                          * words and allocate (set to 1) the bits of these
3275                          * words.
3276                          */
3277                         nwords = rembits >> L2DBWORD;
3278                         memset(&dp->wmap[word], (int) ONES, nwords * 4);
3279
3280                         /* determine how many bits */
3281                         nb = nwords << L2DBWORD;
3282                         word += nwords;
3283                 }
3284         }
3285
3286         /* update the free count for this dmap */
3287         le32_add_cpu(&dp->nfree, -nblocks);
3288
3289         /* reconstruct summary tree */
3290         dbInitDmapTree(dp);
3291
3292         BMAP_LOCK(bmp);
3293
3294         /* if this allocation group is completely free,
3295          * update the highest active allocation group number
3296          * if this allocation group is the new max.
3297          */
3298         agno = blkno >> bmp->db_agl2size;
3299         if (agno > bmp->db_maxag)
3300                 bmp->db_maxag = agno;
3301
3302         /* update the free count for the allocation group and map */
3303         bmp->db_agfree[agno] -= nblocks;
3304         bmp->db_nfree -= nblocks;
3305
3306         BMAP_UNLOCK(bmp);
3307
3308         /* if the root has not changed, done. */
3309         if (tp->stree[ROOT] == oldroot)
3310                 return (0);
3311
3312         /* root changed. bubble the change up to the dmap control pages.
3313          * if the adjustment of the upper level control pages fails,
3314          * backout the bit allocation (thus making everything consistent).
3315          */
3316         if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0)))
3317                 dbFreeBits(bmp, dp, blkno, nblocks);
3318
3319         return (rc);
3320 }
3321
3322
3323 /*
3324  * NAME:        dbExtendFS()
3325  *
3326  * FUNCTION:    extend bmap from blkno for nblocks;
3327  *              dbExtendFS() updates bmap ready for dbAllocBottomUp();
3328  *
3329  * L2
3330  *  |
3331  *   L1---------------------------------L1
3332  *    |                                  |
3333  *     L0---------L0---------L0           L0---------L0---------L0
3334  *      |          |          |            |          |          |
3335  *       d0,...,dn  d0,...,dn  d0,...,dn    d0,...,dn  d0,...,dn  d0,.,dm;
3336  * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3337  *
3338  * <---old---><----------------------------extend----------------------->
3339  */
3340 int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks)
3341 {
3342         struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb);
3343         int nbperpage = sbi->nbperpage;
3344         int i, i0 = true, j, j0 = true, k, n;
3345         s64 newsize;
3346         s64 p;
3347         struct metapage *mp, *l2mp, *l1mp = NULL, *l0mp = NULL;
3348         struct dmapctl *l2dcp, *l1dcp, *l0dcp;
3349         struct dmap *dp;
3350         s8 *l0leaf, *l1leaf, *l2leaf;
3351         struct bmap *bmp = sbi->bmap;
3352         int agno, l2agsize, oldl2agsize;
3353         s64 ag_rem;
3354
3355         newsize = blkno + nblocks;
3356
3357         jfs_info("dbExtendFS: blkno:%Ld nblocks:%Ld newsize:%Ld",
3358                  (long long) blkno, (long long) nblocks, (long long) newsize);
3359
3360         /*
3361          *      initialize bmap control page.
3362          *
3363          * all the data in bmap control page should exclude
3364          * the mkfs hidden dmap page.
3365          */
3366
3367         /* update mapsize */
3368         bmp->db_mapsize = newsize;
3369         bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize);
3370
3371         /* compute new AG size */
3372         l2agsize = dbGetL2AGSize(newsize);
3373         oldl2agsize = bmp->db_agl2size;
3374
3375         bmp->db_agl2size = l2agsize;
3376         bmp->db_agsize = 1 << l2agsize;
3377
3378         /* compute new number of AG */
3379         agno = bmp->db_numag;
3380         bmp->db_numag = newsize >> l2agsize;
3381         bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0;
3382
3383         /*
3384          *      reconfigure db_agfree[]
3385          * from old AG configuration to new AG configuration;
3386          *
3387          * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3388          * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3389          * note: new AG size = old AG size * (2**x).
3390          */
3391         if (l2agsize == oldl2agsize)
3392                 goto extend;
3393         k = 1 << (l2agsize - oldl2agsize);
3394         ag_rem = bmp->db_agfree[0];     /* save agfree[0] */
3395         for (i = 0, n = 0; i < agno; n++) {
3396                 bmp->db_agfree[n] = 0;  /* init collection point */
3397
3398                 /* coalesce contiguous k AGs; */
3399                 for (j = 0; j < k && i < agno; j++, i++) {
3400                         /* merge AGi to AGn */
3401                         bmp->db_agfree[n] += bmp->db_agfree[i];
3402                 }
3403         }
3404         bmp->db_agfree[0] += ag_rem;    /* restore agfree[0] */
3405
3406         for (; n < MAXAG; n++)
3407                 bmp->db_agfree[n] = 0;
3408
3409         /*
3410          * update highest active ag number
3411          */
3412
3413         bmp->db_maxag = bmp->db_maxag / k;
3414
3415         /*
3416          *      extend bmap
3417          *
3418          * update bit maps and corresponding level control pages;
3419          * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3420          */
3421       extend:
3422         /* get L2 page */
3423         p = BMAPBLKNO + nbperpage;      /* L2 page */
3424         l2mp = read_metapage(ipbmap, p, PSIZE, 0);
3425         if (!l2mp) {
3426                 jfs_error(ipbmap->i_sb, "L2 page could not be read\n");
3427                 return -EIO;
3428         }
3429         l2dcp = (struct dmapctl *) l2mp->data;
3430
3431         /* compute start L1 */
3432         k = blkno >> L2MAXL1SIZE;
3433         l2leaf = l2dcp->stree + CTLLEAFIND + k;
3434         p = BLKTOL1(blkno, sbi->l2nbperpage);   /* L1 page */
3435
3436         /*
3437          * extend each L1 in L2
3438          */
3439         for (; k < LPERCTL; k++, p += nbperpage) {
3440                 /* get L1 page */
3441                 if (j0) {
3442                         /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3443                         l1mp = read_metapage(ipbmap, p, PSIZE, 0);
3444                         if (l1mp == NULL)
3445                                 goto errout;
3446                         l1dcp = (struct dmapctl *) l1mp->data;
3447
3448                         /* compute start L0 */
3449                         j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE;
3450                         l1leaf = l1dcp->stree + CTLLEAFIND + j;
3451                         p = BLKTOL0(blkno, sbi->l2nbperpage);
3452                         j0 = false;
3453                 } else {
3454                         /* assign/init L1 page */
3455                         l1mp = get_metapage(ipbmap, p, PSIZE, 0);
3456                         if (l1mp == NULL)
3457                                 goto errout;
3458
3459                         l1dcp = (struct dmapctl *) l1mp->data;
3460
3461                         /* compute start L0 */
3462                         j = 0;
3463                         l1leaf = l1dcp->stree + CTLLEAFIND;
3464                         p += nbperpage; /* 1st L0 of L1.k */
3465                 }
3466
3467                 /*
3468                  * extend each L0 in L1
3469                  */
3470                 for (; j < LPERCTL; j++) {
3471                         /* get L0 page */
3472                         if (i0) {
3473                                 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3474
3475                                 l0mp = read_metapage(ipbmap, p, PSIZE, 0);
3476                                 if (l0mp == NULL)
3477                                         goto errout;
3478                                 l0dcp = (struct dmapctl *) l0mp->data;
3479
3480                                 /* compute start dmap */
3481                                 i = (blkno & (MAXL0SIZE - 1)) >>
3482                                     L2BPERDMAP;
3483                                 l0leaf = l0dcp->stree + CTLLEAFIND + i;
3484                                 p = BLKTODMAP(blkno,
3485                                               sbi->l2nbperpage);
3486                                 i0 = false;
3487                         } else {
3488                                 /* assign/init L0 page */
3489                                 l0mp = get_metapage(ipbmap, p, PSIZE, 0);
3490                                 if (l0mp == NULL)
3491                                         goto errout;
3492
3493                                 l0dcp = (struct dmapctl *) l0mp->data;
3494
3495                                 /* compute start dmap */
3496                                 i = 0;
3497                                 l0leaf = l0dcp->stree + CTLLEAFIND;
3498                                 p += nbperpage; /* 1st dmap of L0.j */
3499                         }
3500
3501                         /*
3502                          * extend each dmap in L0
3503                          */
3504                         for (; i < LPERCTL; i++) {
3505                                 /*
3506                                  * reconstruct the dmap page, and
3507                                  * initialize corresponding parent L0 leaf
3508                                  */
3509                                 if ((n = blkno & (BPERDMAP - 1))) {
3510                                         /* read in dmap page: */
3511                                         mp = read_metapage(ipbmap, p,
3512                                                            PSIZE, 0);
3513                                         if (mp == NULL)
3514                                                 goto errout;
3515                                         n = min(nblocks, (s64)BPERDMAP - n);
3516                                 } else {
3517                                         /* assign/init dmap page */
3518                                         mp = read_metapage(ipbmap, p,
3519                                                            PSIZE, 0);
3520                                         if (mp == NULL)
3521                                                 goto errout;
3522
3523                                         n = min_t(s64, nblocks, BPERDMAP);
3524                                 }
3525
3526                                 dp = (struct dmap *) mp->data;
3527                                 *l0leaf = dbInitDmap(dp, blkno, n);
3528
3529                                 bmp->db_nfree += n;
3530                                 agno = le64_to_cpu(dp->start) >> l2agsize;
3531                                 bmp->db_agfree[agno] += n;
3532
3533                                 write_metapage(mp);
3534
3535                                 l0leaf++;
3536                                 p += nbperpage;
3537
3538                                 blkno += n;
3539                                 nblocks -= n;
3540                                 if (nblocks == 0)
3541                                         break;
3542                         }       /* for each dmap in a L0 */
3543
3544                         /*
3545                          * build current L0 page from its leaves, and
3546                          * initialize corresponding parent L1 leaf
3547                          */
3548                         *l1leaf = dbInitDmapCtl(l0dcp, 0, ++i);
3549                         write_metapage(l0mp);
3550                         l0mp = NULL;
3551
3552                         if (nblocks)
3553                                 l1leaf++;       /* continue for next L0 */
3554                         else {
3555                                 /* more than 1 L0 ? */
3556                                 if (j > 0)
3557                                         break;  /* build L1 page */
3558                                 else {
3559                                         /* summarize in global bmap page */
3560                                         bmp->db_maxfreebud = *l1leaf;
3561                                         release_metapage(l1mp);
3562                                         release_metapage(l2mp);
3563                                         goto finalize;
3564                                 }
3565                         }
3566                 }               /* for each L0 in a L1 */
3567
3568                 /*
3569                  * build current L1 page from its leaves, and
3570                  * initialize corresponding parent L2 leaf
3571                  */
3572                 *l2leaf = dbInitDmapCtl(l1dcp, 1, ++j);
3573                 write_metapage(l1mp);
3574                 l1mp = NULL;
3575
3576                 if (nblocks)
3577                         l2leaf++;       /* continue for next L1 */
3578                 else {
3579                         /* more than 1 L1 ? */
3580                         if (k > 0)
3581                                 break;  /* build L2 page */
3582                         else {
3583                                 /* summarize in global bmap page */
3584                                 bmp->db_maxfreebud = *l2leaf;
3585                                 release_metapage(l2mp);
3586                                 goto finalize;
3587                         }
3588                 }
3589         }                       /* for each L1 in a L2 */
3590
3591         jfs_error(ipbmap->i_sb, "function has not returned as expected\n");
3592 errout:
3593         if (l0mp)
3594                 release_metapage(l0mp);
3595         if (l1mp)
3596                 release_metapage(l1mp);
3597         release_metapage(l2mp);
3598         return -EIO;
3599
3600         /*
3601          *      finalize bmap control page
3602          */
3603 finalize:
3604
3605         return 0;
3606 }
3607
3608
3609 /*
3610  *      dbFinalizeBmap()
3611  */
3612 void dbFinalizeBmap(struct inode *ipbmap)
3613 {
3614         struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
3615         int actags, inactags, l2nl;
3616         s64 ag_rem, actfree, inactfree, avgfree;
3617         int i, n;
3618
3619         /*
3620          *      finalize bmap control page
3621          */
3622 //finalize:
3623         /*
3624          * compute db_agpref: preferred ag to allocate from
3625          * (the leftmost ag with average free space in it);
3626          */
3627 //agpref:
3628         /* get the number of active ags and inactive ags */
3629         actags = bmp->db_maxag + 1;
3630         inactags = bmp->db_numag - actags;
3631         ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1);        /* ??? */
3632
3633         /* determine how many blocks are in the inactive allocation
3634          * groups. in doing this, we must account for the fact that
3635          * the rightmost group might be a partial group (i.e. file
3636          * system size is not a multiple of the group size).
3637          */
3638         inactfree = (inactags && ag_rem) ?
3639             ((inactags - 1) << bmp->db_agl2size) + ag_rem
3640             : inactags << bmp->db_agl2size;
3641
3642         /* determine how many free blocks are in the active
3643          * allocation groups plus the average number of free blocks
3644          * within the active ags.
3645          */
3646         actfree = bmp->db_nfree - inactfree;
3647         avgfree = (u32) actfree / (u32) actags;
3648
3649         /* if the preferred allocation group has not average free space.
3650          * re-establish the preferred group as the leftmost
3651          * group with average free space.
3652          */
3653         if (bmp->db_agfree[bmp->db_agpref] < avgfree) {
3654                 for (bmp->db_agpref = 0; bmp->db_agpref < actags;
3655                      bmp->db_agpref++) {
3656                         if (bmp->db_agfree[bmp->db_agpref] >= avgfree)
3657                                 break;
3658                 }
3659                 if (bmp->db_agpref >= bmp->db_numag) {
3660                         jfs_error(ipbmap->i_sb,
3661                                   "cannot find ag with average freespace\n");
3662                 }
3663         }
3664
3665         /*
3666          * compute db_aglevel, db_agheight, db_width, db_agstart:
3667          * an ag is covered in aglevel dmapctl summary tree,
3668          * at agheight level height (from leaf) with agwidth number of nodes
3669          * each, which starts at agstart index node of the smmary tree node
3670          * array;
3671          */
3672         bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize);
3673         l2nl =
3674             bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL);
3675         bmp->db_agheight = l2nl >> 1;
3676         bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1));
3677         for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0;
3678              i--) {
3679                 bmp->db_agstart += n;
3680                 n <<= 2;
3681         }
3682
3683 }
3684
3685
3686 /*
3687  * NAME:        dbInitDmap()/ujfs_idmap_page()
3688  *
3689  * FUNCTION:    initialize working/persistent bitmap of the dmap page
3690  *              for the specified number of blocks:
3691  *
3692  *              at entry, the bitmaps had been initialized as free (ZEROS);
3693  *              The number of blocks will only account for the actually
3694  *              existing blocks. Blocks which don't actually exist in
3695  *              the aggregate will be marked as allocated (ONES);
3696  *
3697  * PARAMETERS:
3698  *      dp      - pointer to page of map
3699  *      nblocks - number of blocks this page
3700  *
3701  * RETURNS: NONE
3702  */
3703 static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks)
3704 {
3705         int blkno, w, b, r, nw, nb, i;
3706
3707         /* starting block number within the dmap */
3708         blkno = Blkno & (BPERDMAP - 1);
3709
3710         if (blkno == 0) {
3711                 dp->nblocks = dp->nfree = cpu_to_le32(nblocks);
3712                 dp->start = cpu_to_le64(Blkno);
3713
3714                 if (nblocks == BPERDMAP) {
3715                         memset(&dp->wmap[0], 0, LPERDMAP * 4);
3716                         memset(&dp->pmap[0], 0, LPERDMAP * 4);
3717                         goto initTree;
3718                 }
3719         } else {
3720                 le32_add_cpu(&dp->nblocks, nblocks);
3721                 le32_add_cpu(&dp->nfree, nblocks);
3722         }
3723
3724         /* word number containing start block number */
3725         w = blkno >> L2DBWORD;
3726
3727         /*
3728          * free the bits corresponding to the block range (ZEROS):
3729          * note: not all bits of the first and last words may be contained
3730          * within the block range.
3731          */
3732         for (r = nblocks; r > 0; r -= nb, blkno += nb) {
3733                 /* number of bits preceding range to be freed in the word */
3734                 b = blkno & (DBWORD - 1);
3735                 /* number of bits to free in the word */
3736                 nb = min(r, DBWORD - b);
3737
3738                 /* is partial word to be freed ? */
3739                 if (nb < DBWORD) {
3740                         /* free (set to 0) from the bitmap word */
3741                         dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3742                                                      >> b));
3743                         dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3744                                                      >> b));
3745
3746                         /* skip the word freed */
3747                         w++;
3748                 } else {
3749                         /* free (set to 0) contiguous bitmap words */
3750                         nw = r >> L2DBWORD;
3751                         memset(&dp->wmap[w], 0, nw * 4);
3752                         memset(&dp->pmap[w], 0, nw * 4);
3753
3754                         /* skip the words freed */
3755                         nb = nw << L2DBWORD;
3756                         w += nw;
3757                 }
3758         }
3759
3760         /*
3761          * mark bits following the range to be freed (non-existing
3762          * blocks) as allocated (ONES)
3763          */
3764
3765         if (blkno == BPERDMAP)
3766                 goto initTree;
3767
3768         /* the first word beyond the end of existing blocks */
3769         w = blkno >> L2DBWORD;
3770
3771         /* does nblocks fall on a 32-bit boundary ? */
3772         b = blkno & (DBWORD - 1);
3773         if (b) {
3774                 /* mark a partial word allocated */
3775                 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b);
3776                 w++;
3777         }
3778
3779         /* set the rest of the words in the page to allocated (ONES) */
3780         for (i = w; i < LPERDMAP; i++)
3781                 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES);
3782
3783         /*
3784          * init tree
3785          */
3786       initTree:
3787         return (dbInitDmapTree(dp));
3788 }
3789
3790
3791 /*
3792  * NAME:        dbInitDmapTree()/ujfs_complete_dmap()
3793  *
3794  * FUNCTION:    initialize summary tree of the specified dmap:
3795  *
3796  *              at entry, bitmap of the dmap has been initialized;
3797  *
3798  * PARAMETERS:
3799  *      dp      - dmap to complete
3800  *      blkno   - starting block number for this dmap
3801  *      treemax - will be filled in with max free for this dmap
3802  *
3803  * RETURNS:     max free string at the root of the tree
3804  */
3805 static int dbInitDmapTree(struct dmap * dp)
3806 {
3807         struct dmaptree *tp;
3808         s8 *cp;
3809         int i;
3810
3811         /* init fixed info of tree */
3812         tp = &dp->tree;
3813         tp->nleafs = cpu_to_le32(LPERDMAP);
3814         tp->l2nleafs = cpu_to_le32(L2LPERDMAP);
3815         tp->leafidx = cpu_to_le32(LEAFIND);
3816         tp->height = cpu_to_le32(4);
3817         tp->budmin = BUDMIN;
3818
3819         /* init each leaf from corresponding wmap word:
3820          * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3821          * bitmap word are allocated.
3822          */
3823         cp = tp->stree + le32_to_cpu(tp->leafidx);
3824         for (i = 0; i < LPERDMAP; i++)
3825                 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]);
3826
3827         /* build the dmap's binary buddy summary tree */
3828         return (dbInitTree(tp));
3829 }
3830
3831
3832 /*
3833  * NAME:        dbInitTree()/ujfs_adjtree()
3834  *
3835  * FUNCTION:    initialize binary buddy summary tree of a dmap or dmapctl.
3836  *
3837  *              at entry, the leaves of the tree has been initialized
3838  *              from corresponding bitmap word or root of summary tree
3839  *              of the child control page;
3840  *              configure binary buddy system at the leaf level, then
3841  *              bubble up the values of the leaf nodes up the tree.
3842  *
3843  * PARAMETERS:
3844  *      cp      - Pointer to the root of the tree
3845  *      l2leaves- Number of leaf nodes as a power of 2
3846  *      l2min   - Number of blocks that can be covered by a leaf
3847  *                as a power of 2
3848  *
3849  * RETURNS: max free string at the root of the tree
3850  */
3851 static int dbInitTree(struct dmaptree * dtp)
3852 {
3853         int l2max, l2free, bsize, nextb, i;
3854         int child, parent, nparent;
3855         s8 *tp, *cp, *cp1;
3856
3857         tp = dtp->stree;
3858
3859         /* Determine the maximum free string possible for the leaves */
3860         l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin;
3861
3862         /*
3863          * configure the leaf level into binary buddy system
3864          *
3865          * Try to combine buddies starting with a buddy size of 1
3866          * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3867          * can be combined if both buddies have a maximum free of l2min;
3868          * the combination will result in the left-most buddy leaf having
3869          * a maximum free of l2min+1.
3870          * After processing all buddies for a given size, process buddies
3871          * at the next higher buddy size (i.e. current size * 2) and
3872          * the next maximum free (current free + 1).
3873          * This continues until the maximum possible buddy combination
3874          * yields maximum free.
3875          */
3876         for (l2free = dtp->budmin, bsize = 1; l2free < l2max;
3877              l2free++, bsize = nextb) {
3878                 /* get next buddy size == current buddy pair size */
3879                 nextb = bsize << 1;
3880
3881                 /* scan each adjacent buddy pair at current buddy size */
3882                 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx);
3883                      i < le32_to_cpu(dtp->nleafs);
3884                      i += nextb, cp += nextb) {
3885                         /* coalesce if both adjacent buddies are max free */
3886                         if (*cp == l2free && *(cp + bsize) == l2free) {
3887                                 *cp = l2free + 1;       /* left take right */
3888                                 *(cp + bsize) = -1;     /* right give left */
3889                         }
3890                 }
3891         }
3892
3893         /*
3894          * bubble summary information of leaves up the tree.
3895          *
3896          * Starting at the leaf node level, the four nodes described by
3897          * the higher level parent node are compared for a maximum free and
3898          * this maximum becomes the value of the parent node.
3899          * when all lower level nodes are processed in this fashion then
3900          * move up to the next level (parent becomes a lower level node) and
3901          * continue the process for that level.
3902          */
3903         for (child = le32_to_cpu(dtp->leafidx),
3904              nparent = le32_to_cpu(dtp->nleafs) >> 2;
3905              nparent > 0; nparent >>= 2, child = parent) {
3906                 /* get index of 1st node of parent level */
3907                 parent = (child - 1) >> 2;
3908
3909                 /* set the value of the parent node as the maximum
3910                  * of the four nodes of the current level.
3911                  */
3912                 for (i = 0, cp = tp + child, cp1 = tp + parent;
3913                      i < nparent; i++, cp += 4, cp1++)
3914                         *cp1 = TREEMAX(cp);
3915         }
3916
3917         return (*tp);
3918 }
3919
3920
3921 /*
3922  *      dbInitDmapCtl()
3923  *
3924  * function: initialize dmapctl page
3925  */
3926 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i)
3927 {                               /* start leaf index not covered by range */
3928         s8 *cp;
3929
3930         dcp->nleafs = cpu_to_le32(LPERCTL);
3931         dcp->l2nleafs = cpu_to_le32(L2LPERCTL);
3932         dcp->leafidx = cpu_to_le32(CTLLEAFIND);
3933         dcp->height = cpu_to_le32(5);
3934         dcp->budmin = L2BPERDMAP + L2LPERCTL * level;
3935
3936         /*
3937          * initialize the leaves of current level that were not covered
3938          * by the specified input block range (i.e. the leaves have no
3939          * low level dmapctl or dmap).
3940          */
3941         cp = &dcp->stree[CTLLEAFIND + i];
3942         for (; i < LPERCTL; i++)
3943                 *cp++ = NOFREE;
3944
3945         /* build the dmap's binary buddy summary tree */
3946         return (dbInitTree((struct dmaptree *) dcp));
3947 }
3948
3949
3950 /*
3951  * NAME:        dbGetL2AGSize()/ujfs_getagl2size()
3952  *
3953  * FUNCTION:    Determine log2(allocation group size) from aggregate size
3954  *
3955  * PARAMETERS:
3956  *      nblocks - Number of blocks in aggregate
3957  *
3958  * RETURNS: log2(allocation group size) in aggregate blocks
3959  */
3960 static int dbGetL2AGSize(s64 nblocks)
3961 {
3962         s64 sz;
3963         s64 m;
3964         int l2sz;
3965
3966         if (nblocks < BPERDMAP * MAXAG)
3967                 return (L2BPERDMAP);
3968
3969         /* round up aggregate size to power of 2 */
3970         m = ((u64) 1 << (64 - 1));
3971         for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) {
3972                 if (m & nblocks)
3973                         break;
3974         }
3975
3976         sz = (s64) 1 << l2sz;
3977         if (sz < nblocks)
3978                 l2sz += 1;
3979
3980         /* agsize = roundupSize/max_number_of_ag */
3981         return (l2sz - L2MAXAG);
3982 }
3983
3984
3985 /*
3986  * NAME:        dbMapFileSizeToMapSize()
3987  *
3988  * FUNCTION:    compute number of blocks the block allocation map file
3989  *              can cover from the map file size;
3990  *
3991  * RETURNS:     Number of blocks which can be covered by this block map file;
3992  */
3993
3994 /*
3995  * maximum number of map pages at each level including control pages
3996  */
3997 #define MAXL0PAGES      (1 + LPERCTL)
3998 #define MAXL1PAGES      (1 + LPERCTL * MAXL0PAGES)
3999
4000 /*
4001  * convert number of map pages to the zero origin top dmapctl level
4002  */
4003 #define BMAPPGTOLEV(npages)     \
4004         (((npages) <= 3 + MAXL0PAGES) ? 0 : \
4005          ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4006
4007 s64 dbMapFileSizeToMapSize(struct inode * ipbmap)
4008 {
4009         struct super_block *sb = ipbmap->i_sb;
4010         s64 nblocks;
4011         s64 npages, ndmaps;
4012         int level, i;
4013         int complete, factor;
4014
4015         nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize;
4016         npages = nblocks >> JFS_SBI(sb)->l2nbperpage;
4017         level = BMAPPGTOLEV(npages);
4018
4019         /* At each level, accumulate the number of dmap pages covered by
4020          * the number of full child levels below it;
4021          * repeat for the last incomplete child level.
4022          */
4023         ndmaps = 0;
4024         npages--;               /* skip the first global control page */
4025         /* skip higher level control pages above top level covered by map */
4026         npages -= (2 - level);
4027         npages--;               /* skip top level's control page */
4028         for (i = level; i >= 0; i--) {
4029                 factor =
4030                     (i == 2) ? MAXL1PAGES : ((i == 1) ? MAXL0PAGES : 1);
4031                 complete = (u32) npages / factor;
4032                 ndmaps += complete * ((i == 2) ? LPERCTL * LPERCTL :
4033                                       ((i == 1) ? LPERCTL : 1));
4034
4035                 /* pages in last/incomplete child */
4036                 npages = (u32) npages % factor;
4037                 /* skip incomplete child's level control page */
4038                 npages--;
4039         }
4040
4041         /* convert the number of dmaps into the number of blocks
4042          * which can be covered by the dmaps;
4043          */
4044         nblocks = ndmaps << L2BPERDMAP;
4045
4046         return (nblocks);
4047 }