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