fs/jfs/jfs_dmap.c

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