fs/jfs/jfs_xtree.c

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