1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2019 The FreeBSD Foundation
5 *
6 * This software was developed by Konstantin Belousov <[email protected]>
7 * under sponsorship from the FreeBSD Foundation.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31 #include <sys/cdefs.h>
32 #include <sys/param.h>
33 #include <sys/kernel.h>
34 #include <sys/lock.h>
35 #include <sys/pctrie.h>
36 #include <sys/rangeset.h>
37 #include <vm/uma.h>
38
39 #ifdef DIAGNOSTIC
40 static void rangeset_check(struct rangeset *rs);
41 #else
42 #define rangeset_check(rs)
43 #endif
44
45 static uma_zone_t rs_node_zone;
46
47 static void
rs_rangeset_init(void * arg __unused)48 rs_rangeset_init(void *arg __unused)
49 {
50
51 rs_node_zone = uma_zcreate("rangeset pctrie nodes",
52 pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL,
53 UMA_ALIGN_PTR, 0);
54 }
55 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
56
57 static void *
rs_node_alloc(struct pctrie * ptree)58 rs_node_alloc(struct pctrie *ptree)
59 {
60 struct rangeset *rs;
61
62 rs = __containerof(ptree, struct rangeset, rs_trie);
63 return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags));
64 }
65
66 static void
rs_node_free(struct pctrie * ptree __unused,void * node)67 rs_node_free(struct pctrie *ptree __unused, void *node)
68 {
69
70 uma_zfree(rs_node_zone, node);
71 }
72
73 PCTRIE_DEFINE(RANGESET, rs_el, re_start, rs_node_alloc, rs_node_free);
74
75 void
rangeset_init(struct rangeset * rs,rs_dup_data_t dup_data,rs_free_data_t free_data,void * data_ctx,u_int alloc_flags)76 rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data,
77 rs_free_data_t free_data, void *data_ctx, u_int alloc_flags)
78 {
79
80 pctrie_init(&rs->rs_trie);
81 rs->rs_dup_data = dup_data;
82 rs->rs_free_data = free_data;
83 rs->rs_data_ctx = data_ctx;
84 rs->rs_alloc_flags = alloc_flags;
85 }
86
87 void
rangeset_fini(struct rangeset * rs)88 rangeset_fini(struct rangeset *rs)
89 {
90
91 rangeset_check(rs);
92 rangeset_remove_all(rs);
93 }
94
95 bool
rangeset_check_empty(struct rangeset * rs,uint64_t start,uint64_t end)96 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
97 {
98 struct rs_el *r;
99
100 rangeset_check(rs);
101 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end);
102 return (r == NULL || r->re_end <= start);
103 }
104
105 int
rangeset_insert(struct rangeset * rs,uint64_t start,uint64_t end,void * data)106 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
107 void *data)
108 {
109 struct rs_el *r;
110 int error;
111
112 rangeset_check(rs);
113 error = rangeset_remove(rs, start, end);
114 if (error != 0)
115 return (error);
116 r = data;
117 r->re_start = start;
118 r->re_end = end;
119 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r);
120 rangeset_check(rs);
121 return (error);
122 }
123
124 int
rangeset_remove_pred(struct rangeset * rs,uint64_t start,uint64_t end,rs_pred_t pred)125 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
126 rs_pred_t pred)
127 {
128 struct rs_el *r, *rn;
129 int error;
130
131 rangeset_check(rs);
132 error = 0;
133 for (; end > 0 && start < end;) {
134 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end - 1);
135 if (r == NULL)
136 break;
137
138 /*
139 * ------============================--|-------|----
140 * rs re s e
141 */
142 if (r->re_end <= start)
143 break;
144
145 if (r->re_end <= end) {
146 if (r->re_start < start) {
147 /*
148 * ------========|==============-------|----
149 * rs s re e
150 */
151 if (pred(rs->rs_data_ctx, r))
152 r->re_end = start;
153 break;
154 }
155
156 /*
157 * ------|--------===================----------|----
158 * s rs re e
159 */
160 end = r->re_start;
161 if (pred(rs->rs_data_ctx, r)) {
162 RANGESET_PCTRIE_REMOVE(&rs->rs_trie,
163 r->re_start);
164 rs->rs_free_data(rs->rs_data_ctx, r);
165 }
166 continue;
167 }
168
169 /*
170 * ------|--------====================|==========----
171 * s rs e re
172 */
173 if (r->re_start >= start) {
174 if (pred(rs->rs_data_ctx, r)) {
175 RANGESET_PCTRIE_REMOVE(&rs->rs_trie,
176 r->re_start);
177 r->re_start = end;
178 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r);
179 /*
180 * The insert above must succeed
181 * because rs_node zone is marked
182 * nofree and we freed one element
183 * just before.
184 */
185 MPASS(error == 0);
186 } else {
187 end = r->re_start;
188 }
189 continue;
190 }
191
192 /*
193 * ------=========|===================|==========----
194 * rs s e re
195 */
196 if (pred(rs->rs_data_ctx, r)) {
197 /*
198 * Split. Can only happen once, and then if
199 * any allocation fails, the rangeset is kept
200 * intact.
201 */
202 rn = rs->rs_dup_data(rs->rs_data_ctx, r);
203 if (rn == NULL) {
204 error = ENOMEM;
205 break;
206 }
207 rn->re_start = end;
208 rn->re_end = r->re_end;
209 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, rn);
210 if (error != 0) {
211 rs->rs_free_data(rs->rs_data_ctx, rn);
212 break;
213 }
214 r->re_end = start;
215 }
216 break;
217 }
218 rangeset_check(rs);
219 return (error);
220 }
221
222 static bool
rangeset_true_pred(void * ctx __unused,void * r __unused)223 rangeset_true_pred(void *ctx __unused, void *r __unused)
224 {
225
226 return (true);
227 }
228
229 int
rangeset_remove(struct rangeset * rs,uint64_t start,uint64_t end)230 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
231 {
232
233 return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
234 }
235
236 void
rangeset_remove_all(struct rangeset * rs)237 rangeset_remove_all(struct rangeset *rs)
238 {
239 struct rs_el *r;
240
241 for (;;) {
242 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, 0);
243 if (r == NULL)
244 break;
245 RANGESET_PCTRIE_REMOVE(&rs->rs_trie, r->re_start);
246 rs->rs_free_data(rs->rs_data_ctx, r);
247 }
248 }
249
250 void *
rangeset_lookup(struct rangeset * rs,uint64_t place)251 rangeset_lookup(struct rangeset *rs, uint64_t place)
252 {
253 struct rs_el *r;
254
255 rangeset_check(rs);
256 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place);
257 if (r == NULL)
258 return (NULL);
259 if (r->re_end <= place)
260 return (NULL);
261 return (r);
262 }
263
264 int
rangeset_copy(struct rangeset * dst_rs,struct rangeset * src_rs)265 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
266 {
267 struct rs_el *src_r, *dst_r;
268 uint64_t cursor;
269 int error;
270
271 MPASS(pctrie_is_empty(&dst_rs->rs_trie));
272 rangeset_check(src_rs);
273 MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
274
275 error = 0;
276 for (cursor = 0;; cursor = src_r->re_start + 1) {
277 src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor);
278 if (src_r == NULL)
279 break;
280 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
281 if (dst_r == NULL) {
282 error = ENOMEM;
283 break;
284 }
285 error = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r);
286 if (error != 0)
287 break;
288 }
289 if (error != 0)
290 rangeset_remove_all(dst_rs);
291 return (error);
292 }
293
294 #ifdef DIAGNOSTIC
295 static void
rangeset_check(struct rangeset * rs)296 rangeset_check(struct rangeset *rs)
297 {
298 struct rs_el *r, *rp;
299 uint64_t cursor;
300
301 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
302 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
303 if (r == NULL)
304 break;
305 KASSERT(r->re_start < r->re_end,
306 ("invalid interval rs %p elem %p (%#jx, %#jx)",
307 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end));
308 if (rp != NULL) {
309 KASSERT(rp->re_end <= r->re_start,
310 ("non-ascending neighbors rs %p "
311 "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
312 rs, rp, (uintmax_t)rp->re_start,
313 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start,
314 (uintmax_t)r->re_end));
315 }
316 }
317 }
318 #endif
319
320 #include "opt_ddb.h"
321 #ifdef DDB
322 #include <sys/kernel.h>
323 #include <ddb/ddb.h>
324
DB_SHOW_COMMAND(rangeset,rangeset_show_fn)325 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
326 {
327 struct rangeset *rs;
328 struct rs_el *r;
329 uint64_t cursor;
330
331 if (!have_addr) {
332 db_printf("show rangeset addr\n");
333 return;
334 }
335
336 rs = (struct rangeset *)addr;
337 db_printf("rangeset %p\n", rs);
338 for (cursor = 0;; cursor = r->re_start + 1) {
339 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
340 if (r == NULL)
341 break;
342 db_printf(" el %p start %#jx end %#jx\n",
343 r, r->re_start, r->re_end);
344 }
345 }
346 #endif
347