thmap
thmap_gc(thmap_t *thmap, void *ref)
gc_free(thmap, THMAP_GETOFF(thmap, &gc->data[0]), gc->len);
thmap_t *thmap;
thmap = kmem_zalloc(sizeof(thmap_t), KM_SLEEP);
thmap->baseptr = baseptr;
thmap->ops = ops ? ops : &thmap_default_ops;
thmap->flags = flags;
if ((thmap->flags & THMAP_SETROOT) == 0) {
root = gc_alloc(thmap, THMAP_ROOT_LEN);
kmem_free(thmap, sizeof(thmap_t));
thmap->root = THMAP_GETPTR(thmap, root);
memset(thmap->root, 0, THMAP_ROOT_LEN);
cprng_strong(kern_cprng, thmap->seed, sizeof thmap->seed, 0);
return thmap;
thmap_setroot(thmap_t *thmap, uintptr_t root_off)
if (thmap->root) {
thmap->root = THMAP_GETPTR(thmap, root_off);
thmap_getroot(const thmap_t *thmap)
return THMAP_GETOFF(thmap, thmap->root);
thmap_destroy(thmap_t *thmap)
uintptr_t root = THMAP_GETOFF(thmap, thmap->root);
ref = thmap_stage_gc(thmap);
thmap_gc(thmap, ref);
if ((thmap->flags & THMAP_SETROOT) == 0) {
gc_free(thmap, root, THMAP_ROOT_LEN);
kmem_free(thmap, sizeof(thmap_t));
gc_alloc(const thmap_t *thmap, size_t len)
const uintptr_t gcaddr = thmap->ops->alloc(alloclen);
thmap_gc_t *const gc = THMAP_GETPTR(thmap, gcaddr);
return THMAP_GETOFF(thmap, &gc->data[0]);
gc_free(const thmap_t *thmap, uintptr_t addr, size_t len)
char *const ptr = THMAP_GETPTR(thmap, addr);
const uintptr_t gcaddr = THMAP_GETOFF(thmap, gc);
thmap, thmap->ops, (void *)addr, len, gc, gc->len);
thmap->ops->free(gcaddr, alloclen);
hashval_getleafslot(const thmap_t *thmap,
const void *key = THMAP_GETPTR(thmap, leaf->key);
return (hash(thmap->seed, key, leaf->len, i) >> shift) & LEVEL_MASK;
hashval_getl0slot(const thmap_t *thmap, const thmap_query_t *query,
return hashval_getleafslot(thmap, leaf, 0);
key_cmp_p(const thmap_t *thmap, const thmap_leaf_t *leaf,
const void *leafkey = THMAP_GETPTR(thmap, leaf->key);
node_create(thmap_t *thmap, thmap_inode_t *parent)
p = gc_alloc(thmap, THMAP_INODE_LEN);
node = THMAP_GETPTR(thmap, p);
node->parent = THMAP_GETOFF(thmap, parent);
leaf_create(const thmap_t *thmap, const void *key, size_t len, void *val)
leaf_off = gc_alloc(thmap, sizeof(thmap_leaf_t));
leaf = THMAP_GETPTR(thmap, leaf_off);
if ((thmap->flags & THMAP_NOCOPY) == 0) {
key_off = gc_alloc(thmap, len);
gc_free(thmap, leaf_off, sizeof(thmap_leaf_t));
memcpy(THMAP_GETPTR(thmap, key_off), key, len);
leaf_free(const thmap_t *thmap, thmap_leaf_t *leaf)
if ((thmap->flags & THMAP_NOCOPY) == 0) {
gc_free(thmap, leaf->key, leaf->len);
gc_free(thmap, THMAP_GETOFF(thmap, leaf), sizeof(thmap_leaf_t));
get_leaf(const thmap_t *thmap, thmap_inode_t *parent, unsigned slot)
return THMAP_NODE(thmap, node);
root_try_put(thmap_t *thmap, const thmap_query_t *query, thmap_leaf_t *leaf)
if (atomic_load_relaxed(&thmap->root[i])) {
node = node_create(thmap, NULL);
slot = hashval_getl0slot(thmap, query, leaf);
node_insert(node, slot, THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT);
nptr = THMAP_GETOFF(thmap, node);
if (atomic_load_relaxed(&thmap->root[i])) {
gc_free(thmap, nptr, THMAP_INODE_LEN);
if (!atomic_compare_exchange_weak_explicit_ptr(&thmap->root[i], &expected,
find_edge_node(const thmap_t *thmap, thmap_query_t *query,
root_slot = atomic_load_consume(&thmap->root[query->rslot]);
parent = THMAP_NODE(thmap, root_slot);
parent = THMAP_NODE(thmap, node);
find_edge_node_locked(const thmap_t *thmap, thmap_query_t *query,
node = find_edge_node(thmap, query, key, len, slot);
thmap_get(thmap_t *thmap, const void *key, size_t len)
hashval_init(&query, thmap->seed, key, len);
parent = find_edge_node(thmap, &query, key, len, &slot);
leaf = get_leaf(thmap, parent, slot);
if (!key_cmp_p(thmap, leaf, key, len)) {
thmap_put(thmap_t *thmap, const void *key, size_t len, void *val)
leaf = leaf_create(thmap, key, len, val);
hashval_init(&query, thmap->seed, key, len);
switch (root_try_put(thmap, &query, leaf)) {
parent = find_edge_node_locked(thmap, &query, key, len, &slot);
target = THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT;
other = THMAP_NODE(thmap, target);
if (key_cmp_p(thmap, other, key, len)) {
leaf_free(thmap, leaf);
child = node_create(thmap, parent);
leaf_free(thmap, leaf);
other_slot = hashval_getleafslot(thmap, other, query.level);
target = THMAP_GETOFF(thmap, other) | THMAP_LEAF_BIT;
atomic_store_release(&parent->slots[slot], THMAP_GETOFF(thmap, child));
target = THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT;
thmap_del(thmap_t *thmap, const void *key, size_t len)
hashval_init(&query, thmap->seed, key, len);
parent = find_edge_node_locked(thmap, &query, key, len, &slot);
leaf = get_leaf(thmap, parent, slot);
if (!leaf || !key_cmp_p(thmap, leaf, key, len)) {
ASSERT(THMAP_NODE(thmap, atomic_load_relaxed(&parent->slots[slot]))
parent = THMAP_NODE(thmap, node->parent);
ASSERT(THMAP_NODE(thmap,
stage_mem_gc(thmap, THMAP_GETOFF(thmap, node), THMAP_INODE_LEN);
atomic_load_relaxed(&thmap->root[rslot]);
ASSERT(THMAP_GETOFF(thmap, parent) == nptr);
atomic_store_relaxed(&thmap->root[rslot], THMAP_NULL);
stage_mem_gc(thmap, nptr, THMAP_INODE_LEN);
if ((thmap->flags & THMAP_NOCOPY) == 0) {
stage_mem_gc(thmap, leaf->key, leaf->len);
stage_mem_gc(thmap, THMAP_GETOFF(thmap, leaf), sizeof(thmap_leaf_t));
stage_mem_gc(thmap_t *thmap, uintptr_t addr, size_t len)
char *const ptr = THMAP_GETPTR(thmap, addr);
thmap, thmap->ops, (char *)addr, len, gc, gc->len);
head = atomic_load_relaxed(&thmap->gc_list);
if (!atomic_compare_exchange_weak_explicit_ptr(&thmap->gc_list, &head, gc,
thmap_stage_gc(thmap_t *thmap)
return atomic_exchange_explicit(&thmap->gc_list, NULL,
struct thmap *wg_peers_bypubkey;
struct thmap *wg_peers_byname;
struct thmap *wg_sessions_byindex;
struct thmap;
typedef struct thmap thmap_t;