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