fs/jfs/jfs_xtree.c

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