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