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