2 * Copyright (c) 2000-2001 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
32 #ifndef __XFS_DIR_LEAF_H__
33 #define __XFS_DIR_LEAF_H__
36 * Directory layout, internal structure, access macros, etc.
38 * Large directories are structured around Btrees where all the data
39 * elements are in the leaf nodes. Filenames are hashed into an int,
40 * then that int is used as the index into the Btree. Since the hashval
41 * of a filename may not be unique, we may have duplicate keys. The
42 * internal links in the Btree are logical block offsets into the file.
51 struct xfs_da_state_blk
;
52 struct xfs_dir_put_args
;
57 /*========================================================================
58 * Directory Structure when equal to XFS_LBSIZE(mp) bytes.
59 *========================================================================*/
62 * This is the structure of the leaf nodes in the Btree.
64 * Struct leaf_entry's are packed from the top. Names grow from the bottom
65 * but are not packed. The freemap contains run-length-encoded entries
66 * for the free bytes after the leaf_entry's, but only the N largest such,
67 * smaller runs are dropped. When the freemap doesn't show enough space
68 * for an allocation, we compact the namelist area and try again. If we
69 * still don't have enough space, then we have to split the block.
71 * Since we have duplicate hash keys, for each key that matches, compare
72 * the actual string. The root and intermediate node search always takes
73 * the first-in-the-block key match found, so we should only have to work
74 * "forw"ard. If none matches, continue with the "forw"ard leaf nodes
75 * until the hash key changes or the filename is found.
77 * The parent directory and the self-pointer are explicitly represented
78 * (ie: there are entries for "." and "..").
80 * Note that the count being a __uint16_t limits us to something like a
81 * blocksize of 1.3MB in the face of worst case (short) filenames.
83 #define XFS_DIR_LEAF_MAPSIZE 3 /* how many freespace slots */
85 typedef struct xfs_dir_leafblock
{
86 struct xfs_dir_leaf_hdr
{ /* constant-structure header block */
87 xfs_da_blkinfo_t info
; /* block type, links, etc. */
88 __uint16_t count
; /* count of active leaf_entry's */
89 __uint16_t namebytes
; /* num bytes of name strings stored */
90 __uint16_t firstused
; /* first used byte in name area */
91 __uint8_t holes
; /* != 0 if blk needs compaction */
93 struct xfs_dir_leaf_map
{/* RLE map of free bytes */
94 __uint16_t base
; /* base of free region */
95 __uint16_t size
; /* run length of free region */
96 } freemap
[XFS_DIR_LEAF_MAPSIZE
]; /* N largest free regions */
98 struct xfs_dir_leaf_entry
{ /* sorted on key, not name */
99 xfs_dahash_t hashval
; /* hash value of name */
100 __uint16_t nameidx
; /* index into buffer of name */
101 __uint8_t namelen
; /* length of name string */
103 } entries
[1]; /* var sized array */
104 struct xfs_dir_leaf_name
{
105 xfs_dir_ino_t inumber
; /* inode number for this key */
106 __uint8_t name
[1]; /* name string itself */
107 } namelist
[1]; /* grows from bottom of buf */
108 } xfs_dir_leafblock_t
;
109 typedef struct xfs_dir_leaf_hdr xfs_dir_leaf_hdr_t
;
110 typedef struct xfs_dir_leaf_map xfs_dir_leaf_map_t
;
111 typedef struct xfs_dir_leaf_entry xfs_dir_leaf_entry_t
;
112 typedef struct xfs_dir_leaf_name xfs_dir_leaf_name_t
;
115 * Length of name for which a 512-byte block filesystem
116 * can get a double split.
118 #define XFS_DIR_LEAF_CAN_DOUBLE_SPLIT_LEN \
119 (512 - (uint)sizeof(xfs_dir_leaf_hdr_t) - \
120 (uint)sizeof(xfs_dir_leaf_entry_t) * 2 - \
121 (uint)sizeof(xfs_dir_leaf_name_t) * 2 - (MAXNAMELEN - 2) + 1 + 1)
123 typedef int (*xfs_dir_put_t
)(struct xfs_dir_put_args
*pa
);
126 xfs_off_t o
; /* offset (cookie) */
128 * Watch the order here (endian-ness dependent).
131 #if __BYTE_ORDER == __LITTLE_ENDIAN
132 xfs_dahash_t h
; /* hash value */
133 __uint32_t be
; /* block and entry */
134 #else /* __BYTE_ORDER == __BIG_ENDIAN */
135 __uint32_t be
; /* block and entry */
136 xfs_dahash_t h
; /* hash value */
137 #endif /* __BYTE_ORDER == __BIG_ENDIAN */
141 #define XFS_PUT_COOKIE(c,mp,bno,entry,hash) \
142 ((c).s.be = XFS_DA_MAKE_BNOENTRY(mp, bno, entry), (c).s.h = (hash))
144 #define XFS_GET_DIR_INO_ARCH(mp,di,arch) \
145 DIRINO_GET_ARCH(&(di),arch)
146 #define XFS_GET_DIR_INO(mp,di) \
147 XFS_GET_DIR_INO_ARCH(mp,di,ARCH_NOCONVERT)
149 typedef struct xfs_dir_put_args
151 xfs_dircook_t cook
; /* cookie of (next) entry */
152 xfs_intino_t ino
; /* inode number */
153 struct xfs_dirent
*dbp
; /* buffer pointer */
154 char *name
; /* directory entry name */
155 int namelen
; /* length of name */
156 int done
; /* output: set if value was stored */
157 xfs_dir_put_t put
; /* put function ptr (i/o) */
158 struct uio
*uio
; /* uio control structure */
159 } xfs_dir_put_args_t
;
161 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DIR_LEAF_ENTSIZE_BYNAME)
162 int xfs_dir_leaf_entsize_byname(int len
);
163 #define XFS_DIR_LEAF_ENTSIZE_BYNAME(len) xfs_dir_leaf_entsize_byname(len)
165 #define XFS_DIR_LEAF_ENTSIZE_BYNAME(len) /* space a name will use */ \
166 ((uint)sizeof(xfs_dir_leaf_name_t)-1 + len)
168 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DIR_LEAF_ENTSIZE_BYENTRY)
169 int xfs_dir_leaf_entsize_byentry(xfs_dir_leaf_entry_t
*entry
);
170 #define XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry) \
171 xfs_dir_leaf_entsize_byentry(entry)
173 #define XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry) /* space an entry will use */ \
174 ((uint)sizeof(xfs_dir_leaf_name_t)-1 + (entry)->namelen)
176 #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_DIR_LEAF_NAMESTRUCT)
177 xfs_dir_leaf_name_t
*
178 xfs_dir_leaf_namestruct(xfs_dir_leafblock_t
*leafp
, int offset
);
179 #define XFS_DIR_LEAF_NAMESTRUCT(leafp,offset) \
180 xfs_dir_leaf_namestruct(leafp,offset)
182 #define XFS_DIR_LEAF_NAMESTRUCT(leafp,offset) /* point to name struct */ \
183 ((xfs_dir_leaf_name_t *)&((char *)(leafp))[offset])
186 /*========================================================================
187 * Function prototypes for the kernel.
188 *========================================================================*/
191 * Internal routines when dirsize < XFS_LITINO(mp).
193 int xfs_dir_shortform_create(struct xfs_da_args
*args
, xfs_ino_t parent
);
194 int xfs_dir_shortform_addname(struct xfs_da_args
*args
);
195 int xfs_dir_shortform_lookup(struct xfs_da_args
*args
);
196 int xfs_dir_shortform_to_leaf(struct xfs_da_args
*args
);
197 int xfs_dir_shortform_removename(struct xfs_da_args
*args
);
198 int xfs_dir_shortform_getdents(struct xfs_inode
*dp
, struct uio
*uio
, int *eofp
,
199 struct xfs_dirent
*dbp
, xfs_dir_put_t put
);
200 int xfs_dir_shortform_replace(struct xfs_da_args
*args
);
203 * Internal routines when dirsize == XFS_LBSIZE(mp).
205 int xfs_dir_leaf_to_node(struct xfs_da_args
*args
);
206 int xfs_dir_leaf_to_shortform(struct xfs_da_args
*args
);
209 * Routines used for growing the Btree.
211 int xfs_dir_leaf_create(struct xfs_da_args
*args
, xfs_dablk_t which_block
,
212 struct xfs_dabuf
**bpp
);
213 int xfs_dir_leaf_split(struct xfs_da_state
*state
,
214 struct xfs_da_state_blk
*oldblk
,
215 struct xfs_da_state_blk
*newblk
);
216 int xfs_dir_leaf_add(struct xfs_dabuf
*leaf_buffer
,
217 struct xfs_da_args
*args
, int insertion_index
);
218 int xfs_dir_leaf_addname(struct xfs_da_args
*args
);
219 int xfs_dir_leaf_lookup_int(struct xfs_dabuf
*leaf_buffer
,
220 struct xfs_da_args
*args
,
221 int *index_found_at
);
222 int xfs_dir_leaf_remove(struct xfs_trans
*trans
,
223 struct xfs_dabuf
*leaf_buffer
,
224 int index_to_remove
);
225 int xfs_dir_leaf_getdents_int(struct xfs_dabuf
*bp
, struct xfs_inode
*dp
,
226 xfs_dablk_t bno
, struct uio
*uio
,
227 int *eobp
, struct xfs_dirent
*dbp
,
228 xfs_dir_put_t put
, xfs_daddr_t nextda
);
231 * Routines used for shrinking the Btree.
233 int xfs_dir_leaf_toosmall(struct xfs_da_state
*state
, int *retval
);
234 void xfs_dir_leaf_unbalance(struct xfs_da_state
*state
,
235 struct xfs_da_state_blk
*drop_blk
,
236 struct xfs_da_state_blk
*save_blk
);
241 uint
xfs_dir_leaf_lasthash(struct xfs_dabuf
*bp
, int *count
);
242 int xfs_dir_leaf_order(struct xfs_dabuf
*leaf1_bp
,
243 struct xfs_dabuf
*leaf2_bp
);
244 int xfs_dir_put_dirent32_direct(xfs_dir_put_args_t
*pa
);
245 int xfs_dir_put_dirent32_uio(xfs_dir_put_args_t
*pa
);
246 int xfs_dir_put_dirent64_direct(xfs_dir_put_args_t
*pa
);
247 int xfs_dir_put_dirent64_uio(xfs_dir_put_args_t
*pa
);
248 int xfs_dir_ino_validate(struct xfs_mount
*mp
, xfs_ino_t ino
);
254 extern xfs_dahash_t xfs_dir_hash_dot
, xfs_dir_hash_dotdot
;
256 #endif /* __XFS_DIR_LEAF_H__ */