| blob | 52bae3f5c9145df968a3803ee2f7cad0b5fe4bf7 |
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>
105 #include <linux/slab.h>
114 /* dtree split parameter */
117 s16 index;
118 s16 nslot;
122 };
124 #define DT_PAGE(IP, MP) BT_PAGE(IP, MP, dtpage_t, i_dtroot)
126 /* get page buffer for specified block address */
127 #define DT_GETPAGE(IP, BN, MP, SIZE, P, RC) \
128 do { \
129 BT_GETPAGE(IP, BN, MP, dtpage_t, SIZE, P, RC, i_dtroot); \
130 if (!(RC)) { \
131 if (((P)->header.nextindex > \
132 (((BN) == 0) ? DTROOTMAXSLOT : (P)->header.maxslot)) || \
133 ((BN) && ((P)->header.maxslot > DTPAGEMAXSLOT))) { \
134 BT_PUTPAGE(MP); \
135 jfs_error((IP)->i_sb, \
137 MP = NULL; \
138 RC = -EIO; \
139 } \
140 } \
141 } while (0)
143 /* for consistency */
144 #define DT_PUTPAGE(MP) BT_PUTPAGE(MP)
146 #define DT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
147 BT_GETSEARCH(IP, LEAF, BN, MP, dtpage_t, P, INDEX, i_dtroot)
149 /*
150 * forward references
151 */
198 #define ciToUpper(c) UniStrupr((c)->name)
200 /*
201 * read_index_page()
202 *
203 * Reads a page of a directory's index table.
204 * Having metadata mapped into the directory inode's address space
205 * presents a multitude of problems. We avoid this by mapping to
206 * the absolute address space outside of the *_metapage routines
207 */
209 {
211 s64 xaddr;
213 s32 xlen;
220 }
222 /*
223 * get_index_page()
224 *
225 * Same as get_index_page(), but get's a new page without reading
226 */
228 {
230 s64 xaddr;
232 s32 xlen;
239 }
241 /*
242 * find_index()
243 *
244 * Returns dtree page containing directory table entry for specified
245 * index and pointer to its entry.
246 *
247 * mp must be released by caller.
248 */
251 {
253 s64 blkno;
254 s64 offset;
262 maxWarnings--;
263 }
265 }
270 }
273 /*
274 * Inline directory table
275 */
287 }
291 }
295 }
297 slot =
299 page_offset);
300 }
302 }
305 u32 index)
306 {
318 /*
319 * Linelock slot size is twice the size of directory table
320 * slot size. 512 entries per page.
321 */
325 }
327 /*
328 * add_index()
329 *
330 * Adds an entry to the directory index table. This is used to provide
331 * each directory entry with a persistent index in which to resume
332 * directory traversals
333 */
335 {
339 u64 blkno;
341 u32 index;
345 s64 offset;
346 uint page_offset;
348 s64 xaddr;
356 }
361 /*
362 * i_size reflects size of index table, or 8 bytes per entry.
363 */
366 /*
367 * dir table fits inline within inode
368 */
377 }
381 /*
382 * It's time to move the inline table to an external
383 * page and begin to build the xtree
384 */
390 }
392 /*
393 * Save the table, we're going to overwrite it with the
394 * xtree root
395 */
398 /*
399 * Initialize empty x-tree
400 */
403 /*
404 * Add the first block to the xtree
405 */
407 /* This really shouldn't fail */
414 }
424 }
439 /*
440 * Logging is now directed by xtree tlocks
441 */
443 }
449 /*
450 * This will be the beginning of a new page
451 */
456 }
461 else
469 }
473 dirtab_slot =
484 clean_up:
489 }
491 /*
492 * free_index()
493 *
494 * Marks an entry to the directory index table as free.
495 */
497 {
499 s64 lblock;
517 }
519 /*
520 * modify_index()
521 *
522 * Changes an entry in the directory index table
523 */
526 {
542 }
544 /*
545 * read_index()
546 *
547 * reads a directory table slot
548 */
551 {
552 s64 lblock;
559 }
567 }
569 /*
570 * dtSearch()
571 *
572 * function:
573 * Search for the entry with specified key
574 *
575 * parameter:
576 *
577 * return: 0 - search result on stack, leaf page pinned;
578 * errno - I/O error
579 */
582 {
585 s64 bn;
593 ino_t inumber;
598 GFP_NOFS);
602 }
605 /* uppercase search key for c-i directory */
609 /* only uppercase if case-insensitive support is on */
612 }
615 /* init level count for max pages to split */
618 /*
619 * search down tree from root:
620 *
621 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
622 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
623 *
624 * if entry with search key K is not found
625 * internal page search find the entry with largest key Ki
626 * less than K which point to the child page to search;
627 * leaf page search find the entry with smallest key Kj
628 * greater than K so that the returned index is the position of
629 * the entry to be shifted right for insertion of new entry.
630 * for empty tree, search key is greater than any key of the tree.
631 *
632 * by convention, root bn = 0.
633 */
635 /* get/pin the page to search */
640 /* get sorted entry table of the page */
643 /*
644 * binary search with search key K on the current page.
645 */
650 /* uppercase leaf name to compare */
651 cmp =
655 /* router key is in uppercase */
660 }
662 /*
663 * search hit
664 */
665 /* search hit - leaf page:
666 * return the entry found
667 */
672 /*
673 * search for JFS_LOOKUP
674 */
679 }
681 /*
682 * search for JFS_CREATE
683 */
688 }
690 /*
691 * search for JFS_REMOVE or JFS_RENAME
692 */
698 }
700 /*
701 * JFS_REMOVE|JFS_FINDDIR|JFS_RENAME
702 */
703 /* save search result */
712 }
714 /* search hit - internal page:
715 * descend/search its child page
716 */
718 }
723 }
724 }
726 /*
727 * search miss
728 *
729 * base is the smallest index with key (Kj) greater than
730 * search key (K) and may be zero or (maxindex + 1) index.
731 */
732 /*
733 * search miss - leaf page
734 *
735 * return location of entry (base) where new entry with
736 * search key K is to be inserted.
737 */
739 /*
740 * search for JFS_LOOKUP, JFS_REMOVE, or JFS_RENAME
741 */
746 }
748 /*
749 * search for JFS_CREATE|JFS_FINDDIR:
750 *
751 * save search result
752 */
761 }
763 /*
764 * search miss - internal page
765 *
766 * if base is non-zero, decrement base by one to get the parent
767 * entry of the child page to search.
768 */
771 /*
772 * go down to child page
773 */
774 getChild:
775 /* update max. number of pages to split */
777 /* Something's corrupted, mark filesystem dirty so
778 * chkdsk will fix it.
779 */
784 }
787 /* push (bn, index) of the parent page/entry */
790 /* get the child page block number */
795 /* unpin the parent page */
797 }
799 out:
802 dtSearch_Exit1:
806 dtSearch_Exit2:
809 }
812 /*
813 * dtInsert()
814 *
815 * function: insert an entry to directory tree
816 *
817 * parameter:
818 *
819 * return: 0 - success;
820 * errno - failure;
821 */
824 {
828 s64 bn;
831 ddata_t data;
837 /*
838 * retrieve search result
839 *
840 * dtSearch() returns (leaf page pinned, index at which to insert).
841 * n.b. dtSearch() may return index of (maxindex + 1) of
842 * the full page.
843 */
846 /*
847 * insert entry for new key
848 */
853 }
860 }
863 /*
864 * leaf page does not have enough room for new entry:
865 *
866 * extend/split the leaf page;
867 *
868 * dtSplitUp() will insert the entry and unpin the leaf page.
869 */
878 }
880 /*
881 * leaf page does have enough room for new entry:
882 *
883 * insert the new data entry into the leaf page;
884 */
886 /*
887 * acquire a transaction lock on the leaf page
888 */
894 /* linelock header */
901 /* linelock stbl of non-root leaf page */
911 }
913 /* unpin the leaf page */
917 }
920 /*
921 * dtSplitUp()
922 *
923 * function: propagate insertion bottom up;
924 *
925 * parameter:
926 *
927 * return: 0 - success;
928 * errno - failure;
929 * leaf page unpinned;
930 */
933 {
957 /* get split page */
966 }
968 /*
969 * split leaf page
970 *
971 * The split routines insert the new entry, and
972 * acquire txLock as appropriate.
973 */
974 /*
975 * split root leaf page:
976 */
978 /*
979 * allocate a single extent child page
980 */
986 xlen++;
990 }
1002 else
1011 }
1013 /*
1014 * extend first leaf page
1015 *
1016 * extend the 1st extent if less than buffer page size
1017 * (dtExtendPage() reurns leaf page unpinned)
1018 */
1028 else
1031 /* Allocate blocks to quota. */
1050 /* free relocated extent */
1054 /* free extended delta */
1058 }
1063 extendOut:
1066 }
1068 /*
1069 * split leaf page <sp> into <sp> and a new right page <rp>.
1070 *
1071 * return <rp> pinned and its extent descriptor <rpxd>
1072 */
1073 /*
1074 * allocate new directory page extent and
1075 * new index page(s) to cover page split(s)
1076 *
1077 * allocation hint: ?
1078 */
1088 }
1092 /* undo allocation */
1094 }
1100 /* undo allocation */
1102 }
1107 /*
1108 * propagate up the router entry for the leaf page just split
1109 *
1110 * insert a router entry for the new page into the parent page,
1111 * propagate the insert/split up the tree by walking back the stack
1112 * of (bn of parent page, index of child page entry in parent page)
1113 * that were traversed during the search for the page that split.
1114 *
1115 * the propagation of insert/split up the tree stops if the root
1116 * splits or the page inserted into doesn't have to split to hold
1117 * the new entry.
1118 *
1119 * the parent entry for the split page remains the same, and
1120 * a new entry is inserted at its right with the first key and
1121 * block number of the new right page.
1122 *
1123 * There are a maximum of 4 pages pinned at any time:
1124 * two children, left parent and right parent (when the parent splits).
1125 * keep the child pages pinned while working on the parent.
1126 * make sure that all pins are released at exit.
1127 */
1129 /* parent page specified by stack frame <parent> */
1131 /* keep current child pages (<lp>, <rp>) pinned */
1135 /*
1136 * insert router entry in parent for new right child page <rp>
1137 */
1138 /* get the parent page <sp> */
1144 }
1146 /*
1147 * The new key entry goes ONE AFTER the index of parent entry,
1148 * because the split was to the right.
1149 */
1152 /*
1153 * compute the key for the router entry
1154 *
1155 * key suffix compression:
1156 * for internal pages that have leaf pages as children,
1157 * retain only what's needed to distinguish between
1158 * the new entry and the entry on the page to its left.
1159 * If the keys compare equal, retain the entire key.
1160 *
1161 * note that compression is performed only at computing
1162 * router key at the lowest internal level.
1163 * further compression of the key between pairs of higher
1164 * level internal pages loses too much information and
1165 * the search may fail.
1166 * (e.g., two adjacent leaf pages of {a, ..., x} {xx, ...,}
1167 * results in two adjacent parent entries (a)(xx).
1168 * if split occurs between these two entries, and
1169 * if compression is applied, the router key of parent entry
1170 * of right page (x) will divert search for x into right
1171 * subtree and miss x in the left subtree.)
1172 *
1173 * the entire key must be retained for the next-to-leftmost
1174 * internal key at any level of the tree, or search may fail
1175 * (e.g., ?)
1176 */
1179 /*
1180 * compute the length of prefix for suffix compression
1181 * between last entry of left page and first entry
1182 * of right page
1183 */
1186 /* compute uppercase router prefix key */
1196 }
1198 /* next to leftmost entry of
1199 lowest internal level */
1201 /* compute uppercase router key */
1207 }
1220 }
1222 /* unpin left child page */
1225 /*
1226 * compute the data for the router entry
1227 */
1230 /*
1231 * parent page is full - split the parent page
1232 */
1234 /* init for parent page split */
1239 /* split->data = data; */
1241 /* unpin right child page */
1244 /* The split routines insert the new entry,
1245 * acquire txLock as appropriate.
1246 * return <rp> pinned and its block number <rbn>.
1247 */
1254 }
1256 /* smp and rmp are pinned */
1257 }
1258 /*
1259 * parent page is not full - insert router entry in parent page
1260 */
1263 /*
1264 * acquire a transaction lock on the parent page
1265 */
1271 /* linelock header */
1276 /* linelock stbl of non-root parent page */
1278 lv++;
1285 }
1289 /* exit propagate up */
1291 }
1292 }
1294 /* unpin current split and its right page */
1298 /*
1299 * free remaining extents allocated for split
1300 */
1301 splitOut:
1307 freeKeyName:
1310 /* Rollback quota allocation */
1314 dtSplitUp_Exit:
1317 }
1320 /*
1321 * dtSplitPage()
1322 *
1323 * function: Split a non-root page of a btree.
1324 *
1325 * parameter:
1326 *
1327 * return: 0 - success;
1328 * errno - failure;
1329 * return split and new page pinned;
1330 */
1333 {
1342 s64 nextbn;
1357 /* get split page */
1361 /*
1362 * allocate the new right page for the split
1363 */
1372 /* Allocate blocks to quota. */
1377 }
1382 /*
1383 * acquire a transaction lock on the new right page
1384 */
1393 /*
1394 * acquire a transaction lock on the split page
1395 *
1396 * action:
1397 */
1401 /* linelock header of split page */
1408 /*
1409 * initialize/update sibling pointers between sp and rp
1410 */
1416 /*
1417 * initialize new right page
1418 */
1421 /* compute sorted entry table at start of extent data area */
1429 /* init freelist */
1434 /*
1435 * sequential append at tail: append without split
1436 *
1437 * If splitting the last page on a level because of appending
1438 * a entry to it (skip is maxentry), it's likely that the access is
1439 * sequential. Adding an empty page on the side of the level is less
1440 * work and can push the fill factor much higher than normal.
1441 * If we're wrong it's no big deal, we'll just do the split the right
1442 * way next time.
1443 * (It may look like it's equally easy to do a similar hack for
1444 * reverse sorted data, that is, split the tree left,
1445 * but it's not. Be my guest.)
1446 */
1448 /* linelock header + stbl (first slot) of new page */
1454 /*
1455 * initialize freelist of new right page
1456 */
1462 /* insert entry at the first entry of the new right page */
1466 }
1468 /*
1469 * non-sequential insert (at possibly middle page)
1470 */
1472 /*
1473 * update prev pointer of previous right sibling page;
1474 */
1480 }
1483 /*
1484 * acquire a transaction lock on the next page
1485 */
1491 /* linelock header of previous right sibling page */
1500 }
1502 /*
1503 * split the data between the split and right pages.
1504 */
1509 /*
1510 * compute fill factor for split pages
1511 *
1512 * <nxt> traces the next entry to move to rp
1513 * <off> traces the next entry to stay in sp
1514 */
1519 /* check for fill factor with new entry size */
1528 else
1530 namlen);
1540 }
1543 }
1548 }
1550 /* <nxt> poins to the 1st entry to move */
1552 /*
1553 * move entries to right page
1554 *
1555 * dtMoveEntry() initializes rp and reserves entry for insertion
1556 *
1557 * split page moved out entries are linelocked;
1558 * new/right page moved in entries are linelocked;
1559 */
1560 /* linelock header + stbl of new right page */
1570 /*
1571 * finalize freelist of new right page
1572 */
1579 /*
1580 * Update directory index table for entries now in right page
1581 */
1583 s64 lblock;
1591 }
1594 }
1596 /*
1597 * the skipped index was on the left page,
1598 */
1600 /* insert the new entry in the split page */
1603 /* linelock stbl of split page */
1612 }
1613 /*
1614 * the skipped index was on the right page,
1615 */
1617 /* adjust the skip index to reflect the new position */
1620 /* insert the new entry in the right page */
1622 }
1624 out:
1629 }
1632 /*
1633 * dtExtendPage()
1634 *
1635 * function: extend 1st/only directory leaf page
1636 *
1637 * parameter:
1638 *
1639 * return: 0 - success;
1640 * errno - failure;
1641 * return extended page pinned;
1642 */
1645 {
1664 uint type;
1668 /* get page to extend */
1672 /* get parent/root page */
1678 /*
1679 * extend the extent
1680 */
1688 /* in-place extension */
1691 }
1692 /* relocation */
1696 /* save moved extent descriptor for later free */
1703 /*
1704 * Update directory index table to reflect new page address
1705 */
1707 s64 lblock;
1712 ldtentry =
1717 }
1720 }
1721 }
1723 /*
1724 * extend the page
1725 */
1731 /*
1732 * acquire a transaction lock on the extended/leaf page
1733 */
1738 /* update buffer extent descriptor of extended page */
1742 /*
1743 * copy old stbl to new stbl at start of extended area
1744 */
1753 /*
1754 * in-line extension: linelock old area of extended page
1755 */
1757 /* linelock header */
1761 lv++;
1763 /* linelock new stbl of extended page */
1766 }
1767 /*
1768 * relocation: linelock whole relocated area
1769 */
1773 }
1779 /* sp->header.nextindex remains the same */
1781 /*
1782 * add old stbl region at head of freelist
1783 */
1790 }
1794 /*
1795 * append free region of newly extended area at tail of freelist
1796 */
1797 /* init free region of newly extended area */
1804 /* append new free region at tail of old freelist */
1815 }
1819 /*
1820 * insert the new entry
1821 */
1825 /*
1826 * linelock any freeslots residing in old extent
1827 */
1832 }
1834 /*
1835 * update parent entry on the parent/root page
1836 */
1837 /*
1838 * acquire a transaction lock on the parent/root page
1839 */
1844 /* linelock parent entry - 1st slot */
1849 /* update the parent pxd for page extension */
1855 }
1858 /*
1859 * dtSplitRoot()
1860 *
1861 * function:
1862 * split the full root page into
1863 * original/root/split page and new right page
1864 * i.e., root remains fixed in tree anchor (inode) and
1865 * the root is copied to a single new right child page
1866 * since root page << non-root page, and
1867 * the split root page contains a single entry for the
1868 * new right child page.
1869 *
1870 * parameter:
1871 *
1872 * return: 0 - success;
1873 * errno - failure;
1874 * return new page pinned;
1875 */
1878 {
1884 s64 rbn;
1899 /* get split root page */
1903 /*
1904 * allocate/initialize a single (right) child page
1905 *
1906 * N.B. at first split, a one (or two) block to fit new entry
1907 * is allocated; at subsequent split, a full page is allocated;
1908 */
1921 /* Allocate blocks to quota. */
1926 }
1929 /*
1930 * acquire a transaction lock on the new right page
1931 */
1939 /* initialize sibling pointers */
1943 /*
1944 * move in-line root page into new right page extent
1945 */
1946 /* linelock header + copied entries + new stbl (1st slot) in new page */
1957 /* copy old stbl to new stbl at start of extended area */
1963 /* copy old data area to start of new data area */
1966 /*
1967 * append free region of newly extended area at tail of freelist
1968 */
1969 /* init free region of newly extended area */
1976 /* append new free region at tail of old freelist */
1989 }
1993 /*
1994 * Update directory index table for entries now in right page
1995 */
1997 s64 lblock;
2006 }
2009 }
2010 /*
2011 * insert the new entry into the new right/child page
2012 * (skip index in the new right page will not change)
2013 */
2016 /*
2017 * reset parent/root page
2018 *
2019 * set the 1st entry offset to 0, which force the left-most key
2020 * at any level of the tree to be less than any search key.
2021 *
2022 * The btree comparison code guarantees that the left-most key on any
2023 * level of the tree is never used, so it doesn't need to be filled in.
2024 */
2026 /*
2027 * acquire a transaction lock on the root page (in-memory inode)
2028 */
2032 /* linelock root */
2039 /* update page header of root */
2043 }
2045 /* init the first entry */
2056 /* init freelist */
2060 /* init free region of remaining area */
2071 }
2074 /*
2075 * dtDelete()
2076 *
2077 * function: delete the entry(s) referenced by a key.
2078 *
2079 * parameter:
2080 *
2081 * return:
2082 */
2085 {
2087 s64 bn;
2102 /*
2103 * search for the entry to delete:
2104 *
2105 * dtSearch() returns (leaf page pinned, index at which to delete).
2106 */
2110 /* retrieve search result */
2113 /*
2114 * We need to find put the index of the next entry into the
2115 * directory index table in order to resume a readdir from this
2116 * entry.
2117 */
2123 /*
2124 * Last entry in this leaf page
2125 */
2130 /* Read next leaf page */
2137 ldtentry =
2140 next_index =
2143 }
2144 }
2146 ldtentry =
2149 }
2151 }
2152 /*
2153 * the leaf page becomes empty, delete the page
2154 */
2156 /* delete empty page */
2158 }
2159 /*
2160 * the leaf page has other entries remaining:
2161 *
2162 * delete the entry from the leaf page.
2163 */
2166 /*
2167 * acquire a transaction lock on the leaf page
2168 */
2172 /*
2173 * Do not assume that dtlck->index will be zero. During a
2174 * rename within a directory, this transaction may have
2175 * modified this page already when adding the new entry.
2176 */
2178 /* linelock header */
2186 /* linelock stbl of non-root leaf page */
2197 }
2199 /* free the leaf entry */
2202 /*
2203 * Update directory index table for entries moved in stbl
2204 */
2206 s64 lblock;
2211 ldtentry =
2216 }
2219 }
2222 }
2225 }
2228 /*
2229 * dtDeleteUp()
2230 *
2231 * function:
2232 * free empty pages as propagating deletion up the tree
2233 *
2234 * parameter:
2235 *
2236 * return:
2237 */
2240 {
2253 /*
2254 * keep the root leaf page which has become empty
2255 */
2257 /*
2258 * reset the root
2259 *
2260 * dtInitRoot() acquires txlock on the root
2261 */
2267 }
2269 /*
2270 * free the non-root leaf page
2271 */
2272 /*
2273 * acquire a transaction lock on the page
2274 *
2275 * write FREEXTENT|NOREDOPAGE log record
2276 * N.B. linelock is overlaid as freed extent descriptor, and
2277 * the buffer page is freed;
2278 */
2285 /* update sibling pointers */
2289 }
2293 /* Free quota allocation. */
2296 /* free/invalidate its buffer page */
2299 /*
2300 * propagate page deletion up the directory tree
2301 *
2302 * If the delete from the parent page makes it empty,
2303 * continue all the way up the tree.
2304 * stop if the root page is reached (which is never deleted) or
2305 * if the entry deletion does not empty the page.
2306 */
2308 /* pin the parent page <sp> */
2313 /*
2314 * free the extent of the child page deleted
2315 */
2318 /*
2319 * delete the entry for the child page from parent
2320 */
2323 /*
2324 * the parent has the single entry being deleted:
2325 *
2326 * free the parent page which has become empty.
2327 */
2329 /*
2330 * keep the root internal page which has become empty
2331 */
2333 /*
2334 * reset the root
2335 *
2336 * dtInitRoot() acquires txlock on the root
2337 */
2343 }
2344 /*
2345 * free the parent page
2346 */
2348 /*
2349 * acquire a transaction lock on the page
2350 *
2351 * write FREEXTENT|NOREDOPAGE log record
2352 */
2353 tlck =
2361 /* update sibling pointers */
2365 }
2369 /* Free quota allocation */
2372 /* free/invalidate its buffer page */
2375 /* propagate up */
2377 }
2378 }
2380 /*
2381 * the parent has other entries remaining:
2382 *
2383 * delete the router entry from the parent page.
2384 */
2386 /*
2387 * acquire a transaction lock on the page
2388 *
2389 * action: router entry deletion
2390 */
2394 /* linelock header */
2402 /* linelock stbl of non-root leaf page */
2405 lv++;
2409 }
2416 }
2418 /* free the router entry */
2421 /* reset key of new leftmost entry of level (for consistency) */
2426 /* unpin the parent page */
2429 /* exit propagation up */
2431 }
2437 }
2439 #ifdef _NOTYET
2440 /*
2441 * NAME: dtRelocate()
2442 *
2443 * FUNCTION: relocate dtpage (internal or leaf) of directory;
2444 * This function is mainly used by defragfs utility.
2445 */
2447 s64 nxaddr)
2448 {
2452 s64 bn;
2469 xlen);
2471 /*
2472 * 1. get the internal parent dtpage covering
2473 * router entry for the tartget page to be relocated;
2474 */
2479 /* retrieve search result */
2483 /*
2484 * 2. relocate the target dtpage
2485 */
2486 /* read in the target page from src extent */
2489 /* release the pinned parent page */
2492 }
2494 /*
2495 * read in sibling pages if any to update sibling pointers;
2496 */
2505 }
2506 }
2518 }
2519 }
2521 /* at this point, all xtpages to be updated are in memory */
2523 /*
2524 * update sibling pointers of sibling dtpages if any;
2525 */
2529 /* linelock header */
2538 }
2543 /* linelock header */
2552 }
2554 /*
2555 * update the target dtpage to be relocated
2556 *
2557 * write LOG_REDOPAGE of LOG_NEW type for dst page
2558 * for the whole target page (logredo() will apply
2559 * after image and update bmap for allocation of the
2560 * dst extent), and update bmap for allocation of
2561 * the dst extent;
2562 */
2565 /* linelock header */
2569 /* update the self address in the dtpage header */
2573 /* the dst page is the same as the src page, i.e.,
2574 * linelock for afterimage of the whole page;
2575 */
2580 /* update the buffer extent descriptor of the dtpage */
2583 /* unpin the relocated page */
2587 /* the moved extent is dtpage, then a LOG_NOREDOPAGE log rec
2588 * needs to be written (in logredo(), the LOG_NOREDOPAGE log rec
2589 * will also force a bmap update ).
2590 */
2592 /*
2593 * 3. acquire maplock for the source extent to be freed;
2594 */
2595 /* for dtpage relocation, write a LOG_NOREDOPAGE record
2596 * for the source dtpage (logredo() will init NoRedoPage
2597 * filter and will also update bmap for free of the source
2598 * dtpage), and upadte bmap for free of the source dtpage;
2599 */
2607 /*
2608 * 4. update the parent router entry for relocation;
2609 *
2610 * acquire tlck for the parent entry covering the target dtpage;
2611 * write LOG_REDOPAGE to apply after image only;
2612 */
2618 /* update the PXD with the new address */
2626 /* unpin the parent dtpage */
2630 }
2632 /*
2633 * NAME: dtSearchNode()
2634 *
2635 * FUNCTION: Search for an dtpage containing a specified address
2636 * This function is mainly used by defragfs utility.
2637 *
2638 * NOTE: Search result on stack, the found page is pinned at exit.
2639 * The result page must be an internal dtpage.
2640 * lmxaddr give the address of the left most page of the
2641 * dtree level, in which the required dtpage resides.
2642 */
2645 {
2647 s64 bn;
2658 /*
2659 * descend tree to the level with specified leftmost page
2660 *
2661 * by convention, root bn = 0.
2662 */
2664 /* get/pin the page to search */
2669 /* does the xaddr of leftmost page of the levevl
2670 * matches levevl search key ?
2671 */
2678 /*
2679 * descend down to leftmost child page
2680 */
2684 }
2686 /* get the leftmost entry */
2690 /* get the child page block address */
2693 /* unpin the parent page */
2695 }
2697 /*
2698 * search each page at the current levevl
2699 */
2700 loop:
2705 /* found the specified router entry */
2714 }
2715 }
2717 /* get the right sibling page if any */
2723 }
2725 /* unpin current page */
2728 /* get the right sibling page */
2734 }
2737 /*
2738 * dtRelink()
2739 *
2740 * function:
2741 * link around a freed page.
2742 *
2743 * parameter:
2744 * fp: page to be freed
2745 *
2746 * return:
2747 */
2749 {
2760 /* update prev pointer of the next page */
2767 /*
2768 * acquire a transaction lock on the next page
2769 *
2770 * action: update prev pointer;
2771 */
2777 /* linelock header */
2787 }
2789 /* update next pointer of the previous page */
2796 /*
2797 * acquire a transaction lock on the prev page
2798 *
2799 * action: update next pointer;
2800 */
2806 /* linelock header */
2816 }
2819 }
2822 /*
2823 * dtInitRoot()
2824 *
2825 * initialize directory root (inline in inode)
2826 */
2828 {
2836 u16 xflag_save;
2838 /*
2839 * If this was previously an non-empty directory, we need to remove
2840 * the old directory table.
2841 */
2845 /*
2846 * We're playing games with the tid's xflag. If
2847 * we're removing a regular file, the file's xtree
2848 * is committed with COMMIT_PMAP, but we always
2849 * commit the directories xtree with COMMIT_PWMAP.
2850 */
2853 /*
2854 * xtTruncate isn't guaranteed to fully truncate
2855 * the xtree. The caller needs to check i_size
2856 * after committing the transaction to see if
2857 * additional truncation is needed. The
2858 * COMMIT_Stale flag tells caller that we
2859 * initiated the truncation.
2860 */
2872 /*
2873 * acquire a transaction lock on the root
2874 *
2875 * action: directory initialization;
2876 */
2881 /* linelock root */
2894 /* init freelist */
2898 /* init data area of root */
2906 /* init '..' entry */
2910 }
2912 /*
2913 * add_missing_indices()
2914 *
2915 * function: Fix dtree page in which one or more entries has an invalid index.
2916 * fsck.jfs should really fix this, but it currently does not.
2917 * Called from jfs_readdir when bad index is detected.
2918 */
2920 {
2924 uint index;
2930 tid_t tid;
2940 }
2963 }
2964 }
2968 end:
2970 }
2972 /*
2973 * Buffer to hold directory entry info while traversing a dtree page
2974 * before being fed to the filldir function
2975 */
2977 loff_t position;
2979 u16 name_len;
2981 };
2983 /*
2984 * function to determine next variable-sized jfs_dirent in buffer
2985 */
2987 {
2993 }
2995 /*
2996 * jfs_readdir()
2997 *
2998 * function: read directory entries sequentially
2999 * from the specified entry offset
3000 *
3001 * parameter:
3002 *
3003 * return: offset = (pn, index) of start entry
3004 * of next jfs_readdir()/dtRead()
3005 */
3007 {
3013 s16 pn;
3014 s16 index;
3015 s32 unused;
3017 s64 bn;
3029 u32 dir_index;
3041 /*
3042 * persistent index is stored in directory entries.
3043 * Special cases: 0 = .
3044 * 1 = ..
3045 * -1 = End of directory
3046 */
3051 /*
3052 * NFSv4 reserves cookies 1 and 2 for . and .. so the value
3053 * we return to the vfs is one greater than the one we use
3054 * internally.
3055 */
3057 dir_index--;
3064 /* Stale position. Directory has shrunk */
3067 }
3068 repeat:
3073 }
3079 }
3084 }
3086 }
3093 }
3099 }
3102 /*
3103 * self "."
3104 */
3108 }
3109 /*
3110 * parent ".."
3111 */
3116 /*
3117 * Find first entry of left-most leaf
3118 */
3122 }
3128 }
3130 /*
3131 * Legacy filesystem - OS/2 & Linux JFS < 0.3.6
3132 *
3133 * pn = 0; index = 1: First entry "."
3134 * pn = 0; index = 2: Second entry ".."
3135 * pn > 0: Real entries, pn=1 -> leftmost page
3136 * pn = index = -1: No more entries
3137 */
3140 /* build "." entry */
3146 }
3150 /* build ".." entry */
3155 }
3159 }
3164 }
3168 rc);
3171 }
3172 /* get start leaf page and index */
3175 /* offset beyond directory eof ? */
3179 }
3180 }
3188 }
3202 /* DBCS codepages could overrun dirent_buf */
3206 }
3215 /*
3216 * d->index should always be valid, but it
3217 * isn't. fsck.jfs doesn't create the
3218 * directory index for the lost+found
3219 * directory. Rather than let it go,
3220 * we can try to fix it.
3221 */
3227 /*
3228 * setting overflow and setting
3229 * index to i will cause the
3230 * same page to be processed
3231 * again starting here
3232 */
3236 }
3238 }
3239 /*
3240 * We add 1 to the index because we may
3241 * use a value of 2 internally, and NFSv4
3242 * doesn't like that.
3243 */
3248 }
3250 /* copy the name of head/only segment */
3252 codepage);
3255 /* copy name in the additional segment(s) */
3261 /* Sanity Check */
3267 i);
3269 }
3276 }
3278 jfs_dirents++;
3280 skip_one:
3283 }
3286 /* Point to next leaf page */
3292 /* update offset (pn:index) for new page */
3296 }
3297 }
3299 }
3301 /* unpin previous leaf page */
3312 }
3317 }
3322 }
3328 }
3329 }
3331 out:
3335 }
3338 /*
3339 * dtReadFirst()
3340 *
3341 * function: get the leftmost page of the directory
3342 */
3344 {
3346 s64 bn;
3356 /*
3357 * descend leftmost path of the tree
3358 *
3359 * by convention, root bn = 0.
3360 */
3366 /*
3367 * leftmost leaf page
3368 */
3370 /* return leftmost entry */
3377 }
3379 /*
3380 * descend down to leftmost child page
3381 */
3387 }
3388 /* push (bn, index) of the parent page/entry */
3391 /* get the leftmost entry */
3395 /* get the child page block address */
3399 /* unpin the parent page */
3401 }
3402 }
3405 /*
3406 * dtReadNext()
3407 *
3408 * function: get the page of the specified offset (pn:index)
3409 *
3410 * return: if (offset > eof), bn = -1;
3411 *
3412 * note: if index > nextindex of the target leaf page,
3413 * start with 1st entry of next leaf page;
3414 */
3417 {
3420 s16 pn;
3421 s16 index;
3422 s32 unused;
3424 s64 bn;
3433 /*
3434 * get leftmost leaf page pinned
3435 */
3439 /* get leaf page */
3442 /* get the start offset (pn:index) */
3446 /* start at leftmost page ? */
3448 /* offset beyond eof ? */
3455 }
3457 /* start with 1st entry of next leaf page */
3461 }
3463 /* start at non-leftmost page: scan parent pages for large pn */
3467 }
3469 /* start after next leaf page ? */
3473 /* get leaf page pn = 1 */
3474 a:
3477 /* unpin leaf page */
3480 /* offset beyond eof ? */
3484 }
3488 /*
3489 * scan last internal page level to get target leaf page
3490 */
3491 b:
3492 /* unpin leftmost leaf page */
3495 /* get left most parent page */
3503 /* scan parent pages at last internal page level */
3507 /* get next parent page address */
3510 /* unpin current parent page */
3513 /* offset beyond eof ? */
3517 }
3519 /* get next parent page */
3524 /* update parent page stack frame */
3526 }
3528 /* get leaf page address */
3533 /* unpin parent page */
3536 /*
3537 * get target leaf page
3538 */
3539 c:
3544 /*
3545 * leaf page has been completed:
3546 * start with 1st entry of next leaf page
3547 */
3551 /* unpin leaf page */
3554 /* offset beyond eof ? */
3558 }
3560 /* get next leaf page */
3565 /* start with 1st entry of next leaf page */
3568 }
3570 out:
3571 /* return target leaf page pinned */
3578 }
3581 /*
3582 * dtCompare()
3583 *
3584 * function: compare search key with an internal entry
3585 *
3586 * return:
3587 * < 0 if k is < record
3588 * = 0 if k is = record
3589 * > 0 if k is > record
3590 */
3601 /*
3602 * force the left-most key on internal pages, at any level of
3603 * the tree, to be less than any search key.
3604 * this obviates having to update the leftmost key on an internal
3605 * page when the user inserts a new key in the tree smaller than
3606 * anything that has been stored.
3607 *
3608 * (? if/when dtSearch() narrows down to 1st entry (index = 0),
3609 * at any internal page at any level of the tree,
3610 * it descends to child of the entry anyway -
3611 * ? make the entry as min size dummy entry)
3612 *
3613 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
3614 * return (1);
3615 */
3626 /* compare with head/only segment */
3634 /* compare with additional segment(s) */
3637 /* compare with next name segment */
3649 }
3652 }
3657 /*
3658 * ciCompare()
3659 *
3660 * function: compare search key with an (leaf/internal) entry
3661 *
3662 * return:
3663 * < 0 if k is < record
3664 * = 0 if k is = record
3665 * > 0 if k is > record
3666 */
3671 {
3680 /*
3681 * force the left-most key on internal pages, at any level of
3682 * the tree, to be less than any search key.
3683 * this obviates having to update the leftmost key on an internal
3684 * page when the user inserts a new key in the tree smaller than
3685 * anything that has been stored.
3686 *
3687 * (? if/when dtSearch() narrows down to 1st entry (index = 0),
3688 * at any internal page at any level of the tree,
3689 * it descends to child of the entry anyway -
3690 * ? make the entry as min size dummy entry)
3691 *
3692 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
3693 * return (1);
3694 */
3699 /*
3700 * leaf page entry
3701 */
3709 else
3711 }
3712 /*
3713 * internal page entry
3714 */
3721 }
3723 /* compare with head/only segment */
3726 /* only uppercase if case-insensitive support is on */
3729 else
3733 }
3738 /* compare with additional segment(s) */
3740 /* compare with next name segment */
3746 /* only uppercase if case-insensitive support is on */
3749 else
3754 }
3759 }
3762 }
3765 /*
3766 * ciGetLeafPrefixKey()
3767 *
3768 * function: compute prefix of suffix compression
3769 * from two adjacent leaf entries
3770 * across page boundary
3771 *
3772 * return: non-zero on error
3773 *
3774 */
3777 {
3784 GFP_KERNEL);
3789 GFP_KERNEL);
3793 }
3795 /* get left and right key */
3809 /* compute prefix */
3819 }
3820 }
3822 /* l->namlen <= r->namlen since l <= r */
3829 free_names:
3833 }
3837 /*
3838 * dtGetKey()
3839 *
3840 * function: get key of the entry
3841 */
3844 {
3854 /* get entry */
3864 else
3872 }
3877 /*
3878 * move head/only segment
3879 */
3882 /*
3883 * move additional segment(s)
3884 */
3886 /* get next segment */
3894 }
3895 }
3898 /*
3899 * dtInsertEntry()
3900 *
3901 * function: allocate free slot(s) and
3902 * write a leaf/internal entry
3903 *
3904 * return: entry slot index
3905 */
3908 {
3926 /* allocate a free slot */
3932 /* open new linelock */
3939 /* write head/only segment */
3963 }
3970 /* write additional segment(s) */
3974 /* get free slot */
3980 /* is next slot contiguous ? */
3982 /* close current linelock */
3986 /* open new linelock */
3988 lv++;
3992 }
3996 }
4002 n++;
4005 }
4007 /* close current linelock */
4013 /* terminate last/only segment */
4015 /* single segment entry */
4018 else
4021 /* multi-segment entry */
4024 /* if insert into middle, shift right succeeding entries in stbl */
4031 s64 lblock;
4033 /*
4034 * Need to update slot number for entries that moved
4035 * in the stbl
4036 */
4043 }
4046 }
4047 }
4051 /* advance next available entry index of stbl */
4053 }
4056 /*
4057 * dtMoveEntry()
4058 *
4059 * function: move entries from split/left page to new/right page
4060 *
4061 * nextindex of dst page and freelist/freecnt of both pages
4062 * are updated.
4063 */
4067 {
4087 /* linelock destination entry slot */
4091 /* linelock source entry slot */
4096 /*
4097 * move entries
4098 */
4104 /* is next slot contiguous ? */
4106 /* close current linelock */
4110 /* open new linelock */
4112 slv++;
4116 }
4120 }
4122 /*
4123 * move head/only segment of an entry
4124 */
4125 /* get dst slot */
4128 /* get src slot and move */
4131 /* get source entry */
4146 /* update dst head/only segment next field */
4147 dsi++;
4158 dsi++;
4160 }
4162 /* free src head/only segment */
4167 ns++;
4168 nd++;
4171 /*
4172 * move additional segment(s) of the entry
4173 */
4176 /* is next slot contiguous ? */
4178 /* close current linelock */
4182 /* open new linelock */
4184 slv++;
4186 sdtlck =
4190 }
4194 }
4196 /* get next source segment */
4199 /* get next destination free slot */
4200 d++;
4205 ns++;
4206 nd++;
4209 dsi++;
4212 /* free source segment */
4221 /* terminate dst last/only segment */
4223 /* single segment entry */
4226 else
4229 /* multi-segment entry */
4233 /* close current linelock */
4242 /* update source header */
4246 /* update destination header */
4251 }
4254 /*
4255 * dtDeleteEntry()
4256 *
4257 * function: free a (leaf/internal) entry
4258 *
4259 * log freelist header, stbl, and each segment slot of entry
4260 * (even though last/only segment next field is modified,
4261 * physical image logging requires all segment slots of
4262 * the entry logged to avoid applying previous updates
4263 * to the same slots)
4264 */
4266 {
4275 /* get free entry slot index */
4279 /* open new linelock */
4286 /* get the head/only segment */
4290 else
4298 /* find the last/only segment */
4300 /* is next slot contiguous ? */
4302 /* close current linelock */
4306 /* open new linelock */
4308 lv++;
4312 }
4316 }
4318 n++;
4320 freecnt++;
4325 }
4327 /* close current linelock */
4333 /* update freelist */
4338 /* if delete from middle,
4339 * shift left the succedding entries in the stbl
4340 */
4346 }
4349 /*
4350 * dtTruncateEntry()
4351 *
4352 * function: truncate a (leaf/internal) entry
4353 *
4354 * log freelist header, stbl, and each segment slot of entry
4355 * (even though last/only segment next field is modified,
4356 * physical image logging requires all segment slots of
4357 * the entry logged to avoid applying previous updates
4358 * to the same slots)
4359 */
4361 {
4370 /* get free entry slot index */
4374 /* open new linelock */
4381 /* get the head/only segment */
4393 /* find the last/only segment */
4395 /* is next slot contiguous ? */
4397 /* close current linelock */
4401 /* open new linelock */
4403 lv++;
4407 }
4411 }
4413 n++;
4415 freecnt++;
4420 }
4422 /* close current linelock */
4428 /* update freelist */
4434 }
4437 /*
4438 * dtLinelockFreelist()
4439 */
4443 {
4451 /* get free entry slot index */
4454 /* open new linelock */
4467 /* find the last/only segment */
4469 /* is next slot contiguous ? */
4471 /* close current linelock */
4475 /* open new linelock */
4477 lv++;
4481 }
4485 }
4487 n++;
4492 }
4494 /* close current linelock */
4499 }
4502 /*
4503 * NAME: dtModify
4504 *
4505 * FUNCTION: Modify the inode number part of a directory entry
4506 *
4507 * PARAMETERS:
4508 * tid - Transaction id
4509 * ip - Inode of parent directory
4510 * key - Name of entry to be modified
4511 * orig_ino - Original inode number expected in entry
4512 * new_ino - New inode number to put into entry
4513 * flag - JFS_RENAME
4514 *
4515 * RETURNS:
4516 * -ESTALE - If entry found does not match orig_ino passed in
4517 * -ENOENT - If no entry can be found to match key
4518 * 0 - If successfully modified entry
4519 */
4522 {
4524 s64 bn;
4536 /*
4537 * search for the entry to modify:
4538 *
4539 * dtSearch() returns (leaf page pinned, index at which to modify).
4540 */
4544 /* retrieve search result */
4548 /*
4549 * acquire a transaction lock on the leaf page of named entry
4550 */
4554 /* get slot index of the entry */
4558 /* linelock entry */
4565 /* get the head/only segment */
4568 /* substitute the inode number of the entry */
4571 /* unpin the leaf page */
4575 }