2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2019 The FreeBSD Foundation
7 * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
8 * under sponsorship from the FreeBSD Foundation.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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
32 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD$");
35 #include <sys/param.h>
36 #include <sys/kernel.h>
38 #include <sys/pctrie.h>
39 #include <sys/rangeset.h>
43 static void rangeset_check(struct rangeset *rs);
45 #define rangeset_check(rs)
48 static uma_zone_t rs_node_zone;
51 rs_rangeset_init(void *arg __unused)
54 rs_node_zone = uma_zcreate("rangeset pctrie nodes",
55 pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL,
58 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
61 rs_node_alloc(struct pctrie *ptree)
65 rs = __containerof(ptree, struct rangeset, rs_trie);
66 return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags));
70 rs_node_free(struct pctrie *ptree __unused, void *node)
73 uma_zfree(rs_node_zone, node);
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)
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;
89 rangeset_fini(struct rangeset *rs)
93 rangeset_remove_all(rs);
97 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
103 r1 = pctrie_lookup_le(&rs->rs_trie, end);
105 r = __containerof(r1, struct rs_el, re_start);
106 if (r->re_end > start)
113 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
120 error = rangeset_remove(rs, start, end);
126 error = pctrie_insert(&rs->rs_trie, &r->re_start, rs_node_alloc);
132 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
135 struct rs_el *r, *rn;
141 for (; end > 0 && start < end;) {
142 r1 = pctrie_lookup_le(&rs->rs_trie, end - 1);
145 r = __containerof(r1, struct rs_el, re_start);
148 * ------============================--|-------|----
151 if (r->re_end <= start)
154 if (r->re_end <= end) {
155 if (r->re_start < start) {
157 * ------========|==============-------|----
160 if (pred(rs->rs_data_ctx, r))
166 * ------|--------===================----------|----
170 if (pred(rs->rs_data_ctx, r)) {
171 pctrie_remove(&rs->rs_trie, r->re_start,
173 rs->rs_free_data(rs->rs_data_ctx, r);
179 * ------|--------====================|==========----
182 if (r->re_start >= start) {
183 if (pred(rs->rs_data_ctx, r)) {
184 pctrie_remove(&rs->rs_trie, r->re_start,
187 error = pctrie_insert(&rs->rs_trie,
188 &r->re_start, rs_node_alloc);
190 * The insert above must succeed
191 * because rs_node zone is marked
192 * nofree and we freed one element
203 * ------=========|===================|==========----
206 if (pred(rs->rs_data_ctx, r)) {
208 * Split. Can only happen once, and then if
209 * any allocation fails, the rangeset is kept
212 rn = rs->rs_dup_data(rs->rs_data_ctx, r);
218 rn->re_end = r->re_end;
219 error = pctrie_insert(&rs->rs_trie, &rn->re_start,
222 rs->rs_free_data(rs->rs_data_ctx, rn);
234 rangeset_true_pred(void *ctx __unused, void *r __unused)
241 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
244 return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
248 rangeset_remove_all(struct rangeset *rs)
254 r1 = pctrie_lookup_ge(&rs->rs_trie, 0);
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);
264 rangeset_lookup(struct rangeset *rs, uint64_t place)
270 r1 = pctrie_lookup_le(&rs->rs_trie, place);
273 r = __containerof(r1, struct rs_el, re_start);
274 if (r->re_end <= place)
280 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
282 struct rs_el *src_r, *dst_r;
283 uint64_t cursor, *r1;
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);
291 for (cursor = 0;; cursor = src_r->re_start + 1) {
292 r1 = pctrie_lookup_ge(&src_rs->rs_trie, cursor);
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);
301 error = pctrie_insert(&dst_rs->rs_trie, &dst_r->re_start,
307 rangeset_remove_all(dst_rs);
313 rangeset_check(struct rangeset *rs)
315 struct rs_el *r, *rp;
316 uint64_t cursor, *r1;
318 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
319 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
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));
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));
340 #include <sys/kernel.h>
343 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
347 uint64_t cursor, *r1;
350 db_printf("show rangeset addr\n");
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);
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);