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 for
 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 = 1 << 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                                 return rc;
2554                         oldval = dcp->stree[ti];
2555                 }
2556                 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval);
2557         } else {
2558                 rc = dbJoin((dmtree_t *) dcp, leafno, newval);
2559                 if (rc)
2560                         return rc;
2561         }
2562
2563         /* check if the root of the current dmap control page changed due
2564          * to the update and if the current dmap control page is not at
2565          * the current top level (i.e. L0, L1, L2) of the map.  if so (i.e.
2566          * root changed and this is not the top level), call this routine
2567          * again (recursion) for the next higher level of the mapping to
2568          * reflect the change in root for the current dmap control page.
2569          */
2570         if (dcp->stree[ROOT] != oldroot) {
2571                 /* are we below the top level of the map.  if so,
2572                  * bubble the root up to the next higher level.
2573                  */
2574                 if (level < bmp->db_maxlevel) {
2575                         /* bubble up the new root of this dmap control page to
2576                          * the next level.
2577                          */
2578                         if ((rc =
2579                              dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc,
2580                                       level + 1))) {
2581                                 /* something went wrong in bubbling up the new
2582                                  * root value, so backout the changes to the
2583                                  * current dmap control page.
2584                                  */
2585                                 if (alloc) {
2586                                         dbJoin((dmtree_t *) dcp, leafno,
2587                                                oldval);
2588                                 } else {
2589                                         /* the dbJoin() above might have
2590                                          * caused a larger binary buddy system
2591                                          * to form and we may now be in the
2592                                          * middle of it.  if this is the case,
2593                                          * back split the buddies.
2594                                          */
2595                                         if (dcp->stree[ti] == NOFREE)
2596                                                 dbBackSplit((dmtree_t *)
2597                                                             dcp, leafno);
2598                                         dbSplit((dmtree_t *) dcp, leafno,
2599                                                 dcp->budmin, oldval);
2600                                 }
2601
2602                                 /* release the buffer and return the error.
2603                                  */
2604                                 release_metapage(mp);
2605                                 return (rc);
2606                         }
2607                 } else {
2608                         /* we're at the top level of the map. update
2609                          * the bmap control page to reflect the size
2610                          * of the maximum free buddy system.
2611                          */
2612                         assert(level == bmp->db_maxlevel);
2613                         if (bmp->db_maxfreebud != oldroot) {
2614                                 jfs_error(bmp->db_ipbmap->i_sb,
2615                                           "the maximum free buddy is not the old root\n");
2616                         }
2617                         bmp->db_maxfreebud = dcp->stree[ROOT];
2618                 }
2619         }
2620
2621         /* write the buffer.
2622          */
2623         write_metapage(mp);
2624
2625         return (0);
2626 }
2627
2628
2629 /*
2630  * NAME:        dbSplit()
2631  *
2632  * FUNCTION:    update the leaf of a dmtree with a new value, splitting
2633  *              the leaf from the binary buddy system of the dmtree's
2634  *              leaves, as required.
2635  *
2636  * PARAMETERS:
2637  *      tp      - pointer to the tree containing the leaf.
2638  *      leafno  - the number of the leaf to be updated.
2639  *      splitsz - the size the binary buddy system starting at the leaf
2640  *                must be split to, specified as the log2 number of blocks.
2641  *      newval  - the new value for the leaf.
2642  *
2643  * RETURN VALUES: none
2644  *
2645  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2646  */
2647 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval)
2648 {
2649         int budsz;
2650         int cursz;
2651         s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2652
2653         /* check if the leaf needs to be split.
2654          */
2655         if (leaf[leafno] > tp->dmt_budmin) {
2656                 /* the split occurs by cutting the buddy system in half
2657                  * at the specified leaf until we reach the specified
2658                  * size.  pick up the starting split size (current size
2659                  * - 1 in l2) and the corresponding buddy size.
2660                  */
2661                 cursz = leaf[leafno] - 1;
2662                 budsz = BUDSIZE(cursz, tp->dmt_budmin);
2663
2664                 /* split until we reach the specified size.
2665                  */
2666                 while (cursz >= splitsz) {
2667                         /* update the buddy's leaf with its new value.
2668                          */
2669                         dbAdjTree(tp, leafno ^ budsz, cursz);
2670
2671                         /* on to the next size and buddy.
2672                          */
2673                         cursz -= 1;
2674                         budsz >>= 1;
2675                 }
2676         }
2677
2678         /* adjust the dmap tree to reflect the specified leaf's new
2679          * value.
2680          */
2681         dbAdjTree(tp, leafno, newval);
2682 }
2683
2684
2685 /*
2686  * NAME:        dbBackSplit()
2687  *
2688  * FUNCTION:    back split the binary buddy system of dmtree leaves
2689  *              that hold a specified leaf until the specified leaf
2690  *              starts its own binary buddy system.
2691  *
2692  *              the allocators typically perform allocations at the start
2693  *              of binary buddy systems and dbSplit() is used to accomplish
2694  *              any required splits.  in some cases, however, allocation
2695  *              may occur in the middle of a binary system and requires a
2696  *              back split, with the split proceeding out from the middle of
2697  *              the system (less efficient) rather than the start of the
2698  *              system (more efficient).  the cases in which a back split
2699  *              is required are rare and are limited to the first allocation
2700  *              within an allocation group which is a part (not first part)
2701  *              of a larger binary buddy system and a few exception cases
2702  *              in which a previous join operation must be backed out.
2703  *
2704  * PARAMETERS:
2705  *      tp      - pointer to the tree containing the leaf.
2706  *      leafno  - the number of the leaf to be updated.
2707  *
2708  * RETURN VALUES: none
2709  *
2710  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2711  */
2712 static int dbBackSplit(dmtree_t * tp, int leafno)
2713 {
2714         int budsz, bud, w, bsz, size;
2715         int cursz;
2716         s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2717
2718         /* leaf should be part (not first part) of a binary
2719          * buddy system.
2720          */
2721         assert(leaf[leafno] == NOFREE);
2722
2723         /* the back split is accomplished by iteratively finding the leaf
2724          * that starts the buddy system that contains the specified leaf and
2725          * splitting that system in two.  this iteration continues until
2726          * the specified leaf becomes the start of a buddy system.
2727          *
2728          * determine maximum possible l2 size for the specified leaf.
2729          */
2730         size =
2731             LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs),
2732                       tp->dmt_budmin);
2733
2734         /* determine the number of leaves covered by this size.  this
2735          * is the buddy size that we will start with as we search for
2736          * the buddy system that contains the specified leaf.
2737          */
2738         budsz = BUDSIZE(size, tp->dmt_budmin);
2739
2740         /* back split.
2741          */
2742         while (leaf[leafno] == NOFREE) {
2743                 /* find the leftmost buddy leaf.
2744                  */
2745                 for (w = leafno, bsz = budsz;; bsz <<= 1,
2746                      w = (w < bud) ? w : bud) {
2747                         if (bsz >= le32_to_cpu(tp->dmt_nleafs)) {
2748                                 jfs_err("JFS: block map error in dbBackSplit");
2749                                 return -EIO;
2750                         }
2751
2752                         /* determine the buddy.
2753                          */
2754                         bud = w ^ bsz;
2755
2756                         /* check if this buddy is the start of the system.
2757                          */
2758                         if (leaf[bud] != NOFREE) {
2759                                 /* split the leaf at the start of the
2760                                  * system in two.
2761                                  */
2762                                 cursz = leaf[bud] - 1;
2763                                 dbSplit(tp, bud, cursz, cursz);
2764                                 break;
2765                         }
2766                 }
2767         }
2768
2769         if (leaf[leafno] != size) {
2770                 jfs_err("JFS: wrong leaf value in dbBackSplit");
2771                 return -EIO;
2772         }
2773         return 0;
2774 }
2775
2776
2777 /*
2778  * NAME:        dbJoin()
2779  *
2780  * FUNCTION:    update the leaf of a dmtree with a new value, joining
2781  *              the leaf with other leaves of the dmtree into a multi-leaf
2782  *              binary buddy system, as required.
2783  *
2784  * PARAMETERS:
2785  *      tp      - pointer to the tree containing the leaf.
2786  *      leafno  - the number of the leaf to be updated.
2787  *      newval  - the new value for the leaf.
2788  *
2789  * RETURN VALUES: none
2790  */
2791 static int dbJoin(dmtree_t * tp, int leafno, int newval)
2792 {
2793         int budsz, buddy;
2794         s8 *leaf;
2795
2796         /* can the new leaf value require a join with other leaves ?
2797          */
2798         if (newval >= tp->dmt_budmin) {
2799                 /* pickup a pointer to the leaves of the tree.
2800                  */
2801                 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2802
2803                 /* try to join the specified leaf into a large binary
2804                  * buddy system.  the join proceeds by attempting to join
2805                  * the specified leafno with its buddy (leaf) at new value.
2806                  * if the join occurs, we attempt to join the left leaf
2807                  * of the joined buddies with its buddy at new value + 1.
2808                  * we continue to join until we find a buddy that cannot be
2809                  * joined (does not have a value equal to the size of the
2810                  * last join) or until all leaves have been joined into a
2811                  * single system.
2812                  *
2813                  * get the buddy size (number of words covered) of
2814                  * the new value.
2815                  */
2816                 budsz = BUDSIZE(newval, tp->dmt_budmin);
2817
2818                 /* try to join.
2819                  */
2820                 while (budsz < le32_to_cpu(tp->dmt_nleafs)) {
2821                         /* get the buddy leaf.
2822                          */
2823                         buddy = leafno ^ budsz;
2824
2825                         /* if the leaf's new value is greater than its
2826                          * buddy's value, we join no more.
2827                          */
2828                         if (newval > leaf[buddy])
2829                                 break;
2830
2831                         /* It shouldn't be less */
2832                         if (newval < leaf[buddy])
2833                                 return -EIO;
2834
2835                         /* check which (leafno or buddy) is the left buddy.
2836                          * the left buddy gets to claim the blocks resulting
2837                          * from the join while the right gets to claim none.
2838                          * the left buddy is also eligible to participate in
2839                          * a join at the next higher level while the right
2840                          * is not.
2841                          *
2842                          */
2843                         if (leafno < buddy) {
2844                                 /* leafno is the left buddy.
2845                                  */
2846                                 dbAdjTree(tp, buddy, NOFREE);
2847                         } else {
2848                                 /* buddy is the left buddy and becomes
2849                                  * leafno.
2850                                  */
2851                                 dbAdjTree(tp, leafno, NOFREE);
2852                                 leafno = buddy;
2853                         }
2854
2855                         /* on to try the next join.
2856                          */
2857                         newval += 1;
2858                         budsz <<= 1;
2859                 }
2860         }
2861
2862         /* update the leaf value.
2863          */
2864         dbAdjTree(tp, leafno, newval);
2865
2866         return 0;
2867 }
2868
2869
2870 /*
2871  * NAME:        dbAdjTree()
2872  *
2873  * FUNCTION:    update a leaf of a dmtree with a new value, adjusting
2874  *              the dmtree, as required, to reflect the new leaf value.
2875  *              the combination of any buddies must already be done before
2876  *              this is called.
2877  *
2878  * PARAMETERS:
2879  *      tp      - pointer to the tree to be adjusted.
2880  *      leafno  - the number of the leaf to be updated.
2881  *      newval  - the new value for the leaf.
2882  *
2883  * RETURN VALUES: none
2884  */
2885 static void dbAdjTree(dmtree_t * tp, int leafno, int newval)
2886 {
2887         int lp, pp, k;
2888         int max;
2889
2890         /* pick up the index of the leaf for this leafno.
2891          */
2892         lp = leafno + le32_to_cpu(tp->dmt_leafidx);
2893
2894         /* is the current value the same as the old value ?  if so,
2895          * there is nothing to do.
2896          */
2897         if (tp->dmt_stree[lp] == newval)
2898                 return;
2899
2900         /* set the new value.
2901          */
2902         tp->dmt_stree[lp] = newval;
2903
2904         /* bubble the new value up the tree as required.
2905          */
2906         for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) {
2907                 /* get the index of the first leaf of the 4 leaf
2908                  * group containing the specified leaf (leafno).
2909                  */
2910                 lp = ((lp - 1) & ~0x03) + 1;
2911
2912                 /* get the index of the parent of this 4 leaf group.
2913                  */
2914                 pp = (lp - 1) >> 2;
2915
2916                 /* determine the maximum of the 4 leaves.
2917                  */
2918                 max = TREEMAX(&tp->dmt_stree[lp]);
2919
2920                 /* if the maximum of the 4 is the same as the
2921                  * parent's value, we're done.
2922                  */
2923                 if (tp->dmt_stree[pp] == max)
2924                         break;
2925
2926                 /* parent gets new value.
2927                  */
2928                 tp->dmt_stree[pp] = max;
2929
2930                 /* parent becomes leaf for next go-round.
2931                  */
2932                 lp = pp;
2933         }
2934 }
2935
2936
2937 /*
2938  * NAME:        dbFindLeaf()
2939  *
2940  * FUNCTION:    search a dmtree_t for sufficient free blocks, returning
2941  *              the index of a leaf describing the free blocks if
2942  *              sufficient free blocks are found.
2943  *
2944  *              the search starts at the top of the dmtree_t tree and
2945  *              proceeds down the tree to the leftmost leaf with sufficient
2946  *              free space.
2947  *
2948  * PARAMETERS:
2949  *      tp      - pointer to the tree to be searched.
2950  *      l2nb    - log2 number of free blocks to search for.
2951  *      leafidx - return pointer to be set to the index of the leaf
2952  *                describing at least l2nb free blocks if sufficient
2953  *                free blocks are found.
2954  *
2955  * RETURN VALUES:
2956  *      0       - success
2957  *      -ENOSPC - insufficient free blocks.
2958  */
2959 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx)
2960 {
2961         int ti, n = 0, k, x = 0;
2962
2963         /* first check the root of the tree to see if there is
2964          * sufficient free space.
2965          */
2966         if (l2nb > tp->dmt_stree[ROOT])
2967                 return -ENOSPC;
2968
2969         /* sufficient free space available. now search down the tree
2970          * starting at the next level for the leftmost leaf that
2971          * describes sufficient free space.
2972          */
2973         for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2974              k > 0; k--, ti = ((ti + n) << 2) + 1) {
2975                 /* search the four nodes at this level, starting from
2976                  * the left.
2977                  */
2978                 for (x = ti, n = 0; n < 4; n++) {
2979                         /* sufficient free space found.  move to the next
2980                          * level (or quit if this is the last level).
2981                          */
2982                         if (l2nb <= tp->dmt_stree[x + n])
2983                                 break;
2984                 }
2985
2986                 /* better have found something since the higher
2987                  * levels of the tree said it was here.
2988                  */
2989                 assert(n < 4);
2990         }
2991
2992         /* set the return to the leftmost leaf describing sufficient
2993          * free space.
2994          */
2995         *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
2996
2997         return (0);
2998 }
2999
3000
3001 /*
3002  * NAME:        dbFindBits()
3003  *
3004  * FUNCTION:    find a specified number of binary buddy free bits within a
3005  *              dmap bitmap word value.
3006  *
3007  *              this routine searches the bitmap value for (1 << l2nb) free
3008  *              bits at (1 << l2nb) alignments within the value.
3009  *
3010  * PARAMETERS:
3011  *      word    -  dmap bitmap word value.
3012  *      l2nb    -  number of free bits specified as a log2 number.
3013  *
3014  * RETURN VALUES:
3015  *      starting bit number of free bits.
3016  */
3017 static int dbFindBits(u32 word, int l2nb)
3018 {
3019         int bitno, nb;
3020         u32 mask;
3021
3022         /* get the number of bits.
3023          */
3024         nb = 1 << l2nb;
3025         assert(nb <= DBWORD);
3026
3027         /* complement the word so we can use a mask (i.e. 0s represent
3028          * free bits) and compute the mask.
3029          */
3030         word = ~word;
3031         mask = ONES << (DBWORD - nb);
3032
3033         /* scan the word for nb free bits at nb alignments.
3034          */
3035         for (bitno = 0; mask != 0; bitno += nb, mask >>= nb) {
3036                 if ((mask & word) == mask)
3037                         break;
3038         }
3039
3040         ASSERT(bitno < 32);
3041
3042         /* return the bit number.
3043          */
3044         return (bitno);
3045 }
3046
3047
3048 /*
3049  * NAME:        dbMaxBud(u8 *cp)
3050  *
3051  * FUNCTION:    determine the largest binary buddy string of free
3052  *              bits within 32-bits of the map.
3053  *
3054  * PARAMETERS:
3055  *      cp      -  pointer to the 32-bit value.
3056  *
3057  * RETURN VALUES:
3058  *      largest binary buddy of free bits within a dmap word.
3059  */
3060 static int dbMaxBud(u8 * cp)
3061 {
3062         signed char tmp1, tmp2;
3063
3064         /* check if the wmap word is all free. if so, the
3065          * free buddy size is BUDMIN.
3066          */
3067         if (*((uint *) cp) == 0)
3068                 return (BUDMIN);
3069
3070         /* check if the wmap word is half free. if so, the
3071          * free buddy size is BUDMIN-1.
3072          */
3073         if (*((u16 *) cp) == 0 || *((u16 *) cp + 1) == 0)
3074                 return (BUDMIN - 1);
3075
3076         /* not all free or half free. determine the free buddy
3077          * size thru table lookup using quarters of the wmap word.
3078          */
3079         tmp1 = max(budtab[cp[2]], budtab[cp[3]]);
3080         tmp2 = max(budtab[cp[0]], budtab[cp[1]]);
3081         return (max(tmp1, tmp2));
3082 }
3083
3084
3085 /*
3086  * NAME:        cnttz(uint word)
3087  *
3088  * FUNCTION:    determine the number of trailing zeros within a 32-bit
3089  *              value.
3090  *
3091  * PARAMETERS:
3092  *      value   -  32-bit value to be examined.
3093  *
3094  * RETURN VALUES:
3095  *      count of trailing zeros
3096  */
3097 static int cnttz(u32 word)
3098 {
3099         int n;
3100
3101         for (n = 0; n < 32; n++, word >>= 1) {
3102                 if (word & 0x01)
3103                         break;
3104         }
3105
3106         return (n);
3107 }
3108
3109
3110 /*
3111  * NAME:        cntlz(u32 value)
3112  *
3113  * FUNCTION:    determine the number of leading zeros within a 32-bit
3114  *              value.
3115  *
3116  * PARAMETERS:
3117  *      value   -  32-bit value to be examined.
3118  *
3119  * RETURN VALUES:
3120  *      count of leading zeros
3121  */
3122 static int cntlz(u32 value)
3123 {
3124         int n;
3125
3126         for (n = 0; n < 32; n++, value <<= 1) {
3127                 if (value & HIGHORDER)
3128                         break;
3129         }
3130         return (n);
3131 }
3132
3133
3134 /*
3135  * NAME:        blkstol2(s64 nb)
3136  *
3137  * FUNCTION:    convert a block count to its log2 value. if the block
3138  *              count is not a l2 multiple, it is rounded up to the next
3139  *              larger l2 multiple.
3140  *
3141  * PARAMETERS:
3142  *      nb      -  number of blocks
3143  *
3144  * RETURN VALUES:
3145  *      log2 number of blocks
3146  */
3147 static int blkstol2(s64 nb)
3148 {
3149         int l2nb;
3150         s64 mask;               /* meant to be signed */
3151
3152         mask = (s64) 1 << (64 - 1);
3153
3154         /* count the leading bits.
3155          */
3156         for (l2nb = 0; l2nb < 64; l2nb++, mask >>= 1) {
3157                 /* leading bit found.
3158                  */
3159                 if (nb & mask) {
3160                         /* determine the l2 value.
3161                          */
3162                         l2nb = (64 - 1) - l2nb;
3163
3164                         /* check if we need to round up.
3165                          */
3166                         if (~mask & nb)
3167                                 l2nb++;
3168
3169                         return (l2nb);
3170                 }
3171         }
3172         assert(0);
3173         return 0;               /* fix compiler warning */
3174 }
3175
3176
3177 /*
3178  * NAME:        dbAllocBottomUp()
3179  *
3180  * FUNCTION:    alloc the specified block range from the working block
3181  *              allocation map.
3182  *
3183  *              the blocks will be alloc from the working map one dmap
3184  *              at a time.
3185  *
3186  * PARAMETERS:
3187  *      ip      -  pointer to in-core inode;
3188  *      blkno   -  starting block number to be freed.
3189  *      nblocks -  number of blocks to be freed.
3190  *
3191  * RETURN VALUES:
3192  *      0       - success
3193  *      -EIO    - i/o error
3194  */
3195 int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks)
3196 {
3197         struct metapage *mp;
3198         struct dmap *dp;
3199         int nb, rc;
3200         s64 lblkno, rem;
3201         struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
3202         struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
3203
3204         IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
3205
3206         /* block to be allocated better be within the mapsize. */
3207         ASSERT(nblocks <= bmp->db_mapsize - blkno);
3208
3209         /*
3210          * allocate the blocks a dmap at a time.
3211          */
3212         mp = NULL;
3213         for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
3214                 /* release previous dmap if any */
3215                 if (mp) {
3216                         write_metapage(mp);
3217                 }
3218
3219                 /* get the buffer for the current dmap. */
3220                 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
3221                 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
3222                 if (mp == NULL) {
3223                         IREAD_UNLOCK(ipbmap);
3224                         return -EIO;
3225                 }
3226                 dp = (struct dmap *) mp->data;
3227
3228                 /* determine the number of blocks to be allocated from
3229                  * this dmap.
3230                  */
3231                 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
3232
3233                 /* allocate the blocks. */
3234                 if ((rc = dbAllocDmapBU(bmp, dp, blkno, nb))) {
3235                         release_metapage(mp);
3236                         IREAD_UNLOCK(ipbmap);
3237                         return (rc);
3238                 }
3239         }
3240
3241         /* write the last buffer. */
3242         write_metapage(mp);
3243
3244         IREAD_UNLOCK(ipbmap);
3245
3246         return (0);
3247 }
3248
3249
3250 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
3251                          int nblocks)
3252 {
3253         int rc;
3254         int dbitno, word, rembits, nb, nwords, wbitno, agno;
3255         s8 oldroot;
3256         struct dmaptree *tp = (struct dmaptree *) & dp->tree;
3257
3258         /* save the current value of the root (i.e. maximum free string)
3259          * of the dmap tree.
3260          */
3261         oldroot = tp->stree[ROOT];
3262
3263         /* determine the bit number and word within the dmap of the
3264          * starting block.
3265          */
3266         dbitno = blkno & (BPERDMAP - 1);
3267         word = dbitno >> L2DBWORD;
3268
3269         /* block range better be within the dmap */
3270         assert(dbitno + nblocks <= BPERDMAP);
3271
3272         /* allocate the bits of the dmap's words corresponding to the block
3273          * range. not all bits of the first and last words may be contained
3274          * within the block range.  if this is the case, we'll work against
3275          * those words (i.e. partial first and/or last) on an individual basis
3276          * (a single pass), allocating the bits of interest by hand and
3277          * updating the leaf corresponding to the dmap word. a single pass
3278          * will be used for all dmap words fully contained within the
3279          * specified range.  within this pass, the bits of all fully contained
3280          * dmap words will be marked as free in a single shot and the leaves
3281          * will be updated. a single leaf may describe the free space of
3282          * multiple dmap words, so we may update only a subset of the actual
3283          * leaves corresponding to the dmap words of the block range.
3284          */
3285         for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
3286                 /* determine the bit number within the word and
3287                  * the number of bits within the word.
3288                  */
3289                 wbitno = dbitno & (DBWORD - 1);
3290                 nb = min(rembits, DBWORD - wbitno);
3291
3292                 /* check if only part of a word is to be allocated.
3293                  */
3294                 if (nb < DBWORD) {
3295                         /* allocate (set to 1) the appropriate bits within
3296                          * this dmap word.
3297                          */
3298                         dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
3299                                                       >> wbitno);
3300
3301                         word++;
3302                 } else {
3303                         /* one or more dmap words are fully contained
3304                          * within the block range.  determine how many
3305                          * words and allocate (set to 1) the bits of these
3306                          * words.
3307                          */
3308                         nwords = rembits >> L2DBWORD;
3309                         memset(&dp->wmap[word], (int) ONES, nwords * 4);
3310
3311                         /* determine how many bits */
3312                         nb = nwords << L2DBWORD;
3313                         word += nwords;
3314                 }
3315         }
3316
3317         /* update the free count for this dmap */
3318         le32_add_cpu(&dp->nfree, -nblocks);
3319
3320         /* reconstruct summary tree */
3321         dbInitDmapTree(dp);
3322
3323         BMAP_LOCK(bmp);
3324
3325         /* if this allocation group is completely free,
3326          * update the highest active allocation group number
3327          * if this allocation group is the new max.
3328          */
3329         agno = blkno >> bmp->db_agl2size;
3330         if (agno > bmp->db_maxag)
3331                 bmp->db_maxag = agno;
3332
3333         /* update the free count for the allocation group and map */
3334         bmp->db_agfree[agno] -= nblocks;
3335         bmp->db_nfree -= nblocks;
3336
3337         BMAP_UNLOCK(bmp);
3338
3339         /* if the root has not changed, done. */
3340         if (tp->stree[ROOT] == oldroot)
3341                 return (0);
3342
3343         /* root changed. bubble the change up to the dmap control pages.
3344          * if the adjustment of the upper level control pages fails,
3345          * backout the bit allocation (thus making everything consistent).
3346          */
3347         if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0)))
3348                 dbFreeBits(bmp, dp, blkno, nblocks);
3349
3350         return (rc);
3351 }
3352
3353
3354 /*
3355  * NAME:        dbExtendFS()
3356  *
3357  * FUNCTION:    extend bmap from blkno for nblocks;
3358  *              dbExtendFS() updates bmap ready for dbAllocBottomUp();
3359  *
3360  * L2
3361  *  |
3362  *   L1---------------------------------L1
3363  *    |                                  |
3364  *     L0---------L0---------L0           L0---------L0---------L0
3365  *      |          |          |            |          |          |
3366  *       d0,...,dn  d0,...,dn  d0,...,dn    d0,...,dn  d0,...,dn  d0,.,dm;
3367  * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3368  *
3369  * <---old---><----------------------------extend----------------------->
3370  */
3371 int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks)
3372 {
3373         struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb);
3374         int nbperpage = sbi->nbperpage;
3375         int i, i0 = true, j, j0 = true, k, n;
3376         s64 newsize;
3377         s64 p;
3378         struct metapage *mp, *l2mp, *l1mp = NULL, *l0mp = NULL;
3379         struct dmapctl *l2dcp, *l1dcp, *l0dcp;
3380         struct dmap *dp;
3381         s8 *l0leaf, *l1leaf, *l2leaf;
3382         struct bmap *bmp = sbi->bmap;
3383         int agno, l2agsize, oldl2agsize;
3384         s64 ag_rem;
3385
3386         newsize = blkno + nblocks;
3387
3388         jfs_info("dbExtendFS: blkno:%Ld nblocks:%Ld newsize:%Ld",
3389                  (long long) blkno, (long long) nblocks, (long long) newsize);
3390
3391         /*
3392          *      initialize bmap control page.
3393          *
3394          * all the data in bmap control page should exclude
3395          * the mkfs hidden dmap page.
3396          */
3397
3398         /* update mapsize */
3399         bmp->db_mapsize = newsize;
3400         bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize);
3401
3402         /* compute new AG size */
3403         l2agsize = dbGetL2AGSize(newsize);
3404         oldl2agsize = bmp->db_agl2size;
3405
3406         bmp->db_agl2size = l2agsize;
3407         bmp->db_agsize = 1 << l2agsize;
3408
3409         /* compute new number of AG */
3410         agno = bmp->db_numag;
3411         bmp->db_numag = newsize >> l2agsize;
3412         bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0;
3413
3414         /*
3415          *      reconfigure db_agfree[]
3416          * from old AG configuration to new AG configuration;
3417          *
3418          * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3419          * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3420          * note: new AG size = old AG size * (2**x).
3421          */
3422         if (l2agsize == oldl2agsize)
3423                 goto extend;
3424         k = 1 << (l2agsize - oldl2agsize);
3425         ag_rem = bmp->db_agfree[0];     /* save agfree[0] */
3426         for (i = 0, n = 0; i < agno; n++) {
3427                 bmp->db_agfree[n] = 0;  /* init collection point */
3428
3429                 /* coalesce contiguous k AGs; */
3430                 for (j = 0; j < k && i < agno; j++, i++) {
3431                         /* merge AGi to AGn */
3432                         bmp->db_agfree[n] += bmp->db_agfree[i];
3433                 }
3434         }
3435         bmp->db_agfree[0] += ag_rem;    /* restore agfree[0] */
3436
3437         for (; n < MAXAG; n++)
3438                 bmp->db_agfree[n] = 0;
3439
3440         /*
3441          * update highest active ag number
3442          */
3443
3444         bmp->db_maxag = bmp->db_maxag / k;
3445
3446         /*
3447          *      extend bmap
3448          *
3449          * update bit maps and corresponding level control pages;
3450          * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3451          */
3452       extend:
3453         /* get L2 page */
3454         p = BMAPBLKNO + nbperpage;      /* L2 page */
3455         l2mp = read_metapage(ipbmap, p, PSIZE, 0);
3456         if (!l2mp) {
3457                 jfs_error(ipbmap->i_sb, "L2 page could not be read\n");
3458                 return -EIO;
3459         }
3460         l2dcp = (struct dmapctl *) l2mp->data;
3461
3462         /* compute start L1 */
3463         k = blkno >> L2MAXL1SIZE;
3464         l2leaf = l2dcp->stree + CTLLEAFIND + k;
3465         p = BLKTOL1(blkno, sbi->l2nbperpage);   /* L1 page */
3466
3467         /*
3468          * extend each L1 in L2
3469          */
3470         for (; k < LPERCTL; k++, p += nbperpage) {
3471                 /* get L1 page */
3472                 if (j0) {
3473                         /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3474                         l1mp = read_metapage(ipbmap, p, PSIZE, 0);
3475                         if (l1mp == NULL)
3476                                 goto errout;
3477                         l1dcp = (struct dmapctl *) l1mp->data;
3478
3479                         /* compute start L0 */
3480                         j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE;
3481                         l1leaf = l1dcp->stree + CTLLEAFIND + j;
3482                         p = BLKTOL0(blkno, sbi->l2nbperpage);
3483                         j0 = false;
3484                 } else {
3485                         /* assign/init L1 page */
3486                         l1mp = get_metapage(ipbmap, p, PSIZE, 0);
3487                         if (l1mp == NULL)
3488                                 goto errout;
3489
3490                         l1dcp = (struct dmapctl *) l1mp->data;
3491
3492                         /* compute start L0 */
3493                         j = 0;
3494                         l1leaf = l1dcp->stree + CTLLEAFIND;
3495                         p += nbperpage; /* 1st L0 of L1.k */
3496                 }
3497
3498                 /*
3499                  * extend each L0 in L1
3500                  */
3501                 for (; j < LPERCTL; j++) {
3502                         /* get L0 page */
3503                         if (i0) {
3504                                 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3505
3506                                 l0mp = read_metapage(ipbmap, p, PSIZE, 0);
3507                                 if (l0mp == NULL)
3508                                         goto errout;
3509                                 l0dcp = (struct dmapctl *) l0mp->data;
3510
3511                                 /* compute start dmap */
3512                                 i = (blkno & (MAXL0SIZE - 1)) >>
3513                                     L2BPERDMAP;
3514                                 l0leaf = l0dcp->stree + CTLLEAFIND + i;
3515                                 p = BLKTODMAP(blkno,
3516                                               sbi->l2nbperpage);
3517                                 i0 = false;
3518                         } else {
3519                                 /* assign/init L0 page */
3520                                 l0mp = get_metapage(ipbmap, p, PSIZE, 0);
3521                                 if (l0mp == NULL)
3522                                         goto errout;
3523
3524                                 l0dcp = (struct dmapctl *) l0mp->data;
3525
3526                                 /* compute start dmap */
3527                                 i = 0;
3528                                 l0leaf = l0dcp->stree + CTLLEAFIND;
3529                                 p += nbperpage; /* 1st dmap of L0.j */
3530                         }
3531
3532                         /*
3533                          * extend each dmap in L0
3534                          */
3535                         for (; i < LPERCTL; i++) {
3536                                 /*
3537                                  * reconstruct the dmap page, and
3538                                  * initialize corresponding parent L0 leaf
3539                                  */
3540                                 if ((n = blkno & (BPERDMAP - 1))) {
3541                                         /* read in dmap page: */
3542                                         mp = read_metapage(ipbmap, p,
3543                                                            PSIZE, 0);
3544                                         if (mp == NULL)
3545                                                 goto errout;
3546                                         n = min(nblocks, (s64)BPERDMAP - n);
3547                                 } else {
3548                                         /* assign/init dmap page */
3549                                         mp = read_metapage(ipbmap, p,
3550                                                            PSIZE, 0);
3551                                         if (mp == NULL)
3552                                                 goto errout;
3553
3554                                         n = min_t(s64, nblocks, BPERDMAP);
3555                                 }
3556
3557                                 dp = (struct dmap *) mp->data;
3558                                 *l0leaf = dbInitDmap(dp, blkno, n);
3559
3560                                 bmp->db_nfree += n;
3561                                 agno = le64_to_cpu(dp->start) >> l2agsize;
3562                                 bmp->db_agfree[agno] += n;
3563
3564                                 write_metapage(mp);
3565
3566                                 l0leaf++;
3567                                 p += nbperpage;
3568
3569                                 blkno += n;
3570                                 nblocks -= n;
3571                                 if (nblocks == 0)
3572                                         break;
3573                         }       /* for each dmap in a L0 */
3574
3575                         /*
3576                          * build current L0 page from its leaves, and
3577                          * initialize corresponding parent L1 leaf
3578                          */
3579                         *l1leaf = dbInitDmapCtl(l0dcp, 0, ++i);
3580                         write_metapage(l0mp);
3581                         l0mp = NULL;
3582
3583                         if (nblocks)
3584                                 l1leaf++;       /* continue for next L0 */
3585                         else {
3586                                 /* more than 1 L0 ? */
3587                                 if (j > 0)
3588                                         break;  /* build L1 page */
3589                                 else {
3590                                         /* summarize in global bmap page */
3591                                         bmp->db_maxfreebud = *l1leaf;
3592                                         release_metapage(l1mp);
3593                                         release_metapage(l2mp);
3594                                         goto finalize;
3595                                 }
3596                         }
3597                 }               /* for each L0 in a L1 */
3598
3599                 /*
3600                  * build current L1 page from its leaves, and
3601                  * initialize corresponding parent L2 leaf
3602                  */
3603                 *l2leaf = dbInitDmapCtl(l1dcp, 1, ++j);
3604                 write_metapage(l1mp);
3605                 l1mp = NULL;
3606
3607                 if (nblocks)
3608                         l2leaf++;       /* continue for next L1 */
3609                 else {
3610                         /* more than 1 L1 ? */
3611                         if (k > 0)
3612                                 break;  /* build L2 page */
3613                         else {
3614                                 /* summarize in global bmap page */
3615                                 bmp->db_maxfreebud = *l2leaf;
3616                                 release_metapage(l2mp);
3617                                 goto finalize;
3618                         }
3619                 }
3620         }                       /* for each L1 in a L2 */
3621
3622         jfs_error(ipbmap->i_sb, "function has not returned as expected\n");
3623 errout:
3624         if (l0mp)
3625                 release_metapage(l0mp);
3626         if (l1mp)
3627                 release_metapage(l1mp);
3628         release_metapage(l2mp);
3629         return -EIO;
3630
3631         /*
3632          *      finalize bmap control page
3633          */
3634 finalize:
3635
3636         return 0;
3637 }
3638
3639
3640 /*
3641  *      dbFinalizeBmap()
3642  */
3643 void dbFinalizeBmap(struct inode *ipbmap)
3644 {
3645         struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
3646         int actags, inactags, l2nl;
3647         s64 ag_rem, actfree, inactfree, avgfree;
3648         int i, n;
3649
3650         /*
3651          *      finalize bmap control page
3652          */
3653 //finalize:
3654         /*
3655          * compute db_agpref: preferred ag to allocate from
3656          * (the leftmost ag with average free space in it);
3657          */
3658 //agpref:
3659         /* get the number of active ags and inacitve ags */
3660         actags = bmp->db_maxag + 1;
3661         inactags = bmp->db_numag - actags;
3662         ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1);        /* ??? */
3663
3664         /* determine how many blocks are in the inactive allocation
3665          * groups. in doing this, we must account for the fact that
3666          * the rightmost group might be a partial group (i.e. file
3667          * system size is not a multiple of the group size).
3668          */
3669         inactfree = (inactags && ag_rem) ?
3670             ((inactags - 1) << bmp->db_agl2size) + ag_rem
3671             : inactags << bmp->db_agl2size;
3672
3673         /* determine how many free blocks are in the active
3674          * allocation groups plus the average number of free blocks
3675          * within the active ags.
3676          */
3677         actfree = bmp->db_nfree - inactfree;
3678         avgfree = (u32) actfree / (u32) actags;
3679
3680         /* if the preferred allocation group has not average free space.
3681          * re-establish the preferred group as the leftmost
3682          * group with average free space.
3683          */
3684         if (bmp->db_agfree[bmp->db_agpref] < avgfree) {
3685                 for (bmp->db_agpref = 0; bmp->db_agpref < actags;
3686                      bmp->db_agpref++) {
3687                         if (bmp->db_agfree[bmp->db_agpref] >= avgfree)
3688                                 break;
3689                 }
3690                 if (bmp->db_agpref >= bmp->db_numag) {
3691                         jfs_error(ipbmap->i_sb,
3692                                   "cannot find ag with average freespace\n");
3693                 }
3694         }
3695
3696         /*
3697          * compute db_aglevel, db_agheight, db_width, db_agstart:
3698          * an ag is covered in aglevel dmapctl summary tree,
3699          * at agheight level height (from leaf) with agwidth number of nodes
3700          * each, which starts at agstart index node of the smmary tree node
3701          * array;
3702          */
3703         bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize);
3704         l2nl =
3705             bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL);
3706         bmp->db_agheight = l2nl >> 1;
3707         bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1));
3708         for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0;
3709              i--) {
3710                 bmp->db_agstart += n;
3711                 n <<= 2;
3712         }
3713
3714 }
3715
3716
3717 /*
3718  * NAME:        dbInitDmap()/ujfs_idmap_page()
3719  *
3720  * FUNCTION:    initialize working/persistent bitmap of the dmap page
3721  *              for the specified number of blocks:
3722  *
3723  *              at entry, the bitmaps had been initialized as free (ZEROS);
3724  *              The number of blocks will only account for the actually
3725  *              existing blocks. Blocks which don't actually exist in
3726  *              the aggregate will be marked as allocated (ONES);
3727  *
3728  * PARAMETERS:
3729  *      dp      - pointer to page of map
3730  *      nblocks - number of blocks this page
3731  *
3732  * RETURNS: NONE
3733  */
3734 static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks)
3735 {
3736         int blkno, w, b, r, nw, nb, i;
3737
3738         /* starting block number within the dmap */
3739         blkno = Blkno & (BPERDMAP - 1);
3740
3741         if (blkno == 0) {
3742                 dp->nblocks = dp->nfree = cpu_to_le32(nblocks);
3743                 dp->start = cpu_to_le64(Blkno);
3744
3745                 if (nblocks == BPERDMAP) {
3746                         memset(&dp->wmap[0], 0, LPERDMAP * 4);
3747                         memset(&dp->pmap[0], 0, LPERDMAP * 4);
3748                         goto initTree;
3749                 }
3750         } else {
3751                 le32_add_cpu(&dp->nblocks, nblocks);
3752                 le32_add_cpu(&dp->nfree, nblocks);
3753         }
3754
3755         /* word number containing start block number */
3756         w = blkno >> L2DBWORD;
3757
3758         /*
3759          * free the bits corresponding to the block range (ZEROS):
3760          * note: not all bits of the first and last words may be contained
3761          * within the block range.
3762          */
3763         for (r = nblocks; r > 0; r -= nb, blkno += nb) {
3764                 /* number of bits preceding range to be freed in the word */
3765                 b = blkno & (DBWORD - 1);
3766                 /* number of bits to free in the word */
3767                 nb = min(r, DBWORD - b);
3768
3769                 /* is partial word to be freed ? */
3770                 if (nb < DBWORD) {
3771                         /* free (set to 0) from the bitmap word */
3772                         dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3773                                                      >> b));
3774                         dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3775                                                      >> b));
3776
3777                         /* skip the word freed */
3778                         w++;
3779                 } else {
3780                         /* free (set to 0) contiguous bitmap words */
3781                         nw = r >> L2DBWORD;
3782                         memset(&dp->wmap[w], 0, nw * 4);
3783                         memset(&dp->pmap[w], 0, nw * 4);
3784
3785                         /* skip the words freed */
3786                         nb = nw << L2DBWORD;
3787                         w += nw;
3788                 }
3789         }
3790
3791         /*
3792          * mark bits following the range to be freed (non-existing
3793          * blocks) as allocated (ONES)
3794          */
3795
3796         if (blkno == BPERDMAP)
3797                 goto initTree;
3798
3799         /* the first word beyond the end of existing blocks */
3800         w = blkno >> L2DBWORD;
3801
3802         /* does nblocks fall on a 32-bit boundary ? */
3803         b = blkno & (DBWORD - 1);
3804         if (b) {
3805                 /* mark a partial word allocated */
3806                 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b);
3807                 w++;
3808         }
3809
3810         /* set the rest of the words in the page to allocated (ONES) */
3811         for (i = w; i < LPERDMAP; i++)
3812                 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES);
3813
3814         /*
3815          * init tree
3816          */
3817       initTree:
3818         return (dbInitDmapTree(dp));
3819 }
3820
3821
3822 /*
3823  * NAME:        dbInitDmapTree()/ujfs_complete_dmap()
3824  *
3825  * FUNCTION:    initialize summary tree of the specified dmap:
3826  *
3827  *              at entry, bitmap of the dmap has been initialized;
3828  *
3829  * PARAMETERS:
3830  *      dp      - dmap to complete
3831  *      blkno   - starting block number for this dmap
3832  *      treemax - will be filled in with max free for this dmap
3833  *
3834  * RETURNS:     max free string at the root of the tree
3835  */
3836 static int dbInitDmapTree(struct dmap * dp)
3837 {
3838         struct dmaptree *tp;
3839         s8 *cp;
3840         int i;
3841
3842         /* init fixed info of tree */
3843         tp = &dp->tree;
3844         tp->nleafs = cpu_to_le32(LPERDMAP);
3845         tp->l2nleafs = cpu_to_le32(L2LPERDMAP);
3846         tp->leafidx = cpu_to_le32(LEAFIND);
3847         tp->height = cpu_to_le32(4);
3848         tp->budmin = BUDMIN;
3849
3850         /* init each leaf from corresponding wmap word:
3851          * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3852          * bitmap word are allocated.
3853          */
3854         cp = tp->stree + le32_to_cpu(tp->leafidx);
3855         for (i = 0; i < LPERDMAP; i++)
3856                 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]);
3857
3858         /* build the dmap's binary buddy summary tree */
3859         return (dbInitTree(tp));
3860 }
3861
3862
3863 /*
3864  * NAME:        dbInitTree()/ujfs_adjtree()
3865  *
3866  * FUNCTION:    initialize binary buddy summary tree of a dmap or dmapctl.
3867  *
3868  *              at entry, the leaves of the tree has been initialized
3869  *              from corresponding bitmap word or root of summary tree
3870  *              of the child control page;
3871  *              configure binary buddy system at the leaf level, then
3872  *              bubble up the values of the leaf nodes up the tree.
3873  *
3874  * PARAMETERS:
3875  *      cp      - Pointer to the root of the tree
3876  *      l2leaves- Number of leaf nodes as a power of 2
3877  *      l2min   - Number of blocks that can be covered by a leaf
3878  *                as a power of 2
3879  *
3880  * RETURNS: max free string at the root of the tree
3881  */
3882 static int dbInitTree(struct dmaptree * dtp)
3883 {
3884         int l2max, l2free, bsize, nextb, i;
3885         int child, parent, nparent;
3886         s8 *tp, *cp, *cp1;
3887
3888         tp = dtp->stree;
3889
3890         /* Determine the maximum free string possible for the leaves */
3891         l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin;
3892
3893         /*
3894          * configure the leaf levevl into binary buddy system
3895          *
3896          * Try to combine buddies starting with a buddy size of 1
3897          * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3898          * can be combined if both buddies have a maximum free of l2min;
3899          * the combination will result in the left-most buddy leaf having
3900          * a maximum free of l2min+1.
3901          * After processing all buddies for a given size, process buddies
3902          * at the next higher buddy size (i.e. current size * 2) and
3903          * the next maximum free (current free + 1).
3904          * This continues until the maximum possible buddy combination
3905          * yields maximum free.
3906          */
3907         for (l2free = dtp->budmin, bsize = 1; l2free < l2max;
3908              l2free++, bsize = nextb) {
3909                 /* get next buddy size == current buddy pair size */
3910                 nextb = bsize << 1;
3911
3912                 /* scan each adjacent buddy pair at current buddy size */
3913                 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx);
3914                      i < le32_to_cpu(dtp->nleafs);
3915                      i += nextb, cp += nextb) {
3916                         /* coalesce if both adjacent buddies are max free */
3917                         if (*cp == l2free && *(cp + bsize) == l2free) {
3918                                 *cp = l2free + 1;       /* left take right */
3919                                 *(cp + bsize) = -1;     /* right give left */
3920                         }
3921                 }
3922         }
3923
3924         /*
3925          * bubble summary information of leaves up the tree.
3926          *
3927          * Starting at the leaf node level, the four nodes described by
3928          * the higher level parent node are compared for a maximum free and
3929          * this maximum becomes the value of the parent node.
3930          * when all lower level nodes are processed in this fashion then
3931          * move up to the next level (parent becomes a lower level node) and
3932          * continue the process for that level.
3933          */
3934         for (child = le32_to_cpu(dtp->leafidx),
3935              nparent = le32_to_cpu(dtp->nleafs) >> 2;
3936              nparent > 0; nparent >>= 2, child = parent) {
3937                 /* get index of 1st node of parent level */
3938                 parent = (child - 1) >> 2;
3939
3940                 /* set the value of the parent node as the maximum
3941                  * of the four nodes of the current level.
3942                  */
3943                 for (i = 0, cp = tp + child, cp1 = tp + parent;
3944                      i < nparent; i++, cp += 4, cp1++)
3945                         *cp1 = TREEMAX(cp);
3946         }
3947
3948         return (*tp);
3949 }
3950
3951
3952 /*
3953  *      dbInitDmapCtl()
3954  *
3955  * function: initialize dmapctl page
3956  */
3957 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i)
3958 {                               /* start leaf index not covered by range */
3959         s8 *cp;
3960
3961         dcp->nleafs = cpu_to_le32(LPERCTL);
3962         dcp->l2nleafs = cpu_to_le32(L2LPERCTL);
3963         dcp->leafidx = cpu_to_le32(CTLLEAFIND);
3964         dcp->height = cpu_to_le32(5);
3965         dcp->budmin = L2BPERDMAP + L2LPERCTL * level;
3966
3967         /*
3968          * initialize the leaves of current level that were not covered
3969          * by the specified input block range (i.e. the leaves have no
3970          * low level dmapctl or dmap).
3971          */
3972         cp = &dcp->stree[CTLLEAFIND + i];
3973         for (; i < LPERCTL; i++)
3974                 *cp++ = NOFREE;
3975
3976         /* build the dmap's binary buddy summary tree */
3977         return (dbInitTree((struct dmaptree *) dcp));
3978 }
3979
3980
3981 /*
3982  * NAME:        dbGetL2AGSize()/ujfs_getagl2size()
3983  *
3984  * FUNCTION:    Determine log2(allocation group size) from aggregate size
3985  *
3986  * PARAMETERS:
3987  *      nblocks - Number of blocks in aggregate
3988  *
3989  * RETURNS: log2(allocation group size) in aggregate blocks
3990  */
3991 static int dbGetL2AGSize(s64 nblocks)
3992 {
3993         s64 sz;
3994         s64 m;
3995         int l2sz;
3996
3997         if (nblocks < BPERDMAP * MAXAG)
3998                 return (L2BPERDMAP);
3999
4000         /* round up aggregate size to power of 2 */
4001         m = ((u64) 1 << (64 - 1));
4002         for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) {
4003                 if (m & nblocks)
4004                         break;
4005         }
4006
4007         sz = (s64) 1 << l2sz;
4008         if (sz < nblocks)
4009                 l2sz += 1;
4010
4011         /* agsize = roundupSize/max_number_of_ag */
4012         return (l2sz - L2MAXAG);
4013 }
4014
4015
4016 /*
4017  * NAME:        dbMapFileSizeToMapSize()
4018  *
4019  * FUNCTION:    compute number of blocks the block allocation map file
4020  *              can cover from the map file size;
4021  *
4022  * RETURNS:     Number of blocks which can be covered by this block map file;
4023  */
4024
4025 /*
4026  * maximum number of map pages at each level including control pages
4027  */
4028 #define MAXL0PAGES      (1 + LPERCTL)
4029 #define MAXL1PAGES      (1 + LPERCTL * MAXL0PAGES)
4030
4031 /*
4032  * convert number of map pages to the zero origin top dmapctl level
4033  */
4034 #define BMAPPGTOLEV(npages)     \
4035         (((npages) <= 3 + MAXL0PAGES) ? 0 : \
4036          ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4037
4038 s64 dbMapFileSizeToMapSize(struct inode * ipbmap)
4039 {
4040         struct super_block *sb = ipbmap->i_sb;
4041         s64 nblocks;
4042         s64 npages, ndmaps;
4043         int level, i;
4044         int complete, factor;
4045
4046         nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize;
4047         npages = nblocks >> JFS_SBI(sb)->l2nbperpage;
4048         level = BMAPPGTOLEV(npages);
4049
4050         /* At each level, accumulate the number of dmap pages covered by
4051          * the number of full child levels below it;
4052          * repeat for the last incomplete child level.
4053          */
4054         ndmaps = 0;
4055         npages--;               /* skip the first global control page */
4056         /* skip higher level control pages above top level covered by map */
4057         npages -= (2 - level);
4058         npages--;               /* skip top level's control page */
4059         for (i = level; i >= 0; i--) {
4060                 factor =
4061                     (i == 2) ? MAXL1PAGES : ((i == 1) ? MAXL0PAGES : 1);
4062                 complete = (u32) npages / factor;
4063                 ndmaps += complete * ((i == 2) ? LPERCTL * LPERCTL :
4064                                       ((i == 1) ? LPERCTL : 1));
4065
4066                 /* pages in last/incomplete child */
4067                 npages = (u32) npages % factor;
4068                 /* skip incomplete child's level control page */
4069                 npages--;
4070         }
4071
4072         /* convert the number of dmaps into the number of blocks
4073          * which can be covered by the dmaps;
4074          */
4075         nblocks = ndmaps << L2BPERDMAP;
4076
4077         return (nblocks);
4078 }