| blob | ac41f72d6d502fd22bcba1181a84b1c90a9d4584 |
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 */
19 /*
20 * jfs_dtree.c: directory B+-tree manager
21 *
22 * B+-tree with variable length key directory:
23 *
24 * each directory page is structured as an array of 32-byte
25 * directory entry slots initialized as a freelist
26 * to avoid search/compaction of free space at insertion.
27 * when an entry is inserted, a number of slots are allocated
28 * from the freelist as required to store variable length data
29 * of the entry; when the entry is deleted, slots of the entry
30 * are returned to freelist.
31 *
32 * leaf entry stores full name as key and file serial number
33 * (aka inode number) as data.
34 * internal/router entry stores sufffix compressed name
35 * as key and simple extent descriptor as data.
36 *
37 * each directory page maintains a sorted entry index table
38 * which stores the start slot index of sorted entries
39 * to allow binary search on the table.
40 *
41 * directory starts as a root/leaf page in on-disk inode
42 * inline data area.
43 * when it becomes full, it starts a leaf of a external extent
44 * of length of 1 block. each time the first leaf becomes full,
45 * it is extended rather than split (its size is doubled),
46 * until its length becoms 4 KBytes, from then the extent is split
47 * with new 4 Kbyte extent when it becomes full
48 * to reduce external fragmentation of small directories.
49 *
50 * blah, blah, blah, for linear scan of directory in pieces by
51 * readdir().
52 *
53 *
54 * case-insensitive directory file system
55 *
56 * names are stored in case-sensitive way in leaf entry.
57 * but stored, searched and compared in case-insensitive (uppercase) order
58 * (i.e., both search key and entry key are folded for search/compare):
59 * (note that case-sensitive order is BROKEN in storage, e.g.,
60 * sensitive: Ad, aB, aC, aD -> insensitive: aB, aC, aD, Ad
61 *
62 * entries which folds to the same key makes up a equivalent class
63 * whose members are stored as contiguous cluster (may cross page boundary)
64 * but whose order is arbitrary and acts as duplicate, e.g.,
65 * abc, Abc, aBc, abC)
66 *
67 * once match is found at leaf, requires scan forward/backward
68 * either for, in case-insensitive search, duplicate
69 * or for, in case-sensitive search, for exact match
70 *
71 * router entry must be created/stored in case-insensitive way
72 * in internal entry:
73 * (right most key of left page and left most key of right page
74 * are folded, and its suffix compression is propagated as router
75 * key in parent)
76 * (e.g., if split occurs <abc> and <aBd>, <ABD> trather than <aB>
77 * should be made the router key for the split)
78 *
79 * case-insensitive search:
80 *
81 * fold search key;
82 *
83 * case-insensitive search of B-tree:
84 * for internal entry, router key is already folded;
85 * for leaf entry, fold the entry key before comparison.
86 *
87 * if (leaf entry case-insensitive match found)
88 * if (next entry satisfies case-insensitive match)
89 * return EDUPLICATE;
90 * if (prev entry satisfies case-insensitive match)
91 * return EDUPLICATE;
92 * return match;
93 * else
94 * return no match;
95 *
96 * serialization:
97 * target directory inode lock is being held on entry/exit
98 * of all main directory service routines.
99 *
100 * log based recovery:
101 */
103 #include <linux/fs.h>
104 #include <linux/quotaops.h>
113 /* dtree split parameter */
116 s16 index;
117 s16 nslot;
121 };
123 #define DT_PAGE(IP, MP) BT_PAGE(IP, MP, dtpage_t, i_dtroot)
125 /* get page buffer for specified block address */
126 #define DT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
127 {\
128 BT_GETPAGE(IP, BN, MP, dtpage_t, SIZE, P, RC, i_dtroot)\
129 if (!(RC))\
130 {\
131 if (((P)->header.nextindex > (((BN)==0)?DTROOTMAXSLOT:(P)->header.maxslot)) ||\
132 ((BN) && ((P)->header.maxslot > DTPAGEMAXSLOT)))\
133 {\
134 BT_PUTPAGE(MP);\
136 MP = NULL;\
137 RC = -EIO;\
138 }\
139 }\
140 }
142 /* for consistency */
143 #define DT_PUTPAGE(MP) BT_PUTPAGE(MP)
145 #define DT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
146 BT_GETSEARCH(IP, LEAF, BN, MP, dtpage_t, P, INDEX, i_dtroot)
148 /*
149 * forward references
150 */
197 #define ciToUpper(c) UniStrupr((c)->name)
199 /*
200 * read_index_page()
201 *
202 * Reads a page of a directory's index table.
203 * Having metadata mapped into the directory inode's address space
204 * presents a multitude of problems. We avoid this by mapping to
205 * the absolute address space outside of the *_metapage routines
206 */
208 {
210 s64 xaddr;
212 s32 xlen;
219 }
221 /*
222 * get_index_page()
223 *
224 * Same as get_index_page(), but get's a new page without reading
225 */
227 {
229 s64 xaddr;
231 s32 xlen;
238 }
240 /*
241 * find_index()
242 *
243 * Returns dtree page containing directory table entry for specified
244 * index and pointer to its entry.
245 *
246 * mp must be released by caller.
247 */
250 {
252 s64 blkno;
253 s64 offset;
261 maxWarnings--;
262 }
264 }
269 }
272 /*
273 * Inline directory table
274 */
286 }
290 }
294 }
296 slot =
298 page_offset);
299 }
301 }
304 u32 index)
305 {
317 /*
318 * Linelock slot size is twice the size of directory table
319 * slot size. 512 entries per page.
320 */
324 }
326 /*
327 * add_index()
328 *
329 * Adds an entry to the directory index table. This is used to provide
330 * each directory entry with a persistent index in which to resume
331 * directory traversals
332 */
334 {
338 u64 blkno;
340 u32 index;
344 s64 offset;
345 uint page_offset;
347 s64 xaddr;
355 }
360 /*
361 * i_size reflects size of index table, or 8 bytes per entry.
362 */
365 /*
366 * dir table fits inline within inode
367 */
376 }
380 /*
381 * It's time to move the inline table to an external
382 * page and begin to build the xtree
383 */
388 /*
389 * Save the table, we're going to overwrite it with the
390 * xtree root
391 */
394 /*
395 * Initialize empty x-tree
396 */
399 /*
400 * Allocate the first block & add it to the xtree
401 */
403 /* This really shouldn't fail */
408 }
417 }
432 /*
433 * Logging is now directed by xtree tlocks
434 */
436 }
442 /*
443 * This will be the beginning of a new page
444 */
449 }
454 else
462 }
466 dirtab_slot =
477 clean_up:
482 }
484 /*
485 * free_index()
486 *
487 * Marks an entry to the directory index table as free.
488 */
490 {
492 s64 lblock;
510 }
512 /*
513 * modify_index()
514 *
515 * Changes an entry in the directory index table
516 */
519 {
535 }
537 /*
538 * read_index()
539 *
540 * reads a directory table slot
541 */
544 {
545 s64 lblock;
552 }
560 }
562 /*
563 * dtSearch()
564 *
565 * function:
566 * Search for the entry with specified key
567 *
568 * parameter:
569 *
570 * return: 0 - search result on stack, leaf page pinned;
571 * errno - I/O error
572 */
575 {
578 s64 bn;
586 ino_t inumber;
592 GFP_NOFS);
596 }
599 /* uppercase search key for c-i directory */
603 /* only uppercase if case-insensitive support is on */
606 }
609 /* init level count for max pages to split */
612 /*
613 * search down tree from root:
614 *
615 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
616 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
617 *
618 * if entry with search key K is not found
619 * internal page search find the entry with largest key Ki
620 * less than K which point to the child page to search;
621 * leaf page search find the entry with smallest key Kj
622 * greater than K so that the returned index is the position of
623 * the entry to be shifted right for insertion of new entry.
624 * for empty tree, search key is greater than any key of the tree.
625 *
626 * by convention, root bn = 0.
627 */
629 /* get/pin the page to search */
634 /* get sorted entry table of the page */
637 /*
638 * binary search with search key K on the current page.
639 */
644 /* uppercase leaf name to compare */
645 cmp =
649 /* router key is in uppercase */
654 }
656 /*
657 * search hit
658 */
659 /* search hit - leaf page:
660 * return the entry found
661 */
666 /*
667 * search for JFS_LOOKUP
668 */
673 }
675 /*
676 * search for JFS_CREATE
677 */
682 }
684 /*
685 * search for JFS_REMOVE or JFS_RENAME
686 */
692 }
694 /*
695 * JFS_REMOVE|JFS_FINDDIR|JFS_RENAME
696 */
697 /* save search result */
706 }
708 /* search hit - internal page:
709 * descend/search its child page
710 */
712 }
717 }
718 }
720 /*
721 * search miss
722 *
723 * base is the smallest index with key (Kj) greater than
724 * search key (K) and may be zero or (maxindex + 1) index.
725 */
726 /*
727 * search miss - leaf page
728 *
729 * return location of entry (base) where new entry with
730 * search key K is to be inserted.
731 */
733 /*
734 * search for JFS_LOOKUP, JFS_REMOVE, or JFS_RENAME
735 */
740 }
742 /*
743 * search for JFS_CREATE|JFS_FINDDIR:
744 *
745 * save search result
746 */
755 }
757 /*
758 * search miss - internal page
759 *
760 * if base is non-zero, decrement base by one to get the parent
761 * entry of the child page to search.
762 */
765 /*
766 * go down to child page
767 */
768 getChild:
769 /* update max. number of pages to split */
771 /* Something's corrupted, mark filesytem dirty so
772 * chkdsk will fix it.
773 */
778 }
781 /* push (bn, index) of the parent page/entry */
784 /* get the child page block number */
789 /* unpin the parent page */
791 }
793 out:
796 dtSearch_Exit1:
800 dtSearch_Exit2:
803 }
806 /*
807 * dtInsert()
808 *
809 * function: insert an entry to directory tree
810 *
811 * parameter:
812 *
813 * return: 0 - success;
814 * errno - failure;
815 */
818 {
822 s64 bn;
825 ddata_t data;
831 /*
832 * retrieve search result
833 *
834 * dtSearch() returns (leaf page pinned, index at which to insert).
835 * n.b. dtSearch() may return index of (maxindex + 1) of
836 * the full page.
837 */
840 /*
841 * insert entry for new key
842 */
847 }
854 }
857 /*
858 * leaf page does not have enough room for new entry:
859 *
860 * extend/split the leaf page;
861 *
862 * dtSplitUp() will insert the entry and unpin the leaf page.
863 */
872 }
874 /*
875 * leaf page does have enough room for new entry:
876 *
877 * insert the new data entry into the leaf page;
878 */
880 /*
881 * acquire a transaction lock on the leaf page
882 */
888 /* linelock header */
895 /* linelock stbl of non-root leaf page */
905 }
907 /* unpin the leaf page */
911 }
914 /*
915 * dtSplitUp()
916 *
917 * function: propagate insertion bottom up;
918 *
919 * parameter:
920 *
921 * return: 0 - success;
922 * errno - failure;
923 * leaf page unpinned;
924 */
927 {
951 /* get split page */
957 GFP_NOFS);
962 }
964 /*
965 * split leaf page
966 *
967 * The split routines insert the new entry, and
968 * acquire txLock as appropriate.
969 */
970 /*
971 * split root leaf page:
972 */
974 /*
975 * allocate a single extent child page
976 */
982 xlen++;
986 }
998 else
1004 }
1006 /*
1007 * extend first leaf page
1008 *
1009 * extend the 1st extent if less than buffer page size
1010 * (dtExtendPage() reurns leaf page unpinned)
1011 */
1021 else
1024 /* Allocate blocks to quota. */
1028 }
1044 /* free relocated extent */
1048 /* free extended delta */
1052 }
1053 }
1055 extendOut:
1058 }
1060 /*
1061 * split leaf page <sp> into <sp> and a new right page <rp>.
1062 *
1063 * return <rp> pinned and its extent descriptor <rpxd>
1064 */
1065 /*
1066 * allocate new directory page extent and
1067 * new index page(s) to cover page split(s)
1068 *
1069 * allocation hint: ?
1070 */
1080 }
1084 /* undo allocation */
1086 }
1092 /* undo allocation */
1094 }
1096 /*
1097 * propagate up the router entry for the leaf page just split
1098 *
1099 * insert a router entry for the new page into the parent page,
1100 * propagate the insert/split up the tree by walking back the stack
1101 * of (bn of parent page, index of child page entry in parent page)
1102 * that were traversed during the search for the page that split.
1103 *
1104 * the propagation of insert/split up the tree stops if the root
1105 * splits or the page inserted into doesn't have to split to hold
1106 * the new entry.
1107 *
1108 * the parent entry for the split page remains the same, and
1109 * a new entry is inserted at its right with the first key and
1110 * block number of the new right page.
1111 *
1112 * There are a maximum of 4 pages pinned at any time:
1113 * two children, left parent and right parent (when the parent splits).
1114 * keep the child pages pinned while working on the parent.
1115 * make sure that all pins are released at exit.
1116 */
1118 /* parent page specified by stack frame <parent> */
1120 /* keep current child pages (<lp>, <rp>) pinned */
1124 /*
1125 * insert router entry in parent for new right child page <rp>
1126 */
1127 /* get the parent page <sp> */
1133 }
1135 /*
1136 * The new key entry goes ONE AFTER the index of parent entry,
1137 * because the split was to the right.
1138 */
1141 /*
1142 * compute the key for the router entry
1143 *
1144 * key suffix compression:
1145 * for internal pages that have leaf pages as children,
1146 * retain only what's needed to distinguish between
1147 * the new entry and the entry on the page to its left.
1148 * If the keys compare equal, retain the entire key.
1149 *
1150 * note that compression is performed only at computing
1151 * router key at the lowest internal level.
1152 * further compression of the key between pairs of higher
1153 * level internal pages loses too much information and
1154 * the search may fail.
1155 * (e.g., two adjacent leaf pages of {a, ..., x} {xx, ...,}
1156 * results in two adjacent parent entries (a)(xx).
1157 * if split occurs between these two entries, and
1158 * if compression is applied, the router key of parent entry
1159 * of right page (x) will divert search for x into right
1160 * subtree and miss x in the left subtree.)
1161 *
1162 * the entire key must be retained for the next-to-leftmost
1163 * internal key at any level of the tree, or search may fail
1164 * (e.g., ?)
1165 */
1168 /*
1169 * compute the length of prefix for suffix compression
1170 * between last entry of left page and first entry
1171 * of right page
1172 */
1175 /* compute uppercase router prefix key */
1185 }
1187 /* next to leftmost entry of
1188 lowest internal level */
1190 /* compute uppercase router key */
1196 }
1209 }
1211 /* unpin left child page */
1214 /*
1215 * compute the data for the router entry
1216 */
1219 /*
1220 * parent page is full - split the parent page
1221 */
1223 /* init for parent page split */
1228 /* split->data = data; */
1230 /* unpin right child page */
1233 /* The split routines insert the new entry,
1234 * acquire txLock as appropriate.
1235 * return <rp> pinned and its block number <rbn>.
1236 */
1243 }
1245 /* smp and rmp are pinned */
1246 }
1247 /*
1248 * parent page is not full - insert router entry in parent page
1249 */
1252 /*
1253 * acquire a transaction lock on the parent page
1254 */
1260 /* linelock header */
1265 /* linelock stbl of non-root parent page */
1267 lv++;
1274 }
1278 /* exit propagate up */
1280 }
1281 }
1283 /* unpin current split and its right page */
1287 /*
1288 * free remaining extents allocated for split
1289 */
1290 splitOut:
1296 freeKeyName:
1299 /* Rollback quota allocation */
1303 dtSplitUp_Exit:
1306 }
1309 /*
1310 * dtSplitPage()
1311 *
1312 * function: Split a non-root page of a btree.
1313 *
1314 * parameter:
1315 *
1316 * return: 0 - success;
1317 * errno - failure;
1318 * return split and new page pinned;
1319 */
1322 {
1331 s64 nextbn;
1346 /* get split page */
1350 /*
1351 * allocate the new right page for the split
1352 */
1361 /* Allocate blocks to quota. */
1365 }
1370 /*
1371 * acquire a transaction lock on the new right page
1372 */
1381 /*
1382 * acquire a transaction lock on the split page
1383 *
1384 * action:
1385 */
1389 /* linelock header of split page */
1396 /*
1397 * initialize/update sibling pointers between sp and rp
1398 */
1404 /*
1405 * initialize new right page
1406 */
1409 /* compute sorted entry table at start of extent data area */
1417 /* init freelist */
1422 /*
1423 * sequential append at tail: append without split
1424 *
1425 * If splitting the last page on a level because of appending
1426 * a entry to it (skip is maxentry), it's likely that the access is
1427 * sequential. Adding an empty page on the side of the level is less
1428 * work and can push the fill factor much higher than normal.
1429 * If we're wrong it's no big deal, we'll just do the split the right
1430 * way next time.
1431 * (It may look like it's equally easy to do a similar hack for
1432 * reverse sorted data, that is, split the tree left,
1433 * but it's not. Be my guest.)
1434 */
1436 /* linelock header + stbl (first slot) of new page */
1442 /*
1443 * initialize freelist of new right page
1444 */
1450 /* insert entry at the first entry of the new right page */
1454 }
1456 /*
1457 * non-sequential insert (at possibly middle page)
1458 */
1460 /*
1461 * update prev pointer of previous right sibling page;
1462 */
1468 }
1471 /*
1472 * acquire a transaction lock on the next page
1473 */
1479 /* linelock header of previous right sibling page */
1488 }
1490 /*
1491 * split the data between the split and right pages.
1492 */
1497 /*
1498 * compute fill factor for split pages
1499 *
1500 * <nxt> traces the next entry to move to rp
1501 * <off> traces the next entry to stay in sp
1502 */
1507 /* check for fill factor with new entry size */
1516 else
1518 namlen);
1528 }
1531 }
1536 }
1538 /* <nxt> poins to the 1st entry to move */
1540 /*
1541 * move entries to right page
1542 *
1543 * dtMoveEntry() initializes rp and reserves entry for insertion
1544 *
1545 * split page moved out entries are linelocked;
1546 * new/right page moved in entries are linelocked;
1547 */
1548 /* linelock header + stbl of new right page */
1558 /*
1559 * finalize freelist of new right page
1560 */
1567 /*
1568 * Update directory index table for entries now in right page
1569 */
1571 s64 lblock;
1579 }
1582 }
1584 /*
1585 * the skipped index was on the left page,
1586 */
1588 /* insert the new entry in the split page */
1591 /* linelock stbl of split page */
1600 }
1601 /*
1602 * the skipped index was on the right page,
1603 */
1605 /* adjust the skip index to reflect the new position */
1608 /* insert the new entry in the right page */
1610 }
1612 out:
1617 }
1620 /*
1621 * dtExtendPage()
1622 *
1623 * function: extend 1st/only directory leaf page
1624 *
1625 * parameter:
1626 *
1627 * return: 0 - success;
1628 * errno - failure;
1629 * return extended page pinned;
1630 */
1633 {
1652 uint type;
1656 /* get page to extend */
1660 /* get parent/root page */
1666 /*
1667 * extend the extent
1668 */
1676 /* in-place extension */
1679 }
1680 /* relocation */
1684 /* save moved extent descriptor for later free */
1691 /*
1692 * Update directory index table to reflect new page address
1693 */
1695 s64 lblock;
1700 ldtentry =
1705 }
1708 }
1709 }
1711 /*
1712 * extend the page
1713 */
1719 /*
1720 * acquire a transaction lock on the extended/leaf page
1721 */
1726 /* update buffer extent descriptor of extended page */
1729 #ifdef _STILL_TO_PORT
1733 /*
1734 * copy old stbl to new stbl at start of extended area
1735 */
1744 /*
1745 * in-line extension: linelock old area of extended page
1746 */
1748 /* linelock header */
1752 lv++;
1754 /* linelock new stbl of extended page */
1757 }
1758 /*
1759 * relocation: linelock whole relocated area
1760 */
1764 }
1770 /* sp->header.nextindex remains the same */
1772 /*
1773 * add old stbl region at head of freelist
1774 */
1781 }
1785 /*
1786 * append free region of newly extended area at tail of freelist
1787 */
1788 /* init free region of newly extended area */
1795 /* append new free region at tail of old freelist */
1806 }
1810 /*
1811 * insert the new entry
1812 */
1816 /*
1817 * linelock any freeslots residing in old extent
1818 */
1823 }
1825 /*
1826 * update parent entry on the parent/root page
1827 */
1828 /*
1829 * acquire a transaction lock on the parent/root page
1830 */
1835 /* linelock parent entry - 1st slot */
1840 /* update the parent pxd for page extension */
1846 }
1849 /*
1850 * dtSplitRoot()
1851 *
1852 * function:
1853 * split the full root page into
1854 * original/root/split page and new right page
1855 * i.e., root remains fixed in tree anchor (inode) and
1856 * the root is copied to a single new right child page
1857 * since root page << non-root page, and
1858 * the split root page contains a single entry for the
1859 * new right child page.
1860 *
1861 * parameter:
1862 *
1863 * return: 0 - success;
1864 * errno - failure;
1865 * return new page pinned;
1866 */
1869 {
1875 s64 rbn;
1889 /* get split root page */
1893 /*
1894 * allocate/initialize a single (right) child page
1895 *
1896 * N.B. at first split, a one (or two) block to fit new entry
1897 * is allocated; at subsequent split, a full page is allocated;
1898 */
1911 /* Allocate blocks to quota. */
1915 }
1918 /*
1919 * acquire a transaction lock on the new right page
1920 */
1928 /* initialize sibling pointers */
1932 /*
1933 * move in-line root page into new right page extent
1934 */
1935 /* linelock header + copied entries + new stbl (1st slot) in new page */
1946 /* copy old stbl to new stbl at start of extended area */
1952 /* copy old data area to start of new data area */
1955 /*
1956 * append free region of newly extended area at tail of freelist
1957 */
1958 /* init free region of newly extended area */
1965 /* append new free region at tail of old freelist */
1978 }
1982 /*
1983 * Update directory index table for entries now in right page
1984 */
1986 s64 lblock;
1995 }
1998 }
1999 /*
2000 * insert the new entry into the new right/child page
2001 * (skip index in the new right page will not change)
2002 */
2005 /*
2006 * reset parent/root page
2007 *
2008 * set the 1st entry offset to 0, which force the left-most key
2009 * at any level of the tree to be less than any search key.
2010 *
2011 * The btree comparison code guarantees that the left-most key on any
2012 * level of the tree is never used, so it doesn't need to be filled in.
2013 */
2015 /*
2016 * acquire a transaction lock on the root page (in-memory inode)
2017 */
2021 /* linelock root */
2028 /* update page header of root */
2032 }
2034 /* init the first entry */
2045 /* init freelist */
2049 /* init free region of remaining area */
2060 }
2063 /*
2064 * dtDelete()
2065 *
2066 * function: delete the entry(s) referenced by a key.
2067 *
2068 * parameter:
2069 *
2070 * return:
2071 */
2074 {
2076 s64 bn;
2091 /*
2092 * search for the entry to delete:
2093 *
2094 * dtSearch() returns (leaf page pinned, index at which to delete).
2095 */
2099 /* retrieve search result */
2102 /*
2103 * We need to find put the index of the next entry into the
2104 * directory index table in order to resume a readdir from this
2105 * entry.
2106 */
2112 /*
2113 * Last entry in this leaf page
2114 */
2119 /* Read next leaf page */
2126 ldtentry =
2129 next_index =
2132 }
2133 }
2135 ldtentry =
2138 }
2140 }
2141 /*
2142 * the leaf page becomes empty, delete the page
2143 */
2145 /* delete empty page */
2147 }
2148 /*
2149 * the leaf page has other entries remaining:
2150 *
2151 * delete the entry from the leaf page.
2152 */
2155 /*
2156 * acquire a transaction lock on the leaf page
2157 */
2161 /*
2162 * Do not assume that dtlck->index will be zero. During a
2163 * rename within a directory, this transaction may have
2164 * modified this page already when adding the new entry.
2165 */
2167 /* linelock header */
2175 /* linelock stbl of non-root leaf page */
2186 }
2188 /* free the leaf entry */
2191 /*
2192 * Update directory index table for entries moved in stbl
2193 */
2195 s64 lblock;
2200 ldtentry =
2205 }
2208 }
2211 }
2214 }
2217 /*
2218 * dtDeleteUp()
2219 *
2220 * function:
2221 * free empty pages as propagating deletion up the tree
2222 *
2223 * parameter:
2224 *
2225 * return:
2226 */
2229 {
2242 /*
2243 * keep the root leaf page which has become empty
2244 */
2246 /*
2247 * reset the root
2248 *
2249 * dtInitRoot() acquires txlock on the root
2250 */
2256 }
2258 /*
2259 * free the non-root leaf page
2260 */
2261 /*
2262 * acquire a transaction lock on the page
2263 *
2264 * write FREEXTENT|NOREDOPAGE log record
2265 * N.B. linelock is overlaid as freed extent descriptor, and
2266 * the buffer page is freed;
2267 */
2274 /* update sibling pointers */
2278 }
2282 /* Free quota allocation. */
2285 /* free/invalidate its buffer page */
2288 /*
2289 * propagate page deletion up the directory tree
2290 *
2291 * If the delete from the parent page makes it empty,
2292 * continue all the way up the tree.
2293 * stop if the root page is reached (which is never deleted) or
2294 * if the entry deletion does not empty the page.
2295 */
2297 /* pin the parent page <sp> */
2302 /*
2303 * free the extent of the child page deleted
2304 */
2307 /*
2308 * delete the entry for the child page from parent
2309 */
2312 /*
2313 * the parent has the single entry being deleted:
2314 *
2315 * free the parent page which has become empty.
2316 */
2318 /*
2319 * keep the root internal page which has become empty
2320 */
2322 /*
2323 * reset the root
2324 *
2325 * dtInitRoot() acquires txlock on the root
2326 */
2332 }
2333 /*
2334 * free the parent page
2335 */
2337 /*
2338 * acquire a transaction lock on the page
2339 *
2340 * write FREEXTENT|NOREDOPAGE log record
2341 */
2342 tlck =
2350 /* update sibling pointers */
2354 }
2358 /* Free quota allocation */
2361 /* free/invalidate its buffer page */
2364 /* propagate up */
2366 }
2367 }
2369 /*
2370 * the parent has other entries remaining:
2371 *
2372 * delete the router entry from the parent page.
2373 */
2375 /*
2376 * acquire a transaction lock on the page
2377 *
2378 * action: router entry deletion
2379 */
2383 /* linelock header */
2391 /* linelock stbl of non-root leaf page */
2394 lv++;
2398 }
2405 }
2407 /* free the router entry */
2410 /* reset key of new leftmost entry of level (for consistency) */
2415 /* unpin the parent page */
2418 /* exit propagation up */
2420 }
2423 }
2425 #ifdef _NOTYET
2426 /*
2427 * NAME: dtRelocate()
2428 *
2429 * FUNCTION: relocate dtpage (internal or leaf) of directory;
2430 * This function is mainly used by defragfs utility.
2431 */
2433 s64 nxaddr)
2434 {
2438 s64 bn;
2455 xlen);
2457 /*
2458 * 1. get the internal parent dtpage covering
2459 * router entry for the tartget page to be relocated;
2460 */
2465 /* retrieve search result */
2469 /*
2470 * 2. relocate the target dtpage
2471 */
2472 /* read in the target page from src extent */
2475 /* release the pinned parent page */
2478 }
2480 /*
2481 * read in sibling pages if any to update sibling pointers;
2482 */
2491 }
2492 }
2504 }
2505 }
2507 /* at this point, all xtpages to be updated are in memory */
2509 /*
2510 * update sibling pointers of sibling dtpages if any;
2511 */
2515 /* linelock header */
2524 }
2529 /* linelock header */
2538 }
2540 /*
2541 * update the target dtpage to be relocated
2542 *
2543 * write LOG_REDOPAGE of LOG_NEW type for dst page
2544 * for the whole target page (logredo() will apply
2545 * after image and update bmap for allocation of the
2546 * dst extent), and update bmap for allocation of
2547 * the dst extent;
2548 */
2551 /* linelock header */
2555 /* update the self address in the dtpage header */
2559 /* the dst page is the same as the src page, i.e.,
2560 * linelock for afterimage of the whole page;
2561 */
2566 /* update the buffer extent descriptor of the dtpage */
2568 #ifdef _STILL_TO_PORT
2571 /* unpin the relocated page */
2575 /* the moved extent is dtpage, then a LOG_NOREDOPAGE log rec
2576 * needs to be written (in logredo(), the LOG_NOREDOPAGE log rec
2577 * will also force a bmap update ).
2578 */
2580 /*
2581 * 3. acquire maplock for the source extent to be freed;
2582 */
2583 /* for dtpage relocation, write a LOG_NOREDOPAGE record
2584 * for the source dtpage (logredo() will init NoRedoPage
2585 * filter and will also update bmap for free of the source
2586 * dtpage), and upadte bmap for free of the source dtpage;
2587 */
2595 /*
2596 * 4. update the parent router entry for relocation;
2597 *
2598 * acquire tlck for the parent entry covering the target dtpage;
2599 * write LOG_REDOPAGE to apply after image only;
2600 */
2606 /* update the PXD with the new address */
2614 /* unpin the parent dtpage */
2618 }
2620 /*
2621 * NAME: dtSearchNode()
2622 *
2623 * FUNCTION: Search for an dtpage containing a specified address
2624 * This function is mainly used by defragfs utility.
2625 *
2626 * NOTE: Search result on stack, the found page is pinned at exit.
2627 * The result page must be an internal dtpage.
2628 * lmxaddr give the address of the left most page of the
2629 * dtree level, in which the required dtpage resides.
2630 */
2633 {
2635 s64 bn;
2646 /*
2647 * descend tree to the level with specified leftmost page
2648 *
2649 * by convention, root bn = 0.
2650 */
2652 /* get/pin the page to search */
2657 /* does the xaddr of leftmost page of the levevl
2658 * matches levevl search key ?
2659 */
2666 /*
2667 * descend down to leftmost child page
2668 */
2672 }
2674 /* get the leftmost entry */
2678 /* get the child page block address */
2681 /* unpin the parent page */
2683 }
2685 /*
2686 * search each page at the current levevl
2687 */
2688 loop:
2693 /* found the specified router entry */
2702 }
2703 }
2705 /* get the right sibling page if any */
2711 }
2713 /* unpin current page */
2716 /* get the right sibling page */
2722 }
2725 /*
2726 * dtRelink()
2727 *
2728 * function:
2729 * link around a freed page.
2730 *
2731 * parameter:
2732 * fp: page to be freed
2733 *
2734 * return:
2735 */
2737 {
2748 /* update prev pointer of the next page */
2755 /*
2756 * acquire a transaction lock on the next page
2757 *
2758 * action: update prev pointer;
2759 */
2765 /* linelock header */
2775 }
2777 /* update next pointer of the previous page */
2784 /*
2785 * acquire a transaction lock on the prev page
2786 *
2787 * action: update next pointer;
2788 */
2794 /* linelock header */
2804 }
2807 }
2810 /*
2811 * dtInitRoot()
2812 *
2813 * initialize directory root (inline in inode)
2814 */
2816 {
2824 u16 xflag_save;
2826 /*
2827 * If this was previously an non-empty directory, we need to remove
2828 * the old directory table.
2829 */
2833 /*
2834 * We're playing games with the tid's xflag. If
2835 * we're removing a regular file, the file's xtree
2836 * is committed with COMMIT_PMAP, but we always
2837 * commit the directories xtree with COMMIT_PWMAP.
2838 */
2841 /*
2842 * xtTruncate isn't guaranteed to fully truncate
2843 * the xtree. The caller needs to check i_size
2844 * after committing the transaction to see if
2845 * additional truncation is needed. The
2846 * COMMIT_Stale flag tells caller that we
2847 * initiated the truncation.
2848 */
2860 /*
2861 * acquire a transaction lock on the root
2862 *
2863 * action: directory initialization;
2864 */
2869 /* linelock root */
2882 /* init freelist */
2886 /* init data area of root */
2894 /* init '..' entry */
2898 }
2900 /*
2901 * add_missing_indices()
2902 *
2903 * function: Fix dtree page in which one or more entries has an invalid index.
2904 * fsck.jfs should really fix this, but it currently does not.
2905 * Called from jfs_readdir when bad index is detected.
2906 */
2908 {
2912 uint index;
2918 tid_t tid;
2928 }
2948 }
2949 }
2953 end:
2955 }
2957 /*
2958 * Buffer to hold directory entry info while traversing a dtree page
2959 * before being fed to the filldir function
2960 */
2962 loff_t position;
2964 u16 name_len;
2966 };
2968 /*
2969 * function to determine next variable-sized jfs_dirent in buffer
2970 */
2972 {
2978 }
2980 /*
2981 * jfs_readdir()
2982 *
2983 * function: read directory entries sequentially
2984 * from the specified entry offset
2985 *
2986 * parameter:
2987 *
2988 * return: offset = (pn, index) of start entry
2989 * of next jfs_readdir()/dtRead()
2990 */
2992 {
2998 s16 pn;
2999 s16 index;
3000 s32 unused;
3002 s64 bn;
3014 u32 dir_index;
3026 /*
3027 * persistent index is stored in directory entries.
3028 * Special cases: 0 = .
3029 * 1 = ..
3030 * -1 = End of directory
3031 */
3041 /* Stale position. Directory has shrunk */
3044 }
3045 repeat:
3050 }
3057 }
3062 }
3064 }
3071 }
3077 }
3080 /*
3081 * self "."
3082 */
3085 DT_DIR))
3087 }
3088 /*
3089 * parent ".."
3090 */
3095 /*
3096 * Find first entry of left-most leaf
3097 */
3101 }
3107 }
3109 /*
3110 * Legacy filesystem - OS/2 & Linux JFS < 0.3.6
3111 *
3112 * pn = index = 0: First entry "."
3113 * pn = 0; index = 1: Second entry ".."
3114 * pn > 0: Real entries, pn=1 -> leftmost page
3115 * pn = index = -1: No more entries
3116 */
3119 /* build "." entry */
3122 DT_DIR))
3126 }
3130 /* build ".." entry */
3138 }
3142 }
3147 }
3154 }
3155 /* get start leaf page and index */
3158 /* offset beyond directory eof ? */
3162 }
3163 }
3171 }
3185 /* DBCS codepages could overrun dirent_buf */
3189 }
3198 /*
3199 * d->index should always be valid, but it
3200 * isn't. fsck.jfs doesn't create the
3201 * directory index for the lost+found
3202 * directory. Rather than let it go,
3203 * we can try to fix it.
3204 */
3210 /*
3211 * setting overflow and setting
3212 * index to i will cause the
3213 * same page to be processed
3214 * again starting here
3215 */
3219 }
3221 }
3225 }
3227 /* copy the name of head/only segment */
3229 codepage);
3232 /* copy name in the additional segment(s) */
3238 /* Sanity Check */
3241 "JFS:Dtree error: ino = "
3245 i);
3247 }
3254 }
3256 jfs_dirents++;
3258 skip_one:
3261 }
3264 /* Point to next leaf page */
3270 /* update offset (pn:index) for new page */
3274 }
3275 }
3277 }
3279 /* unpin previous leaf page */
3290 }
3295 }
3300 }
3306 }
3307 }
3309 out:
3313 }
3316 /*
3317 * dtReadFirst()
3318 *
3319 * function: get the leftmost page of the directory
3320 */
3322 {
3324 s64 bn;
3334 /*
3335 * descend leftmost path of the tree
3336 *
3337 * by convention, root bn = 0.
3338 */
3344 /*
3345 * leftmost leaf page
3346 */
3348 /* return leftmost entry */
3355 }
3357 /*
3358 * descend down to leftmost child page
3359 */
3365 }
3366 /* push (bn, index) of the parent page/entry */
3369 /* get the leftmost entry */
3373 /* get the child page block address */
3377 /* unpin the parent page */
3379 }
3380 }
3383 /*
3384 * dtReadNext()
3385 *
3386 * function: get the page of the specified offset (pn:index)
3387 *
3388 * return: if (offset > eof), bn = -1;
3389 *
3390 * note: if index > nextindex of the target leaf page,
3391 * start with 1st entry of next leaf page;
3392 */
3395 {
3398 s16 pn;
3399 s16 index;
3400 s32 unused;
3402 s64 bn;
3411 /*
3412 * get leftmost leaf page pinned
3413 */
3417 /* get leaf page */
3420 /* get the start offset (pn:index) */
3424 /* start at leftmost page ? */
3426 /* offset beyond eof ? */
3433 }
3435 /* start with 1st entry of next leaf page */
3439 }
3441 /* start at non-leftmost page: scan parent pages for large pn */
3445 }
3447 /* start after next leaf page ? */
3451 /* get leaf page pn = 1 */
3452 a:
3455 /* unpin leaf page */
3458 /* offset beyond eof ? */
3462 }
3466 /*
3467 * scan last internal page level to get target leaf page
3468 */
3469 b:
3470 /* unpin leftmost leaf page */
3473 /* get left most parent page */
3481 /* scan parent pages at last internal page level */
3485 /* get next parent page address */
3488 /* unpin current parent page */
3491 /* offset beyond eof ? */
3495 }
3497 /* get next parent page */
3502 /* update parent page stack frame */
3504 }
3506 /* get leaf page address */
3511 /* unpin parent page */
3514 /*
3515 * get target leaf page
3516 */
3517 c:
3522 /*
3523 * leaf page has been completed:
3524 * start with 1st entry of next leaf page
3525 */
3529 /* unpin leaf page */
3532 /* offset beyond eof ? */
3536 }
3538 /* get next leaf page */
3543 /* start with 1st entry of next leaf page */
3546 }
3548 out:
3549 /* return target leaf page pinned */
3556 }
3559 /*
3560 * dtCompare()
3561 *
3562 * function: compare search key with an internal entry
3563 *
3564 * return:
3565 * < 0 if k is < record
3566 * = 0 if k is = record
3567 * > 0 if k is > record
3568 */
3579 /*
3580 * force the left-most key on internal pages, at any level of
3581 * the tree, to be less than any search key.
3582 * this obviates having to update the leftmost key on an internal
3583 * page when the user inserts a new key in the tree smaller than
3584 * anything that has been stored.
3585 *
3586 * (? if/when dtSearch() narrows down to 1st entry (index = 0),
3587 * at any internal page at any level of the tree,
3588 * it descends to child of the entry anyway -
3589 * ? make the entry as min size dummy entry)
3590 *
3591 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
3592 * return (1);
3593 */
3604 /* compare with head/only segment */
3612 /* compare with additional segment(s) */
3615 /* compare with next name segment */
3627 }
3630 }
3635 /*
3636 * ciCompare()
3637 *
3638 * function: compare search key with an (leaf/internal) entry
3639 *
3640 * return:
3641 * < 0 if k is < record
3642 * = 0 if k is = record
3643 * > 0 if k is > record
3644 */
3649 {
3658 /*
3659 * force the left-most key on internal pages, at any level of
3660 * the tree, to be less than any search key.
3661 * this obviates having to update the leftmost key on an internal
3662 * page when the user inserts a new key in the tree smaller than
3663 * anything that has been stored.
3664 *
3665 * (? if/when dtSearch() narrows down to 1st entry (index = 0),
3666 * at any internal page at any level of the tree,
3667 * it descends to child of the entry anyway -
3668 * ? make the entry as min size dummy entry)
3669 *
3670 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
3671 * return (1);
3672 */
3677 /*
3678 * leaf page entry
3679 */
3687 else
3689 }
3690 /*
3691 * internal page entry
3692 */
3699 }
3701 /* compare with head/only segment */
3704 /* only uppercase if case-insensitive support is on */
3707 else
3711 }
3716 /* compare with additional segment(s) */
3718 /* compare with next name segment */
3724 /* only uppercase if case-insensitive support is on */
3727 else
3732 }
3737 }
3740 }
3743 /*
3744 * ciGetLeafPrefixKey()
3745 *
3746 * function: compute prefix of suffix compression
3747 * from two adjacent leaf entries
3748 * across page boundary
3749 *
3750 * return: non-zero on error
3751 *
3752 */
3755 {
3762 GFP_KERNEL);
3767 GFP_KERNEL);
3771 }
3773 /* get left and right key */
3787 /* compute prefix */
3797 }
3798 }
3800 /* l->namlen <= r->namlen since l <= r */
3807 free_names:
3811 }
3815 /*
3816 * dtGetKey()
3817 *
3818 * function: get key of the entry
3819 */
3822 {
3832 /* get entry */
3842 else
3850 }
3855 /*
3856 * move head/only segment
3857 */
3860 /*
3861 * move additional segment(s)
3862 */
3864 /* get next segment */
3872 }
3873 }
3876 /*
3877 * dtInsertEntry()
3878 *
3879 * function: allocate free slot(s) and
3880 * write a leaf/internal entry
3881 *
3882 * return: entry slot index
3883 */
3886 {
3904 /* allocate a free slot */
3910 /* open new linelock */
3917 /* write head/only segment */
3941 }
3948 /* write additional segment(s) */
3952 /* get free slot */
3958 /* is next slot contiguous ? */
3960 /* close current linelock */
3964 /* open new linelock */
3966 lv++;
3970 }
3974 }
3980 n++;
3983 }
3985 /* close current linelock */
3991 /* terminate last/only segment */
3993 /* single segment entry */
3996 else
3999 /* multi-segment entry */
4002 /* if insert into middle, shift right succeeding entries in stbl */
4009 s64 lblock;
4011 /*
4012 * Need to update slot number for entries that moved
4013 * in the stbl
4014 */
4021 }
4024 }
4025 }
4029 /* advance next available entry index of stbl */
4031 }
4034 /*
4035 * dtMoveEntry()
4036 *
4037 * function: move entries from split/left page to new/right page
4038 *
4039 * nextindex of dst page and freelist/freecnt of both pages
4040 * are updated.
4041 */
4045 {
4065 /* linelock destination entry slot */
4069 /* linelock source entry slot */
4074 /*
4075 * move entries
4076 */
4082 /* is next slot contiguous ? */
4084 /* close current linelock */
4088 /* open new linelock */
4090 slv++;
4094 }
4098 }
4100 /*
4101 * move head/only segment of an entry
4102 */
4103 /* get dst slot */
4106 /* get src slot and move */
4109 /* get source entry */
4124 /* update dst head/only segment next field */
4125 dsi++;
4136 dsi++;
4138 }
4140 /* free src head/only segment */
4145 ns++;
4146 nd++;
4149 /*
4150 * move additional segment(s) of the entry
4151 */
4154 /* is next slot contiguous ? */
4156 /* close current linelock */
4160 /* open new linelock */
4162 slv++;
4164 sdtlck =
4168 }
4172 }
4174 /* get next source segment */
4177 /* get next destination free slot */
4178 d++;
4183 ns++;
4184 nd++;
4187 dsi++;
4190 /* free source segment */
4199 /* terminate dst last/only segment */
4201 /* single segment entry */
4204 else
4207 /* multi-segment entry */
4211 /* close current linelock */
4220 /* update source header */
4224 /* update destination header */
4229 }
4232 /*
4233 * dtDeleteEntry()
4234 *
4235 * function: free a (leaf/internal) entry
4236 *
4237 * log freelist header, stbl, and each segment slot of entry
4238 * (even though last/only segment next field is modified,
4239 * physical image logging requires all segment slots of
4240 * the entry logged to avoid applying previous updates
4241 * to the same slots)
4242 */
4244 {
4253 /* get free entry slot index */
4257 /* open new linelock */
4264 /* get the head/only segment */
4268 else
4276 /* find the last/only segment */
4278 /* is next slot contiguous ? */
4280 /* close current linelock */
4284 /* open new linelock */
4286 lv++;
4290 }
4294 }
4296 n++;
4298 freecnt++;
4303 }
4305 /* close current linelock */
4311 /* update freelist */
4316 /* if delete from middle,
4317 * shift left the succedding entries in the stbl
4318 */
4324 }
4327 /*
4328 * dtTruncateEntry()
4329 *
4330 * function: truncate a (leaf/internal) entry
4331 *
4332 * log freelist header, stbl, and each segment slot of entry
4333 * (even though last/only segment next field is modified,
4334 * physical image logging requires all segment slots of
4335 * the entry logged to avoid applying previous updates
4336 * to the same slots)
4337 */
4339 {
4348 /* get free entry slot index */
4352 /* open new linelock */
4359 /* get the head/only segment */
4371 /* find the last/only segment */
4373 /* is next slot contiguous ? */
4375 /* close current linelock */
4379 /* open new linelock */
4381 lv++;
4385 }
4389 }
4391 n++;
4393 freecnt++;
4398 }
4400 /* close current linelock */
4406 /* update freelist */
4412 }
4415 /*
4416 * dtLinelockFreelist()
4417 */
4421 {
4429 /* get free entry slot index */
4432 /* open new linelock */
4445 /* find the last/only segment */
4447 /* is next slot contiguous ? */
4449 /* close current linelock */
4453 /* open new linelock */
4455 lv++;
4459 }
4463 }
4465 n++;
4470 }
4472 /* close current linelock */
4477 }
4480 /*
4481 * NAME: dtModify
4482 *
4483 * FUNCTION: Modify the inode number part of a directory entry
4484 *
4485 * PARAMETERS:
4486 * tid - Transaction id
4487 * ip - Inode of parent directory
4488 * key - Name of entry to be modified
4489 * orig_ino - Original inode number expected in entry
4490 * new_ino - New inode number to put into entry
4491 * flag - JFS_RENAME
4492 *
4493 * RETURNS:
4494 * -ESTALE - If entry found does not match orig_ino passed in
4495 * -ENOENT - If no entry can be found to match key
4496 * 0 - If successfully modified entry
4497 */
4500 {
4502 s64 bn;
4514 /*
4515 * search for the entry to modify:
4516 *
4517 * dtSearch() returns (leaf page pinned, index at which to modify).
4518 */
4522 /* retrieve search result */
4526 /*
4527 * acquire a transaction lock on the leaf page of named entry
4528 */
4532 /* get slot index of the entry */
4536 /* linelock entry */
4543 /* get the head/only segment */
4546 /* substitute the inode number of the entry */
4549 /* unpin the leaf page */
4553 }
4555 #ifdef _JFS_DEBUG_DTREE
4556 /*
4557 * dtDisplayTree()
4558 *
4559 * function: traverse forward
4560 */
4562 {
4577 /* clear stack */
4580 /*
4581 * start with root
4582 *
4583 * root resides in the inode
4584 */
4588 /*
4589 * first access of each page:
4590 */
4591 newPage:
4596 /* process entries forward from first index */
4601 /*
4602 * first access of each internal page
4603 */
4610 /*
4611 * first access of each leaf page
4612 */
4616 /*
4617 * process leaf page entries
4618 *
4619 for ( ; index <= lastindex; index++)
4620 {
4621 }
4622 */
4624 /* unpin the leaf page */
4626 }
4628 /*
4629 * go back up to the parent page
4630 */
4631 getParent:
4632 /* pop/restore parent entry for the current child page */
4634 /* current page must have been root */
4637 /*
4638 * parent page scan completed
4639 */
4641 /* go back up to the parent page */
4643 }
4645 /*
4646 * parent page has entries remaining
4647 */
4648 /* get back the parent page */
4650 /* v = parent->level; */
4655 /* get next parent entry */
4656 index++;
4658 /*
4659 * internal page: go down to child page of current entry
4660 */
4661 getChild:
4662 /* push/save current parent entry for the child page */
4666 /* btsp->level = v; */
4667 /* btsp->node = h; */
4670 /* get current entry for the child page */
4674 /*
4675 * first access of each internal entry:
4676 */
4678 /* get child page */
4683 v++;
4686 /* release parent page */
4689 /* process the child page */
4691 }
4694 /*
4695 * dtDisplayPage()
4696 *
4697 * function: display page
4698 */
4700 {
4717 }
4719 /* display page control */
4723 /* display entries */
4737 }
4742 }
4743 }
4751 }