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