229 struct thmap {  struct
262 gc_alloc(const thmap_t *thmap, size_t len)  in gc_alloc()  argument
265 	const uintptr_t gcaddr = thmap->ops->alloc(alloclen);  in gc_alloc()
270 	thmap_gc_t *const gc = THMAP_GETPTR(thmap, gcaddr);  in gc_alloc()
272 	return THMAP_GETOFF(thmap, &gc->data[0]);  in gc_alloc()
276 gc_free(const thmap_t *thmap, uintptr_t addr, size_t len)  in gc_free()  argument
279 	char *const ptr = THMAP_GETPTR(thmap, addr);  in gc_free()
281 	const uintptr_t gcaddr = THMAP_GETOFF(thmap, gc);  in gc_free()
285 	    thmap, thmap->ops, (void *)addr, len, gc, gc->len);  in gc_free()
286 	thmap->ops->free(gcaddr, alloclen);  in gc_free()
393 hashval_getleafslot(const thmap_t *thmap,  in hashval_getleafslot()  argument
396 	const void *key = THMAP_GETPTR(thmap, leaf->key);  in hashval_getleafslot()
401 	return (hash(thmap->seed, key, leaf->len, i) >> shift) & LEVEL_MASK;  in hashval_getleafslot()
405 hashval_getl0slot(const thmap_t *thmap, const thmap_query_t *query,  in hashval_getl0slot()  argument
411 	return hashval_getleafslot(thmap, leaf, 0);  in hashval_getl0slot()
415 key_cmp_p(const thmap_t *thmap, const thmap_leaf_t *leaf,  in key_cmp_p()  argument
418 	const void *leafkey = THMAP_GETPTR(thmap, leaf->key);  in key_cmp_p()
427 node_create(thmap_t *thmap, thmap_inode_t *parent)  in node_create()  argument
432 	p = gc_alloc(thmap, THMAP_INODE_LEN);  in node_create()
436 	node = THMAP_GETPTR(thmap, p);  in node_create()
443 		node->parent = THMAP_GETOFF(thmap, parent);  in node_create()
488 leaf_create(const thmap_t *thmap, const void *key, size_t len, void *val)  in leaf_create()  argument
493 	leaf_off = gc_alloc(thmap, sizeof(thmap_leaf_t));  in leaf_create()
497 	leaf = THMAP_GETPTR(thmap, leaf_off);  in leaf_create()
500 	if ((thmap->flags & THMAP_NOCOPY) == 0) {  in leaf_create()
504 		key_off = gc_alloc(thmap, len);  in leaf_create()
506 			gc_free(thmap, leaf_off, sizeof(thmap_leaf_t));  in leaf_create()
509 		memcpy(THMAP_GETPTR(thmap, key_off), key, len);  in leaf_create()
521 leaf_free(const thmap_t *thmap, thmap_leaf_t *leaf)  in leaf_free()  argument
523 	if ((thmap->flags & THMAP_NOCOPY) == 0) {  in leaf_free()
524 		gc_free(thmap, leaf->key, leaf->len);  in leaf_free()
526 	gc_free(thmap, THMAP_GETOFF(thmap, leaf), sizeof(thmap_leaf_t));  in leaf_free()
530 get_leaf(const thmap_t *thmap, thmap_inode_t *parent, unsigned slot)  in get_leaf()  argument
539 	return THMAP_NODE(thmap, node);  in get_leaf()
553 root_try_put(thmap_t *thmap, const thmap_query_t *query, thmap_leaf_t *leaf)  in root_try_put()  argument
566 	if (atomic_load_relaxed(&thmap->root[i])) {  in root_try_put()
575 	node = node_create(thmap, NULL);  in root_try_put()
579 	slot = hashval_getl0slot(thmap, query, leaf);  in root_try_put()
580 	node_insert(node, slot, THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT);  in root_try_put()
581 	nptr = THMAP_GETOFF(thmap, node);  in root_try_put()
583 	if (atomic_load_relaxed(&thmap->root[i])) {  in root_try_put()
584 		gc_free(thmap, nptr, THMAP_INODE_LEN);  in root_try_put()
589 	if (!atomic_compare_exchange_weak_explicit_ptr(&thmap->root[i], &expected,  in root_try_put()
603 find_edge_node(const thmap_t *thmap, thmap_query_t *query,  in find_edge_node()  argument
614 	root_slot = atomic_load_consume(&thmap->root[query->rslot]);  in find_edge_node()
615 	parent = THMAP_NODE(thmap, root_slot);  in find_edge_node()
626 		parent = THMAP_NODE(thmap, node);  in find_edge_node()
651 find_edge_node_locked(const thmap_t *thmap, thmap_query_t *query,  in find_edge_node_locked()  argument
661 	node = find_edge_node(thmap, query, key, len, slot);  in find_edge_node_locked()
694 thmap_get(thmap_t *thmap, const void *key, size_t len)  in thmap_get()  argument
701 	hashval_init(&query, thmap->seed, key, len);  in thmap_get()
702 	parent = find_edge_node(thmap, &query, key, len, &slot);  in thmap_get()
706 	leaf = get_leaf(thmap, parent, slot);  in thmap_get()
710 	if (!key_cmp_p(thmap, leaf, key, len)) {  in thmap_get()
723 thmap_put(thmap_t *thmap, const void *key, size_t len, void *val)  in thmap_put()  argument
734 	leaf = leaf_create(thmap, key, len, val);  in thmap_put()
738 	hashval_init(&query, thmap->seed, key, len);  in thmap_put()
743 	switch (root_try_put(thmap, &query, leaf)) {  in thmap_put()
764 	parent = find_edge_node_locked(thmap, &query, key, len, &slot);  in thmap_put()
774 		target = THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT;  in thmap_put()
782 	other = THMAP_NODE(thmap, target);  in thmap_put()
783 	if (key_cmp_p(thmap, other, key, len)) {  in thmap_put()
788 		leaf_free(thmap, leaf);  in thmap_put()
798 	child = node_create(thmap, parent);  in thmap_put()
800 		leaf_free(thmap, leaf);  in thmap_put()
810 	other_slot = hashval_getleafslot(thmap, other, query.level);  in thmap_put()
811 	target = THMAP_GETOFF(thmap, other) | THMAP_LEAF_BIT;  in thmap_put()
822 	atomic_store_release(&parent->slots[slot], THMAP_GETOFF(thmap, child));  in thmap_put()
842 	target = THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT;  in thmap_put()
853 thmap_del(thmap_t *thmap, const void *key, size_t len)  in thmap_del()  argument
861 	hashval_init(&query, thmap->seed, key, len);  in thmap_del()
862 	parent = find_edge_node_locked(thmap, &query, key, len, &slot);  in thmap_del()
867 	leaf = get_leaf(thmap, parent, slot);  in thmap_del()
868 	if (!leaf || !key_cmp_p(thmap, leaf, key, len)) {  in thmap_del()
875 	ASSERT(THMAP_NODE(thmap, atomic_load_relaxed(&parent->slots[slot]))  in thmap_del()
895 		parent = THMAP_NODE(thmap, node->parent);  in thmap_del()
913 		ASSERT(THMAP_NODE(thmap,  in thmap_del()
918 		stage_mem_gc(thmap, THMAP_GETOFF(thmap, node), THMAP_INODE_LEN);  in thmap_del()
931 		    atomic_load_relaxed(&thmap->root[rslot]);  in thmap_del()
935 		ASSERT(THMAP_GETOFF(thmap, parent) == nptr);  in thmap_del()
940 		atomic_store_relaxed(&thmap->root[rslot], THMAP_NULL);  in thmap_del()
942 		stage_mem_gc(thmap, nptr, THMAP_INODE_LEN);  in thmap_del()
950 	if ((thmap->flags & THMAP_NOCOPY) == 0) {  in thmap_del()
951 		stage_mem_gc(thmap, leaf->key, leaf->len);  in thmap_del()
953 	stage_mem_gc(thmap, THMAP_GETOFF(thmap, leaf), sizeof(thmap_leaf_t));  in thmap_del()
962 stage_mem_gc(thmap_t *thmap, uintptr_t addr, size_t len)  in stage_mem_gc()  argument
964 	char *const ptr = THMAP_GETPTR(thmap, addr);  in stage_mem_gc()
970 	    thmap, thmap->ops, (char *)addr, len, gc, gc->len);  in stage_mem_gc()
972 	head = atomic_load_relaxed(&thmap->gc_list);  in stage_mem_gc()
976 	if (!atomic_compare_exchange_weak_explicit_ptr(&thmap->gc_list, &head, gc,  in stage_mem_gc()
983 thmap_stage_gc(thmap_t *thmap)  in thmap_stage_gc()  argument
986 	return atomic_exchange_explicit(&thmap->gc_list, NULL,  in thmap_stage_gc()
991 thmap_gc(thmap_t *thmap, void *ref)  in thmap_gc()  argument
997 		gc_free(thmap, THMAP_GETOFF(thmap, &gc->data[0]), gc->len);  in thmap_gc()
1008 	thmap_t *thmap;  in thmap_create()  local
1017 	thmap = kmem_zalloc(sizeof(thmap_t), KM_SLEEP);  in thmap_create()
1018 	thmap->baseptr = baseptr;  in thmap_create()
1019 	thmap->ops = ops ? ops : &thmap_default_ops;  in thmap_create()
1020 	thmap->flags = flags;  in thmap_create()
1022 	if ((thmap->flags & THMAP_SETROOT) == 0) {  in thmap_create()
1024 		root = gc_alloc(thmap, THMAP_ROOT_LEN);  in thmap_create()
1026 			kmem_free(thmap, sizeof(thmap_t));  in thmap_create()
1029 		thmap->root = THMAP_GETPTR(thmap, root);  in thmap_create()
1030 		memset(thmap->root, 0, THMAP_ROOT_LEN);  in thmap_create()
1033 	cprng_strong(kern_cprng, thmap->seed, sizeof thmap->seed, 0);  in thmap_create()
1035 	return thmap;  in thmap_create()
1039 thmap_setroot(thmap_t *thmap, uintptr_t root_off)  in thmap_setroot()  argument
1041 	if (thmap->root) {  in thmap_setroot()
1044 	thmap->root = THMAP_GETPTR(thmap, root_off);  in thmap_setroot()
1049 thmap_getroot(const thmap_t *thmap)  in thmap_getroot()  argument
1051 	return THMAP_GETOFF(thmap, thmap->root);  in thmap_getroot()
1055 thmap_destroy(thmap_t *thmap)  in thmap_destroy()  argument
1057 	uintptr_t root = THMAP_GETOFF(thmap, thmap->root);  in thmap_destroy()
1060 	ref = thmap_stage_gc(thmap);  in thmap_destroy()
1061 	thmap_gc(thmap, ref);  in thmap_destroy()
1063 	if ((thmap->flags & THMAP_SETROOT) == 0) {  in thmap_destroy()
1064 		gc_free(thmap, root, THMAP_ROOT_LEN);  in thmap_destroy()
1066 	kmem_free(thmap, sizeof(thmap_t));  in thmap_destroy()