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 } header; /* (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 } header; /* (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
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.