/*- * Copyright (c) 2015--2019 Taylor R. Campbell * 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. */ #ifdef _KERNEL #include #include #define assert KASSERT #else /* !_KERNEL */ #include #include #include #include #include #include #ifndef __diagused #ifdef NDEBUG #define __diagused __unused #else #define __diagused #endif #endif #endif /* _KERNEL */ #include "container_of.h" #include "critbit_alloc.h" #define MIN(x, y) ((x) < (y) ? (x) : (y)) #ifdef _KERNEL struct critbit_branch * critbit_branch_alloc_default(void) { return kmem_alloc(sizeof(*critbit_branch_alloc_default()), KM_SLEEP); } void critbit_branch_free_default(struct critbit_branch *B) { kmem_free(B, sizeof(*B)); } #else static struct critbit_branch * critbit_branch_alloc_default(void) { return malloc(sizeof(*critbit_branch_alloc_default())); } static void critbit_branch_free_default(struct critbit_branch *B) { free(B); } #endif /* _KERNEL */ struct critbit_branch * critbit_branch_alloc(struct critbit *C) { if (C->cb_ops->cbo_branch_alloc) return (*C->cb_ops->cbo_branch_alloc)(C); return critbit_branch_alloc_default(); } void critbit_branch_free(struct critbit *C, struct critbit_branch *B) { if (B == NULL) return; if (C->cb_ops->cbo_branch_free) return (*C->cb_ops->cbo_branch_free)(C, B); return critbit_branch_free_default(B); } /* Child pointer load and store ordering */ /* * load_child(C, childp) * * Atomically load a tagged child pointer from *childp and return * it. Guarantees to load a single snapshot of the value of the * pointer, and to load it only once. Makes no guarantees about * subsequent loads. Caller is responsible for issuing a * data-dependent read barrier if the tagged child pointer is of * interest -- this is not even a `consume' load, let alone an * `acquire' load. */ static inline uintptr_t load_child(const struct critbit *C __unused, const volatile uintptr_t *childp) { uintptr_t child; child = *childp; __insn_barrier(); return child; } /* * store_child(C, childp, child) * * Atomically store a tagged child pointer to *childp. Guarantees * all prior stores in program order have completed before the * store to *childp. */ static inline void store_child(struct critbit *C, volatile uintptr_t *childp, uintptr_t child) { (void)C; (*C->cb_ops->cbo_membar_producer)(); *childp = child; } /* Tagged child pointers */ static bool isbranch(uintptr_t child) { return (child & 1) == 1; } static bool __diagused isleaf(uintptr_t child) { return (child & 1) == 0; } static uintptr_t branch2child(struct critbit_branch *B) { assert((uintptr_t)B != 0); assert(((uintptr_t)B & 1) == 0); return (uintptr_t)B | 1; } static uintptr_t leaf2child(struct critbit_node *N) { assert((uintptr_t)N != 0); assert(((uintptr_t)N & 1) == 0); return (uintptr_t)N; } static struct critbit_branch * child2branch(uintptr_t child) { struct critbit_branch *B; assert((child & 1) == 1); B = (struct critbit_branch *)(child - 1); assert(B != NULL); return B; } static struct critbit_node * child2leaf(uintptr_t child) { struct critbit_node *N; assert((child & 1) == 0); N = (struct critbit_node *)child; assert(N != NULL); return N; } /* Direction and iteration paths */ static inline unsigned revdir(unsigned dir) { /* * Could use 1 - dir instead, but that usually takes one more * instruction on common CPU architectures, since subtraction * instructions usually accept a immediate subtrahend but not * an immediate minuend, while xor is commutative so it doesn't * matter. */ return 1 ^ dir; } static inline unsigned getdir(unsigned char *S, unsigned d) { const unsigned i = d / CHAR_BIT; const unsigned j = d % CHAR_BIT; assert(d <= CHAR_BIT*CRITBIT_MAX_KEYLEN); return 1 & (S[i] >> j); } static inline void setdir(unsigned char *S, unsigned d, unsigned dir) { const unsigned i = d / CHAR_BIT; const unsigned j = d % CHAR_BIT; assert(d <= CHAR_BIT*CRITBIT_MAX_KEYLEN); assert(dir == (dir & 1)); S[i] &= ~(1 << j); S[i] |= dir << j; } /* Critbit tree and node creation and destruction */ void critbit_init(struct critbit *C, const struct critbit_ops *ops) { C->cb_root = 0; C->cb_ops = ops; } void critbit_destroy(struct critbit *C) { assert(C->cb_root == 0); assert(C->cb_ops != NULL); C->cb_root = -1; C->cb_ops = NULL; } void critbit_node_init(struct critbit_node *N __diagused, const void *key __diagused, size_t keylen __diagused) { assert(((uintptr_t)N & 1) == 0); assert(key != NULL); assert(0 < keylen); assert(keylen <= CRITBIT_MAX_KEYLEN); } void critbit_node_destroy(struct critbit_node *N __diagused) { assert(((uintptr_t)N & 1) == 0); } bool critbit_empty(const struct critbit *C) { return (C->cb_root == 0); } static const uint8_t * critbit_key(const struct critbit *C, const struct critbit_node *N, size_t *keylenp) { const uint8_t *k; k = (*C->cb_ops->cbo_key)(C, N, keylenp); assert(k != NULL); assert(*keylenp <= CRITBIT_MAX_KEYLEN); return k; } /* Lookup */ struct critbit_node * critbit_lookup(const struct critbit *C, const void *key, size_t keylen) { const uint8_t *const k = key; const struct critbit_branch *B; uintptr_t child; unsigned dir; struct critbit_node *N; const uint8_t *k0; size_t keylen0; size_t i; assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, not there. */ if ((child = load_child(C, &C->cb_root)) == 0) return NULL; /* Find the first candidate match. */ for (; isbranch(child); child = load_child(C, &B->cbb_child[dir])) { unsigned byte; B = child2branch(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (B->cbb_bits | byte)) >> 9; } /* Get the node. */ assert(isleaf(child)); N = child2leaf(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); k0 = critbit_key(C, N, &keylen0); /* Reject if the prefix doesn't match. */ if (keylen0 != keylen) return NULL; for (i = 0; i < keylen; i++) if (k[i] != k0[i]) return NULL; /* Success! */ return N; } /* Min/max */ static struct critbit_node * critbit_extreme(const struct critbit *C, unsigned dir) { struct critbit_branch *B; struct critbit_node *N; uintptr_t child; if ((child = load_child(C, &C->cb_root)) == 0) return NULL; for (; isbranch(child); child = load_child(C, &B->cbb_child[dir])) { B = child2branch(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); } assert(isleaf(child)); N = child2leaf(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); return N; } struct critbit_node * critbit_min(const struct critbit *C) { return critbit_extreme(C, 0); } struct critbit_node * critbit_max(const struct critbit *C) { return critbit_extreme(C, 0); } /* Min/max with prefix */ static struct critbit_node * critbit_extreme_prefix(const struct critbit *C, const void *key, size_t keylen, unsigned subdir) { const uint8_t *const k = key; const struct critbit_branch *B; uintptr_t child; unsigned dir; struct critbit_node *N; const uint8_t *k0; size_t keylen0; size_t i; assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, not there. */ if ((child = load_child(C, &C->cb_root)) == 0) return NULL; /* Find the first candidate match. */ for (; isbranch(child); child = load_child(C, &B->cbb_child[dir])) { unsigned byte; B = child2branch(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); if (B->cbb_idx < keylen) { byte = 0x100 | k[B->cbb_idx]; dir = (1 + (B->cbb_bits | byte)) >> 9; } else { dir = subdir; } } /* Get the node. */ assert(isleaf(child)); N = child2leaf(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); k0 = critbit_key(C, N, &keylen0); /* Reject if the prefix doesn't match. */ if (keylen0 < keylen) return NULL; for (i = 0; i < keylen; i++) if (k[i] != k0[i]) return NULL; /* Success! */ return N; } struct critbit_node * critbit_min_prefix(const struct critbit *C, const void *key, size_t keylen) { return critbit_extreme_prefix(C, key, keylen, 0); } struct critbit_node * critbit_max_prefix(const struct critbit *C, const void *key, size_t keylen) { return critbit_extreme_prefix(C, key, keylen, 1); } /* Insert */ struct critbit_node * critbit_insert_explicit(struct critbit *C, struct critbit_node *N, struct critbit_branch **B_new) { size_t keylen, keylen0; const uint8_t *k, *k0; struct critbit_branch *B; uintptr_t child, *childp; unsigned dir, byte = 0 /*XXXGCC*/, newdir, newbyte; struct critbit_node *N0; uint32_t i, diff, newbits; /* The node had better be aligned. */ assert(((uintptr_t)N & 1) == 0); /* The branch pointer had better be provided, and aligned. */ assert(*B_new != NULL); assert(((uintptr_t)*B_new & 1) == 0); /* Get the key. */ k = critbit_key(C, N, &keylen); assert(k != NULL); assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, insert it at the root. */ if (C->cb_root == 0) { store_child(C, &C->cb_root, leaf2child(N)); return N; /* inserted */ } /* Find the first candidate match. */ for (child = C->cb_root; isbranch(child); child = B->cbb_child[dir]) { B = child2branch(child); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (B->cbb_bits | byte)) >> 9; } /* Get the candidate node. */ assert(isleaf(child)); N0 = child2leaf(child); k0 = critbit_key(C, N0, &keylen0); /* Find the index of the critical byte. */ for (i = 0; i < MIN(keylen, keylen0); i++) { newbyte = k[i]; if ((diff = k0[i] ^ newbyte) != 0) goto branch; } if (keylen < keylen0) { /* new key k is shorter */ newbyte = 0; diff = 0x100 | k0[i]; goto branch; } else if (keylen0 < keylen) { /* existing key k0 is shorter */ newbyte = k[i]; diff = 0x100 | newbyte; goto branch; } return N0; /* collision */ branch: /* * Find the critical bit: * * . Set all bits from LSB up to the critical bit. * . Clear all bits but the critical bit. * . Complement -- set all bits but the critical bit. * * This way, newbits | b is 0x1ff iff b has 1 in the critical * bit, so that (1 + (newbits | b)) >> 9 is 1 iff b has 1 in * the critical bit. */ diff |= diff >> 1; diff |= diff >> 2; diff |= diff >> 4; diff |= diff >> 8; diff ^= diff >> 1; newbits = diff ^ 0x1ff; /* Direction from parent in which to put the new item. */ newdir = (1 + (newbits | newbyte)) >> 9; /* Find where to insert a new branch. */ for (childp = &C->cb_root; isbranch(*childp); childp = &B->cbb_child[dir]) { B = child2branch(*childp); if (i < B->cbb_idx) break; if (i == B->cbb_idx && newbits < B->cbb_bits) break; byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (B->cbb_bits | byte)) >> 9; } /* Claim and initialize the new branch. */ B = *B_new; *B_new = NULL; B->cbb_idx = i; B->cbb_bits = newbits; B->cbb_child[newdir] = leaf2child(N); B->cbb_child[revdir(newdir)] = *childp; /* * Publish the new branch; store_child guarantees the caller's * writes and branch initialization have completed before * anything after load_child attempts to read them. */ store_child(C, childp, branch2child(B)); return N; /* inserted */ } struct critbit_node * critbit_insert(struct critbit *C, struct critbit_node *N) { struct critbit_branch *B; struct critbit_node *N0; /* Preallocate a branch, or fail if we can't. */ B = critbit_branch_alloc(C); if (B == NULL) return NULL; /* Insert the node with the preallocated branch. */ N0 = critbit_insert_explicit(C, N, &B); /* * If the tree was empty so critbit_insert_explicit didn't use * the branch, then free the branch we preallocated. */ if (B != NULL) critbit_branch_free(C, B); /* Return the node that is in the tree, either N or a collision. */ return N0; } struct critbit_node * critbit_delete_key_explicit(struct critbit *C, const void *key, size_t keylen, struct critbit_branch **B_ret) { const uint8_t *const k = key; struct critbit_branch *B = NULL; uintptr_t *childp, *parentp = NULL; unsigned dir = 0 /*XXXGCC*/, byte; struct critbit_node *N; const uint8_t *k0; size_t keylen0; uint32_t i; /* If the tree is empty, do nothing. */ if (C->cb_root == 0) return NULL; /* Find the closest node. */ for (childp = &C->cb_root; isbranch(*childp); childp = &B->cbb_child[dir]) { parentp = childp; B = child2branch(*childp); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (B->cbb_bits | byte)) >> 9; } /* Ignore it if it doesn't match. */ assert(isleaf(*childp)); N = child2leaf(*childp); k0 = critbit_key(C, N, &keylen0); if (keylen0 != keylen) return NULL; for (i = 0; i < keylen; i++) { if (k0[i] != k[i]) return NULL; } /* If the root was a leaf, just replace it by empty. */ if (parentp == NULL) { assert(childp == &C->cb_root); assert(C->cb_root == leaf2child(N)); C->cb_root = 0; *B_ret = NULL; /* no branch pruned */ return N; } /* * Otherwise, replace it by the other child. No memory * ordering required because we're not publishing anything * new: whoever inserted the child that will remain will have * used store_child to publish it. However, caller must wait * until all pending lookups have completed before recycling * the pruned branch. */ assert(B != NULL); assert(B->cbb_child[dir] == leaf2child(N)); *parentp = B->cbb_child[revdir(dir)]; /* Return the node we deleted and the branch we pruned. */ *B_ret = B; return N; } struct critbit_node * critbit_delete_key(struct critbit *C, const void *key, size_t keylen) { struct critbit_node *N; struct critbit_branch *B = NULL; /* Delete the key, which might prune a branch. */ N = critbit_delete_key_explicit(C, key, keylen, &B); /* If a branch was pruned, free it. */ if (B != NULL) critbit_branch_free(C, B); /* Return the node we deleted. */ return N; } void critbit_delete_explicit(struct critbit *C, struct critbit_node *N, struct critbit_branch **B_ret) { struct critbit_node *N0; const void *key; size_t keylen; /* Get the key. */ key = critbit_key(C, N, &keylen); /* * Delete by the key. Without parent pointers, we can do no * better than this. */ N0 = critbit_delete_key_explicit(C, key, keylen, B_ret); /* The node had better be the same one. */ assert(N0 == N); } void critbit_delete(struct critbit *C, struct critbit_node *N) { struct critbit_branch *B = NULL; /* Delete the node, which might prune a branch. */ critbit_delete_explicit(C, N, &B); /* If a branch was pruned, free it. */ if (B != NULL) critbit_branch_free(C, B); } /* Iteration */ void critbit_iter_init(struct critbit *C, struct critbit_iter *I, void *stack, size_t stacklen) { assert(stacklen <= CRITBIT_MAX_KEYLEN); I->cbi_critbit = C; I->cbi_stack = stack; I->cbi_stacklen = stacklen; I->cbi_depth = 0; } void critbit_iter_destroy(struct critbit *C __diagused, struct critbit_iter *I) { assert(I->cbi_critbit == C); assert(I->cbi_stack != NULL); I->cbi_critbit = NULL; I->cbi_stack = NULL; I->cbi_stacklen = 0; I->cbi_depth = UINT_MAX; } static struct critbit_node * critbit_iter_extreme(struct critbit *C, struct critbit_iter *I, unsigned dir) { unsigned char *S = I->cbi_stack; const unsigned maxdepth __diagused = CHAR_BIT*I->cbi_stacklen; struct critbit_branch *B; uintptr_t child; unsigned d; assert(I->cbi_critbit == C); assert(I->cbi_depth == 0); /* If there's nothing in the tree, we're done. */ if (C->cb_root == 0) return NULL; /* Move down and in the designated direction until we hit a leaf. */ for (d = 0, child = C->cb_root; assert(d < maxdepth), isbranch(child); d++, child = B->cbb_child[dir]) { B = child2branch(child); setdir(S, d, dir); } /* Mark where we were and return the node. */ assert(d < maxdepth); I->cbi_depth = d; I->cbi_root = C->cb_root; return child2leaf(child); } struct critbit_node * critbit_iter_min(struct critbit *C, struct critbit_iter *I) { return critbit_iter_extreme(C, I, 0); } struct critbit_node * critbit_iter_max(struct critbit *C, struct critbit_iter *I) { return critbit_iter_extreme(C, I, 1); } struct critbit_node * critbit_iter_extreme_prefix(struct critbit *C, struct critbit_iter *I, const void *key, size_t keylen, unsigned subdir) { unsigned char *S = I->cbi_stack; const unsigned maxdepth __diagused = CHAR_BIT*I->cbi_stacklen; const uint8_t *const k = key; const struct critbit_branch *B; uintptr_t child, root = C->cb_root; unsigned dir; struct critbit_node *N; const uint8_t *k0; size_t keylen0; size_t i; unsigned d = 0; assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, not there. */ if (C->cb_root == 0) return NULL; /* Find the first candidate match. */ for (child = C->cb_root; isbranch(child); child = B->cbb_child[dir]) { unsigned byte; B = child2branch(child); if (B->cbb_idx < keylen) { byte = 0x100 | k[B->cbb_idx]; dir = (1 + (B->cbb_bits | byte)) >> 9; root = B->cbb_child[dir]; } else { assert(d < maxdepth); setdir(S, d++, subdir); dir = subdir; } } /* Get the node. */ assert(isleaf(child)); N = child2leaf(child); k0 = critbit_key(C, N, &keylen0); /* Reject if the prefix doesn't match. */ if (keylen0 < keylen) return NULL; for (i = 0; i < keylen; i++) if (k[i] != k0[i]) return NULL; /* Mark where we were and return the node. */ assert(d < maxdepth); I->cbi_depth = d; I->cbi_root = root; return child2leaf(child); } struct critbit_node * critbit_iter_min_prefix(struct critbit *C, struct critbit_iter *I, const void *key, size_t keylen) { return critbit_iter_extreme_prefix(C, I, key, keylen, 0); } struct critbit_node * critbit_iter_max_prefix(struct critbit *C, struct critbit_iter *I, const void *key, size_t keylen) { return critbit_iter_extreme_prefix(C, I, key, keylen, 1); } static struct critbit_node * critbit_iter_adjacent(struct critbit *C __diagused, struct critbit_iter *I, unsigned dir) { unsigned char *S = I->cbi_stack; const unsigned maxdepth __diagused = CHAR_BIT*I->cbi_stacklen; struct critbit_branch *B; unsigned d0, d, dir0; uintptr_t child; assert(I->cbi_critbit == C); /* Move back up until we can move forward. */ for (d0 = I->cbi_depth; d0 --> 0;) { /* Can we move forward? */ if (getdir(S, d0) != dir) { /* Yes. First, make one step forward. */ setdir(S, d0++, dir); /* Next, follow the path down the stack. */ for (d = 0, child = I->cbi_root; d < d0; d++, child = B->cbb_child[dir0]) { assert(isbranch(child)); B = child2branch(child); dir0 = getdir(S, d); } /* Now move down and in reverse as far as we can. */ for (; assert(d < maxdepth), isbranch(child); d++, child = B->cbb_child[revdir(dir)]) { B = child2branch(child); setdir(S, d, revdir(dir)); } /* Stop here. We are done. */ assert(d < maxdepth); I->cbi_depth = d; return child2leaf(child); } } /* There is nothing more. Note that we are done. */ I->cbi_depth = 0; return NULL; } struct critbit_node * critbit_iter_next(struct critbit *C, struct critbit_iter *I) { return critbit_iter_adjacent(C, I, 1); } struct critbit_node * critbit_iter_prev(struct critbit *C, struct critbit_iter *I) { return critbit_iter_adjacent(C, I, 0); } /* Consistency check */ static void critbit_check_leaf(const struct critbit *C, const struct critbit_node *N) { const uint8_t *k; size_t keylen; const struct critbit_branch *B; uintptr_t child; unsigned dir; k = critbit_key(C, N, &keylen); assert(C->cb_root != 0); for (child = C->cb_root; isbranch(child); child = B->cbb_child[dir]) { unsigned byte; B = child2branch(child); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (B->cbb_bits | byte)) >> 9; } assert(isleaf(child)); assert(N == child2leaf(child)); } static void critbit_check_child(struct critbit *C, uintptr_t child, size_t idx __diagused) { if (isbranch(child)) { struct critbit_branch *B = child2branch(child); assert(idx <= B->cbb_idx); critbit_check_child(C, B->cbb_child[0], B->cbb_idx); critbit_check_child(C, B->cbb_child[1], B->cbb_idx); } else { critbit_check_leaf(C, child2leaf(child)); } } void critbit_check(struct critbit *C) { if (C->cb_root == 0) return; critbit_check_child(C, C->cb_root, 0); } /* Print */ /* * WARNING: This debugging operation requires that the node's key be a * NUL-terminated printable string. */ #include #include static void critbit_print_child(struct critbit *C, uintptr_t child, unsigned indent) { if (isbranch(child)) { struct critbit_branch *const B = child2branch(child); printf("%*sbranch on 8*%u + %u (0x%02x) @ %p\n", indent*2, "", B->cbb_idx, 9 - ffs(0x1ff ^ B->cbb_bits), 0x1ff ^ B->cbb_bits, B); critbit_print_child(C, B->cbb_child[0], indent + 1); critbit_print_child(C, B->cbb_child[1], indent + 1); } else { struct critbit_node *const N = child2leaf(child); size_t keylen __unused; const uint8_t *const k = critbit_key(C, N, &keylen); printf("%*sleaf @ %p: %s\n", indent*2, "", N, k); } } void critbit_print(struct critbit *C) { if (C->cb_root == 0) { printf("empty\n"); return; } critbit_print_child(C, C->cb_root, 0); }