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