fs/jfs/jfs_xtree.c

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