fs/jfs/jfs_dmap.c

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