diff --git a/sys/kern/subr_rangeset.c b/sys/kern/subr_rangeset.c index c8af58c6f84f..a27126ab127b 100644 --- a/sys/kern/subr_rangeset.c +++ b/sys/kern/subr_rangeset.c @@ -1,364 +1,348 @@ /*- * SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2019 The FreeBSD Foundation * * This software was developed by Konstantin Belousov * 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 __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #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); } +PCTRIE_DEFINE(RANGESET, rs_el, re_start, rs_node_alloc, rs_node_free); + 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); + r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end); + return (r == NULL || r->re_end <= start); } 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); + error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r); 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) + r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end - 1); + if (r == 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); + RANGESET_PCTRIE_REMOVE(&rs->rs_trie, + r->re_start); 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); + RANGESET_PCTRIE_REMOVE(&rs->rs_trie, + r->re_start); r->re_start = end; - error = pctrie_insert(&rs->rs_trie, - &r->re_start, rs_node_alloc); + error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r); /* * 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); + error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, rn); 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) + r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, 0); + if (r == NULL) break; - r = __containerof(r1, struct rs_el, re_start); - pctrie_remove(&rs->rs_trie, r->re_start, rs_node_free); + RANGESET_PCTRIE_REMOVE(&rs->rs_trie, r->re_start); 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) + r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place); + if (r == 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; + uint64_t cursor; 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) + src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor); + if (src_r == 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); + error = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r); 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; + uint64_t cursor; for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) { - r1 = pctrie_lookup_ge(&rs->rs_trie, cursor); - if (r1 == NULL) + r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor); + if (r == 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 #include DB_SHOW_COMMAND(rangeset, rangeset_show_fn) { struct rangeset *rs; struct rs_el *r; - uint64_t cursor, *r1; + uint64_t cursor; 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) + r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor); + if (r == 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 diff --git a/sys/sys/pctrie.h b/sys/sys/pctrie.h index 687236cdd872..62af29d3f754 100644 --- a/sys/sys/pctrie.h +++ b/sys/sys/pctrie.h @@ -1,172 +1,172 @@ /*- * SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2013 EMC Corp. * Copyright (c) 2011 Jeffrey Roberson * Copyright (c) 2008 Mayur Shardul * All rights reserved. * * 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_PCTRIE_H_ #define _SYS_PCTRIE_H_ #include #include #ifdef _KERNEL #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \ PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ \ static __inline struct type * \ name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \ { \ \ return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \ key, (smr))); \ } \ #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ \ CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \ /* \ * XXX This assert protects flag bits, it does not enforce natural \ * alignment. 32bit architectures do not naturally align 64bit fields. \ */ \ CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \ \ static __inline struct type * \ name##_PCTRIE_VAL2PTR(uint64_t *val) \ { \ \ if (val == NULL) \ return (NULL); \ return (struct type *) \ ((uintptr_t)val - __offsetof(struct type, field)); \ } \ \ static __inline uint64_t * \ name##_PCTRIE_PTR2VAL(struct type *ptr) \ { \ \ return &ptr->field; \ } \ \ static __inline int \ name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \ { \ \ return pctrie_insert(ptree, name##_PCTRIE_PTR2VAL(ptr), \ allocfn); \ } \ \ -static __inline struct type * \ +static __inline __unused struct type * \ name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \ { \ \ return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \ } \ \ static __inline __unused struct type * \ name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \ { \ \ return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \ } \ \ static __inline __unused struct type * \ name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \ { \ \ return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \ } \ \ static __inline __unused void \ name##_PCTRIE_RECLAIM(struct pctrie *ptree) \ { \ \ pctrie_reclaim_allnodes(ptree, freefn); \ } \ \ static __inline void \ name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \ { \ \ pctrie_remove(ptree, key, freefn); \ } typedef void *(*pctrie_alloc_t)(struct pctrie *ptree); typedef void (*pctrie_free_t)(struct pctrie *ptree, void *node); int pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn); uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, smr_t smr); void pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn); void pctrie_remove(struct pctrie *ptree, uint64_t key, pctrie_free_t freefn); size_t pctrie_node_size(void); int pctrie_zone_init(void *mem, int size, int flags); /* * Each search path in the trie terminates at a leaf, which is a pointer to a * value marked with a set 1-bit. A leaf may be associated with a null pointer * to indicate no value there. */ #define PCTRIE_ISLEAF 0x1 #define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF static __inline void pctrie_init(struct pctrie *ptree) { ptree->pt_root = PCTRIE_NULL; } static __inline bool pctrie_is_empty(struct pctrie *ptree) { return (ptree->pt_root == PCTRIE_NULL); } /* * These widths should allow the pointers to a node's children to fit within * a single cache line. The extra levels from a narrow width should not be * a problem thanks to path compression. */ #ifdef __LP64__ #define PCTRIE_WIDTH 4 #else #define PCTRIE_WIDTH 3 #endif #define PCTRIE_COUNT (1 << PCTRIE_WIDTH) #endif /* _KERNEL */ #endif /* !_SYS_PCTRIE_H_ */