fs/jfs/jfs_dmap.c

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