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