fs/jfs/jfs_xtree.c

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