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 2009 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /*
28 * Copyright (c) 2013, 2019 by Delphix. All rights reserved.
29 */
30
31 #ifndef _SYS_RANGE_TREE_H
32 #define _SYS_RANGE_TREE_H
33
34 #include <sys/btree.h>
35 #include <sys/dmu.h>
36
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40
41 #define ZFS_RANGE_TREE_HISTOGRAM_SIZE 64
42
43 typedef struct zfs_range_tree_ops zfs_range_tree_ops_t;
44
45 typedef enum zfs_range_seg_type {
46 ZFS_RANGE_SEG32,
47 ZFS_RANGE_SEG64,
48 ZFS_RANGE_SEG_GAP,
49 ZFS_RANGE_SEG_NUM_TYPES,
50 } zfs_range_seg_type_t;
51
52 #define ZFS_RT_NAME(rt) (((rt)->rt_name != NULL) ? (rt)->rt_name : "")
53 #define ZFS_RT_F_DYN_NAME (1ULL << 0) /* if rt_name must be freed */
54
55 /*
56 * Note: the range_tree may not be accessed concurrently; consumers
57 * must provide external locking if required.
58 */
59 typedef struct zfs_range_tree {
60 zfs_btree_t rt_root; /* offset-ordered segment b-tree */
61 uint64_t rt_space; /* sum of all segments in the map */
62 zfs_range_seg_type_t rt_type; /* type of zfs_range_seg_t in use */
63 /*
64 * All data that is stored in the range tree must have a start higher
65 * than or equal to rt_start, and all sizes and offsets must be
66 * multiples of 1 << rt_shift.
67 */
68 uint8_t rt_shift;
69 uint64_t rt_start;
70 const zfs_range_tree_ops_t *rt_ops;
71 void *rt_arg;
72 uint64_t rt_gap; /* allowable inter-segment gap */
73
74 uint64_t rt_flags;
75 const char *rt_name; /* details for debugging */
76
77 /*
78 * The rt_histogram maintains a histogram of ranges. Each bucket,
79 * rt_histogram[i], contains the number of ranges whose size is:
80 * 2^i <= size of range in bytes < 2^(i+1)
81 */
82 uint64_t rt_histogram[ZFS_RANGE_TREE_HISTOGRAM_SIZE];
83 } zfs_range_tree_t;
84
85 typedef struct zfs_range_seg32 {
86 uint32_t rs_start; /* starting offset of this segment */
87 uint32_t rs_end; /* ending offset (non-inclusive) */
88 } zfs_range_seg32_t;
89
90 /*
91 * Extremely large metaslabs, vdev-wide trees, and dnode-wide trees may
92 * require 64-bit integers for ranges.
93 */
94 typedef struct zfs_range_seg64 {
95 uint64_t rs_start; /* starting offset of this segment */
96 uint64_t rs_end; /* ending offset (non-inclusive) */
97 } zfs_range_seg64_t;
98
99 typedef struct zfs_range_seg_gap {
100 uint64_t rs_start; /* starting offset of this segment */
101 uint64_t rs_end; /* ending offset (non-inclusive) */
102 uint64_t rs_fill; /* actual fill if gap mode is on */
103 } zfs_range_seg_gap_t;
104
105 /*
106 * This type needs to be the largest of the range segs, since it will be stack
107 * allocated and then cast the actual type to do tree operations.
108 */
109 typedef zfs_range_seg_gap_t zfs_range_seg_max_t;
110
111 /*
112 * This is just for clarity of code purposes, so we can make it clear that a
113 * pointer is to a range seg of some type; when we need to do the actual math,
114 * we'll figure out the real type.
115 */
116 typedef void zfs_range_seg_t;
117
118 struct zfs_range_tree_ops {
119 void (*rtop_create)(zfs_range_tree_t *rt, void *arg);
120 void (*rtop_destroy)(zfs_range_tree_t *rt, void *arg);
121 void (*rtop_add)(zfs_range_tree_t *rt, void *rs, void *arg);
122 void (*rtop_remove)(zfs_range_tree_t *rt, void *rs, void *arg);
123 void (*rtop_vacate)(zfs_range_tree_t *rt, void *arg);
124 };
125
126 static inline uint64_t
zfs_rs_get_start_raw(const zfs_range_seg_t * rs,const zfs_range_tree_t * rt)127 zfs_rs_get_start_raw(const zfs_range_seg_t *rs, const zfs_range_tree_t *rt)
128 {
129 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
130 switch (rt->rt_type) {
131 case ZFS_RANGE_SEG32:
132 return (((const zfs_range_seg32_t *)rs)->rs_start);
133 case ZFS_RANGE_SEG64:
134 return (((const zfs_range_seg64_t *)rs)->rs_start);
135 case ZFS_RANGE_SEG_GAP:
136 return (((const zfs_range_seg_gap_t *)rs)->rs_start);
137 default:
138 VERIFY(0);
139 return (0);
140 }
141 }
142
143 static inline uint64_t
zfs_rs_get_end_raw(const zfs_range_seg_t * rs,const zfs_range_tree_t * rt)144 zfs_rs_get_end_raw(const zfs_range_seg_t *rs, const zfs_range_tree_t *rt)
145 {
146 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
147 switch (rt->rt_type) {
148 case ZFS_RANGE_SEG32:
149 return (((const zfs_range_seg32_t *)rs)->rs_end);
150 case ZFS_RANGE_SEG64:
151 return (((const zfs_range_seg64_t *)rs)->rs_end);
152 case ZFS_RANGE_SEG_GAP:
153 return (((const zfs_range_seg_gap_t *)rs)->rs_end);
154 default:
155 VERIFY(0);
156 return (0);
157 }
158 }
159
160 static inline uint64_t
zfs_rs_get_fill_raw(const zfs_range_seg_t * rs,const zfs_range_tree_t * rt)161 zfs_rs_get_fill_raw(const zfs_range_seg_t *rs, const zfs_range_tree_t *rt)
162 {
163 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
164 switch (rt->rt_type) {
165 case ZFS_RANGE_SEG32: {
166 const zfs_range_seg32_t *r32 = (const zfs_range_seg32_t *)rs;
167 return (r32->rs_end - r32->rs_start);
168 }
169 case ZFS_RANGE_SEG64: {
170 const zfs_range_seg64_t *r64 = (const zfs_range_seg64_t *)rs;
171 return (r64->rs_end - r64->rs_start);
172 }
173 case ZFS_RANGE_SEG_GAP:
174 return (((const zfs_range_seg_gap_t *)rs)->rs_fill);
175 default:
176 VERIFY(0);
177 return (0);
178 }
179
180 }
181
182 static inline uint64_t
zfs_rs_get_start(const zfs_range_seg_t * rs,const zfs_range_tree_t * rt)183 zfs_rs_get_start(const zfs_range_seg_t *rs, const zfs_range_tree_t *rt)
184 {
185 return ((zfs_rs_get_start_raw(rs, rt) << rt->rt_shift) + rt->rt_start);
186 }
187
188 static inline uint64_t
zfs_rs_get_end(const zfs_range_seg_t * rs,const zfs_range_tree_t * rt)189 zfs_rs_get_end(const zfs_range_seg_t *rs, const zfs_range_tree_t *rt)
190 {
191 return ((zfs_rs_get_end_raw(rs, rt) << rt->rt_shift) + rt->rt_start);
192 }
193
194 static inline uint64_t
zfs_rs_get_fill(const zfs_range_seg_t * rs,const zfs_range_tree_t * rt)195 zfs_rs_get_fill(const zfs_range_seg_t *rs, const zfs_range_tree_t *rt)
196 {
197 return (zfs_rs_get_fill_raw(rs, rt) << rt->rt_shift);
198 }
199
200 static inline void
zfs_rs_set_start_raw(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t start)201 zfs_rs_set_start_raw(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t start)
202 {
203 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
204 switch (rt->rt_type) {
205 case ZFS_RANGE_SEG32:
206 ASSERT3U(start, <=, UINT32_MAX);
207 ((zfs_range_seg32_t *)rs)->rs_start = (uint32_t)start;
208 break;
209 case ZFS_RANGE_SEG64:
210 ((zfs_range_seg64_t *)rs)->rs_start = start;
211 break;
212 case ZFS_RANGE_SEG_GAP:
213 ((zfs_range_seg_gap_t *)rs)->rs_start = start;
214 break;
215 default:
216 VERIFY(0);
217 }
218 }
219
220 static inline void
zfs_rs_set_end_raw(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t end)221 zfs_rs_set_end_raw(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t end)
222 {
223 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
224 switch (rt->rt_type) {
225 case ZFS_RANGE_SEG32:
226 ASSERT3U(end, <=, UINT32_MAX);
227 ((zfs_range_seg32_t *)rs)->rs_end = (uint32_t)end;
228 break;
229 case ZFS_RANGE_SEG64:
230 ((zfs_range_seg64_t *)rs)->rs_end = end;
231 break;
232 case ZFS_RANGE_SEG_GAP:
233 ((zfs_range_seg_gap_t *)rs)->rs_end = end;
234 break;
235 default:
236 VERIFY(0);
237 }
238 }
239
240 static inline void
zfs_rs_set_fill_raw(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t fill)241 zfs_rs_set_fill_raw(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t fill)
242 {
243 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
244 switch (rt->rt_type) {
245 case ZFS_RANGE_SEG32:
246 /* fall through */
247 case ZFS_RANGE_SEG64:
248 ASSERT3U(fill, ==, zfs_rs_get_end_raw(rs, rt) -
249 zfs_rs_get_start_raw(rs, rt));
250 break;
251 case ZFS_RANGE_SEG_GAP:
252 ((zfs_range_seg_gap_t *)rs)->rs_fill = fill;
253 break;
254 default:
255 VERIFY(0);
256 }
257 }
258
259 static inline void
zfs_rs_set_start(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t start)260 zfs_rs_set_start(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t start)
261 {
262 ASSERT3U(start, >=, rt->rt_start);
263 ASSERT(IS_P2ALIGNED(start, 1ULL << rt->rt_shift));
264 zfs_rs_set_start_raw(rs, rt, (start - rt->rt_start) >> rt->rt_shift);
265 }
266
267 static inline void
zfs_rs_set_end(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t end)268 zfs_rs_set_end(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t end)
269 {
270 ASSERT3U(end, >=, rt->rt_start);
271 ASSERT(IS_P2ALIGNED(end, 1ULL << rt->rt_shift));
272 zfs_rs_set_end_raw(rs, rt, (end - rt->rt_start) >> rt->rt_shift);
273 }
274
275 static inline void
zfs_rs_set_fill(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t fill)276 zfs_rs_set_fill(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t fill)
277 {
278 ASSERT(IS_P2ALIGNED(fill, 1ULL << rt->rt_shift));
279 zfs_rs_set_fill_raw(rs, rt, fill >> rt->rt_shift);
280 }
281
282 typedef void zfs_range_tree_func_t(void *arg, uint64_t start, uint64_t size);
283
284 zfs_range_tree_t *zfs_range_tree_create_gap(const zfs_range_tree_ops_t *ops,
285 zfs_range_seg_type_t type, void *arg, uint64_t start, uint64_t shift,
286 uint64_t gap);
287 zfs_range_tree_t *zfs_range_tree_create(const zfs_range_tree_ops_t *ops,
288 zfs_range_seg_type_t type, void *arg, uint64_t start, uint64_t shift);
289 zfs_range_tree_t *zfs_range_tree_create_flags(const zfs_range_tree_ops_t *ops,
290 zfs_range_seg_type_t type, void *arg, uint64_t start, uint64_t shift,
291 uint64_t flags, const char *name);
292 void zfs_range_tree_destroy(zfs_range_tree_t *rt);
293 boolean_t zfs_range_tree_contains(zfs_range_tree_t *rt, uint64_t start,
294 uint64_t size);
295 zfs_range_seg_t *zfs_range_tree_find(zfs_range_tree_t *rt, uint64_t start,
296 uint64_t size);
297 boolean_t zfs_range_tree_find_in(zfs_range_tree_t *rt, uint64_t start,
298 uint64_t size, uint64_t *ostart, uint64_t *osize);
299 void zfs_range_tree_verify_not_present(zfs_range_tree_t *rt,
300 uint64_t start, uint64_t size);
301 void zfs_range_tree_resize_segment(zfs_range_tree_t *rt, zfs_range_seg_t *rs,
302 uint64_t newstart, uint64_t newsize);
303 uint64_t zfs_range_tree_space(zfs_range_tree_t *rt);
304 uint64_t zfs_range_tree_numsegs(zfs_range_tree_t *rt);
305 boolean_t zfs_range_tree_is_empty(zfs_range_tree_t *rt);
306 void zfs_range_tree_swap(zfs_range_tree_t **rtsrc, zfs_range_tree_t **rtdst);
307 void zfs_range_tree_stat_verify(zfs_range_tree_t *rt);
308 uint64_t zfs_range_tree_min(zfs_range_tree_t *rt);
309 uint64_t zfs_range_tree_max(zfs_range_tree_t *rt);
310 uint64_t zfs_range_tree_span(zfs_range_tree_t *rt);
311
312 void zfs_range_tree_add(void *arg, uint64_t start, uint64_t size);
313 void zfs_range_tree_remove(void *arg, uint64_t start, uint64_t size);
314 void zfs_range_tree_remove_fill(zfs_range_tree_t *rt, uint64_t start,
315 uint64_t size);
316 void zfs_range_tree_adjust_fill(zfs_range_tree_t *rt, zfs_range_seg_t *rs,
317 int64_t delta);
318 void zfs_range_tree_clear(zfs_range_tree_t *rt, uint64_t start, uint64_t size);
319
320 void zfs_range_tree_vacate(zfs_range_tree_t *rt, zfs_range_tree_func_t *func,
321 void *arg);
322 void zfs_range_tree_walk(zfs_range_tree_t *rt, zfs_range_tree_func_t *func,
323 void *arg);
324 zfs_range_seg_t *zfs_range_tree_first(zfs_range_tree_t *rt);
325
326 void zfs_range_tree_remove_xor_add_segment(uint64_t start, uint64_t end,
327 zfs_range_tree_t *removefrom, zfs_range_tree_t *addto);
328 void zfs_range_tree_remove_xor_add(zfs_range_tree_t *rt,
329 zfs_range_tree_t *removefrom, zfs_range_tree_t *addto);
330
331 #ifdef __cplusplus
332 }
333 #endif
334
335 #endif /* _SYS_RANGE_TREE_H */
336