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 <linux/vs_dlimit.h>
25 #include "jfs_incore.h"
26 #include "jfs_filsys.h"
27 #include "jfs_metapage.h"
29 #include "jfs_dinode.h"
30 #include "jfs_superblock.h"
31 #include "jfs_debug.h"
36 #define XT_INSERT 0x00000001
39 * xtree key/entry comparison: extent offset
42 * -1: k < start of extent
43 * 0: start_of_extent <= k <= end_of_extent
44 * 1: k > end_of_extent
46 #define XT_CMP(CMP, K, X, OFFSET64)\
48 OFFSET64 = offsetXAD(X);\
49 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
50 ((K) < OFFSET64) ? -1 : 0;\
53 /* write a xad entry */
54 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
56 (XAD)->flag = (FLAG);\
57 XADoffset((XAD), (OFF));\
58 XADlength((XAD), (LEN));\
59 XADaddress((XAD), (ADDR));\
62 #define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)
64 /* get page buffer for specified block address */
65 /* ToDo: Replace this ugly macro with a function */
66 #define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
68 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
71 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
72 (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
73 (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
75 jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
84 #define XT_PUTPAGE(MP) BT_PUTPAGE(MP)
86 #define XT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
87 BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
88 /* xtree entry parameter descriptor */
96 struct pxdlist *pxdlist;
103 #ifdef CONFIG_JFS_STATISTICS
115 static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
116 struct btstack * btstack, int flag);
118 static int xtSplitUp(tid_t tid,
120 struct xtsplit * split, struct btstack * btstack);
122 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
123 struct metapage ** rmpp, s64 * rbnp);
125 static int xtSplitRoot(tid_t tid, struct inode *ip,
126 struct xtsplit * split, struct metapage ** rmpp);
128 #ifdef _STILL_TO_PORT
129 static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
130 xtpage_t * fp, struct btstack * btstack);
132 static int xtSearchNode(struct inode *ip,
134 int *cmpp, struct btstack * btstack, int flag);
136 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
137 #endif /* _STILL_TO_PORT */
142 * function: map a single page into a physical extent;
144 int xtLookup(struct inode *ip, s64 lstart,
145 s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
148 struct btstack btstack;
155 s64 next, size, xoff, xend;
163 /* is lookup offset beyond eof ? */
164 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
165 JFS_SBI(ip->i_sb)->l2bsize;
166 if (lstart >= size) {
167 jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
168 (ulong) lstart, (ulong) size);
174 * search for the xad entry covering the logical extent
177 if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
178 jfs_err("xtLookup: xtSearch returned %d", rc);
183 * compute the physical extent covering logical extent
185 * N.B. search may have failed (e.g., hole in sparse file),
186 * and returned the index of the next entry.
188 /* retrieve search result */
189 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
191 /* is xad found covering start of logical extent ?
192 * lstart is a page start address,
193 * i.e., lstart cannot start in a hole;
197 *plen = min(next - lstart, llen);
204 xad = &p->xad[index];
205 xoff = offsetXAD(xad);
206 xlen = lengthXAD(xad);
208 xaddr = addressXAD(xad);
210 /* initialize new pxd */
212 *paddr = xaddr + (lstart - xoff);
213 /* a page must be fully covered by an xad */
214 *plen = min(xend - lstart, llen);
226 * function: map a single logical extent into a list of physical extent;
230 * struct lxdlist *lxdlist, lxd list (in)
231 * struct xadlist *xadlist, xad list (in/out)
234 * coverage of lxd by xad under assumption of
235 * . lxd's are ordered and disjoint.
236 * . xad's are ordered and disjoint.
241 * note: a page being written (even a single byte) is backed fully,
242 * except the last page which is only backed with blocks
243 * required to cover the last byte;
244 * the extent backing a page is fully contained within an xad;
246 int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
247 struct xadlist * xadlist, int flag)
250 struct btstack btstack;
258 s64 size, lstart, lend, xstart, xend, pstart;
259 s64 llen, xlen, plen;
261 int nlxd, npxd, maxnpxd;
263 npxd = xadlist->nxad = 0;
264 maxnpxd = xadlist->maxnxad;
267 nlxd = lxdlist->nlxd;
270 lstart = offsetLXD(lxd);
271 llen = lengthLXD(lxd);
272 lend = lstart + llen;
274 size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
275 JFS_SBI(ip->i_sb)->l2bsize;
278 * search for the xad entry covering the logical extent
284 if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
288 * compute the physical extent covering logical extent
290 * N.B. search may have failed (e.g., hole in sparse file),
291 * and returned the index of the next entry.
294 /* retrieve search result */
295 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
297 /* is xad on the next sibling page ? */
298 if (index == le16_to_cpu(p->header.nextindex)) {
299 if (p->header.flag & BT_ROOT)
302 if ((bn = le64_to_cpu(p->header.next)) == 0)
307 /* get next sibling page */
308 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
312 index = XTENTRYSTART;
315 xad = &p->xad[index];
318 * is lxd covered by xad ?
321 xstart = offsetXAD(xad);
322 xlen = lengthXAD(xad);
323 xend = xstart + xlen;
324 xaddr = addressXAD(xad);
330 /* (lstart <= xstart) */
332 /* lxd is NOT covered by xad */
333 if (lend <= xstart) {
341 lstart = offsetLXD(lxd);
342 llen = lengthLXD(lxd);
343 lend = lstart + llen;
347 /* compare with the current xad */
350 /* lxd is covered by xad */
351 else { /* (xstart < lend) */
353 /* initialize new pxd */
355 plen = min(lend - xstart, xlen);
361 /* (xstart < lstart) */
363 /* lxd is covered by xad */
365 /* initialize new pxd */
367 plen = min(xend - lstart, llen);
368 paddr = xaddr + (lstart - xstart);
372 /* lxd is NOT covered by xad */
373 else { /* (xend <= lstart) */
378 * linear search next xad covering lxd on
379 * the current xad page, and then tree search
381 if (index == le16_to_cpu(p->header.nextindex) - 1) {
382 if (p->header.flag & BT_ROOT)
391 /* compare with new xad */
397 * lxd is covered by xad and a new pxd has been initialized
398 * (lstart <= xstart < lend) or (xstart < lstart < xend)
401 /* finalize pxd corresponding to current xad */
402 XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);
404 if (++npxd >= maxnpxd)
409 * lxd is fully covered by xad
419 lstart = offsetLXD(lxd);
420 llen = lengthLXD(lxd);
421 lend = lstart + llen;
426 * test for old xad covering new lxd
427 * (old xstart < new lstart)
432 * lxd is partially covered by xad
434 else { /* (xend < lend) */
439 * linear search next xad covering lxd on
440 * the current xad page, and then next xad page search
442 if (index == le16_to_cpu(p->header.nextindex) - 1) {
443 if (p->header.flag & BT_ROOT)
446 if ((bn = le64_to_cpu(p->header.next)) == 0)
451 /* get next sibling page */
452 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
456 index = XTENTRYSTART;
457 xad = &p->xad[index];
464 * test for new xad covering old lxd
465 * (old lstart < new xstart)
471 xadlist->nxad = npxd;
483 * function: search for the xad entry covering specified offset.
487 * xoff - extent offset;
488 * nextp - address of next extent (if any) for search miss
489 * cmpp - comparison result:
490 * btstack - traverse stack;
491 * flag - search process flag (XT_INSERT);
494 * btstack contains (bn, index) of search path traversed to the entry.
495 * *cmpp is set to result of comparison with the entry returned.
496 * the page containing the entry is pinned at exit.
498 static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
499 int *cmpp, struct btstack * btstack, int flag)
501 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
503 int cmp = 1; /* init for empty page */
504 s64 bn; /* block number */
505 struct metapage *mp; /* page buffer */
506 xtpage_t *p; /* page */
508 int base, index, lim, btindex;
509 struct btframe *btsp;
510 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
585 /* (xoff >= t64 + lengthXAD(xad));
586 * matching entry may be further out:
587 * stop heuristic search
589 /* stop sequential access heuristics */
593 /* (index == p->header.nextindex);
594 * miss: key entry does not exist in
595 * the target leaf/tree
602 * if hit, return index of the entry found, and
603 * if miss, where new entry with search key is
607 /* compute number of pages to split */
608 if (flag & XT_INSERT) {
609 if (p->header.nextindex == /* little-endian */
614 btstack->nsplit = nsplit;
617 /* save search result */
623 /* update sequential access heuristics */
624 jfs_ip->btindex = index;
629 INCREMENT(xtStat.fastSearch);
633 /* well, ... full search now */
635 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
638 * binary search with search key K on the current page
640 for (base = XTENTRYSTART; lim; lim >>= 1) {
641 index = base + (lim >> 1);
643 XT_CMP(cmp, xoff, &p->xad[index], t64);
648 /* search hit - leaf page:
649 * return the entry found
651 if (p->header.flag & BT_LEAF) {
654 /* compute number of pages to split */
655 if (flag & XT_INSERT) {
656 if (p->header.nextindex ==
661 btstack->nsplit = nsplit;
664 /* save search result */
670 /* init sequential access heuristics */
671 btindex = jfs_ip->btindex;
672 if (index == btindex ||
673 index == btindex + 1)
674 jfs_ip->btorder = BT_SEQUENTIAL;
676 jfs_ip->btorder = BT_RANDOM;
677 jfs_ip->btindex = index;
681 /* search hit - internal page:
682 * descend/search its child page
684 if (index < le16_to_cpu(p->header.nextindex)-1)
685 next = offsetXAD(&p->xad[index + 1]);
698 * base is the smallest index with key (Kj) greater than
699 * search key (K) and may be zero or maxentry index.
701 if (base < le16_to_cpu(p->header.nextindex))
702 next = offsetXAD(&p->xad[base]);
704 * search miss - leaf page:
706 * return location of entry (base) where new entry with
707 * search key K is to be inserted.
709 if (p->header.flag & BT_LEAF) {
712 /* compute number of pages to split */
713 if (flag & XT_INSERT) {
714 if (p->header.nextindex ==
719 btstack->nsplit = nsplit;
722 /* save search result */
728 /* init sequential access heuristics */
729 btindex = jfs_ip->btindex;
730 if (base == btindex || base == btindex + 1)
731 jfs_ip->btorder = BT_SEQUENTIAL;
733 jfs_ip->btorder = BT_RANDOM;
734 jfs_ip->btindex = base;
743 * search miss - non-leaf page:
745 * if base is non-zero, decrement base by one to get the parent
746 * entry of the child page to search.
748 index = base ? base - 1 : base;
751 * go down to child page
754 /* update number of pages to split */
755 if (p->header.nextindex == p->header.maxentry)
760 /* push (bn, index) of the parent page/entry */
761 BT_PUSH(btstack, bn, index);
763 /* get the child page block number */
764 bn = addressXAD(&p->xad[index]);
766 /* unpin the parent page */
777 * tid - transaction id;
779 * xflag - extent flag (XAD_NOTRECORDED):
780 * xoff - extent offset;
781 * xlen - extent length;
782 * xaddrp - extent address pointer (in/out):
784 * caller allocated data extent at *xaddrp;
786 * allocate data extent and return its xaddr;
791 int xtInsert(tid_t tid, /* transaction id */
792 struct inode *ip, int xflag, s64 xoff, s32 xlen, s64 * xaddrp,
797 struct metapage *mp; /* meta-page buffer */
798 xtpage_t *p; /* base B+-tree index page */
800 int index, nextindex;
801 struct btstack btstack; /* traverse stack */
802 struct xtsplit split; /* split information */
807 struct xtlock *xtlck;
809 jfs_info("xtInsert: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
812 * search for the entry location at which to insert:
814 * xtFastSearch() and xtSearch() both returns (leaf page
815 * pinned, index at which to insert).
816 * n.b. xtSearch() may return index of maxentry of
819 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
822 /* retrieve search result */
823 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
825 /* This test must follow XT_GETSEARCH since mp must be valid if
826 * we branch to out: */
827 if ((cmp == 0) || (next && (xlen > next - xoff))) {
833 * allocate data extent requested
835 * allocation hint: last xad
837 if ((xaddr = *xaddrp) == 0) {
838 if (index > XTENTRYSTART) {
839 xad = &p->xad[index - 1];
840 hint = addressXAD(xad) + lengthXAD(xad) - 1;
843 if ((rc = DQUOT_ALLOC_BLOCK(ip, xlen)))
845 if ((rc = DLIMIT_ALLOC_BLOCK(ip, xlen))) {
846 DQUOT_FREE_BLOCK(ip, xlen);
849 if ((rc = dbAlloc(ip, hint, (s64) xlen, &xaddr))) {
850 DLIMIT_FREE_BLOCK(ip, xlen);
851 DQUOT_FREE_BLOCK(ip, xlen);
857 * insert entry for new extent
862 * if the leaf page is full, split the page and
863 * propagate up the router entry for the new page from split
865 * The xtSplitUp() will insert the entry and unpin the leaf page.
867 nextindex = le16_to_cpu(p->header.nextindex);
868 if (nextindex == le16_to_cpu(p->header.maxentry)) {
875 split.pxdlist = NULL;
876 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
877 /* undo data extent allocation */
879 dbFree(ip, xaddr, (s64) xlen);
880 DLIMIT_FREE_BLOCK(ip, xlen);
881 DQUOT_FREE_BLOCK(ip, xlen);
891 * insert the new entry into the leaf page
894 * acquire a transaction lock on the leaf page;
896 * action: xad insertion/extension;
898 BT_MARK_DIRTY(mp, ip);
900 /* if insert into middle, shift right remaining entries. */
901 if (index < nextindex)
902 memmove(&p->xad[index + 1], &p->xad[index],
903 (nextindex - index) * sizeof(xad_t));
905 /* insert the new entry: mark the entry NEW */
906 xad = &p->xad[index];
907 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
909 /* advance next available entry index */
910 p->header.nextindex =
911 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
913 /* Don't log it if there are no links to the file */
914 if (!test_cflag(COMMIT_Nolink, ip)) {
915 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
916 xtlck = (struct xtlock *) & tlck->lock;
918 (xtlck->lwm.offset) ? min(index,
919 (int)xtlck->lwm.offset) : index;
921 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
927 /* unpin the leaf page */
938 * split full pages as propagating insertion up the tree
941 * tid - transaction id;
943 * split - entry parameter descriptor;
944 * btstack - traverse stack from xtSearch()
950 struct inode *ip, struct xtsplit * split, struct btstack * btstack)
953 struct metapage *smp;
954 xtpage_t *sp; /* split page */
955 struct metapage *rmp;
956 s64 rbn; /* new right page block number */
957 struct metapage *rcmp;
958 xtpage_t *rcp; /* right child page */
959 s64 rcbn; /* right child page block number */
960 int skip; /* index of entry of insertion */
961 int nextindex; /* next available entry index of p */
962 struct btframe *parent; /* parent page entry on traverse stack */
966 int nsplit; /* number of pages split */
967 struct pxdlist pxdlist;
970 struct xtlock *xtlck;
973 sp = XT_PAGE(ip, smp);
975 /* is inode xtree root extension/inline EA area free ? */
976 if ((sp->header.flag & BT_ROOT) && (!S_ISDIR(ip->i_mode)) &&
977 (le16_to_cpu(sp->header.maxentry) < XTROOTMAXSLOT) &&
978 (JFS_IP(ip)->mode2 & INLINEEA)) {
979 sp->header.maxentry = cpu_to_le16(XTROOTMAXSLOT);
980 JFS_IP(ip)->mode2 &= ~INLINEEA;
982 BT_MARK_DIRTY(smp, ip);
984 * acquire a transaction lock on the leaf page;
986 * action: xad insertion/extension;
989 /* if insert into middle, shift right remaining entries. */
991 nextindex = le16_to_cpu(sp->header.nextindex);
992 if (skip < nextindex)
993 memmove(&sp->xad[skip + 1], &sp->xad[skip],
994 (nextindex - skip) * sizeof(xad_t));
996 /* insert the new entry: mark the entry NEW */
997 xad = &sp->xad[skip];
998 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1001 /* advance next available entry index */
1002 sp->header.nextindex =
1003 cpu_to_le16(le16_to_cpu(sp->header.nextindex) + 1);
1005 /* Don't log it if there are no links to the file */
1006 if (!test_cflag(COMMIT_Nolink, ip)) {
1007 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1008 xtlck = (struct xtlock *) & tlck->lock;
1009 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1010 min(skip, (int)xtlck->lwm.offset) : skip;
1012 le16_to_cpu(sp->header.nextindex) -
1020 * allocate new index blocks to cover index page split(s)
1022 * allocation hint: ?
1024 if (split->pxdlist == NULL) {
1025 nsplit = btstack->nsplit;
1026 split->pxdlist = &pxdlist;
1027 pxdlist.maxnpxd = pxdlist.npxd = 0;
1028 pxd = &pxdlist.pxd[0];
1029 xlen = JFS_SBI(ip->i_sb)->nbperpage;
1030 for (; nsplit > 0; nsplit--, pxd++) {
1031 if ((rc = dbAlloc(ip, (s64) 0, (s64) xlen, &xaddr))
1033 PXDaddress(pxd, xaddr);
1034 PXDlength(pxd, xlen);
1041 /* undo allocation */
1049 * Split leaf page <sp> into <sp> and a new right page <rp>.
1051 * The split routines insert the new entry into the leaf page,
1052 * and acquire txLock as appropriate.
1053 * return <rp> pinned and its block number <rpbn>.
1055 rc = (sp->header.flag & BT_ROOT) ?
1056 xtSplitRoot(tid, ip, split, &rmp) :
1057 xtSplitPage(tid, ip, split, &rmp, &rbn);
1064 * propagate up the router entry for the leaf page just split
1066 * insert a router entry for the new page into the parent page,
1067 * propagate the insert/split up the tree by walking back the stack
1068 * of (bn of parent page, index of child page entry in parent page)
1069 * that were traversed during the search for the page that split.
1071 * the propagation of insert/split up the tree stops if the root
1072 * splits or the page inserted into doesn't have to split to hold
1075 * the parent entry for the split page remains the same, and
1076 * a new entry is inserted at its right with the first key and
1077 * block number of the new right page.
1079 * There are a maximum of 3 pages pinned at any time:
1080 * right child, left parent and right parent (when the parent splits)
1081 * to keep the child page pinned while working on the parent.
1082 * make sure that all pins are released at exit.
1084 while ((parent = BT_POP(btstack)) != NULL) {
1085 /* parent page specified by stack frame <parent> */
1087 /* keep current child pages <rcp> pinned */
1090 rcp = XT_PAGE(ip, rcmp);
1093 * insert router entry in parent for new right child page <rp>
1095 /* get/pin the parent page <sp> */
1096 XT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
1103 * The new key entry goes ONE AFTER the index of parent entry,
1104 * because the split was to the right.
1106 skip = parent->index + 1;
1109 * split or shift right remaining entries of the parent page
1111 nextindex = le16_to_cpu(sp->header.nextindex);
1113 * parent page is full - split the parent page
1115 if (nextindex == le16_to_cpu(sp->header.maxentry)) {
1116 /* init for parent page split */
1118 split->index = skip; /* index at insert */
1119 split->flag = XAD_NEW;
1120 split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
1121 split->len = JFS_SBI(ip->i_sb)->nbperpage;
1124 /* unpin previous right child page */
1127 /* The split routines insert the new entry,
1128 * and acquire txLock as appropriate.
1129 * return <rp> pinned and its block number <rpbn>.
1131 rc = (sp->header.flag & BT_ROOT) ?
1132 xtSplitRoot(tid, ip, split, &rmp) :
1133 xtSplitPage(tid, ip, split, &rmp, &rbn);
1140 /* keep new child page <rp> pinned */
1143 * parent page is not full - insert in parent page
1147 * insert router entry in parent for the right child
1148 * page from the first entry of the right child page:
1151 * acquire a transaction lock on the parent page;
1153 * action: router xad insertion;
1155 BT_MARK_DIRTY(smp, ip);
1158 * if insert into middle, shift right remaining entries
1160 if (skip < nextindex)
1161 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1163 skip) << L2XTSLOTSIZE);
1165 /* insert the router entry */
1166 xad = &sp->xad[skip];
1167 XT_PUTENTRY(xad, XAD_NEW,
1168 offsetXAD(&rcp->xad[XTENTRYSTART]),
1169 JFS_SBI(ip->i_sb)->nbperpage, rcbn);
1171 /* advance next available entry index. */
1172 sp->header.nextindex =
1173 cpu_to_le16(le16_to_cpu(sp->header.nextindex) +
1176 /* Don't log it if there are no links to the file */
1177 if (!test_cflag(COMMIT_Nolink, ip)) {
1178 tlck = txLock(tid, ip, smp,
1179 tlckXTREE | tlckGROW);
1180 xtlck = (struct xtlock *) & tlck->lock;
1181 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1182 min(skip, (int)xtlck->lwm.offset) : skip;
1184 le16_to_cpu(sp->header.nextindex) -
1188 /* unpin parent page */
1191 /* exit propagate up */
1196 /* unpin current right page */
1207 * split a full non-root page into
1208 * original/split/left page and new right page
1209 * i.e., the original/split page remains as left page.
1214 * struct xtsplit *split,
1215 * struct metapage **rmpp,
1219 * Pointer to page in which to insert or NULL on error.
1222 xtSplitPage(tid_t tid, struct inode *ip,
1223 struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
1226 struct metapage *smp;
1228 struct metapage *rmp;
1229 xtpage_t *rp; /* new right page allocated */
1230 s64 rbn; /* new right page block number */
1231 struct metapage *mp;
1234 int skip, maxentry, middle, righthalf, n;
1236 struct pxdlist *pxdlist;
1239 struct xtlock *sxtlck = NULL, *rxtlck = NULL;
1240 int quota_allocation = 0;
1241 int dlimit_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);
1261 /* Allocate blocks to dlimit. */
1262 if (DLIMIT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
1266 dlimit_allocation += lengthPXD(pxd);
1269 * allocate the new right page for the split
1271 rmp = get_metapage(ip, rbn, PSIZE, 1);
1277 jfs_info("xtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1279 BT_MARK_DIRTY(rmp, ip);
1284 rp = (xtpage_t *) rmp->data;
1285 rp->header.self = *pxd;
1286 rp->header.flag = sp->header.flag & BT_TYPE;
1287 rp->header.maxentry = sp->header.maxentry; /* little-endian */
1288 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1290 BT_MARK_DIRTY(smp, ip);
1291 /* Don't log it if there are no links to the file */
1292 if (!test_cflag(COMMIT_Nolink, ip)) {
1294 * acquire a transaction lock on the new right page;
1296 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1297 rxtlck = (struct xtlock *) & tlck->lock;
1298 rxtlck->lwm.offset = XTENTRYSTART;
1300 * acquire a transaction lock on the split page
1302 tlck = txLock(tid, ip, smp, tlckXTREE | tlckGROW);
1303 sxtlck = (struct xtlock *) & tlck->lock;
1307 * initialize/update sibling pointers of <sp> and <rp>
1309 nextbn = le64_to_cpu(sp->header.next);
1310 rp->header.next = cpu_to_le64(nextbn);
1311 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1312 sp->header.next = cpu_to_le64(rbn);
1314 skip = split->index;
1317 * sequential append at tail (after last entry of last page)
1319 * if splitting the last page on a level because of appending
1320 * a entry to it (skip is maxentry), it's likely that the access is
1321 * sequential. adding an empty page on the side of the level is less
1322 * work and can push the fill factor much higher than normal.
1323 * if we're wrong it's no big deal - we will do the split the right
1325 * (it may look like it's equally easy to do a similar hack for
1326 * reverse sorted data, that is, split the tree left, but it's not.
1329 if (nextbn == 0 && skip == le16_to_cpu(sp->header.maxentry)) {
1331 * acquire a transaction lock on the new/right page;
1333 * action: xad insertion;
1335 /* insert entry at the first entry of the new right page */
1336 xad = &rp->xad[XTENTRYSTART];
1337 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1340 rp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1342 if (!test_cflag(COMMIT_Nolink, ip)) {
1343 /* rxtlck->lwm.offset = XTENTRYSTART; */
1344 rxtlck->lwm.length = 1;
1350 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1355 * non-sequential insert (at possibly middle page)
1359 * update previous pointer of old next/right page of <sp>
1362 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1368 BT_MARK_DIRTY(mp, ip);
1370 * acquire a transaction lock on the next page;
1372 * action:sibling pointer update;
1374 if (!test_cflag(COMMIT_Nolink, ip))
1375 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
1377 p->header.prev = cpu_to_le64(rbn);
1379 /* sibling page may have been updated previously, or
1380 * it may be updated later;
1387 * split the data between the split and new/right pages
1389 maxentry = le16_to_cpu(sp->header.maxentry);
1390 middle = maxentry >> 1;
1391 righthalf = maxentry - middle;
1394 * skip index in old split/left page - insert into left page:
1396 if (skip <= middle) {
1397 /* move right half of split page to the new right page */
1398 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1399 righthalf << L2XTSLOTSIZE);
1401 /* shift right tail of left half to make room for new entry */
1403 memmove(&sp->xad[skip + 1], &sp->xad[skip],
1404 (middle - skip) << L2XTSLOTSIZE);
1406 /* insert new entry */
1407 xad = &sp->xad[skip];
1408 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1411 /* update page header */
1412 sp->header.nextindex = cpu_to_le16(middle + 1);
1413 if (!test_cflag(COMMIT_Nolink, ip)) {
1414 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1415 min(skip, (int)sxtlck->lwm.offset) : skip;
1418 rp->header.nextindex =
1419 cpu_to_le16(XTENTRYSTART + righthalf);
1422 * skip index in new right page - insert into right page:
1425 /* move left head of right half to right page */
1427 memmove(&rp->xad[XTENTRYSTART], &sp->xad[middle],
1430 /* insert new entry */
1433 XT_PUTENTRY(xad, split->flag, split->off, split->len,
1436 /* move right tail of right half to right page */
1437 if (skip < maxentry)
1438 memmove(&rp->xad[n + 1], &sp->xad[skip],
1439 (maxentry - skip) << L2XTSLOTSIZE);
1441 /* update page header */
1442 sp->header.nextindex = cpu_to_le16(middle);
1443 if (!test_cflag(COMMIT_Nolink, ip)) {
1444 sxtlck->lwm.offset = (sxtlck->lwm.offset) ?
1445 min(middle, (int)sxtlck->lwm.offset) : middle;
1448 rp->header.nextindex = cpu_to_le16(XTENTRYSTART +
1452 if (!test_cflag(COMMIT_Nolink, ip)) {
1453 sxtlck->lwm.length = le16_to_cpu(sp->header.nextindex) -
1456 /* rxtlck->lwm.offset = XTENTRYSTART; */
1457 rxtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1464 jfs_info("xtSplitPage: sp:0x%p rp:0x%p", sp, rp);
1469 /* Rollback dlimit allocation. */
1470 if (dlimit_allocation)
1471 DLIMIT_FREE_BLOCK(ip, dlimit_allocation);
1472 /* Rollback quota allocation. */
1473 if (quota_allocation)
1474 DQUOT_FREE_BLOCK(ip, quota_allocation);
1484 * split the full root page into
1485 * original/root/split page and new right page
1486 * i.e., root remains fixed in tree anchor (inode) and
1487 * the root is copied to a single new right child page
1488 * since root page << non-root page, and
1489 * the split root page contains a single entry for the
1490 * new right child page.
1495 * struct xtsplit *split,
1496 * struct metapage **rmpp)
1499 * Pointer to page in which to insert or NULL on error.
1502 xtSplitRoot(tid_t tid,
1503 struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1506 struct metapage *rmp;
1509 int skip, nextindex;
1512 struct pxdlist *pxdlist;
1514 struct xtlock *xtlck;
1516 sp = &JFS_IP(ip)->i_xtroot;
1518 INCREMENT(xtStat.split);
1521 * allocate a single (right) child page
1523 pxdlist = split->pxdlist;
1524 pxd = &pxdlist->pxd[pxdlist->npxd];
1526 rbn = addressPXD(pxd);
1527 rmp = get_metapage(ip, rbn, PSIZE, 1);
1531 /* Allocate blocks to quota. */
1532 if (DQUOT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
1533 release_metapage(rmp);
1536 /* Allocate blocks to dlimit. */
1537 if (DLIMIT_ALLOC_BLOCK(ip, lengthPXD(pxd))) {
1538 DQUOT_FREE_BLOCK(ip, lengthPXD(pxd));
1539 release_metapage(rmp);
1543 jfs_info("xtSplitRoot: ip:0x%p rmp:0x%p", ip, rmp);
1546 * acquire a transaction lock on the new right page;
1550 BT_MARK_DIRTY(rmp, ip);
1552 rp = (xtpage_t *) rmp->data;
1554 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1555 rp->header.self = *pxd;
1556 rp->header.nextindex = cpu_to_le16(XTENTRYSTART);
1557 rp->header.maxentry = cpu_to_le16(PSIZE >> L2XTSLOTSIZE);
1559 /* initialize sibling pointers */
1560 rp->header.next = 0;
1561 rp->header.prev = 0;
1564 * copy the in-line root page into new right page extent
1566 nextindex = le16_to_cpu(sp->header.maxentry);
1567 memmove(&rp->xad[XTENTRYSTART], &sp->xad[XTENTRYSTART],
1568 (nextindex - XTENTRYSTART) << L2XTSLOTSIZE);
1571 * insert the new entry into the new right/child page
1572 * (skip index in the new right page will not change)
1574 skip = split->index;
1575 /* if insert into middle, shift right remaining entries */
1576 if (skip != nextindex)
1577 memmove(&rp->xad[skip + 1], &rp->xad[skip],
1578 (nextindex - skip) * sizeof(xad_t));
1580 xad = &rp->xad[skip];
1581 XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1583 /* update page header */
1584 rp->header.nextindex = cpu_to_le16(nextindex + 1);
1586 if (!test_cflag(COMMIT_Nolink, ip)) {
1587 tlck = txLock(tid, ip, rmp, tlckXTREE | tlckNEW);
1588 xtlck = (struct xtlock *) & tlck->lock;
1589 xtlck->lwm.offset = XTENTRYSTART;
1590 xtlck->lwm.length = le16_to_cpu(rp->header.nextindex) -
1597 * init root with the single entry for the new right page
1598 * set the 1st entry offset to 0, which force the left-most key
1599 * at any level of the tree to be less than any search key.
1602 * acquire a transaction lock on the root page (in-memory inode);
1604 * action: root split;
1606 BT_MARK_DIRTY(split->mp, ip);
1608 xad = &sp->xad[XTENTRYSTART];
1609 XT_PUTENTRY(xad, XAD_NEW, 0, JFS_SBI(ip->i_sb)->nbperpage, rbn);
1611 /* update page header of root */
1612 sp->header.flag &= ~BT_LEAF;
1613 sp->header.flag |= BT_INTERNAL;
1615 sp->header.nextindex = cpu_to_le16(XTENTRYSTART + 1);
1617 if (!test_cflag(COMMIT_Nolink, ip)) {
1618 tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1619 xtlck = (struct xtlock *) & tlck->lock;
1620 xtlck->lwm.offset = XTENTRYSTART;
1621 xtlck->lwm.length = 1;
1626 jfs_info("xtSplitRoot: sp:0x%p rp:0x%p", sp, rp);
1634 * function: extend in-place;
1636 * note: existing extent may or may not have been committed.
1637 * caller is responsible for pager buffer cache update, and
1638 * working block allocation map update;
1639 * update pmap: alloc whole extended extent;
1641 int xtExtend(tid_t tid, /* transaction id */
1642 struct inode *ip, s64 xoff, /* delta extent offset */
1643 s32 xlen, /* delta extent length */
1648 struct metapage *mp; /* meta-page buffer */
1649 xtpage_t *p; /* base B+-tree index page */
1651 int index, nextindex, len;
1652 struct btstack btstack; /* traverse stack */
1653 struct xtsplit split; /* split information */
1657 struct xtlock *xtlck = NULL;
1659 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1661 /* there must exist extent to be extended */
1662 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1665 /* retrieve search result */
1666 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1670 jfs_error(ip->i_sb, "xtExtend: xtSearch did not find extent");
1674 /* extension must be contiguous */
1675 xad = &p->xad[index];
1676 if ((offsetXAD(xad) + lengthXAD(xad)) != xoff) {
1678 jfs_error(ip->i_sb, "xtExtend: extension is not contiguous");
1683 * acquire a transaction lock on the leaf page;
1685 * action: xad insertion/extension;
1687 BT_MARK_DIRTY(mp, ip);
1688 if (!test_cflag(COMMIT_Nolink, ip)) {
1689 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1690 xtlck = (struct xtlock *) & tlck->lock;
1693 /* extend will overflow extent ? */
1694 xlen = lengthXAD(xad) + xlen;
1695 if ((len = xlen - MAXXLEN) <= 0)
1699 * extent overflow: insert entry for new extent
1702 xoff = offsetXAD(xad) + MAXXLEN;
1703 xaddr = addressXAD(xad) + MAXXLEN;
1704 nextindex = le16_to_cpu(p->header.nextindex);
1707 * if the leaf page is full, insert the new entry and
1708 * propagate up the router entry for the new page from split
1710 * The xtSplitUp() will insert the entry and unpin the leaf page.
1712 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1713 /* xtSpliUp() unpins leaf pages */
1715 split.index = index + 1;
1716 split.flag = XAD_NEW;
1717 split.off = xoff; /* split offset */
1720 split.pxdlist = NULL;
1721 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1724 /* get back old page */
1725 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1729 * if leaf root has been split, original root has been
1730 * copied to new child page, i.e., original entry now
1731 * resides on the new child page;
1733 if (p->header.flag & BT_INTERNAL) {
1734 ASSERT(p->header.nextindex ==
1735 cpu_to_le16(XTENTRYSTART + 1));
1736 xad = &p->xad[XTENTRYSTART];
1737 bn = addressXAD(xad);
1740 /* get new child page */
1741 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1745 BT_MARK_DIRTY(mp, ip);
1746 if (!test_cflag(COMMIT_Nolink, ip)) {
1747 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1748 xtlck = (struct xtlock *) & tlck->lock;
1753 * insert the new entry into the leaf page
1756 /* insert the new entry: mark the entry NEW */
1757 xad = &p->xad[index + 1];
1758 XT_PUTENTRY(xad, XAD_NEW, xoff, len, xaddr);
1760 /* advance next available entry index */
1761 p->header.nextindex =
1762 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1765 /* get back old entry */
1766 xad = &p->xad[index];
1773 XADlength(xad, xlen);
1774 if (!(xad->flag & XAD_NEW))
1775 xad->flag |= XAD_EXTENDED;
1777 if (!test_cflag(COMMIT_Nolink, ip)) {
1779 (xtlck->lwm.offset) ? min(index,
1780 (int)xtlck->lwm.offset) : index;
1782 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
1785 /* unpin the leaf page */
1795 * function: split existing 'tail' extent
1796 * (split offset >= start offset of tail extent), and
1797 * relocate and extend the split tail half;
1799 * note: existing extent may or may not have been committed.
1800 * caller is responsible for pager buffer cache update, and
1801 * working block allocation map update;
1802 * update pmap: free old split tail extent, alloc new extent;
1804 int xtTailgate(tid_t tid, /* transaction id */
1805 struct inode *ip, s64 xoff, /* split/new extent offset */
1806 s32 xlen, /* new extent length */
1807 s64 xaddr, /* new extent address */
1812 struct metapage *mp; /* meta-page buffer */
1813 xtpage_t *p; /* base B+-tree index page */
1815 int index, nextindex, llen, rlen;
1816 struct btstack btstack; /* traverse stack */
1817 struct xtsplit split; /* split information */
1820 struct xtlock *xtlck = 0;
1821 struct tlock *mtlck;
1822 struct maplock *pxdlock;
1825 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1826 (ulong)xoff, xlen, (ulong)xaddr);
1829 /* there must exist extent to be tailgated */
1830 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
1833 /* retrieve search result */
1834 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
1838 jfs_error(ip->i_sb, "xtTailgate: couldn't find extent");
1842 /* entry found must be last entry */
1843 nextindex = le16_to_cpu(p->header.nextindex);
1844 if (index != nextindex - 1) {
1847 "xtTailgate: the entry found is not the last entry");
1851 BT_MARK_DIRTY(mp, ip);
1853 * acquire tlock of the leaf page containing original entry
1855 if (!test_cflag(COMMIT_Nolink, ip)) {
1856 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
1857 xtlck = (struct xtlock *) & tlck->lock;
1860 /* completely replace extent ? */
1861 xad = &p->xad[index];
1863 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1864 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1866 if ((llen = xoff - offsetXAD(xad)) == 0)
1870 * partially replace extent: insert entry for new extent
1874 * if the leaf page is full, insert the new entry and
1875 * propagate up the router entry for the new page from split
1877 * The xtSplitUp() will insert the entry and unpin the leaf page.
1879 if (nextindex == le16_to_cpu(p->header.maxentry)) {
1880 /* xtSpliUp() unpins leaf pages */
1882 split.index = index + 1;
1883 split.flag = XAD_NEW;
1884 split.off = xoff; /* split offset */
1887 split.pxdlist = NULL;
1888 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1891 /* get back old page */
1892 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1896 * if leaf root has been split, original root has been
1897 * copied to new child page, i.e., original entry now
1898 * resides on the new child page;
1900 if (p->header.flag & BT_INTERNAL) {
1901 ASSERT(p->header.nextindex ==
1902 cpu_to_le16(XTENTRYSTART + 1));
1903 xad = &p->xad[XTENTRYSTART];
1904 bn = addressXAD(xad);
1907 /* get new child page */
1908 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
1912 BT_MARK_DIRTY(mp, ip);
1913 if (!test_cflag(COMMIT_Nolink, ip)) {
1914 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
1915 xtlck = (struct xtlock *) & tlck->lock;
1920 * insert the new entry into the leaf page
1923 /* insert the new entry: mark the entry NEW */
1924 xad = &p->xad[index + 1];
1925 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1927 /* advance next available entry index */
1928 p->header.nextindex =
1929 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
1932 /* get back old XAD */
1933 xad = &p->xad[index];
1936 * truncate/relocate old extent at split offset
1939 /* update dmap for old/committed/truncated extent */
1940 rlen = lengthXAD(xad) - llen;
1941 if (!(xad->flag & XAD_NEW)) {
1942 /* free from PWMAP at commit */
1943 if (!test_cflag(COMMIT_Nolink, ip)) {
1944 mtlck = txMaplock(tid, ip, tlckMAP);
1945 pxdlock = (struct maplock *) & mtlck->lock;
1946 pxdlock->flag = mlckFREEPXD;
1947 PXDaddress(&pxdlock->pxd, addressXAD(xad) + llen);
1948 PXDlength(&pxdlock->pxd, rlen);
1952 /* free from WMAP */
1953 dbFree(ip, addressXAD(xad) + llen, (s64) rlen);
1957 XADlength(xad, llen);
1960 XT_PUTENTRY(xad, XAD_NEW, xoff, xlen, xaddr);
1962 if (!test_cflag(COMMIT_Nolink, ip)) {
1963 xtlck->lwm.offset = (xtlck->lwm.offset) ?
1964 min(index, (int)xtlck->lwm.offset) : index;
1965 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
1969 /* unpin the leaf page */
1974 #endif /* _NOTYET */
1979 * function: update XAD;
1981 * update extent for allocated_but_not_recorded or
1982 * compressed extent;
1986 * logical extent of the specified XAD must be completely
1987 * contained by an existing XAD;
1989 int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1993 struct metapage *mp; /* meta-page buffer */
1994 xtpage_t *p; /* base B+-tree index page */
1996 int index0, index, newindex, nextindex;
1997 struct btstack btstack; /* traverse stack */
1998 struct xtsplit split; /* split information */
1999 xad_t *xad, *lxad, *rxad;
2002 int nxlen, xlen, lxlen, rxlen;
2005 struct xtlock *xtlck = NULL;
2008 /* there must exist extent to be tailgated */
2009 nxoff = offsetXAD(nxad);
2010 nxlen = lengthXAD(nxad);
2011 nxaddr = addressXAD(nxad);
2013 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2016 /* retrieve search result */
2017 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2021 jfs_error(ip->i_sb, "xtUpdate: Could not find extent");
2025 BT_MARK_DIRTY(mp, ip);
2027 * acquire tlock of the leaf page containing original entry
2029 if (!test_cflag(COMMIT_Nolink, ip)) {
2030 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2031 xtlck = (struct xtlock *) & tlck->lock;
2034 xad = &p->xad[index0];
2036 xoff = offsetXAD(xad);
2037 xlen = lengthXAD(xad);
2038 xaddr = addressXAD(xad);
2040 /* nXAD must be completely contained within XAD */
2041 if ((xoff > nxoff) ||
2042 (nxoff + nxlen > xoff + xlen)) {
2045 "xtUpdate: nXAD in not completely contained within XAD");
2050 newindex = index + 1;
2051 nextindex = le16_to_cpu(p->header.nextindex);
2053 #ifdef _JFS_WIP_NOCOALESCE
2058 * replace XAD with nXAD
2060 replace: /* (nxoff == xoff) */
2061 if (nxlen == xlen) {
2062 /* replace XAD with nXAD:recorded */
2064 xad->flag = xflag & ~XAD_NOTRECORDED;
2067 } else /* (nxlen < xlen) */
2069 #endif /* _JFS_WIP_NOCOALESCE */
2071 /* #ifdef _JFS_WIP_COALESCE */
2076 * coalesce with left XAD
2078 //coalesceLeft: /* (xoff == nxoff) */
2079 /* is XAD first entry of page ? */
2080 if (index == XTENTRYSTART)
2083 /* is nXAD logically and physically contiguous with lXAD ? */
2084 lxad = &p->xad[index - 1];
2085 lxlen = lengthXAD(lxad);
2086 if (!(lxad->flag & XAD_NOTRECORDED) &&
2087 (nxoff == offsetXAD(lxad) + lxlen) &&
2088 (nxaddr == addressXAD(lxad) + lxlen) &&
2089 (lxlen + nxlen < MAXXLEN)) {
2090 /* extend right lXAD */
2092 XADlength(lxad, lxlen + nxlen);
2094 /* If we just merged two extents together, need to make sure the
2095 * right extent gets logged. If the left one is marked XAD_NEW,
2096 * then we know it will be logged. Otherwise, mark as
2099 if (!(lxad->flag & XAD_NEW))
2100 lxad->flag |= XAD_EXTENDED;
2104 XADoffset(xad, xoff + nxlen);
2105 XADlength(xad, xlen - nxlen);
2106 XADaddress(xad, xaddr + nxlen);
2108 } else { /* (xlen == nxlen) */
2111 if (index < nextindex - 1)
2112 memmove(&p->xad[index], &p->xad[index + 1],
2113 (nextindex - index -
2114 1) << L2XTSLOTSIZE);
2116 p->header.nextindex =
2117 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2121 newindex = index + 1;
2122 nextindex = le16_to_cpu(p->header.nextindex);
2123 xoff = nxoff = offsetXAD(lxad);
2124 xlen = nxlen = lxlen + nxlen;
2125 xaddr = nxaddr = addressXAD(lxad);
2131 * replace XAD with nXAD
2133 replace: /* (nxoff == xoff) */
2134 if (nxlen == xlen) {
2135 /* replace XAD with nXAD:recorded */
2137 xad->flag = xflag & ~XAD_NOTRECORDED;
2140 } else /* (nxlen < xlen) */
2144 * coalesce with right XAD
2146 coalesceRight: /* (xoff <= nxoff) */
2147 /* is XAD last entry of page ? */
2148 if (newindex == nextindex) {
2154 /* is nXAD logically and physically contiguous with rXAD ? */
2155 rxad = &p->xad[index + 1];
2156 rxlen = lengthXAD(rxad);
2157 if (!(rxad->flag & XAD_NOTRECORDED) &&
2158 (nxoff + nxlen == offsetXAD(rxad)) &&
2159 (nxaddr + nxlen == addressXAD(rxad)) &&
2160 (rxlen + nxlen < MAXXLEN)) {
2161 /* extend left rXAD */
2162 XADoffset(rxad, nxoff);
2163 XADlength(rxad, rxlen + nxlen);
2164 XADaddress(rxad, nxaddr);
2166 /* If we just merged two extents together, need to make sure
2167 * the left extent gets logged. If the right one is marked
2168 * XAD_NEW, then we know it will be logged. Otherwise, mark as
2171 if (!(rxad->flag & XAD_NEW))
2172 rxad->flag |= XAD_EXTENDED;
2176 XADlength(xad, xlen - nxlen);
2177 else { /* (xlen == nxlen) */
2180 memmove(&p->xad[index], &p->xad[index + 1],
2181 (nextindex - index - 1) << L2XTSLOTSIZE);
2183 p->header.nextindex =
2184 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2189 } else if (xoff == nxoff)
2192 if (xoff >= nxoff) {
2194 jfs_error(ip->i_sb, "xtUpdate: xoff >= nxoff");
2197 /* #endif _JFS_WIP_COALESCE */
2200 * split XAD into (lXAD, nXAD):
2203 * --|----------XAD----------|--
2206 updateRight: /* (xoff < nxoff) */
2207 /* truncate old XAD as lXAD:not_recorded */
2208 xad = &p->xad[index];
2209 XADlength(xad, nxoff - xoff);
2211 /* insert nXAD:recorded */
2212 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2214 /* xtSpliUp() unpins leaf pages */
2216 split.index = newindex;
2217 split.flag = xflag & ~XAD_NOTRECORDED;
2220 split.addr = nxaddr;
2221 split.pxdlist = NULL;
2222 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2225 /* get back old page */
2226 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2230 * if leaf root has been split, original root has been
2231 * copied to new child page, i.e., original entry now
2232 * resides on the new child page;
2234 if (p->header.flag & BT_INTERNAL) {
2235 ASSERT(p->header.nextindex ==
2236 cpu_to_le16(XTENTRYSTART + 1));
2237 xad = &p->xad[XTENTRYSTART];
2238 bn = addressXAD(xad);
2241 /* get new child page */
2242 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2246 BT_MARK_DIRTY(mp, ip);
2247 if (!test_cflag(COMMIT_Nolink, ip)) {
2248 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2249 xtlck = (struct xtlock *) & tlck->lock;
2252 /* is nXAD on new page ? */
2254 (le16_to_cpu(p->header.maxentry) >> 1)) {
2257 le16_to_cpu(p->header.nextindex) +
2263 /* if insert into middle, shift right remaining entries */
2264 if (newindex < nextindex)
2265 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2266 (nextindex - newindex) << L2XTSLOTSIZE);
2268 /* insert the entry */
2269 xad = &p->xad[newindex];
2271 xad->flag = xflag & ~XAD_NOTRECORDED;
2273 /* advance next available entry index. */
2274 p->header.nextindex =
2275 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2279 * does nXAD force 3-way split ?
2282 * --|----------XAD-------------|--
2283 * |-lXAD-| |-rXAD -|
2285 if (nxoff + nxlen == xoff + xlen)
2288 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2290 /* close out old page */
2291 if (!test_cflag(COMMIT_Nolink, ip)) {
2292 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2293 min(index0, (int)xtlck->lwm.offset) : index0;
2295 le16_to_cpu(p->header.nextindex) -
2299 bn = le64_to_cpu(p->header.next);
2302 /* get new right page */
2303 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2307 BT_MARK_DIRTY(mp, ip);
2308 if (!test_cflag(COMMIT_Nolink, ip)) {
2309 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2310 xtlck = (struct xtlock *) & tlck->lock;
2313 index0 = index = newindex;
2317 newindex = index + 1;
2318 nextindex = le16_to_cpu(p->header.nextindex);
2319 xlen = xlen - (nxoff - xoff);
2323 /* recompute split pages */
2324 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2327 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2330 /* retrieve search result */
2331 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index0);
2335 jfs_error(ip->i_sb, "xtUpdate: xtSearch failed");
2339 if (index0 != index) {
2342 "xtUpdate: unexpected value of index");
2348 * split XAD into (nXAD, rXAD)
2351 * --|----------XAD----------|--
2354 updateLeft: /* (nxoff == xoff) && (nxlen < xlen) */
2355 /* update old XAD with nXAD:recorded */
2356 xad = &p->xad[index];
2358 xad->flag = xflag & ~XAD_NOTRECORDED;
2360 /* insert rXAD:not_recorded */
2361 xoff = xoff + nxlen;
2362 xlen = xlen - nxlen;
2363 xaddr = xaddr + nxlen;
2364 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2366 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2368 /* xtSpliUp() unpins leaf pages */
2370 split.index = newindex;
2375 split.pxdlist = NULL;
2376 if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
2379 /* get back old page */
2380 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2385 * if leaf root has been split, original root has been
2386 * copied to new child page, i.e., original entry now
2387 * resides on the new child page;
2389 if (p->header.flag & BT_INTERNAL) {
2390 ASSERT(p->header.nextindex ==
2391 cpu_to_le16(XTENTRYSTART + 1));
2392 xad = &p->xad[XTENTRYSTART];
2393 bn = addressXAD(xad);
2396 /* get new child page */
2397 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2401 BT_MARK_DIRTY(mp, ip);
2402 if (!test_cflag(COMMIT_Nolink, ip)) {
2403 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
2404 xtlck = (struct xtlock *) & tlck->lock;
2408 /* if insert into middle, shift right remaining entries */
2409 if (newindex < nextindex)
2410 memmove(&p->xad[newindex + 1], &p->xad[newindex],
2411 (nextindex - newindex) << L2XTSLOTSIZE);
2413 /* insert the entry */
2414 xad = &p->xad[newindex];
2415 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2417 /* advance next available entry index. */
2418 p->header.nextindex =
2419 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2423 if (!test_cflag(COMMIT_Nolink, ip)) {
2424 xtlck->lwm.offset = (xtlck->lwm.offset) ?
2425 min(index0, (int)xtlck->lwm.offset) : index0;
2426 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2430 /* unpin the leaf page */
2440 * function: grow in append mode from contiguous region specified ;
2443 * tid - transaction id;
2445 * xflag - extent flag:
2446 * xoff - extent offset;
2447 * maxblocks - max extent length;
2448 * xlen - extent length (in/out);
2449 * xaddrp - extent address pointer (in/out):
2454 int xtAppend(tid_t tid, /* transaction id */
2455 struct inode *ip, int xflag, s64 xoff, s32 maxblocks,
2456 s32 * xlenp, /* (in/out) */
2457 s64 * xaddrp, /* (in/out) */
2461 struct metapage *mp; /* meta-page buffer */
2462 xtpage_t *p; /* base B+-tree index page */
2464 int index, nextindex;
2465 struct btstack btstack; /* traverse stack */
2466 struct xtsplit split; /* split information */
2470 struct xtlock *xtlck;
2471 int nsplit, nblocks, xlen;
2472 struct pxdlist pxdlist;
2478 jfs_info("xtAppend: xoff:0x%lx maxblocks:%d xlen:%d xaddr:0x%lx",
2479 (ulong) xoff, maxblocks, xlen, (ulong) xaddr);
2482 * search for the entry location at which to insert:
2484 * xtFastSearch() and xtSearch() both returns (leaf page
2485 * pinned, index at which to insert).
2486 * n.b. xtSearch() may return index of maxentry of
2489 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
2492 /* retrieve search result */
2493 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2501 xlen = min(xlen, (int)(next - xoff));
2504 * insert entry for new extent
2509 * if the leaf page is full, split the page and
2510 * propagate up the router entry for the new page from split
2512 * The xtSplitUp() will insert the entry and unpin the leaf page.
2514 nextindex = le16_to_cpu(p->header.nextindex);
2515 if (nextindex < le16_to_cpu(p->header.maxentry))
2519 * allocate new index blocks to cover index page split(s)
2521 nsplit = btstack.nsplit;
2522 split.pxdlist = &pxdlist;
2523 pxdlist.maxnpxd = pxdlist.npxd = 0;
2524 pxd = &pxdlist.pxd[0];
2525 nblocks = JFS_SBI(ip->i_sb)->nbperpage;
2526 for (; nsplit > 0; nsplit--, pxd++, xaddr += nblocks, maxblocks -= nblocks) {
2527 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) nblocks)) == 0) {
2528 PXDaddress(pxd, xaddr);
2529 PXDlength(pxd, nblocks);
2536 /* undo allocation */
2541 xlen = min(xlen, maxblocks);
2544 * allocate data extent requested
2546 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2550 split.index = index;
2555 if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2556 /* undo data extent allocation */
2557 dbFree(ip, *xaddrp, (s64) * xlenp);
2567 * insert the new entry into the leaf page
2571 * allocate data extent requested
2573 if ((rc = dbAllocBottomUp(ip, xaddr, (s64) xlen)))
2576 BT_MARK_DIRTY(mp, ip);
2578 * acquire a transaction lock on the leaf page;
2580 * action: xad insertion/extension;
2582 tlck = txLock(tid, ip, mp, tlckXTREE | tlckGROW);
2583 xtlck = (struct xtlock *) & tlck->lock;
2585 /* insert the new entry: mark the entry NEW */
2586 xad = &p->xad[index];
2587 XT_PUTENTRY(xad, xflag, xoff, xlen, xaddr);
2589 /* advance next available entry index */
2590 p->header.nextindex =
2591 cpu_to_le16(le16_to_cpu(p->header.nextindex) + 1);
2594 (xtlck->lwm.offset) ? min(index,(int) xtlck->lwm.offset) : index;
2595 xtlck->lwm.length = le16_to_cpu(p->header.nextindex) -
2602 /* unpin the leaf page */
2607 #ifdef _STILL_TO_PORT
2609 /* - TBD for defragmentaion/reorganization -
2614 * delete the entry with the specified key.
2616 * N.B.: whole extent of the entry is assumed to be deleted.
2621 * ENOENT: if the entry is not found.
2625 int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2628 struct btstack btstack;
2631 struct metapage *mp;
2633 int index, nextindex;
2635 struct xtlock *xtlck;
2638 * find the matching entry; xtSearch() pins the page
2640 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2643 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2645 /* unpin the leaf page */
2651 * delete the entry from the leaf page
2653 nextindex = le16_to_cpu(p->header.nextindex);
2654 p->header.nextindex =
2655 cpu_to_le16(le16_to_cpu(p->header.nextindex) - 1);
2658 * if the leaf page bocome empty, free the page
2660 if (p->header.nextindex == cpu_to_le16(XTENTRYSTART))
2661 return (xtDeleteUp(tid, ip, mp, p, &btstack));
2663 BT_MARK_DIRTY(mp, ip);
2665 * acquire a transaction lock on the leaf page;
2667 * action:xad deletion;
2669 tlck = txLock(tid, ip, mp, tlckXTREE);
2670 xtlck = (struct xtlock *) & tlck->lock;
2672 (xtlck->lwm.offset) ? min(index, xtlck->lwm.offset) : index;
2674 /* if delete from middle, shift left/compact the remaining entries */
2675 if (index < nextindex - 1)
2676 memmove(&p->xad[index], &p->xad[index + 1],
2677 (nextindex - index - 1) * sizeof(xad_t));
2685 /* - TBD for defragmentaion/reorganization -
2690 * free empty pages as propagating deletion up the tree
2697 xtDeleteUp(tid_t tid, struct inode *ip,
2698 struct metapage * fmp, xtpage_t * fp, struct btstack * btstack)
2701 struct metapage *mp;
2703 int index, nextindex;
2706 struct btframe *parent;
2708 struct xtlock *xtlck;
2711 * keep root leaf page which has become empty
2713 if (fp->header.flag & BT_ROOT) {
2714 /* keep the root page */
2715 fp->header.flag &= ~BT_INTERNAL;
2716 fp->header.flag |= BT_LEAF;
2717 fp->header.nextindex = cpu_to_le16(XTENTRYSTART);
2719 /* XT_PUTPAGE(fmp); */
2725 * free non-root leaf page
2727 if ((rc = xtRelink(tid, ip, fp))) {
2732 xaddr = addressPXD(&fp->header.self);
2733 xlen = lengthPXD(&fp->header.self);
2734 /* free the page extent */
2735 dbFree(ip, xaddr, (s64) xlen);
2737 /* free the buffer page */
2738 discard_metapage(fmp);
2741 * propagate page deletion up the index tree
2743 * If the delete from the parent page makes it empty,
2744 * continue all the way up the tree.
2745 * stop if the root page is reached (which is never deleted) or
2746 * if the entry deletion does not empty the page.
2748 while ((parent = BT_POP(btstack)) != NULL) {
2749 /* get/pin the parent page <sp> */
2750 XT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2754 index = parent->index;
2756 /* delete the entry for the freed child page from parent.
2758 nextindex = le16_to_cpu(p->header.nextindex);
2761 * the parent has the single entry being deleted:
2762 * free the parent page which has become empty.
2764 if (nextindex == 1) {
2765 if (p->header.flag & BT_ROOT) {
2766 /* keep the root page */
2767 p->header.flag &= ~BT_INTERNAL;
2768 p->header.flag |= BT_LEAF;
2769 p->header.nextindex =
2770 cpu_to_le16(XTENTRYSTART);
2772 /* XT_PUTPAGE(mp); */
2776 /* free the parent page */
2777 if ((rc = xtRelink(tid, ip, p)))
2780 xaddr = addressPXD(&p->header.self);
2781 /* free the page extent */
2783 (s64) JFS_SBI(ip->i_sb)->nbperpage);
2785 /* unpin/free the buffer page */
2786 discard_metapage(mp);
2793 * the parent has other entries remaining:
2794 * delete the router entry from the parent page.
2797 BT_MARK_DIRTY(mp, ip);
2799 * acquire a transaction lock on the leaf page;
2801 * action:xad deletion;
2803 tlck = txLock(tid, ip, mp, tlckXTREE);
2804 xtlck = (struct xtlock *) & tlck->lock;
2806 (xtlck->lwm.offset) ? min(index,
2810 /* if delete from middle,
2811 * shift left/compact the remaining entries in the page
2813 if (index < nextindex - 1)
2814 memmove(&p->xad[index], &p->xad[index + 1],
2815 (nextindex - index -
2816 1) << L2XTSLOTSIZE);
2818 p->header.nextindex =
2819 cpu_to_le16(le16_to_cpu(p->header.nextindex) -
2821 jfs_info("xtDeleteUp(entry): 0x%lx[%d]",
2822 (ulong) parent->bn, index);
2825 /* unpin the parent page */
2828 /* exit propagation up */
2837 * NAME: xtRelocate()
2839 * FUNCTION: relocate xtpage or data extent of regular file;
2840 * This function is mainly used by defragfs utility.
2842 * NOTE: This routine does not have the logic to handle
2843 * uncommitted allocated extent. The caller should call
2844 * txCommit() to commit all the allocation before call
2848 xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2849 s64 nxaddr, /* new xaddr */
2851 { /* extent type: XTPAGE or DATAEXT */
2853 struct tblock *tblk;
2855 struct xtlock *xtlck;
2856 struct metapage *mp, *pmp, *lmp, *rmp; /* meta-page buffer */
2857 xtpage_t *p, *pp, *rp, *lp; /* base B+-tree index page */
2862 s64 oxaddr, sxaddr, dxaddr, nextbn, prevbn;
2864 s64 offset, nbytes, nbrd, pno;
2865 int nb, npages, nblks;
2869 struct pxd_lock *pxdlock;
2870 struct btstack btstack; /* traverse stack */
2872 xtype = xtype & EXTENT_TYPE;
2874 xoff = offsetXAD(oxad);
2875 oxaddr = addressXAD(oxad);
2876 xlen = lengthXAD(oxad);
2878 /* validate extent offset */
2879 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2880 if (offset >= ip->i_size)
2881 return -ESTALE; /* stale extent */
2883 jfs_info("xtRelocate: xtype:%d xoff:0x%lx xlen:0x%x xaddr:0x%lx:0x%lx",
2884 xtype, (ulong) xoff, xlen, (ulong) oxaddr, (ulong) nxaddr);
2887 * 1. get and validate the parent xtpage/xad entry
2888 * covering the source extent to be relocated;
2890 if (xtype == DATAEXT) {
2891 /* search in leaf entry */
2892 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2896 /* retrieve search result */
2897 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2904 /* validate for exact match with a single entry */
2905 xad = &pp->xad[index];
2906 if (addressXAD(xad) != oxaddr || lengthXAD(xad) != xlen) {
2910 } else { /* (xtype == XTPAGE) */
2912 /* search in internal entry */
2913 rc = xtSearchNode(ip, oxad, &cmp, &btstack, 0);
2917 /* retrieve search result */
2918 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2925 /* xtSearchNode() validated for exact match with a single entry
2927 xad = &pp->xad[index];
2929 jfs_info("xtRelocate: parent xad entry validated.");
2932 * 2. relocate the extent
2934 if (xtype == DATAEXT) {
2935 /* if the extent is allocated-but-not-recorded
2936 * there is no real data to be moved in this extent,
2938 if (xad->flag & XAD_NOTRECORDED)
2941 /* release xtpage for cmRead()/xtLookup() */
2947 * copy target data pages to be relocated;
2949 * data extent must start at page boundary and
2950 * multiple of page size (except the last data extent);
2951 * read in each page of the source data extent into cbuf,
2952 * update the cbuf extent descriptor of the page to be
2953 * homeward bound to new dst data extent
2954 * copy the data from the old extent to new extent.
2955 * copy is essential for compressed files to avoid problems
2956 * that can arise if there was a change in compression
2958 * it is a good strategy because it may disrupt cache
2959 * policy to keep the pages in memory afterwards.
2961 offset = xoff << JFS_SBI(ip->i_sb)->l2bsize;
2962 assert((offset & CM_OFFSET) == 0);
2963 nbytes = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2964 pno = offset >> CM_L2BSIZE;
2965 npages = (nbytes + (CM_BSIZE - 1)) >> CM_L2BSIZE;
2967 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2968 (offset >> CM_L2BSIZE) + 1;
2973 /* process the request one cache buffer at a time */
2974 for (nbrd = 0; nbrd < nbytes; nbrd += nb,
2975 offset += nb, pno++, npages--) {
2976 /* compute page size */
2977 nb = min(nbytes - nbrd, CM_BSIZE);
2979 /* get the cache buffer of the page */
2980 if (rc = cmRead(ip, offset, npages, &cp))
2983 assert(addressPXD(&cp->cm_pxd) == sxaddr);
2984 assert(!cp->cm_modified);
2986 /* bind buffer with the new extent address */
2987 nblks = nb >> JFS_IP(ip->i_sb)->l2bsize;
2988 cmSetXD(ip, cp, pno, dxaddr, nblks);
2990 /* release the cbuf, mark it as modified */
2997 /* get back parent page */
2998 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
3001 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
3002 jfs_info("xtRelocate: target data extent relocated.");
3003 } else { /* (xtype == XTPAGE) */
3006 * read in the target xtpage from the source extent;
3008 XT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
3015 * read in sibling pages if any to update sibling pointers;
3018 if (p->header.next) {
3019 nextbn = le64_to_cpu(p->header.next);
3020 XT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
3029 if (p->header.prev) {
3030 prevbn = le64_to_cpu(p->header.prev);
3031 XT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
3041 /* at this point, all xtpages to be updated are in memory */
3044 * update sibling pointers of sibling xtpages if any;
3047 BT_MARK_DIRTY(lmp, ip);
3049 txLock(tid, ip, lmp, tlckXTREE | tlckRELINK);
3050 lp->header.next = cpu_to_le64(nxaddr);
3055 BT_MARK_DIRTY(rmp, ip);
3057 txLock(tid, ip, rmp, tlckXTREE | tlckRELINK);
3058 rp->header.prev = cpu_to_le64(nxaddr);
3063 * update the target xtpage to be relocated
3065 * update the self address of the target page
3066 * and write to destination extent;
3067 * redo image covers the whole xtpage since it is new page
3068 * to the destination extent;
3069 * update of bmap for the free of source extent
3070 * of the target xtpage itself:
3071 * update of bmap for the allocation of destination extent
3072 * of the target xtpage itself:
3073 * update of bmap for the extents covered by xad entries in
3074 * the target xtpage is not necessary since they are not
3076 * if not committed before this relocation,
3077 * target page may contain XAD_NEW entries which must
3078 * be scanned for bmap update (logredo() always
3079 * scan xtpage REDOPAGE image for bmap update);
3080 * if committed before this relocation (tlckRELOCATE),
3081 * scan may be skipped by commit() and logredo();
3083 BT_MARK_DIRTY(mp, ip);
3084 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
3085 tlck = txLock(tid, ip, mp, tlckXTREE | tlckNEW);
3086 xtlck = (struct xtlock *) & tlck->lock;
3088 /* update the self address in the xtpage header */
3089 pxd = &p->header.self;
3090 PXDaddress(pxd, nxaddr);
3092 /* linelock for the after image of the whole page */
3094 le16_to_cpu(p->header.nextindex) - xtlck->lwm.offset;
3096 /* update the buffer extent descriptor of target xtpage */
3097 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
3098 bmSetXD(mp, nxaddr, xsize);
3100 /* unpin the target page to new homeward bound */
3102 jfs_info("xtRelocate: target xtpage relocated.");
3106 * 3. acquire maplock for the source extent to be freed;
3108 * acquire a maplock saving the src relocated extent address;
3109 * to free of the extent at commit time;
3112 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
3113 * free PXD of the source data extent (logredo() will update
3114 * bmap for free of source data extent), and update bmap for
3115 * free of the source data extent;
3117 if (xtype == DATAEXT)
3118 tlck = txMaplock(tid, ip, tlckMAP);
3119 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
3120 * for the source xtpage (logredo() will init NoRedoPage
3121 * filter and will also update bmap for free of the source
3122 * xtpage), and update bmap for free of the source xtpage;
3123 * N.B. We use tlckMAP instead of tlkcXTREE because there
3124 * is no buffer associated with this lock since the buffer
3125 * has been redirected to the target location.
3127 else /* (xtype == XTPAGE) */
3128 tlck = txMaplock(tid, ip, tlckMAP | tlckRELOCATE);
3130 pxdlock = (struct pxd_lock *) & tlck->lock;
3131 pxdlock->flag = mlckFREEPXD;
3132 PXDaddress(&pxdlock->pxd, oxaddr);
3133 PXDlength(&pxdlock->pxd, xlen);
3137 * 4. update the parent xad entry for relocation;
3139 * acquire tlck for the parent entry with XAD_NEW as entry
3140 * update which will write LOG_REDOPAGE and update bmap for
3141 * allocation of XAD_NEW destination extent;
3143 jfs_info("xtRelocate: update parent xad entry.");
3144 BT_MARK_DIRTY(pmp, ip);
3145 tlck = txLock(tid, ip, pmp, tlckXTREE | tlckGROW);
3146 xtlck = (struct xtlock *) & tlck->lock;
3148 /* update the XAD with the new destination extent; */
3149 xad = &pp->xad[index];
3150 xad->flag |= XAD_NEW;
3151 XADaddress(xad, nxaddr);
3153 xtlck->lwm.offset = min(index, xtlck->lwm.offset);
3154 xtlck->lwm.length = le16_to_cpu(pp->header.nextindex) -
3157 /* unpin the parent xtpage */
3167 * function: search for the internal xad entry covering specified extent.
3168 * This function is mainly used by defragfs utility.
3172 * xad - extent to find;
3173 * cmpp - comparison result:
3174 * btstack - traverse stack;
3175 * flag - search process flag;
3178 * btstack contains (bn, index) of search path traversed to the entry.
3179 * *cmpp is set to result of comparison with the entry returned.
3180 * the page containing the entry is pinned at exit.
3182 static int xtSearchNode(struct inode *ip, xad_t * xad, /* required XAD entry */
3183 int *cmpp, struct btstack * btstack, int flag)
3188 int cmp = 1; /* init for empty page */
3189 s64 bn; /* block number */
3190 struct metapage *mp; /* meta-page buffer */
3191 xtpage_t *p; /* page */
3192 int base, index, lim;
3193 struct btframe *btsp;
3198 xoff = offsetXAD(xad);
3199 xlen = lengthXAD(xad);
3200 xaddr = addressXAD(xad);
3203 * search down tree from root:
3205 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
3206 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
3208 * if entry with search key K is not found
3209 * internal page search find the entry with largest key Ki
3210 * less than K which point to the child page to search;
3211 * leaf page search find the entry with smallest key Kj
3212 * greater than K so that the returned index is the position of
3213 * the entry to be shifted right for insertion of new entry.
3214 * for empty tree, search key is greater than any key of the tree.
3216 * by convention, root bn = 0.
3219 /* get/pin the page to search */
3220 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3223 if (p->header.flag & BT_LEAF) {
3228 lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3231 * binary search with search key K on the current page
3233 for (base = XTENTRYSTART; lim; lim >>= 1) {
3234 index = base + (lim >> 1);
3236 XT_CMP(cmp, xoff, &p->xad[index], t64);
3241 * verify for exact match;
3243 if (xaddr == addressXAD(&p->xad[index]) &&
3244 xoff == offsetXAD(&p->xad[index])) {
3247 /* save search result */
3248 btsp = btstack->top;
3250 btsp->index = index;
3256 /* descend/search its child page */
3267 * search miss - non-leaf page:
3269 * base is the smallest index with key (Kj) greater than
3270 * search key (K) and may be zero or maxentry index.
3271 * if base is non-zero, decrement base by one to get the parent
3272 * entry of the child page to search.
3274 index = base ? base - 1 : base;
3277 * go down to child page
3280 /* get the child page block number */
3281 bn = addressXAD(&p->xad[index]);
3283 /* unpin the parent page */
3293 * link around a freed page.
3302 static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * p)
3305 struct metapage *mp;
3309 nextbn = le64_to_cpu(p->header.next);
3310 prevbn = le64_to_cpu(p->header.prev);
3312 /* update prev pointer of the next page */
3314 XT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
3319 * acquire a transaction lock on the page;
3321 * action: update prev pointer;
3323 BT_MARK_DIRTY(mp, ip);
3324 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3326 /* the page may already have been tlock'd */
3328 p->header.prev = cpu_to_le64(prevbn);
3333 /* update next pointer of the previous page */
3335 XT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
3340 * acquire a transaction lock on the page;
3342 * action: update next pointer;
3344 BT_MARK_DIRTY(mp, ip);
3345 tlck = txLock(tid, ip, mp, tlckXTREE | tlckRELINK);
3347 /* the page may already have been tlock'd */
3349 p->header.next = le64_to_cpu(nextbn);
3356 #endif /* _STILL_TO_PORT */
3362 * initialize file root (inline in inode)
3364 void xtInitRoot(tid_t tid, struct inode *ip)
3369 * acquire a transaction lock on the root
3373 txLock(tid, ip, (struct metapage *) &JFS_IP(ip)->bxflag,
3374 tlckXTREE | tlckNEW);
3375 p = &JFS_IP(ip)->i_xtroot;
3377 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
3378 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3380 if (S_ISDIR(ip->i_mode))
3381 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT_DIR);
3383 p->header.maxentry = cpu_to_le16(XTROOTINITSLOT);
3393 * We can run into a deadlock truncating a file with a large number of
3394 * xtree pages (large fragmented file). A robust fix would entail a
3395 * reservation system where we would reserve a number of metadata pages
3396 * and tlocks which we would be guaranteed without a deadlock. Without
3397 * this, a partial fix is to limit number of metadata pages we will lock
3398 * in a single transaction. Currently we will truncate the file so that
3399 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3400 * will be responsible for ensuring that the current transaction gets
3401 * committed, and that subsequent transactions are created to truncate
3402 * the file further if needed.
3404 #define MAX_TRUNCATE_LEAVES 50
3410 * traverse for truncation logging backward bottom up;
3411 * terminate at the last extent entry at the current subtree
3412 * root page covering new down size.
3413 * truncation may occur within the last extent entry.
3419 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3425 * 1. truncate (non-COMMIT_NOLINK file)
3426 * by jfs_truncate() or jfs_open(O_TRUNC):
3428 * 2. truncate index table of directory when last entry removed
3429 * map update via tlock at commit time;
3431 * Call xtTruncate_pmap instead
3433 * 1. remove (free zero link count) on last reference release
3434 * (pmap has been freed at commit zero link count);
3435 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3437 * map update directly at truncation time;
3440 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3441 * else if (TRUNCATE)
3442 * must write LOG_NOREDOPAGE for deleted index page;
3444 * pages may already have been tlocked by anonymous transactions
3445 * during file growth (i.e., write) before truncation;
3447 * except last truncated entry, deleted entries remains as is
3448 * in the page (nextindex is updated) for other use
3449 * (e.g., log/update allocation map): this avoid copying the page
3450 * info but delay free of pages;
3453 s64 xtTruncate(tid_t tid, struct inode *ip, s64 newsize, int flag)
3457 struct metapage *mp;
3460 int index, nextindex;
3463 int xlen, len, freexlen;
3464 struct btstack btstack;
3465 struct btframe *parent;
3466 struct tblock *tblk = NULL;
3467 struct tlock *tlck = NULL;
3468 struct xtlock *xtlck = NULL;
3469 struct xdlistlock xadlock; /* maplock for COMMIT_WMAP */
3470 struct pxd_lock *pxdlock; /* maplock for COMMIT_WMAP */
3473 int locked_leaves = 0;
3475 /* save object truncation type */
3477 tblk = tid_to_tblock(tid);
3478 tblk->xflag |= flag;
3484 assert(flag != COMMIT_PMAP);
3486 if (flag == COMMIT_PWMAP)
3490 xadlock.flag = mlckFREEXADLIST;
3495 * if the newsize is not an integral number of pages,
3496 * the file between newsize and next page boundary will
3498 * if truncating into a file hole, it will cause
3499 * a full block to be allocated for the logical block.
3503 * release page blocks of truncated region <teof, eof>
3505 * free the data blocks from the leaf index blocks.
3506 * delete the parent index entries corresponding to
3507 * the freed child data/index blocks.
3508 * free the index blocks themselves which aren't needed
3509 * in new sized file.
3511 * index blocks are updated only if the blocks are to be
3512 * retained in the new sized file.
3513 * if type is PMAP, the data and index pages are NOT
3514 * freed, and the data and index blocks are NOT freed
3516 * (this will allow continued access of data/index of
3517 * temporary file (zerolink count file truncated to zero-length)).
3519 teof = (newsize + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
3520 JFS_SBI(ip->i_sb)->l2bsize;
3528 * root resides in the inode
3533 * first access of each page:
3536 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3540 /* process entries backward from last index */
3541 index = le16_to_cpu(p->header.nextindex) - 1;
3544 /* Since this is the rightmost page at this level, and we may have
3545 * already freed a page that was formerly to the right, let's make
3546 * sure that the next pointer is zero.
3548 if (p->header.next) {
3551 * Make sure this change to the header is logged.
3552 * If we really truncate this leaf, the flag
3553 * will be changed to tlckTRUNCATE
3555 tlck = txLock(tid, ip, mp, tlckXTREE|tlckGROW);
3556 BT_MARK_DIRTY(mp, ip);
3560 if (p->header.flag & BT_INTERNAL)
3568 /* does region covered by leaf page precede Teof ? */
3569 xad = &p->xad[index];
3570 xoff = offsetXAD(xad);
3571 xlen = lengthXAD(xad);
3572 if (teof >= xoff + xlen) {
3577 /* (re)acquire tlock of the leaf page */
3579 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
3581 * We need to limit the size of the transaction
3582 * to avoid exhausting pagecache & tlocks
3585 newsize = (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
3588 tlck = txLock(tid, ip, mp, tlckXTREE);
3589 tlck->type = tlckXTREE | tlckTRUNCATE;
3590 xtlck = (struct xtlock *) & tlck->lock;
3591 xtlck->hwm.offset = le16_to_cpu(p->header.nextindex) - 1;
3593 BT_MARK_DIRTY(mp, ip);
3596 * scan backward leaf page entries
3598 for (; index >= XTENTRYSTART; index--) {
3599 xad = &p->xad[index];
3600 xoff = offsetXAD(xad);
3601 xlen = lengthXAD(xad);
3602 xaddr = addressXAD(xad);
3605 * The "data" for a directory is indexed by the block
3606 * device's address space. This metadata must be invalidated
3609 if (S_ISDIR(ip->i_mode) && (teof == 0))
3610 invalidate_xad_metapages(ip, *xad);
3612 * entry beyond eof: continue scan of current page
3614 * ---|---=======------->
3623 * (xoff <= teof): last entry to be deleted from page;
3624 * If other entries remain in page: keep and update the page.
3628 * eof == entry_start: delete the entry
3630 * -------|=======------->
3637 if (index == XTENTRYSTART)
3643 * eof within the entry: truncate the entry.
3645 * -------===|===------->
3648 else if (teof < xoff + xlen) {
3649 /* update truncated entry */
3651 freexlen = xlen - len;
3652 XADlength(xad, len);
3654 /* save pxd of truncated extent in tlck */
3656 if (log) { /* COMMIT_PWMAP */
3657 xtlck->lwm.offset = (xtlck->lwm.offset) ?
3658 min(index, (int)xtlck->lwm.offset) : index;
3659 xtlck->lwm.length = index + 1 -
3661 xtlck->twm.offset = index;
3662 pxdlock = (struct pxd_lock *) & xtlck->pxdlock;
3663 pxdlock->flag = mlckFREEPXD;
3664 PXDaddress(&pxdlock->pxd, xaddr);
3665 PXDlength(&pxdlock->pxd, freexlen);
3667 /* free truncated extent */
3668 else { /* COMMIT_WMAP */
3670 pxdlock = (struct pxd_lock *) & xadlock;
3671 pxdlock->flag = mlckFREEPXD;
3672 PXDaddress(&pxdlock->pxd, xaddr);
3673 PXDlength(&pxdlock->pxd, freexlen);
3674 txFreeMap(ip, pxdlock, NULL, COMMIT_WMAP);
3676 /* reset map lock */
3677 xadlock.flag = mlckFREEXADLIST;
3680 /* current entry is new last entry; */
3681 nextindex = index + 1;
3686 * eof beyond the entry:
3688 * -------=======---|--->
3691 else { /* (xoff + xlen < teof) */
3693 nextindex = index + 1;
3696 if (nextindex < le16_to_cpu(p->header.nextindex)) {
3697 if (!log) { /* COMMIT_WAMP */
3698 xadlock.xdlist = &p->xad[nextindex];
3700 le16_to_cpu(p->header.nextindex) -
3702 txFreeMap(ip, (struct maplock *) & xadlock,
3705 p->header.nextindex = cpu_to_le16(nextindex);
3710 /* assert(freed == 0); */
3712 } /* end scan of leaf page entries */
3717 * leaf page become empty: free the page if type != PMAP
3719 if (log) { /* COMMIT_PWMAP */
3720 /* txCommit() with tlckFREE:
3721 * free data extents covered by leaf [XTENTRYSTART:hwm);
3722 * invalidate leaf if COMMIT_PWMAP;
3723 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3725 tlck->type = tlckXTREE | tlckFREE;
3726 } else { /* COMMIT_WAMP */
3728 /* free data extents covered by leaf */
3729 xadlock.xdlist = &p->xad[XTENTRYSTART];
3731 le16_to_cpu(p->header.nextindex) - XTENTRYSTART;
3732 txFreeMap(ip, (struct maplock *) & xadlock, NULL, COMMIT_WMAP);
3735 if (p->header.flag & BT_ROOT) {
3736 p->header.flag &= ~BT_INTERNAL;
3737 p->header.flag |= BT_LEAF;
3738 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3740 XT_PUTPAGE(mp); /* debug */
3743 if (log) { /* COMMIT_PWMAP */
3744 /* page will be invalidated at tx completion
3747 } else { /* COMMIT_WMAP */
3750 lid_to_tlock(mp->lid)->flag |= tlckFREELOCK;
3752 /* invalidate empty leaf page */
3753 discard_metapage(mp);
3758 * the leaf page become empty: delete the parent entry
3759 * for the leaf page if the parent page is to be kept
3760 * in the new sized file.
3764 * go back up to the parent page
3767 /* pop/restore parent entry for the current child page */
3768 if ((parent = BT_POP(&btstack)) == NULL)
3769 /* current page must have been root */
3772 /* get back the parent page */
3774 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3778 index = parent->index;
3781 * child page was not empty:
3784 /* has any entry deleted from parent ? */
3785 if (index < le16_to_cpu(p->header.nextindex) - 1) {
3786 /* (re)acquire tlock on the parent page */
3787 if (log) { /* COMMIT_PWMAP */
3788 /* txCommit() with tlckTRUNCATE:
3789 * free child extents covered by parent [);
3791 tlck = txLock(tid, ip, mp, tlckXTREE);
3792 xtlck = (struct xtlock *) & tlck->lock;
3793 if (!(tlck->type & tlckTRUNCATE)) {
3795 le16_to_cpu(p->header.
3798 tlckXTREE | tlckTRUNCATE;
3800 } else { /* COMMIT_WMAP */
3802 /* free child extents covered by parent */
3803 xadlock.xdlist = &p->xad[index + 1];
3805 le16_to_cpu(p->header.nextindex) -
3807 txFreeMap(ip, (struct maplock *) & xadlock,
3810 BT_MARK_DIRTY(mp, ip);
3812 p->header.nextindex = cpu_to_le16(index + 1);
3819 * child page was empty:
3821 nfreed += lengthXAD(&p->xad[index]);
3824 * During working map update, child page's tlock must be handled
3825 * before parent's. This is because the parent's tlock will cause
3826 * the child's disk space to be marked available in the wmap, so
3827 * it's important that the child page be released by that time.
3829 * ToDo: tlocks should be on doubly-linked list, so we can
3830 * quickly remove it and add it to the end.
3834 * Move parent page's tlock to the end of the tid's tlock list
3836 if (log && mp->lid && (tblk->last != mp->lid) &&
3837 lid_to_tlock(mp->lid)->tid) {
3838 lid_t lid = mp->lid;
3841 tlck = lid_to_tlock(lid);
3843 if (tblk->next == lid)
3844 tblk->next = tlck->next;
3846 for (prev = lid_to_tlock(tblk->next);
3848 prev = lid_to_tlock(prev->next)) {
3851 prev->next = tlck->next;
3853 lid_to_tlock(tblk->last)->next = lid;
3859 * parent page become empty: free the page
3861 if (index == XTENTRYSTART) {
3862 if (log) { /* COMMIT_PWMAP */
3863 /* txCommit() with tlckFREE:
3864 * free child extents covered by parent;
3865 * invalidate parent if COMMIT_PWMAP;
3867 tlck = txLock(tid, ip, mp, tlckXTREE);
3868 xtlck = (struct xtlock *) & tlck->lock;
3870 le16_to_cpu(p->header.nextindex) - 1;
3871 tlck->type = tlckXTREE | tlckFREE;
3872 } else { /* COMMIT_WMAP */
3874 /* free child extents covered by parent */
3875 xadlock.xdlist = &p->xad[XTENTRYSTART];
3877 le16_to_cpu(p->header.nextindex) -
3879 txFreeMap(ip, (struct maplock *) & xadlock, NULL,
3882 BT_MARK_DIRTY(mp, ip);
3884 if (p->header.flag & BT_ROOT) {
3885 p->header.flag &= ~BT_INTERNAL;
3886 p->header.flag |= BT_LEAF;
3887 p->header.nextindex = cpu_to_le16(XTENTRYSTART);
3888 if (le16_to_cpu(p->header.maxentry) == XTROOTMAXSLOT) {
3890 * Shrink root down to allow inline
3891 * EA (otherwise fsck complains)
3893 p->header.maxentry =
3894 cpu_to_le16(XTROOTINITSLOT);
3895 JFS_IP(ip)->mode2 |= INLINEEA;
3898 XT_PUTPAGE(mp); /* debug */
3901 if (log) { /* COMMIT_PWMAP */
3902 /* page will be invalidated at tx completion
3905 } else { /* COMMIT_WMAP */
3908 lid_to_tlock(mp->lid)->flag |=
3911 /* invalidate parent page */
3912 discard_metapage(mp);
3915 /* parent has become empty and freed:
3916 * go back up to its parent page
3923 * parent page still has entries for front region;
3926 /* try truncate region covered by preceding entry
3927 * (process backward)
3931 /* go back down to the child page corresponding
3938 * internal page: go down to child page of current entry
3941 /* save current parent entry for the child page */
3942 BT_PUSH(&btstack, bn, index);
3944 /* get child page */
3945 xad = &p->xad[index];
3946 bn = addressXAD(xad);
3949 * first access of each internal entry:
3951 /* release parent page */
3954 /* process the child page */
3959 * update file resource stat
3963 if (S_ISDIR(ip->i_mode) && !newsize)
3964 ip->i_size = 1; /* fsck hates zero-length directories */
3966 ip->i_size = newsize;
3968 /* update dlimit allocation to reflect freed blocks */
3969 DLIMIT_FREE_BLOCK(ip, nfreed);
3970 /* update quota allocation to reflect freed blocks */
3971 DQUOT_FREE_BLOCK(ip, nfreed);
3974 * free tlock of invalidated pages
3976 if (flag == COMMIT_WMAP)
3987 * Perform truncate to zero lenghth for deleted file, leaving the
3988 * the xtree and working map untouched. This allows the file to
3989 * be accessed via open file handles, while the delete of the file
3990 * is committed to disk.
3995 * s64 committed_size)
3997 * return: new committed size
4001 * To avoid deadlock by holding too many transaction locks, the
4002 * truncation may be broken up into multiple transactions.
4003 * The committed_size keeps track of part of the file has been
4004 * freed from the pmaps.
4006 s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
4009 struct btstack btstack;
4012 int locked_leaves = 0;
4013 struct metapage *mp;
4015 struct btframe *parent;
4017 struct tblock *tblk;
4018 struct tlock *tlck = NULL;
4022 struct xtlock *xtlck = NULL;
4024 /* save object truncation type */
4025 tblk = tid_to_tblock(tid);
4026 tblk->xflag |= COMMIT_PMAP;
4031 if (committed_size) {
4032 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
4033 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
4037 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
4042 "xtTruncate_pmap: did not find extent");
4049 * root resides in the inode
4054 * first access of each page:
4057 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4061 /* process entries backward from last index */
4062 index = le16_to_cpu(p->header.nextindex) - 1;
4064 if (p->header.flag & BT_INTERNAL)
4072 if (++locked_leaves > MAX_TRUNCATE_LEAVES) {
4074 * We need to limit the size of the transaction
4075 * to avoid exhausting pagecache & tlocks
4077 xad = &p->xad[index];
4078 xoff = offsetXAD(xad);
4079 xlen = lengthXAD(xad);
4081 return (xoff + xlen) << JFS_SBI(ip->i_sb)->l2bsize;
4083 tlck = txLock(tid, ip, mp, tlckXTREE);
4084 tlck->type = tlckXTREE | tlckFREE;
4085 xtlck = (struct xtlock *) & tlck->lock;
4086 xtlck->hwm.offset = index;
4092 * go back up to the parent page
4095 /* pop/restore parent entry for the current child page */
4096 if ((parent = BT_POP(&btstack)) == NULL)
4097 /* current page must have been root */
4100 /* get back the parent page */
4102 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
4106 index = parent->index;
4109 * parent page become empty: free the page
4111 if (index == XTENTRYSTART) {
4112 /* txCommit() with tlckFREE:
4113 * free child extents covered by parent;
4114 * invalidate parent if COMMIT_PWMAP;
4116 tlck = txLock(tid, ip, mp, tlckXTREE);
4117 xtlck = (struct xtlock *) & tlck->lock;
4119 le16_to_cpu(p->header.nextindex) - 1;
4120 tlck->type = tlckXTREE | tlckFREE;
4124 if (p->header.flag & BT_ROOT) {
4132 * parent page still has entries for front region;
4137 * internal page: go down to child page of current entry
4140 /* save current parent entry for the child page */
4141 BT_PUSH(&btstack, bn, index);
4143 /* get child page */
4144 xad = &p->xad[index];
4145 bn = addressXAD(xad);
4148 * first access of each internal entry:
4150 /* release parent page */
4153 /* process the child page */
4161 #ifdef CONFIG_JFS_STATISTICS
4162 int jfs_xtstat_read(char *buffer, char **start, off_t offset, int length,
4163 int *eof, void *data)
4168 len += sprintf(buffer,
4169 "JFS Xtree statistics\n"
4170 "====================\n"
4172 "fast searches = %d\n"
4179 *start = buffer + begin;