| blob | 11c58c54b818e8bfba8e9affffc1e834a987b620 |
1 /*
2 * Copyright (C) International Business Machines Corp., 2000-2004
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;
169 /* is lookup offset beyond eof ? */
176 }
177 }
179 /*
180 * search for the xad entry covering the logical extent
181 */
182 //search:
186 }
188 /*
189 * compute the physical extent covering logical extent
190 *
191 * N.B. search may have failed (e.g., hole in sparse file),
192 * and returned the index of the next entry.
193 */
194 /* retrieve search result */
197 /* is xad found covering start of logical extent ?
198 * lstart is a page start address,
199 * i.e., lstart cannot start in a hole;
200 */
204 /*
205 * lxd covered by xad
206 */
213 /* initialize new pxd */
216 /* a page must be fully covered by an xad */
219 out:
223 }
226 /*
227 * xtLookupList()
228 *
229 * function: map a single logical extent into a list of physical extent;
230 *
231 * parameter:
232 * struct inode *ip,
233 * struct lxdlist *lxdlist, lxd list (in)
234 * struct xadlist *xadlist, xad list (in/out)
235 * int flag)
236 *
237 * coverage of lxd by xad under assumption of
238 * . lxd's are ordered and disjoint.
239 * . xad's are ordered and disjoint.
240 *
241 * return:
242 * 0: success
243 *
244 * note: a page being written (even a single byte) is backed fully,
245 * except the last page which is only backed with blocks
246 * required to cover the last byte;
247 * the extent backing a page is fully contained within an xad;
248 */
251 {
255 s64 bn;
280 /*
281 * search for the xad entry covering the logical extent
282 */
283 search:
290 /*
291 * compute the physical extent covering logical extent
292 *
293 * N.B. search may have failed (e.g., hole in sparse file),
294 * and returned the index of the next entry.
295 */
296 //map:
297 /* retrieve search result */
300 /* is xad on the next sibling page ? */
310 /* get next sibling page */
316 }
320 /*
321 * is lxd covered by xad ?
322 */
323 compare:
329 compare1:
333 /* (lstart <= xstart) */
335 /* lxd is NOT covered by xad */
337 /*
338 * get next lxd
339 */
342 lxd++;
350 /* compare with the current xad */
352 }
353 /* lxd is covered by xad */
356 /* initialize new pxd */
362 }
364 /* (xstart < lstart) */
365 compare2:
366 /* lxd is covered by xad */
368 /* initialize new pxd */
374 }
375 /* lxd is NOT covered by xad */
378 /*
379 * get next xad
380 *
381 * linear search next xad covering lxd on
382 * the current xad page, and then tree search
383 */
391 index++;
392 xad++;
394 /* compare with new xad */
396 }
397 }
399 /*
400 * lxd is covered by xad and a new pxd has been initialized
401 * (lstart <= xstart < lend) or (xstart < lstart < xend)
402 */
403 cover:
404 /* finalize pxd corresponding to current xad */
409 pxd++;
411 /*
412 * lxd is fully covered by xad
413 */
415 /*
416 * get next lxd
417 */
420 lxd++;
428 /*
429 * test for old xad covering new lxd
430 * (old xstart < new lstart)
431 */
433 }
434 /*
435 * lxd is partially covered by xad
436 */
439 /*
440 * get next xad
441 *
442 * linear search next xad covering lxd on
443 * the current xad page, and then next xad page search
444 */
454 /* get next sibling page */
462 index++;
463 xad++;
464 }
466 /*
467 * test for new xad covering old lxd
468 * (old lstart < new xstart)
469 */
471 }
473 mapend:
476 //out:
480 }
483 /*
484 * xtSearch()
485 *
486 * function: search for the xad entry covering specified offset.
487 *
488 * parameters:
489 * ip - file object;
490 * xoff - extent offset;
491 * cmpp - comparison result:
492 * btstack - traverse stack;
493 * flag - search process flag (XT_INSERT);
494 *
495 * returns:
496 * btstack contains (bn, index) of search path traversed to the entry.
497 * *cmpp is set to result of comparison with the entry returned.
498 * the page containing the entry is pinned at exit.
499 */
502 {
513 s64 t64;
521 /*
522 * search down tree from root:
523 *
524 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
525 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
526 *
527 * if entry with search key K is not found
528 * internal page search find the entry with largest key Ki
529 * less than K which point to the child page to search;
530 * leaf page search find the entry with smallest key Kj
531 * greater than K so that the returned index is the position of
532 * the entry to be shifted right for insertion of new entry.
533 * for empty tree, search key is greater than any key of the tree.
534 *
535 * by convention, root bn = 0.
536 */
538 /* get/pin the page to search */
543 /* try sequential access heuristics with the previous
544 * access entry in target leaf page:
545 * once search narrowed down into the target leaf,
546 * key must either match an entry in the leaf or
547 * key entry does not exist in the tree;
548 */
549 //fastSearch:
560 }
562 /* stop sequential access heuristics */
566 /* try next sequential entry */
567 index++;
570 xad++;
576 }
578 /* miss: key falls between
579 * previous and this entry
580 */
583 }
585 /* (xoff >= t64 + lengthXAD(xad));
586 * matching entry may be further out:
587 * stop heuristic search
588 */
589 /* stop sequential access heuristics */
591 }
593 /* (index == p->header.nextindex);
594 * miss: key entry does not exist in
595 * the target leaf/tree
596 */
599 }
601 /*
602 * if hit, return index of the entry found, and
603 * if miss, where new entry with search key is
604 * to be inserted;
605 */
606 out:
607 /* compute number of pages to split */
611 nsplit++;
612 else
615 }
617 /* save search result */
623 /* update sequential access heuristics */
628 }
630 /* well, ... full search now */
631 binarySearch:
634 /*
635 * binary search with search key K on the current page
636 */
642 /*
643 * search hit
644 */
645 /* search hit - leaf page:
646 * return the entry found
647 */
651 /* compute number of pages to split */
655 nsplit++;
656 else
659 }
661 /* save search result */
667 /* init sequential access heuristics */
672 else
677 }
679 /* search hit - internal page:
680 * descend/search its child page
681 */
683 }
688 }
689 }
691 /*
692 * search miss
693 *
694 * base is the smallest index with key (Kj) greater than
695 * search key (K) and may be zero or maxentry index.
696 */
697 /*
698 * search miss - leaf page:
699 *
700 * return location of entry (base) where new entry with
701 * search key K is to be inserted.
702 */
706 /* compute number of pages to split */
710 nsplit++;
711 else
714 }
716 /* save search result */
722 /* init sequential access heuristics */
726 else
731 }
733 /*
734 * search miss - non-leaf page:
735 *
736 * if base is non-zero, decrement base by one to get the parent
737 * entry of the child page to search.
738 */
741 /*
742 * go down to child page
743 */
744 next:
745 /* update number of pages to split */
747 nsplit++;
748 else
751 /* push (bn, index) of the parent page/entry */
754 /* get the child page block number */
757 /* unpin the parent page */
759 }
760 }
762 /*
763 * xtInsert()
764 *
765 * function:
766 *
767 * parameter:
768 * tid - transaction id;
769 * ip - file object;
770 * xflag - extent flag (XAD_NOTRECORDED):
771 * xoff - extent offset;
772 * xlen - extent length;
773 * xaddrp - extent address pointer (in/out):
774 * if (*xaddrp)
775 * caller allocated data extent at *xaddrp;
776 * else
777 * allocate data extent and return its xaddr;
778 * flag -
779 *
780 * return:
781 */
785 {
790 s64 bn;
801 /*
802 * search for the entry location at which to insert:
803 *
804 * xtFastSearch() and xtSearch() both returns (leaf page
805 * pinned, index at which to insert).
806 * n.b. xtSearch() may return index of maxentry of
807 * the full page.
808 */
812 /* retrieve search result */
815 /* This test must follow XT_GETSEARCH since mp must be valid if
816 * we branch to out: */
820 }
822 /*
823 * allocate data extent requested
824 *
825 * allocation hint: last xad
826 */
838 }
839 }
841 /*
842 * insert entry for new extent
843 */
846 /*
847 * if the leaf page is full, split the page and
848 * propagate up the router entry for the new page from split
849 *
850 * The xtSplitUp() will insert the entry and unpin the leaf page.
851 */
862 /* undo data extent allocation */
866 }
868 }
872 }
874 /*
875 * insert the new entry into the leaf page
876 */
877 /*
878 * acquire a transaction lock on the leaf page;
879 *
880 * action: xad insertion/extension;
881 */
884 /* if insert into middle, shift right remaining entries. */
889 /* insert the new entry: mark the entry NEW */
893 /* advance next available entry index */
897 /* Don't log it if there are no links to the file */
906 }
910 out:
911 /* unpin the leaf page */
915 }
918 /*
919 * xtSplitUp()
920 *
921 * function:
922 * split full pages as propagating insertion up the tree
923 *
924 * parameter:
925 * tid - transaction id;
926 * ip - file object;
927 * split - entry parameter descriptor;
928 * btstack - traverse stack from xtSearch()
929 *
930 * return:
931 */
932 static int
935 {
948 s64 xaddr;
959 /* is inode xtree root extension/inline EA area free ? */
967 /*
968 * acquire a transaction lock on the leaf page;
969 *
970 * action: xad insertion/extension;
971 */
973 /* if insert into middle, shift right remaining entries. */
980 /* insert the new entry: mark the entry NEW */
985 /* advance next available entry index */
989 /* Don't log it if there are no links to the file */
998 }
1001 }
1003 /*
1004 * allocate new index blocks to cover index page split(s)
1005 *
1006 * allocation hint: ?
1007 */
1023 }
1025 /* undo allocation */
1029 }
1030 }
1032 /*
1033 * Split leaf page <sp> into <sp> and a new right page <rp>.
1034 *
1035 * The split routines insert the new entry into the leaf page,
1036 * and acquire txLock as appropriate.
1037 * return <rp> pinned and its block number <rpbn>.
1038 */
1047 /*
1048 * propagate up the router entry for the leaf page just split
1049 *
1050 * insert a router entry for the new page into the parent page,
1051 * propagate the insert/split up the tree by walking back the stack
1052 * of (bn of parent page, index of child page entry in parent page)
1053 * that were traversed during the search for the page that split.
1054 *
1055 * the propagation of insert/split up the tree stops if the root
1056 * splits or the page inserted into doesn't have to split to hold
1057 * the new entry.
1058 *
1059 * the parent entry for the split page remains the same, and
1060 * a new entry is inserted at its right with the first key and
1061 * block number of the new right page.
1062 *
1063 * There are a maximum of 3 pages pinned at any time:
1064 * right child, left parent and right parent (when the parent splits)
1065 * to keep the child page pinned while working on the parent.
1066 * make sure that all pins are released at exit.
1067 */
1069 /* parent page specified by stack frame <parent> */
1071 /* keep current child pages <rcp> pinned */
1076 /*
1077 * insert router entry in parent for new right child page <rp>
1078 */
1079 /* get/pin the parent page <sp> */
1084 }
1086 /*
1087 * The new key entry goes ONE AFTER the index of parent entry,
1088 * because the split was to the right.
1089 */
1092 /*
1093 * split or shift right remaining entries of the parent page
1094 */
1096 /*
1097 * parent page is full - split the parent page
1098 */
1100 /* init for parent page split */
1108 /* unpin previous right child page */
1111 /* The split routines insert the new entry,
1112 * and acquire txLock as appropriate.
1113 * return <rp> pinned and its block number <rpbn>.
1114 */
1121 }
1124 /* keep new child page <rp> pinned */
1125 }
1126 /*
1127 * parent page is not full - insert in parent page
1128 */
1130 /*
1131 * insert router entry in parent for the right child
1132 * page from the first entry of the right child page:
1133 */
1134 /*
1135 * acquire a transaction lock on the parent page;
1136 *
1137 * action: router xad insertion;
1138 */
1141 /*
1142 * if insert into middle, shift right remaining entries
1143 */
1149 /* insert the router entry */
1155 /* advance next available entry index. */
1160 /* Don't log it if there are no links to the file */
1170 }
1172 /* unpin parent page */
1175 /* exit propagate up */
1177 }
1178 }
1180 /* unpin current right page */
1184 }
1187 /*
1188 * xtSplitPage()
1189 *
1190 * function:
1191 * split a full non-root page into
1192 * original/split/left page and new right page
1193 * i.e., the original/split page remains as left page.
1194 *
1195 * parameter:
1196 * int tid,
1197 * struct inode *ip,
1198 * struct xtsplit *split,
1199 * struct metapage **rmpp,
1200 * u64 *rbnp,
1201 *
1202 * return:
1203 * Pointer to page in which to insert or NULL on error.
1204 */
1205 static int
1208 {
1217 s64 nextbn;
1236 /* Allocate blocks to quota. */
1240 }
1244 /*
1245 * allocate the new right page for the split
1246 */
1251 }
1256 /*
1257 * action: new page;
1258 */
1267 /* Don't log it if there are no links to the file */
1269 /*
1270 * acquire a transaction lock on the new right page;
1271 */
1275 /*
1276 * acquire a transaction lock on the split page
1277 */
1280 }
1282 /*
1283 * initialize/update sibling pointers of <sp> and <rp>
1284 */
1292 /*
1293 * sequential append at tail (after last entry of last page)
1294 *
1295 * if splitting the last page on a level because of appending
1296 * a entry to it (skip is maxentry), it's likely that the access is
1297 * sequential. adding an empty page on the side of the level is less
1298 * work and can push the fill factor much higher than normal.
1299 * if we're wrong it's no big deal - we will do the split the right
1300 * way next time.
1301 * (it may look like it's equally easy to do a similar hack for
1302 * reverse sorted data, that is, split the tree left, but it's not.
1303 * Be my guest.)
1304 */
1306 /*
1307 * acquire a transaction lock on the new/right page;
1308 *
1309 * action: xad insertion;
1310 */
1311 /* insert entry at the first entry of the new right page */
1319 /* rxtlck->lwm.offset = XTENTRYSTART; */
1321 }
1328 }
1330 /*
1331 * non-sequential insert (at possibly middle page)
1332 */
1334 /*
1335 * update previous pointer of old next/right page of <sp>
1336 */
1342 }
1345 /*
1346 * acquire a transaction lock on the next page;
1347 *
1348 * action:sibling pointer update;
1349 */
1355 /* sibling page may have been updated previously, or
1356 * it may be updated later;
1357 */
1360 }
1362 /*
1363 * split the data between the split and new/right pages
1364 */
1369 /*
1370 * skip index in old split/left page - insert into left page:
1371 */
1373 /* move right half of split page to the new right page */
1377 /* shift right tail of left half to make room for new entry */
1382 /* insert new entry */
1387 /* update page header */
1392 }
1396 }
1397 /*
1398 * skip index in new right page - insert into right page:
1399 */
1401 /* move left head of right half to right page */
1406 /* insert new entry */
1412 /* move right tail of right half to right page */
1417 /* update page header */
1422 }
1426 }
1432 /* rxtlck->lwm.offset = XTENTRYSTART; */
1434 XTENTRYSTART;
1435 }
1443 clean_up:
1445 /* Rollback quota allocation. */
1450 }
1453 /*
1454 * xtSplitRoot()
1455 *
1456 * function:
1457 * split the full root page into
1458 * original/root/split page and new right page
1459 * i.e., root remains fixed in tree anchor (inode) and
1460 * the root is copied to a single new right child page
1461 * since root page << non-root page, and
1462 * the split root page contains a single entry for the
1463 * new right child page.
1464 *
1465 * parameter:
1466 * int tid,
1467 * struct inode *ip,
1468 * struct xtsplit *split,
1469 * struct metapage **rmpp)
1470 *
1471 * return:
1472 * Pointer to page in which to insert or NULL on error.
1473 */
1474 static int
1477 {
1481 s64 rbn;
1493 /*
1494 * allocate a single (right) child page
1495 */
1504 /* Allocate blocks to quota. */
1508 }
1512 /*
1513 * acquire a transaction lock on the new right page;
1514 *
1515 * action: new page;
1516 */
1526 /* initialize sibling pointers */
1530 /*
1531 * copy the in-line root page into new right page extent
1532 */
1537 /*
1538 * insert the new entry into the new right/child page
1539 * (skip index in the new right page will not change)
1540 */
1542 /* if insert into middle, shift right remaining entries */
1550 /* update page header */
1558 XTENTRYSTART;
1559 }
1561 /*
1562 * reset the root
1563 *
1564 * init root with the single entry for the new right page
1565 * set the 1st entry offset to 0, which force the left-most key
1566 * at any level of the tree to be less than any search key.
1567 */
1568 /*
1569 * acquire a transaction lock on the root page (in-memory inode);
1570 *
1571 * action: root split;
1572 */
1578 /* update page header of root */
1589 }
1595 }
1598 /*
1599 * xtExtend()
1600 *
1601 * function: extend in-place;
1602 *
1603 * note: existing extent may or may not have been committed.
1604 * caller is responsible for pager buffer cache update, and
1605 * working block allocation map update;
1606 * update pmap: alloc whole extended extent;
1607 */
1612 {
1617 s64 bn;
1622 s64 xaddr;
1628 /* there must exist extent to be extended */
1632 /* retrieve search result */
1639 }
1641 /* extension must be contiguous */
1647 }
1649 /*
1650 * acquire a transaction lock on the leaf page;
1651 *
1652 * action: xad insertion/extension;
1653 */
1658 }
1660 /* extend will overflow extent ? */
1665 /*
1666 * extent overflow: insert entry for new extent
1667 */
1668 //insertNew:
1673 /*
1674 * if the leaf page is full, insert the new entry and
1675 * propagate up the router entry for the new page from split
1676 *
1677 * The xtSplitUp() will insert the entry and unpin the leaf page.
1678 */
1680 /* xtSpliUp() unpins leaf pages */
1691 /* get back old page */
1695 /*
1696 * if leaf root has been split, original root has been
1697 * copied to new child page, i.e., original entry now
1698 * resides on the new child page;
1699 */
1707 /* get new child page */
1716 }
1717 }
1718 }
1719 /*
1720 * insert the new entry into the leaf page
1721 */
1723 /* insert the new entry: mark the entry NEW */
1727 /* advance next available entry index */
1730 }
1732 /* get back old entry */
1736 /*
1737 * extend old extent
1738 */
1739 extendOld:
1750 }
1752 /* unpin the leaf page */
1756 }
1758 #ifdef _NOTYET
1759 /*
1760 * xtTailgate()
1761 *
1762 * function: split existing 'tail' extent
1763 * (split offset >= start offset of tail extent), and
1764 * relocate and extend the split tail half;
1765 *
1766 * note: existing extent may or may not have been committed.
1767 * caller is responsible for pager buffer cache update, and
1768 * working block allocation map update;
1769 * update pmap: free old split tail extent, alloc new extent;
1770 */
1776 {
1781 s64 bn;
1791 /*
1792 printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1793 (ulong)xoff, xlen, (ulong)xaddr);
1794 */
1796 /* there must exist extent to be tailgated */
1800 /* retrieve search result */
1807 }
1809 /* entry found must be last entry */
1816 }
1819 /*
1820 * acquire tlock of the leaf page containing original entry
1821 */
1825 }
1827 /* completely replace extent ? */
1829 /*
1830 printf("xtTailgate: xoff:0x%lx xlen:0x%x xaddr:0x%lx\n",
1831 (ulong)offsetXAD(xad), lengthXAD(xad), (ulong)addressXAD(xad));
1832 */
1836 /*
1837 * partially replace extent: insert entry for new extent
1838 */
1839 //insertNew:
1840 /*
1841 * if the leaf page is full, insert the new entry and
1842 * propagate up the router entry for the new page from split
1843 *
1844 * The xtSplitUp() will insert the entry and unpin the leaf page.
1845 */
1847 /* xtSpliUp() unpins leaf pages */
1858 /* get back old page */
1862 /*
1863 * if leaf root has been split, original root has been
1864 * copied to new child page, i.e., original entry now
1865 * resides on the new child page;
1866 */
1874 /* get new child page */
1883 }
1884 }
1885 }
1886 /*
1887 * insert the new entry into the leaf page
1888 */
1890 /* insert the new entry: mark the entry NEW */
1894 /* advance next available entry index */
1897 }
1899 /* get back old XAD */
1902 /*
1903 * truncate/relocate old extent at split offset
1904 */
1905 updateOld:
1906 /* update dmap for old/committed/truncated extent */
1909 /* free from PWMAP at commit */
1917 }
1919 /* free from WMAP */
1923 /* truncate */
1925 else
1926 /* replace */
1934 }
1936 /* unpin the leaf page */
1940 }
1943 /*
1944 * xtUpdate()
1945 *
1946 * function: update XAD;
1947 *
1948 * update extent for allocated_but_not_recorded or
1949 * compressed extent;
1950 *
1951 * parameter:
1952 * nxad - new XAD;
1953 * logical extent of the specified XAD must be completely
1954 * contained by an existing XAD;
1955 */
1962 s64 bn;
1975 /* there must exist extent to be tailgated */
1983 /* retrieve search result */
1990 }
1993 /*
1994 * acquire tlock of the leaf page containing original entry
1995 */
1999 }
2007 /* nXAD must be completely contained within XAD */
2014 }
2020 #ifdef _JFS_WIP_NOCOALESCE
2024 /*
2025 * replace XAD with nXAD
2026 */
2029 /* replace XAD with nXAD:recorded */
2038 /* #ifdef _JFS_WIP_COALESCE */
2042 /*
2043 * coalesce with left XAD
2044 */
2045 //coalesceLeft: /* (xoff == nxoff) */
2046 /* is XAD first entry of page ? */
2050 /* is nXAD logically and physically contiguous with lXAD ? */
2057 /* extend right lXAD */
2061 /* If we just merged two extents together, need to make sure the
2062 * right extent gets logged. If the left one is marked XAD_NEW,
2063 * then we know it will be logged. Otherwise, mark as
2064 * XAD_EXTENDED
2065 */
2070 /* truncate XAD */
2077 /* remove XAD */
2094 }
2095 }
2097 /*
2098 * replace XAD with nXAD
2099 */
2102 /* replace XAD with nXAD:recorded */
2110 /*
2111 * coalesce with right XAD
2112 */
2114 /* is XAD last entry of page ? */
2119 }
2121 /* is nXAD logically and physically contiguous with rXAD ? */
2128 /* extend left rXAD */
2133 /* If we just merged two extents together, need to make sure
2134 * the left extent gets logged. If the right one is marked
2135 * XAD_NEW, then we know it will be logged. Otherwise, mark as
2136 * XAD_EXTENDED
2137 */
2142 /* truncate XAD */
2146 /* remove XAD */
2153 }
2163 }
2164 /* #endif _JFS_WIP_COALESCE */
2166 /*
2167 * split XAD into (lXAD, nXAD):
2168 *
2169 * |---nXAD--->
2170 * --|----------XAD----------|--
2171 * |-lXAD-|
2172 */
2174 /* truncate old XAD as lXAD:not_recorded */
2178 /* insert nXAD:recorded */
2181 /* xtSpliUp() unpins leaf pages */
2192 /* get back old page */
2196 /*
2197 * if leaf root has been split, original root has been
2198 * copied to new child page, i.e., original entry now
2199 * resides on the new child page;
2200 */
2208 /* get new child page */
2217 }
2219 /* is nXAD on new page ? */
2222 newindex =
2223 newindex -
2225 XTENTRYSTART;
2227 }
2228 }
2230 /* if insert into middle, shift right remaining entries */
2235 /* insert the entry */
2240 /* advance next available entry index. */
2243 }
2245 /*
2246 * does nXAD force 3-way split ?
2247 *
2248 * |---nXAD--->|
2249 * --|----------XAD-------------|--
2250 * |-lXAD-| |-rXAD -|
2251 */
2255 /* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
2257 /* close out old page */
2264 }
2269 /* get new right page */
2278 }
2282 index++;
2290 /* recompute split pages */
2297 /* retrieve search result */
2304 }
2311 }
2312 }
2314 /*
2315 * split XAD into (nXAD, rXAD)
2316 *
2317 * ---nXAD---|
2318 * --|----------XAD----------|--
2319 * |-rXAD-|
2320 */
2322 /* update old XAD with nXAD:recorded */
2327 /* insert rXAD:not_recorded */
2332 /*
2333 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
2334 */
2335 /* xtSpliUp() unpins leaf pages */
2346 /* get back old page */
2351 /*
2352 * if leaf root has been split, original root has been
2353 * copied to new child page, i.e., original entry now
2354 * resides on the new child page;
2355 */
2363 /* get new child page */
2372 }
2373 }
2375 /* if insert into middle, shift right remaining entries */
2380 /* insert the entry */
2384 /* advance next available entry index. */
2387 }
2389 out:
2395 }
2397 /* unpin the leaf page */
2401 }
2404 /*
2405 * xtAppend()
2406 *
2407 * function: grow in append mode from contiguous region specified ;
2408 *
2409 * parameter:
2410 * tid - transaction id;
2411 * ip - file object;
2412 * xflag - extent flag:
2413 * xoff - extent offset;
2414 * maxblocks - max extent length;
2415 * xlen - extent length (in/out);
2416 * xaddrp - extent address pointer (in/out):
2417 * flag -
2418 *
2419 * return:
2420 */
2426 {
2447 /*
2448 * search for the entry location at which to insert:
2449 *
2450 * xtFastSearch() and xtSearch() both returns (leaf page
2451 * pinned, index at which to insert).
2452 * n.b. xtSearch() may return index of maxentry of
2453 * the full page.
2454 */
2458 /* retrieve search result */
2464 }
2465 //insert:
2466 /*
2467 * insert entry for new extent
2468 */
2471 /*
2472 * if the leaf page is full, split the page and
2473 * propagate up the router entry for the new page from split
2474 *
2475 * The xtSplitUp() will insert the entry and unpin the leaf page.
2476 */
2481 /*
2482 * allocate new index blocks to cover index page split(s)
2483 */
2497 }
2499 /* undo allocation */
2502 }
2506 /*
2507 * allocate data extent requested
2508 */
2519 /* undo data extent allocation */
2523 }
2529 /*
2530 * insert the new entry into the leaf page
2531 */
2532 insertLeaf:
2533 /*
2534 * allocate data extent requested
2535 */
2540 /*
2541 * acquire a transaction lock on the leaf page;
2542 *
2543 * action: xad insertion/extension;
2544 */
2548 /* insert the new entry: mark the entry NEW */
2552 /* advance next available entry index */
2564 out:
2565 /* unpin the leaf page */
2569 }
2570 #ifdef _STILL_TO_PORT
2572 /* - TBD for defragmentaion/reorganization -
2573 *
2574 * xtDelete()
2575 *
2576 * function:
2577 * delete the entry with the specified key.
2578 *
2579 * N.B.: whole extent of the entry is assumed to be deleted.
2580 *
2581 * parameter:
2582 *
2583 * return:
2584 * ENOENT: if the entry is not found.
2585 *
2586 * exception:
2587 */
2589 {
2593 s64 bn;
2600 /*
2601 * find the matching entry; xtSearch() pins the page
2602 */
2608 /* unpin the leaf page */
2611 }
2613 /*
2614 * delete the entry from the leaf page
2615 */
2620 /*
2621 * if the leaf page bocome empty, free the page
2622 */
2627 /*
2628 * acquire a transaction lock on the leaf page;
2629 *
2630 * action:xad deletion;
2631 */
2637 /* if delete from middle, shift left/compact the remaining entries */
2645 }
2648 /* - TBD for defragmentaion/reorganization -
2649 *
2650 * xtDeleteUp()
2651 *
2652 * function:
2653 * free empty pages as propagating deletion up the tree
2654 *
2655 * parameter:
2656 *
2657 * return:
2658 */
2659 static int
2662 {
2667 s64 xaddr;
2673 /*
2674 * keep root leaf page which has become empty
2675 */
2677 /* keep the root page */
2682 /* XT_PUTPAGE(fmp); */
2685 }
2687 /*
2688 * free non-root leaf page
2689 */
2693 }
2697 /* free the page extent */
2700 /* free the buffer page */
2703 /*
2704 * propagate page deletion up the index tree
2705 *
2706 * If the delete from the parent page makes it empty,
2707 * continue all the way up the tree.
2708 * stop if the root page is reached (which is never deleted) or
2709 * if the entry deletion does not empty the page.
2710 */
2712 /* get/pin the parent page <sp> */
2719 /* delete the entry for the freed child page from parent.
2720 */
2723 /*
2724 * the parent has the single entry being deleted:
2725 * free the parent page which has become empty.
2726 */
2729 /* keep the root page */
2735 /* XT_PUTPAGE(mp); */
2739 /* free the parent page */
2744 /* free the page extent */
2748 /* unpin/free the buffer page */
2751 /* propagate up */
2753 }
2754 }
2755 /*
2756 * the parent has other entries remaining:
2757 * delete the router entry from the parent page.
2758 */
2761 /*
2762 * acquire a transaction lock on the leaf page;
2763 *
2764 * action:xad deletion;
2765 */
2773 /* if delete from middle,
2774 * shift left/compact the remaining entries in the page
2775 */
2786 }
2788 /* unpin the parent page */
2791 /* exit propagation up */
2793 }
2796 }
2799 /*
2800 * NAME: xtRelocate()
2801 *
2802 * FUNCTION: relocate xtpage or data extent of regular file;
2803 * This function is mainly used by defragfs utility.
2804 *
2805 * NOTE: This routine does not have the logic to handle
2806 * uncommitted allocated extent. The caller should call
2807 * txCommit() to commit all the allocation before call
2808 * this routine.
2809 */
2810 int
2829 s64 bn;
2841 /* validate extent offset */
2849 /*
2850 * 1. get and validate the parent xtpage/xad entry
2851 * covering the source extent to be relocated;
2852 */
2854 /* search in leaf entry */
2859 /* retrieve search result */
2865 }
2867 /* validate for exact match with a single entry */
2872 }
2875 /* search in internal entry */
2880 /* retrieve search result */
2886 }
2888 /* xtSearchNode() validated for exact match with a single entry
2889 */
2891 }
2894 /*
2895 * 2. relocate the extent
2896 */
2898 /* if the extent is allocated-but-not-recorded
2899 * there is no real data to be moved in this extent,
2900 */
2903 else
2904 /* release xtpage for cmRead()/xtLookup() */
2907 /*
2908 * cmRelocate()
2909 *
2910 * copy target data pages to be relocated;
2911 *
2912 * data extent must start at page boundary and
2913 * multiple of page size (except the last data extent);
2914 * read in each page of the source data extent into cbuf,
2915 * update the cbuf extent descriptor of the page to be
2916 * homeward bound to new dst data extent
2917 * copy the data from the old extent to new extent.
2918 * copy is essential for compressed files to avoid problems
2919 * that can arise if there was a change in compression
2920 * algorithms.
2921 * it is a good strategy because it may disrupt cache
2922 * policy to keep the pages in memory afterwards.
2923 */
2929 /*
2930 npages = ((offset + nbytes - 1) >> CM_L2BSIZE) -
2931 (offset >> CM_L2BSIZE) + 1;
2932 */
2936 /* process the request one cache buffer at a time */
2939 /* compute page size */
2942 /* get the cache buffer of the page */
2949 /* bind buffer with the new extent address */
2953 /* release the cbuf, mark it as modified */
2958 }
2960 /* get back parent page */
2968 /*
2969 * read in the target xtpage from the source extent;
2970 */
2975 }
2977 /*
2978 * read in sibling pages if any to update sibling pointers;
2979 */
2988 }
2989 }
3001 }
3002 }
3004 /* at this point, all xtpages to be updated are in memory */
3006 /*
3007 * update sibling pointers of sibling xtpages if any;
3008 */
3011 tlck =
3015 }
3019 tlck =
3023 }
3025 /*
3026 * update the target xtpage to be relocated
3027 *
3028 * update the self address of the target page
3029 * and write to destination extent;
3030 * redo image covers the whole xtpage since it is new page
3031 * to the destination extent;
3032 * update of bmap for the free of source extent
3033 * of the target xtpage itself:
3034 * update of bmap for the allocation of destination extent
3035 * of the target xtpage itself:
3036 * update of bmap for the extents covered by xad entries in
3037 * the target xtpage is not necessary since they are not
3038 * updated;
3039 * if not committed before this relocation,
3040 * target page may contain XAD_NEW entries which must
3041 * be scanned for bmap update (logredo() always
3042 * scan xtpage REDOPAGE image for bmap update);
3043 * if committed before this relocation (tlckRELOCATE),
3044 * scan may be skipped by commit() and logredo();
3045 */
3047 /* tlckNEW init xtlck->lwm.offset = XTENTRYSTART; */
3051 /* update the self address in the xtpage header */
3055 /* linelock for the after image of the whole page */
3059 /* update the buffer extent descriptor of target xtpage */
3063 /* unpin the target page to new homeward bound */
3066 }
3068 /*
3069 * 3. acquire maplock for the source extent to be freed;
3070 *
3071 * acquire a maplock saving the src relocated extent address;
3072 * to free of the extent at commit time;
3073 */
3074 out:
3075 /* if DATAEXT relocation, write a LOG_UPDATEMAP record for
3076 * free PXD of the source data extent (logredo() will update
3077 * bmap for free of source data extent), and update bmap for
3078 * free of the source data extent;
3079 */
3082 /* if XTPAGE relocation, write a LOG_NOREDOPAGE record
3083 * for the source xtpage (logredo() will init NoRedoPage
3084 * filter and will also update bmap for free of the source
3085 * xtpage), and update bmap for free of the source xtpage;
3086 * N.B. We use tlckMAP instead of tlkcXTREE because there
3087 * is no buffer associated with this lock since the buffer
3088 * has been redirected to the target location.
3089 */
3099 /*
3100 * 4. update the parent xad entry for relocation;
3101 *
3102 * acquire tlck for the parent entry with XAD_NEW as entry
3103 * update which will write LOG_REDOPAGE and update bmap for
3104 * allocation of XAD_NEW destination extent;
3105 */
3111 /* update the XAD with the new destination extent; */
3120 /* unpin the parent xtpage */
3124 }
3127 /*
3128 * xtSearchNode()
3129 *
3130 * function: search for the internal xad entry covering specified extent.
3131 * This function is mainly used by defragfs utility.
3132 *
3133 * parameters:
3134 * ip - file object;
3135 * xad - extent to find;
3136 * cmpp - comparison result:
3137 * btstack - traverse stack;
3138 * flag - search process flag;
3139 *
3140 * returns:
3141 * btstack contains (bn, index) of search path traversed to the entry.
3142 * *cmpp is set to result of comparison with the entry returned.
3143 * the page containing the entry is pinned at exit.
3144 */
3147 {
3157 s64 t64;
3165 /*
3166 * search down tree from root:
3167 *
3168 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
3169 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
3170 *
3171 * if entry with search key K is not found
3172 * internal page search find the entry with largest key Ki
3173 * less than K which point to the child page to search;
3174 * leaf page search find the entry with smallest key Kj
3175 * greater than K so that the returned index is the position of
3176 * the entry to be shifted right for insertion of new entry.
3177 * for empty tree, search key is greater than any key of the tree.
3178 *
3179 * by convention, root bn = 0.
3180 */
3182 /* get/pin the page to search */
3189 }
3193 /*
3194 * binary search with search key K on the current page
3195 */
3201 /*
3202 * search hit
3203 *
3204 * verify for exact match;
3205 */
3210 /* save search result */
3217 }
3219 /* descend/search its child page */
3221 }
3226 }
3227 }
3229 /*
3230 * search miss - non-leaf page:
3231 *
3232 * base is the smallest index with key (Kj) greater than
3233 * search key (K) and may be zero or maxentry index.
3234 * if base is non-zero, decrement base by one to get the parent
3235 * entry of the child page to search.
3236 */
3239 /*
3240 * go down to child page
3241 */
3242 next:
3243 /* get the child page block number */
3246 /* unpin the parent page */
3248 }
3249 }
3252 /*
3253 * xtRelink()
3254 *
3255 * function:
3256 * link around a freed page.
3257 *
3258 * Parameter:
3259 * int tid,
3260 * struct inode *ip,
3261 * xtpage_t *p)
3262 *
3263 * returns:
3264 */
3266 {
3275 /* update prev pointer of the next page */
3281 /*
3282 * acquire a transaction lock on the page;
3283 *
3284 * action: update prev pointer;
3285 */
3289 /* the page may already have been tlock'd */
3294 }
3296 /* update next pointer of the previous page */
3302 /*
3303 * acquire a transaction lock on the page;
3304 *
3305 * action: update next pointer;
3306 */
3310 /* the page may already have been tlock'd */
3315 }
3318 }
3322 /*
3323 * xtInitRoot()
3324 *
3325 * initialize file root (inline in inode)
3326 */
3328 {
3331 /*
3332 * acquire a transaction lock on the root
3333 *
3334 * action:
3335 */
3348 }
3352 }
3355 /*
3356 * We can run into a deadlock truncating a file with a large number of
3357 * xtree pages (large fragmented file). A robust fix would entail a
3358 * reservation system where we would reserve a number of metadata pages
3359 * and tlocks which we would be guaranteed without a deadlock. Without
3360 * this, a partial fix is to limit number of metadata pages we will lock
3361 * in a single transaction. Currently we will truncate the file so that
3362 * no more than 50 leaf pages will be locked. The caller of xtTruncate
3363 * will be responsible for ensuring that the current transaction gets
3364 * committed, and that subsequent transactions are created to truncate
3365 * the file further if needed.
3366 */
3367 #define MAX_TRUNCATE_LEAVES 50
3369 /*
3370 * xtTruncate()
3371 *
3372 * function:
3373 * traverse for truncation logging backward bottom up;
3374 * terminate at the last extent entry at the current subtree
3375 * root page covering new down size.
3376 * truncation may occur within the last extent entry.
3377 *
3378 * parameter:
3379 * int tid,
3380 * struct inode *ip,
3381 * s64 newsize,
3382 * int type) {PWMAP, PMAP, WMAP; DELETE, TRUNCATE}
3383 *
3384 * return:
3385 *
3386 * note:
3387 * PWMAP:
3388 * 1. truncate (non-COMMIT_NOLINK file)
3389 * by jfs_truncate() or jfs_open(O_TRUNC):
3390 * xtree is updated;
3391 * 2. truncate index table of directory when last entry removed
3392 * map update via tlock at commit time;
3393 * PMAP:
3394 * Call xtTruncate_pmap instead
3395 * WMAP:
3396 * 1. remove (free zero link count) on last reference release
3397 * (pmap has been freed at commit zero link count);
3398 * 2. truncate (COMMIT_NOLINK file, i.e., tmp file):
3399 * xtree is updated;
3400 * map update directly at truncation time;
3401 *
3402 * if (DELETE)
3403 * no LOG_NOREDOPAGE is required (NOREDOFILE is sufficient);
3404 * else if (TRUNCATE)
3405 * must write LOG_NOREDOPAGE for deleted index page;
3406 *
3407 * pages may already have been tlocked by anonymous transactions
3408 * during file growth (i.e., write) before truncation;
3409 *
3410 * except last truncated entry, deleted entries remains as is
3411 * in the page (nextindex is updated) for other use
3412 * (e.g., log/update allocation map): this avoid copying the page
3413 * info but delay free of pages;
3414 *
3415 */
3417 {
3419 s64 teof;
3422 s64 bn;
3434 s64 nfreed;
3438 /* save object truncation type */
3442 }
3455 }
3457 /*
3458 * if the newsize is not an integral number of pages,
3459 * the file between newsize and next page boundary will
3460 * be cleared.
3461 * if truncating into a file hole, it will cause
3462 * a full block to be allocated for the logical block.
3463 */
3465 /*
3466 * release page blocks of truncated region <teof, eof>
3467 *
3468 * free the data blocks from the leaf index blocks.
3469 * delete the parent index entries corresponding to
3470 * the freed child data/index blocks.
3471 * free the index blocks themselves which aren't needed
3472 * in new sized file.
3473 *
3474 * index blocks are updated only if the blocks are to be
3475 * retained in the new sized file.
3476 * if type is PMAP, the data and index pages are NOT
3477 * freed, and the data and index blocks are NOT freed
3478 * from working map.
3479 * (this will allow continued access of data/index of
3480 * temporary file (zerolink count file truncated to zero-length)).
3481 */
3485 /* clear stack */
3488 /*
3489 * start with root
3490 *
3491 * root resides in the inode
3492 */
3495 /*
3496 * first access of each page:
3497 */
3498 getPage:
3503 /* process entries backward from last index */
3509 /*
3510 * leaf page
3511 */
3513 /* Since this is the rightmost leaf, and we may have already freed
3514 * a page that was formerly to the right, let's make sure that the
3515 * next pointer is zero.
3516 */
3519 /*
3520 * Make sure this change to the header is logged.
3521 * If we really truncate this leaf, the flag
3522 * will be changed to tlckTRUNCATE
3523 */
3527 }
3531 /* does region covered by leaf page precede Teof ? */
3538 }
3540 /* (re)acquire tlock of the leaf page */
3543 /*
3544 * We need to limit the size of the transaction
3545 * to avoid exhausting pagecache & tlocks
3546 */
3550 }
3555 }
3558 /*
3559 * scan backward leaf page entries
3560 */
3567 /*
3568 * The "data" for a directory is indexed by the block
3569 * device's address space. This metadata must be invalidated
3570 * here
3571 */
3574 /*
3575 * entry beyond eof: continue scan of current page
3576 * xad
3577 * ---|---=======------->
3578 * eof
3579 */
3583 }
3585 /*
3586 * (xoff <= teof): last entry to be deleted from page;
3587 * If other entries remain in page: keep and update the page.
3588 */
3590 /*
3591 * eof == entry_start: delete the entry
3592 * xad
3593 * -------|=======------->
3594 * eof
3595 *
3596 */
3604 }
3605 /*
3606 * eof within the entry: truncate the entry.
3607 * xad
3608 * -------===|===------->
3609 * eof
3610 */
3612 /* update truncated entry */
3617 /* save pxd of truncated extent in tlck */
3629 }
3630 /* free truncated extent */
3639 /* reset map lock */
3641 }
3643 /* current entry is new last entry; */
3647 }
3648 /*
3649 * eof beyond the entry:
3650 * xad
3651 * -------=======---|--->
3652 * eof
3653 */
3657 }
3664 nextindex;
3667 }
3669 }
3673 /* assert(freed == 0); */
3679 /*
3680 * leaf page become empty: free the page if type != PMAP
3681 */
3683 /* txCommit() with tlckFREE:
3684 * free data extents covered by leaf [XTENTRYSTART:hwm);
3685 * invalidate leaf if COMMIT_PWMAP;
3686 * if (TRUNCATE), will write LOG_NOREDOPAGE;
3687 */
3691 /* free data extents covered by leaf */
3696 }
3707 /* page will be invalidated at tx completion
3708 */
3715 /* invalidate empty leaf page */
3717 }
3718 }
3720 /*
3721 * the leaf page become empty: delete the parent entry
3722 * for the leaf page if the parent page is to be kept
3723 * in the new sized file.
3724 */
3726 /*
3727 * go back up to the parent page
3728 */
3729 getParent:
3730 /* pop/restore parent entry for the current child page */
3732 /* current page must have been root */
3735 /* get back the parent page */
3743 /*
3744 * child page was not empty:
3745 */
3747 /* has any entry deleted from parent ? */
3749 /* (re)acquire tlock on the parent page */
3751 /* txCommit() with tlckTRUNCATE:
3752 * free child extents covered by parent [);
3753 */
3762 }
3765 /* free child extents covered by parent */
3772 }
3776 }
3779 }
3781 /*
3782 * child page was empty:
3783 */
3786 /*
3787 * During working map update, child page's tlock must be handled
3788 * before parent's. This is because the parent's tlock will cause
3789 * the child's disk space to be marked available in the wmap, so
3790 * it's important that the child page be released by that time.
3791 *
3792 * ToDo: tlocks should be on doubly-linked list, so we can
3793 * quickly remove it and add it to the end.
3794 */
3796 /*
3797 * Move parent page's tlock to the end of the tid's tlock list
3798 */
3813 }
3815 }
3819 }
3821 /*
3822 * parent page become empty: free the page
3823 */
3826 /* txCommit() with tlckFREE:
3827 * free child extents covered by parent;
3828 * invalidate parent if COMMIT_PWMAP;
3829 */
3837 /* free child extents covered by parent */
3841 XTENTRYSTART;
3843 COMMIT_WMAP);
3844 }
3852 /*
3853 * Shrink root down to allow inline
3854 * EA (otherwise fsck complains)
3855 */
3859 }
3865 /* page will be invalidated at tx completion
3866 */
3872 tlckFREELOCK;
3874 /* invalidate parent page */
3876 }
3878 /* parent has become empty and freed:
3879 * go back up to its parent page
3880 */
3881 /* freed = 1; */
3883 }
3884 }
3885 /*
3886 * parent page still has entries for front region;
3887 */
3889 /* try truncate region covered by preceding entry
3890 * (process backward)
3891 */
3892 index--;
3894 /* go back down to the child page corresponding
3895 * to the entry
3896 */
3898 }
3900 /*
3901 * internal page: go down to child page of current entry
3902 */
3903 getChild:
3904 /* save current parent entry for the child page */
3907 /* get child page */
3911 /*
3912 * first access of each internal entry:
3913 */
3914 /* release parent page */
3917 /* process the child page */
3920 out:
3921 /*
3922 * update file resource stat
3923 */
3924 /* set size
3925 */
3928 else
3931 /* update quota allocation to reflect freed blocks */
3934 /*
3935 * free tlock of invalidated pages
3936 */
3941 }
3944 /*
3945 * xtTruncate_pmap()
3946 *
3947 * function:
3948 * Perform truncate to zero lenghth for deleted file, leaving the
3949 * the xtree and working map untouched. This allows the file to
3950 * be accessed via open file handles, while the delete of the file
3951 * is committed to disk.
3952 *
3953 * parameter:
3954 * tid_t tid,
3955 * struct inode *ip,
3956 * s64 committed_size)
3957 *
3958 * return: new committed size
3959 *
3960 * note:
3961 *
3962 * To avoid deadlock by holding too many transaction locks, the
3963 * truncation may be broken up into multiple transactions.
3964 * The committed_size keeps track of part of the file has been
3965 * freed from the pmaps.
3966 */
3968 {
3969 s64 bn;
3982 s64 xoff;
3985 /* save object truncation type */
3989 /* clear stack */
4005 }
4007 /*
4008 * start with root
4009 *
4010 * root resides in the inode
4011 */
4014 /*
4015 * first access of each page:
4016 */
4017 getPage:
4022 /* process entries backward from last index */
4027 }
4029 /*
4030 * leaf page
4031 */
4034 /*
4035 * We need to limit the size of the transaction
4036 * to avoid exhausting pagecache & tlocks
4037 */
4043 }
4052 /*
4053 * go back up to the parent page
4054 */
4055 getParent:
4056 /* pop/restore parent entry for the current child page */
4058 /* current page must have been root */
4061 /* get back the parent page */
4069 /*
4070 * parent page become empty: free the page
4071 */
4073 /* txCommit() with tlckFREE:
4074 * free child extents covered by parent;
4075 * invalidate parent if COMMIT_PWMAP;
4076 */
4090 }
4091 }
4092 /*
4093 * parent page still has entries for front region;
4094 */
4095 else
4096 index--;
4097 /*
4098 * internal page: go down to child page of current entry
4099 */
4100 getChild:
4101 /* save current parent entry for the child page */
4104 /* get child page */
4108 /*
4109 * first access of each internal entry:
4110 */
4111 /* release parent page */
4114 /* process the child page */
4117 out:
4120 }
4123 #ifdef _JFS_DEBUG_XTREE
4124 /*
4125 * xtDisplayTree()
4126 *
4127 * function: traverse forward
4128 */
4130 {
4143 /* clear stack */
4146 /*
4147 * start with root
4148 *
4149 * root resides in the inode
4150 */
4154 /*
4155 * first access of each page:
4156 */
4157 getPage:
4162 /* process entries forward from first index */
4167 /*
4168 * first access of each internal page
4169 */
4173 /*
4174 * first access of each leaf page
4175 */
4179 /* unpin the leaf page */
4181 }
4183 /*
4184 * go back up to the parent page
4185 */
4186 getParent:
4187 /* pop/restore parent entry for the current child page */
4189 /* current page must have been root */
4192 /*
4193 * parent page scan completed
4194 */
4196 /* go back up to the parent page */
4198 }
4200 /*
4201 * parent page has entries remaining
4202 */
4203 /* get back the parent page */
4205 /* v = parent->level; */
4210 /* get next parent entry */
4211 index++;
4213 /*
4214 * internal page: go down to child page of current entry
4215 */
4216 getChild:
4217 /* push/save current parent entry for the child page */
4221 /* btsp->level = v; */
4222 /* btsp->node = h; */
4225 /* get child page */
4229 /*
4230 * first access of each internal entry:
4231 */
4232 /* release parent page */
4237 v++;
4240 /* process the child page */
4242 }
4245 /*
4246 * xtDisplayPage()
4247 *
4248 * function: display page
4249 */
4251 {
4257 /* display page control */
4262 /* display entries */
4275 }
4276 }
4279 }
4283 #ifdef _JFS_WIP
4284 /*
4285 * xtGather()
4286 *
4287 * function:
4288 * traverse for allocation acquiring tlock at commit time
4289 * (vs at the time of update) logging backward top down
4290 *
4291 * note:
4292 * problem - establishing that all new allocation have been
4293 * processed both for append and random write in sparse file
4294 * at the current entry at the current subtree root page
4295 *
4296 */
4298 {
4301 u64 bn;
4307 /* clear stack */
4310 /*
4311 * start with root
4312 *
4313 * root resides in the inode
4314 */
4320 /* new root is NOT pointed by a new entry
4321 if (p->header.flag & NEW)
4322 allocate new page lock;
4323 write a NEWPAGE log;
4324 */
4326 dopage:
4327 /*
4328 * first access of each page:
4329 */
4330 /* process entries backward from last index */
4334 /*
4335 * first access of each leaf page
4336 */
4337 /* process leaf page entries backward */
4340 /*
4341 * if newpage, log NEWPAGE.
4342 *
4343 if (e->flag & XAD_NEW) {
4344 nfound =+ entry->length;
4345 update current page lock for the entry;
4346 newpage(entry);
4347 *
4348 * if moved, log move.
4349 *
4350 } else if (e->flag & XAD_MOVED) {
4351 reset flag;
4352 update current page lock for the entry;
4353 }
4354 */
4355 }
4357 /* unpin the leaf page */
4360 /*
4361 * go back up to the parent page
4362 */
4363 getParent:
4364 /* restore parent entry for the current child page */
4366 /* current page must have been root */
4370 /*
4371 * parent page scan completed
4372 */
4373 /* go back up to the parent page */
4376 /*
4377 * parent page has entries remaining
4378 */
4379 /* get back the parent page */
4385 /* first subroot page which
4386 * covers all new allocated blocks
4387 * itself not new/modified.
4388 * (if modified from split of descendent,
4389 * go down path of split page)
4391 if (nfound == nnew &&
4392 !(p->header.flag & (NEW | MOD)))
4393 exit scan;
4394 */
4396 /* process parent page entries backward */
4397 index--;
4398 }
4400 /*
4401 * first access of each internal page
4402 */
4403 }
4405 /*
4406 * internal page: go down to child page of current entry
4407 */
4409 /* save current parent entry for the child page */
4412 /* get current entry for the child page */
4415 /*
4416 * first access of each internal entry:
4417 */
4418 /*
4419 * if new entry, log btree_tnewentry.
4420 *
4421 if (e->flag & XAD_NEW)
4422 update parent page lock for the entry;
4423 */
4425 /* release parent page */
4428 /* get child page */
4434 /*
4435 * first access of each non-root page:
4436 */
4437 /*
4438 * if new, log btree_newpage.
4439 *
4440 if (p->header.flag & NEW)
4441 allocate new page lock;
4442 write a NEWPAGE log (next, prev);
4443 */
4445 /* process the child page */
4448 out:
4450 }
4454 #ifdef CONFIG_JFS_STATISTICS
4457 {
4459 off_t begin;
4477 else
4484 }
4485 #endif