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