xref: /freebsd/sys/contrib/openzfs/include/sys/range_tree.h (revision df58e8b1506f241670be86a560fb6e8432043aee)
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