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