linux/fs/jfs/jfs_xtree.c
<<
>>
Prefs
   1/*
   2 *   Copyright (C) International Business Machines Corp., 2000-2005
   3 *
   4 *   This program is free software;  you can redistribute it and/or modify
   5 *   it under the terms of the GNU General Public License as published by
   6 *   the Free Software Foundation; either version 2 of the License, or
   7 *   (at your option) any later version.
   8 *
   9 *   This program is distributed in the hope that it will be useful,
  10 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
  11 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
  12 *   the GNU General Public License for more details.
  13 *
  14 *   You should have received a copy of the GNU General Public License
  15 *   along with this program;  if not, write to the Free Software
  16 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  17 */
  18/*
  19 *      jfs_xtree.c: extent allocation descriptor B+-tree manager
  20 */
  21
  22#include <linux/fs.h>
  23#include <linux/module.h>
  24#include <linux/quotaops.h>
  25#include <linux/seq_file.h>
  26#include "jfs_incore.h"
  27#include "jfs_filsys.h"
  28#include "jfs_metapage.h"
  29#include "jfs_dmap.h"
  30#include "jfs_dinode.h"
  31#include "jfs_superblock.h"
  32#include "jfs_debug.h"
  33
  34/*
  35 * xtree local flag
  36 */
  37#define XT_INSERT       0x00000001
  38
  39/*
  40 *      xtree key/entry comparison: extent offset
  41 *
  42 * return:
  43 *      -1: k < start of extent
  44 *       0: start_of_extent <= k <= end_of_extent
  45 *       1: k > end_of_extent
  46 */
  47#define XT_CMP(CMP, K, X, OFFSET64)\
  48{\
  49        OFFSET64 = offsetXAD(X);\
  50        (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
  51                ((K) < OFFSET64) ? -1 : 0;\
  52}
  53
  54/* write a xad entry */
  55#define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
  56{\
  57        (XAD)->flag = (FLAG);\
  58        XADoffset((XAD), (OFF));\
  59        XADlength((XAD), (LEN));\
  60        XADaddress((XAD), (ADDR));\
  61}
  62
  63#define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
  64
  65/* get page buffer for specified block address */
  66/* ToDo: Replace this ugly macro with a function */
  67#define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)                             \
  68do {                                                                    \
  69        BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot);        \
  70        if (!(RC)) {                                                    \
  71                if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) || \
  72                    (le16_to_cpu((P)->header.nextindex) >               \
  73                     le16_to_cpu((P)->header.maxentry)) ||              \
  74                    (le16_to_cpu((P)->header.maxentry) >                \
  75                     (((BN) == 0) ? XTROOTMAXSLOT : PSIZE >> L2XTSLOTSIZE))) { \
  76                        jfs_error((IP)->i_sb,                           \
  77                                  "XT_GETPAGE: xtree page corrupt\n");  \
  78                        BT_PUTPAGE(MP);                                 \
  79                        MP = NULL;                                      \
  80                        RC = -EIO;                                      \
  81                }                                                       \
  82        }                                                               \
  83} while (0)
  84
  85/* for consistency */
  86#define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
  87
  88#define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
  89        BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
  90/* xtree entry parameter descriptor */
  91struct xtsplit {
  92        struct metapage *mp;
  93        s16 index;
  94        u8 flag;
  95        s64 off;
  96        s64 addr;
  97        int len;
  98        struct pxdlist *pxdlist;
  99};
 100
 101
 102/*
 103 *      statistics
 104 */
 105#ifdef CONFIG_JFS_STATISTICS
 106static struct {
 107        uint search;
 108        uint fastSearch;
 109        uint split;
 110} xtStat;
 111#endif
 112
 113
 114/*
 115 * forward references
 116 */
 117static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
 118                    struct btstack * btstack, int flag);
 119
 120static int xtSplitUp(tid_t tid,
 121                     struct inode *ip,
 122                     struct xtsplit * split, struct btstack * btstack);
 123
 124static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
 125                       struct metapage ** rmpp, s64 * rbnp);
 126
 127static int xtSplitRoot(tid_t tid, struct inode *ip,
 128                       struct xtsplit * split, struct metapage ** rmpp);
 129
 130#ifdef _STILL_TO_PORT
 131static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
 132                      xtpage_t * fp, struct btstack * btstack);
 133
 134static int xtSearchNode(struct inode *ip,
 135                        xad_t * xad,
 136                        int *cmpp, struct btstack * btstack, int flag);
 137
 138static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
 139#endif                          /*  _STILL_TO_PORT */
 140
 141/*
 142 *      xtLookup()
 143 *
 144 * function: map a single page into a physical extent;
 145 */
 146int xtLookup(struct inode *ip, s64 lstart,
 147             s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
 148{
 149        int rc = 0;
 150        struct btstack btstack;
 151        int cmp;
 152        s64 bn;
 153        struct metapage *mp;
 154        xtpage_t *p;
 155        int index;
 156        xad_t *xad;
 157        s64 next, size, xoff, xend;
 158        int xlen;
 159        s64 xaddr;
 160
 161        *paddr = 0;
 162        *plen = llen;
 163
 164        if (!no_check) {
 165                /* is lookup offset beyond eof ? */
 166                size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
 167                    JFS_SBI(ip->i_sb)->l2bsize;
 168                if (lstart >= size)
 169                        return 0;
 170        }
 171
 172        /*
 173         * search for the xad entry covering the logical extent
 174         */
 175//search:
 176        if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
 177                jfs_err("xtLookup: xtSearch returned %d", rc);
 178                return rc;
 179        }
 180
 181        /*
 182         *      compute the physical extent covering logical extent
 183         *
 184         * N.B. search may have failed (e.g., hole in sparse file),
 185         * and returned the index of the next entry.
 186         */
 187        /* retrieve search result */
 188        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
 189
 190        /* is xad found covering start of logical extent ?
 191         * lstart is a page start address,
 192         * i.e., lstart cannot start in a hole;
 193         */
 194        if (cmp) {
 195                if (next)
 196                        *plen = min(next - lstart, llen);
 197                goto out;
 198        }
 199
 200        /*
 201         * lxd covered by xad
 202         */
 203        xad = &p->xad[index];
 204        xoff = offsetXAD(xad);
 205        xlen = lengthXAD(xad);
 206        xend = xoff + xlen;
 207        xaddr = addressXAD(xad);
 208
 209        /* initialize new pxd */
 210        *pflag = xad->flag;
 211        *paddr = xaddr + (lstart - xoff);
 212        /* a page must be fully covered by an xad */
 213        *plen = min(xend - lstart, llen);
 214
 215      out:
 216        XT_PUTPAGE(mp);
 217
 218        return rc;
 219}
 220
 221/*
 222 *      xtSearch()
 223 *
 224 * function:    search for the xad entry covering specified offset.
 225 *
 226 * parameters:
 227 *      ip      - file object;
 228 *      xoff    - extent offset;
 229 *      nextp   - address of next extent (if any) for search miss
 230 *      cmpp    - comparison result:
 231 *      btstack - traverse stack;
 232 *      flag    - search process flag (XT_INSERT);
 233 *
 234 * returns:
 235 *      btstack contains (bn, index) of search path traversed to the entry.
 236 *      *cmpp is set to result of comparison with the entry returned.
 237 *      the page containing the entry is pinned at exit.
 238 */
 239static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
 240                    int *cmpp, struct btstack * btstack, int flag)
 241{
 242        struct jfs_inode_info *jfs_ip = JFS_IP(ip);
 243        int rc = 0;
 244        int cmp = 1;            /* init for empty page */
 245        s64 bn;                 /* block number */
 246        struct metapage *mp;    /* page buffer */
 247        xtpage_t *p;            /* page */
 248        xad_t *xad;
 249        int base, index, lim, btindex;
 250        struct btframe *btsp;
 251        int nsplit = 0;         /* number of pages to split */
 252        s64 t64;
 253        s64 next = 0;
 254
 255        INCREMENT(xtStat.search);
 256
 257        BT_CLR(btstack);
 258
 259        btstack->nsplit = 0;
 260
 261        /*
 262         *      search down tree from root:
 263         *
 264         * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
 265         * internal page, child page Pi contains entry with k, Ki <= K < Kj.
 266         *
 267         * if entry with search key K is not found
 268         * internal page search find the entry with largest key Ki
 269         * less than K which point to the child page to search;
 270         * leaf page search find the entry with smallest key Kj
 271         * greater than K so that the returned index is the position of
 272         * the entry to be shifted right for insertion of new entry.
 273         * for empty tree, search key is greater than any key of the tree.
 274         *
 275         * by convention, root bn = 0.
 276         */
 277        for (bn = 0;;) {
 278                /* get/pin the page to search */
 279                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
 280                if (rc)
 281                        return rc;
 282
 283                /* try sequential access heuristics with the previous
 284                 * access entry in target leaf page:
 285                 * once search narrowed down into the target leaf,
 286                 * key must either match an entry in the leaf or
 287                 * key entry does not exist in the tree;
 288                 */
 289//fastSearch:
 290                if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
 291                    (p->header.flag & BT_LEAF) &&
 292                    (index = jfs_ip->btindex) <
 293                    le16_to_cpu(p->header.nextindex)) {
 294                        xad = &p->xad[index];
 295                        t64 = offsetXAD(xad);
 296                        if (xoff < t64 + lengthXAD(xad)) {
 297                                if (xoff >= t64) {
 298                                        *cmpp = 0;
 299                                        goto out;
 300                                }
 301
 302                                /* stop sequential access heuristics */
 303                                goto binarySearch;
 304                        } else {        /* (t64 + lengthXAD(xad)) <= xoff */
 305
 306                                /* try next sequential entry */
 307                                index++;
 308                                if (index <
 309                                    le16_to_cpu(p->header.nextindex)) {
 310                                        xad++;
 311                                        t64 = offsetXAD(xad);
 312                                        if (xoff < t64 + lengthXAD(xad)) {
 313                                                if (xoff >= t64) {
 314                                                        *cmpp = 0;
 315                                                        goto out;
 316                                                }
 317
 318                                                /* miss: key falls between
 319                                                 * previous and this entry
 320                                                 */
 321                                                *cmpp = 1;
 322                                                next = t64;
 323                                                goto out;
 324                                        }
 325
 326                                        /* (xoff >= t64 + lengthXAD(xad));
 327                                         * matching entry may be further out:
 328                                         * stop heuristic search
 329                                         */
 330                                        /* stop sequential access heuristics */
 331                                        goto binarySearch;
 332                                }
 333
 334                                /* (index == p->header.nextindex);
 335                                 * miss: key entry does not exist in
 336                                 * the target leaf/tree
 337                                 */
 338                                *cmpp = 1;
 339                                goto out;
 340                        }
 341
 342                        /*
 343                         * if hit, return index of the entry found, and
 344                         * if miss, where new entry with search key is
 345                         * to be inserted;
 346                         */
 347                      out:
 348                        /* compute number of pages to split */
 349                        if (flag & XT_INSERT) {
 350                                if (p->header.nextindex ==      /* little-endian */
 351                                    p->header.maxentry)
 352                                        nsplit++;
 353                                else
 354                                        nsplit = 0;
 355                                btstack->nsplit = nsplit;
 356                        }
 357
 358                        /* save search result */
 359                        btsp = btstack->top;
 360                        btsp->bn = bn;
 361                        btsp->index = index;
 362                        btsp->mp = mp;
 363
 364                        /* update sequential access heuristics */
 365                        jfs_ip->btindex = index;
 366
 367                        if (nextp)
 368                                *nextp = next;
 369
 370                        INCREMENT(xtStat.fastSearch);
 371                        return 0;
 372                }
 373
 374                /* well, ... full search now */
 375              binarySearch:
 376                lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
 377
 378                /*
 379                 * binary search with search key K on the current page
 380                 */
 381                for (base = XTENTRYSTART; lim; lim >>= 1) {
 382                        index = base + (lim >> 1);
 383
 384                        XT_CMP(cmp, xoff, &p->xad[index], t64);
 385                        if (cmp == 0) {
 386                                /*
 387                                 *      search hit
 388                                 */
 389                                /* search hit - leaf page:
 390                                 * return the entry found
 391                                 */
 392                                if (p->header.flag & BT_LEAF) {
 393                                        *cmpp = cmp;
 394
 395                                        /* compute number of pages to split */
 396                                        if (flag & XT_INSERT) {
 397                                                if (p->header.nextindex ==
 398                                                    p->header.maxentry)
 399                                                        nsplit++;
 400                                                else
 401                                                        nsplit = 0;
 402                                                btstack->nsplit = nsplit;
 403                                        }
 404
 405                                        /* save search result */
 406                                        btsp = btstack->top;
 407                                        btsp->bn = bn;
 408                                        btsp->index = index;
 409                                        btsp->mp = mp;
 410
 411                                        /* init sequential access heuristics */
 412                                        btindex = jfs_ip->btindex;
 413                                        if (index == btindex ||
 414                                            index == btindex + 1)
 415                                                jfs_ip->btorder = BT_SEQUENTIAL;
 416                                        else
 417                                                jfs_ip->btorder = BT_RANDOM;
 418                                        jfs_ip->btindex = index;
 419
 420                                        return 0;
 421                                }
 422                                /* search hit - internal page:
 423                                 * descend/search its child page
 424                                 */
 425                                if (index < le16_to_cpu(p->header.nextindex)-1)
 426                                        next = offsetXAD(&p->xad[index + 1]);
 427                                goto next;
 428                        }
 429
 430                        if (cmp > 0) {
 431                                base = index + 1;
 432                                --lim;
 433                        }
 434                }
 435
 436                /*
 437                 *      search miss
 438                 *
 439                 * base is the smallest index with key (Kj) greater than
 440                 * search key (K) and may be zero or maxentry index.
 441                 */
 442                if (base < le16_to_cpu(p->header.nextindex))
 443                        next = offsetXAD(&p->xad[base]);
 444                /*
 445                 * search miss - leaf page:
 446                 *
 447                 * return location of entry (base) where new entry with
 448                 * search key K is to be inserted.
 449                 */
 450                if (p->header.flag & BT_LEAF) {
 451                        *cmpp = cmp;
 452
 453                        /* compute number of pages to split */
 454                        if (flag & XT_INSERT) {
 455                                if (p->header.nextindex ==
 456                                    p->header.maxentry)
 457                                        nsplit++;
 458                                else
 459                                        nsplit = 0;
 460                                btstack->nsplit = nsplit;
 461                        }
 462
 463                        /* save search result */
 464                        btsp = btstack->top;
 465                        btsp->bn = bn;
 466                        btsp->index = base;
 467                        btsp->mp = mp;
 468
 469                        /* init sequential access heuristics */
 470                        btindex = jfs_ip->btindex;
 471                        if (base == btindex || base == btindex + 1)
 472                                jfs_ip->btorder = BT_SEQUENTIAL;
 473                        else
 474                                jfs_ip->btorder = BT_RANDOM;
 475                        jfs_ip->btindex = base;
 476
 477                        if (nextp)
 478                                *nextp = next;
 479
 480                        return 0;
 481                }
 482
 483                /*
 484                 * search miss - non-leaf page:
 485                 *
 486                 * if base is non-zero, decrement base by one to get the parent
 487                 * entry of the child page to search.
 488                 */
 489                index = base ? base - 1 : base;
 490
 491                /*
 492                 * go down to child page
 493                 */
 494              next:
 495                /* update number of pages to split */
 496                if (p->header.nextindex == p->header.maxentry)
 497                        nsplit++;
 498                else
 499                        nsplit = 0;
 500
 501                /* push (bn, index) of the parent page/entry */
 502                if (BT_STACK_FULL(btstack)) {
 503                        jfs_error(ip->i_sb, "stack overrun!\n");
 504                        XT_PUTPAGE(mp);
 505                        return -EIO;
 506                }
 507                BT_PUSH(btstack, bn, index);
 508
 509                /* get the child page block number */
 510                bn = addressXAD(&p->xad[index]);
 511
 512                /* unpin the parent page */
 513                XT_PUTPAGE(mp);
 514        }
 515}
 516
 517/*
 518 *      xtInsert()
 519 *
 520 * function:
 521 *
 522 * parameter:
 523 *      tid     - transaction id;
 524 *      ip      - file object;
 525 *      xflag   - extent flag (XAD_NOTRECORDED):
 526 *      xoff    - extent offset;
 527 *      xlen    - extent length;
 528 *      xaddrp  - extent address pointer (in/out):
 529 *              if (*xaddrp)
 530 *                      caller allocated data extent at *xaddrp;
 531 *              else
 532 *                      allocate data extent and return its xaddr;
 533 *      flag    -
 534 *
 535 * return:
 536 */
 537int xtInsert(tid_t tid,         /* transaction id */
 538             struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
 539             int flag)
 540{
 541        int rc = 0;
 542        s64 xaddr, hint;
 543        struct metapage *mp;    /* meta-page buffer */
 544        xtpage_t *p;            /* base B+-tree index page */
 545        s64 bn;
 546        int index, nextindex;
 547        struct btstack btstack; /* traverse stack */
 548        struct xtsplit split;   /* split information */
 549        xad_t *xad;
 550        int cmp;
 551        s64 next;
 552        struct tlock *tlck;
 553        struct xtlock *xtlck;
 554
 555        jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
 556
 557        /*
 558         *      search for the entry location at which to insert:
 559         *
 560         * xtFastSearch() and xtSearch() both returns (leaf page
 561         * pinned, index at which to insert).
 562         * n.b. xtSearch() may return index of maxentry of
 563         * the full page.
 564         */
 565        if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
 566                return rc;
 567
 568        /* retrieve search result */
 569        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
 570
 571        /* This test must follow XT_GETSEARCH since mp must be valid if
 572         * we branch to out: */
 573        if ((cmp == 0) || (next && (xlen > next - xoff))) {
 574                rc = -EEXIST;
 575                goto out;
 576        }
 577
 578        /*
 579         * allocate data extent requested
 580         *
 581         * allocation hint: last xad
 582         */
 583        if ((xaddr = *xaddrp) == 0) {
 584                if (index > XTENTRYSTART) {
 585                        xad = &p->xad[index - 1];
 586                        hint = addressXAD(xad) + lengthXAD(xad) - 1;
 587                } else
 588                        hint = 0;
 589                if ((rc = dquot_alloc_block(ip, xlen)))
 590                        goto out;
 591                if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
 592                        dquot_free_block(ip, xlen);
 593                        goto out;
 594                }
 595        }
 596
 597        /*
 598         *      insert entry for new extent
 599         */
 600        xflag |= XAD_NEW;
 601
 602        /*
 603         *      if the leaf page is full, split the page and
 604         *      propagate up the router entry for the new page from split
 605         *
 606         * The xtSplitUp() will insert the entry and unpin the leaf page.
 607         */
 608        nextindex = le16_to_cpu(p->header.nextindex);
 609        if (nextindex == le16_to_cpu(p->header.maxentry)) {
 610                split.mp = mp;
 611                split.index = index;
 612                split.flag = xflag;
 613                split.off = xoff;
 614                split.len = xlen;
 615                split.addr = xaddr;
 616                split.pxdlist = NULL;
 617                if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
 618                        /* undo data extent allocation */
 619                        if (*xaddrp == 0) {
 620                                dbFree(ip, xaddr, (s64) xlen);
 621                                dquot_free_block(ip, xlen);
 622                        }
 623                        return rc;
 624                }
 625
 626                *xaddrp = xaddr;
 627                return 0;
 628        }
 629
 630        /*
 631         *      insert the new entry into the leaf page
 632         */
 633        /*
 634         * acquire a transaction lock on the leaf page;
 635         *
 636         * action: xad insertion/extension;
 637         */
 638        BT_MARK_DIRTY(mp, ip);
 639
 640        /* if insert into middle, shift right remaining entries. */
 641        if (index < nextindex)
 642                memmove(&p->xad[index + 1], &p->xad[index],
 643                        (nextindex - index) * sizeof(xad_t));
 644
 645        /* insert the new entry: mark the entry NEW */
 646        xad = &p->xad[index];
 647        XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
 648
 649        /* advance next available entry index */
 650        le16_add_cpu(&p->header.nextindex, 1);
 651
 652        /* Don't log it if there are no links to the file */
 653        if (!test_cflag(COMMIT_Nolink, ip)) {
 654                tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
 655                xtlck = (struct xtlock *) & tlck->lock;
 656                xtlck->lwm.offset =
 657                    (xtlck->lwm.offset) ? min(index,
 658                                              (int)xtlck->lwm.offset) : index;
 659                xtlck->lwm.length =
 660                    le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
 661        }
 662
 663        *xaddrp = xaddr;
 664
 665      out:
 666        /* unpin the leaf page */
 667        XT_PUTPAGE(mp);
 668
 669        return rc;
 670}
 671
 672
 673/*
 674 *      xtSplitUp()
 675 *
 676 * function:
 677 *      split full pages as propagating insertion up the tree
 678 *
 679 * parameter:
 680 *      tid     - transaction id;
 681 *      ip      - file object;
 682 *      split   - entry parameter descriptor;
 683 *      btstack - traverse stack from xtSearch()
 684 *
 685 * return:
 686 */
 687static int
 688xtSplitUp(tid_t tid,
 689          struct inode *ip, struct xtsplit * split, struct btstack * btstack)
 690{
 691        int rc = 0;
 692        struct metapage *smp;
 693        xtpage_t *sp;           /* split page */
 694        struct metapage *rmp;
 695        s64 rbn;                /* new right page block number */
 696        struct metapage *rcmp;
 697        xtpage_t *rcp;          /* right child page */
 698        s64 rcbn;               /* right child page block number */
 699        int skip;               /* index of entry of insertion */
 700        int nextindex;          /* next available entry index of p */
 701        struct btframe *parent; /* parent page entry on traverse stack */
 702        xad_t *xad;
 703        s64 xaddr;
 704        int xlen;
 705        int nsplit;             /* number of pages split */
 706        struct pxdlist pxdlist;
 707        pxd_t *pxd;
 708        struct tlock *tlck;
 709        struct xtlock *xtlck;
 710
 711        smp = split->mp;
 712        sp = XT_PAGE(ip, smp);
 713
 714        /* is inode xtree root extension/inline EA area free ? */
 715        if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
 716            (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
 717            (JFS_IP(ip)->mode2 & INLINEEA)) {
 718                sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
 719                JFS_IP(ip)->mode2 &= ~INLINEEA;
 720
 721                BT_MARK_DIRTY(smp, ip);
 722                /*
 723                 * acquire a transaction lock on the leaf page;
 724                 *
 725                 * action: xad insertion/extension;
 726                 */
 727
 728                /* if insert into middle, shift right remaining entries. */
 729                skip = split->index;
 730                nextindex = le16_to_cpu(sp->header.nextindex);
 731                if (skip < nextindex)
 732                        memmove(&sp->xad[skip + 1], &sp->xad[skip],
 733                                (nextindex - skip) * sizeof(xad_t));
 734
 735                /* insert the new entry: mark the entry NEW */
 736                xad = &sp->xad[skip];
 737                XT_PUTENTRY(xad, split->flag, split->off, split->len,
 738                            split->addr);
 739
 740                /* advance next available entry index */
 741                le16_add_cpu(&sp->header.nextindex, 1);
 742
 743                /* Don't log it if there are no links to the file */
 744                if (!test_cflag(COMMIT_Nolink, ip)) {
 745                        tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
 746                        xtlck = (struct xtlock *) & tlck->lock;
 747                        xtlck->lwm.offset = (xtlck->lwm.offset) ?
 748                            min(skip, (int)xtlck->lwm.offset) : skip;
 749                        xtlck->lwm.length =
 750                            le16_to_cpu(sp->header.nextindex) -
 751                            xtlck->lwm.offset;
 752                }
 753
 754                return 0;
 755        }
 756
 757        /*
 758         * allocate new index blocks to cover index page split(s)
 759         *
 760         * allocation hint: ?
 761         */
 762        if (split->pxdlist == NULL) {
 763                nsplit = btstack->nsplit;
 764                split->pxdlist = &pxdlist;
 765                pxdlist.maxnpxd = pxdlist.npxd = 0;
 766                pxd = &pxdlist.pxd[0];
 767                xlen = JFS_SBI(ip->i_sb)->nbperpage;
 768                for (; nsplit > 0; nsplit--, pxd++) {
 769                        if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
 770                            == 0) {
 771                                PXDaddress(pxd, xaddr);
 772                                PXDlength(pxd, xlen);
 773
 774                                pxdlist.maxnpxd++;
 775
 776                                continue;
 777                        }
 778
 779                        /* undo allocation */
 780
 781                        XT_PUTPAGE(smp);
 782                        return rc;
 783                }
 784        }
 785
 786        /*
 787         * Split leaf page <sp> into <sp> and a new right page <rp>.
 788         *
 789         * The split routines insert the new entry into the leaf page,
 790         * and acquire txLock as appropriate.
 791         * return <rp> pinned and its block number <rpbn>.
 792         */
 793        rc = (sp->header.flag & BT_ROOT) ?
 794            xtSplitRoot(tid, ip, split, &rmp) :
 795            xtSplitPage(tid, ip, split, &rmp, &rbn);
 796
 797        XT_PUTPAGE(smp);
 798
 799        if (rc)
 800                return -EIO;
 801        /*
 802         * propagate up the router entry for the leaf page just split
 803         *
 804         * insert a router entry for the new page into the parent page,
 805         * propagate the insert/split up the tree by walking back the stack
 806         * of (bn of parent page, index of child page entry in parent page)
 807         * that were traversed during the search for the page that split.
 808         *
 809         * the propagation of insert/split up the tree stops if the root
 810         * splits or the page inserted into doesn't have to split to hold
 811         * the new entry.
 812         *
 813         * the parent entry for the split page remains the same, and
 814         * a new entry is inserted at its right with the first key and
 815         * block number of the new right page.
 816         *
 817         * There are a maximum of 3 pages pinned at any time:
 818         * right child, left parent and right parent (when the parent splits)
 819         * to keep the child page pinned while working on the parent.
 820         * make sure that all pins are released at exit.
 821         */
 822        while ((parent = BT_POP(btstack)) != NULL) {
 823                /* parent page specified by stack frame <parent> */
 824
 825                /* keep current child pages <rcp> pinned */
 826                rcmp = rmp;
 827                rcbn = rbn;
 828                rcp = XT_PAGE(ip, rcmp);
 829
 830                /*
 831                 * insert router entry in parent for new right child page <rp>
 832                 */
 833                /* get/pin the parent page <sp> */
 834                XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
 835                if (rc) {
 836                        XT_PUTPAGE(rcmp);
 837                        return rc;
 838                }
 839
 840                /*
 841                 * The new key entry goes ONE AFTER the index of parent entry,
 842                 * because the split was to the right.
 843                 */
 844                skip = parent->index + 1;
 845
 846                /*
 847                 * split or shift right remaining entries of the parent page
 848                 */
 849                nextindex = le16_to_cpu(sp->header.nextindex);
 850                /*
 851                 * parent page is full - split the parent page
 852                 */
 853                if (nextindex == le16_to_cpu(sp->header.maxentry)) {
 854                        /* init for parent page split */
 855                        split->mp = smp;
 856                        split->index = skip;    /* index at insert */
 857                        split->flag = XAD_NEW;
 858                        split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
 859                        split->len = JFS_SBI(ip->i_sb)->nbperpage;
 860                        split->addr = rcbn;
 861
 862                        /* unpin previous right child page */
 863                        XT_PUTPAGE(rcmp);
 864
 865                        /* The split routines insert the new entry,
 866                         * and acquire txLock as appropriate.
 867                         * return <rp> pinned and its block number <rpbn>.
 868                         */
 869                        rc = (sp->header.flag & BT_ROOT) ?
 870                            xtSplitRoot(tid, ip, split, &rmp) :
 871                            xtSplitPage(tid, ip, split, &rmp, &rbn);
 872                        if (rc) {
 873                                XT_PUTPAGE(smp);
 874                                return rc;
 875                        }
 876
 877                        XT_PUTPAGE(smp);
 878                        /* keep new child page <rp> pinned */
 879                }
 880                /*
 881                 * parent page is not full - insert in parent page
 882                 */
 883                else {
 884                        /*
 885                         * insert router entry in parent for the right child
 886                         * page from the first entry of the right child page:
 887                         */
 888                        /*
 889                         * acquire a transaction lock on the parent page;
 890                         *
 891                         * action: router xad insertion;
 892                         */
 893                        BT_MARK_DIRTY(smp, ip);
 894
 895                        /*
 896                         * if insert into middle, shift right remaining entries
 897                         */
 898                        if (skip < nextindex)
 899                                memmove(&sp->xad[skip + 1], &sp->xad[skip],
 900                                        (nextindex -
 901                                         skip) << L2XTSLOTSIZE);
 902
 903                        /* insert the router entry */
 904                        xad = &sp->xad[skip];
 905                        XT_PUTENTRY(xad, XAD_NEW,
 906                                    offsetXAD(&rcp->xad[XTENTRYSTART]),
 907                                    JFS_SBI(ip->i_sb)->nbperpage, rcbn);
 908
 909                        /* advance next available entry index. */
 910                        le16_add_cpu(&sp->header.nextindex, 1);
 911
 912                        /* Don't log it if there are no links to the file */
 913                        if (!test_cflag(COMMIT_Nolink, ip)) {
 914                                tlck = txLock(tid, ip, smp,
 915                                              tlckXTREE | tlckGROW);
 916                                xtlck = (struct xtlock *) & tlck->lock;
 917                                xtlck->lwm.offset = (xtlck->lwm.offset) ?
 918                                    min(skip, (int)xtlck->lwm.offset) : skip;
 919                                xtlck->lwm.length =
 920                                    le16_to_cpu(sp->header.nextindex) -
 921                                    xtlck->lwm.offset;
 922                        }
 923
 924                        /* unpin parent page */
 925                        XT_PUTPAGE(smp);
 926
 927                        /* exit propagate up */
 928                        break;
 929                }
 930        }
 931
 932        /* unpin current right page */
 933        XT_PUTPAGE(rmp);
 934
 935        return 0;
 936}
 937
 938
 939/*
 940 *      xtSplitPage()
 941 *
 942 * function:
 943 *      split a full non-root page into
 944 *      original/split/left page and new right page
 945 *      i.e., the original/split page remains as left page.
 946 *
 947 * parameter:
 948 *      int             tid,
 949 *      struct inode    *ip,
 950 *      struct xtsplit  *split,
 951 *      struct metapage **rmpp,
 952 *      u64             *rbnp,
 953 *
 954 * return:
 955 *      Pointer to page in which to insert or NULL on error.
 956 */
 957static int
 958xtSplitPage(tid_t tid, struct inode *ip,
 959            struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
 960{
 961        int rc = 0;
 962        struct metapage *smp;
 963        xtpage_t *sp;
 964        struct metapage *rmp;
 965        xtpage_t *rp;           /* new right page allocated */
 966        s64 rbn;                /* new right page block number */
 967        struct metapage *mp;
 968        xtpage_t *p;
 969        s64 nextbn;
 970        int skip, maxentry, middle, righthalf, n;
 971        xad_t *xad;
 972        struct pxdlist *pxdlist;
 973        pxd_t *pxd;
 974        struct tlock *tlck;
 975        struct xtlock *sxtlck = NULL, *rxtlck = NULL;
 976        int quota_allocation = 0;
 977
 978        smp = split->mp;
 979        sp = XT_PAGE(ip, smp);
 980
 981        INCREMENT(xtStat.split);
 982
 983        pxdlist = split->pxdlist;
 984        pxd = &pxdlist->pxd[pxdlist->npxd];
 985        pxdlist->npxd++;
 986        rbn = addressPXD(pxd);
 987
 988        /* Allocate blocks to quota. */
 989        rc = dquot_alloc_block(ip, lengthPXD(pxd));
 990        if (rc)
 991                goto clean_up;
 992
 993        quota_allocation += lengthPXD(pxd);
 994
 995        /*
 996         * allocate the new right page for the split
 997         */
 998        rmp = get_metapage(ip, rbn, PSIZE, 1);
 999        if (rmp == NULL) {
1000                rc = -EIO;
1001                goto clean_up;
1002        }
1003
1004        jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1005
1006        BT_MARK_DIRTY(rmp, ip);
1007        /*
1008         * action: new page;
1009         */
1010
1011        rp = (xtpage_t *) rmp->data;
1012        rp->header.self = *pxd;
1013        rp->header.flag = sp->header.flag & BT_TYPE;
1014        rp->header.maxentry = sp->header.maxentry;      /* little-endian */
1015        rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1016
1017        BT_MARK_DIRTY(smp, ip);
1018        /* Don't log it if there are no links to the file */
1019        if (!test_cflag(COMMIT_Nolink, ip)) {
1020                /*
1021                 * acquire a transaction lock on the new right page;
1022                 */
1023                tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1024                rxtlck = (struct xtlock *) & tlck->lock;
1025                rxtlck->lwm.offset = XTENTRYSTART;
1026                /*
1027                 * acquire a transaction lock on the split page
1028                 */
1029                tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1030                sxtlck = (struct xtlock *) & tlck->lock;
1031        }
1032
1033        /*
1034         * initialize/update sibling pointers of <sp> and <rp>
1035         */
1036        nextbn = le64_to_cpu(sp->header.next);
1037        rp->header.next = cpu_to_le64(nextbn);
1038        rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1039        sp->header.next = cpu_to_le64(rbn);
1040
1041        skip = split->index;
1042
1043        /*
1044         *      sequential append at tail (after last entry of last page)
1045         *
1046         * if splitting the last page on a level because of appending
1047         * a entry to it (skip is maxentry), it's likely that the access is
1048         * sequential. adding an empty page on the side of the level is less
1049         * work and can push the fill factor much higher than normal.
1050         * if we're wrong it's no big deal -  we will do the split the right
1051         * way next time.
1052         * (it may look like it's equally easy to do a similar hack for
1053         * reverse sorted data, that is, split the tree left, but it's not.
1054         * Be my guest.)
1055         */
1056        if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1057                /*
1058                 * acquire a transaction lock on the new/right page;
1059                 *
1060                 * action: xad insertion;
1061                 */
1062                /* insert entry at the first entry of the new right page */
1063                xad = &rp->xad[XTENTRYSTART];
1064                XT_PUTENTRY(xad, split->flag, split->off, split->len,
1065                            split->addr);
1066
1067                rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1068
1069                if (!test_cflag(COMMIT_Nolink, ip)) {
1070                        /* rxtlck->lwm.offset = XTENTRYSTART; */
1071                        rxtlck->lwm.length = 1;
1072                }
1073
1074                *rmpp = rmp;
1075                *rbnp = rbn;
1076
1077                jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1078                return 0;
1079        }
1080
1081        /*
1082         *      non-sequential insert (at possibly middle page)
1083         */
1084
1085        /*
1086         * update previous pointer of old next/right page of <sp>
1087         */
1088        if (nextbn != 0) {
1089                XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1090                if (rc) {
1091                        XT_PUTPAGE(rmp);
1092                        goto clean_up;
1093                }
1094
1095                BT_MARK_DIRTY(mp, ip);
1096                /*
1097                 * acquire a transaction lock on the next page;
1098                 *
1099                 * action:sibling pointer update;
1100                 */
1101                if (!test_cflag(COMMIT_Nolink, ip))
1102                        tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1103
1104                p->header.prev = cpu_to_le64(rbn);
1105
1106                /* sibling page may have been updated previously, or
1107                 * it may be updated later;
1108                 */
1109
1110                XT_PUTPAGE(mp);
1111        }
1112
1113        /*
1114         * split the data between the split and new/right pages
1115         */
1116        maxentry = le16_to_cpu(sp->header.maxentry);
1117        middle = maxentry >> 1;
1118        righthalf = maxentry - middle;
1119
1120        /*
1121         * skip index in old split/left page - insert into left page:
1122         */
1123        if (skip <= middle) {
1124                /* move right half of split page to the new right page */
1125                memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1126                        righthalf << L2XTSLOTSIZE);
1127
1128                /* shift right tail of left half to make room for new entry */
1129                if (skip < middle)
1130                        memmove(&sp->xad[skip + 1], &sp->xad[skip],
1131                                (middle - skip) << L2XTSLOTSIZE);
1132
1133                /* insert new entry */
1134                xad = &sp->xad[skip];
1135                XT_PUTENTRY(xad, split->flag, split->off, split->len,
1136                            split->addr);
1137
1138                /* update page header */
1139                sp->header.nextindex = cpu_to_le16(middle + 1);
1140                if (!test_cflag(COMMIT_Nolink, ip)) {
1141                        sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1142                            min(skip, (int)sxtlck->lwm.offset) : skip;
1143                }
1144
1145                rp->header.nextindex =
1146                    cpu_to_le16(XTENTRYSTART + righthalf);
1147        }
1148        /*
1149         * skip index in new right page - insert into right page:
1150         */
1151        else {
1152                /* move left head of right half to right page */
1153                n = skip - middle;
1154                memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1155                        n << L2XTSLOTSIZE);
1156
1157                /* insert new entry */
1158                n += XTENTRYSTART;
1159                xad = &rp->xad[n];
1160                XT_PUTENTRY(xad, split->flag, split->off, split->len,
1161                            split->addr);
1162
1163                /* move right tail of right half to right page */
1164                if (skip < maxentry)
1165                        memmove(&rp->xad[n + 1], &sp->xad[skip],
1166                                (maxentry - skip) << L2XTSLOTSIZE);
1167
1168                /* update page header */
1169                sp->header.nextindex = cpu_to_le16(middle);
1170                if (!test_cflag(COMMIT_Nolink, ip)) {
1171                        sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1172                            min(middle, (int)sxtlck->lwm.offset) : middle;
1173                }
1174
1175                rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1176                                                   righthalf + 1);
1177        }
1178
1179        if (!test_cflag(COMMIT_Nolink, ip)) {
1180                sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1181                    sxtlck->lwm.offset;
1182
1183                /* rxtlck->lwm.offset = XTENTRYSTART; */
1184                rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1185                    XTENTRYSTART;
1186        }
1187
1188        *rmpp = rmp;
1189        *rbnp = rbn;
1190
1191        jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1192        return rc;
1193
1194      clean_up:
1195
1196        /* Rollback quota allocation. */
1197        if (quota_allocation)
1198                dquot_free_block(ip, quota_allocation);
1199
1200        return (rc);
1201}
1202
1203
1204/*
1205 *      xtSplitRoot()
1206 *
1207 * function:
1208 *      split the full root page into original/root/split page and new
1209 *      right page
1210 *      i.e., root remains fixed in tree anchor (inode) and the root is
1211 *      copied to a single new right child page since root page <<
1212 *      non-root page, and the split root page contains a single entry
1213 *      for the new right child page.
1214 *
1215 * parameter:
1216 *      int             tid,
1217 *      struct inode    *ip,
1218 *      struct xtsplit  *split,
1219 *      struct metapage **rmpp)
1220 *
1221 * return:
1222 *      Pointer to page in which to insert or NULL on error.
1223 */
1224static int
1225xtSplitRoot(tid_t tid,
1226            struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1227{
1228        xtpage_t *sp;
1229        struct metapage *rmp;
1230        xtpage_t *rp;
1231        s64 rbn;
1232        int skip, nextindex;
1233        xad_t *xad;
1234        pxd_t *pxd;
1235        struct pxdlist *pxdlist;
1236        struct tlock *tlck;
1237        struct xtlock *xtlck;
1238        int rc;
1239
1240        sp = &JFS_IP(ip)->i_xtroot;
1241
1242        INCREMENT(xtStat.split);
1243
1244        /*
1245         *      allocate a single (right) child page
1246         */
1247        pxdlist = split->pxdlist;
1248        pxd = &pxdlist->pxd[pxdlist->npxd];
1249        pxdlist->npxd++;
1250        rbn = addressPXD(pxd);
1251        rmp = get_metapage(ip, rbn, PSIZE, 1);
1252        if (rmp == NULL)
1253                return -EIO;
1254
1255        /* Allocate blocks to quota. */
1256        rc = dquot_alloc_block(ip, lengthPXD(pxd));
1257        if (rc) {
1258                release_metapage(rmp);
1259                return rc;
1260        }
1261
1262        jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1263
1264        /*
1265         * acquire a transaction lock on the new right page;
1266         *
1267         * action: new page;
1268         */
1269        BT_MARK_DIRTY(rmp, ip);
1270
1271        rp = (xtpage_t *) rmp->data;
1272        rp->header.flag =
1273            (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1274        rp->header.self = *pxd;
1275        rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1276        rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1277
1278        /* initialize sibling pointers */
1279        rp->header.next = 0;
1280        rp->header.prev = 0;
1281
1282        /*
1283         * copy the in-line root page into new right page extent
1284         */
1285        nextindex = le16_to_cpu(sp->header.maxentry);
1286        memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1287                (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1288
1289        /*
1290         * insert the new entry into the new right/child page
1291         * (skip index in the new right page will not change)
1292         */
1293        skip = split->index;
1294        /* if insert into middle, shift right remaining entries */
1295        if (skip != nextindex)
1296                memmove(&rp->xad[skip + 1], &rp->xad[skip],
1297                        (nextindex - skip) * sizeof(xad_t));
1298
1299        xad = &rp->xad[skip];
1300        XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1301
1302        /* update page header */
1303        rp->header.nextindex = cpu_to_le16(nextindex + 1);
1304
1305        if (!test_cflag(COMMIT_Nolink, ip)) {
1306                tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1307                xtlck = (struct xtlock *) & tlck->lock;
1308                xtlck->lwm.offset = XTENTRYSTART;
1309                xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1310                    XTENTRYSTART;
1311        }
1312
1313        /*
1314         *      reset the root
1315         *
1316         * init root with the single entry for the new right page
1317         * set the 1st entry offset to 0, which force the left-most key
1318         * at any level of the tree to be less than any search key.
1319         */
1320        /*
1321         * acquire a transaction lock on the root page (in-memory inode);
1322         *
1323         * action: root split;
1324         */
1325        BT_MARK_DIRTY(split->mp, ip);
1326
1327        xad = &sp->xad[XTENTRYSTART];
1328        XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1329
1330        /* update page header of root */
1331        sp->header.flag &= ~BT_LEAF;
1332        sp->header.flag |= BT_INTERNAL;
1333
1334        sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1335
1336        if (!test_cflag(COMMIT_Nolink, ip)) {
1337                tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1338                xtlck = (struct xtlock *) & tlck->lock;
1339                xtlck->lwm.offset = XTENTRYSTART;
1340                xtlck->lwm.length = 1;
1341        }
1342
1343        *rmpp = rmp;
1344
1345        jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1346        return 0;
1347}
1348
1349
1350/*
1351 *      xtExtend()
1352 *
1353 * function: extend in-place;
1354 *
1355 * note: existing extent may or may not have been committed.
1356 * caller is responsible for pager buffer cache update, and
1357 * working block allocation map update;
1358 * update pmap: alloc whole extended extent;
1359 */
1360int xtExtend(tid_t tid,         /* transaction id */
1361             struct inode *ip, s64 xoff,        /* delta extent offset */
1362             s32 xlen,          /* delta extent length */
1363             int flag)
1364{
1365        int rc = 0;
1366        int cmp;
1367        struct metapage *mp;    /* meta-page buffer */
1368        xtpage_t *p;            /* base B+-tree index page */
1369        s64 bn;
1370        int index, nextindex, len;
1371        struct btstack btstack; /* traverse stack */
1372        struct xtsplit split;   /* split information */
1373        xad_t *xad;
1374        s64 xaddr;
1375        struct tlock *tlck;
1376        struct xtlock *xtlck = NULL;
1377
1378        jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1379
1380        /* there must exist extent to be extended */
1381        if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1382                return rc;
1383
1384        /* retrieve search result */
1385        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1386
1387        if (cmp != 0) {
1388                XT_PUTPAGE(mp);
1389                jfs_error(ip->i_sb, "xtSearch did not find extent\n");
1390                return -EIO;
1391        }
1392
1393        /* extension must be contiguous */
1394        xad = &p->xad[index];
1395        if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1396                XT_PUTPAGE(mp);
1397                jfs_error(ip->i_sb, "extension is not contiguous\n");
1398                return -EIO;
1399        }
1400
1401        /*
1402         * acquire a transaction lock on the leaf page;
1403         *
1404         * action: xad insertion/extension;
1405         */
1406        BT_MARK_DIRTY(mp, ip);
1407        if (!test_cflag(COMMIT_Nolink, ip)) {
1408                tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1409                xtlck = (struct xtlock *) & tlck->lock;
1410        }
1411
1412        /* extend will overflow extent ? */
1413        xlen = lengthXAD(xad) + xlen;
1414        if ((len = xlen - MAXXLEN) <= 0)
1415                goto extendOld;
1416
1417        /*
1418         *      extent overflow: insert entry for new extent
1419         */
1420//insertNew:
1421        xoff = offsetXAD(xad) + MAXXLEN;
1422        xaddr = addressXAD(xad) + MAXXLEN;
1423        nextindex = le16_to_cpu(p->header.nextindex);
1424
1425        /*
1426         *      if the leaf page is full, insert the new entry and
1427         *      propagate up the router entry for the new page from split
1428         *
1429         * The xtSplitUp() will insert the entry and unpin the leaf page.
1430         */
1431        if (nextindex == le16_to_cpu(p->header.maxentry)) {
1432                /* xtSpliUp() unpins leaf pages */
1433                split.mp = mp;
1434                split.index = index + 1;
1435                split.flag = XAD_NEW;
1436                split.off = xoff;       /* split offset */
1437                split.len = len;
1438                split.addr = xaddr;
1439                split.pxdlist = NULL;
1440                if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1441                        return rc;
1442
1443                /* get back old page */
1444                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1445                if (rc)
1446                        return rc;
1447                /*
1448                 * if leaf root has been split, original root has been
1449                 * copied to new child page, i.e., original entry now
1450                 * resides on the new child page;
1451                 */
1452                if (p->header.flag & BT_INTERNAL) {
1453                        ASSERT(p->header.nextindex ==
1454                               cpu_to_le16(XTENTRYSTART + 1));
1455                        xad = &p->xad[XTENTRYSTART];
1456                        bn = addressXAD(xad);
1457                        XT_PUTPAGE(mp);
1458
1459                        /* get new child page */
1460                        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1461                        if (rc)
1462                                return rc;
1463
1464                        BT_MARK_DIRTY(mp, ip);
1465                        if (!test_cflag(COMMIT_Nolink, ip)) {
1466                                tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1467                                xtlck = (struct xtlock *) & tlck->lock;
1468                        }
1469                }
1470        }
1471        /*
1472         *      insert the new entry into the leaf page
1473         */
1474        else {
1475                /* insert the new entry: mark the entry NEW */
1476                xad = &p->xad[index + 1];
1477                XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1478
1479                /* advance next available entry index */
1480                le16_add_cpu(&p->header.nextindex, 1);
1481        }
1482
1483        /* get back old entry */
1484        xad = &p->xad[index];
1485        xlen = MAXXLEN;
1486
1487        /*
1488         * extend old extent
1489         */
1490      extendOld:
1491        XADlength(xad, xlen);
1492        if (!(xad->flag & XAD_NEW))
1493                xad->flag |= XAD_EXTENDED;
1494
1495        if (!test_cflag(COMMIT_Nolink, ip)) {
1496                xtlck->lwm.offset =
1497                    (xtlck->lwm.offset) ? min(index,
1498                                              (int)xtlck->lwm.offset) : index;
1499                xtlck->lwm.length =
1500                    le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1501        }
1502
1503        /* unpin the leaf page */
1504        XT_PUTPAGE(mp);
1505
1506        return rc;
1507}
1508
1509#ifdef _NOTYET
1510/*
1511 *      xtTailgate()
1512 *
1513 * function: split existing 'tail' extent
1514 *      (split offset >= start offset of tail extent), and
1515 *      relocate and extend the split tail half;
1516 *
1517 * note: existing extent may or may not have been committed.
1518 * caller is responsible for pager buffer cache update, and
1519 * working block allocation map update;
1520 * update pmap: free old split tail extent, alloc new extent;
1521 */
1522int xtTailgate(tid_t tid,               /* transaction id */
1523               struct inode *ip, s64 xoff,      /* split/new extent offset */
1524               s32 xlen,        /* new extent length */
1525               s64 xaddr,       /* new extent address */
1526               int flag)
1527{
1528        int rc = 0;
1529        int cmp;
1530        struct metapage *mp;    /* meta-page buffer */
1531        xtpage_t *p;            /* base B+-tree index page */
1532        s64 bn;
1533        int index, nextindex, llen, rlen;
1534        struct btstack btstack; /* traverse stack */
1535        struct xtsplit split;   /* split information */
1536        xad_t *xad;
1537        struct tlock *tlck;
1538        struct xtlock *xtlck = 0;
1539        struct tlock *mtlck;
1540        struct maplock *pxdlock;
1541
1542/*
1543printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1544        (ulong)xoff, xlen, (ulong)xaddr);
1545*/
1546
1547        /* there must exist extent to be tailgated */
1548        if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
1549                return rc;
1550
1551        /* retrieve search result */
1552        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1553
1554        if (cmp != 0) {
1555                XT_PUTPAGE(mp);
1556                jfs_error(ip->i_sb, "couldn't find extent\n");
1557                return -EIO;
1558        }
1559
1560        /* entry found must be last entry */
1561        nextindex = le16_to_cpu(p->header.nextindex);
1562        if (index != nextindex - 1) {
1563                XT_PUTPAGE(mp);
1564                jfs_error(ip->i_sb, "the entry found is not the last entry\n");
1565                return -EIO;
1566        }
1567
1568        BT_MARK_DIRTY(mp, ip);
1569        /*
1570         * acquire tlock of the leaf page containing original entry
1571         */
1572        if (!test_cflag(COMMIT_Nolink, ip)) {
1573                tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1574                xtlck = (struct xtlock *) & tlck->lock;
1575        }
1576
1577        /* completely replace extent ? */
1578        xad = &p->xad[index];
1579/*
1580printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1581        (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1582*/
1583        if ((llen = xoff - offsetXAD(xad)) == 0)
1584                goto updateOld;
1585
1586        /*
1587         *      partially replace extent: insert entry for new extent
1588         */
1589//insertNew:
1590        /*
1591         *      if the leaf page is full, insert the new entry and
1592         *      propagate up the router entry for the new page from split
1593         *
1594         * The xtSplitUp() will insert the entry and unpin the leaf page.
1595         */
1596        if (nextindex == le16_to_cpu(p->header.maxentry)) {
1597                /* xtSpliUp() unpins leaf pages */
1598                split.mp = mp;
1599                split.index = index + 1;
1600                split.flag = XAD_NEW;
1601                split.off = xoff;       /* split offset */
1602                split.len = xlen;
1603                split.addr = xaddr;
1604                split.pxdlist = NULL;
1605                if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1606                        return rc;
1607
1608                /* get back old page */
1609                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1610                if (rc)
1611                        return rc;
1612                /*
1613                 * if leaf root has been split, original root has been
1614                 * copied to new child page, i.e., original entry now
1615                 * resides on the new child page;
1616                 */
1617                if (p->header.flag & BT_INTERNAL) {
1618                        ASSERT(p->header.nextindex ==
1619                               cpu_to_le16(XTENTRYSTART + 1));
1620                        xad = &p->xad[XTENTRYSTART];
1621                        bn = addressXAD(xad);
1622                        XT_PUTPAGE(mp);
1623
1624                        /* get new child page */
1625                        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1626                        if (rc)
1627                                return rc;
1628
1629                        BT_MARK_DIRTY(mp, ip);
1630                        if (!test_cflag(COMMIT_Nolink, ip)) {
1631                                tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1632                                xtlck = (struct xtlock *) & tlck->lock;
1633                        }
1634                }
1635        }
1636        /*
1637         *      insert the new entry into the leaf page
1638         */
1639        else {
1640                /* insert the new entry: mark the entry NEW */
1641                xad = &p->xad[index + 1];
1642                XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1643
1644                /* advance next available entry index */
1645                le16_add_cpu(&p->header.nextindex, 1);
1646        }
1647
1648        /* get back old XAD */
1649        xad = &p->xad[index];
1650
1651        /*
1652         * truncate/relocate old extent at split offset
1653         */
1654      updateOld:
1655        /* update dmap for old/committed/truncated extent */
1656        rlen = lengthXAD(xad) - llen;
1657        if (!(xad->flag & XAD_NEW)) {
1658                /* free from PWMAP at commit */
1659                if (!test_cflag(COMMIT_Nolink, ip)) {
1660                        mtlck = txMaplock(tid, ip, tlckMAP);
1661                        pxdlock = (struct maplock *) & mtlck->lock;
1662                        pxdlock->flag = mlckFREEPXD;
1663                        PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1664                        PXDlength(&pxdlock->pxd, rlen);
1665                        pxdlock->index = 1;
1666                }
1667        } else
1668                /* free from WMAP */
1669                dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1670
1671        if (llen)
1672                /* truncate */
1673                XADlength(xad, llen);
1674        else
1675                /* replace */
1676                XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1677
1678        if (!test_cflag(COMMIT_Nolink, ip)) {
1679                xtlck->lwm.offset = (xtlck->lwm.offset) ?
1680                    min(index, (int)xtlck->lwm.offset) : index;
1681                xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1682                    xtlck->lwm.offset;
1683        }
1684
1685        /* unpin the leaf page */
1686        XT_PUTPAGE(mp);
1687
1688        return rc;
1689}
1690#endif /* _NOTYET */
1691
1692/*
1693 *      xtUpdate()
1694 *
1695 * function: update XAD;
1696 *
1697 *      update extent for allocated_but_not_recorded or
1698 *      compressed extent;
1699 *
1700 * parameter:
1701 *      nxad    - new XAD;
1702 *              logical extent of the specified XAD must be completely
1703 *              contained by an existing XAD;
1704 */
1705int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1706{                               /* new XAD */
1707        int rc = 0;
1708        int cmp;
1709        struct metapage *mp;    /* meta-page buffer */
1710        xtpage_t *p;            /* base B+-tree index page */
1711        s64 bn;
1712        int index0, index, newindex, nextindex;
1713        struct btstack btstack; /* traverse stack */
1714        struct xtsplit split;   /* split information */
1715        xad_t *xad, *lxad, *rxad;
1716        int xflag;
1717        s64 nxoff, xoff;
1718        int nxlen, xlen, lxlen, rxlen;
1719        s64 nxaddr, xaddr;
1720        struct tlock *tlck;
1721        struct xtlock *xtlck = NULL;
1722        int newpage = 0;
1723
1724        /* there must exist extent to be tailgated */
1725        nxoff = offsetXAD(nxad);
1726        nxlen = lengthXAD(nxad);
1727        nxaddr = addressXAD(nxad);
1728
1729        if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
1730                return rc;
1731
1732        /* retrieve search result */
1733        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1734
1735        if (cmp != 0) {
1736                XT_PUTPAGE(mp);
1737                jfs_error(ip->i_sb, "Could not find extent\n");
1738                return -EIO;
1739        }
1740
1741        BT_MARK_DIRTY(mp, ip);
1742        /*
1743         * acquire tlock of the leaf page containing original entry
1744         */
1745        if (!test_cflag(COMMIT_Nolink, ip)) {
1746                tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1747                xtlck = (struct xtlock *) & tlck->lock;
1748        }
1749
1750        xad = &p->xad[index0];
1751        xflag = xad->flag;
1752        xoff = offsetXAD(xad);
1753        xlen = lengthXAD(xad);
1754        xaddr = addressXAD(xad);
1755
1756        /* nXAD must be completely contained within XAD */
1757        if ((xoff > nxoff) ||
1758            (nxoff + nxlen > xoff + xlen)) {
1759                XT_PUTPAGE(mp);
1760                jfs_error(ip->i_sb,
1761                          "nXAD in not completely contained within XAD\n");
1762                return -EIO;
1763        }
1764
1765        index = index0;
1766        newindex = index + 1;
1767        nextindex = le16_to_cpu(p->header.nextindex);
1768
1769#ifdef  _JFS_WIP_NOCOALESCE
1770        if (xoff < nxoff)
1771                goto updateRight;
1772
1773        /*
1774         * replace XAD with nXAD
1775         */
1776      replace:                  /* (nxoff == xoff) */
1777        if (nxlen == xlen) {
1778                /* replace XAD with nXAD:recorded */
1779                *xad = *nxad;
1780                xad->flag = xflag & ~XAD_NOTRECORDED;
1781
1782                goto out;
1783        } else                  /* (nxlen < xlen) */
1784                goto updateLeft;
1785#endif                          /* _JFS_WIP_NOCOALESCE */
1786
1787/* #ifdef _JFS_WIP_COALESCE */
1788        if (xoff < nxoff)
1789                goto coalesceRight;
1790
1791        /*
1792         * coalesce with left XAD
1793         */
1794//coalesceLeft: /* (xoff == nxoff) */
1795        /* is XAD first entry of page ? */
1796        if (index == XTENTRYSTART)
1797                goto replace;
1798
1799        /* is nXAD logically and physically contiguous with lXAD ? */
1800        lxad = &p->xad[index - 1];
1801        lxlen = lengthXAD(lxad);
1802        if (!(lxad->flag & XAD_NOTRECORDED) &&
1803            (nxoff == offsetXAD(lxad) + lxlen) &&
1804            (nxaddr == addressXAD(lxad) + lxlen) &&
1805            (lxlen + nxlen < MAXXLEN)) {
1806                /* extend right lXAD */
1807                index0 = index - 1;
1808                XADlength(lxad, lxlen + nxlen);
1809
1810                /* If we just merged two extents together, need to make sure the
1811                 * right extent gets logged.  If the left one is marked XAD_NEW,
1812                 * then we know it will be logged.  Otherwise, mark as
1813                 * XAD_EXTENDED
1814                 */
1815                if (!(lxad->flag & XAD_NEW))
1816                        lxad->flag |= XAD_EXTENDED;
1817
1818                if (xlen > nxlen) {
1819                        /* truncate XAD */
1820                        XADoffset(xad, xoff + nxlen);
1821                        XADlength(xad, xlen - nxlen);
1822                        XADaddress(xad, xaddr + nxlen);
1823                        goto out;
1824                } else {        /* (xlen == nxlen) */
1825
1826                        /* remove XAD */
1827                        if (index < nextindex - 1)
1828                                memmove(&p->xad[index], &p->xad[index + 1],
1829                                        (nextindex - index -
1830                                         1) << L2XTSLOTSIZE);
1831
1832                        p->header.nextindex =
1833                            cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1834                                        1);
1835
1836                        index = index0;
1837                        newindex = index + 1;
1838                        nextindex = le16_to_cpu(p->header.nextindex);
1839                        xoff = nxoff = offsetXAD(lxad);
1840                        xlen = nxlen = lxlen + nxlen;
1841                        xaddr = nxaddr = addressXAD(lxad);
1842                        goto coalesceRight;
1843                }
1844        }
1845
1846        /*
1847         * replace XAD with nXAD
1848         */
1849      replace:                  /* (nxoff == xoff) */
1850        if (nxlen == xlen) {
1851                /* replace XAD with nXAD:recorded */
1852                *xad = *nxad;
1853                xad->flag = xflag & ~XAD_NOTRECORDED;
1854
1855                goto coalesceRight;
1856        } else                  /* (nxlen < xlen) */
1857                goto updateLeft;
1858
1859        /*
1860         * coalesce with right XAD
1861         */
1862      coalesceRight:            /* (xoff <= nxoff) */
1863        /* is XAD last entry of page ? */
1864        if (newindex == nextindex) {
1865                if (xoff == nxoff)
1866                        goto out;
1867                goto updateRight;
1868        }
1869
1870        /* is nXAD logically and physically contiguous with rXAD ? */
1871        rxad = &p->xad[index + 1];
1872        rxlen = lengthXAD(rxad);
1873        if (!(rxad->flag & XAD_NOTRECORDED) &&
1874            (nxoff + nxlen == offsetXAD(rxad)) &&
1875            (nxaddr + nxlen == addressXAD(rxad)) &&
1876            (rxlen + nxlen < MAXXLEN)) {
1877                /* extend left rXAD */
1878                XADoffset(rxad, nxoff);
1879                XADlength(rxad, rxlen + nxlen);
1880                XADaddress(rxad, nxaddr);
1881
1882                /* If we just merged two extents together, need to make sure
1883                 * the left extent gets logged.  If the right one is marked
1884                 * XAD_NEW, then we know it will be logged.  Otherwise, mark as
1885                 * XAD_EXTENDED
1886                 */
1887                if (!(rxad->flag & XAD_NEW))
1888                        rxad->flag |= XAD_EXTENDED;
1889
1890                if (xlen > nxlen)
1891                        /* truncate XAD */
1892                        XADlength(xad, xlen - nxlen);
1893                else {          /* (xlen == nxlen) */
1894
1895                        /* remove XAD */
1896                        memmove(&p->xad[index], &p->xad[index + 1],
1897                                (nextindex - index - 1) << L2XTSLOTSIZE);
1898
1899                        p->header.nextindex =
1900                            cpu_to_le16(le16_to_cpu(p->header.nextindex) -
1901                                        1);
1902                }
1903
1904                goto out;
1905        } else if (xoff == nxoff)
1906                goto out;
1907
1908        if (xoff >= nxoff) {
1909                XT_PUTPAGE(mp);
1910                jfs_error(ip->i_sb, "xoff >= nxoff\n");
1911                return -EIO;
1912        }
1913/* #endif _JFS_WIP_COALESCE */
1914
1915        /*
1916         * split XAD into (lXAD, nXAD):
1917         *
1918         *          |---nXAD--->
1919         * --|----------XAD----------|--
1920         *   |-lXAD-|
1921         */
1922      updateRight:              /* (xoff < nxoff) */
1923        /* truncate old XAD as lXAD:not_recorded */
1924        xad = &p->xad[index];
1925        XADlength(xad, nxoff - xoff);
1926
1927        /* insert nXAD:recorded */
1928        if (nextindex == le16_to_cpu(p->header.maxentry)) {
1929
1930                /* xtSpliUp() unpins leaf pages */
1931                split.mp = mp;
1932                split.index = newindex;
1933                split.flag = xflag & ~XAD_NOTRECORDED;
1934                split.off = nxoff;
1935                split.len = nxlen;
1936                split.addr = nxaddr;
1937                split.pxdlist = NULL;
1938                if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1939                        return rc;
1940
1941                /* get back old page */
1942                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1943                if (rc)
1944                        return rc;
1945                /*
1946                 * if leaf root has been split, original root has been
1947                 * copied to new child page, i.e., original entry now
1948                 * resides on the new child page;
1949                 */
1950                if (p->header.flag & BT_INTERNAL) {
1951                        ASSERT(p->header.nextindex ==
1952                               cpu_to_le16(XTENTRYSTART + 1));
1953                        xad = &p->xad[XTENTRYSTART];
1954                        bn = addressXAD(xad);
1955                        XT_PUTPAGE(mp);
1956
1957                        /* get new child page */
1958                        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1959                        if (rc)
1960                                return rc;
1961
1962                        BT_MARK_DIRTY(mp, ip);
1963                        if (!test_cflag(COMMIT_Nolink, ip)) {
1964                                tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1965                                xtlck = (struct xtlock *) & tlck->lock;
1966                        }
1967                } else {
1968                        /* is nXAD on new page ? */
1969                        if (newindex >
1970                            (le16_to_cpu(p->header.maxentry) >> 1)) {
1971                                newindex =
1972                                    newindex -
1973                                    le16_to_cpu(p->header.nextindex) +
1974                                    XTENTRYSTART;
1975                                newpage = 1;
1976                        }
1977                }
1978        } else {
1979                /* if insert into middle, shift right remaining entries */
1980                if (newindex < nextindex)
1981                        memmove(&p->xad[newindex + 1], &p->xad[newindex],
1982                                (nextindex - newindex) << L2XTSLOTSIZE);
1983
1984                /* insert the entry */
1985                xad = &p->xad[newindex];
1986                *xad = *nxad;
1987                xad->flag = xflag & ~XAD_NOTRECORDED;
1988
1989                /* advance next available entry index. */
1990                p->header.nextindex =
1991                    cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1992        }
1993
1994        /*
1995         * does nXAD force 3-way split ?
1996         *
1997         *          |---nXAD--->|
1998         * --|----------XAD-------------|--
1999         *   |-lXAD-|           |-rXAD -|
2000         */
2001        if (nxoff + nxlen == xoff + xlen)
2002                goto out;
2003
2004        /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2005        if (newpage) {
2006                /* close out old page */
2007                if (!test_cflag(COMMIT_Nolink, ip)) {
2008                        xtlck->lwm.offset = (xtlck->lwm.offset) ?
2009                            min(index0, (int)xtlck->lwm.offset) : index0;
2010                        xtlck->lwm.length =
2011                            le16_to_cpu(p->header.nextindex) -
2012                            xtlck->lwm.offset;
2013                }
2014
2015                bn = le64_to_cpu(p->header.next);
2016                XT_PUTPAGE(mp);
2017
2018                /* get new right page */
2019                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2020                if (rc)
2021                        return rc;
2022
2023                BT_MARK_DIRTY(mp, ip);
2024                if (!test_cflag(COMMIT_Nolink, ip)) {
2025                        tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2026                        xtlck = (struct xtlock *) & tlck->lock;
2027                }
2028
2029                index0 = index = newindex;
2030        } else
2031                index++;
2032
2033        newindex = index + 1;
2034        nextindex = le16_to_cpu(p->header.nextindex);
2035        xlen = xlen - (nxoff - xoff);
2036        xoff = nxoff;
2037        xaddr = nxaddr;
2038
2039        /* recompute split pages */
2040        if (nextindex == le16_to_cpu(p->header.maxentry)) {
2041                XT_PUTPAGE(mp);
2042
2043                if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2044                        return rc;
2045
2046                /* retrieve search result */
2047                XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2048
2049                if (cmp != 0) {
2050                        XT_PUTPAGE(mp);
2051                        jfs_error(ip->i_sb, "xtSearch failed\n");
2052                        return -EIO;
2053                }
2054
2055                if (index0 != index) {
2056                        XT_PUTPAGE(mp);
2057                        jfs_error(ip->i_sb, "unexpected value of index\n");
2058                        return -EIO;
2059                }
2060        }
2061
2062        /*
2063         * split XAD into (nXAD, rXAD)
2064         *
2065         *          ---nXAD---|
2066         * --|----------XAD----------|--
2067         *                    |-rXAD-|
2068         */
2069      updateLeft:               /* (nxoff == xoff) && (nxlen < xlen) */
2070        /* update old XAD with nXAD:recorded */
2071        xad = &p->xad[index];
2072        *xad = *nxad;
2073        xad->flag = xflag & ~XAD_NOTRECORDED;
2074
2075        /* insert rXAD:not_recorded */
2076        xoff = xoff + nxlen;
2077        xlen = xlen - nxlen;
2078        xaddr = xaddr + nxlen;
2079        if (nextindex == le16_to_cpu(p->header.maxentry)) {
2080/*
2081printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2082*/
2083                /* xtSpliUp() unpins leaf pages */
2084                split.mp = mp;
2085                split.index = newindex;
2086                split.flag = xflag;
2087                split.off = xoff;
2088                split.len = xlen;
2089                split.addr = xaddr;
2090                split.pxdlist = NULL;
2091                if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2092                        return rc;
2093
2094                /* get back old page */
2095                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2096                if (rc)
2097                        return rc;
2098
2099                /*
2100                 * if leaf root has been split, original root has been
2101                 * copied to new child page, i.e., original entry now
2102                 * resides on the new child page;
2103                 */
2104                if (p->header.flag & BT_INTERNAL) {
2105                        ASSERT(p->header.nextindex ==
2106                               cpu_to_le16(XTENTRYSTART + 1));
2107                        xad = &p->xad[XTENTRYSTART];
2108                        bn = addressXAD(xad);
2109                        XT_PUTPAGE(mp);
2110
2111                        /* get new child page */
2112                        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2113                        if (rc)
2114                                return rc;
2115
2116                        BT_MARK_DIRTY(mp, ip);
2117                        if (!test_cflag(COMMIT_Nolink, ip)) {
2118                                tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2119                                xtlck = (struct xtlock *) & tlck->lock;
2120                        }
2121                }
2122        } else {
2123                /* if insert into middle, shift right remaining entries */
2124                if (newindex < nextindex)
2125                        memmove(&p->xad[newindex + 1], &p->xad[newindex],
2126                                (nextindex - newindex) << L2XTSLOTSIZE);
2127
2128                /* insert the entry */
2129                xad = &p->xad[newindex];
2130                XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2131
2132                /* advance next available entry index. */
2133                p->header.nextindex =
2134                    cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2135        }
2136
2137      out:
2138        if (!test_cflag(COMMIT_Nolink, ip)) {
2139                xtlck->lwm.offset = (xtlck->lwm.offset) ?
2140                    min(index0, (int)xtlck->lwm.offset) : index0;
2141                xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2142                    xtlck->lwm.offset;
2143        }
2144
2145        /* unpin the leaf page */
2146        XT_PUTPAGE(mp);
2147
2148        return rc;
2149}
2150
2151
2152/*
2153 *      xtAppend()
2154 *
2155 * function: grow in append mode from contiguous region specified ;
2156 *
2157 * parameter:
2158 *      tid             - transaction id;
2159 *      ip              - file object;
2160 *      xflag           - extent flag:
2161 *      xoff            - extent offset;
2162 *      maxblocks       - max extent length;
2163 *      xlen            - extent length (in/out);
2164 *      xaddrp          - extent address pointer (in/out):
2165 *      flag            -
2166 *
2167 * return:
2168 */
2169int xtAppend(tid_t tid,         /* transaction id */
2170             struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2171             s32 * xlenp,       /* (in/out) */
2172             s64 * xaddrp,      /* (in/out) */
2173             int flag)
2174{
2175        int rc = 0;
2176        struct metapage *mp;    /* meta-page buffer */
2177        xtpage_t *p;            /* base B+-tree index page */
2178        s64 bn, xaddr;
2179        int index, nextindex;
2180        struct btstack btstack; /* traverse stack */
2181        struct xtsplit split;   /* split information */
2182        xad_t *xad;
2183        int cmp;
2184        struct tlock *tlck;
2185        struct xtlock *xtlck;
2186        int nsplit, nblocks, xlen;
2187        struct pxdlist pxdlist;
2188        pxd_t *pxd;
2189        s64 next;
2190
2191        xaddr = *xaddrp;
2192        xlen = *xlenp;
2193        jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2194                 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2195
2196        /*
2197         *      search for the entry location at which to insert:
2198         *
2199         * xtFastSearch() and xtSearch() both returns (leaf page
2200         * pinned, index at which to insert).
2201         * n.b. xtSearch() may return index of maxentry of
2202         * the full page.
2203         */
2204        if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
2205                return rc;
2206
2207        /* retrieve search result */
2208        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2209
2210        if (cmp == 0) {
2211                rc = -EEXIST;
2212                goto out;
2213        }
2214
2215        if (next)
2216                xlen = min(xlen, (int)(next - xoff));
2217//insert:
2218        /*
2219         *      insert entry for new extent
2220         */
2221        xflag |= XAD_NEW;
2222
2223        /*
2224         *      if the leaf page is full, split the page and
2225         *      propagate up the router entry for the new page from split
2226         *
2227         * The xtSplitUp() will insert the entry and unpin the leaf page.
2228         */
2229        nextindex = le16_to_cpu(p->header.nextindex);
2230        if (nextindex < le16_to_cpu(p->header.maxentry))
2231                goto insertLeaf;
2232
2233        /*
2234         * allocate new index blocks to cover index page split(s)
2235         */
2236        nsplit = btstack.nsplit;
2237        split.pxdlist = &pxdlist;
2238        pxdlist.maxnpxd = pxdlist.npxd = 0;
2239        pxd = &pxdlist.pxd[0];
2240        nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2241        for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2242                if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2243                        PXDaddress(pxd, xaddr);
2244                        PXDlength(pxd, nblocks);
2245
2246                        pxdlist.maxnpxd++;
2247
2248                        continue;
2249                }
2250
2251                /* undo allocation */
2252
2253                goto out;
2254        }
2255
2256        xlen = min(xlen, maxblocks);
2257
2258        /*
2259         * allocate data extent requested
2260         */
2261        if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2262                goto out;
2263
2264        split.mp = mp;
2265        split.index = index;
2266        split.flag = xflag;
2267        split.off = xoff;
2268        split.len = xlen;
2269        split.addr = xaddr;
2270        if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2271                /* undo data extent allocation */
2272                dbFree(ip, *xaddrp, (s64) * xlenp);
2273
2274                return rc;
2275        }
2276
2277        *xaddrp = xaddr;
2278        *xlenp = xlen;
2279        return 0;
2280
2281        /*
2282         *      insert the new entry into the leaf page
2283         */
2284      insertLeaf:
2285        /*
2286         * allocate data extent requested
2287         */
2288        if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2289                goto out;
2290
2291        BT_MARK_DIRTY(mp, ip);
2292        /*
2293         * acquire a transaction lock on the leaf page;
2294         *
2295         * action: xad insertion/extension;
2296         */
2297        tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2298        xtlck = (struct xtlock *) & tlck->lock;
2299
2300        /* insert the new entry: mark the entry NEW */
2301        xad = &p->xad[index];
2302        XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2303
2304        /* advance next available entry index */
2305        le16_add_cpu(&p->header.nextindex, 1);
2306
2307        xtlck->lwm.offset =
2308            (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2309        xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2310            xtlck->lwm.offset;
2311
2312        *xaddrp = xaddr;
2313        *xlenp = xlen;
2314
2315      out:
2316        /* unpin the leaf page */
2317        XT_PUTPAGE(mp);
2318
2319        return rc;
2320}
2321#ifdef _STILL_TO_PORT
2322
2323/* - TBD for defragmentaion/reorganization -
2324 *
2325 *      xtDelete()
2326 *
2327 * function:
2328 *      delete the entry with the specified key.
2329 *
2330 *      N.B.: whole extent of the entry is assumed to be deleted.
2331 *
2332 * parameter:
2333 *
2334 * return:
2335 *      ENOENT: if the entry is not found.
2336 *
2337 * exception:
2338 */
2339int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2340{
2341        int rc = 0;
2342        struct btstack btstack;
2343        int cmp;
2344        s64 bn;
2345        struct metapage *mp;
2346        xtpage_t *p;
2347        int index, nextindex;
2348        struct tlock *tlck;
2349        struct xtlock *xtlck;
2350
2351        /*
2352         * find the matching entry; xtSearch() pins the page
2353         */
2354        if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2355                return rc;
2356
2357        XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2358        if (cmp) {
2359                /* unpin the leaf page */
2360                XT_PUTPAGE(mp);
2361                return -ENOENT;
2362        }
2363
2364        /*
2365         * delete the entry from the leaf page
2366         */
2367        nextindex = le16_to_cpu(p->header.nextindex);
2368        le16_add_cpu(&p->header.nextindex, -1);
2369
2370        /*
2371         * if the leaf page bocome empty, free the page
2372         */
2373        if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2374                return (xtDeleteUp(tid, ip, mp, p, &btstack));
2375
2376        BT_MARK_DIRTY(mp, ip);
2377        /*
2378         * acquire a transaction lock on the leaf page;
2379         *
2380         * action:xad deletion;
2381         */
2382        tlck = txLock(tid, ip, mp, tlckXTREE);
2383        xtlck = (struct xtlock *) & tlck->lock;
2384        xtlck->lwm.offset =
2385            (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2386
2387        /* if delete from middle, shift left/compact the remaining entries */
2388        if (index < nextindex - 1)
2389                memmove(&p->xad[index], &p->xad[index + 1],
2390                        (nextindex - index - 1) * sizeof(xad_t));
2391
2392        XT_PUTPAGE(mp);
2393
2394        return 0;
2395}
2396
2397
2398/* - TBD for defragmentaion/reorganization -
2399 *
2400 *      xtDeleteUp()
2401 *
2402 * function:
2403 *      free empty pages as propagating deletion up the tree
2404 *
2405 * parameter:
2406 *
2407 * return:
2408 */
2409static int
2410xtDeleteUp(tid_t tid, struct inode *ip,
2411           struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2412{
2413        int rc = 0;
2414        struct metapage *mp;
2415        xtpage_t *p;
2416        int index, nextindex;
2417        s64 xaddr;
2418        int xlen;
2419        struct btframe *parent;
2420        struct tlock *tlck;
2421        struct xtlock *xtlck;
2422
2423        /*
2424         * keep root leaf page which has become empty
2425         */
2426        if (fp->header.flag & BT_ROOT) {
2427                /* keep the root page */
2428                fp->header.flag &= ~BT_INTERNAL;
2429                fp->header.flag |= BT_LEAF;
2430                fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2431
2432                /* XT_PUTPAGE(fmp); */
2433
2434                return 0;
2435        }
2436
2437        /*
2438         * free non-root leaf page
2439         */
2440        if ((rc = xtRelink(tid, ip, fp))) {
2441                XT_PUTPAGE(fmp);
2442                return rc;
2443        }
2444
2445        xaddr = addressPXD(&fp->header.self);
2446        xlen = lengthPXD(&fp->header.self);
2447        /* free the page extent */
2448        dbFree(ip, xaddr, (s64) xlen);
2449
2450        /* free the buffer page */
2451        discard_metapage(fmp);
2452
2453        /*
2454         * propagate page deletion up the index tree
2455         *
2456         * If the delete from the parent page makes it empty,
2457         * continue all the way up the tree.
2458         * stop if the root page is reached (which is never deleted) or
2459         * if the entry deletion does not empty the page.
2460         */
2461        while ((parent = BT_POP(btstack)) != NULL) {
2462                /* get/pin the parent page <sp> */
2463                XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2464                if (rc)
2465                        return rc;
2466
2467                index = parent->index;
2468
2469                /* delete the entry for the freed child page from parent.
2470                 */
2471                nextindex = le16_to_cpu(p->header.nextindex);
2472
2473                /*
2474                 * the parent has the single entry being deleted:
2475                 * free the parent page which has become empty.
2476                 */
2477                if (nextindex == 1) {
2478                        if (p->header.flag & BT_ROOT) {
2479                                /* keep the root page */
2480                                p->header.flag &= ~BT_INTERNAL;
2481                                p->header.flag |= BT_LEAF;
2482                                p->header.nextindex =
2483                                    cpu_to_le16(XTENTRYSTART);
2484
2485                                /* XT_PUTPAGE(mp); */
2486
2487                                break;
2488                        } else {
2489                                /* free the parent page */
2490                                if ((rc = xtRelink(tid, ip, p)))
2491                                        return rc;
2492
2493                                xaddr = addressPXD(&p->header.self);
2494                                /* free the page extent */
2495                                dbFree(ip, xaddr,
2496                                       (s64) JFS_SBI(ip->i_sb)->nbperpage);
2497
2498                                /* unpin/free the buffer page */
2499                                discard_metapage(mp);
2500
2501                                /* propagate up */
2502                                continue;
2503                        }
2504                }
2505                /*
2506                 * the parent has other entries remaining:
2507                 * delete the router entry from the parent page.
2508                 */
2509                else {
2510                        BT_MARK_DIRTY(mp, ip);
2511                        /*
2512                         * acquire a transaction lock on the leaf page;
2513                         *
2514                         * action:xad deletion;
2515                         */
2516                        tlck = txLock(tid, ip, mp, tlckXTREE);
2517                        xtlck = (struct xtlock *) & tlck->lock;
2518                        xtlck->lwm.offset =
2519                            (xtlck->lwm.offset) ? min(index,
2520                                                      xtlck->lwm.
2521                                                      offset) : index;
2522
2523                        /* if delete from middle,
2524                         * shift left/compact the remaining entries in the page
2525                         */
2526                        if (index < nextindex - 1)
2527                                memmove(&p->xad[index], &p->xad[index + 1],
2528                                        (nextindex - index -
2529                                         1) << L2XTSLOTSIZE);
2530
2531                        le16_add_cpu(&p->header.nextindex, -1);
2532                        jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2533                                 (ulong) parent->bn, index);
2534                }
2535
2536                /* unpin the parent page */
2537                XT_PUTPAGE(mp);
2538
2539                /* exit propagation up */
2540                break;
2541        }
2542
2543        return 0;
2544}
2545
2546
2547/*
2548 * NAME:        xtRelocate()
2549 *
2550 * FUNCTION:    relocate xtpage or data extent of regular file;
2551 *              This function is mainly used by defragfs utility.
2552 *
2553 * NOTE:        This routine does not have the logic to handle
2554 *              uncommitted allocated extent. The caller should call
2555 *              txCommit() to commit all the allocation before call
2556 *              this routine.
2557 */
2558int
2559xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad,  /* old XAD */
2560           s64 nxaddr,          /* new xaddr */
2561           int xtype)
2562{                               /* extent type: XTPAGE or DATAEXT */
2563        int rc = 0;
2564        struct tblock *tblk;
2565        struct tlock *tlck;
2566        struct xtlock *xtlck;
2567        struct metapage *mp, *pmp, *lmp, *rmp;  /* meta-page buffer */
2568        xtpage_t *p, *pp, *rp, *lp;     /* base B+-tree index page */
2569        xad_t *xad;
2570        pxd_t *pxd;
2571        s64 xoff, xsize;
2572        int xlen;
2573        s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2574        cbuf_t *cp;
2575        s64 offset, nbytes, nbrd, pno;
2576        int nb, npages, nblks;
2577        s64 bn;
2578        int cmp;
2579        int index;
2580        struct pxd_lock *pxdlock;
2581        struct btstack btstack; /* traverse stack */
2582
2583        xtype = xtype & EXTENT_TYPE;
2584
2585        xoff = offsetXAD(oxad);
2586        oxaddr = addressXAD(oxad);
2587        xlen = lengthXAD(oxad);
2588
2589        /* validate extent offset */
2590        offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2591        if (offset >= ip->i_size)
2592                return -ESTALE; /* stale extent */
2593
2594        jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2595                 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2596
2597        /*
2598         *      1. get and validate the parent xtpage/xad entry
2599         *      covering the source extent to be relocated;
2600         */
2601        if (xtype == DATAEXT) {
2602                /* search in leaf entry */
2603                rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2604                if (rc)
2605                        return rc;
2606
2607                /* retrieve search result */
2608                XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2609
2610                if (cmp) {
2611                        XT_PUTPAGE(pmp);
2612                        return -ESTALE;
2613                }
2614
2615                /* validate for exact match with a single entry */
2616                xad = &pp->xad[index];
2617                if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2618                        XT_PUTPAGE(pmp);
2619                        return -ESTALE;
2620                }
2621        } else {                /* (xtype == XTPAGE) */
2622
2623                /* search in internal entry */
2624                rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2625                if (rc)
2626                        return rc;
2627
2628                /* retrieve search result */
2629                XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2630
2631                if (cmp) {
2632                        XT_PUTPAGE(pmp);
2633                        return -ESTALE;
2634                }
2635
2636                /* xtSearchNode() validated for exact match with a single entry
2637                 */
2638                xad = &pp->xad[index];
2639        }
2640        jfs_info("xtRelocate: parent xad entry validated.");
2641
2642        /*
2643         *      2. relocate the extent
2644         */
2645        if (xtype == DATAEXT) {
2646                /* if the extent is allocated-but-not-recorded
2647                 * there is no real data to be moved in this extent,
2648                 */
2649                if (xad->flag & XAD_NOTRECORDED)
2650                        goto out;
2651                else
2652                        /* release xtpage for cmRead()/xtLookup() */
2653                        XT_PUTPAGE(pmp);
2654
2655                /*
2656                 *      cmRelocate()
2657                 *
2658                 * copy target data pages to be relocated;
2659                 *
2660                 * data extent must start at page boundary and
2661                 * multiple of page size (except the last data extent);
2662                 * read in each page of the source data extent into cbuf,
2663                 * update the cbuf extent descriptor of the page to be
2664                 * homeward bound to new dst data extent
2665                 * copy the data from the old extent to new extent.
2666                 * copy is essential for compressed files to avoid problems
2667                 * that can arise if there was a change in compression
2668                 * algorithms.
2669                 * it is a good strategy because it may disrupt cache
2670                 * policy to keep the pages in memory afterwards.
2671                 */
2672                offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2673                assert((offset & CM_OFFSET) == 0);
2674                nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2675                pno = offset >> CM_L2BSIZE;
2676                npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2677/*
2678                npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2679                          (offset >> CM_L2BSIZE) + 1;
2680*/
2681                sxaddr = oxaddr;
2682                dxaddr = nxaddr;
2683
2684                /* process the request one cache buffer at a time */
2685                for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2686                     offset += nb, pno++, npages--) {
2687                        /* compute page size */
2688                        nb = min(nbytes - nbrd, CM_BSIZE);
2689
2690                        /* get the cache buffer of the page */
2691                        if (rc = cmRead(ip, offset, npages, &cp))
2692                                break;
2693
2694                        assert(addressPXD(&cp->cm_pxd) == sxaddr);
2695                        assert(!cp->cm_modified);
2696
2697                        /* bind buffer with the new extent address */
2698                        nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2699                        cmSetXD(ip, cp, pno, dxaddr, nblks);
2700
2701                        /* release the cbuf, mark it as modified */
2702                        cmPut(cp, true);
2703
2704                        dxaddr += nblks;
2705                        sxaddr += nblks;
2706                }
2707
2708                /* get back parent page */
2709                if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2710                        return rc;
2711
2712                XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2713                jfs_info("xtRelocate: target data extent relocated.");
2714        } else {                /* (xtype == XTPAGE) */
2715
2716                /*
2717                 * read in the target xtpage from the source extent;
2718                 */
2719                XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2720                if (rc) {
2721                        XT_PUTPAGE(pmp);
2722                        return rc;
2723                }
2724
2725                /*
2726                 * read in sibling pages if any to update sibling pointers;
2727                 */
2728                rmp = NULL;
2729                if (p->header.next) {
2730                        nextbn = le64_to_cpu(p->header.next);
2731                        XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
2732                        if (rc) {
2733                                XT_PUTPAGE(pmp);
2734                                XT_PUTPAGE(mp);
2735                                return (rc);
2736                        }
2737                }
2738
2739                lmp = NULL;
2740                if (p->header.prev) {
2741                        prevbn = le64_to_cpu(p->header.prev);
2742                        XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
2743                        if (rc) {
2744                                XT_PUTPAGE(pmp);
2745                                XT_PUTPAGE(mp);
2746                                if (rmp)
2747                                        XT_PUTPAGE(rmp);
2748                                return (rc);
2749                        }
2750                }
2751
2752                /* at this point, all xtpages to be updated are in memory */
2753
2754                /*
2755                 * update sibling pointers of sibling xtpages if any;
2756                 */
2757                if (lmp) {
2758                        BT_MARK_DIRTY(lmp, ip);
2759                        tlck = txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
2760                        lp->header.next = cpu_to_le64(nxaddr);
2761                        XT_PUTPAGE(lmp);
2762                }
2763
2764                if (rmp) {
2765                        BT_MARK_DIRTY(rmp, ip);
2766                        tlck = txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
2767                        rp->header.prev = cpu_to_le64(nxaddr);
2768                        XT_PUTPAGE(rmp);
2769                }
2770
2771                /*
2772                 * update the target xtpage to be relocated
2773                 *
2774                 * update the self address of the target page
2775                 * and write to destination extent;
2776                 * redo image covers the whole xtpage since it is new page
2777                 * to the destination extent;
2778                 * update of bmap for the free of source extent
2779                 * of the target xtpage itself:
2780                 * update of bmap for the allocation of destination extent
2781                 * of the target xtpage itself:
2782                 * update of bmap for the extents covered by xad entries in
2783                 * the target xtpage is not necessary since they are not
2784                 * updated;
2785                 * if not committed before this relocation,
2786                 * target page may contain XAD_NEW entries which must
2787                 * be scanned for bmap update (logredo() always
2788                 * scan xtpage REDOPAGE image for bmap update);
2789                 * if committed before this relocation (tlckRELOCATE),
2790                 * scan may be skipped by commit() and logredo();
2791                 */
2792                BT_MARK_DIRTY(mp, ip);
2793                /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
2794                tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
2795                xtlck = (struct xtlock *) & tlck->lock;
2796
2797                /* update the self address in the xtpage header */
2798                pxd = &p->header.self;
2799                PXDaddress(pxd, nxaddr);
2800
2801                /* linelock for the after image of the whole page */
2802                xtlck->lwm.length =
2803                    le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
2804
2805                /* update the buffer extent descriptor of target xtpage */
2806                xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2807                bmSetXD(mp, nxaddr, xsize);
2808
2809                /* unpin the target page to new homeward bound */
2810                XT_PUTPAGE(mp);
2811                jfs_info("xtRelocate: target xtpage relocated.");
2812        }
2813
2814        /*
2815         *      3. acquire maplock for the source extent to be freed;
2816         *
2817         * acquire a maplock saving the src relocated extent address;
2818         * to free of the extent at commit time;
2819         */
2820      out:
2821        /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
2822         * free PXD of the source data extent (logredo() will update
2823         * bmap for free of source data extent), and update bmap for
2824         * free of the source data extent;
2825         */
2826        if (xtype == DATAEXT)
2827                tlck = txMaplock(tid, ip, tlckMAP);
2828        /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
2829         * for the source xtpage (logredo() will init NoRedoPage
2830         * filter and will also update bmap for free of the source
2831         * xtpage), and update bmap for free of the source xtpage;
2832         * N.B. We use tlckMAP instead of tlkcXTREE because there
2833         *      is no buffer associated with this lock since the buffer
2834         *      has been redirected to the target location.
2835         */
2836        else                    /* (xtype == XTPAGE) */
2837                tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
2838
2839        pxdlock = (struct pxd_lock *) & tlck->lock;
2840        pxdlock->flag = mlckFREEPXD;
2841        PXDaddress(&pxdlock->pxd, oxaddr);
2842        PXDlength(&pxdlock->pxd, xlen);
2843        pxdlock->index = 1;
2844
2845        /*
2846         *      4. update the parent xad entry for relocation;
2847         *
2848         * acquire tlck for the parent entry with XAD_NEW as entry
2849         * update which will write LOG_REDOPAGE and update bmap for
2850         * allocation of XAD_NEW destination extent;
2851         */
2852        jfs_info("xtRelocate: update parent xad entry.");
2853        BT_MARK_DIRTY(pmp, ip);
2854        tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
2855        xtlck = (struct xtlock *) & tlck->lock;
2856
2857        /* update the XAD with the new destination extent; */
2858        xad = &pp->xad[index];
2859        xad->flag |= XAD_NEW;
2860        XADaddress(xad, nxaddr);
2861
2862        xtlck->lwm.offset = min(index, xtlck->lwm.offset);
2863        xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
2864            xtlck->lwm.offset;
2865
2866        /* unpin the parent xtpage */
2867        XT_PUTPAGE(pmp);
2868
2869        return rc;
2870}
2871
2872
2873/*
2874 *      xtSearchNode()
2875 *
2876 * function:    search for the internal xad entry covering specified extent.
2877 *              This function is mainly used by defragfs utility.
2878 *
2879 * parameters:
2880 *      ip      - file object;
2881 *      xad     - extent to find;
2882 *      cmpp    - comparison result:
2883 *      btstack - traverse stack;
2884 *      flag    - search process flag;
2885 *
2886 * returns:
2887 *      btstack contains (bn, index) of search path traversed to the entry.
2888 *      *cmpp is set to result of comparison with the entry returned.
2889 *      the page containing the entry is pinned at exit.
2890 */
2891static int xtSearchNode(struct inode *ip, xad_t * xad,  /* required XAD entry */
2892                        int *cmpp, struct btstack * btstack, int flag)
2893{
2894        int rc = 0;
2895        s64 xoff, xaddr;
2896        int xlen;
2897        int cmp = 1;            /* init for empty page */
2898        s64 bn;                 /* block number */
2899        struct metapage *mp;    /* meta-page buffer */
2900        xtpage_t *p;            /* page */
2901        int base, index, lim;
2902        struct btframe *btsp;
2903        s64 t64;
2904
2905        BT_CLR(btstack);
2906
2907        xoff = offsetXAD(xad);
2908        xlen = lengthXAD(xad);
2909        xaddr = addressXAD(xad);
2910
2911        /*
2912         *      search down tree from root:
2913         *
2914         * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
2915         * internal page, child page Pi contains entry with k, Ki <= K < Kj.
2916         *
2917         * if entry with search key K is not found
2918         * internal page search find the entry with largest key Ki
2919         * less than K which point to the child page to search;
2920         * leaf page search find the entry with smallest key Kj
2921         * greater than K so that the returned index is the position of
2922         * the entry to be shifted right for insertion of new entry.
2923         * for empty tree, search key is greater than any key of the tree.
2924         *
2925         * by convention, root bn = 0.
2926         */
2927        for (bn = 0;;) {
2928                /* get/pin the page to search */
2929                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2930                if (rc)
2931                        return rc;
2932                if (p->header.flag & BT_LEAF) {
2933                        XT_PUTPAGE(mp);
2934                        return -ESTALE;
2935                }
2936
2937                lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
2938
2939                /*
2940                 * binary search with search key K on the current page
2941                 */
2942                for (base = XTENTRYSTART; lim; lim >>= 1) {
2943                        index = base + (lim >> 1);
2944
2945                        XT_CMP(cmp, xoff, &p->xad[index], t64);
2946                        if (cmp == 0) {
2947                                /*
2948                                 *      search hit
2949                                 *
2950                                 * verify for exact match;
2951                                 */
2952                                if (xaddr == addressXAD(&p->xad[index]) &&
2953                                    xoff == offsetXAD(&p->xad[index])) {
2954                                        *cmpp = cmp;
2955
2956                                        /* save search result */
2957                                        btsp = btstack->top;
2958                                        btsp->bn = bn;
2959                                        btsp->index = index;
2960                                        btsp->mp = mp;
2961
2962                                        return 0;
2963                                }
2964
2965                                /* descend/search its child page */
2966                                goto next;
2967                        }
2968
2969                        if (cmp > 0) {
2970                                base = index + 1;
2971                                --lim;
2972                        }
2973                }
2974
2975                /*
2976                 *      search miss - non-leaf page:
2977                 *
2978                 * base is the smallest index with key (Kj) greater than
2979                 * search key (K) and may be zero or maxentry index.
2980                 * if base is non-zero, decrement base by one to get the parent
2981                 * entry of the child page to search.
2982                 */
2983                index = base ? base - 1 : base;
2984
2985                /*
2986                 * go down to child page
2987                 */
2988              next:
2989                /* get the child page block number */
2990                bn = addressXAD(&p->xad[index]);
2991
2992                /* unpin the parent page */
2993                XT_PUTPAGE(mp);
2994        }
2995}
2996
2997
2998/*
2999 *      xtRelink()
3000 *
3001 * function:
3002 *      link around a freed page.
3003 *
3004 * Parameter:
3005 *      int             tid,
3006 *      struct inode    *ip,
3007 *      xtpage_t        *p)
3008 *
3009 * returns:
3010 */
3011static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
3012{
3013        int rc = 0;
3014        struct metapage *mp;
3015        s64 nextbn, prevbn;
3016        struct tlock *tlck;
3017
3018        nextbn = le64_to_cpu(p->header.next);
3019        prevbn = le64_to_cpu(p->header.prev);
3020
3021        /* update prev pointer of the next page */
3022        if (nextbn != 0) {
3023                XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3024                if (rc)
3025                        return rc;
3026
3027                /*
3028                 * acquire a transaction lock on the page;
3029                 *
3030                 * action: update prev pointer;
3031                 */
3032                BT_MARK_DIRTY(mp, ip);
3033                tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3034
3035                /* the page may already have been tlock'd */
3036
3037                p->header.prev = cpu_to_le64(prevbn);
3038
3039                XT_PUTPAGE(mp);
3040        }
3041
3042        /* update next pointer of the previous page */
3043        if (prevbn != 0) {
3044                XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3045                if (rc)
3046                        return rc;
3047
3048                /*
3049                 * acquire a transaction lock on the page;
3050                 *
3051                 * action: update next pointer;
3052                 */
3053                BT_MARK_DIRTY(mp, ip);
3054                tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3055
3056                /* the page may already have been tlock'd */
3057
3058                p->header.next = le64_to_cpu(nextbn);
3059
3060                XT_PUTPAGE(mp);
3061        }
3062
3063        return 0;
3064}
3065#endif                          /*  _STILL_TO_PORT */
3066
3067
3068/*
3069 *      xtInitRoot()
3070 *
3071 * initialize file root (inline in inode)
3072 */
3073void xtInitRoot(tid_t tid, struct inode *ip)
3074{
3075        xtpage_t *p;
3076
3077        /*
3078         * acquire a transaction lock on the root
3079         *
3080         * action:
3081         */
3082        txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3083                      tlckXTREE | tlckNEW);
3084        p = &JFS_IP(ip)->i_xtroot;
3085
3086        p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3087        p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3088
3089        if (S_ISDIR(ip->i_mode))
3090                p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3091        else {
3092                p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3093                ip->i_size = 0;
3094        }
3095
3096
3097        return;
3098}
3099
3100
3101/*
3102 * We can run into a deadlock truncating a file with a large number of
3103 * xtree pages (large fragmented file).  A robust fix would entail a
3104 * reservation system where we would reserve a number of metadata pages
3105 * and tlocks which we would be guaranteed without a deadlock.  Without
3106 * this, a partial fix is to limit number of metadata pages we will lock
3107 * in a single transaction.  Currently we will truncate the file so that
3108 * no more than 50 leaf pages will be locked.  The caller of xtTruncate
3109 * will be responsible for ensuring that the current transaction gets
3110 * committed, and that subsequent transactions are created to truncate
3111 * the file further if needed.
3112 */
3113#define MAX_TRUNCATE_LEAVES 50
3114
3115/*
3116 *      xtTruncate()
3117 *
3118 * function:
3119 *      traverse for truncation logging backward bottom up;
3120 *      terminate at the last extent entry at the current subtree
3121 *      root page covering new down size.
3122 *      truncation may occur within the last extent entry.
3123 *
3124 * parameter:
3125 *      int             tid,
3126 *      struct inode    *ip,
3127 *      s64             newsize,
3128 *      int             type)   {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3129 *
3130 * return:
3131 *
3132 * note:
3133 *      PWMAP:
3134 *       1. truncate (non-COMMIT_NOLINK file)
3135 *          by jfs_truncate() or jfs_open(O_TRUNC):
3136 *          xtree is updated;
3137 *       2. truncate index table of directory when last entry removed
3138 *      map update via tlock at commit time;
3139 *      PMAP:
3140 *       Call xtTruncate_pmap instead
3141 *      WMAP:
3142 *       1. remove (free zero link count) on last reference release
3143 *          (pmap has been freed at commit zero link count);
3144 *       2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3145 *          xtree is updated;
3146 *       map update directly at truncation time;
3147 *
3148 *      if (DELETE)
3149 *              no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3150 *      else if (TRUNCATE)
3151 *              must write LOG_NOREDOPAGE for deleted index page;
3152 *
3153 * pages may already have been tlocked by anonymous transactions
3154 * during file growth (i.e., write) before truncation;
3155 *
3156 * except last truncated entry, deleted entries remains as is
3157 * in the page (nextindex is updated) for other use
3158 * (e.g., log/update allocation map): this avoid copying the page
3159 * info but delay free of pages;
3160 *
3161 */
3162s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3163{
3164        int rc = 0;
3165        s64 teof;
3166        struct metapage *mp;
3167        xtpage_t *p;
3168        s64 bn;
3169        int index, nextindex;
3170        xad_t *xad;
3171        s64 xoff, xaddr;
3172        int xlen, len, freexlen;
3173        struct btstack btstack;
3174        struct btframe *parent;
3175        struct tblock *tblk = NULL;
3176        struct tlock *tlck = NULL;
3177        struct xtlock *xtlck = NULL;
3178        struct xdlistlock xadlock;      /* maplock for COMMIT_WMAP */
3179        struct pxd_lock *pxdlock;               /* maplock for COMMIT_WMAP */
3180        s64 nfreed;
3181        int freed, log;
3182        int locked_leaves = 0;
3183
3184        /* save object truncation type */
3185        if (tid) {
3186                tblk = tid_to_tblock(tid);
3187                tblk->xflag |= flag;
3188        }
3189
3190        nfreed = 0;
3191
3192        flag &= COMMIT_MAP;
3193        assert(flag != COMMIT_PMAP);
3194
3195        if (flag == COMMIT_PWMAP)
3196                log = 1;
3197        else {
3198                log = 0;
3199                xadlock.flag = mlckFREEXADLIST;
3200                xadlock.index = 1;
3201        }
3202
3203        /*
3204         * if the newsize is not an integral number of pages,
3205         * the file between newsize and next page boundary will
3206         * be cleared.
3207         * if truncating into a file hole, it will cause
3208         * a full block to be allocated for the logical block.
3209         */
3210
3211        /*
3212         * release page blocks of truncated region <teof, eof>
3213         *
3214         * free the data blocks from the leaf index blocks.
3215         * delete the parent index entries corresponding to
3216         * the freed child data/index blocks.
3217         * free the index blocks themselves which aren't needed
3218         * in new sized file.
3219         *
3220         * index blocks are updated only if the blocks are to be
3221         * retained in the new sized file.
3222         * if type is PMAP, the data and index pages are NOT
3223         * freed, and the data and index blocks are NOT freed
3224         * from working map.
3225         * (this will allow continued access of data/index of
3226         * temporary file (zerolink count file truncated to zero-length)).
3227         */
3228        teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3229            JFS_SBI(ip->i_sb)->l2bsize;
3230
3231        /* clear stack */
3232        BT_CLR(&btstack);
3233
3234        /*
3235         * start with root
3236         *
3237         * root resides in the inode
3238         */
3239        bn = 0;
3240
3241        /*
3242         * first access of each page:
3243         */
3244      getPage:
3245        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3246        if (rc)
3247                return rc;
3248
3249        /* process entries backward from last index */
3250        index = le16_to_cpu(p->header.nextindex) - 1;
3251
3252
3253        /* Since this is the rightmost page at this level, and we may have
3254         * already freed a page that was formerly to the right, let's make
3255         * sure that the next pointer is zero.
3256         */
3257        if (p->header.next) {
3258                if (log)
3259                        /*
3260                         * Make sure this change to the header is logged.
3261                         * If we really truncate this leaf, the flag
3262                         * will be changed to tlckTRUNCATE
3263                         */
3264                        tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
3265                BT_MARK_DIRTY(mp, ip);
3266                p->header.next = 0;
3267        }
3268
3269        if (p->header.flag & BT_INTERNAL)
3270                goto getChild;
3271
3272        /*
3273         *      leaf page
3274         */
3275        freed = 0;
3276
3277        /* does region covered by leaf page precede Teof ? */
3278        xad = &p->xad[index];
3279        xoff = offsetXAD(xad);
3280        xlen = lengthXAD(xad);
3281        if (teof >= xoff + xlen) {
3282                XT_PUTPAGE(mp);
3283                goto getParent;
3284        }
3285
3286        /* (re)acquire tlock of the leaf page */
3287        if (log) {
3288                if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3289                        /*
3290                         * We need to limit the size of the transaction
3291                         * to avoid exhausting pagecache & tlocks
3292                         */
3293                        XT_PUTPAGE(mp);
3294                        newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3295                        goto getParent;
3296                }
3297                tlck = txLock(tid, ip, mp, tlckXTREE);
3298                tlck->type = tlckXTREE | tlckTRUNCATE;
3299                xtlck = (struct xtlock *) & tlck->lock;
3300                xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3301        }
3302        BT_MARK_DIRTY(mp, ip);
3303
3304        /*
3305         * scan backward leaf page entries
3306         */
3307        for (; index >= XTENTRYSTART; index--) {
3308                xad = &p->xad[index];
3309                xoff = offsetXAD(xad);
3310                xlen = lengthXAD(xad);
3311                xaddr = addressXAD(xad);
3312
3313                /*
3314                 * The "data" for a directory is indexed by the block
3315                 * device's address space.  This metadata must be invalidated
3316                 * here
3317                 */
3318                if (S_ISDIR(ip->i_mode) && (teof == 0))
3319                        invalidate_xad_metapages(ip, *xad);
3320                /*
3321                 * entry beyond eof: continue scan of current page
3322                 *          xad
3323                 * ---|---=======------->
3324                 *   eof
3325                 */
3326                if (teof < xoff) {
3327                        nfreed += xlen;
3328                        continue;
3329                }
3330
3331                /*
3332                 * (xoff <= teof): last entry to be deleted from page;
3333                 * If other entries remain in page: keep and update the page.
3334                 */
3335
3336                /*
3337                 * eof == entry_start: delete the entry
3338                 *           xad
3339                 * -------|=======------->
3340                 *       eof
3341                 *
3342                 */
3343                if (teof == xoff) {
3344                        nfreed += xlen;
3345
3346                        if (index == XTENTRYSTART)
3347                                break;
3348
3349                        nextindex = index;
3350                }
3351                /*
3352                 * eof within the entry: truncate the entry.
3353                 *          xad
3354                 * -------===|===------->
3355                 *          eof
3356                 */
3357                else if (teof < xoff + xlen) {
3358                        /* update truncated entry */
3359                        len = teof - xoff;
3360                        freexlen = xlen - len;
3361                        XADlength(xad, len);
3362
3363                        /* save pxd of truncated extent in tlck */
3364                        xaddr += len;
3365                        if (log) {      /* COMMIT_PWMAP */
3366                                xtlck->lwm.offset = (xtlck->lwm.offset) ?
3367                                    min(index, (int)xtlck->lwm.offset) : index;
3368                                xtlck->lwm.length = index + 1 -
3369                                    xtlck->lwm.offset;
3370                                xtlck->twm.offset = index;
3371                                pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3372                                pxdlock->flag = mlckFREEPXD;
3373                                PXDaddress(&pxdlock->pxd, xaddr);
3374                                PXDlength(&pxdlock->pxd, freexlen);
3375                        }
3376                        /* free truncated extent */
3377                        else {  /* COMMIT_WMAP */
3378
3379                                pxdlock = (struct pxd_lock *) & xadlock;
3380                                pxdlock->flag = mlckFREEPXD;
3381                                PXDaddress(&pxdlock->pxd, xaddr);
3382                                PXDlength(&pxdlock->pxd, freexlen);
3383                                txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
3384
3385                                /* reset map lock */
3386                                xadlock.flag = mlckFREEXADLIST;
3387                        }
3388
3389                        /* current entry is new last entry; */
3390                        nextindex = index + 1;
3391
3392                        nfreed += freexlen;
3393                }
3394                /*
3395                 * eof beyond the entry:
3396                 *          xad
3397                 * -------=======---|--->
3398                 *                 eof
3399                 */
3400                else {          /* (xoff + xlen < teof) */
3401
3402                        nextindex = index + 1;
3403                }
3404
3405                if (nextindex < le16_to_cpu(p->header.nextindex)) {
3406                        if (!log) {     /* COMMIT_WAMP */
3407                                xadlock.xdlist = &p->xad[nextindex];
3408                                xadlock.count =
3409                                    le16_to_cpu(p->header.nextindex) -
3410                                    nextindex;
3411                                txFreeMap(ip, (struct maplock *) & xadlock,
3412                                          NULL, COMMIT_WMAP);
3413                        }
3414                        p->header.nextindex = cpu_to_le16(nextindex);
3415                }
3416
3417                XT_PUTPAGE(mp);
3418
3419                /* assert(freed == 0); */
3420                goto getParent;
3421        }                       /* end scan of leaf page entries */
3422
3423        freed = 1;
3424
3425        /*
3426         * leaf page become empty: free the page if type != PMAP
3427         */
3428        if (log) {              /* COMMIT_PWMAP */
3429                /* txCommit() with tlckFREE:
3430                 * free data extents covered by leaf [XTENTRYSTART:hwm);
3431                 * invalidate leaf if COMMIT_PWMAP;
3432                 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3433                 */
3434                tlck->type = tlckXTREE | tlckFREE;
3435        } else {                /* COMMIT_WAMP */
3436
3437                /* free data extents covered by leaf */
3438                xadlock.xdlist = &p->xad[XTENTRYSTART];
3439                xadlock.count =
3440                    le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3441                txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
3442        }
3443
3444        if (p->header.flag & BT_ROOT) {
3445                p->header.flag &= ~BT_INTERNAL;
3446                p->header.flag |= BT_LEAF;
3447                p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3448
3449                XT_PUTPAGE(mp); /* debug */
3450                goto out;
3451        } else {
3452                if (log) {      /* COMMIT_PWMAP */
3453                        /* page will be invalidated at tx completion
3454                         */
3455                        XT_PUTPAGE(mp);
3456                } else {        /* COMMIT_WMAP */
3457
3458                        if (mp->lid)
3459                                lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3460
3461                        /* invalidate empty leaf page */
3462                        discard_metapage(mp);
3463                }
3464        }
3465
3466        /*
3467         * the leaf page become empty: delete the parent entry
3468         * for the leaf page if the parent page is to be kept
3469         * in the new sized file.
3470         */
3471
3472        /*
3473         * go back up to the parent page
3474         */
3475      getParent:
3476        /* pop/restore parent entry for the current child page */
3477        if ((parent = BT_POP(&btstack)) == NULL)
3478                /* current page must have been root */
3479                goto out;
3480
3481        /* get back the parent page */
3482        bn = parent->bn;
3483        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3484        if (rc)
3485                return rc;
3486
3487        index = parent->index;
3488
3489        /*
3490         * child page was not empty:
3491         */
3492        if (freed == 0) {
3493                /* has any entry deleted from parent ? */
3494                if (index < le16_to_cpu(p->header.nextindex) - 1) {
3495                        /* (re)acquire tlock on the parent page */
3496                        if (log) {      /* COMMIT_PWMAP */
3497                                /* txCommit() with tlckTRUNCATE:
3498                                 * free child extents covered by parent [);
3499                                 */
3500                                tlck = txLock(tid, ip, mp, tlckXTREE);
3501                                xtlck = (struct xtlock *) & tlck->lock;
3502                                if (!(tlck->type & tlckTRUNCATE)) {
3503                                        xtlck->hwm.offset =
3504                                            le16_to_cpu(p->header.
3505                                                        nextindex) - 1;
3506                                        tlck->type =
3507                                            tlckXTREE | tlckTRUNCATE;
3508                                }
3509                        } else {        /* COMMIT_WMAP */
3510
3511                                /* free child extents covered by parent */
3512                                xadlock.xdlist = &p->xad[index + 1];
3513                                xadlock.count =
3514                                    le16_to_cpu(p->header.nextindex) -
3515                                    index - 1;
3516                                txFreeMap(ip, (struct maplock *) & xadlock,
3517                                          NULL, COMMIT_WMAP);
3518                        }
3519                        BT_MARK_DIRTY(mp, ip);
3520
3521                        p->header.nextindex = cpu_to_le16(index + 1);
3522                }
3523                XT_PUTPAGE(mp);
3524                goto getParent;
3525        }
3526
3527        /*
3528         * child page was empty:
3529         */
3530        nfreed += lengthXAD(&p->xad[index]);
3531
3532        /*
3533         * During working map update, child page's tlock must be handled
3534         * before parent's.  This is because the parent's tlock will cause
3535         * the child's disk space to be marked available in the wmap, so
3536         * it's important that the child page be released by that time.
3537         *
3538         * ToDo:  tlocks should be on doubly-linked list, so we can
3539         * quickly remove it and add it to the end.
3540         */
3541
3542        /*
3543         * Move parent page's tlock to the end of the tid's tlock list
3544         */
3545        if (log && mp->lid && (tblk->last != mp->lid) &&
3546            lid_to_tlock(mp->lid)->tid) {
3547                lid_t lid = mp->lid;
3548                struct tlock *prev;
3549
3550                tlck = lid_to_tlock(lid);
3551
3552                if (tblk->next == lid)
3553                        tblk->next = tlck->next;
3554                else {
3555                        for (prev = lid_to_tlock(tblk->next);
3556                             prev->next != lid;
3557                             prev = lid_to_tlock(prev->next)) {
3558                                assert(prev->next);
3559                        }
3560                        prev->next = tlck->next;
3561                }
3562                lid_to_tlock(tblk->last)->next = lid;
3563                tlck->next = 0;
3564                tblk->last = lid;
3565        }
3566
3567        /*
3568         * parent page become empty: free the page
3569         */
3570        if (index == XTENTRYSTART) {
3571                if (log) {      /* COMMIT_PWMAP */
3572                        /* txCommit() with tlckFREE:
3573                         * free child extents covered by parent;
3574                         * invalidate parent if COMMIT_PWMAP;
3575                         */
3576                        tlck = txLock(tid, ip, mp, tlckXTREE);
3577                        xtlck = (struct xtlock *) & tlck->lock;
3578                        xtlck->hwm.offset =
3579                            le16_to_cpu(p->header.nextindex) - 1;
3580                        tlck->type = tlckXTREE | tlckFREE;
3581                } else {        /* COMMIT_WMAP */
3582
3583                        /* free child extents covered by parent */
3584                        xadlock.xdlist = &p->xad[XTENTRYSTART];
3585                        xadlock.count =
3586                            le16_to_cpu(p->header.nextindex) -
3587                            XTENTRYSTART;
3588                        txFreeMap(ip, (struct maplock *) & xadlock, NULL,
3589                                  COMMIT_WMAP);
3590                }
3591                BT_MARK_DIRTY(mp, ip);
3592
3593                if (p->header.flag & BT_ROOT) {
3594                        p->header.flag &= ~BT_INTERNAL;
3595                        p->header.flag |= BT_LEAF;
3596                        p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3597                        if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3598                                /*
3599                                 * Shrink root down to allow inline
3600                                 * EA (otherwise fsck complains)
3601                                 */
3602                                p->header.maxentry =
3603                                    cpu_to_le16(XTROOTINITSLOT);
3604                                JFS_IP(ip)->mode2 |= INLINEEA;
3605                        }
3606
3607                        XT_PUTPAGE(mp); /* debug */
3608                        goto out;
3609                } else {
3610                        if (log) {      /* COMMIT_PWMAP */
3611                                /* page will be invalidated at tx completion
3612                                 */
3613                                XT_PUTPAGE(mp);
3614                        } else {        /* COMMIT_WMAP */
3615
3616                                if (mp->lid)
3617                                        lid_to_tlock(mp->lid)->flag |=
3618                                                tlckFREELOCK;
3619
3620                                /* invalidate parent page */
3621                                discard_metapage(mp);
3622                        }
3623
3624                        /* parent has become empty and freed:
3625                         * go back up to its parent page
3626                         */
3627                        /* freed = 1; */
3628                        goto getParent;
3629                }
3630        }
3631        /*
3632         * parent page still has entries for front region;
3633         */
3634        else {
3635                /* try truncate region covered by preceding entry
3636                 * (process backward)
3637                 */
3638                index--;
3639
3640                /* go back down to the child page corresponding
3641                 * to the entry
3642                 */
3643                goto getChild;
3644        }
3645
3646        /*
3647         *      internal page: go down to child page of current entry
3648         */
3649      getChild:
3650        /* save current parent entry for the child page */
3651        if (BT_STACK_FULL(&btstack)) {
3652                jfs_error(ip->i_sb, "stack overrun!\n");
3653                XT_PUTPAGE(mp);
3654                return -EIO;
3655        }
3656        BT_PUSH(&btstack, bn, index);
3657
3658        /* get child page */
3659        xad = &p->xad[index];
3660        bn = addressXAD(xad);
3661
3662        /*
3663         * first access of each internal entry:
3664         */
3665        /* release parent page */
3666        XT_PUTPAGE(mp);
3667
3668        /* process the child page */
3669        goto getPage;
3670
3671      out:
3672        /*
3673         * update file resource stat
3674         */
3675        /* set size
3676         */
3677        if (S_ISDIR(ip->i_mode) && !newsize)
3678                ip->i_size = 1; /* fsck hates zero-length directories */
3679        else
3680                ip->i_size = newsize;
3681
3682        /* update quota allocation to reflect freed blocks */
3683        dquot_free_block(ip, nfreed);
3684
3685        /*
3686         * free tlock of invalidated pages
3687         */
3688        if (flag == COMMIT_WMAP)
3689                txFreelock(ip);
3690
3691        return newsize;
3692}
3693
3694
3695/*
3696 *      xtTruncate_pmap()
3697 *
3698 * function:
3699 *      Perform truncate to zero length for deleted file, leaving the
3700 *      the xtree and working map untouched.  This allows the file to
3701 *      be accessed via open file handles, while the delete of the file
3702 *      is committed to disk.
3703 *
3704 * parameter:
3705 *      tid_t           tid,
3706 *      struct inode    *ip,
3707 *      s64             committed_size)
3708 *
3709 * return: new committed size
3710 *
3711 * note:
3712 *
3713 *      To avoid deadlock by holding too many transaction locks, the
3714 *      truncation may be broken up into multiple transactions.
3715 *      The committed_size keeps track of part of the file has been
3716 *      freed from the pmaps.
3717 */
3718s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3719{
3720        s64 bn;
3721        struct btstack btstack;
3722        int cmp;
3723        int index;
3724        int locked_leaves = 0;
3725        struct metapage *mp;
3726        xtpage_t *p;
3727        struct btframe *parent;
3728        int rc;
3729        struct tblock *tblk;
3730        struct tlock *tlck = NULL;
3731        xad_t *xad;
3732        int xlen;
3733        s64 xoff;
3734        struct xtlock *xtlck = NULL;
3735
3736        /* save object truncation type */
3737        tblk = tid_to_tblock(tid);
3738        tblk->xflag |= COMMIT_PMAP;
3739
3740        /* clear stack */
3741        BT_CLR(&btstack);
3742
3743        if (committed_size) {
3744                xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
3745                rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
3746                if (rc)
3747                        return rc;
3748
3749                XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3750
3751                if (cmp != 0) {
3752                        XT_PUTPAGE(mp);
3753                        jfs_error(ip->i_sb, "did not find extent\n");
3754                        return -EIO;
3755                }
3756        } else {
3757                /*
3758                 * start with root
3759                 *
3760                 * root resides in the inode
3761                 */
3762                bn = 0;
3763
3764                /*
3765                 * first access of each page:
3766                 */
3767      getPage:
3768                XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3769                if (rc)
3770                        return rc;
3771
3772                /* process entries backward from last index */
3773                index = le16_to_cpu(p->header.nextindex) - 1;
3774
3775                if (p->header.flag & BT_INTERNAL)
3776                        goto getChild;
3777        }
3778
3779        /*
3780         *      leaf page
3781         */
3782
3783        if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3784                /*
3785                 * We need to limit the size of the transaction
3786                 * to avoid exhausting pagecache & tlocks
3787                 */
3788                xad = &p->xad[index];
3789                xoff = offsetXAD(xad);
3790                xlen = lengthXAD(xad);
3791                XT_PUTPAGE(mp);
3792                return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3793        }
3794        tlck = txLock(tid, ip, mp, tlckXTREE);
3795        tlck->type = tlckXTREE | tlckFREE;
3796        xtlck = (struct xtlock *) & tlck->lock;
3797        xtlck->hwm.offset = index;
3798
3799
3800        XT_PUTPAGE(mp);
3801
3802        /*
3803         * go back up to the parent page
3804         */
3805      getParent:
3806        /* pop/restore parent entry for the current child page */
3807        if ((parent = BT_POP(&btstack)) == NULL)
3808                /* current page must have been root */
3809                goto out;
3810
3811        /* get back the parent page */
3812        bn = parent->bn;
3813        XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3814        if (rc)
3815                return rc;
3816
3817        index = parent->index;
3818
3819        /*
3820         * parent page become empty: free the page
3821         */
3822        if (index == XTENTRYSTART) {
3823                /* txCommit() with tlckFREE:
3824                 * free child extents covered by parent;
3825                 * invalidate parent if COMMIT_PWMAP;
3826                 */
3827                tlck = txLock(tid, ip, mp, tlckXTREE);
3828                xtlck = (struct xtlock *) & tlck->lock;
3829                xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3830                tlck->type = tlckXTREE | tlckFREE;
3831
3832                XT_PUTPAGE(mp);
3833
3834                if (p->header.flag & BT_ROOT) {
3835
3836                        goto out;
3837                } else {
3838                        goto getParent;
3839                }
3840        }
3841        /*
3842         * parent page still has entries for front region;
3843         */
3844        else
3845                index--;
3846        /*
3847         *      internal page: go down to child page of current entry
3848         */
3849      getChild:
3850        /* save current parent entry for the child page */
3851        if (BT_STACK_FULL(&btstack)) {
3852                jfs_error(ip->i_sb, "stack overrun!\n");
3853                XT_PUTPAGE(mp);
3854                return -EIO;
3855        }
3856        BT_PUSH(&btstack, bn, index);
3857
3858        /* get child page */
3859        xad = &p->xad[index];
3860        bn = addressXAD(xad);
3861
3862        /*
3863         * first access of each internal entry:
3864         */
3865        /* release parent page */
3866        XT_PUTPAGE(mp);
3867
3868        /* process the child page */
3869        goto getPage;
3870
3871      out:
3872
3873        return 0;
3874}
3875
3876#ifdef CONFIG_JFS_STATISTICS
3877int jfs_xtstat_proc_show(struct seq_file *m, void *v)
3878{
3879        seq_printf(m,
3880                       "JFS Xtree statistics\n"
3881                       "====================\n"
3882                       "searches = %d\n"
3883                       "fast searches = %d\n"
3884                       "splits = %d\n",
3885                       xtStat.search,
3886                       xtStat.fastSearch,
3887                       xtStat.split);
3888        return 0;
3889}
3890#endif
3891