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