1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
2 | /* |
3 | * Copyright (C) International Business Machines Corp., 2000-2002 |
4 | */ |
5 | #ifndef _H_JFS_DTREE |
6 | #define _H_JFS_DTREE |
7 | |
8 | /* |
9 | * jfs_dtree.h: directory B+-tree manager |
10 | */ |
11 | |
12 | #include "jfs_btree.h" |
13 | |
14 | typedef union { |
15 | struct { |
16 | tid_t tid; |
17 | struct inode *ip; |
18 | u32 ino; |
19 | } leaf; |
20 | pxd_t xd; |
21 | } ddata_t; |
22 | |
23 | |
24 | /* |
25 | * entry segment/slot |
26 | * |
27 | * an entry consists of type dependent head/only segment/slot and |
28 | * additional segments/slots linked vi next field; |
29 | * N.B. last/only segment of entry is terminated by next = -1; |
30 | */ |
31 | /* |
32 | * directory page slot |
33 | */ |
34 | struct dtslot { |
35 | s8 next; /* 1: */ |
36 | s8 cnt; /* 1: */ |
37 | __le16 name[15]; /* 30: */ |
38 | }; /* (32) */ |
39 | |
40 | |
41 | #define DATASLOTSIZE 16 |
42 | #define L2DATASLOTSIZE 4 |
43 | #define DTSLOTSIZE 32 |
44 | #define L2DTSLOTSIZE 5 |
45 | #define DTSLOTHDRSIZE 2 |
46 | #define DTSLOTDATASIZE 30 |
47 | #define DTSLOTDATALEN 15 |
48 | |
49 | /* |
50 | * internal node entry head/only segment |
51 | */ |
52 | struct idtentry { |
53 | pxd_t xd; /* 8: child extent descriptor */ |
54 | |
55 | s8 next; /* 1: */ |
56 | u8 namlen; /* 1: */ |
57 | __le16 name[11]; /* 22: 2-byte aligned */ |
58 | }; /* (32) */ |
59 | |
60 | #define DTIHDRSIZE 10 |
61 | #define DTIHDRDATALEN 11 |
62 | |
63 | /* compute number of slots for entry */ |
64 | #define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15)) |
65 | |
66 | |
67 | /* |
68 | * leaf node entry head/only segment |
69 | * |
70 | * For legacy filesystems, name contains 13 wchars -- no index field |
71 | */ |
72 | struct ldtentry { |
73 | __le32 inumber; /* 4: 4-byte aligned */ |
74 | s8 next; /* 1: */ |
75 | u8 namlen; /* 1: */ |
76 | __le16 name[11]; /* 22: 2-byte aligned */ |
77 | __le32 index; /* 4: index into dir_table */ |
78 | }; /* (32) */ |
79 | |
80 | #define DTLHDRSIZE 6 |
81 | #define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */ |
82 | #define DTLHDRDATALEN 11 |
83 | |
84 | /* |
85 | * dir_table used for directory traversal during readdir |
86 | */ |
87 | |
88 | /* |
89 | * Keep persistent index for directory entries |
90 | */ |
91 | #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX) |
92 | |
93 | /* |
94 | * Maximum entry in inline directory table |
95 | */ |
96 | #define MAX_INLINE_DIRTABLE_ENTRY 13 |
97 | |
98 | struct dir_table_slot { |
99 | u8 rsrvd; /* 1: */ |
100 | u8 flag; /* 1: 0 if free */ |
101 | u8 slot; /* 1: slot within leaf page of entry */ |
102 | u8 addr1; /* 1: upper 8 bits of leaf page address */ |
103 | __le32 addr2; /* 4: lower 32 bits of leaf page address -OR- |
104 | index of next entry when this entry was deleted */ |
105 | }; /* (8) */ |
106 | |
107 | /* |
108 | * flag values |
109 | */ |
110 | #define DIR_INDEX_VALID 1 |
111 | #define DIR_INDEX_FREE 0 |
112 | |
113 | #define DTSaddress(dir_table_slot, address64)\ |
114 | {\ |
115 | (dir_table_slot)->addr1 = ((u64)address64) >> 32;\ |
116 | (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\ |
117 | } |
118 | |
119 | #define addressDTS(dts)\ |
120 | ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) ) |
121 | |
122 | /* compute number of slots for entry */ |
123 | #define NDTLEAF_LEGACY(klen) (DIV_ROUND_UP((2 + (klen)), 15)) |
124 | #define NDTLEAF NDTINTERNAL |
125 | |
126 | |
127 | /* |
128 | * directory root page (in-line in on-disk inode): |
129 | * |
130 | * cf. dtpage_t below. |
131 | */ |
132 | typedef union { |
133 | struct { |
134 | struct dasd DASD; /* 16: DASD limit/usage info */ |
135 | |
136 | u8 flag; /* 1: */ |
137 | u8 nextindex; /* 1: next free entry in stbl */ |
138 | s8 freecnt; /* 1: free count */ |
139 | s8 freelist; /* 1: freelist header */ |
140 | |
141 | __le32 idotdot; /* 4: parent inode number */ |
142 | |
143 | s8 stbl[8]; /* 8: sorted entry index table */ |
144 | } ; /* (32) */ |
145 | |
146 | struct dtslot slot[9]; |
147 | } dtroot_t; |
148 | |
149 | #define PARENT(IP) \ |
150 | (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot)) |
151 | |
152 | #define DTROOTMAXSLOT 9 |
153 | |
154 | #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0) |
155 | |
156 | |
157 | /* |
158 | * directory regular page: |
159 | * |
160 | * entry slot array of 32 byte slot |
161 | * |
162 | * sorted entry slot index table (stbl): |
163 | * contiguous slots at slot specified by stblindex, |
164 | * 1-byte per entry |
165 | * 512 byte block: 16 entry tbl (1 slot) |
166 | * 1024 byte block: 32 entry tbl (1 slot) |
167 | * 2048 byte block: 64 entry tbl (2 slot) |
168 | * 4096 byte block: 128 entry tbl (4 slot) |
169 | * |
170 | * data area: |
171 | * 512 byte block: 16 - 2 = 14 slot |
172 | * 1024 byte block: 32 - 2 = 30 slot |
173 | * 2048 byte block: 64 - 3 = 61 slot |
174 | * 4096 byte block: 128 - 5 = 123 slot |
175 | * |
176 | * N.B. index is 0-based; index fields refer to slot index |
177 | * except nextindex which refers to entry index in stbl; |
178 | * end of entry stot list or freelist is marked with -1. |
179 | */ |
180 | typedef union { |
181 | struct { |
182 | __le64 next; /* 8: next sibling */ |
183 | __le64 prev; /* 8: previous sibling */ |
184 | |
185 | u8 flag; /* 1: */ |
186 | u8 nextindex; /* 1: next entry index in stbl */ |
187 | s8 freecnt; /* 1: */ |
188 | s8 freelist; /* 1: slot index of head of freelist */ |
189 | |
190 | u8 maxslot; /* 1: number of slots in page slot[] */ |
191 | u8 stblindex; /* 1: slot index of start of stbl */ |
192 | u8 rsrvd[2]; /* 2: */ |
193 | |
194 | pxd_t self; /* 8: self pxd */ |
195 | } ; /* (32) */ |
196 | |
197 | struct dtslot slot[128]; |
198 | } dtpage_t; |
199 | |
200 | #define DTPAGEMAXSLOT 128 |
201 | |
202 | #define DT8THPGNODEBYTES 512 |
203 | #define DT8THPGNODETSLOTS 1 |
204 | #define DT8THPGNODESLOTS 16 |
205 | |
206 | #define DTQTRPGNODEBYTES 1024 |
207 | #define DTQTRPGNODETSLOTS 1 |
208 | #define DTQTRPGNODESLOTS 32 |
209 | |
210 | #define DTHALFPGNODEBYTES 2048 |
211 | #define DTHALFPGNODETSLOTS 2 |
212 | #define DTHALFPGNODESLOTS 64 |
213 | |
214 | #define DTFULLPGNODEBYTES 4096 |
215 | #define DTFULLPGNODETSLOTS 4 |
216 | #define DTFULLPGNODESLOTS 128 |
217 | |
218 | #define DTENTRYSTART 1 |
219 | |
220 | /* get sorted entry table of the page */ |
221 | #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\ |
222 | ((dtroot_t *)(p))->header.stbl : \ |
223 | (s8 *)&(p)->slot[(p)->header.stblindex] ) |
224 | |
225 | /* |
226 | * Flags for dtSearch |
227 | */ |
228 | #define JFS_CREATE 1 |
229 | #define JFS_LOOKUP 2 |
230 | #define JFS_REMOVE 3 |
231 | #define JFS_RENAME 4 |
232 | |
233 | /* |
234 | * Maximum file offset for directories. |
235 | */ |
236 | #define DIREND INT_MAX |
237 | |
238 | /* |
239 | * external declarations |
240 | */ |
241 | extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot); |
242 | |
243 | extern int dtSearch(struct inode *ip, struct component_name * key, |
244 | ino_t * data, struct btstack * btstack, int flag); |
245 | |
246 | extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key, |
247 | ino_t * ino, struct btstack * btstack); |
248 | |
249 | extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key, |
250 | ino_t * data, int flag); |
251 | |
252 | extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key, |
253 | ino_t * orig_ino, ino_t new_ino, int flag); |
254 | |
255 | extern int jfs_readdir(struct file *file, struct dir_context *ctx); |
256 | #endif /* !_H_JFS_DTREE */ |
257 | |