| blob | 31b34db4519ec9cabc2668211177c3c2554d64e0 |
1 /*
2 * Copyright (C) International Business Machines Corp., 2000-2005
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12 * the GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 /*
19 * jfs_xtree.c: extent allocation descriptor B+-tree manager
20 */
22 #include <linux/fs.h>
23 #include <linux/quotaops.h>
32 /*
33 * xtree local flag
34 */
35 #define XT_INSERT 0x00000001
37 /*
38 * xtree key/entry comparison: extent offset
39 *
40 * return:
41 * -1: k < start of extent
42 * 0: start_of_extent <= k <= end_of_extent
43 * 1: k > end_of_extent
44 */
45 #define XT_CMP(CMP, K, X, OFFSET64)\
46 {\
47 OFFSET64 = offsetXAD(X);\
48 (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
49 ((K) < OFFSET64) ? -1 : 0;\
50 }
52 /* write a xad entry */
53 #define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
54 {\
55 (XAD)->flag = (FLAG);\
56 XADoffset((XAD), (OFF));\
57 XADlength((XAD), (LEN));\
58 XADaddress((XAD), (ADDR));\
59 }
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)\
66 {\
67 BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
68 if (!(RC))\
69 {\
70 if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
71 (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
72 (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
73 {\
75 BT_PUTPAGE(MP);\
76 MP = NULL;\
77 RC = -EIO;\
78 }\
79 }\
80 }
82 /* for consistency */
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 */
90 s16 index;
91 u8 flag;
92 s64 off;
93 s64 addr;
96 };
99 /*
100 * statistics
101 */
102 #ifdef CONFIG_JFS_STATISTICS
104 uint search;
105 uint fastSearch;
106 uint split;
108 #endif
111 /*
112 * forward references
113 */
127 #ifdef _STILL_TO_PORT
138 /* External references */
140 /*
141 * debug control
142 */
143 /* #define _JFS_DEBUG_XTREE 1 */
146 /*
147 * xtLookup()
148 *
149 * function: map a single page into a physical extent;
150 */
153 {
157 s64 bn;
164 s64 xaddr;
170 /* is lookup offset beyond eof ? */
177 }
178 }
180 /*
181 * search for the xad entry covering the logical extent
182 */
183 //search:
187 }
189 /*
190 * compute the physical extent covering logical extent
191 *
192 * N.B. search may have failed (e.g., hole in sparse file),
193 * and returned the index of the next entry.
194 */
195 /* retrieve search result */
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;
201 */
206 }
208 /*
209 * lxd covered by xad
210 */
217 /* initialize new pxd */
220 /* a page must be fully covered by an xad */
223 out:
227 }
230 /*
231 * xtLookupList()
232 *
233 * function: map a single logical extent into a list of physical extent;
234 *
235 * parameter:
236 * struct inode *ip,
237 * struct lxdlist *lxdlist, lxd list (in)
238 * struct xadlist *xadlist, xad list (in/out)
239 * int flag)
240 *
241 * coverage of lxd by xad under assumption of
242 * . lxd's are ordered and disjoint.
243 * . xad's are ordered and disjoint.
244 *
245 * return:
246 * 0: success
247 *
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;
252 */
255 {
259 s64 bn;
284 /*
285 * search for the xad entry covering the logical extent
286 */
287 search:
294 /*
295 * compute the physical extent covering logical extent
296 *
297 * N.B. search may have failed (e.g., hole in sparse file),
298 * and returned the index of the next entry.
299 */
300 //map:
301 /* retrieve search result */
304 /* is xad on the next sibling page ? */
314 /* get next sibling page */
320 }
324 /*
325 * is lxd covered by xad ?
326 */
327 compare:
333 compare1:
337 /* (lstart <= xstart) */
339 /* lxd is NOT covered by xad */
341 /*
342 * get next lxd
343 */
346 lxd++;
354 /* compare with the current xad */
356 }
357 /* lxd is covered by xad */
360 /* initialize new pxd */
366 }
368 /* (xstart < lstart) */
369 compare2:
370 /* lxd is covered by xad */
372 /* initialize new pxd */
378 }
379 /* lxd is NOT covered by xad */
382 /*
383 * get next xad
384 *
385 * linear search next xad covering lxd on
386 * the current xad page, and then tree search
387 */
395 index++;
396 xad++;
398 /* compare with new xad */
400 }
401 }
403 /*
404 * lxd is covered by xad and a new pxd has been initialized
405 * (lstart <= xstart < lend) or (xstart < lstart < xend)
406 */
407 cover:
408 /* finalize pxd corresponding to current xad */
413 pxd++;
415 /*
416 * lxd is fully covered by xad
417 */
419 /*
420 * get next lxd
421 */
424 lxd++;
432 /*
433 * test for old xad covering new lxd
434 * (old xstart < new lstart)
435 */
437 }
438 /*
439 * lxd is partially covered by xad
440 */
443 /*
444 * get next xad
445 *
446 * linear search next xad covering lxd on
447 * the current xad page, and then next xad page search
448 */
458 /* get next sibling page */
466 index++;
467 xad++;
468 }
470 /*
471 * test for new xad covering old lxd
472 * (old lstart < new xstart)
473 */
475 }
477 mapend:
480 //out:
484 }
487 /*
488 * xtSearch()
489 *
490 * function: search for the xad entry covering specified offset.
491 *
492 * parameters:
493 * ip - file object;
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);
499 *
500 * returns:
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.
504 */
507 {
518 s64 t64;
527 /*
528 * search down tree from root:
529 *
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.
532 *
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.
540 *
541 * by convention, root bn = 0.
542 */
544 /* get/pin the page to search */
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;
554 */
555 //fastSearch:
566 }
568 /* stop sequential access heuristics */
572 /* try next sequential entry */
573 index++;
576 xad++;
582 }
584 /* miss: key falls between
585 * previous and this entry
586 */
590 }
592 /* (xoff >= t64 + lengthXAD(xad));
593 * matching entry may be further out:
594 * stop heuristic search
595 */
596 /* stop sequential access heuristics */
598 }
600 /* (index == p->header.nextindex);
601 * miss: key entry does not exist in
602 * the target leaf/tree
603 */
606 }
608 /*
609 * if hit, return index of the entry found, and
610 * if miss, where new entry with search key is
611 * to be inserted;
612 */
613 out:
614 /* compute number of pages to split */
618 nsplit++;
619 else
622 }
624 /* save search result */
630 /* update sequential access heuristics */
638 }
640 /* well, ... full search now */
641 binarySearch:
644 /*
645 * binary search with search key K on the current page
646 */
652 /*
653 * search hit
654 */
655 /* search hit - leaf page:
656 * return the entry found
657 */
661 /* compute number of pages to split */
665 nsplit++;
666 else
669 }
671 /* save search result */
677 /* init sequential access heuristics */
682 else
687 }
688 /* search hit - internal page:
689 * descend/search its child page
690 */
694 }
699 }
700 }
702 /*
703 * search miss
704 *
705 * base is the smallest index with key (Kj) greater than
706 * search key (K) and may be zero or maxentry index.
707 */
710 /*
711 * search miss - leaf page:
712 *
713 * return location of entry (base) where new entry with
714 * search key K is to be inserted.
715 */
719 /* compute number of pages to split */
723 nsplit++;
724 else
727 }
729 /* save search result */
735 /* init sequential access heuristics */
739 else
747 }
749 /*
750 * search miss - non-leaf page:
751 *
752 * if base is non-zero, decrement base by one to get the parent
753 * entry of the child page to search.
754 */
757 /*
758 * go down to child page
759 */
760 next:
761 /* update number of pages to split */
763 nsplit++;
764 else
767 /* push (bn, index) of the parent page/entry */
770 /* get the child page block number */
773 /* unpin the parent page */
775 }
776 }
778 /*
779 * xtInsert()
780 *
781 * function:
782 *
783 * parameter:
784 * tid - transaction id;
785 * ip - file object;
786 * xflag - extent flag (XAD_NOTRECORDED):
787 * xoff - extent offset;
788 * xlen - extent length;
789 * xaddrp - extent address pointer (in/out):
790 * if (*xaddrp)
791 * caller allocated data extent at *xaddrp;
792 * else
793 * allocate data extent and return its xaddr;
794 * flag -
795 *
796 * return:
797 */
801 {
806 s64 bn;
812 s64 next;
818 /*
819 * search for the entry location at which to insert:
820 *
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
824 * the full page.
825 */
829 /* retrieve search result */
832 /* This test must follow XT_GETSEARCH since mp must be valid if
833 * we branch to out: */
837 }
839 /*
840 * allocate data extent requested
841 *
842 * allocation hint: last xad
843 */
855 }
856 }
858 /*
859 * insert entry for new extent
860 */
863 /*
864 * if the leaf page is full, split the page and
865 * propagate up the router entry for the new page from split
866 *
867 * The xtSplitUp() will insert the entry and unpin the leaf page.
868 */
879 /* undo data extent allocation */
883 }
885 }
889 }
891 /*
892 * insert the new entry into the leaf page
893 */
894 /*
895 * acquire a transaction lock on the leaf page;
896 *
897 * action: xad insertion/extension;
898 */
901 /* if insert into middle, shift right remaining entries. */
906 /* insert the new entry: mark the entry NEW */
910 /* advance next available entry index */
914 /* Don't log it if there are no links to the file */
923 }
927 out:
928 /* unpin the leaf page */
932 }
935 /*
936 * xtSplitUp()
937 *
938 * function:
939 * split full pages as propagating insertion up the tree
940 *
941 * parameter:
942 * tid - transaction id;
943 * ip - file object;
944 * split - entry parameter descriptor;
945 * btstack - traverse stack from xtSearch()
946 *
947 * return:
948 */
949 static int
952 {
965 s64 xaddr;
976 /* is inode xtree root extension/inline EA area free ? */
984 /*
985 * acquire a transaction lock on the leaf page;
986 *
987 * action: xad insertion/extension;
988 */
990 /* if insert into middle, shift right remaining entries. */
997 /* insert the new entry: mark the entry NEW */
1002 /* advance next available entry index */
1006 /* Don't log it if there are no links to the file */
1015 }
1018 }
1020 /*
1021 * allocate new index blocks to cover index page split(s)
1022 *
1023 * allocation hint: ?
1024 */
1040 }
1042 /* undo allocation */
1046 }
1047 }
1049 /*
1050 * Split leaf page <sp> into <sp> and a new right page <rp>.
1051 *
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>.
1055 */
1064 /*
1065 * propagate up the router entry for the leaf page just split
1066 *
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.
1071 *
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
1074 * the new entry.
1075 *
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.
1079 *
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.
1084 */
1086 /* parent page specified by stack frame <parent> */
1088 /* keep current child pages <rcp> pinned */
1093 /*
1094 * insert router entry in parent for new right child page <rp>
1095 */
1096 /* get/pin the parent page <sp> */
1101 }
1103 /*
1104 * The new key entry goes ONE AFTER the index of parent entry,
1105 * because the split was to the right.
1106 */
1109 /*
1110 * split or shift right remaining entries of the parent page
1111 */
1113 /*
1114 * parent page is full - split the parent page
1115 */
1117 /* init for parent page split */
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>.
1131 */
1138 }
1141 /* keep new child page <rp> pinned */
1142 }
1143 /*
1144 * parent page is not full - insert in parent page
1145 */
1147 /*
1148 * insert router entry in parent for the right child
1149 * page from the first entry of the right child page:
1150 */
1151 /*
1152 * acquire a transaction lock on the parent page;
1153 *
1154 * action: router xad insertion;
1155 */
1158 /*
1159 * if insert into middle, shift right remaining entries
1160 */
1166 /* insert the router entry */
1172 /* advance next available entry index. */
1177 /* Don't log it if there are no links to the file */
1187 }
1189 /* unpin parent page */
1192 /* exit propagate up */
1194 }
1195 }
1197 /* unpin current right page */
1201 }
1204 /*
1205 * xtSplitPage()
1206 *
1207 * function:
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.
1211 *
1212 * parameter:
1213 * int tid,
1214 * struct inode *ip,
1215 * struct xtsplit *split,
1216 * struct metapage **rmpp,
1217 * u64 *rbnp,
1218 *
1219 * return:
1220 * Pointer to page in which to insert or NULL on error.
1221 */
1222 static int
1225 {
1234 s64 nextbn;
1253 /* Allocate blocks to quota. */
1257 }
1261 /*
1262 * allocate the new right page for the split
1263 */
1268 }
1273 /*
1274 * action: new page;
1275 */
1284 /* Don't log it if there are no links to the file */
1286 /*
1287 * acquire a transaction lock on the new right page;
1288 */
1292 /*
1293 * acquire a transaction lock on the split page
1294 */
1297 }
1299 /*
1300 * initialize/update sibling pointers of <sp> and <rp>
1301 */
1309 /*
1310 * sequential append at tail (after last entry of last page)
1311 *
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
1317 * way next time.
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.
1320 * Be my guest.)
1321 */
1323 /*
1324 * acquire a transaction lock on the new/right page;
1325 *
1326 * action: xad insertion;
1327 */
1328 /* insert entry at the first entry of the new right page */
1336 /* rxtlck->lwm.offset = XTENTRYSTART; */
1338 }
1345 }
1347 /*
1348 * non-sequential insert (at possibly middle page)
1349 */
1351 /*
1352 * update previous pointer of old next/right page of <sp>
1353 */
1359 }
1362 /*
1363 * acquire a transaction lock on the next page;
1364 *
1365 * action:sibling pointer update;
1366 */
1372 /* sibling page may have been updated previously, or
1373 * it may be updated later;
1374 */
1377 }
1379 /*
1380 * split the data between the split and new/right pages
1381 */
1386 /*
1387 * skip index in old split/left page - insert into left page:
1388 */
1390 /* move right half of split page to the new right page */
1394 /* shift right tail of left half to make room for new entry */
1399 /* insert new entry */
1404 /* update page header */
1409 }
1413 }
1414 /*
1415 * skip index in new right page - insert into right page:
1416 */
1418 /* move left head of right half to right page */
1423 /* insert new entry */
1429 /* move right tail of right half to right page */
1434 /* update page header */
1439 }
1443 }
1449 /* rxtlck->lwm.offset = XTENTRYSTART; */
1451 XTENTRYSTART;
1452 }
1460 clean_up:
1462 /* Rollback quota allocation. */
1467 }
1470 /*
1471 * xtSplitRoot()
1472 *
1473 * function:
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.
1481 *
1482 * parameter:
1483 * int tid,
1484 * struct inode *ip,
1485 * struct xtsplit *split,
1486 * struct metapage **rmpp)
1487 *
1488 * return:
1489 * Pointer to page in which to insert or NULL on error.
1490 */
1491 static int
1494 {
1498 s64 rbn;
1510 /*
1511 * allocate a single (right) child page
1512 */
1521 /* Allocate blocks to quota. */
1525 }
1529 /*
1530 * acquire a transaction lock on the new right page;
1531 *
1532 * action: new page;
1533 */
1543 /* initialize sibling pointers */
1547 /*
1548 * copy the in-line root page into new right page extent
1549 */
1554 /*
1555 * insert the new entry into the new right/child page
1556 * (skip index in the new right page will not change)
1557 */
1559 /* if insert into middle, shift right remaining entries */
1567 /* update page header */
1575 XTENTRYSTART;
1576 }
1578 /*
1579 * reset the root
1580 *
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.
1584 */
1585 /*
1586 * acquire a transaction lock on the root page (in-memory inode);
1587 *
1588 * action: root split;
1589 */
1595 /* update page header of root */
1606 }
1612 }
1615 /*
1616 * xtExtend()
1617 *
1618 * function: extend in-place;
1619 *
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;
1624 */
1629 {
1634 s64 bn;
1639 s64 xaddr;
1645 /* there must exist extent to be extended */
1649 /* retrieve search result */
1656 }
1658 /* extension must be contiguous */
1664 }
1666 /*
1667 * acquire a transaction lock on the leaf page;
1668 *
1669 * action: xad insertion/extension;
1670 */
1675 }
1677 /* extend will overflow extent ? */
1682 /*
1683 * extent overflow: insert entry for new extent
1684 */
1685 //insertNew:
1690 /*
1691 * if the leaf page is full, insert the new entry and
1692 * propagate up the router entry for the new page from split
1693 *
1694 * The xtSplitUp() will insert the entry and unpin the leaf page.
1695 */
1697 /* xtSpliUp() unpins leaf pages */
1708 /* get back old page */
1712 /*
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;
1716 */
1724 /* get new child page */
1733 }
1734 }
1735 }
1736 /*
1737 * insert the new entry into the leaf page
1738 */
1740 /* insert the new entry: mark the entry NEW */
1744 /* advance next available entry index */
1747 }
1749 /* get back old entry */
1753 /*
1754 * extend old extent
1755 */
1756 extendOld:
1767 }
1769 /* unpin the leaf page */
1773 }
1775 #ifdef _NOTYET
1776 /*
1777 * xtTailgate()
1778 *
1779 * function: split existing 'tail' extent
1780 * (split offset >= start offset of tail extent), and
1781 * relocate and extend the split tail half;
1782 *
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;
1787 */
1793 {
1798 s64 bn;
1808 /*
1809 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1810 (ulong)xoff, xlen, (ulong)xaddr);
1811 */
1813 /* there must exist extent to be tailgated */
1817 /* retrieve search result */
1824 }
1826 /* entry found must be last entry */
1833 }
1836 /*
1837 * acquire tlock of the leaf page containing original entry
1838 */
1842 }
1844 /* completely replace extent ? */
1846 /*
1847 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1848 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1849 */
1853 /*
1854 * partially replace extent: insert entry for new extent
1855 */
1856 //insertNew:
1857 /*
1858 * if the leaf page is full, insert the new entry and
1859 * propagate up the router entry for the new page from split
1860 *
1861 * The xtSplitUp() will insert the entry and unpin the leaf page.
1862 */
1864 /* xtSpliUp() unpins leaf pages */
1875 /* get back old page */
1879 /*
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;
1883 */
1891 /* get new child page */
1900 }
1901 }
1902 }
1903 /*
1904 * insert the new entry into the leaf page
1905 */
1907 /* insert the new entry: mark the entry NEW */
1911 /* advance next available entry index */
1914 }
1916 /* get back old XAD */
1919 /*
1920 * truncate/relocate old extent at split offset
1921 */
1922 updateOld:
1923 /* update dmap for old/committed/truncated extent */
1926 /* free from PWMAP at commit */
1934 }
1936 /* free from WMAP */
1940 /* truncate */
1942 else
1943 /* replace */
1951 }
1953 /* unpin the leaf page */
1957 }
1960 /*
1961 * xtUpdate()
1962 *
1963 * function: update XAD;
1964 *
1965 * update extent for allocated_but_not_recorded or
1966 * compressed extent;
1967 *
1968 * parameter:
1969 * nxad - new XAD;
1970 * logical extent of the specified XAD must be completely
1971 * contained by an existing XAD;
1972 */
1979 s64 bn;
1992 /* there must exist extent to be tailgated */
2000 /* retrieve search result */
2007 }
2010 /*
2011 * acquire tlock of the leaf page containing original entry
2012 */
2016 }
2024 /* nXAD must be completely contained within XAD */
2031 }
2037 #ifdef _JFS_WIP_NOCOALESCE
2041 /*
2042 * replace XAD with nXAD
2043 */
2046 /* replace XAD with nXAD:recorded */
2055 /* #ifdef _JFS_WIP_COALESCE */
2059 /*
2060 * coalesce with left XAD
2061 */
2062 //coalesceLeft: /* (xoff == nxoff) */
2063 /* is XAD first entry of page ? */
2067 /* is nXAD logically and physically contiguous with lXAD ? */
2074 /* extend right lXAD */
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
2081 * XAD_EXTENDED
2082 */
2087 /* truncate XAD */
2094 /* remove XAD */
2111 }
2112 }
2114 /*
2115 * replace XAD with nXAD
2116 */
2119 /* replace XAD with nXAD:recorded */
2127 /*
2128 * coalesce with right XAD
2129 */
2131 /* is XAD last entry of page ? */
2136 }
2138 /* is nXAD logically and physically contiguous with rXAD ? */
2145 /* extend left rXAD */
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
2153 * XAD_EXTENDED
2154 */
2159 /* truncate XAD */
2163 /* remove XAD */
2170 }
2180 }
2181 /* #endif _JFS_WIP_COALESCE */
2183 /*
2184 * split XAD into (lXAD, nXAD):
2185 *
2186 * |---nXAD--->
2187 * --|----------XAD----------|--
2188 * |-lXAD-|
2189 */
2191 /* truncate old XAD as lXAD:not_recorded */
2195 /* insert nXAD:recorded */
2198 /* xtSpliUp() unpins leaf pages */
2209 /* get back old page */
2213 /*
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;
2217 */
2225 /* get new child page */
2234 }
2236 /* is nXAD on new page ? */
2239 newindex =
2240 newindex -
2242 XTENTRYSTART;
2244 }
2245 }
2247 /* if insert into middle, shift right remaining entries */
2252 /* insert the entry */
2257 /* advance next available entry index. */
2260 }
2262 /*
2263 * does nXAD force 3-way split ?
2264 *
2265 * |---nXAD--->|
2266 * --|----------XAD-------------|--
2267 * |-lXAD-| |-rXAD -|
2268 */
2272 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2274 /* close out old page */
2281 }
2286 /* get new right page */
2295 }
2299 index++;
2307 /* recompute split pages */
2314 /* retrieve search result */
2321 }
2328 }
2329 }
2331 /*
2332 * split XAD into (nXAD, rXAD)
2333 *
2334 * ---nXAD---|
2335 * --|----------XAD----------|--
2336 * |-rXAD-|
2337 */
2339 /* update old XAD with nXAD:recorded */
2344 /* insert rXAD:not_recorded */
2349 /*
2350 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2351 */
2352 /* xtSpliUp() unpins leaf pages */
2363 /* get back old page */
2368 /*
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;
2372 */
2380 /* get new child page */
2389 }
2390 }
2392 /* if insert into middle, shift right remaining entries */
2397 /* insert the entry */
2401 /* advance next available entry index. */
2404 }
2406 out:
2412 }
2414 /* unpin the leaf page */
2418 }
2421 /*
2422 * xtAppend()
2423 *
2424 * function: grow in append mode from contiguous region specified ;
2425 *
2426 * parameter:
2427 * tid - transaction id;
2428 * ip - file object;
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):
2434 * flag -
2435 *
2436 * return:
2437 */
2443 {
2458 s64 next;
2465 /*
2466 * search for the entry location at which to insert:
2467 *
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
2471 * the full page.
2472 */
2476 /* retrieve search result */
2482 }
2486 //insert:
2487 /*
2488 * insert entry for new extent
2489 */
2492 /*
2493 * if the leaf page is full, split the page and
2494 * propagate up the router entry for the new page from split
2495 *
2496 * The xtSplitUp() will insert the entry and unpin the leaf page.
2497 */
2502 /*
2503 * allocate new index blocks to cover index page split(s)
2504 */
2518 }
2520 /* undo allocation */
2523 }
2527 /*
2528 * allocate data extent requested
2529 */
2540 /* undo data extent allocation */
2544 }
2550 /*
2551 * insert the new entry into the leaf page
2552 */
2553 insertLeaf:
2554 /*
2555 * allocate data extent requested
2556 */
2561 /*
2562 * acquire a transaction lock on the leaf page;
2563 *
2564 * action: xad insertion/extension;
2565 */
2569 /* insert the new entry: mark the entry NEW */
2573 /* advance next available entry index */
2585 out:
2586 /* unpin the leaf page */
2590 }
2591 #ifdef _STILL_TO_PORT
2593 /* - TBD for defragmentaion/reorganization -
2594 *
2595 * xtDelete()
2596 *
2597 * function:
2598 * delete the entry with the specified key.
2599 *
2600 * N.B.: whole extent of the entry is assumed to be deleted.
2601 *
2602 * parameter:
2603 *
2604 * return:
2605 * ENOENT: if the entry is not found.
2606 *
2607 * exception:
2608 */
2610 {
2614 s64 bn;
2621 /*
2622 * find the matching entry; xtSearch() pins the page
2623 */
2629 /* unpin the leaf page */
2632 }
2634 /*
2635 * delete the entry from the leaf page
2636 */
2641 /*
2642 * if the leaf page bocome empty, free the page
2643 */
2648 /*
2649 * acquire a transaction lock on the leaf page;
2650 *
2651 * action:xad deletion;
2652 */
2658 /* if delete from middle, shift left/compact the remaining entries */
2666 }
2669 /* - TBD for defragmentaion/reorganization -
2670 *
2671 * xtDeleteUp()
2672 *
2673 * function:
2674 * free empty pages as propagating deletion up the tree
2675 *
2676 * parameter:
2677 *
2678 * return:
2679 */
2680 static int
2683 {
2688 s64 xaddr;
2694 /*
2695 * keep root leaf page which has become empty
2696 */
2698 /* keep the root page */
2703 /* XT_PUTPAGE(fmp); */
2706 }
2708 /*
2709 * free non-root leaf page
2710 */
2714 }
2718 /* free the page extent */
2721 /* free the buffer page */
2724 /*
2725 * propagate page deletion up the index tree
2726 *
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.
2731 */
2733 /* get/pin the parent page <sp> */
2740 /* delete the entry for the freed child page from parent.
2741 */
2744 /*
2745 * the parent has the single entry being deleted:
2746 * free the parent page which has become empty.
2747 */
2750 /* keep the root page */
2756 /* XT_PUTPAGE(mp); */
2760 /* free the parent page */
2765 /* free the page extent */
2769 /* unpin/free the buffer page */
2772 /* propagate up */
2774 }
2775 }
2776 /*
2777 * the parent has other entries remaining:
2778 * delete the router entry from the parent page.
2779 */
2782 /*
2783 * acquire a transaction lock on the leaf page;
2784 *
2785 * action:xad deletion;
2786 */
2794 /* if delete from middle,
2795 * shift left/compact the remaining entries in the page
2796 */
2807 }
2809 /* unpin the parent page */
2812 /* exit propagation up */
2814 }
2817 }
2820 /*
2821 * NAME: xtRelocate()
2822 *
2823 * FUNCTION: relocate xtpage or data extent of regular file;
2824 * This function is mainly used by defragfs utility.
2825 *
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
2829 * this routine.
2830 */
2831 int
2850 s64 bn;
2862 /* validate extent offset */
2870 /*
2871 * 1. get and validate the parent xtpage/xad entry
2872 * covering the source extent to be relocated;
2873 */
2875 /* search in leaf entry */
2880 /* retrieve search result */
2886 }
2888 /* validate for exact match with a single entry */
2893 }
2896 /* search in internal entry */
2901 /* retrieve search result */
2907 }
2909 /* xtSearchNode() validated for exact match with a single entry
2910 */
2912 }
2915 /*
2916 * 2. relocate the extent
2917 */
2919 /* if the extent is allocated-but-not-recorded
2920 * there is no real data to be moved in this extent,
2921 */
2924 else
2925 /* release xtpage for cmRead()/xtLookup() */
2928 /*
2929 * cmRelocate()
2930 *
2931 * copy target data pages to be relocated;
2932 *
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
2941 * algorithms.
2942 * it is a good strategy because it may disrupt cache
2943 * policy to keep the pages in memory afterwards.
2944 */
2950 /*
2951 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2952 (offset >> CM_L2BSIZE) + 1;
2953 */
2957 /* process the request one cache buffer at a time */
2960 /* compute page size */
2963 /* get the cache buffer of the page */
2970 /* bind buffer with the new extent address */
2974 /* release the cbuf, mark it as modified */
2979 }
2981 /* get back parent page */
2989 /*
2990 * read in the target xtpage from the source extent;
2991 */
2996 }
2998 /*
2999 * read in sibling pages if any to update sibling pointers;
3000 */
3009 }
3010 }
3022 }
3023 }
3025 /* at this point, all xtpages to be updated are in memory */
3027 /*
3028 * update sibling pointers of sibling xtpages if any;
3029 */
3032 tlck =
3036 }
3040 tlck =
3044 }
3046 /*
3047 * update the target xtpage to be relocated
3048 *
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
3059 * updated;
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();
3066 */
3068 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
3072 /* update the self address in the xtpage header */
3076 /* linelock for the after image of the whole page */
3080 /* update the buffer extent descriptor of target xtpage */
3084 /* unpin the target page to new homeward bound */
3087 }
3089 /*
3090 * 3. acquire maplock for the source extent to be freed;
3091 *
3092 * acquire a maplock saving the src relocated extent address;
3093 * to free of the extent at commit time;
3094 */
3095 out:
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;
3100 */
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.
3110 */
3120 /*
3121 * 4. update the parent xad entry for relocation;
3122 *
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;
3126 */
3132 /* update the XAD with the new destination extent; */
3141 /* unpin the parent xtpage */
3145 }
3148 /*
3149 * xtSearchNode()
3150 *
3151 * function: search for the internal xad entry covering specified extent.
3152 * This function is mainly used by defragfs utility.
3153 *
3154 * parameters:
3155 * ip - file object;
3156 * xad - extent to find;
3157 * cmpp - comparison result:
3158 * btstack - traverse stack;
3159 * flag - search process flag;
3160 *
3161 * returns:
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.
3165 */
3168 {
3178 s64 t64;
3186 /*
3187 * search down tree from root:
3188 *
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.
3191 *
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.
3199 *
3200 * by convention, root bn = 0.
3201 */
3203 /* get/pin the page to search */
3210 }
3214 /*
3215 * binary search with search key K on the current page
3216 */
3222 /*
3223 * search hit
3224 *
3225 * verify for exact match;
3226 */
3231 /* save search result */
3238 }
3240 /* descend/search its child page */
3242 }
3247 }
3248 }
3250 /*
3251 * search miss - non-leaf page:
3252 *
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.
3257 */
3260 /*
3261 * go down to child page
3262 */
3263 next:
3264 /* get the child page block number */
3267 /* unpin the parent page */
3269 }
3270 }
3273 /*
3274 * xtRelink()
3275 *
3276 * function:
3277 * link around a freed page.
3278 *
3279 * Parameter:
3280 * int tid,
3281 * struct inode *ip,
3282 * xtpage_t *p)
3283 *
3284 * returns:
3285 */
3287 {
3296 /* update prev pointer of the next page */
3302 /*
3303 * acquire a transaction lock on the page;
3304 *
3305 * action: update prev pointer;
3306 */
3310 /* the page may already have been tlock'd */
3315 }
3317 /* update next pointer of the previous page */
3323 /*
3324 * acquire a transaction lock on the page;
3325 *
3326 * action: update next pointer;
3327 */
3331 /* the page may already have been tlock'd */
3336 }
3339 }
3343 /*
3344 * xtInitRoot()
3345 *
3346 * initialize file root (inline in inode)
3347 */
3349 {
3352 /*
3353 * acquire a transaction lock on the root
3354 *
3355 * action:
3356 */
3369 }
3373 }
3376 /*
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.
3387 */
3388 #define MAX_TRUNCATE_LEAVES 50
3390 /*
3391 * xtTruncate()
3392 *
3393 * function:
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.
3398 *
3399 * parameter:
3400 * int tid,
3401 * struct inode *ip,
3402 * s64 newsize,
3403 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3404 *
3405 * return:
3406 *
3407 * note:
3408 * PWMAP:
3409 * 1. truncate (non-COMMIT_NOLINK file)
3410 * by jfs_truncate() or jfs_open(O_TRUNC):
3411 * xtree is updated;
3412 * 2. truncate index table of directory when last entry removed
3413 * map update via tlock at commit time;
3414 * PMAP:
3415 * Call xtTruncate_pmap instead
3416 * WMAP:
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):
3420 * xtree is updated;
3421 * map update directly at truncation time;
3422 *
3423 * if (DELETE)
3424 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3425 * else if (TRUNCATE)
3426 * must write LOG_NOREDOPAGE for deleted index page;
3427 *
3428 * pages may already have been tlocked by anonymous transactions
3429 * during file growth (i.e., write) before truncation;
3430 *
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;
3435 *
3436 */
3438 {
3440 s64 teof;
3443 s64 bn;
3455 s64 nfreed;
3459 /* save object truncation type */
3463 }
3476 }
3478 /*
3479 * if the newsize is not an integral number of pages,
3480 * the file between newsize and next page boundary will
3481 * be cleared.
3482 * if truncating into a file hole, it will cause
3483 * a full block to be allocated for the logical block.
3484 */
3486 /*
3487 * release page blocks of truncated region <teof, eof>
3488 *
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.
3494 *
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
3499 * from working map.
3500 * (this will allow continued access of data/index of
3501 * temporary file (zerolink count file truncated to zero-length)).
3502 */
3506 /* clear stack */
3509 /*
3510 * start with root
3511 *
3512 * root resides in the inode
3513 */
3516 /*
3517 * first access of each page:
3518 */
3519 getPage:
3524 /* process entries backward from last index */
3530 /*
3531 * leaf page
3532 */
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.
3537 */
3540 /*
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
3544 */
3548 }
3552 /* does region covered by leaf page precede Teof ? */
3559 }
3561 /* (re)acquire tlock of the leaf page */
3564 /*
3565 * We need to limit the size of the transaction
3566 * to avoid exhausting pagecache & tlocks
3567 */
3571 }
3576 }
3579 /*
3580 * scan backward leaf page entries
3581 */
3588 /*
3589 * The "data" for a directory is indexed by the block
3590 * device's address space. This metadata must be invalidated
3591 * here
3592 */
3595 /*
3596 * entry beyond eof: continue scan of current page
3597 * xad
3598 * ---|---=======------->
3599 * eof
3600 */
3604 }
3606 /*
3607 * (xoff <= teof): last entry to be deleted from page;
3608 * If other entries remain in page: keep and update the page.
3609 */
3611 /*
3612 * eof == entry_start: delete the entry
3613 * xad
3614 * -------|=======------->
3615 * eof
3616 *
3617 */
3625 }
3626 /*
3627 * eof within the entry: truncate the entry.
3628 * xad
3629 * -------===|===------->
3630 * eof
3631 */
3633 /* update truncated entry */
3638 /* save pxd of truncated extent in tlck */
3650 }
3651 /* free truncated extent */
3660 /* reset map lock */
3662 }
3664 /* current entry is new last entry; */
3668 }
3669 /*
3670 * eof beyond the entry:
3671 * xad
3672 * -------=======---|--->
3673 * eof
3674 */
3678 }
3685 nextindex;
3688 }
3690 }
3694 /* assert(freed == 0); */
3700 /*
3701 * leaf page become empty: free the page if type != PMAP
3702 */
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;
3708 */
3712 /* free data extents covered by leaf */
3717 }
3728 /* page will be invalidated at tx completion
3729 */
3736 /* invalidate empty leaf page */
3738 }
3739 }
3741 /*
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.
3745 */
3747 /*
3748 * go back up to the parent page
3749 */
3750 getParent:
3751 /* pop/restore parent entry for the current child page */
3753 /* current page must have been root */
3756 /* get back the parent page */
3764 /*
3765 * child page was not empty:
3766 */
3768 /* has any entry deleted from parent ? */
3770 /* (re)acquire tlock on the parent page */
3772 /* txCommit() with tlckTRUNCATE:
3773 * free child extents covered by parent [);
3774 */
3783 }
3786 /* free child extents covered by parent */
3793 }
3797 }
3800 }
3802 /*
3803 * child page was empty:
3804 */
3807 /*
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.
3812 *
3813 * ToDo: tlocks should be on doubly-linked list, so we can
3814 * quickly remove it and add it to the end.
3815 */
3817 /*
3818 * Move parent page's tlock to the end of the tid's tlock list
3819 */
3834 }
3836 }
3840 }
3842 /*
3843 * parent page become empty: free the page
3844 */
3847 /* txCommit() with tlckFREE:
3848 * free child extents covered by parent;
3849 * invalidate parent if COMMIT_PWMAP;
3850 */
3858 /* free child extents covered by parent */
3862 XTENTRYSTART;
3864 COMMIT_WMAP);
3865 }
3873 /*
3874 * Shrink root down to allow inline
3875 * EA (otherwise fsck complains)
3876 */
3880 }
3886 /* page will be invalidated at tx completion
3887 */
3893 tlckFREELOCK;
3895 /* invalidate parent page */
3897 }
3899 /* parent has become empty and freed:
3900 * go back up to its parent page
3901 */
3902 /* freed = 1; */
3904 }
3905 }
3906 /*
3907 * parent page still has entries for front region;
3908 */
3910 /* try truncate region covered by preceding entry
3911 * (process backward)
3912 */
3913 index--;
3915 /* go back down to the child page corresponding
3916 * to the entry
3917 */
3919 }
3921 /*
3922 * internal page: go down to child page of current entry
3923 */
3924 getChild:
3925 /* save current parent entry for the child page */
3928 /* get child page */
3932 /*
3933 * first access of each internal entry:
3934 */
3935 /* release parent page */
3938 /* process the child page */
3941 out:
3942 /*
3943 * update file resource stat
3944 */
3945 /* set size
3946 */
3949 else
3952 /* update quota allocation to reflect freed blocks */
3955 /*
3956 * free tlock of invalidated pages
3957 */
3962 }
3965 /*
3966 * xtTruncate_pmap()
3967 *
3968 * function:
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.
3973 *
3974 * parameter:
3975 * tid_t tid,
3976 * struct inode *ip,
3977 * s64 committed_size)
3978 *
3979 * return: new committed size
3980 *
3981 * note:
3982 *
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.
3987 */
3989 {
3990 s64 bn;
4003 s64 xoff;
4006 /* save object truncation type */
4010 /* clear stack */
4026 }
4028 /*
4029 * start with root
4030 *
4031 * root resides in the inode
4032 */
4035 /*
4036 * first access of each page:
4037 */
4038 getPage:
4043 /* process entries backward from last index */
4048 }
4050 /*
4051 * leaf page
4052 */
4055 /*
4056 * We need to limit the size of the transaction
4057 * to avoid exhausting pagecache & tlocks
4058 */
4064 }
4073 /*
4074 * go back up to the parent page
4075 */
4076 getParent:
4077 /* pop/restore parent entry for the current child page */
4079 /* current page must have been root */
4082 /* get back the parent page */
4090 /*
4091 * parent page become empty: free the page
4092 */
4094 /* txCommit() with tlckFREE:
4095 * free child extents covered by parent;
4096 * invalidate parent if COMMIT_PWMAP;
4097 */
4111 }
4112 }
4113 /*
4114 * parent page still has entries for front region;
4115 */
4116 else
4117 index--;
4118 /*
4119 * internal page: go down to child page of current entry
4120 */
4121 getChild:
4122 /* save current parent entry for the child page */
4125 /* get child page */
4129 /*
4130 * first access of each internal entry:
4131 */
4132 /* release parent page */
4135 /* process the child page */
4138 out:
4141 }
4144 #ifdef _JFS_DEBUG_XTREE
4145 /*
4146 * xtDisplayTree()
4147 *
4148 * function: traverse forward
4149 */
4151 {
4164 /* clear stack */
4167 /*
4168 * start with root
4169 *
4170 * root resides in the inode
4171 */
4175 /*
4176 * first access of each page:
4177 */
4178 getPage:
4183 /* process entries forward from first index */
4188 /*
4189 * first access of each internal page
4190 */
4194 /*
4195 * first access of each leaf page
4196 */
4200 /* unpin the leaf page */
4202 }
4204 /*
4205 * go back up to the parent page
4206 */
4207 getParent:
4208 /* pop/restore parent entry for the current child page */
4210 /* current page must have been root */
4213 /*
4214 * parent page scan completed
4215 */
4217 /* go back up to the parent page */
4219 }
4221 /*
4222 * parent page has entries remaining
4223 */
4224 /* get back the parent page */
4226 /* v = parent->level; */
4231 /* get next parent entry */
4232 index++;
4234 /*
4235 * internal page: go down to child page of current entry
4236 */
4237 getChild:
4238 /* push/save current parent entry for the child page */
4242 /* btsp->level = v; */
4243 /* btsp->node = h; */
4246 /* get child page */
4250 /*
4251 * first access of each internal entry:
4252 */
4253 /* release parent page */
4258 v++;
4261 /* process the child page */
4263 }
4266 /*
4267 * xtDisplayPage()
4268 *
4269 * function: display page
4270 */
4272 {
4278 /* display page control */
4283 /* display entries */
4296 }
4297 }
4300 }
4304 #ifdef _JFS_WIP
4305 /*
4306 * xtGather()
4307 *
4308 * function:
4309 * traverse for allocation acquiring tlock at commit time
4310 * (vs at the time of update) logging backward top down
4311 *
4312 * note:
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
4316 *
4317 */
4319 {
4322 u64 bn;
4328 /* clear stack */
4331 /*
4332 * start with root
4333 *
4334 * root resides in the inode
4335 */
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;
4345 */
4347 dopage:
4348 /*
4349 * first access of each page:
4350 */
4351 /* process entries backward from last index */
4355 /*
4356 * first access of each leaf page
4357 */
4358 /* process leaf page entries backward */
4361 /*
4362 * if newpage, log NEWPAGE.
4363 *
4364 if (e->flag & XAD_NEW) {
4365 nfound =+ entry->length;
4366 update current page lock for the entry;
4367 newpage(entry);
4368 *
4369 * if moved, log move.
4370 *
4371 } else if (e->flag & XAD_MOVED) {
4372 reset flag;
4373 update current page lock for the entry;
4374 }
4375 */
4376 }
4378 /* unpin the leaf page */
4381 /*
4382 * go back up to the parent page
4383 */
4384 getParent:
4385 /* restore parent entry for the current child page */
4387 /* current page must have been root */
4391 /*
4392 * parent page scan completed
4393 */
4394 /* go back up to the parent page */
4397 /*
4398 * parent page has entries remaining
4399 */
4400 /* get back the parent page */
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)))
4414 exit scan;
4415 */
4417 /* process parent page entries backward */
4418 index--;
4419 }
4421 /*
4422 * first access of each internal page
4423 */
4424 }
4426 /*
4427 * internal page: go down to child page of current entry
4428 */
4430 /* save current parent entry for the child page */
4433 /* get current entry for the child page */
4436 /*
4437 * first access of each internal entry:
4438 */
4439 /*
4440 * if new entry, log btree_tnewentry.
4441 *
4442 if (e->flag & XAD_NEW)
4443 update parent page lock for the entry;
4444 */
4446 /* release parent page */
4449 /* get child page */
4455 /*
4456 * first access of each non-root page:
4457 */
4458 /*
4459 * if new, log btree_newpage.
4460 *
4461 if (p->header.flag & NEW)
4462 allocate new page lock;
4463 write a NEWPAGE log (next, prev);
4464 */
4466 /* process the child page */
4469 out:
4471 }
4475 #ifdef CONFIG_JFS_STATISTICS
4478 {
4480 off_t begin;
4498 else
4505 }
4506 #endif