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