2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2019 The FreeBSD Foundation
6 * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
7 * under sponsorship from the FreeBSD Foundation.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
31 #include <sys/cdefs.h>
32 __FBSDID("$FreeBSD$");
34 #include <sys/param.h>
35 #include <sys/kernel.h>
37 #include <sys/pctrie.h>
38 #include <sys/rangeset.h>
42 static void rangeset_check(struct rangeset *rs);
44 #define rangeset_check(rs)
47 static uma_zone_t rs_node_zone;
50 rs_rangeset_init(void *arg __unused)
53 rs_node_zone = uma_zcreate("rangeset pctrie nodes",
54 pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL,
57 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
60 rs_node_alloc(struct pctrie *ptree)
64 rs = __containerof(ptree, struct rangeset, rs_trie);
65 return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags));
69 rs_node_free(struct pctrie *ptree __unused, void *node)
72 uma_zfree(rs_node_zone, node);
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)
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;
88 rangeset_fini(struct rangeset *rs)
92 rangeset_remove_all(rs);
96 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
102 r1 = pctrie_lookup_le(&rs->rs_trie, end);
104 r = __containerof(r1, struct rs_el, re_start);
105 if (r->re_end > start)
112 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end,
119 error = rangeset_remove(rs, start, end);
125 error = pctrie_insert(&rs->rs_trie, &r->re_start, rs_node_alloc);
131 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end,
134 struct rs_el *r, *rn;
140 for (; end > 0 && start < end;) {
141 r1 = pctrie_lookup_le(&rs->rs_trie, end - 1);
144 r = __containerof(r1, struct rs_el, re_start);
147 * ------============================--|-------|----
150 if (r->re_end <= start)
153 if (r->re_end <= end) {
154 if (r->re_start < start) {
156 * ------========|==============-------|----
159 if (pred(rs->rs_data_ctx, r))
165 * ------|--------===================----------|----
169 if (pred(rs->rs_data_ctx, r)) {
170 pctrie_remove(&rs->rs_trie, r->re_start,
172 rs->rs_free_data(rs->rs_data_ctx, r);
178 * ------|--------====================|==========----
181 if (r->re_start >= start) {
182 if (pred(rs->rs_data_ctx, r)) {
183 pctrie_remove(&rs->rs_trie, r->re_start,
186 error = pctrie_insert(&rs->rs_trie,
187 &r->re_start, rs_node_alloc);
189 * The insert above must succeed
190 * because rs_node zone is marked
191 * nofree and we freed one element
202 * ------=========|===================|==========----
205 if (pred(rs->rs_data_ctx, r)) {
207 * Split. Can only happen once, and then if
208 * any allocation fails, the rangeset is kept
211 rn = rs->rs_dup_data(rs->rs_data_ctx, r);
217 rn->re_end = r->re_end;
218 error = pctrie_insert(&rs->rs_trie, &rn->re_start,
221 rs->rs_free_data(rs->rs_data_ctx, rn);
233 rangeset_true_pred(void *ctx __unused, void *r __unused)
240 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
243 return (rangeset_remove_pred(rs, start, end, rangeset_true_pred));
247 rangeset_remove_all(struct rangeset *rs)
253 r1 = pctrie_lookup_ge(&rs->rs_trie, 0);
256 r = __containerof(r1, struct rs_el, re_start);
257 pctrie_remove(&rs->rs_trie, r->re_start, rs_node_free);
258 rs->rs_free_data(rs->rs_data_ctx, r);
263 rangeset_lookup(struct rangeset *rs, uint64_t place)
269 r1 = pctrie_lookup_le(&rs->rs_trie, place);
272 r = __containerof(r1, struct rs_el, re_start);
273 if (r->re_end <= place)
279 rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
281 struct rs_el *src_r, *dst_r;
282 uint64_t cursor, *r1;
285 MPASS(pctrie_is_empty(&dst_rs->rs_trie));
286 rangeset_check(src_rs);
287 MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
290 for (cursor = 0;; cursor = src_r->re_start + 1) {
291 r1 = pctrie_lookup_ge(&src_rs->rs_trie, cursor);
294 src_r = __containerof(r1, struct rs_el, re_start);
295 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
300 error = pctrie_insert(&dst_rs->rs_trie, &dst_r->re_start,
306 rangeset_remove_all(dst_rs);
312 rangeset_check(struct rangeset *rs)
314 struct rs_el *r, *rp;
315 uint64_t cursor, *r1;
317 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
318 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
321 r = __containerof(r1, struct rs_el, re_start);
322 KASSERT(r->re_start < r->re_end,
323 ("invalid interval rs %p elem %p (%#jx, %#jx)",
324 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end));
326 KASSERT(rp->re_end <= r->re_start,
327 ("non-ascending neighbors rs %p "
328 "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
329 rs, rp, (uintmax_t)rp->re_start,
330 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start,
331 (uintmax_t)r->re_end));
339 #include <sys/kernel.h>
342 DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
346 uint64_t cursor, *r1;
349 db_printf("show rangeset addr\n");
353 rs = (struct rangeset *)addr;
354 db_printf("rangeset %p\n", rs);
355 for (cursor = 0;; cursor = r->re_start + 1) {
356 r1 = pctrie_lookup_ge(&rs->rs_trie, cursor);
359 r = __containerof(r1, struct rs_el, re_start);
360 db_printf(" el %p start %#jx end %#jx\n",
361 r, r->re_start, r->re_end);