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_zfs_rs_set_fill_raw(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t fill)241 zfs_zfs_rs_set_fill_raw(zfs_range_seg_t *rs, zfs_range_tree_t *rt,
242 uint64_t fill)
243 {
244 ASSERT3U(rt->rt_type, <=, ZFS_RANGE_SEG_NUM_TYPES);
245 switch (rt->rt_type) {
246 case ZFS_RANGE_SEG32:
247 /* fall through */
248 case ZFS_RANGE_SEG64:
249 ASSERT3U(fill, ==, zfs_rs_get_end_raw(rs, rt) -
250 zfs_rs_get_start_raw(rs, rt));
251 break;
252 case ZFS_RANGE_SEG_GAP:
253 ((zfs_range_seg_gap_t *)rs)->rs_fill = fill;
254 break;
255 default:
256 VERIFY(0);
257 }
258 }
259
260 static inline void
zfs_rs_set_start(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t start)261 zfs_rs_set_start(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t start)
262 {
263 ASSERT3U(start, >=, rt->rt_start);
264 ASSERT(IS_P2ALIGNED(start, 1ULL << rt->rt_shift));
265 zfs_rs_set_start_raw(rs, rt, (start - rt->rt_start) >> rt->rt_shift);
266 }
267
268 static inline void
zfs_rs_set_end(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t end)269 zfs_rs_set_end(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t end)
270 {
271 ASSERT3U(end, >=, rt->rt_start);
272 ASSERT(IS_P2ALIGNED(end, 1ULL << rt->rt_shift));
273 zfs_rs_set_end_raw(rs, rt, (end - rt->rt_start) >> rt->rt_shift);
274 }
275
276 static inline void
zfs_rs_set_fill(zfs_range_seg_t * rs,zfs_range_tree_t * rt,uint64_t fill)277 zfs_rs_set_fill(zfs_range_seg_t *rs, zfs_range_tree_t *rt, uint64_t fill)
278 {
279 ASSERT(IS_P2ALIGNED(fill, 1ULL << rt->rt_shift));
280 zfs_zfs_rs_set_fill_raw(rs, rt, fill >> rt->rt_shift);
281 }
282
283 typedef void zfs_range_tree_func_t(void *arg, uint64_t start, uint64_t size);
284
285 zfs_range_tree_t *zfs_range_tree_create_gap(const zfs_range_tree_ops_t *ops,
286 zfs_range_seg_type_t type, void *arg, uint64_t start, uint64_t shift,
287 uint64_t gap);
288 zfs_range_tree_t *zfs_range_tree_create(const zfs_range_tree_ops_t *ops,
289 zfs_range_seg_type_t type, void *arg, uint64_t start, uint64_t shift);
290 zfs_range_tree_t *zfs_range_tree_create_flags(const zfs_range_tree_ops_t *ops,
291 zfs_range_seg_type_t type, void *arg, uint64_t start, uint64_t shift,
292 uint64_t flags, const char *name);
293 void zfs_range_tree_destroy(zfs_range_tree_t *rt);
294 boolean_t zfs_range_tree_contains(zfs_range_tree_t *rt, uint64_t start,
295 uint64_t size);
296 zfs_range_seg_t *zfs_range_tree_find(zfs_range_tree_t *rt, uint64_t start,
297 uint64_t size);
298 boolean_t zfs_range_tree_find_in(zfs_range_tree_t *rt, uint64_t start,
299 uint64_t size, uint64_t *ostart, uint64_t *osize);
300 void zfs_range_tree_verify_not_present(zfs_range_tree_t *rt,
301 uint64_t start, uint64_t size);
302 void zfs_range_tree_resize_segment(zfs_range_tree_t *rt, zfs_range_seg_t *rs,
303 uint64_t newstart, uint64_t newsize);
304 uint64_t zfs_range_tree_space(zfs_range_tree_t *rt);
305 uint64_t zfs_range_tree_numsegs(zfs_range_tree_t *rt);
306 boolean_t zfs_range_tree_is_empty(zfs_range_tree_t *rt);
307 void zfs_range_tree_swap(zfs_range_tree_t **rtsrc, zfs_range_tree_t **rtdst);
308 void zfs_range_tree_stat_verify(zfs_range_tree_t *rt);
309 uint64_t zfs_range_tree_min(zfs_range_tree_t *rt);
310 uint64_t zfs_range_tree_max(zfs_range_tree_t *rt);
311 uint64_t zfs_range_tree_span(zfs_range_tree_t *rt);
312
313 void zfs_range_tree_add(void *arg, uint64_t start, uint64_t size);
314 void zfs_range_tree_remove(void *arg, uint64_t start, uint64_t size);
315 void zfs_range_tree_remove_fill(zfs_range_tree_t *rt, uint64_t start,
316 uint64_t size);
317 void zfs_range_tree_adjust_fill(zfs_range_tree_t *rt, zfs_range_seg_t *rs,
318 int64_t delta);
319 void zfs_range_tree_clear(zfs_range_tree_t *rt, uint64_t start, uint64_t size);
320
321 void zfs_range_tree_vacate(zfs_range_tree_t *rt, zfs_range_tree_func_t *func,
322 void *arg);
323 void zfs_range_tree_walk(zfs_range_tree_t *rt, zfs_range_tree_func_t *func,
324 void *arg);
325 zfs_range_seg_t *zfs_range_tree_first(zfs_range_tree_t *rt);
326
327 void zfs_range_tree_remove_xor_add_segment(uint64_t start, uint64_t end,
328 zfs_range_tree_t *removefrom, zfs_range_tree_t *addto);
329 void zfs_range_tree_remove_xor_add(zfs_range_tree_t *rt,
330 zfs_range_tree_t *removefrom, zfs_range_tree_t *addto);
331
332 #ifdef __cplusplus
333 }
334 #endif
335
336 #endif /* _SYS_RANGE_TREE_H */
337