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 <kib@FreeBSD.org>
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/param.h>
32 #include <sys/kernel.h>
33 #include <sys/lock.h>
34 #include <sys/pctrie.h>
35 #include <sys/rangeset.h>
36 #include <vm/uma.h>
37
38 #ifdef DIAGNOSTIC
39 static void rangeset_check(struct rangeset *rs);
40 #else
41 #define rangeset_check(rs)
42 #endif
43
44 static uma_zone_t rs_node_zone;
45
46 static void
rs_rangeset_init(void * arg __unused)47 rs_rangeset_init(void *arg __unused)
48 {
49
50 rs_node_zone = uma_zcreate("rangeset pctrie nodes",
51 pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL,
52 UMA_ALIGN_PTR, 0);
53 }
54 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
55
56 static void *
rs_node_alloc(struct pctrie * ptree)57 rs_node_alloc(struct pctrie *ptree)
58 {
59 struct rangeset *rs;
60
61 rs = __containerof(ptree, struct rangeset, rs_trie);
62 return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags));
63 }
64
65 static void
rs_node_free(struct pctrie * ptree __unused,void * node)66 rs_node_free(struct pctrie *ptree __unused, void *node)
67 {
68
69 uma_zfree(rs_node_zone, node);
70 }
71
72 PCTRIE_DEFINE(RANGESET, rs_el, re_start, rs_node_alloc, rs_node_free);
73
74 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)75 rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data,
76 rs_free_data_t free_data, void *data_ctx, u_int alloc_flags)
77 {
78
79 pctrie_init(&rs->rs_trie);
80 rs->rs_dup_data = dup_data;
81 rs->rs_free_data = free_data;
82 rs->rs_data_ctx = data_ctx;
83 rs->rs_alloc_flags = alloc_flags;
84 }
85
86 void
rangeset_fini(struct rangeset * rs)87 rangeset_fini(struct rangeset *rs)
88 {
89
90 rangeset_check(rs);
91 rangeset_remove_all(rs);
92 }
93
94 bool
rangeset_check_empty(struct rangeset * rs,uint64_t start,uint64_t end)95 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
96 {
97 struct rs_el *r;
98
99 rangeset_check(rs);
100 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end);
101 return (r == NULL || r->re_end <= start);
102 }
103
104 int
rangeset_insert(struct rangeset * rs,uint64_t start,uint64_t end,void * data)105 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
106 void *data)
107 {
108 struct rs_el *r;
109 int error;
110
111 rangeset_check(rs);
112 error = rangeset_remove(rs, start, end);
113 if (error != 0)
114 return (error);
115 r = data;
116 r->re_start = start;
117 r->re_end = end;
118 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r);
119 rangeset_check(rs);
120 return (error);
121 }
122
123 int
rangeset_remove_pred(struct rangeset * rs,uint64_t start,uint64_t end,rs_pred_t pred)124 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
125 rs_pred_t pred)
126 {
127 struct rs_el *r, *rn;
128 int error;
129
130 rangeset_check(rs);
131 error = 0;
132 for (; end > 0 && start < end;) {
133 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end - 1);
134 if (r == NULL)
135 break;
136
137 /*
138 * ------============================--|-------|----
139 * rs re s e
140 */
141 if (r->re_end <= start)
142 break;
143
144 if (r->re_end <= end) {
145 if (r->re_start < start) {
146 /*
147 * ------========|==============-------|----
148 * rs s re e
149 */
150 if (pred(rs->rs_data_ctx, r))
151 r->re_end = start;
152 break;
153 }
154
155 /*
156 * ------|--------===================----------|----
157 * s rs re e
158 */
159 end = r->re_start;
160 if (pred(rs->rs_data_ctx, r)) {
161 RANGESET_PCTRIE_REMOVE(&rs->rs_trie,
162 r->re_start);
163 rs->rs_free_data(rs->rs_data_ctx, r);
164 }
165 continue;
166 }
167
168 /*
169 * ------|--------====================|==========----
170 * s rs e re
171 */
172 if (r->re_start >= start) {
173 if (pred(rs->rs_data_ctx, r)) {
174 RANGESET_PCTRIE_REMOVE(&rs->rs_trie,
175 r->re_start);
176 r->re_start = end;
177 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r);
178 /*
179 * The insert above must succeed
180 * because rs_node zone is marked
181 * nofree and we freed one element
182 * just before.
183 */
184 MPASS(error == 0);
185 } else {
186 end = r->re_start;
187 }
188 continue;
189 }
190
191 /*
192 * ------=========|===================|==========----
193 * rs s e re
194 */
195 if (pred(rs->rs_data_ctx, r)) {
196 /*
197 * Split. Can only happen once, and then if
198 * any allocation fails, the rangeset is kept
199 * intact.
200 */
201 rn = rs->rs_dup_data(rs->rs_data_ctx, r);
202 if (rn == NULL) {
203 error = ENOMEM;
204 break;
205 }
206 rn->re_start = end;
207 rn->re_end = r->re_end;
208 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, rn);
209 if (error != 0) {
210 rs->rs_free_data(rs->rs_data_ctx, rn);
211 break;
212 }
213 r->re_end = start;
214 }
215 break;
216 }
217 rangeset_check(rs);
218 return (error);
219 }
220
221 static bool
rangeset_true_pred(void * ctx __unused,void * r __unused)222 rangeset_true_pred(void *ctx __unused, void *r __unused)
223 {
224
225 return (true);
226 }
227
228 int
rangeset_remove(struct rangeset * rs,uint64_t start,uint64_t end)229 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
230 {
231
232 return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
233 }
234
235 void
rangeset_remove_all(struct rangeset * rs)236 rangeset_remove_all(struct rangeset *rs)
237 {
238 struct rs_el *r;
239
240 for (;;) {
241 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, 0);
242 if (r == NULL)
243 break;
244 RANGESET_PCTRIE_REMOVE(&rs->rs_trie, r->re_start);
245 rs->rs_free_data(rs->rs_data_ctx, r);
246 }
247 }
248
249 void *
rangeset_lookup(struct rangeset * rs,uint64_t place)250 rangeset_lookup(struct rangeset *rs, uint64_t place)
251 {
252 struct rs_el *r;
253
254 rangeset_check(rs);
255 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place);
256 if (r == NULL)
257 return (NULL);
258 if (r->re_end <= place)
259 return (NULL);
260 return (r);
261 }
262
263 void *
rangeset_next(struct rangeset * rs,uint64_t place)264 rangeset_next(struct rangeset *rs, uint64_t place)
265 {
266
267 rangeset_check(rs);
268 return (RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, place));
269 }
270
271 int
rangeset_copy(struct rangeset * dst_rs,struct rangeset * src_rs)272 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
273 {
274 struct rs_el *src_r, *dst_r;
275 uint64_t cursor;
276 int error;
277
278 MPASS(pctrie_is_empty(&dst_rs->rs_trie));
279 rangeset_check(src_rs);
280 MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
281
282 error = 0;
283 for (cursor = 0;; cursor = src_r->re_start + 1) {
284 src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor);
285 if (src_r == NULL)
286 break;
287 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
288 if (dst_r == NULL) {
289 error = ENOMEM;
290 break;
291 }
292 error = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r);
293 if (error != 0)
294 break;
295 }
296 if (error != 0)
297 rangeset_remove_all(dst_rs);
298 return (error);
299 }
300
301 #ifdef DIAGNOSTIC
302 static void
rangeset_check(struct rangeset * rs)303 rangeset_check(struct rangeset *rs)
304 {
305 struct rs_el *r, *rp;
306 uint64_t cursor;
307
308 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
309 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
310 if (r == NULL)
311 break;
312 KASSERT(r->re_start < r->re_end,
313 ("invalid interval rs %p elem %p (%#jx, %#jx)",
314 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end));
315 if (rp != NULL) {
316 KASSERT(rp->re_end <= r->re_start,
317 ("non-ascending neighbors rs %p "
318 "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
319 rs, rp, (uintmax_t)rp->re_start,
320 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start,
321 (uintmax_t)r->re_end));
322 }
323 }
324 }
325 #endif
326
327 #include "opt_ddb.h"
328 #ifdef DDB
329 #include <sys/kernel.h>
330 #include <ddb/ddb.h>
331
DB_SHOW_COMMAND(rangeset,rangeset_show_fn)332 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
333 {
334 struct rangeset *rs;
335 struct rs_el *r;
336 uint64_t cursor;
337
338 if (!have_addr) {
339 db_printf("show rangeset addr\n");
340 return;
341 }
342
343 rs = (struct rangeset *)addr;
344 db_printf("rangeset %p\n", rs);
345 for (cursor = 0;; cursor = r->re_start + 1) {
346 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor);
347 if (r == NULL)
348 break;
349 db_printf(" el %p start %#jx end %#jx\n",
350 r, r->re_start, r->re_end);
351 }
352 }
353 #endif
354