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