fs/jfs/jfs_xtree.c

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