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