Author: kib Date: Wed Feb 20 09:38:19 2019 New Revision: 344351 URL: https://svnweb.freebsd.org/changeset/base/344351
Log: Implement rangesets. The data structure implements non-intersecting intervals over the [0, UINT64_MAX] range, and supports fast insert, predicated clearing of subrange, and lookup of an interval containing the specified address. Internally it is a pctrie over the interval start addresses. Implementation provides additional guarantees over the structure state in case of memory allocation failures. Reviewed by: markj Tested by: pho Sponsored by: The FreeBSD Foundation MFC after: 2 weeks Differential revision: https://reviews.freebsd.org/D18893 Added: head/sys/kern/subr_rangeset.c (contents, props changed) head/sys/sys/_rangeset.h (contents, props changed) head/sys/sys/rangeset.h (contents, props changed) Modified: head/sys/conf/files Modified: head/sys/conf/files ============================================================================== --- head/sys/conf/files Wed Feb 20 09:33:55 2019 (r344350) +++ head/sys/conf/files Wed Feb 20 09:38:19 2019 (r344351) @@ -3861,6 +3861,7 @@ kern/subr_pidctrl.c standard kern/subr_power.c standard kern/subr_prf.c standard kern/subr_prof.c standard +kern/subr_rangeset.c standard kern/subr_rman.c standard kern/subr_rtc.c standard kern/subr_sbuf.c standard Added: head/sys/kern/subr_rangeset.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/kern/subr_rangeset.c Wed Feb 20 09:38:19 2019 (r344351) @@ -0,0 +1,365 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD + * + * Copyright (c) 2019 The FreeBSD Foundation + * All rights reserved. + * + * This software was developed by Konstantin Belousov <k...@freebsd.org> + * under sponsorship from the FreeBSD Foundation. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <sys/param.h> +#include <sys/kernel.h> +#include <sys/lock.h> +#include <sys/pctrie.h> +#include <sys/rangeset.h> +#include <vm/uma.h> + +#ifdef DIAGNOSTIC +static void rangeset_check(struct rangeset *rs); +#else +#define rangeset_check(rs) +#endif + +static uma_zone_t rs_node_zone; + +static void +rs_rangeset_init(void *arg __unused) +{ + + rs_node_zone = uma_zcreate("rangeset pctrie nodes", + pctrie_node_size(), NULL, NULL, pctrie_zone_init, NULL, + UMA_ALIGN_PTR, 0); +} +SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL); + +static void * +rs_node_alloc(struct pctrie *ptree) +{ + struct rangeset *rs; + + rs = __containerof(ptree, struct rangeset, rs_trie); + return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags)); +} + +static void +rs_node_free(struct pctrie *ptree __unused, void *node) +{ + + uma_zfree(rs_node_zone, node); +} + +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) +{ + + pctrie_init(&rs->rs_trie); + rs->rs_dup_data = dup_data; + rs->rs_free_data = free_data; + rs->rs_data_ctx = data_ctx; + rs->rs_alloc_flags = alloc_flags; +} + +void +rangeset_fini(struct rangeset *rs) +{ + + rangeset_check(rs); + rangeset_remove_all(rs); +} + +bool +rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end) +{ + struct rs_el *r; + uint64_t *r1; + + rangeset_check(rs); + r1 = pctrie_lookup_le(&rs->rs_trie, end); + if (r1 != NULL) { + r = __containerof(r1, struct rs_el, re_start); + if (r->re_end > start) + return (false); + } + return (true); +} + +int +rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end, + void *data) +{ + struct rs_el *r; + int error; + + rangeset_check(rs); + error = rangeset_remove(rs, start, end); + if (error != 0) + return (error); + r = data; + r->re_start = start; + r->re_end = end; + error = pctrie_insert(&rs->rs_trie, &r->re_start, rs_node_alloc); + rangeset_check(rs); + return (error); +} + +int +rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end, + rs_pred_t pred) +{ + struct rs_el *r, *rn; + uint64_t *r1; + int error; + + rangeset_check(rs); + error = 0; + for (; end > 0 && start < end;) { + r1 = pctrie_lookup_le(&rs->rs_trie, end - 1); + if (r1 == NULL) + break; + r = __containerof(r1, struct rs_el, re_start); + + /* + * ------============================--|-------|---- + * rs re s e + */ + if (r->re_end <= start) + break; + + if (r->re_end <= end) { + if (r->re_start < start) { + /* + * ------========|==============-------|---- + * rs s re e + */ + if (pred(rs->rs_data_ctx, r)) + r->re_end = start; + break; + } + + /* + * ------|--------===================----------|---- + * s rs re e + */ + end = r->re_start; + if (pred(rs->rs_data_ctx, r)) { + pctrie_remove(&rs->rs_trie, r->re_start, + rs_node_free); + rs->rs_free_data(rs->rs_data_ctx, r); + } + continue; + } + + /* + * ------|--------====================|==========---- + * s rs e re + */ + if (r->re_start >= start) { + if (pred(rs->rs_data_ctx, r)) { + pctrie_remove(&rs->rs_trie, r->re_start, + rs_node_free); + r->re_start = end; + error = pctrie_insert(&rs->rs_trie, + &r->re_start, rs_node_alloc); + /* + * The insert above must succeed + * because rs_node zone is marked + * nofree and we freed one element + * just before. + */ + MPASS(error == 0); + } else { + end = r->re_start; + } + continue; + } + + /* + * ------=========|===================|==========---- + * rs s e re + */ + if (pred(rs->rs_data_ctx, r)) { + /* + * Split. Can only happen once, and then if + * any allocation fails, the rangeset is kept + * intact. + */ + rn = rs->rs_dup_data(rs->rs_data_ctx, r); + if (rn == NULL) { + error = ENOMEM; + break; + } + rn->re_start = end; + rn->re_end = r->re_end; + error = pctrie_insert(&rs->rs_trie, &rn->re_start, + rs_node_alloc); + if (error != 0) { + rs->rs_free_data(rs->rs_data_ctx, rn); + break; + } + r->re_end = start; + } + break; + } + rangeset_check(rs); + return (error); +} + +static bool +rangeset_true_pred(void *ctx __unused, void *r __unused) +{ + + return (true); +} + +int +rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end) +{ + + return (rangeset_remove_pred(rs, start, end, rangeset_true_pred)); +} + +void +rangeset_remove_all(struct rangeset *rs) +{ + struct rs_el *r; + uint64_t *r1; + + for (;;) { + r1 = pctrie_lookup_ge(&rs->rs_trie, 0); + if (r1 == NULL) + break; + r = __containerof(r1, struct rs_el, re_start); + pctrie_remove(&rs->rs_trie, r->re_start, rs_node_free); + rs->rs_free_data(rs->rs_data_ctx, r); + } +} + +void * +rangeset_lookup(struct rangeset *rs, uint64_t place) +{ + struct rs_el *r; + uint64_t *r1; + + rangeset_check(rs); + r1 = pctrie_lookup_le(&rs->rs_trie, place); + if (r1 == NULL) + return (NULL); + r = __containerof(r1, struct rs_el, re_start); + if (r->re_end <= place) + return (NULL); + return (r); +} + +int +rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs) +{ + struct rs_el *src_r, *dst_r; + uint64_t cursor, *r1; + int error; + + MPASS(pctrie_is_empty(&dst_rs->rs_trie)); + rangeset_check(src_rs); + MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data); + + error = 0; + for (cursor = 0;; cursor = src_r->re_start + 1) { + r1 = pctrie_lookup_ge(&src_rs->rs_trie, cursor); + if (r1 == NULL) + break; + src_r = __containerof(r1, struct rs_el, re_start); + dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r); + if (dst_r == NULL) { + error = ENOMEM; + break; + } + error = pctrie_insert(&dst_rs->rs_trie, &dst_r->re_start, + rs_node_alloc); + if (error != 0) + break; + } + if (error != 0) + rangeset_remove_all(dst_rs); + return (error); +} + +#ifdef DIAGNOSTIC +static void +rangeset_check(struct rangeset *rs) +{ + struct rs_el *r, *rp; + uint64_t cursor, *r1; + + for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) { + r1 = pctrie_lookup_ge(&rs->rs_trie, cursor); + if (r1 == NULL) + break; + r = __containerof(r1, struct rs_el, re_start); + KASSERT(r->re_start < r->re_end, + ("invalid interval rs %p elem %p (%#jx, %#jx)", + rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end)); + if (rp != NULL) { + KASSERT(rp->re_end <= r->re_start, + ("non-ascending neighbors rs %p " + "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)", + rs, rp, (uintmax_t)rp->re_start, + (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start, + (uintmax_t)r->re_end)); + } + } +} +#endif + +#include "opt_ddb.h" +#ifdef DDB +#include <sys/kernel.h> +#include <ddb/ddb.h> + +DB_SHOW_COMMAND(rangeset, rangeset_show_fn) +{ + struct rangeset *rs; + struct rs_el *r; + uint64_t cursor, *r1; + + if (!have_addr) { + db_printf("show rangeset addr\n"); + return; + } + + rs = (struct rangeset *)addr; + db_printf("rangeset %p\n", rs); + for (cursor = 0;; cursor = r->re_start + 1) { + r1 = pctrie_lookup_ge(&rs->rs_trie, cursor); + if (r1 == NULL) + break; + r = __containerof(r1, struct rs_el, re_start); + db_printf(" el %p start %#jx end %#jx\n", + r, r->re_start, r->re_end); + } +} +#endif Added: head/sys/sys/_rangeset.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/sys/_rangeset.h Wed Feb 20 09:38:19 2019 (r344351) @@ -0,0 +1,51 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD + * + * Copyright (c) 2019 The FreeBSD Foundation + * All rights reserved. + * + * This software was developed by Konstantin Belousov <k...@freebsd.org> + * under sponsorship from the FreeBSD Foundation. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#ifndef _SYS__RANGESET_H +#define _SYS__RANGESET_H + +#include <sys/_pctrie.h> + +typedef void *(*rs_dup_data_t)(void *ctx, void *data); +typedef void (*rs_free_data_t)(void *ctx, void *data); + +struct rangeset { + struct pctrie rs_trie; + rs_dup_data_t rs_dup_data; + rs_free_data_t rs_free_data; + void *rs_data_ctx; + u_int rs_alloc_flags; +}; + +#endif + Added: head/sys/sys/rangeset.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/sys/rangeset.h Wed Feb 20 09:38:19 2019 (r344351) @@ -0,0 +1,88 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD + * + * Copyright (c) 2019 The FreeBSD Foundation + * All rights reserved. + * + * This software was developed by Konstantin Belousov <k...@freebsd.org> + * under sponsorship from the FreeBSD Foundation. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#ifndef _SYS_RANGESET_H +#define _SYS_RANGESET_H + +#ifdef _KERNEL + +#include <sys/_rangeset.h> + +typedef bool (*rs_pred_t)(void *ctx, void *r); + +/* + * This structure must be embedded at the start of the rangeset element. + */ +struct rs_el { + uint64_t re_start; /* pctrie key */ + uint64_t re_end; +}; + +void rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data, + rs_free_data_t free_data, void *rs_data_ctx, u_int alloc_flags); +void rangeset_fini(struct rangeset *rs); + +bool rangeset_check_empty(struct rangeset *rs, uint64_t start, + uint64_t end); + +/* + * r point to the app data with struct rs_el at the beginning. + */ +int rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end, + void *r); + +/* + * Guarantees that on error the rangeset is not modified. Remove + * might need to split element if its start/end completely cover the + * removed range, in which case ENOMEM might be returned. + */ +void rangeset_remove_all(struct rangeset *rs); +int rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end); +int rangeset_remove_pred(struct rangeset *rs, uint64_t start, + uint64_t end, rs_pred_t pred); + +/* + * Really returns the pointer to the data with struct rs_el embedded + * at the beginning. + */ +void *rangeset_lookup(struct rangeset *rs, uint64_t place); + +/* + * Copies src_rs entries into dst_rs. dst_rs must be empty. + * Leaves dst_rs empty on failure. + */ +int rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs); + +#endif + +#endif _______________________________________________ svn-src-head@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
