fs/jfs/jfs_dmap.c

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