]>
Commit | Line | Data |
---|---|---|
34dc7c2f BB |
1 | /* |
2 | * CDDL HEADER START | |
3 | * | |
4 | * The contents of this file are subject to the terms of the | |
5 | * Common Development and Distribution License (the "License"). | |
6 | * You may not use this file except in compliance with the License. | |
7 | * | |
8 | * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE | |
9 | * or http://www.opensolaris.org/os/licensing. | |
10 | * See the License for the specific language governing permissions | |
11 | * and limitations under the License. | |
12 | * | |
13 | * When distributing Covered Code, include this CDDL HEADER in each | |
14 | * file and include the License file at usr/src/OPENSOLARIS.LICENSE. | |
15 | * If applicable, add the following below this CDDL HEADER, with the | |
16 | * fields enclosed by brackets "[]" replaced with your own identifying | |
17 | * information: Portions Copyright [yyyy] [name of copyright owner] | |
18 | * | |
19 | * CDDL HEADER END | |
20 | */ | |
21 | /* | |
428870ff | 22 | * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved. |
0c66c32d | 23 | * Copyright (c) 2014 Spectra Logic Corporation, All rights reserved. |
34dc7c2f BB |
24 | */ |
25 | ||
26 | #ifndef _SYS_ZAP_LEAF_H | |
27 | #define _SYS_ZAP_LEAF_H | |
28 | ||
428870ff | 29 | #include <sys/zap.h> |
34dc7c2f BB |
30 | |
31 | #ifdef __cplusplus | |
32 | extern "C" { | |
33 | #endif | |
34 | ||
35 | struct zap; | |
428870ff BB |
36 | struct zap_name; |
37 | struct zap_stats; | |
34dc7c2f BB |
38 | |
39 | #define ZAP_LEAF_MAGIC 0x2AB1EAF | |
40 | ||
41 | /* chunk size = 24 bytes */ | |
42 | #define ZAP_LEAF_CHUNKSIZE 24 | |
43 | ||
44 | /* | |
45 | * The amount of space available for chunks is: | |
46 | * block size (1<<l->l_bs) - hash entry size (2) * number of hash | |
47 | * entries - header space (2*chunksize) | |
48 | */ | |
599b8648 CC |
49 | #define ZAP_LEAF_NUMCHUNKS_BS(bs) \ |
50 | (((1<<(bs)) - 2*ZAP_LEAF_HASH_NUMENTRIES_BS(bs)) / \ | |
34dc7c2f BB |
51 | ZAP_LEAF_CHUNKSIZE - 2) |
52 | ||
599b8648 CC |
53 | #define ZAP_LEAF_NUMCHUNKS(l) (ZAP_LEAF_NUMCHUNKS_BS(((l)->l_bs))) |
54 | ||
55 | #define ZAP_LEAF_NUMCHUNKS_DEF \ | |
56 | (ZAP_LEAF_NUMCHUNKS_BS(fzap_default_block_shift)) | |
57 | ||
34dc7c2f BB |
58 | /* |
59 | * The amount of space within the chunk available for the array is: | |
60 | * chunk size - space for type (1) - space for next pointer (2) | |
61 | */ | |
62 | #define ZAP_LEAF_ARRAY_BYTES (ZAP_LEAF_CHUNKSIZE - 3) | |
63 | ||
64 | #define ZAP_LEAF_ARRAY_NCHUNKS(bytes) \ | |
65 | (((bytes)+ZAP_LEAF_ARRAY_BYTES-1)/ZAP_LEAF_ARRAY_BYTES) | |
66 | ||
67 | /* | |
68 | * Low water mark: when there are only this many chunks free, start | |
69 | * growing the ptrtbl. Ideally, this should be larger than a | |
70 | * "reasonably-sized" entry. 20 chunks is more than enough for the | |
71 | * largest directory entry (MAXNAMELEN (256) byte name, 8-byte value), | |
72 | * while still being only around 3% for 16k blocks. | |
73 | */ | |
74 | #define ZAP_LEAF_LOW_WATER (20) | |
75 | ||
76 | /* | |
77 | * The leaf hash table has block size / 2^5 (32) number of entries, | |
78 | * which should be more than enough for the maximum number of entries, | |
79 | * which is less than block size / CHUNKSIZE (24) / minimum number of | |
80 | * chunks per entry (3). | |
81 | */ | |
599b8648 CC |
82 | #define ZAP_LEAF_HASH_SHIFT_BS(bs) ((bs) - 5) |
83 | #define ZAP_LEAF_HASH_NUMENTRIES_BS(bs) (1 << ZAP_LEAF_HASH_SHIFT_BS(bs)) | |
84 | #define ZAP_LEAF_HASH_SHIFT(l) (ZAP_LEAF_HASH_SHIFT_BS(((l)->l_bs))) | |
85 | #define ZAP_LEAF_HASH_NUMENTRIES(l) (ZAP_LEAF_HASH_NUMENTRIES_BS(((l)->l_bs))) | |
34dc7c2f BB |
86 | |
87 | /* | |
88 | * The chunks start immediately after the hash table. The end of the | |
89 | * hash table is at l_hash + HASH_NUMENTRIES, which we simply cast to a | |
90 | * chunk_t. | |
91 | */ | |
92 | #define ZAP_LEAF_CHUNK(l, idx) \ | |
93 | ((zap_leaf_chunk_t *) \ | |
d683ddbb | 94 | (zap_leaf_phys(l)->l_hash + ZAP_LEAF_HASH_NUMENTRIES(l)))[idx] |
34dc7c2f BB |
95 | #define ZAP_LEAF_ENTRY(l, idx) (&ZAP_LEAF_CHUNK(l, idx).l_entry) |
96 | ||
97 | typedef enum zap_chunk_type { | |
98 | ZAP_CHUNK_FREE = 253, | |
99 | ZAP_CHUNK_ENTRY = 252, | |
100 | ZAP_CHUNK_ARRAY = 251, | |
101 | ZAP_CHUNK_TYPE_MAX = 250 | |
102 | } zap_chunk_type_t; | |
103 | ||
104 | #define ZLF_ENTRIES_CDSORTED (1<<0) | |
105 | ||
106 | /* | |
107 | * TAKE NOTE: | |
108 | * If zap_leaf_phys_t is modified, zap_leaf_byteswap() must be modified. | |
109 | */ | |
110 | typedef struct zap_leaf_phys { | |
111 | struct zap_leaf_header { | |
d3cc8b15 | 112 | /* Public to ZAP */ |
34dc7c2f BB |
113 | uint64_t lh_block_type; /* ZBT_LEAF */ |
114 | uint64_t lh_pad1; | |
115 | uint64_t lh_prefix; /* hash prefix of this leaf */ | |
116 | uint32_t lh_magic; /* ZAP_LEAF_MAGIC */ | |
117 | uint16_t lh_nfree; /* number free chunks */ | |
118 | uint16_t lh_nentries; /* number of entries */ | |
119 | uint16_t lh_prefix_len; /* num bits used to id this */ | |
120 | ||
d3cc8b15 | 121 | /* Private to zap_leaf */ |
34dc7c2f BB |
122 | uint16_t lh_freelist; /* chunk head of free list */ |
123 | uint8_t lh_flags; /* ZLF_* flags */ | |
124 | uint8_t lh_pad2[11]; | |
125 | } l_hdr; /* 2 24-byte chunks */ | |
126 | ||
127 | /* | |
128 | * The header is followed by a hash table with | |
129 | * ZAP_LEAF_HASH_NUMENTRIES(zap) entries. The hash table is | |
130 | * followed by an array of ZAP_LEAF_NUMCHUNKS(zap) | |
131 | * zap_leaf_chunk structures. These structures are accessed | |
132 | * with the ZAP_LEAF_CHUNK() macro. | |
133 | */ | |
134 | ||
135 | uint16_t l_hash[1]; | |
136 | } zap_leaf_phys_t; | |
137 | ||
138 | typedef union zap_leaf_chunk { | |
139 | struct zap_leaf_entry { | |
140 | uint8_t le_type; /* always ZAP_CHUNK_ENTRY */ | |
428870ff | 141 | uint8_t le_value_intlen; /* size of value's ints */ |
34dc7c2f BB |
142 | uint16_t le_next; /* next entry in hash chain */ |
143 | uint16_t le_name_chunk; /* first chunk of the name */ | |
428870ff | 144 | uint16_t le_name_numints; /* ints in name (incl null) */ |
34dc7c2f | 145 | uint16_t le_value_chunk; /* first chunk of the value */ |
428870ff | 146 | uint16_t le_value_numints; /* value length in ints */ |
34dc7c2f BB |
147 | uint32_t le_cd; /* collision differentiator */ |
148 | uint64_t le_hash; /* hash value of the name */ | |
149 | } l_entry; | |
150 | struct zap_leaf_array { | |
151 | uint8_t la_type; /* always ZAP_CHUNK_ARRAY */ | |
152 | uint8_t la_array[ZAP_LEAF_ARRAY_BYTES]; | |
153 | uint16_t la_next; /* next blk or CHAIN_END */ | |
154 | } l_array; | |
155 | struct zap_leaf_free { | |
156 | uint8_t lf_type; /* always ZAP_CHUNK_FREE */ | |
157 | uint8_t lf_pad[ZAP_LEAF_ARRAY_BYTES]; | |
158 | uint16_t lf_next; /* next in free list, or CHAIN_END */ | |
159 | } l_free; | |
160 | } zap_leaf_chunk_t; | |
161 | ||
162 | typedef struct zap_leaf { | |
0c66c32d | 163 | dmu_buf_user_t l_dbu; |
b128c09f | 164 | krwlock_t l_rwlock; |
34dc7c2f BB |
165 | uint64_t l_blkid; /* 1<<ZAP_BLOCK_SHIFT byte block off */ |
166 | int l_bs; /* block size shift */ | |
167 | dmu_buf_t *l_dbuf; | |
34dc7c2f BB |
168 | } zap_leaf_t; |
169 | ||
d683ddbb JG |
170 | static inline zap_leaf_phys_t * |
171 | zap_leaf_phys(zap_leaf_t *l) | |
172 | { | |
173 | return (l->l_dbuf->db_data); | |
174 | } | |
34dc7c2f BB |
175 | |
176 | typedef struct zap_entry_handle { | |
d3cc8b15 | 177 | /* Set by zap_leaf and public to ZAP */ |
34dc7c2f BB |
178 | uint64_t zeh_num_integers; |
179 | uint64_t zeh_hash; | |
180 | uint32_t zeh_cd; | |
181 | uint8_t zeh_integer_size; | |
182 | ||
d3cc8b15 | 183 | /* Private to zap_leaf */ |
34dc7c2f BB |
184 | uint16_t zeh_fakechunk; |
185 | uint16_t *zeh_chunkp; | |
186 | zap_leaf_t *zeh_leaf; | |
187 | } zap_entry_handle_t; | |
188 | ||
189 | /* | |
190 | * Return a handle to the named entry, or ENOENT if not found. The hash | |
191 | * value must equal zap_hash(name). | |
192 | */ | |
193 | extern int zap_leaf_lookup(zap_leaf_t *l, | |
428870ff | 194 | struct zap_name *zn, zap_entry_handle_t *zeh); |
34dc7c2f BB |
195 | |
196 | /* | |
197 | * Return a handle to the entry with this hash+cd, or the entry with the | |
198 | * next closest hash+cd. | |
199 | */ | |
200 | extern int zap_leaf_lookup_closest(zap_leaf_t *l, | |
201 | uint64_t hash, uint32_t cd, zap_entry_handle_t *zeh); | |
202 | ||
203 | /* | |
204 | * Read the first num_integers in the attribute. Integer size | |
205 | * conversion will be done without sign extension. Return EINVAL if | |
206 | * integer_size is too small. Return EOVERFLOW if there are more than | |
207 | * num_integers in the attribute. | |
208 | */ | |
209 | extern int zap_entry_read(const zap_entry_handle_t *zeh, | |
428870ff | 210 | uint8_t integer_size, uint64_t num_integers, void *buf); |
34dc7c2f | 211 | |
428870ff BB |
212 | extern int zap_entry_read_name(struct zap *zap, const zap_entry_handle_t *zeh, |
213 | uint16_t buflen, char *buf); | |
34dc7c2f BB |
214 | |
215 | /* | |
216 | * Replace the value of an existing entry. | |
217 | * | |
d3cc8b15 | 218 | * May fail if it runs out of space (ENOSPC). |
34dc7c2f BB |
219 | */ |
220 | extern int zap_entry_update(zap_entry_handle_t *zeh, | |
428870ff | 221 | uint8_t integer_size, uint64_t num_integers, const void *buf); |
34dc7c2f BB |
222 | |
223 | /* | |
224 | * Remove an entry. | |
225 | */ | |
226 | extern void zap_entry_remove(zap_entry_handle_t *zeh); | |
227 | ||
228 | /* | |
229 | * Create an entry. An equal entry must not exist, and this entry must | |
230 | * belong in this leaf (according to its hash value). Fills in the | |
231 | * entry handle on success. Returns 0 on success or ENOSPC on failure. | |
232 | */ | |
428870ff BB |
233 | extern int zap_entry_create(zap_leaf_t *l, struct zap_name *zn, uint32_t cd, |
234 | uint8_t integer_size, uint64_t num_integers, const void *buf, | |
235 | zap_entry_handle_t *zeh); | |
34dc7c2f | 236 | |
d3cc8b15 | 237 | /* Determine whether there is another entry with the same normalized form. */ |
34dc7c2f | 238 | extern boolean_t zap_entry_normalization_conflict(zap_entry_handle_t *zeh, |
428870ff | 239 | struct zap_name *zn, const char *name, struct zap *zap); |
34dc7c2f BB |
240 | |
241 | /* | |
242 | * Other stuff. | |
243 | */ | |
244 | ||
245 | extern void zap_leaf_init(zap_leaf_t *l, boolean_t sort); | |
246 | extern void zap_leaf_byteswap(zap_leaf_phys_t *buf, int len); | |
247 | extern void zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl, boolean_t sort); | |
428870ff BB |
248 | extern void zap_leaf_stats(struct zap *zap, zap_leaf_t *l, |
249 | struct zap_stats *zs); | |
34dc7c2f BB |
250 | |
251 | #ifdef __cplusplus | |
252 | } | |
253 | #endif | |
254 | ||
255 | #endif /* _SYS_ZAP_LEAF_H */ |