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);
1078 * The new key entry goes ONE AFTER the index of parent entry,
1079 * because the split was to the right.
1081 skip = parent->index + 1;
1084 * split or shift right remaining entries of the parent page
1086 nextindex = le16_to_cpu(sp->header.nextindex);
1088 * parent page is full - split the parent page
1090 if (nextindex == le16_to_cpu(sp->header.maxentry)) {
1091 /* init for parent page split */
1093 split->index = skip; /* index at insert */
1094 split->flag = XAD_NEW;
1095 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
1096 split->len = JFS_SBI(ip->i_sb)->nbperpage;
1099 /* unpin previous right child page */
1102 /* The split routines insert the new entry,
1103 * and acquire txLock as appropriate.
1104 * return <rp> pinned and its block number <rpbn>.
1106 rc = (sp->header.flag & BT_ROOT) ?
1107 xtSplitRoot(tid, ip, split, &rmp) :
1108 xtSplitPage(tid, ip, split, &rmp, &rbn);
1113 /* keep new child page <rp> pinned */
1116 * parent page is not full - insert in parent page
1120 * insert router entry in parent for the right child
1121 * page from the first entry of the right child page:
1124 * acquire a transaction lock on the parent page;
1126 * action: router xad insertion;
1128 BT_MARK_DIRTY(smp, ip);
1131 * if insert into middle, shift right remaining entries
1133 if (skip < nextindex)
1134 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1136 skip) << L2XTSLOTSIZE);
1138 /* insert the router entry */
1139 xad = &sp->xad[skip];
1140 XT_PUTENTRY(xad, XAD_NEW,
1141 offsetXAD(&rcp->xad[XTENTRYSTART]),
1142 JFS_SBI(ip->i_sb)->nbperpage, rcbn);
1144 /* advance next available entry index. */
1145 sp->header.nextindex =
1146 cpu_to_le16(le16_to_cpu(sp->header.nextindex) +
1149 /* Don't log it if there are no links to the file */
1150 if (!test_cflag(COMMIT_Nolink, ip)) {
1151 tlck = txLock(tid, ip, smp,
1152 tlckXTREE | tlckGROW);
1153 xtlck = (struct xtlock *) & tlck->lock;
1154 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1155 min(skip, (int)xtlck->lwm.offset) : skip;
1157 le16_to_cpu(sp->header.nextindex) -
1161 /* unpin parent page */
1164 /* exit propagate up */
1169 /* unpin current right page */
1175 * If something fails in the above loop we were already walking back
1176 * up the tree and the tree is now inconsistent.
1177 * release all pages we're holding.
1193 * split a full non-root page into
1194 * original/split/left page and new right page
1195 * i.e., the original/split page remains as left page.
1200 * struct xtsplit *split,
1201 * struct metapage **rmpp,
1205 * Pointer to page in which to insert or NULL on error.
1208 xtSplitPage(tid_t tid, struct inode *ip,
1209 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
1212 struct metapage *smp;
1214 struct metapage *rmp;
1215 xtpage_t *rp; /* new right page allocated */
1216 s64 rbn; /* new right page block number */
1217 struct metapage *mp;
1220 int skip, maxentry, middle, righthalf, n;
1222 struct pxdlist *pxdlist;
1225 struct xtlock *sxtlck = 0, *rxtlck = 0;
1228 sp = XT_PAGE(ip, smp);
1230 INCREMENT(xtStat.split);
1233 * allocate the new right page for the split
1235 pxdlist = split->pxdlist;
1236 pxd = &pxdlist->pxd[pxdlist->npxd];
1238 rbn = addressPXD(pxd);
1239 rmp = get_metapage(ip, rbn, PSIZE, 1);
1243 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1245 BT_MARK_DIRTY(rmp, ip);
1250 rp = (xtpage_t *) rmp->data;
1251 rp->header.self = *pxd;
1252 rp->header.flag = sp->header.flag & BT_TYPE;
1253 rp->header.maxentry = sp->header.maxentry; /* little-endian */
1254 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1256 BT_MARK_DIRTY(smp, ip);
1257 /* Don't log it if there are no links to the file */
1258 if (!test_cflag(COMMIT_Nolink, ip)) {
1260 * acquire a transaction lock on the new right page;
1262 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1263 rxtlck = (struct xtlock *) & tlck->lock;
1264 rxtlck->lwm.offset = XTENTRYSTART;
1266 * acquire a transaction lock on the split page
1268 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1269 sxtlck = (struct xtlock *) & tlck->lock;
1273 * initialize/update sibling pointers of <sp> and <rp>
1275 nextbn = le64_to_cpu(sp->header.next);
1276 rp->header.next = cpu_to_le64(nextbn);
1277 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1278 sp->header.next = cpu_to_le64(rbn);
1280 skip = split->index;
1283 * sequential append at tail (after last entry of last page)
1285 * if splitting the last page on a level because of appending
1286 * a entry to it (skip is maxentry), it's likely that the access is
1287 * sequential. adding an empty page on the side of the level is less
1288 * work and can push the fill factor much higher than normal.
1289 * if we're wrong it's no big deal - we will do the split the right
1291 * (it may look like it's equally easy to do a similar hack for
1292 * reverse sorted data, that is, split the tree left, but it's not.
1295 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1297 * acquire a transaction lock on the new/right page;
1299 * action: xad insertion;
1301 /* insert entry at the first entry of the new right page */
1302 xad = &rp->xad[XTENTRYSTART];
1303 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1306 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1308 if (!test_cflag(COMMIT_Nolink, ip)) {
1309 /* rxtlck->lwm.offset = XTENTRYSTART; */
1310 rxtlck->lwm.length = 1;
1316 ip->i_blocks += LBLK2PBLK(ip->i_sb, lengthPXD(pxd));
1318 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1323 * non-sequential insert (at possibly middle page)
1327 * update previous pointer of old next/right page of <sp>
1330 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1336 BT_MARK_DIRTY(mp, ip);
1338 * acquire a transaction lock on the next page;
1340 * action:sibling pointer update;
1342 if (!test_cflag(COMMIT_Nolink, ip))
1343 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1345 p->header.prev = cpu_to_le64(rbn);
1347 /* sibling page may have been updated previously, or
1348 * it may be updated later;
1355 * split the data between the split and new/right pages
1357 maxentry = le16_to_cpu(sp->header.maxentry);
1358 middle = maxentry >> 1;
1359 righthalf = maxentry - middle;
1362 * skip index in old split/left page - insert into left page:
1364 if (skip <= middle) {
1365 /* move right half of split page to the new right page */
1366 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1367 righthalf << L2XTSLOTSIZE);
1369 /* shift right tail of left half to make room for new entry */
1371 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1372 (middle - skip) << L2XTSLOTSIZE);
1374 /* insert new entry */
1375 xad = &sp->xad[skip];
1376 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1379 /* update page header */
1380 sp->header.nextindex = cpu_to_le16(middle + 1);
1381 if (!test_cflag(COMMIT_Nolink, ip)) {
1382 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1383 min(skip, (int)sxtlck->lwm.offset) : skip;
1386 rp->header.nextindex =
1387 cpu_to_le16(XTENTRYSTART + righthalf);
1390 * skip index in new right page - insert into right page:
1393 /* move left head of right half to right page */
1395 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1398 /* insert new entry */
1401 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1404 /* move right tail of right half to right page */
1405 if (skip < maxentry)
1406 memmove(&rp->xad[n + 1], &sp->xad[skip],
1407 (maxentry - skip) << L2XTSLOTSIZE);
1409 /* update page header */
1410 sp->header.nextindex = cpu_to_le16(middle);
1411 if (!test_cflag(COMMIT_Nolink, ip)) {
1412 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1413 min(middle, (int)sxtlck->lwm.offset) : middle;
1416 rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1420 if (!test_cflag(COMMIT_Nolink, ip)) {
1421 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1424 /* rxtlck->lwm.offset = XTENTRYSTART; */
1425 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1432 ip->i_blocks += LBLK2PBLK(ip->i_sb, lengthPXD(pxd));
1434 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1443 * split the full root page into
1444 * original/root/split page and new right page
1445 * i.e., root remains fixed in tree anchor (inode) and
1446 * the root is copied to a single new right child page
1447 * since root page << non-root page, and
1448 * the split root page contains a single entry for the
1449 * new right child page.
1454 * struct xtsplit *split,
1455 * struct metapage **rmpp)
1458 * Pointer to page in which to insert or NULL on error.
1461 xtSplitRoot(tid_t tid,
1462 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1465 struct metapage *rmp;
1468 int skip, nextindex;
1471 struct pxdlist *pxdlist;
1473 struct xtlock *xtlck;
1475 sp = &JFS_IP(ip)->i_xtroot;
1477 INCREMENT(xtStat.split);
1480 * allocate a single (right) child page
1482 pxdlist = split->pxdlist;
1483 pxd = &pxdlist->pxd[pxdlist->npxd];
1485 rbn = addressPXD(pxd);
1486 rmp = get_metapage(ip, rbn, PSIZE, 1);
1490 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1493 * acquire a transaction lock on the new right page;
1497 BT_MARK_DIRTY(rmp, ip);
1499 rp = (xtpage_t *) rmp->data;
1501 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1502 rp->header.self = *pxd;
1503 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1504 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1506 /* initialize sibling pointers */
1507 rp->header.next = 0;
1508 rp->header.prev = 0;
1511 * copy the in-line root page into new right page extent
1513 nextindex = le16_to_cpu(sp->header.maxentry);
1514 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1515 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1518 * insert the new entry into the new right/child page
1519 * (skip index in the new right page will not change)
1521 skip = split->index;
1522 /* if insert into middle, shift right remaining entries */
1523 if (skip != nextindex)
1524 memmove(&rp->xad[skip + 1], &rp->xad[skip],
1525 (nextindex - skip) * sizeof(xad_t));
1527 xad = &rp->xad[skip];
1528 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1530 /* update page header */
1531 rp->header.nextindex = cpu_to_le16(nextindex + 1);
1533 if (!test_cflag(COMMIT_Nolink, ip)) {
1534 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1535 xtlck = (struct xtlock *) & tlck->lock;
1536 xtlck->lwm.offset = XTENTRYSTART;
1537 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1544 * init root with the single entry for the new right page
1545 * set the 1st entry offset to 0, which force the left-most key
1546 * at any level of the tree to be less than any search key.
1549 * acquire a transaction lock on the root page (in-memory inode);
1551 * action: root split;
1553 BT_MARK_DIRTY(split->mp, ip);
1555 xad = &sp->xad[XTENTRYSTART];
1556 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1558 /* update page header of root */
1559 sp->header.flag &= ~BT_LEAF;
1560 sp->header.flag |= BT_INTERNAL;
1562 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1564 if (!test_cflag(COMMIT_Nolink, ip)) {
1565 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1566 xtlck = (struct xtlock *) & tlck->lock;
1567 xtlck->lwm.offset = XTENTRYSTART;
1568 xtlck->lwm.length = 1;
1573 ip->i_blocks += LBLK2PBLK(ip->i_sb, lengthPXD(pxd));
1575 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1583 * function: extend in-place;
1585 * note: existing extent may or may not have been committed.
1586 * caller is responsible for pager buffer cache update, and
1587 * working block allocation map update;
1588 * update pmap: alloc whole extended extent;
1590 int xtExtend(tid_t tid, /* transaction id */
1591 struct inode *ip, s64 xoff, /* delta extent offset */
1592 s32 xlen, /* delta extent length */
1597 struct metapage *mp; /* meta-page buffer */
1598 xtpage_t *p; /* base B+-tree index page */
1600 int index, nextindex, len;
1601 struct btstack btstack; /* traverse stack */
1602 struct xtsplit split; /* split information */
1606 struct xtlock *xtlck = 0;
1609 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1611 /* there must exist extent to be extended */
1612 if ((rc = xtSearch(ip, xoff - 1, &cmp, &btstack, XT_INSERT)))
1615 /* retrieve search result */
1616 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1620 jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
1624 /* extension must be contiguous */
1625 xad = &p->xad[index];
1626 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1628 jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
1633 * acquire a transaction lock on the leaf page;
1635 * action: xad insertion/extension;
1637 BT_MARK_DIRTY(mp, ip);
1638 if (!test_cflag(COMMIT_Nolink, ip)) {
1639 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1640 xtlck = (struct xtlock *) & tlck->lock;
1643 /* extend will overflow extent ? */
1644 xlen = lengthXAD(xad) + xlen;
1645 if ((len = xlen - MAXXLEN) <= 0)
1649 * extent overflow: insert entry for new extent
1652 xoff = offsetXAD(xad) + MAXXLEN;
1653 xaddr = addressXAD(xad) + MAXXLEN;
1654 nextindex = le16_to_cpu(p->header.nextindex);
1657 * if the leaf page is full, insert the new entry and
1658 * propagate up the router entry for the new page from split
1660 * The xtSplitUp() will insert the entry and unpin the leaf page.
1662 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1663 rootsplit = p->header.flag & BT_ROOT;
1665 /* xtSpliUp() unpins leaf pages */
1667 split.index = index + 1;
1668 split.flag = XAD_NEW;
1669 split.off = xoff; /* split offset */
1672 split.pxdlist = NULL;
1673 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1677 * if leaf root has been split, original root has been
1678 * copied to new child page, i.e., original entry now
1679 * resides on the new child page;
1682 ASSERT(p->header.nextindex ==
1683 cpu_to_le16(XTENTRYSTART + 1));
1684 xad = &p->xad[XTENTRYSTART];
1685 bn = addressXAD(xad);
1687 /* get new child page */
1688 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1692 BT_MARK_DIRTY(mp, ip);
1693 if (!test_cflag(COMMIT_Nolink, ip)) {
1694 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1695 xtlck = (struct xtlock *) & tlck->lock;
1698 /* get back old page */
1699 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1705 * insert the new entry into the leaf page
1708 /* insert the new entry: mark the entry NEW */
1709 xad = &p->xad[index + 1];
1710 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1712 /* advance next available entry index */
1713 p->header.nextindex =
1714 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1717 /* get back old entry */
1718 xad = &p->xad[index];
1725 XADlength(xad, xlen);
1726 if (!(xad->flag & XAD_NEW))
1727 xad->flag |= XAD_EXTENDED;
1729 if (!test_cflag(COMMIT_Nolink, ip)) {
1731 (xtlck->lwm.offset) ? min(index,
1732 (int)xtlck->lwm.offset) : index;
1734 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1737 /* unpin the leaf page */
1747 * function: split existing 'tail' extent
1748 * (split offset >= start offset of tail extent), and
1749 * relocate and extend the split tail half;
1751 * note: existing extent may or may not have been committed.
1752 * caller is responsible for pager buffer cache update, and
1753 * working block allocation map update;
1754 * update pmap: free old split tail extent, alloc new extent;
1756 int xtTailgate(tid_t tid, /* transaction id */
1757 struct inode *ip, s64 xoff, /* split/new extent offset */
1758 s32 xlen, /* new extent length */
1759 s64 xaddr, /* new extent address */
1764 struct metapage *mp; /* meta-page buffer */
1765 xtpage_t *p; /* base B+-tree index page */
1767 int index, nextindex, llen, rlen;
1768 struct btstack btstack; /* traverse stack */
1769 struct xtsplit split; /* split information */
1772 struct xtlock *xtlck = 0;
1773 struct tlock *mtlck;
1774 struct maplock *pxdlock;
1778 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1779 (ulong)xoff, xlen, (ulong)xaddr);
1782 /* there must exist extent to be tailgated */
1783 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
1786 /* retrieve search result */
1787 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1791 jfs_error(ip->i_sb, "xtTailgate: couldn't find extent");
1795 /* entry found must be last entry */
1796 nextindex = le16_to_cpu(p->header.nextindex);
1797 if (index != nextindex - 1) {
1800 "xtTailgate: the entry found is not the last entry");
1804 BT_MARK_DIRTY(mp, ip);
1806 * acquire tlock of the leaf page containing original entry
1808 if (!test_cflag(COMMIT_Nolink, ip)) {
1809 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1810 xtlck = (struct xtlock *) & tlck->lock;
1813 /* completely replace extent ? */
1814 xad = &p->xad[index];
1816 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1817 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1819 if ((llen = xoff - offsetXAD(xad)) == 0)
1823 * partially replace extent: insert entry for new extent
1827 * if the leaf page is full, insert the new entry and
1828 * propagate up the router entry for the new page from split
1830 * The xtSplitUp() will insert the entry and unpin the leaf page.
1832 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1833 rootsplit = p->header.flag & BT_ROOT;
1835 /* xtSpliUp() unpins leaf pages */
1837 split.index = index + 1;
1838 split.flag = XAD_NEW;
1839 split.off = xoff; /* split offset */
1842 split.pxdlist = NULL;
1843 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1847 * if leaf root has been split, original root has been
1848 * copied to new child page, i.e., original entry now
1849 * resides on the new child page;
1852 ASSERT(p->header.nextindex ==
1853 cpu_to_le16(XTENTRYSTART + 1));
1854 xad = &p->xad[XTENTRYSTART];
1855 bn = addressXAD(xad);
1857 /* get new child page */
1858 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1862 BT_MARK_DIRTY(mp, ip);
1863 if (!test_cflag(COMMIT_Nolink, ip)) {
1864 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1865 xtlck = (struct xtlock *) & tlck->lock;
1868 /* get back old page */
1869 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1875 * insert the new entry into the leaf page
1878 /* insert the new entry: mark the entry NEW */
1879 xad = &p->xad[index + 1];
1880 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1882 /* advance next available entry index */
1883 p->header.nextindex =
1884 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1887 /* get back old XAD */
1888 xad = &p->xad[index];
1891 * truncate/relocate old extent at split offset
1894 /* update dmap for old/committed/truncated extent */
1895 rlen = lengthXAD(xad) - llen;
1896 if (!(xad->flag & XAD_NEW)) {
1897 /* free from PWMAP at commit */
1898 if (!test_cflag(COMMIT_Nolink, ip)) {
1899 mtlck = txMaplock(tid, ip, tlckMAP);
1900 pxdlock = (struct maplock *) & mtlck->lock;
1901 pxdlock->flag = mlckFREEPXD;
1902 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1903 PXDlength(&pxdlock->pxd, rlen);
1907 /* free from WMAP */
1908 dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1912 XADlength(xad, llen);
1915 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1917 if (!test_cflag(COMMIT_Nolink, ip)) {
1918 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1919 min(index, (int)xtlck->lwm.offset) : index;
1920 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1924 /* unpin the leaf page */
1929 #endif /* _NOTYET */
1934 * function: update XAD;
1936 * update extent for allocated_but_not_recorded or
1937 * compressed extent;
1941 * logical extent of the specified XAD must be completely
1942 * contained by an existing XAD;
1944 int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1948 struct metapage *mp; /* meta-page buffer */
1949 xtpage_t *p; /* base B+-tree index page */
1951 int index0, index, newindex, nextindex;
1952 struct btstack btstack; /* traverse stack */
1953 struct xtsplit split; /* split information */
1954 xad_t *xad, *lxad, *rxad;
1957 int nxlen, xlen, lxlen, rxlen;
1960 struct xtlock *xtlck = 0;
1961 int rootsplit = 0, newpage = 0;
1963 /* there must exist extent to be tailgated */
1964 nxoff = offsetXAD(nxad);
1965 nxlen = lengthXAD(nxad);
1966 nxaddr = addressXAD(nxad);
1968 if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT)))
1971 /* retrieve search result */
1972 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
1976 jfs_error(ip->i_sb, "xtUpdate: Could not find extent");
1980 BT_MARK_DIRTY(mp, ip);
1982 * acquire tlock of the leaf page containing original entry
1984 if (!test_cflag(COMMIT_Nolink, ip)) {
1985 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1986 xtlck = (struct xtlock *) & tlck->lock;
1989 xad = &p->xad[index0];
1991 xoff = offsetXAD(xad);
1992 xlen = lengthXAD(xad);
1993 xaddr = addressXAD(xad);
1995 /* nXAD must be completely contained within XAD */
1996 if ((xoff > nxoff) ||
1997 (nxoff + nxlen > xoff + xlen)) {
2000 "xtUpdate: nXAD in not completely contained within XAD");
2005 newindex = index + 1;
2006 nextindex = le16_to_cpu(p->header.nextindex);
2008 #ifdef _JFS_WIP_NOCOALESCE
2013 * replace XAD with nXAD
2015 replace: /* (nxoff == xoff) */
2016 if (nxlen == xlen) {
2017 /* replace XAD with nXAD:recorded */
2019 xad->flag = xflag & ~XAD_NOTRECORDED;
2022 } else /* (nxlen < xlen) */
2024 #endif /* _JFS_WIP_NOCOALESCE */
2026 /* #ifdef _JFS_WIP_COALESCE */
2031 * coalesce with left XAD
2033 //coalesceLeft: /* (xoff == nxoff) */
2034 /* is XAD first entry of page ? */
2035 if (index == XTENTRYSTART)
2038 /* is nXAD logically and physically contiguous with lXAD ? */
2039 lxad = &p->xad[index - 1];
2040 lxlen = lengthXAD(lxad);
2041 if (!(lxad->flag & XAD_NOTRECORDED) &&
2042 (nxoff == offsetXAD(lxad) + lxlen) &&
2043 (nxaddr == addressXAD(lxad) + lxlen) &&
2044 (lxlen + nxlen < MAXXLEN)) {
2045 /* extend right lXAD */
2047 XADlength(lxad, lxlen + nxlen);
2049 /* If we just merged two extents together, need to make sure the
2050 * right extent gets logged. If the left one is marked XAD_NEW,
2051 * then we know it will be logged. Otherwise, mark as
2054 if (!(lxad->flag & XAD_NEW))
2055 lxad->flag |= XAD_EXTENDED;
2059 XADoffset(xad, xoff + nxlen);
2060 XADlength(xad, xlen - nxlen);
2061 XADaddress(xad, xaddr + nxlen);
2063 } else { /* (xlen == nxlen) */
2066 if (index < nextindex - 1)
2067 memmove(&p->xad[index], &p->xad[index + 1],
2068 (nextindex - index -
2069 1) << L2XTSLOTSIZE);
2071 p->header.nextindex =
2072 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2076 newindex = index + 1;
2077 nextindex = le16_to_cpu(p->header.nextindex);
2078 xoff = nxoff = offsetXAD(lxad);
2079 xlen = nxlen = lxlen + nxlen;
2080 xaddr = nxaddr = addressXAD(lxad);
2086 * replace XAD with nXAD
2088 replace: /* (nxoff == xoff) */
2089 if (nxlen == xlen) {
2090 /* replace XAD with nXAD:recorded */
2092 xad->flag = xflag & ~XAD_NOTRECORDED;
2095 } else /* (nxlen < xlen) */
2099 * coalesce with right XAD
2101 coalesceRight: /* (xoff <= nxoff) */
2102 /* is XAD last entry of page ? */
2103 if (newindex == nextindex) {
2109 /* is nXAD logically and physically contiguous with rXAD ? */
2110 rxad = &p->xad[index + 1];
2111 rxlen = lengthXAD(rxad);
2112 if (!(rxad->flag & XAD_NOTRECORDED) &&
2113 (nxoff + nxlen == offsetXAD(rxad)) &&
2114 (nxaddr + nxlen == addressXAD(rxad)) &&
2115 (rxlen + nxlen < MAXXLEN)) {
2116 /* extend left rXAD */
2117 XADoffset(rxad, nxoff);
2118 XADlength(rxad, rxlen + nxlen);
2119 XADaddress(rxad, nxaddr);
2121 /* If we just merged two extents together, need to make sure
2122 * the left extent gets logged. If the right one is marked
2123 * XAD_NEW, then we know it will be logged. Otherwise, mark as
2126 if (!(rxad->flag & XAD_NEW))
2127 rxad->flag |= XAD_EXTENDED;
2131 XADlength(xad, xlen - nxlen);
2132 else { /* (xlen == nxlen) */
2135 memmove(&p->xad[index], &p->xad[index + 1],
2136 (nextindex - index - 1) << L2XTSLOTSIZE);
2138 p->header.nextindex =
2139 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2144 } else if (xoff == nxoff)
2147 if (xoff >= nxoff) {
2149 jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff");
2152 /* #endif _JFS_WIP_COALESCE */
2155 * split XAD into (lXAD, nXAD):
2158 * --|----------XAD----------|--
2161 updateRight: /* (xoff < nxoff) */
2162 /* truncate old XAD as lXAD:not_recorded */
2163 xad = &p->xad[index];
2164 XADlength(xad, nxoff - xoff);
2166 /* insert nXAD:recorded */
2167 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2168 rootsplit = p->header.flag & BT_ROOT;
2170 /* xtSpliUp() unpins leaf pages */
2172 split.index = newindex;
2173 split.flag = xflag & ~XAD_NOTRECORDED;
2176 split.addr = nxaddr;
2177 split.pxdlist = NULL;
2178 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2182 * if leaf root has been split, original root has been
2183 * copied to new child page, i.e., original entry now
2184 * resides on the new child page;
2187 ASSERT(p->header.nextindex ==
2188 cpu_to_le16(XTENTRYSTART + 1));
2189 xad = &p->xad[XTENTRYSTART];
2190 bn = addressXAD(xad);
2192 /* get new child page */
2193 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2197 BT_MARK_DIRTY(mp, ip);
2198 if (!test_cflag(COMMIT_Nolink, ip)) {
2199 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2200 xtlck = (struct xtlock *) & tlck->lock;
2203 /* get back old page */
2204 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2208 /* is nXAD on new page ? */
2210 (le16_to_cpu(p->header.maxentry) >> 1)) {
2213 le16_to_cpu(p->header.nextindex) +
2219 /* if insert into middle, shift right remaining entries */
2220 if (newindex < nextindex)
2221 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2222 (nextindex - newindex) << L2XTSLOTSIZE);
2224 /* insert the entry */
2225 xad = &p->xad[newindex];
2227 xad->flag = xflag & ~XAD_NOTRECORDED;
2229 /* advance next available entry index. */
2230 p->header.nextindex =
2231 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2235 * does nXAD force 3-way split ?
2238 * --|----------XAD-------------|--
2239 * |-lXAD-| |-rXAD -|
2241 if (nxoff + nxlen == xoff + xlen)
2244 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2246 /* close out old page */
2247 if (!test_cflag(COMMIT_Nolink, ip)) {
2248 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2249 min(index0, (int)xtlck->lwm.offset) : index0;
2251 le16_to_cpu(p->header.nextindex) -
2255 bn = le64_to_cpu(p->header.next);
2258 /* get new right page */
2259 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2263 BT_MARK_DIRTY(mp, ip);
2264 if (!test_cflag(COMMIT_Nolink, ip)) {
2265 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2266 xtlck = (struct xtlock *) & tlck->lock;
2269 index0 = index = newindex;
2273 newindex = index + 1;
2274 nextindex = le16_to_cpu(p->header.nextindex);
2275 xlen = xlen - (nxoff - xoff);
2279 /* recompute split pages */
2280 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2283 if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT)))
2286 /* retrieve search result */
2287 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2291 jfs_error(ip->i_sb, "xtUpdate: xtSearch failed");
2295 if (index0 != index) {
2298 "xtUpdate: unexpected value of index");
2304 * split XAD into (nXAD, rXAD)
2307 * --|----------XAD----------|--
2310 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
2311 /* update old XAD with nXAD:recorded */
2312 xad = &p->xad[index];
2314 xad->flag = xflag & ~XAD_NOTRECORDED;
2316 /* insert rXAD:not_recorded */
2317 xoff = xoff + nxlen;
2318 xlen = xlen - nxlen;
2319 xaddr = xaddr + nxlen;
2320 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2321 rootsplit = p->header.flag & BT_ROOT;
2324 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2326 /* xtSpliUp() unpins leaf pages */
2328 split.index = newindex;
2333 split.pxdlist = NULL;
2334 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2338 * if leaf root has been split, original root has been
2339 * copied to new child page, i.e., original entry now
2340 * resides on the new child page;
2343 ASSERT(p->header.nextindex ==
2344 cpu_to_le16(XTENTRYSTART + 1));
2345 xad = &p->xad[XTENTRYSTART];
2346 bn = addressXAD(xad);
2348 /* get new child page */
2349 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2353 BT_MARK_DIRTY(mp, ip);
2354 if (!test_cflag(COMMIT_Nolink, ip)) {
2355 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2356 xtlck = (struct xtlock *) & tlck->lock;
2359 /* get back old page */
2360 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2365 /* if insert into middle, shift right remaining entries */
2366 if (newindex < nextindex)
2367 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2368 (nextindex - newindex) << L2XTSLOTSIZE);
2370 /* insert the entry */
2371 xad = &p->xad[newindex];
2372 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2374 /* advance next available entry index. */
2375 p->header.nextindex =
2376 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2380 if (!test_cflag(COMMIT_Nolink, ip)) {
2381 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2382 min(index0, (int)xtlck->lwm.offset) : index0;
2383 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2387 /* unpin the leaf page */
2397 * function: grow in append mode from contiguous region specified ;
2400 * tid - transaction id;
2402 * xflag - extent flag:
2403 * xoff - extent offset;
2404 * maxblocks - max extent length;
2405 * xlen - extent length (in/out);
2406 * xaddrp - extent address pointer (in/out):
2411 int xtAppend(tid_t tid, /* transaction id */
2412 struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2413 s32 * xlenp, /* (in/out) */
2414 s64 * xaddrp, /* (in/out) */
2418 struct metapage *mp; /* meta-page buffer */
2419 xtpage_t *p; /* base B+-tree index page */
2421 int index, nextindex;
2422 struct btstack btstack; /* traverse stack */
2423 struct xtsplit split; /* split information */
2427 struct xtlock *xtlck;
2428 int nsplit, nblocks, xlen;
2429 struct pxdlist pxdlist;
2434 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2435 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2438 * search for the entry location at which to insert:
2440 * xtFastSearch() and xtSearch() both returns (leaf page
2441 * pinned, index at which to insert).
2442 * n.b. xtSearch() may return index of maxentry of
2445 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
2448 /* retrieve search result */
2449 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2457 * insert entry for new extent
2462 * if the leaf page is full, split the page and
2463 * propagate up the router entry for the new page from split
2465 * The xtSplitUp() will insert the entry and unpin the leaf page.
2467 nextindex = le16_to_cpu(p->header.nextindex);
2468 if (nextindex < le16_to_cpu(p->header.maxentry))
2472 * allocate new index blocks to cover index page split(s)
2474 nsplit = btstack.nsplit;
2475 split.pxdlist = &pxdlist;
2476 pxdlist.maxnpxd = pxdlist.npxd = 0;
2477 pxd = &pxdlist.pxd[0];
2478 nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2479 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2480 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2481 PXDaddress(pxd, xaddr);
2482 PXDlength(pxd, nblocks);
2489 /* undo allocation */
2494 xlen = min(xlen, maxblocks);
2497 * allocate data extent requested
2499 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2503 split.index = index;
2508 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2509 /* undo data extent allocation */
2510 dbFree(ip, *xaddrp, (s64) * xlenp);
2520 * insert the new entry into the leaf page
2524 * allocate data extent requested
2526 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2529 BT_MARK_DIRTY(mp, ip);
2531 * acquire a transaction lock on the leaf page;
2533 * action: xad insertion/extension;
2535 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2536 xtlck = (struct xtlock *) & tlck->lock;
2538 /* insert the new entry: mark the entry NEW */
2539 xad = &p->xad[index];
2540 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2542 /* advance next available entry index */
2543 p->header.nextindex =
2544 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2547 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2548 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2555 /* unpin the leaf page */
2560 #ifdef _STILL_TO_PORT
2562 /* - TBD for defragmentaion/reorganization -
2567 * delete the entry with the specified key.
2569 * N.B.: whole extent of the entry is assumed to be deleted.
2574 * ENOENT: if the entry is not found.
2578 int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2581 struct btstack btstack;
2584 struct metapage *mp;
2586 int index, nextindex;
2588 struct xtlock *xtlck;
2591 * find the matching entry; xtSearch() pins the page
2593 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0)))
2596 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2598 /* unpin the leaf page */
2604 * delete the entry from the leaf page
2606 nextindex = le16_to_cpu(p->header.nextindex);
2607 p->header.nextindex =
2608 cpu_to_le16(le16_to_cpu(p->header.nextindex) - 1);
2611 * if the leaf page bocome empty, free the page
2613 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2614 return (xtDeleteUp(tid, ip, mp, p, &btstack));
2616 BT_MARK_DIRTY(mp, ip);
2618 * acquire a transaction lock on the leaf page;
2620 * action:xad deletion;
2622 tlck = txLock(tid, ip, mp, tlckXTREE);
2623 xtlck = (struct xtlock *) & tlck->lock;
2625 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2627 /* if delete from middle, shift left/compact the remaining entries */
2628 if (index < nextindex - 1)
2629 memmove(&p->xad[index], &p->xad[index + 1],
2630 (nextindex - index - 1) * sizeof(xad_t));
2638 /* - TBD for defragmentaion/reorganization -
2643 * free empty pages as propagating deletion up the tree
2650 xtDeleteUp(tid_t tid, struct inode *ip,
2651 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2654 struct metapage *mp;
2656 int index, nextindex;
2659 struct btframe *parent;
2661 struct xtlock *xtlck;
2664 * keep root leaf page which has become empty
2666 if (fp->header.flag & BT_ROOT) {
2667 /* keep the root page */
2668 fp->header.flag &= ~BT_INTERNAL;
2669 fp->header.flag |= BT_LEAF;
2670 fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2672 /* XT_PUTPAGE(fmp); */
2678 * free non-root leaf page
2680 if ((rc = xtRelink(tid, ip, fp))) {
2685 xaddr = addressPXD(&fp->header.self);
2686 xlen = lengthPXD(&fp->header.self);
2687 /* free the page extent */
2688 dbFree(ip, xaddr, (s64) xlen);
2690 /* free the buffer page */
2691 discard_metapage(fmp);
2694 * propagate page deletion up the index tree
2696 * If the delete from the parent page makes it empty,
2697 * continue all the way up the tree.
2698 * stop if the root page is reached (which is never deleted) or
2699 * if the entry deletion does not empty the page.
2701 while ((parent = BT_POP(btstack)) != NULL) {
2702 /* get/pin the parent page <sp> */
2703 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2707 index = parent->index;
2709 /* delete the entry for the freed child page from parent.
2711 nextindex = le16_to_cpu(p->header.nextindex);
2714 * the parent has the single entry being deleted:
2715 * free the parent page which has become empty.
2717 if (nextindex == 1) {
2718 if (p->header.flag & BT_ROOT) {
2719 /* keep the root page */
2720 p->header.flag &= ~BT_INTERNAL;
2721 p->header.flag |= BT_LEAF;
2722 p->header.nextindex =
2723 cpu_to_le16(XTENTRYSTART);
2725 /* XT_PUTPAGE(mp); */
2729 /* free the parent page */
2730 if ((rc = xtRelink(tid, ip, p)))
2733 xaddr = addressPXD(&p->header.self);
2734 /* free the page extent */
2736 (s64) JFS_SBI(ip->i_sb)->nbperpage);
2738 /* unpin/free the buffer page */
2739 discard_metapage(mp);
2746 * the parent has other entries remaining:
2747 * delete the router entry from the parent page.
2750 BT_MARK_DIRTY(mp, ip);
2752 * acquire a transaction lock on the leaf page;
2754 * action:xad deletion;
2756 tlck = txLock(tid, ip, mp, tlckXTREE);
2757 xtlck = (struct xtlock *) & tlck->lock;
2759 (xtlck->lwm.offset) ? min(index,
2763 /* if delete from middle,
2764 * shift left/compact the remaining entries in the page
2766 if (index < nextindex - 1)
2767 memmove(&p->xad[index], &p->xad[index + 1],
2768 (nextindex - index -
2769 1) << L2XTSLOTSIZE);
2771 p->header.nextindex =
2772 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2774 jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2775 (ulong) parent->bn, index);
2778 /* unpin the parent page */
2781 /* exit propagation up */
2790 * NAME: xtRelocate()
2792 * FUNCTION: relocate xtpage or data extent of regular file;
2793 * This function is mainly used by defragfs utility.
2795 * NOTE: This routine does not have the logic to handle
2796 * uncommitted allocated extent. The caller should call
2797 * txCommit() to commit all the allocation before call
2801 xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2802 s64 nxaddr, /* new xaddr */
2804 { /* extent type: XTPAGE or DATAEXT */
2806 struct tblock *tblk;
2808 struct xtlock *xtlck;
2809 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
2810 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
2815 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2817 s64 offset, nbytes, nbrd, pno;
2818 int nb, npages, nblks;
2822 struct pxd_lock *pxdlock;
2823 struct btstack btstack; /* traverse stack */
2825 xtype = xtype & EXTENT_TYPE;
2827 xoff = offsetXAD(oxad);
2828 oxaddr = addressXAD(oxad);
2829 xlen = lengthXAD(oxad);
2831 /* validate extent offset */
2832 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2833 if (offset >= ip->i_size)
2834 return -ESTALE; /* stale extent */
2836 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2837 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2840 * 1. get and validate the parent xtpage/xad entry
2841 * covering the source extent to be relocated;
2843 if (xtype == DATAEXT) {
2844 /* search in leaf entry */
2845 rc = xtSearch(ip, xoff, &cmp, &btstack, 0);
2849 /* retrieve search result */
2850 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2857 /* validate for exact match with a single entry */
2858 xad = &pp->xad[index];
2859 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2863 } else { /* (xtype == XTPAGE) */
2865 /* search in internal entry */
2866 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2870 /* retrieve search result */
2871 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2878 /* xtSearchNode() validated for exact match with a single entry
2880 xad = &pp->xad[index];
2882 jfs_info("xtRelocate: parent xad entry validated.");
2885 * 2. relocate the extent
2887 if (xtype == DATAEXT) {
2888 /* if the extent is allocated-but-not-recorded
2889 * there is no real data to be moved in this extent,
2891 if (xad->flag & XAD_NOTRECORDED)
2894 /* release xtpage for cmRead()/xtLookup() */
2900 * copy target data pages to be relocated;
2902 * data extent must start at page boundary and
2903 * multiple of page size (except the last data extent);
2904 * read in each page of the source data extent into cbuf,
2905 * update the cbuf extent descriptor of the page to be
2906 * homeward bound to new dst data extent
2907 * copy the data from the old extent to new extent.
2908 * copy is essential for compressed files to avoid problems
2909 * that can arise if there was a change in compression
2911 * it is a good strategy because it may disrupt cache
2912 * policy to keep the pages in memory afterwards.
2914 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2915 assert((offset & CM_OFFSET) == 0);
2916 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2917 pno = offset >> CM_L2BSIZE;
2918 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2920 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2921 (offset >> CM_L2BSIZE) + 1;
2926 /* process the request one cache buffer at a time */
2927 for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2928 offset += nb, pno++, npages--) {
2929 /* compute page size */
2930 nb = min(nbytes - nbrd, CM_BSIZE);
2932 /* get the cache buffer of the page */
2933 if (rc = cmRead(ip, offset, npages, &cp))
2936 assert(addressPXD(&cp->cm_pxd) == sxaddr);
2937 assert(!cp->cm_modified);
2939 /* bind buffer with the new extent address */
2940 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2941 cmSetXD(ip, cp, pno, dxaddr, nblks);
2943 /* release the cbuf, mark it as modified */
2950 /* get back parent page */
2951 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0)))
2954 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2955 jfs_info("xtRelocate: target data extent relocated.");
2956 } else { /* (xtype == XTPAGE) */
2959 * read in the target xtpage from the source extent;
2961 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2968 * read in sibling pages if any to update sibling pointers;
2971 if (p->header.next) {
2972 nextbn = le64_to_cpu(p->header.next);
2973 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
2982 if (p->header.prev) {
2983 prevbn = le64_to_cpu(p->header.prev);
2984 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
2994 /* at this point, all xtpages to be updated are in memory */
2997 * update sibling pointers of sibling xtpages if any;
3000 BT_MARK_DIRTY(lmp, ip);
3002 txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
3003 lp->header.next = cpu_to_le64(nxaddr);
3008 BT_MARK_DIRTY(rmp, ip);
3010 txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
3011 rp->header.prev = cpu_to_le64(nxaddr);
3016 * update the target xtpage to be relocated
3018 * update the self address of the target page
3019 * and write to destination extent;
3020 * redo image covers the whole xtpage since it is new page
3021 * to the destination extent;
3022 * update of bmap for the free of source extent
3023 * of the target xtpage itself:
3024 * update of bmap for the allocation of destination extent
3025 * of the target xtpage itself:
3026 * update of bmap for the extents covered by xad entries in
3027 * the target xtpage is not necessary since they are not
3029 * if not committed before this relocation,
3030 * target page may contain XAD_NEW entries which must
3031 * be scanned for bmap update (logredo() always
3032 * scan xtpage REDOPAGE image for bmap update);
3033 * if committed before this relocation (tlckRELOCATE),
3034 * scan may be skipped by commit() and logredo();
3036 BT_MARK_DIRTY(mp, ip);
3037 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
3038 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
3039 xtlck = (struct xtlock *) & tlck->lock;
3041 /* update the self address in the xtpage header */
3042 pxd = &p->header.self;
3043 PXDaddress(pxd, nxaddr);
3045 /* linelock for the after image of the whole page */
3047 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
3049 /* update the buffer extent descriptor of target xtpage */
3050 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
3051 bmSetXD(mp, nxaddr, xsize);
3053 /* unpin the target page to new homeward bound */
3055 jfs_info("xtRelocate: target xtpage relocated.");
3059 * 3. acquire maplock for the source extent to be freed;
3061 * acquire a maplock saving the src relocated extent address;
3062 * to free of the extent at commit time;
3065 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
3066 * free PXD of the source data extent (logredo() will update
3067 * bmap for free of source data extent), and update bmap for
3068 * free of the source data extent;
3070 if (xtype == DATAEXT)
3071 tlck = txMaplock(tid, ip, tlckMAP);
3072 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
3073 * for the source xtpage (logredo() will init NoRedoPage
3074 * filter and will also update bmap for free of the source
3075 * xtpage), and update bmap for free of the source xtpage;
3076 * N.B. We use tlckMAP instead of tlkcXTREE because there
3077 * is no buffer associated with this lock since the buffer
3078 * has been redirected to the target location.
3080 else /* (xtype == XTPAGE) */
3081 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
3083 pxdlock = (struct pxd_lock *) & tlck->lock;
3084 pxdlock->flag = mlckFREEPXD;
3085 PXDaddress(&pxdlock->pxd, oxaddr);
3086 PXDlength(&pxdlock->pxd, xlen);
3090 * 4. update the parent xad entry for relocation;
3092 * acquire tlck for the parent entry with XAD_NEW as entry
3093 * update which will write LOG_REDOPAGE and update bmap for
3094 * allocation of XAD_NEW destination extent;
3096 jfs_info("xtRelocate: update parent xad entry.");
3097 BT_MARK_DIRTY(pmp, ip);
3098 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
3099 xtlck = (struct xtlock *) & tlck->lock;
3101 /* update the XAD with the new destination extent; */
3102 xad = &pp->xad[index];
3103 xad->flag |= XAD_NEW;
3104 XADaddress(xad, nxaddr);
3106 xtlck->lwm.offset = min(index, xtlck->lwm.offset);
3107 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
3110 /* unpin the parent xtpage */
3120 * function: search for the internal xad entry covering specified extent.
3121 * This function is mainly used by defragfs utility.
3125 * xad - extent to find;
3126 * cmpp - comparison result:
3127 * btstack - traverse stack;
3128 * flag - search process flag;
3131 * btstack contains (bn, index) of search path traversed to the entry.
3132 * *cmpp is set to result of comparison with the entry returned.
3133 * the page containing the entry is pinned at exit.
3135 static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
3136 int *cmpp, struct btstack * btstack, int flag)
3141 int cmp = 1; /* init for empty page */
3142 s64 bn; /* block number */
3143 struct metapage *mp; /* meta-page buffer */
3144 xtpage_t *p; /* page */
3145 int base, index, lim;
3146 struct btframe *btsp;
3151 xoff = offsetXAD(xad);
3152 xlen = lengthXAD(xad);
3153 xaddr = addressXAD(xad);
3156 * search down tree from root:
3158 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
3159 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
3161 * if entry with search key K is not found
3162 * internal page search find the entry with largest key Ki
3163 * less than K which point to the child page to search;
3164 * leaf page search find the entry with smallest key Kj
3165 * greater than K so that the returned index is the position of
3166 * the entry to be shifted right for insertion of new entry.
3167 * for empty tree, search key is greater than any key of the tree.
3169 * by convention, root bn = 0.
3172 /* get/pin the page to search */
3173 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3176 if (p->header.flag & BT_LEAF) {
3181 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3184 * binary search with search key K on the current page
3186 for (base = XTENTRYSTART; lim; lim >>= 1) {
3187 index = base + (lim >> 1);
3189 XT_CMP(cmp, xoff, &p->xad[index], t64);
3194 * verify for exact match;
3196 if (xaddr == addressXAD(&p->xad[index]) &&
3197 xoff == offsetXAD(&p->xad[index])) {
3200 /* save search result */
3201 btsp = btstack->top;
3203 btsp->index = index;
3209 /* descend/search its child page */
3220 * search miss - non-leaf page:
3222 * base is the smallest index with key (Kj) greater than
3223 * search key (K) and may be zero or maxentry index.
3224 * if base is non-zero, decrement base by one to get the parent
3225 * entry of the child page to search.
3227 index = base ? base - 1 : base;
3230 * go down to child page
3233 /* get the child page block number */
3234 bn = addressXAD(&p->xad[index]);
3236 /* unpin the parent page */
3246 * link around a freed page.
3255 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
3258 struct metapage *mp;
3262 nextbn = le64_to_cpu(p->header.next);
3263 prevbn = le64_to_cpu(p->header.prev);
3265 /* update prev pointer of the next page */
3267 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3272 * acquire a transaction lock on the page;
3274 * action: update prev pointer;
3276 BT_MARK_DIRTY(mp, ip);
3277 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3279 /* the page may already have been tlock'd */
3281 p->header.prev = cpu_to_le64(prevbn);
3286 /* update next pointer of the previous page */
3288 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3293 * acquire a transaction lock on the page;
3295 * action: update next pointer;
3297 BT_MARK_DIRTY(mp, ip);
3298 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3300 /* the page may already have been tlock'd */
3302 p->header.next = le64_to_cpu(nextbn);
3309 #endif /* _STILL_TO_PORT */
3315 * initialize file root (inline in inode)
3317 void xtInitRoot(tid_t tid, struct inode *ip)
3322 * acquire a transaction lock on the root
3326 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3327 tlckXTREE | tlckNEW);
3328 p = &JFS_IP(ip)->i_xtroot;
3330 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3331 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3333 if (S_ISDIR(ip->i_mode))
3334 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3336 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3346 * We can run into a deadlock truncating a file with a large number of
3347 * xtree pages (large fragmented file). A robust fix would entail a
3348 * reservation system where we would reserve a number of metadata pages
3349 * and tlocks which we would be guaranteed without a deadlock. Without
3350 * this, a partial fix is to limit number of metadata pages we will lock
3351 * in a single transaction. Currently we will truncate the file so that
3352 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3353 * will be responsible for ensuring that the current transaction gets
3354 * committed, and that subsequent transactions are created to truncate
3355 * the file further if needed.
3357 #define MAX_TRUNCATE_LEAVES 50
3363 * traverse for truncation logging backward bottom up;
3364 * terminate at the last extent entry at the current subtree
3365 * root page covering new down size.
3366 * truncation may occur within the last extent entry.
3372 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3378 * 1. truncate (non-COMMIT_NOLINK file)
3379 * by jfs_truncate() or jfs_open(O_TRUNC):
3381 * 2. truncate index table of directory when last entry removed
3382 * map update via tlock at commit time;
3384 * Call xtTruncate_pmap instead
3386 * 1. remove (free zero link count) on last reference release
3387 * (pmap has been freed at commit zero link count);
3388 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3390 * map update directly at truncation time;
3393 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3394 * else if (TRUNCATE)
3395 * must write LOG_NOREDOPAGE for deleted index page;
3397 * pages may already have been tlocked by anonymous transactions
3398 * during file growth (i.e., write) before truncation;
3400 * except last truncated entry, deleted entries remains as is
3401 * in the page (nextindex is updated) for other use
3402 * (e.g., log/update allocation map): this avoid copying the page
3403 * info but delay free of pages;
3406 s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3410 struct metapage *mp;
3413 int index, nextindex;
3416 int xlen, len, freexlen;
3417 struct btstack btstack;
3418 struct btframe *parent;
3419 struct tblock *tblk = 0;
3420 struct tlock *tlck = 0;
3421 struct xtlock *xtlck = 0;
3422 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
3423 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
3426 int locked_leaves = 0;
3428 /* save object truncation type */
3430 tblk = tid_to_tblock(tid);
3431 tblk->xflag |= flag;
3437 assert(flag != COMMIT_PMAP);
3439 if (flag == COMMIT_PWMAP)
3443 xadlock.flag = mlckFREEXADLIST;
3448 * if the newsize is not an integral number of pages,
3449 * the file between newsize and next page boundary will
3451 * if truncating into a file hole, it will cause
3452 * a full block to be allocated for the logical block.
3456 * release page blocks of truncated region <teof, eof>
3458 * free the data blocks from the leaf index blocks.
3459 * delete the parent index entries corresponding to
3460 * the freed child data/index blocks.
3461 * free the index blocks themselves which aren't needed
3462 * in new sized file.
3464 * index blocks are updated only if the blocks are to be
3465 * retained in the new sized file.
3466 * if type is PMAP, the data and index pages are NOT
3467 * freed, and the data and index blocks are NOT freed
3469 * (this will allow continued access of data/index of
3470 * temporary file (zerolink count file truncated to zero-length)).
3472 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3473 JFS_SBI(ip->i_sb)->l2bsize;
3481 * root resides in the inode
3486 * first access of each page:
3489 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3493 /* process entries backward from last index */
3494 index = le16_to_cpu(p->header.nextindex) - 1;
3496 if (p->header.flag & BT_INTERNAL)
3503 /* Since this is the rightmost leaf, and we may have already freed
3504 * a page that was formerly to the right, let's make sure that the
3505 * next pointer is zero.
3511 /* does region covered by leaf page precede Teof ? */
3512 xad = &p->xad[index];
3513 xoff = offsetXAD(xad);
3514 xlen = lengthXAD(xad);
3515 if (teof >= xoff + xlen) {
3520 /* (re)acquire tlock of the leaf page */
3522 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3524 * We need to limit the size of the transaction
3525 * to avoid exhausting pagecache & tlocks
3528 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3531 tlck = txLock(tid, ip, mp, tlckXTREE);
3532 tlck->type = tlckXTREE | tlckTRUNCATE;
3533 xtlck = (struct xtlock *) & tlck->lock;
3534 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3536 BT_MARK_DIRTY(mp, ip);
3539 * scan backward leaf page entries
3541 for (; index >= XTENTRYSTART; index--) {
3542 xad = &p->xad[index];
3543 xoff = offsetXAD(xad);
3544 xlen = lengthXAD(xad);
3545 xaddr = addressXAD(xad);
3548 * The "data" for a directory is indexed by the block
3549 * device's address space. This metadata must be invalidated
3552 if (S_ISDIR(ip->i_mode) && (teof == 0))
3553 invalidate_xad_metapages(ip, *xad);
3555 * entry beyond eof: continue scan of current page
3557 * ---|---=======------->
3566 * (xoff <= teof): last entry to be deleted from page;
3567 * If other entries remain in page: keep and update the page.
3571 * eof == entry_start: delete the entry
3573 * -------|=======------->
3580 if (index == XTENTRYSTART)
3586 * eof within the entry: truncate the entry.
3588 * -------===|===------->
3591 else if (teof < xoff + xlen) {
3592 /* update truncated entry */
3594 freexlen = xlen - len;
3595 XADlength(xad, len);
3597 /* save pxd of truncated extent in tlck */
3599 if (log) { /* COMMIT_PWMAP */
3600 xtlck->lwm.offset = (xtlck->lwm.offset) ?
3601 min(index, (int)xtlck->lwm.offset) : index;
3602 xtlck->lwm.length = index + 1 -
3604 xtlck->twm.offset = index;
3605 pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3606 pxdlock->flag = mlckFREEPXD;
3607 PXDaddress(&pxdlock->pxd, xaddr);
3608 PXDlength(&pxdlock->pxd, freexlen);
3610 /* free truncated extent */
3611 else { /* COMMIT_WMAP */
3613 pxdlock = (struct pxd_lock *) & xadlock;
3614 pxdlock->flag = mlckFREEPXD;
3615 PXDaddress(&pxdlock->pxd, xaddr);
3616 PXDlength(&pxdlock->pxd, freexlen);
3617 txFreeMap(ip, pxdlock, 0, COMMIT_WMAP);
3619 /* reset map lock */
3620 xadlock.flag = mlckFREEXADLIST;
3623 /* current entry is new last entry; */
3624 nextindex = index + 1;
3629 * eof beyond the entry:
3631 * -------=======---|--->
3634 else { /* (xoff + xlen < teof) */
3636 nextindex = index + 1;
3639 if (nextindex < le16_to_cpu(p->header.nextindex)) {
3640 if (!log) { /* COMMIT_WAMP */
3641 xadlock.xdlist = &p->xad[nextindex];
3643 le16_to_cpu(p->header.nextindex) -
3645 txFreeMap(ip, (struct maplock *) & xadlock, 0,
3648 p->header.nextindex = cpu_to_le16(nextindex);
3653 /* assert(freed == 0); */
3655 } /* end scan of leaf page entries */
3660 * leaf page become empty: free the page if type != PMAP
3662 if (log) { /* COMMIT_PWMAP */
3663 /* txCommit() with tlckFREE:
3664 * free data extents covered by leaf [XTENTRYSTART:hwm);
3665 * invalidate leaf if COMMIT_PWMAP;
3666 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3668 tlck->type = tlckXTREE | tlckFREE;
3669 } else { /* COMMIT_WAMP */
3671 /* free data extents covered by leaf */
3672 xadlock.xdlist = &p->xad[XTENTRYSTART];
3674 le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3675 txFreeMap(ip, (struct maplock *) & xadlock, 0, COMMIT_WMAP);
3678 if (p->header.flag & BT_ROOT) {
3679 p->header.flag &= ~BT_INTERNAL;
3680 p->header.flag |= BT_LEAF;
3681 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3683 XT_PUTPAGE(mp); /* debug */
3686 if (log) { /* COMMIT_PWMAP */
3687 /* page will be invalidated at tx completion
3690 } else { /* COMMIT_WMAP */
3693 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3695 /* invalidate empty leaf page */
3696 discard_metapage(mp);
3701 * the leaf page become empty: delete the parent entry
3702 * for the leaf page if the parent page is to be kept
3703 * in the new sized file.
3707 * go back up to the parent page
3710 /* pop/restore parent entry for the current child page */
3711 if ((parent = BT_POP(&btstack)) == NULL)
3712 /* current page must have been root */
3715 /* get back the parent page */
3717 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3721 index = parent->index;
3724 * child page was not empty:
3727 /* has any entry deleted from parent ? */
3728 if (index < le16_to_cpu(p->header.nextindex) - 1) {
3729 /* (re)acquire tlock on the parent page */
3730 if (log) { /* COMMIT_PWMAP */
3731 /* txCommit() with tlckTRUNCATE:
3732 * free child extents covered by parent [);
3734 tlck = txLock(tid, ip, mp, tlckXTREE);
3735 xtlck = (struct xtlock *) & tlck->lock;
3736 if (!(tlck->type & tlckTRUNCATE)) {
3738 le16_to_cpu(p->header.
3741 tlckXTREE | tlckTRUNCATE;
3743 } else { /* COMMIT_WMAP */
3745 /* free child extents covered by parent */
3746 xadlock.xdlist = &p->xad[index + 1];
3748 le16_to_cpu(p->header.nextindex) -
3750 txFreeMap(ip, (struct maplock *) & xadlock, 0,
3753 BT_MARK_DIRTY(mp, ip);
3755 p->header.nextindex = cpu_to_le16(index + 1);
3762 * child page was empty:
3764 nfreed += lengthXAD(&p->xad[index]);
3767 * During working map update, child page's tlock must be handled
3768 * before parent's. This is because the parent's tlock will cause
3769 * the child's disk space to be marked available in the wmap, so
3770 * it's important that the child page be released by that time.
3772 * ToDo: tlocks should be on doubly-linked list, so we can
3773 * quickly remove it and add it to the end.
3777 * Move parent page's tlock to the end of the tid's tlock list
3779 if (log && mp->lid && (tblk->last != mp->lid) &&
3780 lid_to_tlock(mp->lid)->tid) {
3781 lid_t lid = mp->lid;
3784 tlck = lid_to_tlock(lid);
3786 if (tblk->next == lid)
3787 tblk->next = tlck->next;
3789 for (prev = lid_to_tlock(tblk->next);
3791 prev = lid_to_tlock(prev->next)) {
3794 prev->next = tlck->next;
3796 lid_to_tlock(tblk->last)->next = lid;
3802 * parent page become empty: free the page
3804 if (index == XTENTRYSTART) {
3805 if (log) { /* COMMIT_PWMAP */
3806 /* txCommit() with tlckFREE:
3807 * free child extents covered by parent;
3808 * invalidate parent if COMMIT_PWMAP;
3810 tlck = txLock(tid, ip, mp, tlckXTREE);
3811 xtlck = (struct xtlock *) & tlck->lock;
3813 le16_to_cpu(p->header.nextindex) - 1;
3814 tlck->type = tlckXTREE | tlckFREE;
3815 } else { /* COMMIT_WMAP */
3817 /* free child extents covered by parent */
3818 xadlock.xdlist = &p->xad[XTENTRYSTART];
3820 le16_to_cpu(p->header.nextindex) -
3822 txFreeMap(ip, (struct maplock *) & xadlock, 0,
3825 BT_MARK_DIRTY(mp, ip);
3827 if (p->header.flag & BT_ROOT) {
3828 p->header.flag &= ~BT_INTERNAL;
3829 p->header.flag |= BT_LEAF;
3830 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3831 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3833 * Shrink root down to allow inline
3834 * EA (otherwise fsck complains)
3836 p->header.maxentry =
3837 cpu_to_le16(XTROOTINITSLOT);
3838 JFS_IP(ip)->mode2 |= INLINEEA;
3841 XT_PUTPAGE(mp); /* debug */
3844 if (log) { /* COMMIT_PWMAP */
3845 /* page will be invalidated at tx completion
3848 } else { /* COMMIT_WMAP */
3851 lid_to_tlock(mp->lid)->flag |=
3854 /* invalidate parent page */
3855 discard_metapage(mp);
3858 /* parent has become empty and freed:
3859 * go back up to its parent page
3866 * parent page still has entries for front region;
3869 /* try truncate region covered by preceding entry
3870 * (process backward)
3874 /* go back down to the child page corresponding
3881 * internal page: go down to child page of current entry
3884 /* save current parent entry for the child page */
3885 BT_PUSH(&btstack, bn, index);
3887 /* get child page */
3888 xad = &p->xad[index];
3889 bn = addressXAD(xad);
3892 * first access of each internal entry:
3894 /* release parent page */
3897 /* process the child page */
3902 * update file resource stat
3906 if (S_ISDIR(ip->i_mode) && !newsize)
3907 ip->i_size = 1; /* fsck hates zero-length directories */
3909 ip->i_size = newsize;
3911 /* update nblocks to reflect freed blocks */
3912 ip->i_blocks -= LBLK2PBLK(ip->i_sb, nfreed);
3915 * free tlock of invalidated pages
3917 if (flag == COMMIT_WMAP)
3928 * Perform truncate to zero lenghth for deleted file, leaving the
3929 * the xtree and working map untouched. This allows the file to
3930 * be accessed via open file handles, while the delete of the file
3931 * is committed to disk.
3936 * s64 committed_size)
3938 * return: new committed size
3942 * To avoid deadlock by holding too many transaction locks, the
3943 * truncation may be broken up into multiple transactions.
3944 * The committed_size keeps track of part of the file has been
3945 * freed from the pmaps.
3947 s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3950 struct btstack btstack;
3953 int locked_leaves = 0;
3954 struct metapage *mp;
3956 struct btframe *parent;
3958 struct tblock *tblk;
3959 struct tlock *tlck = 0;
3963 struct xtlock *xtlck = 0;
3965 /* save object truncation type */
3966 tblk = tid_to_tblock(tid);
3967 tblk->xflag |= COMMIT_PMAP;
3972 if (committed_size) {
3973 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
3974 rc = xtSearch(ip, xoff, &cmp, &btstack, 0);
3978 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3983 "xtTruncate_pmap: did not find extent");
3990 * root resides in the inode
3995 * first access of each page:
3998 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4002 /* process entries backward from last index */
4003 index = le16_to_cpu(p->header.nextindex) - 1;
4005 if (p->header.flag & BT_INTERNAL)
4013 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
4015 * We need to limit the size of the transaction
4016 * to avoid exhausting pagecache & tlocks
4018 xad = &p->xad[index];
4019 xoff = offsetXAD(xad);
4020 xlen = lengthXAD(xad);
4022 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
4024 tlck = txLock(tid, ip, mp, tlckXTREE);
4025 tlck->type = tlckXTREE | tlckFREE;
4026 xtlck = (struct xtlock *) & tlck->lock;
4027 xtlck->hwm.offset = index;
4033 * go back up to the parent page
4036 /* pop/restore parent entry for the current child page */
4037 if ((parent = BT_POP(&btstack)) == NULL)
4038 /* current page must have been root */
4041 /* get back the parent page */
4043 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4047 index = parent->index;
4050 * parent page become empty: free the page
4052 if (index == XTENTRYSTART) {
4053 /* txCommit() with tlckFREE:
4054 * free child extents covered by parent;
4055 * invalidate parent if COMMIT_PWMAP;
4057 tlck = txLock(tid, ip, mp, tlckXTREE);
4058 xtlck = (struct xtlock *) & tlck->lock;
4060 le16_to_cpu(p->header.nextindex) - 1;
4061 tlck->type = tlckXTREE | tlckFREE;
4065 if (p->header.flag & BT_ROOT) {
4073 * parent page still has entries for front region;
4078 * internal page: go down to child page of current entry
4081 /* save current parent entry for the child page */
4082 BT_PUSH(&btstack, bn, index);
4084 /* get child page */
4085 xad = &p->xad[index];
4086 bn = addressXAD(xad);
4089 * first access of each internal entry:
4091 /* release parent page */
4094 /* process the child page */
4103 #ifdef _JFS_DEBUG_XTREE
4107 * function: traverse forward
4109 int xtDisplayTree(struct inode *ip)
4112 struct metapage *mp;
4115 int index, lastindex, v, h;
4117 struct btstack btstack;
4118 struct btframe *btsp;
4119 struct btframe *parent;
4121 printk("display B+-tree.\n");
4124 btsp = btstack.stack;
4129 * root resides in the inode
4135 * first access of each page:
4138 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4142 /* process entries forward from first index */
4143 index = XTENTRYSTART;
4144 lastindex = le16_to_cpu(p->header.nextindex) - 1;
4146 if (p->header.flag & BT_INTERNAL) {
4148 * first access of each internal page
4151 } else { /* (p->header.flag & BT_LEAF) */
4154 * first access of each leaf page
4156 printf("leaf page ");
4157 xtDisplayPage(ip, bn, p);
4159 /* unpin the leaf page */
4164 * go back up to the parent page
4167 /* pop/restore parent entry for the current child page */
4168 if ((parent = (btsp == btstack.stack ? NULL : --btsp)) == NULL)
4169 /* current page must have been root */
4173 * parent page scan completed
4175 if ((index = parent->index) == (lastindex = parent->lastindex)) {
4176 /* go back up to the parent page */
4181 * parent page has entries remaining
4183 /* get back the parent page */
4185 /* v = parent->level; */
4186 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4190 /* get next parent entry */
4194 * internal page: go down to child page of current entry
4197 /* push/save current parent entry for the child page */
4198 btsp->bn = pbn = bn;
4199 btsp->index = index;
4200 btsp->lastindex = lastindex;
4201 /* btsp->level = v; */
4202 /* btsp->node = h; */
4205 /* get child page */
4206 xad = &p->xad[index];
4207 bn = addressXAD(xad);
4210 * first access of each internal entry:
4212 /* release parent page */
4215 printk("traverse down 0x%lx[%d]->0x%lx\n", (ulong) pbn, index,
4220 /* process the child page */
4228 * function: display page
4230 int xtDisplayPage(struct inode *ip, s64 bn, xtpage_t * p)
4237 /* display page control */
4238 printf("bn:0x%lx flag:0x%x nextindex:%d\n",
4239 (ulong) bn, p->header.flag,
4240 le16_to_cpu(p->header.nextindex));
4242 /* display entries */
4243 xad = &p->xad[XTENTRYSTART];
4244 for (i = XTENTRYSTART, j = 1; i < le16_to_cpu(p->header.nextindex);
4246 xoff = offsetXAD(xad);
4247 xaddr = addressXAD(xad);
4248 xlen = lengthXAD(xad);
4249 printf("\t[%d] 0x%lx:0x%lx(0x%x)", i, (ulong) xoff,
4250 (ulong) xaddr, xlen);
4260 #endif /* _JFS_DEBUG_XTREE */
4268 * traverse for allocation acquiring tlock at commit time
4269 * (vs at the time of update) logging backward top down
4272 * problem - establishing that all new allocation have been
4273 * processed both for append and random write in sparse file
4274 * at the current entry at the current subtree root page
4277 int xtGather(btree_t *t)
4284 struct btstack btstack;
4285 struct btsf *parent;
4293 * root resides in the inode
4296 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4300 /* new root is NOT pointed by a new entry
4301 if (p->header.flag & NEW)
4302 allocate new page lock;
4303 write a NEWPAGE log;
4308 * first access of each page:
4310 /* process entries backward from last index */
4311 index = le16_to_cpu(p->header.nextindex) - 1;
4313 if (p->header.flag & BT_LEAF) {
4315 * first access of each leaf page
4317 /* process leaf page entries backward */
4318 for (; index >= XTENTRYSTART; index--) {
4321 * if newpage, log NEWPAGE.
4323 if (e->flag & XAD_NEW) {
4324 nfound =+ entry->length;
4325 update current page lock for the entry;
4328 * if moved, log move.
4330 } else if (e->flag & XAD_MOVED) {
4332 update current page lock for the entry;
4337 /* unpin the leaf page */
4341 * go back up to the parent page
4344 /* restore parent entry for the current child page */
4345 if ((parent = BT_POP(&btstack)) == NULL)
4346 /* current page must have been root */
4349 if ((index = parent->index) == XTENTRYSTART) {
4351 * parent page scan completed
4353 /* go back up to the parent page */
4357 * parent page has entries remaining
4359 /* get back the parent page */
4361 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4365 /* first subroot page which
4366 * covers all new allocated blocks
4367 * itself not new/modified.
4368 * (if modified from split of descendent,
4369 * go down path of split page)
4371 if (nfound == nnew &&
4372 !(p->header.flag & (NEW | MOD)))
4376 /* process parent page entries backward */
4381 * first access of each internal page
4386 * internal page: go down to child page of current entry
4389 /* save current parent entry for the child page */
4390 BT_PUSH(&btstack, bn, index);
4392 /* get current entry for the child page */
4396 * first access of each internal entry:
4399 * if new entry, log btree_tnewentry.
4401 if (e->flag & XAD_NEW)
4402 update parent page lock for the entry;
4405 /* release parent page */
4408 /* get child page */
4410 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4415 * first access of each non-root page:
4418 * if new, log btree_newpage.
4420 if (p->header.flag & NEW)
4421 allocate new page lock;
4422 write a NEWPAGE log (next, prev);
4425 /* process the child page */
4431 #endif /* _JFS_WIP */
4434 #ifdef CONFIG_JFS_STATISTICS
4435 int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length,
4436 int *eof, void *data)
4441 len += sprintf(buffer,
4442 "JFS Xtree statistics\n"
4443 "====================\n"
4445 "fast searches = %d\n"
4452 *start = buffer + begin;