2 * Copyright (C) International Business Machines Corp., 2000-2005
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 <linux/quotaops.h>
24 #include "jfs_incore.h"
25 #include "jfs_filsys.h"
26 #include "jfs_metapage.h"
28 #include "jfs_dinode.h"
29 #include "jfs_superblock.h"
30 #include "jfs_debug.h"
35 #define XT_INSERT 0x00000001
38 * xtree key/entry comparison: extent offset
41 * -1: k < start of extent
42 * 0: start_of_extent <= k <= end_of_extent
43 * 1: k > end_of_extent
45 #define XT_CMP(CMP, K, X, OFFSET64)\
47 OFFSET64 = offsetXAD(X);\
48 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
49 ((K) < OFFSET64) ? -1 : 0;\
52 /* write a xad entry */
53 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
55 (XAD)->flag = (FLAG);\
56 XADoffset((XAD), (OFF));\
57 XADlength((XAD), (LEN));\
58 XADaddress((XAD), (ADDR));\
61 #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
63 /* get page buffer for specified block address */
64 /* ToDo: Replace this ugly macro with a function */
65 #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
67 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
70 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
71 (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
72 (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
74 jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
83 #define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
85 #define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
86 BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
87 /* xtree entry parameter descriptor */
95 struct pxdlist *pxdlist;
102 #ifdef CONFIG_JFS_STATISTICS
114 static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
115 struct btstack * btstack, int flag);
117 static int xtSplitUp(tid_t tid,
119 struct xtsplit * split, struct btstack * btstack);
121 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
122 struct metapage ** rmpp, s64 * rbnp);
124 static int xtSplitRoot(tid_t tid, struct inode *ip,
125 struct xtsplit * split, struct metapage ** rmpp);
127 #ifdef _STILL_TO_PORT
128 static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
129 xtpage_t * fp, struct btstack * btstack);
131 static int xtSearchNode(struct inode *ip,
133 int *cmpp, struct btstack * btstack, int flag);
135 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
136 #endif /* _STILL_TO_PORT */
138 /* External references */
143 /* #define _JFS_DEBUG_XTREE 1 */
149 * function: map a single page into a physical extent;
151 int xtLookup(struct inode *ip, s64 lstart,
152 s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
155 struct btstack btstack;
162 s64 next, size, xoff, xend;
170 /* is lookup offset beyond eof ? */
171 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
172 JFS_SBI(ip->i_sb)->l2bsize;
173 if (lstart >= size) {
174 jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
175 (ulong) lstart, (ulong) size);
181 * search for the xad entry covering the logical extent
184 if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
185 jfs_err("xtLookup: xtSearch returned %d", rc);
190 * compute the physical extent covering logical extent
192 * N.B. search may have failed (e.g., hole in sparse file),
193 * and returned the index of the next entry.
195 /* retrieve search result */
196 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
198 /* is xad found covering start of logical extent ?
199 * lstart is a page start address,
200 * i.e., lstart cannot start in a hole;
204 *plen = min(next - lstart, llen);
211 xad = &p->xad[index];
212 xoff = offsetXAD(xad);
213 xlen = lengthXAD(xad);
215 xaddr = addressXAD(xad);
217 /* initialize new pxd */
219 *paddr = xaddr + (lstart - xoff);
220 /* a page must be fully covered by an xad */
221 *plen = min(xend - lstart, llen);
233 * function: map a single logical extent into a list of physical extent;
237 * struct lxdlist *lxdlist, lxd list (in)
238 * struct xadlist *xadlist, xad list (in/out)
241 * coverage of lxd by xad under assumption of
242 * . lxd's are ordered and disjoint.
243 * . xad's are ordered and disjoint.
248 * note: a page being written (even a single byte) is backed fully,
249 * except the last page which is only backed with blocks
250 * required to cover the last byte;
251 * the extent backing a page is fully contained within an xad;
253 int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
254 struct xadlist * xadlist, int flag)
257 struct btstack btstack;
265 s64 size, lstart, lend, xstart, xend, pstart;
266 s64 llen, xlen, plen;
268 int nlxd, npxd, maxnpxd;
270 npxd = xadlist->nxad = 0;
271 maxnpxd = xadlist->maxnxad;
274 nlxd = lxdlist->nlxd;
277 lstart = offsetLXD(lxd);
278 llen = lengthLXD(lxd);
279 lend = lstart + llen;
281 size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
282 JFS_SBI(ip->i_sb)->l2bsize;
285 * search for the xad entry covering the logical extent
291 if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
295 * compute the physical extent covering logical extent
297 * N.B. search may have failed (e.g., hole in sparse file),
298 * and returned the index of the next entry.
301 /* retrieve search result */
302 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
304 /* is xad on the next sibling page ? */
305 if (index == le16_to_cpu(p->header.nextindex)) {
306 if (p->header.flag & BT_ROOT)
309 if ((bn = le64_to_cpu(p->header.next)) == 0)
314 /* get next sibling page */
315 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
319 index = XTENTRYSTART;
322 xad = &p->xad[index];
325 * is lxd covered by xad ?
328 xstart = offsetXAD(xad);
329 xlen = lengthXAD(xad);
330 xend = xstart + xlen;
331 xaddr = addressXAD(xad);
337 /* (lstart <= xstart) */
339 /* lxd is NOT covered by xad */
340 if (lend <= xstart) {
348 lstart = offsetLXD(lxd);
349 llen = lengthLXD(lxd);
350 lend = lstart + llen;
354 /* compare with the current xad */
357 /* lxd is covered by xad */
358 else { /* (xstart < lend) */
360 /* initialize new pxd */
362 plen = min(lend - xstart, xlen);
368 /* (xstart < lstart) */
370 /* lxd is covered by xad */
372 /* initialize new pxd */
374 plen = min(xend - lstart, llen);
375 paddr = xaddr + (lstart - xstart);
379 /* lxd is NOT covered by xad */
380 else { /* (xend <= lstart) */
385 * linear search next xad covering lxd on
386 * the current xad page, and then tree search
388 if (index == le16_to_cpu(p->header.nextindex) - 1) {
389 if (p->header.flag & BT_ROOT)
398 /* compare with new xad */
404 * lxd is covered by xad and a new pxd has been initialized
405 * (lstart <= xstart < lend) or (xstart < lstart < xend)
408 /* finalize pxd corresponding to current xad */
409 XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);
411 if (++npxd >= maxnpxd)
416 * lxd is fully covered by xad
426 lstart = offsetLXD(lxd);
427 llen = lengthLXD(lxd);
428 lend = lstart + llen;
433 * test for old xad covering new lxd
434 * (old xstart < new lstart)
439 * lxd is partially covered by xad
441 else { /* (xend < lend) */
446 * linear search next xad covering lxd on
447 * the current xad page, and then next xad page search
449 if (index == le16_to_cpu(p->header.nextindex) - 1) {
450 if (p->header.flag & BT_ROOT)
453 if ((bn = le64_to_cpu(p->header.next)) == 0)
458 /* get next sibling page */
459 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
463 index = XTENTRYSTART;
464 xad = &p->xad[index];
471 * test for new xad covering old lxd
472 * (old lstart < new xstart)
478 xadlist->nxad = npxd;
490 * function: search for the xad entry covering specified offset.
494 * xoff - extent offset;
495 * nextp - address of next extent (if any) for search miss
496 * cmpp - comparison result:
497 * btstack - traverse stack;
498 * flag - search process flag (XT_INSERT);
501 * btstack contains (bn, index) of search path traversed to the entry.
502 * *cmpp is set to result of comparison with the entry returned.
503 * the page containing the entry is pinned at exit.
505 static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
506 int *cmpp, struct btstack * btstack, int flag)
508 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
510 int cmp = 1; /* init for empty page */
511 s64 bn; /* block number */
512 struct metapage *mp; /* page buffer */
513 xtpage_t *p; /* page */
515 int base, index, lim, btindex;
516 struct btframe *btsp;
517 int nsplit = 0; /* number of pages to split */
521 INCREMENT(xtStat.search);
528 * search down tree from root:
530 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
531 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
533 * if entry with search key K is not found
534 * internal page search find the entry with largest key Ki
535 * less than K which point to the child page to search;
536 * leaf page search find the entry with smallest key Kj
537 * greater than K so that the returned index is the position of
538 * the entry to be shifted right for insertion of new entry.
539 * for empty tree, search key is greater than any key of the tree.
541 * by convention, root bn = 0.
544 /* get/pin the page to search */
545 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
549 /* try sequential access heuristics with the previous
550 * access entry in target leaf page:
551 * once search narrowed down into the target leaf,
552 * key must either match an entry in the leaf or
553 * key entry does not exist in the tree;
556 if ((jfs_ip->btorder & BT_SEQUENTIAL) &&
557 (p->header.flag & BT_LEAF) &&
558 (index = jfs_ip->btindex) <
559 le16_to_cpu(p->header.nextindex)) {
560 xad = &p->xad[index];
561 t64 = offsetXAD(xad);
562 if (xoff < t64 + lengthXAD(xad)) {
568 /* stop sequential access heuristics */
570 } else { /* (t64 + lengthXAD(xad)) <= xoff */
572 /* try next sequential entry */
575 le16_to_cpu(p->header.nextindex)) {
577 t64 = offsetXAD(xad);
578 if (xoff < t64 + lengthXAD(xad)) {
584 /* miss: key falls between
585 * previous and this entry
592 /* (xoff >= t64 + lengthXAD(xad));
593 * matching entry may be further out:
594 * stop heuristic search
596 /* stop sequential access heuristics */
600 /* (index == p->header.nextindex);
601 * miss: key entry does not exist in
602 * the target leaf/tree
609 * if hit, return index of the entry found, and
610 * if miss, where new entry with search key is
614 /* compute number of pages to split */
615 if (flag & XT_INSERT) {
616 if (p->header.nextindex == /* little-endian */
621 btstack->nsplit = nsplit;
624 /* save search result */
630 /* update sequential access heuristics */
631 jfs_ip->btindex = index;
636 INCREMENT(xtStat.fastSearch);
640 /* well, ... full search now */
642 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
645 * binary search with search key K on the current page
647 for (base = XTENTRYSTART; lim; lim >>= 1) {
648 index = base + (lim >> 1);
650 XT_CMP(cmp, xoff, &p->xad[index], t64);
655 /* search hit - leaf page:
656 * return the entry found
658 if (p->header.flag & BT_LEAF) {
661 /* compute number of pages to split */
662 if (flag & XT_INSERT) {
663 if (p->header.nextindex ==
668 btstack->nsplit = nsplit;
671 /* save search result */
677 /* init sequential access heuristics */
678 btindex = jfs_ip->btindex;
679 if (index == btindex ||
680 index == btindex + 1)
681 jfs_ip->btorder = BT_SEQUENTIAL;
683 jfs_ip->btorder = BT_RANDOM;
684 jfs_ip->btindex = index;
688 /* search hit - internal page:
689 * descend/search its child page
691 if (index < le16_to_cpu(p->header.nextindex)-1)
692 next = offsetXAD(&p->xad[index + 1]);
705 * base is the smallest index with key (Kj) greater than
706 * search key (K) and may be zero or maxentry index.
708 if (base < le16_to_cpu(p->header.nextindex))
709 next = offsetXAD(&p->xad[base]);
711 * search miss - leaf page:
713 * return location of entry (base) where new entry with
714 * search key K is to be inserted.
716 if (p->header.flag & BT_LEAF) {
719 /* compute number of pages to split */
720 if (flag & XT_INSERT) {
721 if (p->header.nextindex ==
726 btstack->nsplit = nsplit;
729 /* save search result */
735 /* init sequential access heuristics */
736 btindex = jfs_ip->btindex;
737 if (base == btindex || base == btindex + 1)
738 jfs_ip->btorder = BT_SEQUENTIAL;
740 jfs_ip->btorder = BT_RANDOM;
741 jfs_ip->btindex = base;
750 * search miss - non-leaf page:
752 * if base is non-zero, decrement base by one to get the parent
753 * entry of the child page to search.
755 index = base ? base - 1 : base;
758 * go down to child page
761 /* update number of pages to split */
762 if (p->header.nextindex == p->header.maxentry)
767 /* push (bn, index) of the parent page/entry */
768 BT_PUSH(btstack, bn, index);
770 /* get the child page block number */
771 bn = addressXAD(&p->xad[index]);
773 /* unpin the parent page */
784 * tid - transaction id;
786 * xflag - extent flag (XAD_NOTRECORDED):
787 * xoff - extent offset;
788 * xlen - extent length;
789 * xaddrp - extent address pointer (in/out):
791 * caller allocated data extent at *xaddrp;
793 * allocate data extent and return its xaddr;
798 int xtInsert(tid_t tid, /* transaction id */
799 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
804 struct metapage *mp; /* meta-page buffer */
805 xtpage_t *p; /* base B+-tree index page */
807 int index, nextindex;
808 struct btstack btstack; /* traverse stack */
809 struct xtsplit split; /* split information */
814 struct xtlock *xtlck;
816 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
819 * search for the entry location at which to insert:
821 * xtFastSearch() and xtSearch() both returns (leaf page
822 * pinned, index at which to insert).
823 * n.b. xtSearch() may return index of maxentry of
826 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
829 /* retrieve search result */
830 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
832 /* This test must follow XT_GETSEARCH since mp must be valid if
833 * we branch to out: */
834 if ((cmp == 0) || (next && (xlen > next - xoff))) {
840 * allocate data extent requested
842 * allocation hint: last xad
844 if ((xaddr = *xaddrp) == 0) {
845 if (index > XTENTRYSTART) {
846 xad = &p->xad[index - 1];
847 hint = addressXAD(xad) + lengthXAD(xad) - 1;
850 if ((rc = DQUOT_ALLOC_BLOCK(ip, xlen)))
852 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
853 DQUOT_FREE_BLOCK(ip, xlen);
859 * insert entry for new extent
864 * if the leaf page is full, split the page and
865 * propagate up the router entry for the new page from split
867 * The xtSplitUp() will insert the entry and unpin the leaf page.
869 nextindex = le16_to_cpu(p->header.nextindex);
870 if (nextindex == le16_to_cpu(p->header.maxentry)) {
877 split.pxdlist = NULL;
878 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
879 /* undo data extent allocation */
881 dbFree(ip, xaddr, (s64) xlen);
882 DQUOT_FREE_BLOCK(ip, xlen);
892 * insert the new entry into the leaf page
895 * acquire a transaction lock on the leaf page;
897 * action: xad insertion/extension;
899 BT_MARK_DIRTY(mp, ip);
901 /* if insert into middle, shift right remaining entries. */
902 if (index < nextindex)
903 memmove(&p->xad[index + 1], &p->xad[index],
904 (nextindex - index) * sizeof(xad_t));
906 /* insert the new entry: mark the entry NEW */
907 xad = &p->xad[index];
908 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
910 /* advance next available entry index */
911 p->header.nextindex =
912 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
914 /* Don't log it if there are no links to the file */
915 if (!test_cflag(COMMIT_Nolink, ip)) {
916 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
917 xtlck = (struct xtlock *) & tlck->lock;
919 (xtlck->lwm.offset) ? min(index,
920 (int)xtlck->lwm.offset) : index;
922 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
928 /* unpin the leaf page */
939 * split full pages as propagating insertion up the tree
942 * tid - transaction id;
944 * split - entry parameter descriptor;
945 * btstack - traverse stack from xtSearch()
951 struct inode *ip, struct xtsplit * split, struct btstack * btstack)
954 struct metapage *smp;
955 xtpage_t *sp; /* split page */
956 struct metapage *rmp;
957 s64 rbn; /* new right page block number */
958 struct metapage *rcmp;
959 xtpage_t *rcp; /* right child page */
960 s64 rcbn; /* right child page block number */
961 int skip; /* index of entry of insertion */
962 int nextindex; /* next available entry index of p */
963 struct btframe *parent; /* parent page entry on traverse stack */
967 int nsplit; /* number of pages split */
968 struct pxdlist pxdlist;
971 struct xtlock *xtlck;
974 sp = XT_PAGE(ip, smp);
976 /* is inode xtree root extension/inline EA area free ? */
977 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
978 (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
979 (JFS_IP(ip)->mode2 & INLINEEA)) {
980 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
981 JFS_IP(ip)->mode2 &= ~INLINEEA;
983 BT_MARK_DIRTY(smp, ip);
985 * acquire a transaction lock on the leaf page;
987 * action: xad insertion/extension;
990 /* if insert into middle, shift right remaining entries. */
992 nextindex = le16_to_cpu(sp->header.nextindex);
993 if (skip < nextindex)
994 memmove(&sp->xad[skip + 1], &sp->xad[skip],
995 (nextindex - skip) * sizeof(xad_t));
997 /* insert the new entry: mark the entry NEW */
998 xad = &sp->xad[skip];
999 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1002 /* advance next available entry index */
1003 sp->header.nextindex =
1004 cpu_to_le16(le16_to_cpu(sp->header.nextindex) + 1);
1006 /* Don't log it if there are no links to the file */
1007 if (!test_cflag(COMMIT_Nolink, ip)) {
1008 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1009 xtlck = (struct xtlock *) & tlck->lock;
1010 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1011 min(skip, (int)xtlck->lwm.offset) : skip;
1013 le16_to_cpu(sp->header.nextindex) -
1021 * allocate new index blocks to cover index page split(s)
1023 * allocation hint: ?
1025 if (split->pxdlist == NULL) {
1026 nsplit = btstack->nsplit;
1027 split->pxdlist = &pxdlist;
1028 pxdlist.maxnpxd = pxdlist.npxd = 0;
1029 pxd = &pxdlist.pxd[0];
1030 xlen = JFS_SBI(ip->i_sb)->nbperpage;
1031 for (; nsplit > 0; nsplit--, pxd++) {
1032 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
1034 PXDaddress(pxd, xaddr);
1035 PXDlength(pxd, xlen);
1042 /* undo allocation */
1050 * Split leaf page <sp> into <sp> and a new right page <rp>.
1052 * The split routines insert the new entry into the leaf page,
1053 * and acquire txLock as appropriate.
1054 * return <rp> pinned and its block number <rpbn>.
1056 rc = (sp->header.flag & BT_ROOT) ?
1057 xtSplitRoot(tid, ip, split, &rmp) :
1058 xtSplitPage(tid, ip, split, &rmp, &rbn);
1065 * propagate up the router entry for the leaf page just split
1067 * insert a router entry for the new page into the parent page,
1068 * propagate the insert/split up the tree by walking back the stack
1069 * of (bn of parent page, index of child page entry in parent page)
1070 * that were traversed during the search for the page that split.
1072 * the propagation of insert/split up the tree stops if the root
1073 * splits or the page inserted into doesn't have to split to hold
1076 * the parent entry for the split page remains the same, and
1077 * a new entry is inserted at its right with the first key and
1078 * block number of the new right page.
1080 * There are a maximum of 3 pages pinned at any time:
1081 * right child, left parent and right parent (when the parent splits)
1082 * to keep the child page pinned while working on the parent.
1083 * make sure that all pins are released at exit.
1085 while ((parent = BT_POP(btstack)) != NULL) {
1086 /* parent page specified by stack frame <parent> */
1088 /* keep current child pages <rcp> pinned */
1091 rcp = XT_PAGE(ip, rcmp);
1094 * insert router entry in parent for new right child page <rp>
1096 /* get/pin the parent page <sp> */
1097 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
1104 * The new key entry goes ONE AFTER the index of parent entry,
1105 * because the split was to the right.
1107 skip = parent->index + 1;
1110 * split or shift right remaining entries of the parent page
1112 nextindex = le16_to_cpu(sp->header.nextindex);
1114 * parent page is full - split the parent page
1116 if (nextindex == le16_to_cpu(sp->header.maxentry)) {
1117 /* init for parent page split */
1119 split->index = skip; /* index at insert */
1120 split->flag = XAD_NEW;
1121 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
1122 split->len = JFS_SBI(ip->i_sb)->nbperpage;
1125 /* unpin previous right child page */
1128 /* The split routines insert the new entry,
1129 * and acquire txLock as appropriate.
1130 * return <rp> pinned and its block number <rpbn>.
1132 rc = (sp->header.flag & BT_ROOT) ?
1133 xtSplitRoot(tid, ip, split, &rmp) :
1134 xtSplitPage(tid, ip, split, &rmp, &rbn);
1141 /* keep new child page <rp> pinned */
1144 * parent page is not full - insert in parent page
1148 * insert router entry in parent for the right child
1149 * page from the first entry of the right child page:
1152 * acquire a transaction lock on the parent page;
1154 * action: router xad insertion;
1156 BT_MARK_DIRTY(smp, ip);
1159 * if insert into middle, shift right remaining entries
1161 if (skip < nextindex)
1162 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1164 skip) << L2XTSLOTSIZE);
1166 /* insert the router entry */
1167 xad = &sp->xad[skip];
1168 XT_PUTENTRY(xad, XAD_NEW,
1169 offsetXAD(&rcp->xad[XTENTRYSTART]),
1170 JFS_SBI(ip->i_sb)->nbperpage, rcbn);
1172 /* advance next available entry index. */
1173 sp->header.nextindex =
1174 cpu_to_le16(le16_to_cpu(sp->header.nextindex) +
1177 /* Don't log it if there are no links to the file */
1178 if (!test_cflag(COMMIT_Nolink, ip)) {
1179 tlck = txLock(tid, ip, smp,
1180 tlckXTREE | tlckGROW);
1181 xtlck = (struct xtlock *) & tlck->lock;
1182 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1183 min(skip, (int)xtlck->lwm.offset) : skip;
1185 le16_to_cpu(sp->header.nextindex) -
1189 /* unpin parent page */
1192 /* exit propagate up */
1197 /* unpin current right page */
1208 * split a full non-root page into
1209 * original/split/left page and new right page
1210 * i.e., the original/split page remains as left page.
1215 * struct xtsplit *split,
1216 * struct metapage **rmpp,
1220 * Pointer to page in which to insert or NULL on error.
1223 xtSplitPage(tid_t tid, struct inode *ip,
1224 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
1227 struct metapage *smp;
1229 struct metapage *rmp;
1230 xtpage_t *rp; /* new right page allocated */
1231 s64 rbn; /* new right page block number */
1232 struct metapage *mp;
1235 int skip, maxentry, middle, righthalf, n;
1237 struct pxdlist *pxdlist;
1240 struct xtlock *sxtlck = NULL, *rxtlck = NULL;
1241 int quota_allocation = 0;
1244 sp = XT_PAGE(ip, smp);
1246 INCREMENT(xtStat.split);
1248 pxdlist = split->pxdlist;
1249 pxd = &pxdlist->pxd[pxdlist->npxd];
1251 rbn = addressPXD(pxd);
1253 /* Allocate blocks to quota. */
1254 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
1259 quota_allocation += lengthPXD(pxd);
1262 * allocate the new right page for the split
1264 rmp = get_metapage(ip, rbn, PSIZE, 1);
1270 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1272 BT_MARK_DIRTY(rmp, ip);
1277 rp = (xtpage_t *) rmp->data;
1278 rp->header.self = *pxd;
1279 rp->header.flag = sp->header.flag & BT_TYPE;
1280 rp->header.maxentry = sp->header.maxentry; /* little-endian */
1281 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1283 BT_MARK_DIRTY(smp, ip);
1284 /* Don't log it if there are no links to the file */
1285 if (!test_cflag(COMMIT_Nolink, ip)) {
1287 * acquire a transaction lock on the new right page;
1289 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1290 rxtlck = (struct xtlock *) & tlck->lock;
1291 rxtlck->lwm.offset = XTENTRYSTART;
1293 * acquire a transaction lock on the split page
1295 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1296 sxtlck = (struct xtlock *) & tlck->lock;
1300 * initialize/update sibling pointers of <sp> and <rp>
1302 nextbn = le64_to_cpu(sp->header.next);
1303 rp->header.next = cpu_to_le64(nextbn);
1304 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1305 sp->header.next = cpu_to_le64(rbn);
1307 skip = split->index;
1310 * sequential append at tail (after last entry of last page)
1312 * if splitting the last page on a level because of appending
1313 * a entry to it (skip is maxentry), it's likely that the access is
1314 * sequential. adding an empty page on the side of the level is less
1315 * work and can push the fill factor much higher than normal.
1316 * if we're wrong it's no big deal - we will do the split the right
1318 * (it may look like it's equally easy to do a similar hack for
1319 * reverse sorted data, that is, split the tree left, but it's not.
1322 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1324 * acquire a transaction lock on the new/right page;
1326 * action: xad insertion;
1328 /* insert entry at the first entry of the new right page */
1329 xad = &rp->xad[XTENTRYSTART];
1330 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1333 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1335 if (!test_cflag(COMMIT_Nolink, ip)) {
1336 /* rxtlck->lwm.offset = XTENTRYSTART; */
1337 rxtlck->lwm.length = 1;
1343 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1348 * non-sequential insert (at possibly middle page)
1352 * update previous pointer of old next/right page of <sp>
1355 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1361 BT_MARK_DIRTY(mp, ip);
1363 * acquire a transaction lock on the next page;
1365 * action:sibling pointer update;
1367 if (!test_cflag(COMMIT_Nolink, ip))
1368 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1370 p->header.prev = cpu_to_le64(rbn);
1372 /* sibling page may have been updated previously, or
1373 * it may be updated later;
1380 * split the data between the split and new/right pages
1382 maxentry = le16_to_cpu(sp->header.maxentry);
1383 middle = maxentry >> 1;
1384 righthalf = maxentry - middle;
1387 * skip index in old split/left page - insert into left page:
1389 if (skip <= middle) {
1390 /* move right half of split page to the new right page */
1391 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1392 righthalf << L2XTSLOTSIZE);
1394 /* shift right tail of left half to make room for new entry */
1396 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1397 (middle - skip) << L2XTSLOTSIZE);
1399 /* insert new entry */
1400 xad = &sp->xad[skip];
1401 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1404 /* update page header */
1405 sp->header.nextindex = cpu_to_le16(middle + 1);
1406 if (!test_cflag(COMMIT_Nolink, ip)) {
1407 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1408 min(skip, (int)sxtlck->lwm.offset) : skip;
1411 rp->header.nextindex =
1412 cpu_to_le16(XTENTRYSTART + righthalf);
1415 * skip index in new right page - insert into right page:
1418 /* move left head of right half to right page */
1420 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1423 /* insert new entry */
1426 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1429 /* move right tail of right half to right page */
1430 if (skip < maxentry)
1431 memmove(&rp->xad[n + 1], &sp->xad[skip],
1432 (maxentry - skip) << L2XTSLOTSIZE);
1434 /* update page header */
1435 sp->header.nextindex = cpu_to_le16(middle);
1436 if (!test_cflag(COMMIT_Nolink, ip)) {
1437 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1438 min(middle, (int)sxtlck->lwm.offset) : middle;
1441 rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1445 if (!test_cflag(COMMIT_Nolink, ip)) {
1446 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1449 /* rxtlck->lwm.offset = XTENTRYSTART; */
1450 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1457 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1462 /* Rollback quota allocation. */
1463 if (quota_allocation)
1464 DQUOT_FREE_BLOCK(ip, quota_allocation);
1474 * split the full root page into
1475 * original/root/split page and new right page
1476 * i.e., root remains fixed in tree anchor (inode) and
1477 * the root is copied to a single new right child page
1478 * since root page << non-root page, and
1479 * the split root page contains a single entry for the
1480 * new right child page.
1485 * struct xtsplit *split,
1486 * struct metapage **rmpp)
1489 * Pointer to page in which to insert or NULL on error.
1492 xtSplitRoot(tid_t tid,
1493 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1496 struct metapage *rmp;
1499 int skip, nextindex;
1502 struct pxdlist *pxdlist;
1504 struct xtlock *xtlck;
1506 sp = &JFS_IP(ip)->i_xtroot;
1508 INCREMENT(xtStat.split);
1511 * allocate a single (right) child page
1513 pxdlist = split->pxdlist;
1514 pxd = &pxdlist->pxd[pxdlist->npxd];
1516 rbn = addressPXD(pxd);
1517 rmp = get_metapage(ip, rbn, PSIZE, 1);
1521 /* Allocate blocks to quota. */
1522 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
1523 release_metapage(rmp);
1527 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1530 * acquire a transaction lock on the new right page;
1534 BT_MARK_DIRTY(rmp, ip);
1536 rp = (xtpage_t *) rmp->data;
1538 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1539 rp->header.self = *pxd;
1540 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1541 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1543 /* initialize sibling pointers */
1544 rp->header.next = 0;
1545 rp->header.prev = 0;
1548 * copy the in-line root page into new right page extent
1550 nextindex = le16_to_cpu(sp->header.maxentry);
1551 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1552 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1555 * insert the new entry into the new right/child page
1556 * (skip index in the new right page will not change)
1558 skip = split->index;
1559 /* if insert into middle, shift right remaining entries */
1560 if (skip != nextindex)
1561 memmove(&rp->xad[skip + 1], &rp->xad[skip],
1562 (nextindex - skip) * sizeof(xad_t));
1564 xad = &rp->xad[skip];
1565 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1567 /* update page header */
1568 rp->header.nextindex = cpu_to_le16(nextindex + 1);
1570 if (!test_cflag(COMMIT_Nolink, ip)) {
1571 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1572 xtlck = (struct xtlock *) & tlck->lock;
1573 xtlck->lwm.offset = XTENTRYSTART;
1574 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1581 * init root with the single entry for the new right page
1582 * set the 1st entry offset to 0, which force the left-most key
1583 * at any level of the tree to be less than any search key.
1586 * acquire a transaction lock on the root page (in-memory inode);
1588 * action: root split;
1590 BT_MARK_DIRTY(split->mp, ip);
1592 xad = &sp->xad[XTENTRYSTART];
1593 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1595 /* update page header of root */
1596 sp->header.flag &= ~BT_LEAF;
1597 sp->header.flag |= BT_INTERNAL;
1599 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1601 if (!test_cflag(COMMIT_Nolink, ip)) {
1602 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1603 xtlck = (struct xtlock *) & tlck->lock;
1604 xtlck->lwm.offset = XTENTRYSTART;
1605 xtlck->lwm.length = 1;
1610 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1618 * function: extend in-place;
1620 * note: existing extent may or may not have been committed.
1621 * caller is responsible for pager buffer cache update, and
1622 * working block allocation map update;
1623 * update pmap: alloc whole extended extent;
1625 int xtExtend(tid_t tid, /* transaction id */
1626 struct inode *ip, s64 xoff, /* delta extent offset */
1627 s32 xlen, /* delta extent length */
1632 struct metapage *mp; /* meta-page buffer */
1633 xtpage_t *p; /* base B+-tree index page */
1635 int index, nextindex, len;
1636 struct btstack btstack; /* traverse stack */
1637 struct xtsplit split; /* split information */
1641 struct xtlock *xtlck = NULL;
1643 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1645 /* there must exist extent to be extended */
1646 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1649 /* retrieve search result */
1650 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1654 jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
1658 /* extension must be contiguous */
1659 xad = &p->xad[index];
1660 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1662 jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
1667 * acquire a transaction lock on the leaf page;
1669 * action: xad insertion/extension;
1671 BT_MARK_DIRTY(mp, ip);
1672 if (!test_cflag(COMMIT_Nolink, ip)) {
1673 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1674 xtlck = (struct xtlock *) & tlck->lock;
1677 /* extend will overflow extent ? */
1678 xlen = lengthXAD(xad) + xlen;
1679 if ((len = xlen - MAXXLEN) <= 0)
1683 * extent overflow: insert entry for new extent
1686 xoff = offsetXAD(xad) + MAXXLEN;
1687 xaddr = addressXAD(xad) + MAXXLEN;
1688 nextindex = le16_to_cpu(p->header.nextindex);
1691 * if the leaf page is full, insert the new entry and
1692 * propagate up the router entry for the new page from split
1694 * The xtSplitUp() will insert the entry and unpin the leaf page.
1696 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1697 /* xtSpliUp() unpins leaf pages */
1699 split.index = index + 1;
1700 split.flag = XAD_NEW;
1701 split.off = xoff; /* split offset */
1704 split.pxdlist = NULL;
1705 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1708 /* get back old page */
1709 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1713 * if leaf root has been split, original root has been
1714 * copied to new child page, i.e., original entry now
1715 * resides on the new child page;
1717 if (p->header.flag & BT_INTERNAL) {
1718 ASSERT(p->header.nextindex ==
1719 cpu_to_le16(XTENTRYSTART + 1));
1720 xad = &p->xad[XTENTRYSTART];
1721 bn = addressXAD(xad);
1724 /* get new child page */
1725 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1729 BT_MARK_DIRTY(mp, ip);
1730 if (!test_cflag(COMMIT_Nolink, ip)) {
1731 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1732 xtlck = (struct xtlock *) & tlck->lock;
1737 * insert the new entry into the leaf page
1740 /* insert the new entry: mark the entry NEW */
1741 xad = &p->xad[index + 1];
1742 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1744 /* advance next available entry index */
1745 p->header.nextindex =
1746 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1749 /* get back old entry */
1750 xad = &p->xad[index];
1757 XADlength(xad, xlen);
1758 if (!(xad->flag & XAD_NEW))
1759 xad->flag |= XAD_EXTENDED;
1761 if (!test_cflag(COMMIT_Nolink, ip)) {
1763 (xtlck->lwm.offset) ? min(index,
1764 (int)xtlck->lwm.offset) : index;
1766 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1769 /* unpin the leaf page */
1779 * function: split existing 'tail' extent
1780 * (split offset >= start offset of tail extent), and
1781 * relocate and extend the split tail half;
1783 * note: existing extent may or may not have been committed.
1784 * caller is responsible for pager buffer cache update, and
1785 * working block allocation map update;
1786 * update pmap: free old split tail extent, alloc new extent;
1788 int xtTailgate(tid_t tid, /* transaction id */
1789 struct inode *ip, s64 xoff, /* split/new extent offset */
1790 s32 xlen, /* new extent length */
1791 s64 xaddr, /* new extent address */
1796 struct metapage *mp; /* meta-page buffer */
1797 xtpage_t *p; /* base B+-tree index page */
1799 int index, nextindex, llen, rlen;
1800 struct btstack btstack; /* traverse stack */
1801 struct xtsplit split; /* split information */
1804 struct xtlock *xtlck = 0;
1805 struct tlock *mtlck;
1806 struct maplock *pxdlock;
1809 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1810 (ulong)xoff, xlen, (ulong)xaddr);
1813 /* there must exist extent to be tailgated */
1814 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
1817 /* retrieve search result */
1818 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1822 jfs_error(ip->i_sb, "xtTailgate: couldn't find extent");
1826 /* entry found must be last entry */
1827 nextindex = le16_to_cpu(p->header.nextindex);
1828 if (index != nextindex - 1) {
1831 "xtTailgate: the entry found is not the last entry");
1835 BT_MARK_DIRTY(mp, ip);
1837 * acquire tlock of the leaf page containing original entry
1839 if (!test_cflag(COMMIT_Nolink, ip)) {
1840 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1841 xtlck = (struct xtlock *) & tlck->lock;
1844 /* completely replace extent ? */
1845 xad = &p->xad[index];
1847 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1848 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1850 if ((llen = xoff - offsetXAD(xad)) == 0)
1854 * partially replace extent: insert entry for new extent
1858 * if the leaf page is full, insert the new entry and
1859 * propagate up the router entry for the new page from split
1861 * The xtSplitUp() will insert the entry and unpin the leaf page.
1863 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1864 /* xtSpliUp() unpins leaf pages */
1866 split.index = index + 1;
1867 split.flag = XAD_NEW;
1868 split.off = xoff; /* split offset */
1871 split.pxdlist = NULL;
1872 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1875 /* get back old page */
1876 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1880 * if leaf root has been split, original root has been
1881 * copied to new child page, i.e., original entry now
1882 * resides on the new child page;
1884 if (p->header.flag & BT_INTERNAL) {
1885 ASSERT(p->header.nextindex ==
1886 cpu_to_le16(XTENTRYSTART + 1));
1887 xad = &p->xad[XTENTRYSTART];
1888 bn = addressXAD(xad);
1891 /* get new child page */
1892 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1896 BT_MARK_DIRTY(mp, ip);
1897 if (!test_cflag(COMMIT_Nolink, ip)) {
1898 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1899 xtlck = (struct xtlock *) & tlck->lock;
1904 * insert the new entry into the leaf page
1907 /* insert the new entry: mark the entry NEW */
1908 xad = &p->xad[index + 1];
1909 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1911 /* advance next available entry index */
1912 p->header.nextindex =
1913 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1916 /* get back old XAD */
1917 xad = &p->xad[index];
1920 * truncate/relocate old extent at split offset
1923 /* update dmap for old/committed/truncated extent */
1924 rlen = lengthXAD(xad) - llen;
1925 if (!(xad->flag & XAD_NEW)) {
1926 /* free from PWMAP at commit */
1927 if (!test_cflag(COMMIT_Nolink, ip)) {
1928 mtlck = txMaplock(tid, ip, tlckMAP);
1929 pxdlock = (struct maplock *) & mtlck->lock;
1930 pxdlock->flag = mlckFREEPXD;
1931 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1932 PXDlength(&pxdlock->pxd, rlen);
1936 /* free from WMAP */
1937 dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1941 XADlength(xad, llen);
1944 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1946 if (!test_cflag(COMMIT_Nolink, ip)) {
1947 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1948 min(index, (int)xtlck->lwm.offset) : index;
1949 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1953 /* unpin the leaf page */
1958 #endif /* _NOTYET */
1963 * function: update XAD;
1965 * update extent for allocated_but_not_recorded or
1966 * compressed extent;
1970 * logical extent of the specified XAD must be completely
1971 * contained by an existing XAD;
1973 int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1977 struct metapage *mp; /* meta-page buffer */
1978 xtpage_t *p; /* base B+-tree index page */
1980 int index0, index, newindex, nextindex;
1981 struct btstack btstack; /* traverse stack */
1982 struct xtsplit split; /* split information */
1983 xad_t *xad, *lxad, *rxad;
1986 int nxlen, xlen, lxlen, rxlen;
1989 struct xtlock *xtlck = NULL;
1992 /* there must exist extent to be tailgated */
1993 nxoff = offsetXAD(nxad);
1994 nxlen = lengthXAD(nxad);
1995 nxaddr = addressXAD(nxad);
1997 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2000 /* retrieve search result */
2001 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2005 jfs_error(ip->i_sb, "xtUpdate: Could not find extent");
2009 BT_MARK_DIRTY(mp, ip);
2011 * acquire tlock of the leaf page containing original entry
2013 if (!test_cflag(COMMIT_Nolink, ip)) {
2014 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2015 xtlck = (struct xtlock *) & tlck->lock;
2018 xad = &p->xad[index0];
2020 xoff = offsetXAD(xad);
2021 xlen = lengthXAD(xad);
2022 xaddr = addressXAD(xad);
2024 /* nXAD must be completely contained within XAD */
2025 if ((xoff > nxoff) ||
2026 (nxoff + nxlen > xoff + xlen)) {
2029 "xtUpdate: nXAD in not completely contained within XAD");
2034 newindex = index + 1;
2035 nextindex = le16_to_cpu(p->header.nextindex);
2037 #ifdef _JFS_WIP_NOCOALESCE
2042 * replace XAD with nXAD
2044 replace: /* (nxoff == xoff) */
2045 if (nxlen == xlen) {
2046 /* replace XAD with nXAD:recorded */
2048 xad->flag = xflag & ~XAD_NOTRECORDED;
2051 } else /* (nxlen < xlen) */
2053 #endif /* _JFS_WIP_NOCOALESCE */
2055 /* #ifdef _JFS_WIP_COALESCE */
2060 * coalesce with left XAD
2062 //coalesceLeft: /* (xoff == nxoff) */
2063 /* is XAD first entry of page ? */
2064 if (index == XTENTRYSTART)
2067 /* is nXAD logically and physically contiguous with lXAD ? */
2068 lxad = &p->xad[index - 1];
2069 lxlen = lengthXAD(lxad);
2070 if (!(lxad->flag & XAD_NOTRECORDED) &&
2071 (nxoff == offsetXAD(lxad) + lxlen) &&
2072 (nxaddr == addressXAD(lxad) + lxlen) &&
2073 (lxlen + nxlen < MAXXLEN)) {
2074 /* extend right lXAD */
2076 XADlength(lxad, lxlen + nxlen);
2078 /* If we just merged two extents together, need to make sure the
2079 * right extent gets logged. If the left one is marked XAD_NEW,
2080 * then we know it will be logged. Otherwise, mark as
2083 if (!(lxad->flag & XAD_NEW))
2084 lxad->flag |= XAD_EXTENDED;
2088 XADoffset(xad, xoff + nxlen);
2089 XADlength(xad, xlen - nxlen);
2090 XADaddress(xad, xaddr + nxlen);
2092 } else { /* (xlen == nxlen) */
2095 if (index < nextindex - 1)
2096 memmove(&p->xad[index], &p->xad[index + 1],
2097 (nextindex - index -
2098 1) << L2XTSLOTSIZE);
2100 p->header.nextindex =
2101 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2105 newindex = index + 1;
2106 nextindex = le16_to_cpu(p->header.nextindex);
2107 xoff = nxoff = offsetXAD(lxad);
2108 xlen = nxlen = lxlen + nxlen;
2109 xaddr = nxaddr = addressXAD(lxad);
2115 * replace XAD with nXAD
2117 replace: /* (nxoff == xoff) */
2118 if (nxlen == xlen) {
2119 /* replace XAD with nXAD:recorded */
2121 xad->flag = xflag & ~XAD_NOTRECORDED;
2124 } else /* (nxlen < xlen) */
2128 * coalesce with right XAD
2130 coalesceRight: /* (xoff <= nxoff) */
2131 /* is XAD last entry of page ? */
2132 if (newindex == nextindex) {
2138 /* is nXAD logically and physically contiguous with rXAD ? */
2139 rxad = &p->xad[index + 1];
2140 rxlen = lengthXAD(rxad);
2141 if (!(rxad->flag & XAD_NOTRECORDED) &&
2142 (nxoff + nxlen == offsetXAD(rxad)) &&
2143 (nxaddr + nxlen == addressXAD(rxad)) &&
2144 (rxlen + nxlen < MAXXLEN)) {
2145 /* extend left rXAD */
2146 XADoffset(rxad, nxoff);
2147 XADlength(rxad, rxlen + nxlen);
2148 XADaddress(rxad, nxaddr);
2150 /* If we just merged two extents together, need to make sure
2151 * the left extent gets logged. If the right one is marked
2152 * XAD_NEW, then we know it will be logged. Otherwise, mark as
2155 if (!(rxad->flag & XAD_NEW))
2156 rxad->flag |= XAD_EXTENDED;
2160 XADlength(xad, xlen - nxlen);
2161 else { /* (xlen == nxlen) */
2164 memmove(&p->xad[index], &p->xad[index + 1],
2165 (nextindex - index - 1) << L2XTSLOTSIZE);
2167 p->header.nextindex =
2168 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2173 } else if (xoff == nxoff)
2176 if (xoff >= nxoff) {
2178 jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff");
2181 /* #endif _JFS_WIP_COALESCE */
2184 * split XAD into (lXAD, nXAD):
2187 * --|----------XAD----------|--
2190 updateRight: /* (xoff < nxoff) */
2191 /* truncate old XAD as lXAD:not_recorded */
2192 xad = &p->xad[index];
2193 XADlength(xad, nxoff - xoff);
2195 /* insert nXAD:recorded */
2196 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2198 /* xtSpliUp() unpins leaf pages */
2200 split.index = newindex;
2201 split.flag = xflag & ~XAD_NOTRECORDED;
2204 split.addr = nxaddr;
2205 split.pxdlist = NULL;
2206 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2209 /* get back old page */
2210 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2214 * if leaf root has been split, original root has been
2215 * copied to new child page, i.e., original entry now
2216 * resides on the new child page;
2218 if (p->header.flag & BT_INTERNAL) {
2219 ASSERT(p->header.nextindex ==
2220 cpu_to_le16(XTENTRYSTART + 1));
2221 xad = &p->xad[XTENTRYSTART];
2222 bn = addressXAD(xad);
2225 /* get new child page */
2226 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2230 BT_MARK_DIRTY(mp, ip);
2231 if (!test_cflag(COMMIT_Nolink, ip)) {
2232 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2233 xtlck = (struct xtlock *) & tlck->lock;
2236 /* is nXAD on new page ? */
2238 (le16_to_cpu(p->header.maxentry) >> 1)) {
2241 le16_to_cpu(p->header.nextindex) +
2247 /* if insert into middle, shift right remaining entries */
2248 if (newindex < nextindex)
2249 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2250 (nextindex - newindex) << L2XTSLOTSIZE);
2252 /* insert the entry */
2253 xad = &p->xad[newindex];
2255 xad->flag = xflag & ~XAD_NOTRECORDED;
2257 /* advance next available entry index. */
2258 p->header.nextindex =
2259 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2263 * does nXAD force 3-way split ?
2266 * --|----------XAD-------------|--
2267 * |-lXAD-| |-rXAD -|
2269 if (nxoff + nxlen == xoff + xlen)
2272 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2274 /* close out old page */
2275 if (!test_cflag(COMMIT_Nolink, ip)) {
2276 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2277 min(index0, (int)xtlck->lwm.offset) : index0;
2279 le16_to_cpu(p->header.nextindex) -
2283 bn = le64_to_cpu(p->header.next);
2286 /* get new right page */
2287 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2291 BT_MARK_DIRTY(mp, ip);
2292 if (!test_cflag(COMMIT_Nolink, ip)) {
2293 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2294 xtlck = (struct xtlock *) & tlck->lock;
2297 index0 = index = newindex;
2301 newindex = index + 1;
2302 nextindex = le16_to_cpu(p->header.nextindex);
2303 xlen = xlen - (nxoff - xoff);
2307 /* recompute split pages */
2308 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2311 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2314 /* retrieve search result */
2315 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2319 jfs_error(ip->i_sb, "xtUpdate: xtSearch failed");
2323 if (index0 != index) {
2326 "xtUpdate: unexpected value of index");
2332 * split XAD into (nXAD, rXAD)
2335 * --|----------XAD----------|--
2338 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
2339 /* update old XAD with nXAD:recorded */
2340 xad = &p->xad[index];
2342 xad->flag = xflag & ~XAD_NOTRECORDED;
2344 /* insert rXAD:not_recorded */
2345 xoff = xoff + nxlen;
2346 xlen = xlen - nxlen;
2347 xaddr = xaddr + nxlen;
2348 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2350 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2352 /* xtSpliUp() unpins leaf pages */
2354 split.index = newindex;
2359 split.pxdlist = NULL;
2360 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2363 /* get back old page */
2364 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2369 * if leaf root has been split, original root has been
2370 * copied to new child page, i.e., original entry now
2371 * resides on the new child page;
2373 if (p->header.flag & BT_INTERNAL) {
2374 ASSERT(p->header.nextindex ==
2375 cpu_to_le16(XTENTRYSTART + 1));
2376 xad = &p->xad[XTENTRYSTART];
2377 bn = addressXAD(xad);
2380 /* get new child page */
2381 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2385 BT_MARK_DIRTY(mp, ip);
2386 if (!test_cflag(COMMIT_Nolink, ip)) {
2387 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2388 xtlck = (struct xtlock *) & tlck->lock;
2392 /* if insert into middle, shift right remaining entries */
2393 if (newindex < nextindex)
2394 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2395 (nextindex - newindex) << L2XTSLOTSIZE);
2397 /* insert the entry */
2398 xad = &p->xad[newindex];
2399 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2401 /* advance next available entry index. */
2402 p->header.nextindex =
2403 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2407 if (!test_cflag(COMMIT_Nolink, ip)) {
2408 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2409 min(index0, (int)xtlck->lwm.offset) : index0;
2410 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2414 /* unpin the leaf page */
2424 * function: grow in append mode from contiguous region specified ;
2427 * tid - transaction id;
2429 * xflag - extent flag:
2430 * xoff - extent offset;
2431 * maxblocks - max extent length;
2432 * xlen - extent length (in/out);
2433 * xaddrp - extent address pointer (in/out):
2438 int xtAppend(tid_t tid, /* transaction id */
2439 struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2440 s32 * xlenp, /* (in/out) */
2441 s64 * xaddrp, /* (in/out) */
2445 struct metapage *mp; /* meta-page buffer */
2446 xtpage_t *p; /* base B+-tree index page */
2448 int index, nextindex;
2449 struct btstack btstack; /* traverse stack */
2450 struct xtsplit split; /* split information */
2454 struct xtlock *xtlck;
2455 int nsplit, nblocks, xlen;
2456 struct pxdlist pxdlist;
2462 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2463 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2466 * search for the entry location at which to insert:
2468 * xtFastSearch() and xtSearch() both returns (leaf page
2469 * pinned, index at which to insert).
2470 * n.b. xtSearch() may return index of maxentry of
2473 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
2476 /* retrieve search result */
2477 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2485 xlen = min(xlen, (int)(next - xoff));
2488 * insert entry for new extent
2493 * if the leaf page is full, split the page and
2494 * propagate up the router entry for the new page from split
2496 * The xtSplitUp() will insert the entry and unpin the leaf page.
2498 nextindex = le16_to_cpu(p->header.nextindex);
2499 if (nextindex < le16_to_cpu(p->header.maxentry))
2503 * allocate new index blocks to cover index page split(s)
2505 nsplit = btstack.nsplit;
2506 split.pxdlist = &pxdlist;
2507 pxdlist.maxnpxd = pxdlist.npxd = 0;
2508 pxd = &pxdlist.pxd[0];
2509 nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2510 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2511 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2512 PXDaddress(pxd, xaddr);
2513 PXDlength(pxd, nblocks);
2520 /* undo allocation */
2525 xlen = min(xlen, maxblocks);
2528 * allocate data extent requested
2530 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2534 split.index = index;
2539 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2540 /* undo data extent allocation */
2541 dbFree(ip, *xaddrp, (s64) * xlenp);
2551 * insert the new entry into the leaf page
2555 * allocate data extent requested
2557 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2560 BT_MARK_DIRTY(mp, ip);
2562 * acquire a transaction lock on the leaf page;
2564 * action: xad insertion/extension;
2566 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2567 xtlck = (struct xtlock *) & tlck->lock;
2569 /* insert the new entry: mark the entry NEW */
2570 xad = &p->xad[index];
2571 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2573 /* advance next available entry index */
2574 p->header.nextindex =
2575 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2578 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2579 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2586 /* unpin the leaf page */
2591 #ifdef _STILL_TO_PORT
2593 /* - TBD for defragmentaion/reorganization -
2598 * delete the entry with the specified key.
2600 * N.B.: whole extent of the entry is assumed to be deleted.
2605 * ENOENT: if the entry is not found.
2609 int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2612 struct btstack btstack;
2615 struct metapage *mp;
2617 int index, nextindex;
2619 struct xtlock *xtlck;
2622 * find the matching entry; xtSearch() pins the page
2624 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2627 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2629 /* unpin the leaf page */
2635 * delete the entry from the leaf page
2637 nextindex = le16_to_cpu(p->header.nextindex);
2638 p->header.nextindex =
2639 cpu_to_le16(le16_to_cpu(p->header.nextindex) - 1);
2642 * if the leaf page bocome empty, free the page
2644 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2645 return (xtDeleteUp(tid, ip, mp, p, &btstack));
2647 BT_MARK_DIRTY(mp, ip);
2649 * acquire a transaction lock on the leaf page;
2651 * action:xad deletion;
2653 tlck = txLock(tid, ip, mp, tlckXTREE);
2654 xtlck = (struct xtlock *) & tlck->lock;
2656 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2658 /* if delete from middle, shift left/compact the remaining entries */
2659 if (index < nextindex - 1)
2660 memmove(&p->xad[index], &p->xad[index + 1],
2661 (nextindex - index - 1) * sizeof(xad_t));
2669 /* - TBD for defragmentaion/reorganization -
2674 * free empty pages as propagating deletion up the tree
2681 xtDeleteUp(tid_t tid, struct inode *ip,
2682 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2685 struct metapage *mp;
2687 int index, nextindex;
2690 struct btframe *parent;
2692 struct xtlock *xtlck;
2695 * keep root leaf page which has become empty
2697 if (fp->header.flag & BT_ROOT) {
2698 /* keep the root page */
2699 fp->header.flag &= ~BT_INTERNAL;
2700 fp->header.flag |= BT_LEAF;
2701 fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2703 /* XT_PUTPAGE(fmp); */
2709 * free non-root leaf page
2711 if ((rc = xtRelink(tid, ip, fp))) {
2716 xaddr = addressPXD(&fp->header.self);
2717 xlen = lengthPXD(&fp->header.self);
2718 /* free the page extent */
2719 dbFree(ip, xaddr, (s64) xlen);
2721 /* free the buffer page */
2722 discard_metapage(fmp);
2725 * propagate page deletion up the index tree
2727 * If the delete from the parent page makes it empty,
2728 * continue all the way up the tree.
2729 * stop if the root page is reached (which is never deleted) or
2730 * if the entry deletion does not empty the page.
2732 while ((parent = BT_POP(btstack)) != NULL) {
2733 /* get/pin the parent page <sp> */
2734 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2738 index = parent->index;
2740 /* delete the entry for the freed child page from parent.
2742 nextindex = le16_to_cpu(p->header.nextindex);
2745 * the parent has the single entry being deleted:
2746 * free the parent page which has become empty.
2748 if (nextindex == 1) {
2749 if (p->header.flag & BT_ROOT) {
2750 /* keep the root page */
2751 p->header.flag &= ~BT_INTERNAL;
2752 p->header.flag |= BT_LEAF;
2753 p->header.nextindex =
2754 cpu_to_le16(XTENTRYSTART);
2756 /* XT_PUTPAGE(mp); */
2760 /* free the parent page */
2761 if ((rc = xtRelink(tid, ip, p)))
2764 xaddr = addressPXD(&p->header.self);
2765 /* free the page extent */
2767 (s64) JFS_SBI(ip->i_sb)->nbperpage);
2769 /* unpin/free the buffer page */
2770 discard_metapage(mp);
2777 * the parent has other entries remaining:
2778 * delete the router entry from the parent page.
2781 BT_MARK_DIRTY(mp, ip);
2783 * acquire a transaction lock on the leaf page;
2785 * action:xad deletion;
2787 tlck = txLock(tid, ip, mp, tlckXTREE);
2788 xtlck = (struct xtlock *) & tlck->lock;
2790 (xtlck->lwm.offset) ? min(index,
2794 /* if delete from middle,
2795 * shift left/compact the remaining entries in the page
2797 if (index < nextindex - 1)
2798 memmove(&p->xad[index], &p->xad[index + 1],
2799 (nextindex - index -
2800 1) << L2XTSLOTSIZE);
2802 p->header.nextindex =
2803 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2805 jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2806 (ulong) parent->bn, index);
2809 /* unpin the parent page */
2812 /* exit propagation up */
2821 * NAME: xtRelocate()
2823 * FUNCTION: relocate xtpage or data extent of regular file;
2824 * This function is mainly used by defragfs utility.
2826 * NOTE: This routine does not have the logic to handle
2827 * uncommitted allocated extent. The caller should call
2828 * txCommit() to commit all the allocation before call
2832 xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2833 s64 nxaddr, /* new xaddr */
2835 { /* extent type: XTPAGE or DATAEXT */
2837 struct tblock *tblk;
2839 struct xtlock *xtlck;
2840 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
2841 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
2846 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2848 s64 offset, nbytes, nbrd, pno;
2849 int nb, npages, nblks;
2853 struct pxd_lock *pxdlock;
2854 struct btstack btstack; /* traverse stack */
2856 xtype = xtype & EXTENT_TYPE;
2858 xoff = offsetXAD(oxad);
2859 oxaddr = addressXAD(oxad);
2860 xlen = lengthXAD(oxad);
2862 /* validate extent offset */
2863 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2864 if (offset >= ip->i_size)
2865 return -ESTALE; /* stale extent */
2867 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2868 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2871 * 1. get and validate the parent xtpage/xad entry
2872 * covering the source extent to be relocated;
2874 if (xtype == DATAEXT) {
2875 /* search in leaf entry */
2876 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2880 /* retrieve search result */
2881 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2888 /* validate for exact match with a single entry */
2889 xad = &pp->xad[index];
2890 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2894 } else { /* (xtype == XTPAGE) */
2896 /* search in internal entry */
2897 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2901 /* retrieve search result */
2902 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2909 /* xtSearchNode() validated for exact match with a single entry
2911 xad = &pp->xad[index];
2913 jfs_info("xtRelocate: parent xad entry validated.");
2916 * 2. relocate the extent
2918 if (xtype == DATAEXT) {
2919 /* if the extent is allocated-but-not-recorded
2920 * there is no real data to be moved in this extent,
2922 if (xad->flag & XAD_NOTRECORDED)
2925 /* release xtpage for cmRead()/xtLookup() */
2931 * copy target data pages to be relocated;
2933 * data extent must start at page boundary and
2934 * multiple of page size (except the last data extent);
2935 * read in each page of the source data extent into cbuf,
2936 * update the cbuf extent descriptor of the page to be
2937 * homeward bound to new dst data extent
2938 * copy the data from the old extent to new extent.
2939 * copy is essential for compressed files to avoid problems
2940 * that can arise if there was a change in compression
2942 * it is a good strategy because it may disrupt cache
2943 * policy to keep the pages in memory afterwards.
2945 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2946 assert((offset & CM_OFFSET) == 0);
2947 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2948 pno = offset >> CM_L2BSIZE;
2949 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2951 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2952 (offset >> CM_L2BSIZE) + 1;
2957 /* process the request one cache buffer at a time */
2958 for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2959 offset += nb, pno++, npages--) {
2960 /* compute page size */
2961 nb = min(nbytes - nbrd, CM_BSIZE);
2963 /* get the cache buffer of the page */
2964 if (rc = cmRead(ip, offset, npages, &cp))
2967 assert(addressPXD(&cp->cm_pxd) == sxaddr);
2968 assert(!cp->cm_modified);
2970 /* bind buffer with the new extent address */
2971 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2972 cmSetXD(ip, cp, pno, dxaddr, nblks);
2974 /* release the cbuf, mark it as modified */
2981 /* get back parent page */
2982 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2985 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2986 jfs_info("xtRelocate: target data extent relocated.");
2987 } else { /* (xtype == XTPAGE) */
2990 * read in the target xtpage from the source extent;
2992 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2999 * read in sibling pages if any to update sibling pointers;
3002 if (p->header.next) {
3003 nextbn = le64_to_cpu(p->header.next);
3004 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
3013 if (p->header.prev) {
3014 prevbn = le64_to_cpu(p->header.prev);
3015 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
3025 /* at this point, all xtpages to be updated are in memory */
3028 * update sibling pointers of sibling xtpages if any;
3031 BT_MARK_DIRTY(lmp, ip);
3033 txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
3034 lp->header.next = cpu_to_le64(nxaddr);
3039 BT_MARK_DIRTY(rmp, ip);
3041 txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
3042 rp->header.prev = cpu_to_le64(nxaddr);
3047 * update the target xtpage to be relocated
3049 * update the self address of the target page
3050 * and write to destination extent;
3051 * redo image covers the whole xtpage since it is new page
3052 * to the destination extent;
3053 * update of bmap for the free of source extent
3054 * of the target xtpage itself:
3055 * update of bmap for the allocation of destination extent
3056 * of the target xtpage itself:
3057 * update of bmap for the extents covered by xad entries in
3058 * the target xtpage is not necessary since they are not
3060 * if not committed before this relocation,
3061 * target page may contain XAD_NEW entries which must
3062 * be scanned for bmap update (logredo() always
3063 * scan xtpage REDOPAGE image for bmap update);
3064 * if committed before this relocation (tlckRELOCATE),
3065 * scan may be skipped by commit() and logredo();
3067 BT_MARK_DIRTY(mp, ip);
3068 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
3069 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
3070 xtlck = (struct xtlock *) & tlck->lock;
3072 /* update the self address in the xtpage header */
3073 pxd = &p->header.self;
3074 PXDaddress(pxd, nxaddr);
3076 /* linelock for the after image of the whole page */
3078 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
3080 /* update the buffer extent descriptor of target xtpage */
3081 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
3082 bmSetXD(mp, nxaddr, xsize);
3084 /* unpin the target page to new homeward bound */
3086 jfs_info("xtRelocate: target xtpage relocated.");
3090 * 3. acquire maplock for the source extent to be freed;
3092 * acquire a maplock saving the src relocated extent address;
3093 * to free of the extent at commit time;
3096 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
3097 * free PXD of the source data extent (logredo() will update
3098 * bmap for free of source data extent), and update bmap for
3099 * free of the source data extent;
3101 if (xtype == DATAEXT)
3102 tlck = txMaplock(tid, ip, tlckMAP);
3103 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
3104 * for the source xtpage (logredo() will init NoRedoPage
3105 * filter and will also update bmap for free of the source
3106 * xtpage), and update bmap for free of the source xtpage;
3107 * N.B. We use tlckMAP instead of tlkcXTREE because there
3108 * is no buffer associated with this lock since the buffer
3109 * has been redirected to the target location.
3111 else /* (xtype == XTPAGE) */
3112 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
3114 pxdlock = (struct pxd_lock *) & tlck->lock;
3115 pxdlock->flag = mlckFREEPXD;
3116 PXDaddress(&pxdlock->pxd, oxaddr);
3117 PXDlength(&pxdlock->pxd, xlen);
3121 * 4. update the parent xad entry for relocation;
3123 * acquire tlck for the parent entry with XAD_NEW as entry
3124 * update which will write LOG_REDOPAGE and update bmap for
3125 * allocation of XAD_NEW destination extent;
3127 jfs_info("xtRelocate: update parent xad entry.");
3128 BT_MARK_DIRTY(pmp, ip);
3129 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
3130 xtlck = (struct xtlock *) & tlck->lock;
3132 /* update the XAD with the new destination extent; */
3133 xad = &pp->xad[index];
3134 xad->flag |= XAD_NEW;
3135 XADaddress(xad, nxaddr);
3137 xtlck->lwm.offset = min(index, xtlck->lwm.offset);
3138 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
3141 /* unpin the parent xtpage */
3151 * function: search for the internal xad entry covering specified extent.
3152 * This function is mainly used by defragfs utility.
3156 * xad - extent to find;
3157 * cmpp - comparison result:
3158 * btstack - traverse stack;
3159 * flag - search process flag;
3162 * btstack contains (bn, index) of search path traversed to the entry.
3163 * *cmpp is set to result of comparison with the entry returned.
3164 * the page containing the entry is pinned at exit.
3166 static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
3167 int *cmpp, struct btstack * btstack, int flag)
3172 int cmp = 1; /* init for empty page */
3173 s64 bn; /* block number */
3174 struct metapage *mp; /* meta-page buffer */
3175 xtpage_t *p; /* page */
3176 int base, index, lim;
3177 struct btframe *btsp;
3182 xoff = offsetXAD(xad);
3183 xlen = lengthXAD(xad);
3184 xaddr = addressXAD(xad);
3187 * search down tree from root:
3189 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
3190 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
3192 * if entry with search key K is not found
3193 * internal page search find the entry with largest key Ki
3194 * less than K which point to the child page to search;
3195 * leaf page search find the entry with smallest key Kj
3196 * greater than K so that the returned index is the position of
3197 * the entry to be shifted right for insertion of new entry.
3198 * for empty tree, search key is greater than any key of the tree.
3200 * by convention, root bn = 0.
3203 /* get/pin the page to search */
3204 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3207 if (p->header.flag & BT_LEAF) {
3212 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3215 * binary search with search key K on the current page
3217 for (base = XTENTRYSTART; lim; lim >>= 1) {
3218 index = base + (lim >> 1);
3220 XT_CMP(cmp, xoff, &p->xad[index], t64);
3225 * verify for exact match;
3227 if (xaddr == addressXAD(&p->xad[index]) &&
3228 xoff == offsetXAD(&p->xad[index])) {
3231 /* save search result */
3232 btsp = btstack->top;
3234 btsp->index = index;
3240 /* descend/search its child page */
3251 * search miss - non-leaf page:
3253 * base is the smallest index with key (Kj) greater than
3254 * search key (K) and may be zero or maxentry index.
3255 * if base is non-zero, decrement base by one to get the parent
3256 * entry of the child page to search.
3258 index = base ? base - 1 : base;
3261 * go down to child page
3264 /* get the child page block number */
3265 bn = addressXAD(&p->xad[index]);
3267 /* unpin the parent page */
3277 * link around a freed page.
3286 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
3289 struct metapage *mp;
3293 nextbn = le64_to_cpu(p->header.next);
3294 prevbn = le64_to_cpu(p->header.prev);
3296 /* update prev pointer of the next page */
3298 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3303 * acquire a transaction lock on the page;
3305 * action: update prev pointer;
3307 BT_MARK_DIRTY(mp, ip);
3308 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3310 /* the page may already have been tlock'd */
3312 p->header.prev = cpu_to_le64(prevbn);
3317 /* update next pointer of the previous page */
3319 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3324 * acquire a transaction lock on the page;
3326 * action: update next pointer;
3328 BT_MARK_DIRTY(mp, ip);
3329 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3331 /* the page may already have been tlock'd */
3333 p->header.next = le64_to_cpu(nextbn);
3340 #endif /* _STILL_TO_PORT */
3346 * initialize file root (inline in inode)
3348 void xtInitRoot(tid_t tid, struct inode *ip)
3353 * acquire a transaction lock on the root
3357 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3358 tlckXTREE | tlckNEW);
3359 p = &JFS_IP(ip)->i_xtroot;
3361 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3362 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3364 if (S_ISDIR(ip->i_mode))
3365 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3367 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3377 * We can run into a deadlock truncating a file with a large number of
3378 * xtree pages (large fragmented file). A robust fix would entail a
3379 * reservation system where we would reserve a number of metadata pages
3380 * and tlocks which we would be guaranteed without a deadlock. Without
3381 * this, a partial fix is to limit number of metadata pages we will lock
3382 * in a single transaction. Currently we will truncate the file so that
3383 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3384 * will be responsible for ensuring that the current transaction gets
3385 * committed, and that subsequent transactions are created to truncate
3386 * the file further if needed.
3388 #define MAX_TRUNCATE_LEAVES 50
3394 * traverse for truncation logging backward bottom up;
3395 * terminate at the last extent entry at the current subtree
3396 * root page covering new down size.
3397 * truncation may occur within the last extent entry.
3403 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3409 * 1. truncate (non-COMMIT_NOLINK file)
3410 * by jfs_truncate() or jfs_open(O_TRUNC):
3412 * 2. truncate index table of directory when last entry removed
3413 * map update via tlock at commit time;
3415 * Call xtTruncate_pmap instead
3417 * 1. remove (free zero link count) on last reference release
3418 * (pmap has been freed at commit zero link count);
3419 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3421 * map update directly at truncation time;
3424 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3425 * else if (TRUNCATE)
3426 * must write LOG_NOREDOPAGE for deleted index page;
3428 * pages may already have been tlocked by anonymous transactions
3429 * during file growth (i.e., write) before truncation;
3431 * except last truncated entry, deleted entries remains as is
3432 * in the page (nextindex is updated) for other use
3433 * (e.g., log/update allocation map): this avoid copying the page
3434 * info but delay free of pages;
3437 s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3441 struct metapage *mp;
3444 int index, nextindex;
3447 int xlen, len, freexlen;
3448 struct btstack btstack;
3449 struct btframe *parent;
3450 struct tblock *tblk = NULL;
3451 struct tlock *tlck = NULL;
3452 struct xtlock *xtlck = NULL;
3453 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
3454 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
3457 int locked_leaves = 0;
3459 /* save object truncation type */
3461 tblk = tid_to_tblock(tid);
3462 tblk->xflag |= flag;
3468 assert(flag != COMMIT_PMAP);
3470 if (flag == COMMIT_PWMAP)
3474 xadlock.flag = mlckFREEXADLIST;
3479 * if the newsize is not an integral number of pages,
3480 * the file between newsize and next page boundary will
3482 * if truncating into a file hole, it will cause
3483 * a full block to be allocated for the logical block.
3487 * release page blocks of truncated region <teof, eof>
3489 * free the data blocks from the leaf index blocks.
3490 * delete the parent index entries corresponding to
3491 * the freed child data/index blocks.
3492 * free the index blocks themselves which aren't needed
3493 * in new sized file.
3495 * index blocks are updated only if the blocks are to be
3496 * retained in the new sized file.
3497 * if type is PMAP, the data and index pages are NOT
3498 * freed, and the data and index blocks are NOT freed
3500 * (this will allow continued access of data/index of
3501 * temporary file (zerolink count file truncated to zero-length)).
3503 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3504 JFS_SBI(ip->i_sb)->l2bsize;
3512 * root resides in the inode
3517 * first access of each page:
3520 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3524 /* process entries backward from last index */
3525 index = le16_to_cpu(p->header.nextindex) - 1;
3527 if (p->header.flag & BT_INTERNAL)
3534 /* Since this is the rightmost leaf, and we may have already freed
3535 * a page that was formerly to the right, let's make sure that the
3536 * next pointer is zero.
3538 if (p->header.next) {
3541 * Make sure this change to the header is logged.
3542 * If we really truncate this leaf, the flag
3543 * will be changed to tlckTRUNCATE
3545 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
3546 BT_MARK_DIRTY(mp, ip);
3552 /* does region covered by leaf page precede Teof ? */
3553 xad = &p->xad[index];
3554 xoff = offsetXAD(xad);
3555 xlen = lengthXAD(xad);
3556 if (teof >= xoff + xlen) {
3561 /* (re)acquire tlock of the leaf page */
3563 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3565 * We need to limit the size of the transaction
3566 * to avoid exhausting pagecache & tlocks
3569 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3572 tlck = txLock(tid, ip, mp, tlckXTREE);
3573 tlck->type = tlckXTREE | tlckTRUNCATE;
3574 xtlck = (struct xtlock *) & tlck->lock;
3575 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3577 BT_MARK_DIRTY(mp, ip);
3580 * scan backward leaf page entries
3582 for (; index >= XTENTRYSTART; index--) {
3583 xad = &p->xad[index];
3584 xoff = offsetXAD(xad);
3585 xlen = lengthXAD(xad);
3586 xaddr = addressXAD(xad);
3589 * The "data" for a directory is indexed by the block
3590 * device's address space. This metadata must be invalidated
3593 if (S_ISDIR(ip->i_mode) && (teof == 0))
3594 invalidate_xad_metapages(ip, *xad);
3596 * entry beyond eof: continue scan of current page
3598 * ---|---=======------->
3607 * (xoff <= teof): last entry to be deleted from page;
3608 * If other entries remain in page: keep and update the page.
3612 * eof == entry_start: delete the entry
3614 * -------|=======------->
3621 if (index == XTENTRYSTART)
3627 * eof within the entry: truncate the entry.
3629 * -------===|===------->
3632 else if (teof < xoff + xlen) {
3633 /* update truncated entry */
3635 freexlen = xlen - len;
3636 XADlength(xad, len);
3638 /* save pxd of truncated extent in tlck */
3640 if (log) { /* COMMIT_PWMAP */
3641 xtlck->lwm.offset = (xtlck->lwm.offset) ?
3642 min(index, (int)xtlck->lwm.offset) : index;
3643 xtlck->lwm.length = index + 1 -
3645 xtlck->twm.offset = index;
3646 pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3647 pxdlock->flag = mlckFREEPXD;
3648 PXDaddress(&pxdlock->pxd, xaddr);
3649 PXDlength(&pxdlock->pxd, freexlen);
3651 /* free truncated extent */
3652 else { /* COMMIT_WMAP */
3654 pxdlock = (struct pxd_lock *) & xadlock;
3655 pxdlock->flag = mlckFREEPXD;
3656 PXDaddress(&pxdlock->pxd, xaddr);
3657 PXDlength(&pxdlock->pxd, freexlen);
3658 txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
3660 /* reset map lock */
3661 xadlock.flag = mlckFREEXADLIST;
3664 /* current entry is new last entry; */
3665 nextindex = index + 1;
3670 * eof beyond the entry:
3672 * -------=======---|--->
3675 else { /* (xoff + xlen < teof) */
3677 nextindex = index + 1;
3680 if (nextindex < le16_to_cpu(p->header.nextindex)) {
3681 if (!log) { /* COMMIT_WAMP */
3682 xadlock.xdlist = &p->xad[nextindex];
3684 le16_to_cpu(p->header.nextindex) -
3686 txFreeMap(ip, (struct maplock *) & xadlock,
3689 p->header.nextindex = cpu_to_le16(nextindex);
3694 /* assert(freed == 0); */
3696 } /* end scan of leaf page entries */
3701 * leaf page become empty: free the page if type != PMAP
3703 if (log) { /* COMMIT_PWMAP */
3704 /* txCommit() with tlckFREE:
3705 * free data extents covered by leaf [XTENTRYSTART:hwm);
3706 * invalidate leaf if COMMIT_PWMAP;
3707 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3709 tlck->type = tlckXTREE | tlckFREE;
3710 } else { /* COMMIT_WAMP */
3712 /* free data extents covered by leaf */
3713 xadlock.xdlist = &p->xad[XTENTRYSTART];
3715 le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3716 txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
3719 if (p->header.flag & BT_ROOT) {
3720 p->header.flag &= ~BT_INTERNAL;
3721 p->header.flag |= BT_LEAF;
3722 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3724 XT_PUTPAGE(mp); /* debug */
3727 if (log) { /* COMMIT_PWMAP */
3728 /* page will be invalidated at tx completion
3731 } else { /* COMMIT_WMAP */
3734 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3736 /* invalidate empty leaf page */
3737 discard_metapage(mp);
3742 * the leaf page become empty: delete the parent entry
3743 * for the leaf page if the parent page is to be kept
3744 * in the new sized file.
3748 * go back up to the parent page
3751 /* pop/restore parent entry for the current child page */
3752 if ((parent = BT_POP(&btstack)) == NULL)
3753 /* current page must have been root */
3756 /* get back the parent page */
3758 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3762 index = parent->index;
3765 * child page was not empty:
3768 /* has any entry deleted from parent ? */
3769 if (index < le16_to_cpu(p->header.nextindex) - 1) {
3770 /* (re)acquire tlock on the parent page */
3771 if (log) { /* COMMIT_PWMAP */
3772 /* txCommit() with tlckTRUNCATE:
3773 * free child extents covered by parent [);
3775 tlck = txLock(tid, ip, mp, tlckXTREE);
3776 xtlck = (struct xtlock *) & tlck->lock;
3777 if (!(tlck->type & tlckTRUNCATE)) {
3779 le16_to_cpu(p->header.
3782 tlckXTREE | tlckTRUNCATE;
3784 } else { /* COMMIT_WMAP */
3786 /* free child extents covered by parent */
3787 xadlock.xdlist = &p->xad[index + 1];
3789 le16_to_cpu(p->header.nextindex) -
3791 txFreeMap(ip, (struct maplock *) & xadlock,
3794 BT_MARK_DIRTY(mp, ip);
3796 p->header.nextindex = cpu_to_le16(index + 1);
3803 * child page was empty:
3805 nfreed += lengthXAD(&p->xad[index]);
3808 * During working map update, child page's tlock must be handled
3809 * before parent's. This is because the parent's tlock will cause
3810 * the child's disk space to be marked available in the wmap, so
3811 * it's important that the child page be released by that time.
3813 * ToDo: tlocks should be on doubly-linked list, so we can
3814 * quickly remove it and add it to the end.
3818 * Move parent page's tlock to the end of the tid's tlock list
3820 if (log && mp->lid && (tblk->last != mp->lid) &&
3821 lid_to_tlock(mp->lid)->tid) {
3822 lid_t lid = mp->lid;
3825 tlck = lid_to_tlock(lid);
3827 if (tblk->next == lid)
3828 tblk->next = tlck->next;
3830 for (prev = lid_to_tlock(tblk->next);
3832 prev = lid_to_tlock(prev->next)) {
3835 prev->next = tlck->next;
3837 lid_to_tlock(tblk->last)->next = lid;
3843 * parent page become empty: free the page
3845 if (index == XTENTRYSTART) {
3846 if (log) { /* COMMIT_PWMAP */
3847 /* txCommit() with tlckFREE:
3848 * free child extents covered by parent;
3849 * invalidate parent if COMMIT_PWMAP;
3851 tlck = txLock(tid, ip, mp, tlckXTREE);
3852 xtlck = (struct xtlock *) & tlck->lock;
3854 le16_to_cpu(p->header.nextindex) - 1;
3855 tlck->type = tlckXTREE | tlckFREE;
3856 } else { /* COMMIT_WMAP */
3858 /* free child extents covered by parent */
3859 xadlock.xdlist = &p->xad[XTENTRYSTART];
3861 le16_to_cpu(p->header.nextindex) -
3863 txFreeMap(ip, (struct maplock *) & xadlock, NULL,
3866 BT_MARK_DIRTY(mp, ip);
3868 if (p->header.flag & BT_ROOT) {
3869 p->header.flag &= ~BT_INTERNAL;
3870 p->header.flag |= BT_LEAF;
3871 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3872 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3874 * Shrink root down to allow inline
3875 * EA (otherwise fsck complains)
3877 p->header.maxentry =
3878 cpu_to_le16(XTROOTINITSLOT);
3879 JFS_IP(ip)->mode2 |= INLINEEA;
3882 XT_PUTPAGE(mp); /* debug */
3885 if (log) { /* COMMIT_PWMAP */
3886 /* page will be invalidated at tx completion
3889 } else { /* COMMIT_WMAP */
3892 lid_to_tlock(mp->lid)->flag |=
3895 /* invalidate parent page */
3896 discard_metapage(mp);
3899 /* parent has become empty and freed:
3900 * go back up to its parent page
3907 * parent page still has entries for front region;
3910 /* try truncate region covered by preceding entry
3911 * (process backward)
3915 /* go back down to the child page corresponding
3922 * internal page: go down to child page of current entry
3925 /* save current parent entry for the child page */
3926 BT_PUSH(&btstack, bn, index);
3928 /* get child page */
3929 xad = &p->xad[index];
3930 bn = addressXAD(xad);
3933 * first access of each internal entry:
3935 /* release parent page */
3938 /* process the child page */
3943 * update file resource stat
3947 if (S_ISDIR(ip->i_mode) && !newsize)
3948 ip->i_size = 1; /* fsck hates zero-length directories */
3950 ip->i_size = newsize;
3952 /* update quota allocation to reflect freed blocks */
3953 DQUOT_FREE_BLOCK(ip, nfreed);
3956 * free tlock of invalidated pages
3958 if (flag == COMMIT_WMAP)
3969 * Perform truncate to zero lenghth for deleted file, leaving the
3970 * the xtree and working map untouched. This allows the file to
3971 * be accessed via open file handles, while the delete of the file
3972 * is committed to disk.
3977 * s64 committed_size)
3979 * return: new committed size
3983 * To avoid deadlock by holding too many transaction locks, the
3984 * truncation may be broken up into multiple transactions.
3985 * The committed_size keeps track of part of the file has been
3986 * freed from the pmaps.
3988 s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3991 struct btstack btstack;
3994 int locked_leaves = 0;
3995 struct metapage *mp;
3997 struct btframe *parent;
3999 struct tblock *tblk;
4000 struct tlock *tlck = NULL;
4004 struct xtlock *xtlck = NULL;
4006 /* save object truncation type */
4007 tblk = tid_to_tblock(tid);
4008 tblk->xflag |= COMMIT_PMAP;
4013 if (committed_size) {
4014 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
4015 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
4019 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
4024 "xtTruncate_pmap: did not find extent");
4031 * root resides in the inode
4036 * first access of each page:
4039 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4043 /* process entries backward from last index */
4044 index = le16_to_cpu(p->header.nextindex) - 1;
4046 if (p->header.flag & BT_INTERNAL)
4054 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
4056 * We need to limit the size of the transaction
4057 * to avoid exhausting pagecache & tlocks
4059 xad = &p->xad[index];
4060 xoff = offsetXAD(xad);
4061 xlen = lengthXAD(xad);
4063 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
4065 tlck = txLock(tid, ip, mp, tlckXTREE);
4066 tlck->type = tlckXTREE | tlckFREE;
4067 xtlck = (struct xtlock *) & tlck->lock;
4068 xtlck->hwm.offset = index;
4074 * go back up to the parent page
4077 /* pop/restore parent entry for the current child page */
4078 if ((parent = BT_POP(&btstack)) == NULL)
4079 /* current page must have been root */
4082 /* get back the parent page */
4084 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4088 index = parent->index;
4091 * parent page become empty: free the page
4093 if (index == XTENTRYSTART) {
4094 /* txCommit() with tlckFREE:
4095 * free child extents covered by parent;
4096 * invalidate parent if COMMIT_PWMAP;
4098 tlck = txLock(tid, ip, mp, tlckXTREE);
4099 xtlck = (struct xtlock *) & tlck->lock;
4101 le16_to_cpu(p->header.nextindex) - 1;
4102 tlck->type = tlckXTREE | tlckFREE;
4106 if (p->header.flag & BT_ROOT) {
4114 * parent page still has entries for front region;
4119 * internal page: go down to child page of current entry
4122 /* save current parent entry for the child page */
4123 BT_PUSH(&btstack, bn, index);
4125 /* get child page */
4126 xad = &p->xad[index];
4127 bn = addressXAD(xad);
4130 * first access of each internal entry:
4132 /* release parent page */
4135 /* process the child page */
4144 #ifdef _JFS_DEBUG_XTREE
4148 * function: traverse forward
4150 int xtDisplayTree(struct inode *ip)
4153 struct metapage *mp;
4156 int index, lastindex, v, h;
4158 struct btstack btstack;
4159 struct btframe *btsp;
4160 struct btframe *parent;
4162 printk("display B+-tree.\n");
4165 btsp = btstack.stack;
4170 * root resides in the inode
4176 * first access of each page:
4179 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4183 /* process entries forward from first index */
4184 index = XTENTRYSTART;
4185 lastindex = le16_to_cpu(p->header.nextindex) - 1;
4187 if (p->header.flag & BT_INTERNAL) {
4189 * first access of each internal page
4192 } else { /* (p->header.flag & BT_LEAF) */
4195 * first access of each leaf page
4197 printf("leaf page ");
4198 xtDisplayPage(ip, bn, p);
4200 /* unpin the leaf page */
4205 * go back up to the parent page
4208 /* pop/restore parent entry for the current child page */
4209 if ((parent = (btsp == btstack.stack ? NULL : --btsp)) == NULL)
4210 /* current page must have been root */
4214 * parent page scan completed
4216 if ((index = parent->index) == (lastindex = parent->lastindex)) {
4217 /* go back up to the parent page */
4222 * parent page has entries remaining
4224 /* get back the parent page */
4226 /* v = parent->level; */
4227 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4231 /* get next parent entry */
4235 * internal page: go down to child page of current entry
4238 /* push/save current parent entry for the child page */
4239 btsp->bn = pbn = bn;
4240 btsp->index = index;
4241 btsp->lastindex = lastindex;
4242 /* btsp->level = v; */
4243 /* btsp->node = h; */
4246 /* get child page */
4247 xad = &p->xad[index];
4248 bn = addressXAD(xad);
4251 * first access of each internal entry:
4253 /* release parent page */
4256 printk("traverse down 0x%lx[%d]->0x%lx\n", (ulong) pbn, index,
4261 /* process the child page */
4269 * function: display page
4271 int xtDisplayPage(struct inode *ip, s64 bn, xtpage_t * p)
4278 /* display page control */
4279 printf("bn:0x%lx flag:0x%x nextindex:%d\n",
4280 (ulong) bn, p->header.flag,
4281 le16_to_cpu(p->header.nextindex));
4283 /* display entries */
4284 xad = &p->xad[XTENTRYSTART];
4285 for (i = XTENTRYSTART, j = 1; i < le16_to_cpu(p->header.nextindex);
4287 xoff = offsetXAD(xad);
4288 xaddr = addressXAD(xad);
4289 xlen = lengthXAD(xad);
4290 printf("\t[%d] 0x%lx:0x%lx(0x%x)", i, (ulong) xoff,
4291 (ulong) xaddr, xlen);
4301 #endif /* _JFS_DEBUG_XTREE */
4309 * traverse for allocation acquiring tlock at commit time
4310 * (vs at the time of update) logging backward top down
4313 * problem - establishing that all new allocation have been
4314 * processed both for append and random write in sparse file
4315 * at the current entry at the current subtree root page
4318 int xtGather(btree_t *t)
4325 struct btstack btstack;
4326 struct btsf *parent;
4334 * root resides in the inode
4337 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4341 /* new root is NOT pointed by a new entry
4342 if (p->header.flag & NEW)
4343 allocate new page lock;
4344 write a NEWPAGE log;
4349 * first access of each page:
4351 /* process entries backward from last index */
4352 index = le16_to_cpu(p->header.nextindex) - 1;
4354 if (p->header.flag & BT_LEAF) {
4356 * first access of each leaf page
4358 /* process leaf page entries backward */
4359 for (; index >= XTENTRYSTART; index--) {
4362 * if newpage, log NEWPAGE.
4364 if (e->flag & XAD_NEW) {
4365 nfound =+ entry->length;
4366 update current page lock for the entry;
4369 * if moved, log move.
4371 } else if (e->flag & XAD_MOVED) {
4373 update current page lock for the entry;
4378 /* unpin the leaf page */
4382 * go back up to the parent page
4385 /* restore parent entry for the current child page */
4386 if ((parent = BT_POP(&btstack)) == NULL)
4387 /* current page must have been root */
4390 if ((index = parent->index) == XTENTRYSTART) {
4392 * parent page scan completed
4394 /* go back up to the parent page */
4398 * parent page has entries remaining
4400 /* get back the parent page */
4402 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4406 /* first subroot page which
4407 * covers all new allocated blocks
4408 * itself not new/modified.
4409 * (if modified from split of descendent,
4410 * go down path of split page)
4412 if (nfound == nnew &&
4413 !(p->header.flag & (NEW | MOD)))
4417 /* process parent page entries backward */
4422 * first access of each internal page
4427 * internal page: go down to child page of current entry
4430 /* save current parent entry for the child page */
4431 BT_PUSH(&btstack, bn, index);
4433 /* get current entry for the child page */
4437 * first access of each internal entry:
4440 * if new entry, log btree_tnewentry.
4442 if (e->flag & XAD_NEW)
4443 update parent page lock for the entry;
4446 /* release parent page */
4449 /* get child page */
4451 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4456 * first access of each non-root page:
4459 * if new, log btree_newpage.
4461 if (p->header.flag & NEW)
4462 allocate new page lock;
4463 write a NEWPAGE log (next, prev);
4466 /* process the child page */
4472 #endif /* _JFS_WIP */
4475 #ifdef CONFIG_JFS_STATISTICS
4476 int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length,
4477 int *eof, void *data)
4482 len += sprintf(buffer,
4483 "JFS Xtree statistics\n"
4484 "====================\n"
4486 "fast searches = %d\n"
4493 *start = buffer + begin;