Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
jfs_dtree.h
Go to the documentation of this file.
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 {
30  struct inode *ip;
32  } leaf;
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) (DIV_ROUND_UP((4 + (klen)), 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 
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) (DIV_ROUND_UP((2 + (klen)), 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 /*
247  * Maximum file offset for directories.
248  */
249 #define DIREND INT_MAX
250 
251 /*
252  * external declarations
253  */
254 extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
255 
256 extern int dtSearch(struct inode *ip, struct component_name * key,
257  ino_t * data, struct btstack * btstack, int flag);
258 
259 extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
260  ino_t * ino, struct btstack * btstack);
261 
262 extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
263  ino_t * data, int flag);
264 
265 extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
266  ino_t * orig_ino, ino_t new_ino, int flag);
267 
268 extern int jfs_readdir(struct file *filp, void *dirent, filldir_t filldir);
269 #endif /* !_H_JFS_DTREE */