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