2 * Copyright (C) International Business Machines Corp., 2000-2003
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.
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.
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
19 * jfs_xtree.c: extent allocation descriptor B+-tree manager
23 #include "jfs_incore.h"
24 #include "jfs_filsys.h"
25 #include "jfs_metapage.h"
27 #include "jfs_dinode.h"
28 #include "jfs_superblock.h"
29 #include "jfs_debug.h"
34 #define XT_INSERT 0x00000001
37 * xtree key/entry comparison: extent offset
40 * -1: k < start of extent
41 * 0: start_of_extent <= k <= end_of_extent
42 * 1: k > end_of_extent
44 #define XT_CMP(CMP, K, X, OFFSET64)\
46 OFFSET64 = offsetXAD(X);\
47 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
48 ((K) < OFFSET64) ? -1 : 0;\
51 /* write a xad entry */
52 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
54 (XAD)->flag = (FLAG);\
55 XADoffset((XAD), (OFF));\
56 XADlength((XAD), (LEN));\
57 XADaddress((XAD), (ADDR));\
60 #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
62 /* get page buffer for specified block address */
63 /* ToDo: Replace this ugly macro with a function */
64 #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
66 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
69 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
70 (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
71 (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
73 jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
82 #define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
84 #define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
85 BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
86 /* xtree entry parameter descriptor */
94 struct pxdlist *pxdlist;
101 #ifdef CONFIG_JFS_STATISTICS
113 static int xtSearch(struct inode *ip,
114 s64 xoff, int *cmpp, struct btstack * btstack, int flag);
116 static int xtSplitUp(tid_t tid,
118 struct xtsplit * split, struct btstack * btstack);
120 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
121 struct metapage ** rmpp, s64 * rbnp);
123 static int xtSplitRoot(tid_t tid, struct inode *ip,
124 struct xtsplit * split, struct metapage ** rmpp);
126 #ifdef _STILL_TO_PORT
127 static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
128 xtpage_t * fp, struct btstack * btstack);
130 static int xtSearchNode(struct inode *ip,
132 int *cmpp, struct btstack * btstack, int flag);
134 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
135 #endif /* _STILL_TO_PORT */
137 /* External references */
142 /* #define _JFS_DEBUG_XTREE 1 */
148 * function: map a single page into a physical extent;
150 int xtLookup(struct inode *ip, s64 lstart,
151 s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
154 struct btstack btstack;
161 s64 size, xoff, xend;
168 /* is lookup offset beyond eof ? */
169 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
170 JFS_SBI(ip->i_sb)->l2bsize;
171 if (lstart >= size) {
172 jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
173 (ulong) lstart, (ulong) size);
179 * search for the xad entry covering the logical extent
182 if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0))) {
183 jfs_err("xtLookup: xtSearch returned %d", rc);
188 * compute the physical extent covering logical extent
190 * N.B. search may have failed (e.g., hole in sparse file),
191 * and returned the index of the next entry.
193 /* retrieve search result */
194 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
196 /* is xad found covering start of logical extent ?
197 * lstart is a page start address,
198 * i.e., lstart cannot start in a hole;
206 xad = &p->xad[index];
207 xoff = offsetXAD(xad);
208 xlen = lengthXAD(xad);
210 xaddr = addressXAD(xad);
212 /* initialize new pxd */
214 *paddr = xaddr + (lstart - xoff);
215 /* a page must be fully covered by an xad */
216 *plen = min(xend - lstart, llen);
228 * function: map a single logical extent into a list of physical extent;
232 * struct lxdlist *lxdlist, lxd list (in)
233 * struct xadlist *xadlist, xad list (in/out)
236 * coverage of lxd by xad under assumption of
237 * . lxd's are ordered and disjoint.
238 * . xad's are ordered and disjoint.
243 * note: a page being written (even a single byte) is backed fully,
244 * except the last page which is only backed with blocks
245 * required to cover the last byte;
246 * the extent backing a page is fully contained within an xad;
248 int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
249 struct xadlist * xadlist, int flag)
252 struct btstack btstack;
260 s64 size, lstart, lend, xstart, xend, pstart;
261 s64 llen, xlen, plen;
263 int nlxd, npxd, maxnpxd;
265 npxd = xadlist->nxad = 0;
266 maxnpxd = xadlist->maxnxad;
269 nlxd = lxdlist->nlxd;
272 lstart = offsetLXD(lxd);
273 llen = lengthLXD(lxd);
274 lend = lstart + llen;
276 size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
277 JFS_SBI(ip->i_sb)->l2bsize;
280 * search for the xad entry covering the logical extent
286 if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0)))
290 * compute the physical extent covering logical extent
292 * N.B. search may have failed (e.g., hole in sparse file),
293 * and returned the index of the next entry.
296 /* retrieve search result */
297 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
299 /* is xad on the next sibling page ? */
300 if (index == le16_to_cpu(p->header.nextindex)) {
301 if (p->header.flag & BT_ROOT)
304 if ((bn = le64_to_cpu(p->header.next)) == 0)
309 /* get next sibling page */
310 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
314 index = XTENTRYSTART;
317 xad = &p->xad[index];
320 * is lxd covered by xad ?
323 xstart = offsetXAD(xad);
324 xlen = lengthXAD(xad);
325 xend = xstart + xlen;
326 xaddr = addressXAD(xad);
332 /* (lstart <= xstart) */
334 /* lxd is NOT covered by xad */
335 if (lend <= xstart) {
343 lstart = offsetLXD(lxd);
344 llen = lengthLXD(lxd);
345 lend = lstart + llen;
349 /* compare with the current xad */
352 /* lxd is covered by xad */
353 else { /* (xstart < lend) */
355 /* initialize new pxd */
357 plen = min(lend - xstart, xlen);
363 /* (xstart < lstart) */
365 /* lxd is covered by xad */
367 /* initialize new pxd */
369 plen = min(xend - lstart, llen);
370 paddr = xaddr + (lstart - xstart);
374 /* lxd is NOT covered by xad */
375 else { /* (xend <= lstart) */
380 * linear search next xad covering lxd on
381 * the current xad page, and then tree search
383 if (index == le16_to_cpu(p->header.nextindex) - 1) {
384 if (p->header.flag & BT_ROOT)
393 /* compare with new xad */
399 * lxd is covered by xad and a new pxd has been initialized
400 * (lstart <= xstart < lend) or (xstart < lstart < xend)
403 /* finalize pxd corresponding to current xad */
404 XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);
406 if (++npxd >= maxnpxd)
411 * lxd is fully covered by xad
421 lstart = offsetLXD(lxd);
422 llen = lengthLXD(lxd);
423 lend = lstart + llen;
428 * test for old xad covering new lxd
429 * (old xstart < new lstart)
434 * lxd is partially covered by xad
436 else { /* (xend < lend) */
441 * linear search next xad covering lxd on
442 * the current xad page, and then next xad page search
444 if (index == le16_to_cpu(p->header.nextindex) - 1) {
445 if (p->header.flag & BT_ROOT)
448 if ((bn = le64_to_cpu(p->header.next)) == 0)
453 /* get next sibling page */
454 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
458 index = XTENTRYSTART;
459 xad = &p->xad[index];
466 * test for new xad covering old lxd
467 * (old lstart < new xstart)
473 xadlist->nxad = npxd;
485 * function: search for the xad entry covering specified offset.
489 * xoff - extent offset;
490 * cmpp - comparison result:
491 * btstack - traverse stack;
492 * flag - search process flag (XT_INSERT);
495 * btstack contains (bn, index) of search path traversed to the entry.
496 * *cmpp is set to result of comparison with the entry returned.
497 * the page containing the entry is pinned at exit.
499 static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
500 int *cmpp, struct btstack * btstack, int flag)
502 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
504 int cmp = 1; /* init for empty page */
505 s64 bn; /* block number */
506 struct metapage *mp; /* page buffer */
507 xtpage_t *p; /* page */
509 int base, index, lim, btindex;
510 struct btframe *btsp;
511 int nsplit = 0; /* number of pages to split */
514 INCREMENT(xtStat.search);
521 * search down tree from root:
523 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
524 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
526 * if entry with search key K is not found
527 * internal page search find the entry with largest key Ki
528 * less than K which point to the child page to search;
529 * leaf page search find the entry with smallest key Kj
530 * greater than K so that the returned index is the position of
531 * the entry to be shifted right for insertion of new entry.
532 * for empty tree, search key is greater than any key of the tree.
534 * by convention, root bn = 0.
537 /* get/pin the page to search */
538 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
542 /* try sequential access heuristics with the previous
543 * access entry in target leaf page:
544 * once search narrowed down into the target leaf,
545 * key must either match an entry in the leaf or
546 * key entry does not exist in the tree;
549 if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
550 (p->header.flag & BT_LEAF) &&
551 (index = jfs_ip->btindex) <
552 le16_to_cpu(p->header.nextindex)) {
553 xad = &p->xad[index];
554 t64 = offsetXAD(xad);
555 if (xoff < t64 + lengthXAD(xad)) {
561 /* stop sequential access heuristics */
563 } else { /* (t64 + lengthXAD(xad)) <= xoff */
565 /* try next sequential entry */
568 le16_to_cpu(p->header.nextindex)) {
570 t64 = offsetXAD(xad);
571 if (xoff < t64 + lengthXAD(xad)) {
577 /* miss: key falls between
578 * previous and this entry
584 /* (xoff >= t64 + lengthXAD(xad));
585 * matching entry may be further out:
586 * stop heuristic search
588 /* stop sequential access heuristics */
592 /* (index == p->header.nextindex);
593 * miss: key entry does not exist in
594 * the target leaf/tree
601 * if hit, return index of the entry found, and
602 * if miss, where new entry with search key is
606 /* compute number of pages to split */
607 if (flag & XT_INSERT) {
608 if (p->header.nextindex == /* little-endian */
613 btstack->nsplit = nsplit;
616 /* save search result */
622 /* update sequential access heuristics */
623 jfs_ip->btindex = index;
625 INCREMENT(xtStat.fastSearch);
629 /* well, ... full search now */
631 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
634 * binary search with search key K on the current page
636 for (base = XTENTRYSTART; lim; lim >>= 1) {
637 index = base + (lim >> 1);
639 XT_CMP(cmp, xoff, &p->xad[index], t64);
644 /* search hit - leaf page:
645 * return the entry found
647 if (p->header.flag & BT_LEAF) {
650 /* compute number of pages to split */
651 if (flag & XT_INSERT) {
652 if (p->header.nextindex ==
657 btstack->nsplit = nsplit;
660 /* save search result */
666 /* init sequential access heuristics */
667 btindex = jfs_ip->btindex;
668 if (index == btindex ||
669 index == btindex + 1)
670 jfs_ip->btorder = BT_SEQUENTIAL;
672 jfs_ip->btorder = BT_RANDOM;
673 jfs_ip->btindex = index;
678 /* search hit - internal page:
679 * descend/search its child page
693 * base is the smallest index with key (Kj) greater than
694 * search key (K) and may be zero or maxentry index.
697 * search miss - leaf page:
699 * return location of entry (base) where new entry with
700 * search key K is to be inserted.
702 if (p->header.flag & BT_LEAF) {
705 /* compute number of pages to split */
706 if (flag & XT_INSERT) {
707 if (p->header.nextindex ==
712 btstack->nsplit = nsplit;
715 /* save search result */
721 /* init sequential access heuristics */
722 btindex = jfs_ip->btindex;
723 if (base == btindex || base == btindex + 1)
724 jfs_ip->btorder = BT_SEQUENTIAL;
726 jfs_ip->btorder = BT_RANDOM;
727 jfs_ip->btindex = base;
733 * search miss - non-leaf page:
735 * if base is non-zero, decrement base by one to get the parent
736 * entry of the child page to search.
738 index = base ? base - 1 : base;
741 * go down to child page
744 /* update number of pages to split */
745 if (p->header.nextindex == p->header.maxentry)
750 /* push (bn, index) of the parent page/entry */
751 BT_PUSH(btstack, bn, index);
753 /* get the child page block number */
754 bn = addressXAD(&p->xad[index]);
756 /* unpin the parent page */
767 * tid - transaction id;
769 * xflag - extent flag (XAD_NOTRECORDED):
770 * xoff - extent offset;
771 * xlen - extent length;
772 * xaddrp - extent address pointer (in/out):
774 * caller allocated data extent at *xaddrp;
776 * allocate data extent and return its xaddr;
781 int xtInsert(tid_t tid, /* transaction id */
782 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
787 struct metapage *mp; /* meta-page buffer */
788 xtpage_t *p; /* base B+-tree index page */
790 int index, nextindex;
791 struct btstack btstack; /* traverse stack */
792 struct xtsplit split; /* split information */
796 struct xtlock *xtlck;
798 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
801 * search for the entry location at which to insert:
803 * xtFastSearch() and xtSearch() both returns (leaf page
804 * pinned, index at which to insert).
805 * n.b. xtSearch() may return index of maxentry of
808 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
811 /* retrieve search result */
812 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
814 /* This test must follow XT_GETSEARCH since mp must be valid if
815 * we branch to out: */
822 * allocate data extent requested
824 * allocation hint: last xad
826 if ((xaddr = *xaddrp) == 0) {
827 if (index > XTENTRYSTART) {
828 xad = &p->xad[index - 1];
829 hint = addressXAD(xad) + lengthXAD(xad) - 1;
832 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr)))
837 * insert entry for new extent
842 * if the leaf page is full, split the page and
843 * propagate up the router entry for the new page from split
845 * The xtSplitUp() will insert the entry and unpin the leaf page.
847 nextindex = le16_to_cpu(p->header.nextindex);
848 if (nextindex == le16_to_cpu(p->header.maxentry)) {
855 split.pxdlist = NULL;
856 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
857 /* undo data extent allocation */
859 dbFree(ip, xaddr, (s64) xlen);
868 * insert the new entry into the leaf page
871 * acquire a transaction lock on the leaf page;
873 * action: xad insertion/extension;
875 BT_MARK_DIRTY(mp, ip);
877 /* if insert into middle, shift right remaining entries. */
878 if (index < nextindex)
879 memmove(&p->xad[index + 1], &p->xad[index],
880 (nextindex - index) * sizeof(xad_t));
882 /* insert the new entry: mark the entry NEW */
883 xad = &p->xad[index];
884 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
886 /* advance next available entry index */
887 p->header.nextindex =
888 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
890 /* Don't log it if there are no links to the file */
891 if (!test_cflag(COMMIT_Nolink, ip)) {
892 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
893 xtlck = (struct xtlock *) & tlck->lock;
895 (xtlck->lwm.offset) ? min(index,
896 (int)xtlck->lwm.offset) : index;
898 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
904 /* unpin the leaf page */
915 * split full pages as propagating insertion up the tree
918 * tid - transaction id;
920 * split - entry parameter descriptor;
921 * btstack - traverse stack from xtSearch()
927 struct inode *ip, struct xtsplit * split, struct btstack * btstack)
930 struct metapage *smp;
931 xtpage_t *sp; /* split page */
932 struct metapage *rmp;
933 s64 rbn; /* new right page block number */
934 struct metapage *rcmp;
935 xtpage_t *rcp; /* right child page */
936 s64 rcbn; /* right child page block number */
937 int skip; /* index of entry of insertion */
938 int nextindex; /* next available entry index of p */
939 struct btframe *parent; /* parent page entry on traverse stack */
943 int nsplit; /* number of pages split */
944 struct pxdlist pxdlist;
947 struct xtlock *xtlck;
950 sp = XT_PAGE(ip, smp);
952 /* is inode xtree root extension/inline EA area free ? */
953 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
954 (sp->header.maxentry < cpu_to_le16(XTROOTMAXSLOT)) &&
955 (JFS_IP(ip)->mode2 & INLINEEA)) {
956 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
957 JFS_IP(ip)->mode2 &= ~INLINEEA;
959 BT_MARK_DIRTY(smp, ip);
961 * acquire a transaction lock on the leaf page;
963 * action: xad insertion/extension;
966 /* if insert into middle, shift right remaining entries. */
968 nextindex = le16_to_cpu(sp->header.nextindex);
969 if (skip < nextindex)
970 memmove(&sp->xad[skip + 1], &sp->xad[skip],
971 (nextindex - skip) * sizeof(xad_t));
973 /* insert the new entry: mark the entry NEW */
974 xad = &sp->xad[skip];
975 XT_PUTENTRY(xad, split->flag, split->off, split->len,
978 /* advance next available entry index */
979 sp->header.nextindex =
980 cpu_to_le16(le16_to_cpu(sp->header.nextindex) + 1);
982 /* Don't log it if there are no links to the file */
983 if (!test_cflag(COMMIT_Nolink, ip)) {
984 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
985 xtlck = (struct xtlock *) & tlck->lock;
986 xtlck->lwm.offset = (xtlck->lwm.offset) ?
987 min(skip, (int)xtlck->lwm.offset) : skip;
989 le16_to_cpu(sp->header.nextindex) -
997 * allocate new index blocks to cover index page split(s)
1001 if (split->pxdlist == NULL) {
1002 nsplit = btstack->nsplit;
1003 split->pxdlist = &pxdlist;
1004 pxdlist.maxnpxd = pxdlist.npxd = 0;
1005 pxd = &pxdlist.pxd[0];
1006 xlen = JFS_SBI(ip->i_sb)->nbperpage;
1007 for (; nsplit > 0; nsplit--, pxd++) {
1008 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
1010 PXDaddress(pxd, xaddr);
1011 PXDlength(pxd, xlen);
1018 /* undo allocation */
1026 * Split leaf page <sp> into <sp> and a new right page <rp>.
1028 * The split routines insert the new entry into the leaf page,
1029 * and acquire txLock as appropriate.
1030 * return <rp> pinned and its block number <rpbn>.
1032 rc = (sp->header.flag & BT_ROOT) ?
1033 xtSplitRoot(tid, ip, split, &rmp) :
1034 xtSplitPage(tid, ip, split, &rmp, &rbn);
1041 * propagate up the router entry for the leaf page just split
1043 * insert a router entry for the new page into the parent page,
1044 * propagate the insert/split up the tree by walking back the stack
1045 * of (bn of parent page, index of child page entry in parent page)
1046 * that were traversed during the search for the page that split.
1048 * the propagation of insert/split up the tree stops if the root
1049 * splits or the page inserted into doesn't have to split to hold
1052 * the parent entry for the split page remains the same, and
1053 * a new entry is inserted at its right with the first key and
1054 * block number of the new right page.
1056 * There are a maximum of 3 pages pinned at any time:
1057 * right child, left parent and right parent (when the parent splits)
1058 * to keep the child page pinned while working on the parent.
1059 * make sure that all pins are released at exit.
1061 while ((parent = BT_POP(btstack)) != NULL) {
1062 /* parent page specified by stack frame <parent> */
1064 /* keep current child pages <rcp> pinned */
1067 rcp = XT_PAGE(ip, rcmp);
1070 * insert router entry in parent for new right child page <rp>
1072 /* get/pin the parent page <sp> */
1073 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
1080 * The new key entry goes ONE AFTER the index of parent entry,
1081 * because the split was to the right.
1083 skip = parent->index + 1;
1086 * split or shift right remaining entries of the parent page
1088 nextindex = le16_to_cpu(sp->header.nextindex);
1090 * parent page is full - split the parent page
1092 if (nextindex == le16_to_cpu(sp->header.maxentry)) {
1093 /* init for parent page split */
1095 split->index = skip; /* index at insert */
1096 split->flag = XAD_NEW;
1097 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
1098 split->len = JFS_SBI(ip->i_sb)->nbperpage;
1101 /* unpin previous right child page */
1104 /* The split routines insert the new entry,
1105 * and acquire txLock as appropriate.
1106 * return <rp> pinned and its block number <rpbn>.
1108 rc = (sp->header.flag & BT_ROOT) ?
1109 xtSplitRoot(tid, ip, split, &rmp) :
1110 xtSplitPage(tid, ip, split, &rmp, &rbn);
1117 /* keep new child page <rp> pinned */
1120 * parent page is not full - insert in parent page
1124 * insert router entry in parent for the right child
1125 * page from the first entry of the right child page:
1128 * acquire a transaction lock on the parent page;
1130 * action: router xad insertion;
1132 BT_MARK_DIRTY(smp, ip);
1135 * if insert into middle, shift right remaining entries
1137 if (skip < nextindex)
1138 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1140 skip) << L2XTSLOTSIZE);
1142 /* insert the router entry */
1143 xad = &sp->xad[skip];
1144 XT_PUTENTRY(xad, XAD_NEW,
1145 offsetXAD(&rcp->xad[XTENTRYSTART]),
1146 JFS_SBI(ip->i_sb)->nbperpage, rcbn);
1148 /* advance next available entry index. */
1149 sp->header.nextindex =
1150 cpu_to_le16(le16_to_cpu(sp->header.nextindex) +
1153 /* Don't log it if there are no links to the file */
1154 if (!test_cflag(COMMIT_Nolink, ip)) {
1155 tlck = txLock(tid, ip, smp,
1156 tlckXTREE | tlckGROW);
1157 xtlck = (struct xtlock *) & tlck->lock;
1158 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1159 min(skip, (int)xtlck->lwm.offset) : skip;
1161 le16_to_cpu(sp->header.nextindex) -
1165 /* unpin parent page */
1168 /* exit propagate up */
1173 /* unpin current right page */
1184 * split a full non-root page into
1185 * original/split/left page and new right page
1186 * i.e., the original/split page remains as left page.
1191 * struct xtsplit *split,
1192 * struct metapage **rmpp,
1196 * Pointer to page in which to insert or NULL on error.
1199 xtSplitPage(tid_t tid, struct inode *ip,
1200 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
1203 struct metapage *smp;
1205 struct metapage *rmp;
1206 xtpage_t *rp; /* new right page allocated */
1207 s64 rbn; /* new right page block number */
1208 struct metapage *mp;
1211 int skip, maxentry, middle, righthalf, n;
1213 struct pxdlist *pxdlist;
1216 struct xtlock *sxtlck = NULL, *rxtlck = NULL;
1219 sp = XT_PAGE(ip, smp);
1221 INCREMENT(xtStat.split);
1224 * allocate the new right page for the split
1226 pxdlist = split->pxdlist;
1227 pxd = &pxdlist->pxd[pxdlist->npxd];
1229 rbn = addressPXD(pxd);
1230 rmp = get_metapage(ip, rbn, PSIZE, 1);
1234 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1236 BT_MARK_DIRTY(rmp, ip);
1241 rp = (xtpage_t *) rmp->data;
1242 rp->header.self = *pxd;
1243 rp->header.flag = sp->header.flag & BT_TYPE;
1244 rp->header.maxentry = sp->header.maxentry; /* little-endian */
1245 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1247 BT_MARK_DIRTY(smp, ip);
1248 /* Don't log it if there are no links to the file */
1249 if (!test_cflag(COMMIT_Nolink, ip)) {
1251 * acquire a transaction lock on the new right page;
1253 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1254 rxtlck = (struct xtlock *) & tlck->lock;
1255 rxtlck->lwm.offset = XTENTRYSTART;
1257 * acquire a transaction lock on the split page
1259 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1260 sxtlck = (struct xtlock *) & tlck->lock;
1264 * initialize/update sibling pointers of <sp> and <rp>
1266 nextbn = le64_to_cpu(sp->header.next);
1267 rp->header.next = cpu_to_le64(nextbn);
1268 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1269 sp->header.next = cpu_to_le64(rbn);
1271 skip = split->index;
1274 * sequential append at tail (after last entry of last page)
1276 * if splitting the last page on a level because of appending
1277 * a entry to it (skip is maxentry), it's likely that the access is
1278 * sequential. adding an empty page on the side of the level is less
1279 * work and can push the fill factor much higher than normal.
1280 * if we're wrong it's no big deal - we will do the split the right
1282 * (it may look like it's equally easy to do a similar hack for
1283 * reverse sorted data, that is, split the tree left, but it's not.
1286 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1288 * acquire a transaction lock on the new/right page;
1290 * action: xad insertion;
1292 /* insert entry at the first entry of the new right page */
1293 xad = &rp->xad[XTENTRYSTART];
1294 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1297 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1299 if (!test_cflag(COMMIT_Nolink, ip)) {
1300 /* rxtlck->lwm.offset = XTENTRYSTART; */
1301 rxtlck->lwm.length = 1;
1307 ip->i_blocks += LBLK2PBLK(ip->i_sb, lengthPXD(pxd));
1309 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1314 * non-sequential insert (at possibly middle page)
1318 * update previous pointer of old next/right page of <sp>
1321 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1327 BT_MARK_DIRTY(mp, ip);
1329 * acquire a transaction lock on the next page;
1331 * action:sibling pointer update;
1333 if (!test_cflag(COMMIT_Nolink, ip))
1334 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1336 p->header.prev = cpu_to_le64(rbn);
1338 /* sibling page may have been updated previously, or
1339 * it may be updated later;
1346 * split the data between the split and new/right pages
1348 maxentry = le16_to_cpu(sp->header.maxentry);
1349 middle = maxentry >> 1;
1350 righthalf = maxentry - middle;
1353 * skip index in old split/left page - insert into left page:
1355 if (skip <= middle) {
1356 /* move right half of split page to the new right page */
1357 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1358 righthalf << L2XTSLOTSIZE);
1360 /* shift right tail of left half to make room for new entry */
1362 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1363 (middle - skip) << L2XTSLOTSIZE);
1365 /* insert new entry */
1366 xad = &sp->xad[skip];
1367 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1370 /* update page header */
1371 sp->header.nextindex = cpu_to_le16(middle + 1);
1372 if (!test_cflag(COMMIT_Nolink, ip)) {
1373 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1374 min(skip, (int)sxtlck->lwm.offset) : skip;
1377 rp->header.nextindex =
1378 cpu_to_le16(XTENTRYSTART + righthalf);
1381 * skip index in new right page - insert into right page:
1384 /* move left head of right half to right page */
1386 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1389 /* insert new entry */
1392 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1395 /* move right tail of right half to right page */
1396 if (skip < maxentry)
1397 memmove(&rp->xad[n + 1], &sp->xad[skip],
1398 (maxentry - skip) << L2XTSLOTSIZE);
1400 /* update page header */
1401 sp->header.nextindex = cpu_to_le16(middle);
1402 if (!test_cflag(COMMIT_Nolink, ip)) {
1403 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1404 min(middle, (int)sxtlck->lwm.offset) : middle;
1407 rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1411 if (!test_cflag(COMMIT_Nolink, ip)) {
1412 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1415 /* rxtlck->lwm.offset = XTENTRYSTART; */
1416 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1423 ip->i_blocks += LBLK2PBLK(ip->i_sb, lengthPXD(pxd));
1425 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1434 * split the full root page into
1435 * original/root/split page and new right page
1436 * i.e., root remains fixed in tree anchor (inode) and
1437 * the root is copied to a single new right child page
1438 * since root page << non-root page, and
1439 * the split root page contains a single entry for the
1440 * new right child page.
1445 * struct xtsplit *split,
1446 * struct metapage **rmpp)
1449 * Pointer to page in which to insert or NULL on error.
1452 xtSplitRoot(tid_t tid,
1453 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1456 struct metapage *rmp;
1459 int skip, nextindex;
1462 struct pxdlist *pxdlist;
1464 struct xtlock *xtlck;
1466 sp = &JFS_IP(ip)->i_xtroot;
1468 INCREMENT(xtStat.split);
1471 * allocate a single (right) child page
1473 pxdlist = split->pxdlist;
1474 pxd = &pxdlist->pxd[pxdlist->npxd];
1476 rbn = addressPXD(pxd);
1477 rmp = get_metapage(ip, rbn, PSIZE, 1);
1481 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1484 * acquire a transaction lock on the new right page;
1488 BT_MARK_DIRTY(rmp, ip);
1490 rp = (xtpage_t *) rmp->data;
1492 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1493 rp->header.self = *pxd;
1494 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1495 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1497 /* initialize sibling pointers */
1498 rp->header.next = 0;
1499 rp->header.prev = 0;
1502 * copy the in-line root page into new right page extent
1504 nextindex = le16_to_cpu(sp->header.maxentry);
1505 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1506 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1509 * insert the new entry into the new right/child page
1510 * (skip index in the new right page will not change)
1512 skip = split->index;
1513 /* if insert into middle, shift right remaining entries */
1514 if (skip != nextindex)
1515 memmove(&rp->xad[skip + 1], &rp->xad[skip],
1516 (nextindex - skip) * sizeof(xad_t));
1518 xad = &rp->xad[skip];
1519 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1521 /* update page header */
1522 rp->header.nextindex = cpu_to_le16(nextindex + 1);
1524 if (!test_cflag(COMMIT_Nolink, ip)) {
1525 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1526 xtlck = (struct xtlock *) & tlck->lock;
1527 xtlck->lwm.offset = XTENTRYSTART;
1528 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1535 * init root with the single entry for the new right page
1536 * set the 1st entry offset to 0, which force the left-most key
1537 * at any level of the tree to be less than any search key.
1540 * acquire a transaction lock on the root page (in-memory inode);
1542 * action: root split;
1544 BT_MARK_DIRTY(split->mp, ip);
1546 xad = &sp->xad[XTENTRYSTART];
1547 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1549 /* update page header of root */
1550 sp->header.flag &= ~BT_LEAF;
1551 sp->header.flag |= BT_INTERNAL;
1553 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1555 if (!test_cflag(COMMIT_Nolink, ip)) {
1556 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1557 xtlck = (struct xtlock *) & tlck->lock;
1558 xtlck->lwm.offset = XTENTRYSTART;
1559 xtlck->lwm.length = 1;
1564 ip->i_blocks += LBLK2PBLK(ip->i_sb, lengthPXD(pxd));
1566 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1574 * function: extend in-place;
1576 * note: existing extent may or may not have been committed.
1577 * caller is responsible for pager buffer cache update, and
1578 * working block allocation map update;
1579 * update pmap: alloc whole extended extent;
1581 int xtExtend(tid_t tid, /* transaction id */
1582 struct inode *ip, s64 xoff, /* delta extent offset */
1583 s32 xlen, /* delta extent length */
1588 struct metapage *mp; /* meta-page buffer */
1589 xtpage_t *p; /* base B+-tree index page */
1591 int index, nextindex, len;
1592 struct btstack btstack; /* traverse stack */
1593 struct xtsplit split; /* split information */
1597 struct xtlock *xtlck = NULL;
1600 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1602 /* there must exist extent to be extended */
1603 if ((rc = xtSearch(ip, xoff - 1, &cmp, &btstack, XT_INSERT)))
1606 /* retrieve search result */
1607 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1611 jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
1615 /* extension must be contiguous */
1616 xad = &p->xad[index];
1617 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1619 jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
1624 * acquire a transaction lock on the leaf page;
1626 * action: xad insertion/extension;
1628 BT_MARK_DIRTY(mp, ip);
1629 if (!test_cflag(COMMIT_Nolink, ip)) {
1630 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1631 xtlck = (struct xtlock *) & tlck->lock;
1634 /* extend will overflow extent ? */
1635 xlen = lengthXAD(xad) + xlen;
1636 if ((len = xlen - MAXXLEN) <= 0)
1640 * extent overflow: insert entry for new extent
1643 xoff = offsetXAD(xad) + MAXXLEN;
1644 xaddr = addressXAD(xad) + MAXXLEN;
1645 nextindex = le16_to_cpu(p->header.nextindex);
1648 * if the leaf page is full, insert the new entry and
1649 * propagate up the router entry for the new page from split
1651 * The xtSplitUp() will insert the entry and unpin the leaf page.
1653 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1654 rootsplit = p->header.flag & BT_ROOT;
1656 /* xtSpliUp() unpins leaf pages */
1658 split.index = index + 1;
1659 split.flag = XAD_NEW;
1660 split.off = xoff; /* split offset */
1663 split.pxdlist = NULL;
1664 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1668 * if leaf root has been split, original root has been
1669 * copied to new child page, i.e., original entry now
1670 * resides on the new child page;
1673 ASSERT(p->header.nextindex ==
1674 cpu_to_le16(XTENTRYSTART + 1));
1675 xad = &p->xad[XTENTRYSTART];
1676 bn = addressXAD(xad);
1678 /* get new child page */
1679 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1683 BT_MARK_DIRTY(mp, ip);
1684 if (!test_cflag(COMMIT_Nolink, ip)) {
1685 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1686 xtlck = (struct xtlock *) & tlck->lock;
1689 /* get back old page */
1690 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1696 * insert the new entry into the leaf page
1699 /* insert the new entry: mark the entry NEW */
1700 xad = &p->xad[index + 1];
1701 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1703 /* advance next available entry index */
1704 p->header.nextindex =
1705 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1708 /* get back old entry */
1709 xad = &p->xad[index];
1716 XADlength(xad, xlen);
1717 if (!(xad->flag & XAD_NEW))
1718 xad->flag |= XAD_EXTENDED;
1720 if (!test_cflag(COMMIT_Nolink, ip)) {
1722 (xtlck->lwm.offset) ? min(index,
1723 (int)xtlck->lwm.offset) : index;
1725 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1728 /* unpin the leaf page */
1738 * function: split existing 'tail' extent
1739 * (split offset >= start offset of tail extent), and
1740 * relocate and extend the split tail half;
1742 * note: existing extent may or may not have been committed.
1743 * caller is responsible for pager buffer cache update, and
1744 * working block allocation map update;
1745 * update pmap: free old split tail extent, alloc new extent;
1747 int xtTailgate(tid_t tid, /* transaction id */
1748 struct inode *ip, s64 xoff, /* split/new extent offset */
1749 s32 xlen, /* new extent length */
1750 s64 xaddr, /* new extent address */
1755 struct metapage *mp; /* meta-page buffer */
1756 xtpage_t *p; /* base B+-tree index page */
1758 int index, nextindex, llen, rlen;
1759 struct btstack btstack; /* traverse stack */
1760 struct xtsplit split; /* split information */
1763 struct xtlock *xtlck = 0;
1764 struct tlock *mtlck;
1765 struct maplock *pxdlock;
1769 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1770 (ulong)xoff, xlen, (ulong)xaddr);
1773 /* there must exist extent to be tailgated */
1774 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
1777 /* retrieve search result */
1778 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1782 jfs_error(ip->i_sb, "xtTailgate: couldn't find extent");
1786 /* entry found must be last entry */
1787 nextindex = le16_to_cpu(p->header.nextindex);
1788 if (index != nextindex - 1) {
1791 "xtTailgate: the entry found is not the last entry");
1795 BT_MARK_DIRTY(mp, ip);
1797 * acquire tlock of the leaf page containing original entry
1799 if (!test_cflag(COMMIT_Nolink, ip)) {
1800 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1801 xtlck = (struct xtlock *) & tlck->lock;
1804 /* completely replace extent ? */
1805 xad = &p->xad[index];
1807 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1808 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1810 if ((llen = xoff - offsetXAD(xad)) == 0)
1814 * partially replace extent: insert entry for new extent
1818 * if the leaf page is full, insert the new entry and
1819 * propagate up the router entry for the new page from split
1821 * The xtSplitUp() will insert the entry and unpin the leaf page.
1823 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1824 rootsplit = p->header.flag & BT_ROOT;
1826 /* xtSpliUp() unpins leaf pages */
1828 split.index = index + 1;
1829 split.flag = XAD_NEW;
1830 split.off = xoff; /* split offset */
1833 split.pxdlist = NULL;
1834 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1838 * if leaf root has been split, original root has been
1839 * copied to new child page, i.e., original entry now
1840 * resides on the new child page;
1843 ASSERT(p->header.nextindex ==
1844 cpu_to_le16(XTENTRYSTART + 1));
1845 xad = &p->xad[XTENTRYSTART];
1846 bn = addressXAD(xad);
1848 /* get new child page */
1849 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1853 BT_MARK_DIRTY(mp, ip);
1854 if (!test_cflag(COMMIT_Nolink, ip)) {
1855 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1856 xtlck = (struct xtlock *) & tlck->lock;
1859 /* get back old page */
1860 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1866 * insert the new entry into the leaf page
1869 /* insert the new entry: mark the entry NEW */
1870 xad = &p->xad[index + 1];
1871 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1873 /* advance next available entry index */
1874 p->header.nextindex =
1875 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1878 /* get back old XAD */
1879 xad = &p->xad[index];
1882 * truncate/relocate old extent at split offset
1885 /* update dmap for old/committed/truncated extent */
1886 rlen = lengthXAD(xad) - llen;
1887 if (!(xad->flag & XAD_NEW)) {
1888 /* free from PWMAP at commit */
1889 if (!test_cflag(COMMIT_Nolink, ip)) {
1890 mtlck = txMaplock(tid, ip, tlckMAP);
1891 pxdlock = (struct maplock *) & mtlck->lock;
1892 pxdlock->flag = mlckFREEPXD;
1893 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1894 PXDlength(&pxdlock->pxd, rlen);
1898 /* free from WMAP */
1899 dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1903 XADlength(xad, llen);
1906 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1908 if (!test_cflag(COMMIT_Nolink, ip)) {
1909 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1910 min(index, (int)xtlck->lwm.offset) : index;
1911 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1915 /* unpin the leaf page */
1920 #endif /* _NOTYET */
1925 * function: update XAD;
1927 * update extent for allocated_but_not_recorded or
1928 * compressed extent;
1932 * logical extent of the specified XAD must be completely
1933 * contained by an existing XAD;
1935 int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1939 struct metapage *mp; /* meta-page buffer */
1940 xtpage_t *p; /* base B+-tree index page */
1942 int index0, index, newindex, nextindex;
1943 struct btstack btstack; /* traverse stack */
1944 struct xtsplit split; /* split information */
1945 xad_t *xad, *lxad, *rxad;
1948 int nxlen, xlen, lxlen, rxlen;
1951 struct xtlock *xtlck = NULL;
1952 int rootsplit = 0, newpage = 0;
1954 /* there must exist extent to be tailgated */
1955 nxoff = offsetXAD(nxad);
1956 nxlen = lengthXAD(nxad);
1957 nxaddr = addressXAD(nxad);
1959 if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT)))
1962 /* retrieve search result */
1963 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1967 jfs_error(ip->i_sb, "xtUpdate: Could not find extent");
1971 BT_MARK_DIRTY(mp, ip);
1973 * acquire tlock of the leaf page containing original entry
1975 if (!test_cflag(COMMIT_Nolink, ip)) {
1976 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1977 xtlck = (struct xtlock *) & tlck->lock;
1980 xad = &p->xad[index0];
1982 xoff = offsetXAD(xad);
1983 xlen = lengthXAD(xad);
1984 xaddr = addressXAD(xad);
1986 /* nXAD must be completely contained within XAD */
1987 if ((xoff > nxoff) ||
1988 (nxoff + nxlen > xoff + xlen)) {
1991 "xtUpdate: nXAD in not completely contained within XAD");
1996 newindex = index + 1;
1997 nextindex = le16_to_cpu(p->header.nextindex);
1999 #ifdef _JFS_WIP_NOCOALESCE
2004 * replace XAD with nXAD
2006 replace: /* (nxoff == xoff) */
2007 if (nxlen == xlen) {
2008 /* replace XAD with nXAD:recorded */
2010 xad->flag = xflag & ~XAD_NOTRECORDED;
2013 } else /* (nxlen < xlen) */
2015 #endif /* _JFS_WIP_NOCOALESCE */
2017 /* #ifdef _JFS_WIP_COALESCE */
2022 * coalesce with left XAD
2024 //coalesceLeft: /* (xoff == nxoff) */
2025 /* is XAD first entry of page ? */
2026 if (index == XTENTRYSTART)
2029 /* is nXAD logically and physically contiguous with lXAD ? */
2030 lxad = &p->xad[index - 1];
2031 lxlen = lengthXAD(lxad);
2032 if (!(lxad->flag & XAD_NOTRECORDED) &&
2033 (nxoff == offsetXAD(lxad) + lxlen) &&
2034 (nxaddr == addressXAD(lxad) + lxlen) &&
2035 (lxlen + nxlen < MAXXLEN)) {
2036 /* extend right lXAD */
2038 XADlength(lxad, lxlen + nxlen);
2040 /* If we just merged two extents together, need to make sure the
2041 * right extent gets logged. If the left one is marked XAD_NEW,
2042 * then we know it will be logged. Otherwise, mark as
2045 if (!(lxad->flag & XAD_NEW))
2046 lxad->flag |= XAD_EXTENDED;
2050 XADoffset(xad, xoff + nxlen);
2051 XADlength(xad, xlen - nxlen);
2052 XADaddress(xad, xaddr + nxlen);
2054 } else { /* (xlen == nxlen) */
2057 if (index < nextindex - 1)
2058 memmove(&p->xad[index], &p->xad[index + 1],
2059 (nextindex - index -
2060 1) << L2XTSLOTSIZE);
2062 p->header.nextindex =
2063 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2067 newindex = index + 1;
2068 nextindex = le16_to_cpu(p->header.nextindex);
2069 xoff = nxoff = offsetXAD(lxad);
2070 xlen = nxlen = lxlen + nxlen;
2071 xaddr = nxaddr = addressXAD(lxad);
2077 * replace XAD with nXAD
2079 replace: /* (nxoff == xoff) */
2080 if (nxlen == xlen) {
2081 /* replace XAD with nXAD:recorded */
2083 xad->flag = xflag & ~XAD_NOTRECORDED;
2086 } else /* (nxlen < xlen) */
2090 * coalesce with right XAD
2092 coalesceRight: /* (xoff <= nxoff) */
2093 /* is XAD last entry of page ? */
2094 if (newindex == nextindex) {
2100 /* is nXAD logically and physically contiguous with rXAD ? */
2101 rxad = &p->xad[index + 1];
2102 rxlen = lengthXAD(rxad);
2103 if (!(rxad->flag & XAD_NOTRECORDED) &&
2104 (nxoff + nxlen == offsetXAD(rxad)) &&
2105 (nxaddr + nxlen == addressXAD(rxad)) &&
2106 (rxlen + nxlen < MAXXLEN)) {
2107 /* extend left rXAD */
2108 XADoffset(rxad, nxoff);
2109 XADlength(rxad, rxlen + nxlen);
2110 XADaddress(rxad, nxaddr);
2112 /* If we just merged two extents together, need to make sure
2113 * the left extent gets logged. If the right one is marked
2114 * XAD_NEW, then we know it will be logged. Otherwise, mark as
2117 if (!(rxad->flag & XAD_NEW))
2118 rxad->flag |= XAD_EXTENDED;
2122 XADlength(xad, xlen - nxlen);
2123 else { /* (xlen == nxlen) */
2126 memmove(&p->xad[index], &p->xad[index + 1],
2127 (nextindex - index - 1) << L2XTSLOTSIZE);
2129 p->header.nextindex =
2130 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2135 } else if (xoff == nxoff)
2138 if (xoff >= nxoff) {
2140 jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff");
2143 /* #endif _JFS_WIP_COALESCE */
2146 * split XAD into (lXAD, nXAD):
2149 * --|----------XAD----------|--
2152 updateRight: /* (xoff < nxoff) */
2153 /* truncate old XAD as lXAD:not_recorded */
2154 xad = &p->xad[index];
2155 XADlength(xad, nxoff - xoff);
2157 /* insert nXAD:recorded */
2158 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2159 rootsplit = p->header.flag & BT_ROOT;
2161 /* xtSpliUp() unpins leaf pages */
2163 split.index = newindex;
2164 split.flag = xflag & ~XAD_NOTRECORDED;
2167 split.addr = nxaddr;
2168 split.pxdlist = NULL;
2169 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2173 * if leaf root has been split, original root has been
2174 * copied to new child page, i.e., original entry now
2175 * resides on the new child page;
2178 ASSERT(p->header.nextindex ==
2179 cpu_to_le16(XTENTRYSTART + 1));
2180 xad = &p->xad[XTENTRYSTART];
2181 bn = addressXAD(xad);
2183 /* get new child page */
2184 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2188 BT_MARK_DIRTY(mp, ip);
2189 if (!test_cflag(COMMIT_Nolink, ip)) {
2190 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2191 xtlck = (struct xtlock *) & tlck->lock;
2194 /* get back old page */
2195 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2199 /* is nXAD on new page ? */
2201 (le16_to_cpu(p->header.maxentry) >> 1)) {
2204 le16_to_cpu(p->header.nextindex) +
2210 /* if insert into middle, shift right remaining entries */
2211 if (newindex < nextindex)
2212 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2213 (nextindex - newindex) << L2XTSLOTSIZE);
2215 /* insert the entry */
2216 xad = &p->xad[newindex];
2218 xad->flag = xflag & ~XAD_NOTRECORDED;
2220 /* advance next available entry index. */
2221 p->header.nextindex =
2222 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2226 * does nXAD force 3-way split ?
2229 * --|----------XAD-------------|--
2230 * |-lXAD-| |-rXAD -|
2232 if (nxoff + nxlen == xoff + xlen)
2235 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2237 /* close out old page */
2238 if (!test_cflag(COMMIT_Nolink, ip)) {
2239 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2240 min(index0, (int)xtlck->lwm.offset) : index0;
2242 le16_to_cpu(p->header.nextindex) -
2246 bn = le64_to_cpu(p->header.next);
2249 /* get new right page */
2250 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2254 BT_MARK_DIRTY(mp, ip);
2255 if (!test_cflag(COMMIT_Nolink, ip)) {
2256 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2257 xtlck = (struct xtlock *) & tlck->lock;
2260 index0 = index = newindex;
2264 newindex = index + 1;
2265 nextindex = le16_to_cpu(p->header.nextindex);
2266 xlen = xlen - (nxoff - xoff);
2270 /* recompute split pages */
2271 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2274 if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT)))
2277 /* retrieve search result */
2278 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2282 jfs_error(ip->i_sb, "xtUpdate: xtSearch failed");
2286 if (index0 != index) {
2289 "xtUpdate: unexpected value of index");
2295 * split XAD into (nXAD, rXAD)
2298 * --|----------XAD----------|--
2301 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
2302 /* update old XAD with nXAD:recorded */
2303 xad = &p->xad[index];
2305 xad->flag = xflag & ~XAD_NOTRECORDED;
2307 /* insert rXAD:not_recorded */
2308 xoff = xoff + nxlen;
2309 xlen = xlen - nxlen;
2310 xaddr = xaddr + nxlen;
2311 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2312 rootsplit = p->header.flag & BT_ROOT;
2315 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2317 /* xtSpliUp() unpins leaf pages */
2319 split.index = newindex;
2324 split.pxdlist = NULL;
2325 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2329 * if leaf root has been split, original root has been
2330 * copied to new child page, i.e., original entry now
2331 * resides on the new child page;
2334 ASSERT(p->header.nextindex ==
2335 cpu_to_le16(XTENTRYSTART + 1));
2336 xad = &p->xad[XTENTRYSTART];
2337 bn = addressXAD(xad);
2339 /* get new child page */
2340 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2344 BT_MARK_DIRTY(mp, ip);
2345 if (!test_cflag(COMMIT_Nolink, ip)) {
2346 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2347 xtlck = (struct xtlock *) & tlck->lock;
2350 /* get back old page */
2351 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2356 /* if insert into middle, shift right remaining entries */
2357 if (newindex < nextindex)
2358 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2359 (nextindex - newindex) << L2XTSLOTSIZE);
2361 /* insert the entry */
2362 xad = &p->xad[newindex];
2363 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2365 /* advance next available entry index. */
2366 p->header.nextindex =
2367 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2371 if (!test_cflag(COMMIT_Nolink, ip)) {
2372 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2373 min(index0, (int)xtlck->lwm.offset) : index0;
2374 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2378 /* unpin the leaf page */
2388 * function: grow in append mode from contiguous region specified ;
2391 * tid - transaction id;
2393 * xflag - extent flag:
2394 * xoff - extent offset;
2395 * maxblocks - max extent length;
2396 * xlen - extent length (in/out);
2397 * xaddrp - extent address pointer (in/out):
2402 int xtAppend(tid_t tid, /* transaction id */
2403 struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2404 s32 * xlenp, /* (in/out) */
2405 s64 * xaddrp, /* (in/out) */
2409 struct metapage *mp; /* meta-page buffer */
2410 xtpage_t *p; /* base B+-tree index page */
2412 int index, nextindex;
2413 struct btstack btstack; /* traverse stack */
2414 struct xtsplit split; /* split information */
2418 struct xtlock *xtlck;
2419 int nsplit, nblocks, xlen;
2420 struct pxdlist pxdlist;
2425 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2426 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2429 * search for the entry location at which to insert:
2431 * xtFastSearch() and xtSearch() both returns (leaf page
2432 * pinned, index at which to insert).
2433 * n.b. xtSearch() may return index of maxentry of
2436 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
2439 /* retrieve search result */
2440 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2448 * insert entry for new extent
2453 * if the leaf page is full, split the page and
2454 * propagate up the router entry for the new page from split
2456 * The xtSplitUp() will insert the entry and unpin the leaf page.
2458 nextindex = le16_to_cpu(p->header.nextindex);
2459 if (nextindex < le16_to_cpu(p->header.maxentry))
2463 * allocate new index blocks to cover index page split(s)
2465 nsplit = btstack.nsplit;
2466 split.pxdlist = &pxdlist;
2467 pxdlist.maxnpxd = pxdlist.npxd = 0;
2468 pxd = &pxdlist.pxd[0];
2469 nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2470 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2471 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2472 PXDaddress(pxd, xaddr);
2473 PXDlength(pxd, nblocks);
2480 /* undo allocation */
2485 xlen = min(xlen, maxblocks);
2488 * allocate data extent requested
2490 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2494 split.index = index;
2499 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2500 /* undo data extent allocation */
2501 dbFree(ip, *xaddrp, (s64) * xlenp);
2511 * insert the new entry into the leaf page
2515 * allocate data extent requested
2517 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2520 BT_MARK_DIRTY(mp, ip);
2522 * acquire a transaction lock on the leaf page;
2524 * action: xad insertion/extension;
2526 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2527 xtlck = (struct xtlock *) & tlck->lock;
2529 /* insert the new entry: mark the entry NEW */
2530 xad = &p->xad[index];
2531 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2533 /* advance next available entry index */
2534 p->header.nextindex =
2535 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2538 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2539 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2546 /* unpin the leaf page */
2551 #ifdef _STILL_TO_PORT
2553 /* - TBD for defragmentaion/reorganization -
2558 * delete the entry with the specified key.
2560 * N.B.: whole extent of the entry is assumed to be deleted.
2565 * ENOENT: if the entry is not found.
2569 int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2572 struct btstack btstack;
2575 struct metapage *mp;
2577 int index, nextindex;
2579 struct xtlock *xtlck;
2582 * find the matching entry; xtSearch() pins the page
2584 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0)))
2587 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2589 /* unpin the leaf page */
2595 * delete the entry from the leaf page
2597 nextindex = le16_to_cpu(p->header.nextindex);
2598 p->header.nextindex =
2599 cpu_to_le16(le16_to_cpu(p->header.nextindex) - 1);
2602 * if the leaf page bocome empty, free the page
2604 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2605 return (xtDeleteUp(tid, ip, mp, p, &btstack));
2607 BT_MARK_DIRTY(mp, ip);
2609 * acquire a transaction lock on the leaf page;
2611 * action:xad deletion;
2613 tlck = txLock(tid, ip, mp, tlckXTREE);
2614 xtlck = (struct xtlock *) & tlck->lock;
2616 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2618 /* if delete from middle, shift left/compact the remaining entries */
2619 if (index < nextindex - 1)
2620 memmove(&p->xad[index], &p->xad[index + 1],
2621 (nextindex - index - 1) * sizeof(xad_t));
2629 /* - TBD for defragmentaion/reorganization -
2634 * free empty pages as propagating deletion up the tree
2641 xtDeleteUp(tid_t tid, struct inode *ip,
2642 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2645 struct metapage *mp;
2647 int index, nextindex;
2650 struct btframe *parent;
2652 struct xtlock *xtlck;
2655 * keep root leaf page which has become empty
2657 if (fp->header.flag & BT_ROOT) {
2658 /* keep the root page */
2659 fp->header.flag &= ~BT_INTERNAL;
2660 fp->header.flag |= BT_LEAF;
2661 fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2663 /* XT_PUTPAGE(fmp); */
2669 * free non-root leaf page
2671 if ((rc = xtRelink(tid, ip, fp))) {
2676 xaddr = addressPXD(&fp->header.self);
2677 xlen = lengthPXD(&fp->header.self);
2678 /* free the page extent */
2679 dbFree(ip, xaddr, (s64) xlen);
2681 /* free the buffer page */
2682 discard_metapage(fmp);
2685 * propagate page deletion up the index tree
2687 * If the delete from the parent page makes it empty,
2688 * continue all the way up the tree.
2689 * stop if the root page is reached (which is never deleted) or
2690 * if the entry deletion does not empty the page.
2692 while ((parent = BT_POP(btstack)) != NULL) {
2693 /* get/pin the parent page <sp> */
2694 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2698 index = parent->index;
2700 /* delete the entry for the freed child page from parent.
2702 nextindex = le16_to_cpu(p->header.nextindex);
2705 * the parent has the single entry being deleted:
2706 * free the parent page which has become empty.
2708 if (nextindex == 1) {
2709 if (p->header.flag & BT_ROOT) {
2710 /* keep the root page */
2711 p->header.flag &= ~BT_INTERNAL;
2712 p->header.flag |= BT_LEAF;
2713 p->header.nextindex =
2714 cpu_to_le16(XTENTRYSTART);
2716 /* XT_PUTPAGE(mp); */
2720 /* free the parent page */
2721 if ((rc = xtRelink(tid, ip, p)))
2724 xaddr = addressPXD(&p->header.self);
2725 /* free the page extent */
2727 (s64) JFS_SBI(ip->i_sb)->nbperpage);
2729 /* unpin/free the buffer page */
2730 discard_metapage(mp);
2737 * the parent has other entries remaining:
2738 * delete the router entry from the parent page.
2741 BT_MARK_DIRTY(mp, ip);
2743 * acquire a transaction lock on the leaf page;
2745 * action:xad deletion;
2747 tlck = txLock(tid, ip, mp, tlckXTREE);
2748 xtlck = (struct xtlock *) & tlck->lock;
2750 (xtlck->lwm.offset) ? min(index,
2754 /* if delete from middle,
2755 * shift left/compact the remaining entries in the page
2757 if (index < nextindex - 1)
2758 memmove(&p->xad[index], &p->xad[index + 1],
2759 (nextindex - index -
2760 1) << L2XTSLOTSIZE);
2762 p->header.nextindex =
2763 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2765 jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2766 (ulong) parent->bn, index);
2769 /* unpin the parent page */
2772 /* exit propagation up */
2781 * NAME: xtRelocate()
2783 * FUNCTION: relocate xtpage or data extent of regular file;
2784 * This function is mainly used by defragfs utility.
2786 * NOTE: This routine does not have the logic to handle
2787 * uncommitted allocated extent. The caller should call
2788 * txCommit() to commit all the allocation before call
2792 xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2793 s64 nxaddr, /* new xaddr */
2795 { /* extent type: XTPAGE or DATAEXT */
2797 struct tblock *tblk;
2799 struct xtlock *xtlck;
2800 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
2801 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
2806 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2808 s64 offset, nbytes, nbrd, pno;
2809 int nb, npages, nblks;
2813 struct pxd_lock *pxdlock;
2814 struct btstack btstack; /* traverse stack */
2816 xtype = xtype & EXTENT_TYPE;
2818 xoff = offsetXAD(oxad);
2819 oxaddr = addressXAD(oxad);
2820 xlen = lengthXAD(oxad);
2822 /* validate extent offset */
2823 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2824 if (offset >= ip->i_size)
2825 return -ESTALE; /* stale extent */
2827 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2828 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2831 * 1. get and validate the parent xtpage/xad entry
2832 * covering the source extent to be relocated;
2834 if (xtype == DATAEXT) {
2835 /* search in leaf entry */
2836 rc = xtSearch(ip, xoff, &cmp, &btstack, 0);
2840 /* retrieve search result */
2841 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2848 /* validate for exact match with a single entry */
2849 xad = &pp->xad[index];
2850 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2854 } else { /* (xtype == XTPAGE) */
2856 /* search in internal entry */
2857 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2861 /* retrieve search result */
2862 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2869 /* xtSearchNode() validated for exact match with a single entry
2871 xad = &pp->xad[index];
2873 jfs_info("xtRelocate: parent xad entry validated.");
2876 * 2. relocate the extent
2878 if (xtype == DATAEXT) {
2879 /* if the extent is allocated-but-not-recorded
2880 * there is no real data to be moved in this extent,
2882 if (xad->flag & XAD_NOTRECORDED)
2885 /* release xtpage for cmRead()/xtLookup() */
2891 * copy target data pages to be relocated;
2893 * data extent must start at page boundary and
2894 * multiple of page size (except the last data extent);
2895 * read in each page of the source data extent into cbuf,
2896 * update the cbuf extent descriptor of the page to be
2897 * homeward bound to new dst data extent
2898 * copy the data from the old extent to new extent.
2899 * copy is essential for compressed files to avoid problems
2900 * that can arise if there was a change in compression
2902 * it is a good strategy because it may disrupt cache
2903 * policy to keep the pages in memory afterwards.
2905 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2906 assert((offset & CM_OFFSET) == 0);
2907 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2908 pno = offset >> CM_L2BSIZE;
2909 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2911 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2912 (offset >> CM_L2BSIZE) + 1;
2917 /* process the request one cache buffer at a time */
2918 for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2919 offset += nb, pno++, npages--) {
2920 /* compute page size */
2921 nb = min(nbytes - nbrd, CM_BSIZE);
2923 /* get the cache buffer of the page */
2924 if (rc = cmRead(ip, offset, npages, &cp))
2927 assert(addressPXD(&cp->cm_pxd) == sxaddr);
2928 assert(!cp->cm_modified);
2930 /* bind buffer with the new extent address */
2931 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2932 cmSetXD(ip, cp, pno, dxaddr, nblks);
2934 /* release the cbuf, mark it as modified */
2941 /* get back parent page */
2942 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0)))
2945 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2946 jfs_info("xtRelocate: target data extent relocated.");
2947 } else { /* (xtype == XTPAGE) */
2950 * read in the target xtpage from the source extent;
2952 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2959 * read in sibling pages if any to update sibling pointers;
2962 if (p->header.next) {
2963 nextbn = le64_to_cpu(p->header.next);
2964 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
2973 if (p->header.prev) {
2974 prevbn = le64_to_cpu(p->header.prev);
2975 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
2985 /* at this point, all xtpages to be updated are in memory */
2988 * update sibling pointers of sibling xtpages if any;
2991 BT_MARK_DIRTY(lmp, ip);
2993 txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
2994 lp->header.next = cpu_to_le64(nxaddr);
2999 BT_MARK_DIRTY(rmp, ip);
3001 txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
3002 rp->header.prev = cpu_to_le64(nxaddr);
3007 * update the target xtpage to be relocated
3009 * update the self address of the target page
3010 * and write to destination extent;
3011 * redo image covers the whole xtpage since it is new page
3012 * to the destination extent;
3013 * update of bmap for the free of source extent
3014 * of the target xtpage itself:
3015 * update of bmap for the allocation of destination extent
3016 * of the target xtpage itself:
3017 * update of bmap for the extents covered by xad entries in
3018 * the target xtpage is not necessary since they are not
3020 * if not committed before this relocation,
3021 * target page may contain XAD_NEW entries which must
3022 * be scanned for bmap update (logredo() always
3023 * scan xtpage REDOPAGE image for bmap update);
3024 * if committed before this relocation (tlckRELOCATE),
3025 * scan may be skipped by commit() and logredo();
3027 BT_MARK_DIRTY(mp, ip);
3028 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
3029 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
3030 xtlck = (struct xtlock *) & tlck->lock;
3032 /* update the self address in the xtpage header */
3033 pxd = &p->header.self;
3034 PXDaddress(pxd, nxaddr);
3036 /* linelock for the after image of the whole page */
3038 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
3040 /* update the buffer extent descriptor of target xtpage */
3041 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
3042 bmSetXD(mp, nxaddr, xsize);
3044 /* unpin the target page to new homeward bound */
3046 jfs_info("xtRelocate: target xtpage relocated.");
3050 * 3. acquire maplock for the source extent to be freed;
3052 * acquire a maplock saving the src relocated extent address;
3053 * to free of the extent at commit time;
3056 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
3057 * free PXD of the source data extent (logredo() will update
3058 * bmap for free of source data extent), and update bmap for
3059 * free of the source data extent;
3061 if (xtype == DATAEXT)
3062 tlck = txMaplock(tid, ip, tlckMAP);
3063 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
3064 * for the source xtpage (logredo() will init NoRedoPage
3065 * filter and will also update bmap for free of the source
3066 * xtpage), and update bmap for free of the source xtpage;
3067 * N.B. We use tlckMAP instead of tlkcXTREE because there
3068 * is no buffer associated with this lock since the buffer
3069 * has been redirected to the target location.
3071 else /* (xtype == XTPAGE) */
3072 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
3074 pxdlock = (struct pxd_lock *) & tlck->lock;
3075 pxdlock->flag = mlckFREEPXD;
3076 PXDaddress(&pxdlock->pxd, oxaddr);
3077 PXDlength(&pxdlock->pxd, xlen);
3081 * 4. update the parent xad entry for relocation;
3083 * acquire tlck for the parent entry with XAD_NEW as entry
3084 * update which will write LOG_REDOPAGE and update bmap for
3085 * allocation of XAD_NEW destination extent;
3087 jfs_info("xtRelocate: update parent xad entry.");
3088 BT_MARK_DIRTY(pmp, ip);
3089 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
3090 xtlck = (struct xtlock *) & tlck->lock;
3092 /* update the XAD with the new destination extent; */
3093 xad = &pp->xad[index];
3094 xad->flag |= XAD_NEW;
3095 XADaddress(xad, nxaddr);
3097 xtlck->lwm.offset = min(index, xtlck->lwm.offset);
3098 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
3101 /* unpin the parent xtpage */
3111 * function: search for the internal xad entry covering specified extent.
3112 * This function is mainly used by defragfs utility.
3116 * xad - extent to find;
3117 * cmpp - comparison result:
3118 * btstack - traverse stack;
3119 * flag - search process flag;
3122 * btstack contains (bn, index) of search path traversed to the entry.
3123 * *cmpp is set to result of comparison with the entry returned.
3124 * the page containing the entry is pinned at exit.
3126 static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
3127 int *cmpp, struct btstack * btstack, int flag)
3132 int cmp = 1; /* init for empty page */
3133 s64 bn; /* block number */
3134 struct metapage *mp; /* meta-page buffer */
3135 xtpage_t *p; /* page */
3136 int base, index, lim;
3137 struct btframe *btsp;
3142 xoff = offsetXAD(xad);
3143 xlen = lengthXAD(xad);
3144 xaddr = addressXAD(xad);
3147 * search down tree from root:
3149 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
3150 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
3152 * if entry with search key K is not found
3153 * internal page search find the entry with largest key Ki
3154 * less than K which point to the child page to search;
3155 * leaf page search find the entry with smallest key Kj
3156 * greater than K so that the returned index is the position of
3157 * the entry to be shifted right for insertion of new entry.
3158 * for empty tree, search key is greater than any key of the tree.
3160 * by convention, root bn = 0.
3163 /* get/pin the page to search */
3164 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3167 if (p->header.flag & BT_LEAF) {
3172 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3175 * binary search with search key K on the current page
3177 for (base = XTENTRYSTART; lim; lim >>= 1) {
3178 index = base + (lim >> 1);
3180 XT_CMP(cmp, xoff, &p->xad[index], t64);
3185 * verify for exact match;
3187 if (xaddr == addressXAD(&p->xad[index]) &&
3188 xoff == offsetXAD(&p->xad[index])) {
3191 /* save search result */
3192 btsp = btstack->top;
3194 btsp->index = index;
3200 /* descend/search its child page */
3211 * search miss - non-leaf page:
3213 * base is the smallest index with key (Kj) greater than
3214 * search key (K) and may be zero or maxentry index.
3215 * if base is non-zero, decrement base by one to get the parent
3216 * entry of the child page to search.
3218 index = base ? base - 1 : base;
3221 * go down to child page
3224 /* get the child page block number */
3225 bn = addressXAD(&p->xad[index]);
3227 /* unpin the parent page */
3237 * link around a freed page.
3246 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
3249 struct metapage *mp;
3253 nextbn = le64_to_cpu(p->header.next);
3254 prevbn = le64_to_cpu(p->header.prev);
3256 /* update prev pointer of the next page */
3258 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3263 * acquire a transaction lock on the page;
3265 * action: update prev pointer;
3267 BT_MARK_DIRTY(mp, ip);
3268 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3270 /* the page may already have been tlock'd */
3272 p->header.prev = cpu_to_le64(prevbn);
3277 /* update next pointer of the previous page */
3279 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3284 * acquire a transaction lock on the page;
3286 * action: update next pointer;
3288 BT_MARK_DIRTY(mp, ip);
3289 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3291 /* the page may already have been tlock'd */
3293 p->header.next = le64_to_cpu(nextbn);
3300 #endif /* _STILL_TO_PORT */
3306 * initialize file root (inline in inode)
3308 void xtInitRoot(tid_t tid, struct inode *ip)
3313 * acquire a transaction lock on the root
3317 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3318 tlckXTREE | tlckNEW);
3319 p = &JFS_IP(ip)->i_xtroot;
3321 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3322 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3324 if (S_ISDIR(ip->i_mode))
3325 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3327 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3337 * We can run into a deadlock truncating a file with a large number of
3338 * xtree pages (large fragmented file). A robust fix would entail a
3339 * reservation system where we would reserve a number of metadata pages
3340 * and tlocks which we would be guaranteed without a deadlock. Without
3341 * this, a partial fix is to limit number of metadata pages we will lock
3342 * in a single transaction. Currently we will truncate the file so that
3343 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3344 * will be responsible for ensuring that the current transaction gets
3345 * committed, and that subsequent transactions are created to truncate
3346 * the file further if needed.
3348 #define MAX_TRUNCATE_LEAVES 50
3354 * traverse for truncation logging backward bottom up;
3355 * terminate at the last extent entry at the current subtree
3356 * root page covering new down size.
3357 * truncation may occur within the last extent entry.
3363 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3369 * 1. truncate (non-COMMIT_NOLINK file)
3370 * by jfs_truncate() or jfs_open(O_TRUNC):
3372 * 2. truncate index table of directory when last entry removed
3373 * map update via tlock at commit time;
3375 * Call xtTruncate_pmap instead
3377 * 1. remove (free zero link count) on last reference release
3378 * (pmap has been freed at commit zero link count);
3379 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3381 * map update directly at truncation time;
3384 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3385 * else if (TRUNCATE)
3386 * must write LOG_NOREDOPAGE for deleted index page;
3388 * pages may already have been tlocked by anonymous transactions
3389 * during file growth (i.e., write) before truncation;
3391 * except last truncated entry, deleted entries remains as is
3392 * in the page (nextindex is updated) for other use
3393 * (e.g., log/update allocation map): this avoid copying the page
3394 * info but delay free of pages;
3397 s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3401 struct metapage *mp;
3404 int index, nextindex;
3407 int xlen, len, freexlen;
3408 struct btstack btstack;
3409 struct btframe *parent;
3410 struct tblock *tblk = NULL;
3411 struct tlock *tlck = NULL;
3412 struct xtlock *xtlck = NULL;
3413 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
3414 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
3417 int locked_leaves = 0;
3419 /* save object truncation type */
3421 tblk = tid_to_tblock(tid);
3422 tblk->xflag |= flag;
3428 assert(flag != COMMIT_PMAP);
3430 if (flag == COMMIT_PWMAP)
3434 xadlock.flag = mlckFREEXADLIST;
3439 * if the newsize is not an integral number of pages,
3440 * the file between newsize and next page boundary will
3442 * if truncating into a file hole, it will cause
3443 * a full block to be allocated for the logical block.
3447 * release page blocks of truncated region <teof, eof>
3449 * free the data blocks from the leaf index blocks.
3450 * delete the parent index entries corresponding to
3451 * the freed child data/index blocks.
3452 * free the index blocks themselves which aren't needed
3453 * in new sized file.
3455 * index blocks are updated only if the blocks are to be
3456 * retained in the new sized file.
3457 * if type is PMAP, the data and index pages are NOT
3458 * freed, and the data and index blocks are NOT freed
3460 * (this will allow continued access of data/index of
3461 * temporary file (zerolink count file truncated to zero-length)).
3463 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3464 JFS_SBI(ip->i_sb)->l2bsize;
3472 * root resides in the inode
3477 * first access of each page:
3480 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3484 /* process entries backward from last index */
3485 index = le16_to_cpu(p->header.nextindex) - 1;
3487 if (p->header.flag & BT_INTERNAL)
3494 /* Since this is the rightmost leaf, and we may have already freed
3495 * a page that was formerly to the right, let's make sure that the
3496 * next pointer is zero.
3498 if (p->header.next) {
3501 * Make sure this change to the header is logged.
3502 * If we really truncate this leaf, the flag
3503 * will be changed to tlckTRUNCATE
3505 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
3506 BT_MARK_DIRTY(mp, ip);
3512 /* does region covered by leaf page precede Teof ? */
3513 xad = &p->xad[index];
3514 xoff = offsetXAD(xad);
3515 xlen = lengthXAD(xad);
3516 if (teof >= xoff + xlen) {
3521 /* (re)acquire tlock of the leaf page */
3523 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3525 * We need to limit the size of the transaction
3526 * to avoid exhausting pagecache & tlocks
3529 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3532 tlck = txLock(tid, ip, mp, tlckXTREE);
3533 tlck->type = tlckXTREE | tlckTRUNCATE;
3534 xtlck = (struct xtlock *) & tlck->lock;
3535 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3537 BT_MARK_DIRTY(mp, ip);
3540 * scan backward leaf page entries
3542 for (; index >= XTENTRYSTART; index--) {
3543 xad = &p->xad[index];
3544 xoff = offsetXAD(xad);
3545 xlen = lengthXAD(xad);
3546 xaddr = addressXAD(xad);
3549 * The "data" for a directory is indexed by the block
3550 * device's address space. This metadata must be invalidated
3553 if (S_ISDIR(ip->i_mode) && (teof == 0))
3554 invalidate_xad_metapages(ip, *xad);
3556 * entry beyond eof: continue scan of current page
3558 * ---|---=======------->
3567 * (xoff <= teof): last entry to be deleted from page;
3568 * If other entries remain in page: keep and update the page.
3572 * eof == entry_start: delete the entry
3574 * -------|=======------->
3581 if (index == XTENTRYSTART)
3587 * eof within the entry: truncate the entry.
3589 * -------===|===------->
3592 else if (teof < xoff + xlen) {
3593 /* update truncated entry */
3595 freexlen = xlen - len;
3596 XADlength(xad, len);
3598 /* save pxd of truncated extent in tlck */
3600 if (log) { /* COMMIT_PWMAP */
3601 xtlck->lwm.offset = (xtlck->lwm.offset) ?
3602 min(index, (int)xtlck->lwm.offset) : index;
3603 xtlck->lwm.length = index + 1 -
3605 xtlck->twm.offset = index;
3606 pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3607 pxdlock->flag = mlckFREEPXD;
3608 PXDaddress(&pxdlock->pxd, xaddr);
3609 PXDlength(&pxdlock->pxd, freexlen);
3611 /* free truncated extent */
3612 else { /* COMMIT_WMAP */
3614 pxdlock = (struct pxd_lock *) & xadlock;
3615 pxdlock->flag = mlckFREEPXD;
3616 PXDaddress(&pxdlock->pxd, xaddr);
3617 PXDlength(&pxdlock->pxd, freexlen);
3618 txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
3620 /* reset map lock */
3621 xadlock.flag = mlckFREEXADLIST;
3624 /* current entry is new last entry; */
3625 nextindex = index + 1;
3630 * eof beyond the entry:
3632 * -------=======---|--->
3635 else { /* (xoff + xlen < teof) */
3637 nextindex = index + 1;
3640 if (nextindex < le16_to_cpu(p->header.nextindex)) {
3641 if (!log) { /* COMMIT_WAMP */
3642 xadlock.xdlist = &p->xad[nextindex];
3644 le16_to_cpu(p->header.nextindex) -
3646 txFreeMap(ip, (struct maplock *) & xadlock,
3649 p->header.nextindex = cpu_to_le16(nextindex);
3654 /* assert(freed == 0); */
3656 } /* end scan of leaf page entries */
3661 * leaf page become empty: free the page if type != PMAP
3663 if (log) { /* COMMIT_PWMAP */
3664 /* txCommit() with tlckFREE:
3665 * free data extents covered by leaf [XTENTRYSTART:hwm);
3666 * invalidate leaf if COMMIT_PWMAP;
3667 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3669 tlck->type = tlckXTREE | tlckFREE;
3670 } else { /* COMMIT_WAMP */
3672 /* free data extents covered by leaf */
3673 xadlock.xdlist = &p->xad[XTENTRYSTART];
3675 le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3676 txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
3679 if (p->header.flag & BT_ROOT) {
3680 p->header.flag &= ~BT_INTERNAL;
3681 p->header.flag |= BT_LEAF;
3682 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3684 XT_PUTPAGE(mp); /* debug */
3687 if (log) { /* COMMIT_PWMAP */
3688 /* page will be invalidated at tx completion
3691 } else { /* COMMIT_WMAP */
3694 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3696 /* invalidate empty leaf page */
3697 discard_metapage(mp);
3702 * the leaf page become empty: delete the parent entry
3703 * for the leaf page if the parent page is to be kept
3704 * in the new sized file.
3708 * go back up to the parent page
3711 /* pop/restore parent entry for the current child page */
3712 if ((parent = BT_POP(&btstack)) == NULL)
3713 /* current page must have been root */
3716 /* get back the parent page */
3718 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3722 index = parent->index;
3725 * child page was not empty:
3728 /* has any entry deleted from parent ? */
3729 if (index < le16_to_cpu(p->header.nextindex) - 1) {
3730 /* (re)acquire tlock on the parent page */
3731 if (log) { /* COMMIT_PWMAP */
3732 /* txCommit() with tlckTRUNCATE:
3733 * free child extents covered by parent [);
3735 tlck = txLock(tid, ip, mp, tlckXTREE);
3736 xtlck = (struct xtlock *) & tlck->lock;
3737 if (!(tlck->type & tlckTRUNCATE)) {
3739 le16_to_cpu(p->header.
3742 tlckXTREE | tlckTRUNCATE;
3744 } else { /* COMMIT_WMAP */
3746 /* free child extents covered by parent */
3747 xadlock.xdlist = &p->xad[index + 1];
3749 le16_to_cpu(p->header.nextindex) -
3751 txFreeMap(ip, (struct maplock *) & xadlock,
3754 BT_MARK_DIRTY(mp, ip);
3756 p->header.nextindex = cpu_to_le16(index + 1);
3763 * child page was empty:
3765 nfreed += lengthXAD(&p->xad[index]);
3768 * During working map update, child page's tlock must be handled
3769 * before parent's. This is because the parent's tlock will cause
3770 * the child's disk space to be marked available in the wmap, so
3771 * it's important that the child page be released by that time.
3773 * ToDo: tlocks should be on doubly-linked list, so we can
3774 * quickly remove it and add it to the end.
3778 * Move parent page's tlock to the end of the tid's tlock list
3780 if (log && mp->lid && (tblk->last != mp->lid) &&
3781 lid_to_tlock(mp->lid)->tid) {
3782 lid_t lid = mp->lid;
3785 tlck = lid_to_tlock(lid);
3787 if (tblk->next == lid)
3788 tblk->next = tlck->next;
3790 for (prev = lid_to_tlock(tblk->next);
3792 prev = lid_to_tlock(prev->next)) {
3795 prev->next = tlck->next;
3797 lid_to_tlock(tblk->last)->next = lid;
3803 * parent page become empty: free the page
3805 if (index == XTENTRYSTART) {
3806 if (log) { /* COMMIT_PWMAP */
3807 /* txCommit() with tlckFREE:
3808 * free child extents covered by parent;
3809 * invalidate parent if COMMIT_PWMAP;
3811 tlck = txLock(tid, ip, mp, tlckXTREE);
3812 xtlck = (struct xtlock *) & tlck->lock;
3814 le16_to_cpu(p->header.nextindex) - 1;
3815 tlck->type = tlckXTREE | tlckFREE;
3816 } else { /* COMMIT_WMAP */
3818 /* free child extents covered by parent */
3819 xadlock.xdlist = &p->xad[XTENTRYSTART];
3821 le16_to_cpu(p->header.nextindex) -
3823 txFreeMap(ip, (struct maplock *) & xadlock, NULL,
3826 BT_MARK_DIRTY(mp, ip);
3828 if (p->header.flag & BT_ROOT) {
3829 p->header.flag &= ~BT_INTERNAL;
3830 p->header.flag |= BT_LEAF;
3831 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3832 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3834 * Shrink root down to allow inline
3835 * EA (otherwise fsck complains)
3837 p->header.maxentry =
3838 cpu_to_le16(XTROOTINITSLOT);
3839 JFS_IP(ip)->mode2 |= INLINEEA;
3842 XT_PUTPAGE(mp); /* debug */
3845 if (log) { /* COMMIT_PWMAP */
3846 /* page will be invalidated at tx completion
3849 } else { /* COMMIT_WMAP */
3852 lid_to_tlock(mp->lid)->flag |=
3855 /* invalidate parent page */
3856 discard_metapage(mp);
3859 /* parent has become empty and freed:
3860 * go back up to its parent page
3867 * parent page still has entries for front region;
3870 /* try truncate region covered by preceding entry
3871 * (process backward)
3875 /* go back down to the child page corresponding
3882 * internal page: go down to child page of current entry
3885 /* save current parent entry for the child page */
3886 BT_PUSH(&btstack, bn, index);
3888 /* get child page */
3889 xad = &p->xad[index];
3890 bn = addressXAD(xad);
3893 * first access of each internal entry:
3895 /* release parent page */
3898 /* process the child page */
3903 * update file resource stat
3907 if (S_ISDIR(ip->i_mode) && !newsize)
3908 ip->i_size = 1; /* fsck hates zero-length directories */
3910 ip->i_size = newsize;
3912 /* update nblocks to reflect freed blocks */
3913 ip->i_blocks -= LBLK2PBLK(ip->i_sb, nfreed);
3916 * free tlock of invalidated pages
3918 if (flag == COMMIT_WMAP)
3929 * Perform truncate to zero lenghth for deleted file, leaving the
3930 * the xtree and working map untouched. This allows the file to
3931 * be accessed via open file handles, while the delete of the file
3932 * is committed to disk.
3937 * s64 committed_size)
3939 * return: new committed size
3943 * To avoid deadlock by holding too many transaction locks, the
3944 * truncation may be broken up into multiple transactions.
3945 * The committed_size keeps track of part of the file has been
3946 * freed from the pmaps.
3948 s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3951 struct btstack btstack;
3954 int locked_leaves = 0;
3955 struct metapage *mp;
3957 struct btframe *parent;
3959 struct tblock *tblk;
3960 struct tlock *tlck = NULL;
3964 struct xtlock *xtlck = NULL;
3966 /* save object truncation type */
3967 tblk = tid_to_tblock(tid);
3968 tblk->xflag |= COMMIT_PMAP;
3973 if (committed_size) {
3974 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
3975 rc = xtSearch(ip, xoff, &cmp, &btstack, 0);
3979 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3984 "xtTruncate_pmap: did not find extent");
3991 * root resides in the inode
3996 * first access of each page:
3999 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4003 /* process entries backward from last index */
4004 index = le16_to_cpu(p->header.nextindex) - 1;
4006 if (p->header.flag & BT_INTERNAL)
4014 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
4016 * We need to limit the size of the transaction
4017 * to avoid exhausting pagecache & tlocks
4019 xad = &p->xad[index];
4020 xoff = offsetXAD(xad);
4021 xlen = lengthXAD(xad);
4023 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
4025 tlck = txLock(tid, ip, mp, tlckXTREE);
4026 tlck->type = tlckXTREE | tlckFREE;
4027 xtlck = (struct xtlock *) & tlck->lock;
4028 xtlck->hwm.offset = index;
4034 * go back up to the parent page
4037 /* pop/restore parent entry for the current child page */
4038 if ((parent = BT_POP(&btstack)) == NULL)
4039 /* current page must have been root */
4042 /* get back the parent page */
4044 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4048 index = parent->index;
4051 * parent page become empty: free the page
4053 if (index == XTENTRYSTART) {
4054 /* txCommit() with tlckFREE:
4055 * free child extents covered by parent;
4056 * invalidate parent if COMMIT_PWMAP;
4058 tlck = txLock(tid, ip, mp, tlckXTREE);
4059 xtlck = (struct xtlock *) & tlck->lock;
4061 le16_to_cpu(p->header.nextindex) - 1;
4062 tlck->type = tlckXTREE | tlckFREE;
4066 if (p->header.flag & BT_ROOT) {
4074 * parent page still has entries for front region;
4079 * internal page: go down to child page of current entry
4082 /* save current parent entry for the child page */
4083 BT_PUSH(&btstack, bn, index);
4085 /* get child page */
4086 xad = &p->xad[index];
4087 bn = addressXAD(xad);
4090 * first access of each internal entry:
4092 /* release parent page */
4095 /* process the child page */
4104 #ifdef _JFS_DEBUG_XTREE
4108 * function: traverse forward
4110 int xtDisplayTree(struct inode *ip)
4113 struct metapage *mp;
4116 int index, lastindex, v, h;
4118 struct btstack btstack;
4119 struct btframe *btsp;
4120 struct btframe *parent;
4122 printk("display B+-tree.\n");
4125 btsp = btstack.stack;
4130 * root resides in the inode
4136 * first access of each page:
4139 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4143 /* process entries forward from first index */
4144 index = XTENTRYSTART;
4145 lastindex = le16_to_cpu(p->header.nextindex) - 1;
4147 if (p->header.flag & BT_INTERNAL) {
4149 * first access of each internal page
4152 } else { /* (p->header.flag & BT_LEAF) */
4155 * first access of each leaf page
4157 printf("leaf page ");
4158 xtDisplayPage(ip, bn, p);
4160 /* unpin the leaf page */
4165 * go back up to the parent page
4168 /* pop/restore parent entry for the current child page */
4169 if ((parent = (btsp == btstack.stack ? NULL : --btsp)) == NULL)
4170 /* current page must have been root */
4174 * parent page scan completed
4176 if ((index = parent->index) == (lastindex = parent->lastindex)) {
4177 /* go back up to the parent page */
4182 * parent page has entries remaining
4184 /* get back the parent page */
4186 /* v = parent->level; */
4187 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4191 /* get next parent entry */
4195 * internal page: go down to child page of current entry
4198 /* push/save current parent entry for the child page */
4199 btsp->bn = pbn = bn;
4200 btsp->index = index;
4201 btsp->lastindex = lastindex;
4202 /* btsp->level = v; */
4203 /* btsp->node = h; */
4206 /* get child page */
4207 xad = &p->xad[index];
4208 bn = addressXAD(xad);
4211 * first access of each internal entry:
4213 /* release parent page */
4216 printk("traverse down 0x%lx[%d]->0x%lx\n", (ulong) pbn, index,
4221 /* process the child page */
4229 * function: display page
4231 int xtDisplayPage(struct inode *ip, s64 bn, xtpage_t * p)
4238 /* display page control */
4239 printf("bn:0x%lx flag:0x%x nextindex:%d\n",
4240 (ulong) bn, p->header.flag,
4241 le16_to_cpu(p->header.nextindex));
4243 /* display entries */
4244 xad = &p->xad[XTENTRYSTART];
4245 for (i = XTENTRYSTART, j = 1; i < le16_to_cpu(p->header.nextindex);
4247 xoff = offsetXAD(xad);
4248 xaddr = addressXAD(xad);
4249 xlen = lengthXAD(xad);
4250 printf("\t[%d] 0x%lx:0x%lx(0x%x)", i, (ulong) xoff,
4251 (ulong) xaddr, xlen);
4261 #endif /* _JFS_DEBUG_XTREE */
4269 * traverse for allocation acquiring tlock at commit time
4270 * (vs at the time of update) logging backward top down
4273 * problem - establishing that all new allocation have been
4274 * processed both for append and random write in sparse file
4275 * at the current entry at the current subtree root page
4278 int xtGather(btree_t *t)
4285 struct btstack btstack;
4286 struct btsf *parent;
4294 * root resides in the inode
4297 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4301 /* new root is NOT pointed by a new entry
4302 if (p->header.flag & NEW)
4303 allocate new page lock;
4304 write a NEWPAGE log;
4309 * first access of each page:
4311 /* process entries backward from last index */
4312 index = le16_to_cpu(p->header.nextindex) - 1;
4314 if (p->header.flag & BT_LEAF) {
4316 * first access of each leaf page
4318 /* process leaf page entries backward */
4319 for (; index >= XTENTRYSTART; index--) {
4322 * if newpage, log NEWPAGE.
4324 if (e->flag & XAD_NEW) {
4325 nfound =+ entry->length;
4326 update current page lock for the entry;
4329 * if moved, log move.
4331 } else if (e->flag & XAD_MOVED) {
4333 update current page lock for the entry;
4338 /* unpin the leaf page */
4342 * go back up to the parent page
4345 /* restore parent entry for the current child page */
4346 if ((parent = BT_POP(&btstack)) == NULL)
4347 /* current page must have been root */
4350 if ((index = parent->index) == XTENTRYSTART) {
4352 * parent page scan completed
4354 /* go back up to the parent page */
4358 * parent page has entries remaining
4360 /* get back the parent page */
4362 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4366 /* first subroot page which
4367 * covers all new allocated blocks
4368 * itself not new/modified.
4369 * (if modified from split of descendent,
4370 * go down path of split page)
4372 if (nfound == nnew &&
4373 !(p->header.flag & (NEW | MOD)))
4377 /* process parent page entries backward */
4382 * first access of each internal page
4387 * internal page: go down to child page of current entry
4390 /* save current parent entry for the child page */
4391 BT_PUSH(&btstack, bn, index);
4393 /* get current entry for the child page */
4397 * first access of each internal entry:
4400 * if new entry, log btree_tnewentry.
4402 if (e->flag & XAD_NEW)
4403 update parent page lock for the entry;
4406 /* release parent page */
4409 /* get child page */
4411 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4416 * first access of each non-root page:
4419 * if new, log btree_newpage.
4421 if (p->header.flag & NEW)
4422 allocate new page lock;
4423 write a NEWPAGE log (next, prev);
4426 /* process the child page */
4432 #endif /* _JFS_WIP */
4435 #ifdef CONFIG_JFS_STATISTICS
4436 int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length,
4437 int *eof, void *data)
4442 len += sprintf(buffer,
4443 "JFS Xtree statistics\n"
4444 "====================\n"
4446 "fast searches = %d\n"
4453 *start = buffer + begin;