Cross Reference: /src/sys/kern/subr

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