D46895.diff
No OneTemporary
Actions

Size

31 KB

Referenced Files

None

Subscribers

None

D46895.diff
View Options

	Index: sys/kern/subr_pctrie.c
	===================================================================
	--- sys/kern/subr_pctrie.c
	+++ sys/kern/subr_pctrie.c
	@@ -54,9 +54,6 @@
	#include <sys/kernel.h>
	#include <sys/libkern.h>
	#include <sys/pctrie.h>
	-#include <sys/proc.h> /* smr.h depends on struct thread. */
	-#include <sys/smr.h>
	-#include <sys/smr_types.h>

	#ifdef DDB
	#include <ddb/ddb.h>
	@@ -74,9 +71,6 @@
	_Static_assert(sizeof(pn_popmap_t) <= sizeof(int),
	"pn_popmap_t too wide");

	-struct pctrie_node;
	-typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t;
	-
	struct pctrie_node {
	uint64_t pn_owner; /* Owner of record. */
	pn_popmap_t pn_popmap; /* Valid children. */
	@@ -107,66 +101,6 @@
	return (false);
	}

	-/*
	- * Check radix node.
	- */
	-static __inline void
	-pctrie_node_put(struct pctrie_node *node)
	-{
	-#ifdef INVARIANTS
	- int slot;
	-
	- KASSERT(powerof2(node->pn_popmap),
	- ("pctrie_node_put: node %p has too many children %04x", node,
	- node->pn_popmap));
	- for (slot = 0; slot < PCTRIE_COUNT; slot++) {
	- if ((node->pn_popmap & (1 << slot)) != 0)
	- continue;
	- KASSERT(smr_unserialized_load(&node->pn_child[slot], true) ==
	- PCTRIE_NULL,
	- ("pctrie_node_put: node %p has a child", node));
	- }
	-#endif
	-}
	-
	-enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
	-
	-/*
	- * Fetch a node pointer from a slot.
	- */
	-static __inline struct pctrie_node *
	-pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
	-{
	- switch (access) {
	- case PCTRIE_UNSERIALIZED:
	- return (smr_unserialized_load(p, true));
	- case PCTRIE_LOCKED:
	- return (smr_serialized_load(p, true));
	- case PCTRIE_SMR:
	- return (smr_entered_load(p, smr));
	- }
	- __assert_unreachable();
	-}
	-
	-static __inline void
	-pctrie_node_store(smr_pctnode_t p, void v, enum pctrie_access access)
	-{
	- switch (access) {
	- case PCTRIE_UNSERIALIZED:
	- smr_unserialized_store(p, v, true);
	- break;
	- case PCTRIE_LOCKED:
	- smr_serialized_store(p, v, true);
	- break;
	- case PCTRIE_SMR:
	- panic("%s: Not supported in SMR section.", __func__);
	- break;
	- default:
	- __assert_unreachable();
	- break;
	- }
	-}
	-
	/*
	* Get the root address, cast to proper type for load/store.
	*/
	@@ -194,15 +128,6 @@
	return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
	}

	-/*
	- * Returns val with leaf bit set.
	- */
	-static __inline void *
	-pctrie_toleaf(uint64_t *val)
	-{
	- return ((void *)((uintptr_t)val \| PCTRIE_ISLEAF));
	-}
	-
	/*
	* Returns the associated val extracted from node.
	*/
	@@ -221,20 +146,29 @@
	return ((void *)(((uintptr_t)node & ~PCTRIE_FLAGS) - keyoff));
	}

	+/*
	+ * Change the state of the 'slot'th popmap bit from clear to set.
	+ */
	+static __inline void
	+pctrie_setpop(struct pctrie_node *node, int slot)
	+{
	+ node->pn_popmap ^= 1 << slot;
	+ KASSERT((node->pn_popmap & (1 << slot)) != 0,
	+ ("%s: bad popmap slot %d in node %p", __func__, slot, node));
	+}
	+
	/*
	* Make 'child' a child of 'node'.
	*/
	static __inline void
	pctrie_addnode(struct pctrie_node *node, uint64_t index,
	- struct pctrie_node *child, enum pctrie_access access)
	+ struct pctrie_node *child)
	{
	int slot;

	slot = pctrie_slot(node, index);
	- pctrie_node_store(&node->pn_child[slot], child, access);
	- node->pn_popmap ^= 1 << slot;
	- KASSERT((node->pn_popmap & (1 << slot)) != 0,
	- ("%s: bad popmap slot %d in node %p", __func__, slot, node));
	+ pctrie_node_store(&node->pn_child[slot], child, PCTRIE_UNSERIALIZED);
	+ pctrie_setpop(node, slot);
	}

	/*
	@@ -282,16 +216,18 @@
	* Note that mode is expected to be a compile-time constant, and this procedure
	* is expected to be inlined into callers with extraneous code optimized out.
	*/
	-static __always_inline void *
	-pctrie_insert_lookup_compound(struct pctrie ptree, uint64_t val,
	+static __always_inline smr_pctnode_t *
	+pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t index,
	uint64_t found_out, struct pctrie_node neighbor_out,
	enum pctrie_insert_neighbor_mode mode)
	{
	- uint64_t index;
	struct pctrie_node node, parent;
	int slot;

	- index = *val;
	+ if (neighbor_out != NULL)
	+ *neighbor_out = NULL;
	+ if (found_out != NULL)
	+ *found_out = NULL;

	/*
	* The owner of record for root is not really important because it
	@@ -301,19 +237,13 @@
	parent = NULL;
	for (;;) {
	if (pctrie_isleaf(node)) {
	- if (node == PCTRIE_NULL) {
	- if (parent == NULL)
	- pctrie_node_store(pctrie_root(ptree),
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	- else
	- pctrie_addnode(parent, index,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	- return (NULL);
	- }
	- if (*pctrie_toval(node) == index) {
	- *found_out = pctrie_toval(node);
	- return (NULL);
	- }
	+ if (node != PCTRIE_NULL) {
	+ if (*pctrie_toval(node) == index) {
	+ *found_out = pctrie_toval(node);
	+ return (NULL);
	+ }
	+ } else if (parent != NULL)
	+ pctrie_setpop(parent, slot);
	break;
	}
	if (pctrie_keybarr(node, index, &slot))
	@@ -336,22 +266,21 @@
	}

	/*
	- * The caller will split this node. If we're tracking the next
	- * neighbor, record the old node if the old entry is in the right
	- * direction.
	+ * If we're tracking the next neighbor, and node is not NULL, record
	+ * this future sibling node if it is in the right direction.
	*/
	- if (mode == PCTRIE_INSERT_NEIGHBOR_LT) {
	+ if (node != PCTRIE_NULL && mode == PCTRIE_INSERT_NEIGHBOR_LT) {
	if (*pctrie_toval(node) < index)
	*neighbor_out = node;
	- } else if (mode == PCTRIE_INSERT_NEIGHBOR_GT) {
	+ } else if (node != PCTRIE_NULL && mode == PCTRIE_INSERT_NEIGHBOR_GT) {
	if (*pctrie_toval(node) > index)
	*neighbor_out = node;
	}

	/*
	- * 'node' must be replaced in the tree with a new branch node, with
	- * children 'node' and 'val'. Return the place that points to 'node'
	- * now, and will point to to the new branching node later.
	+ * 'node' must be replaced in the tree with an index leaf, or with a new
	+ * branch node, with children 'node' and an index leaf. Return the place
	+ * that points to 'node' now, and will point to to the new node later.
	*/
	return ((parent == NULL) ? pctrie_root(ptree): &parent->pn_child[slot]);
	}
	@@ -360,18 +289,17 @@
	* Wrap pctrie_insert_lookup_compound to implement a strict insertion. Panic
	* if the key already exists, and do not look for neighboring entries.
	*/
	-void *
	-pctrie_insert_lookup_strict(struct pctrie ptree, uint64_t val)
	+smr_pctnode_t *
	+pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t index)
	{
	- void *parentp;
	+ smr_pctnode_t *parentp;
	uint64_t *found;

	- found = NULL;
	- parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL,
	+ parentp = pctrie_insert_lookup_compound(ptree, index, &found, NULL,
	PCTRIE_INSERT_NEIGHBOR_NONE);
	if (__predict_false(found != NULL))
	panic("%s: key %jx is already present", __func__,
	- (uintmax_t)*val);
	+ (uintmax_t)index);
	return (parentp);
	}

	@@ -379,12 +307,11 @@
	* Wrap pctrie_insert_lookup_compound to implement find-or-insert. Do not look
	* for neighboring entries.
	*/
	-void *
	-pctrie_insert_lookup(struct pctrie ptree, uint64_t val,
	+smr_pctnode_t *
	+pctrie_insert_lookup(struct pctrie *ptree, uint64_t index,
	uint64_t **found_out)
	{
	- *found_out = NULL;
	- return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
	+ return (pctrie_insert_lookup_compound(ptree, index, found_out, NULL,
	PCTRIE_INSERT_NEIGHBOR_NONE));
	}

	@@ -393,13 +320,11 @@
	* greater entry. Find a subtree that contains the next entry greater than the
	* newly-inserted or to-be-inserted entry.
	*/
	-void *
	-pctrie_insert_lookup_gt(struct pctrie ptree, uint64_t val,
	+smr_pctnode_t *
	+pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t index,
	uint64_t found_out, struct pctrie_node neighbor_out)
	{
	- *found_out = NULL;
	- *neighbor_out = NULL;
	- return (pctrie_insert_lookup_compound(ptree, val, found_out,
	+ return (pctrie_insert_lookup_compound(ptree, index, found_out,
	neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
	}

	@@ -408,46 +333,34 @@
	* lesser entry. Find a subtree that contains the next entry less than the
	* newly-inserted or to-be-inserted entry.
	*/
	-void *
	-pctrie_insert_lookup_lt(struct pctrie ptree, uint64_t val,
	+smr_pctnode_t *
	+pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t index,
	uint64_t found_out, struct pctrie_node neighbor_out)
	{
	- *found_out = NULL;
	- *neighbor_out = NULL;
	- return (pctrie_insert_lookup_compound(ptree, val, found_out,
	+ return (pctrie_insert_lookup_compound(ptree, index, found_out,
	neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
	}

	/*
	- * Uses new node to insert key-value pair into the trie at given location.
	+ * Prepare a newly allocated node, nulling any stray children and filling in its
	+ * new clev and owner fields
	*/
	-void
	-pctrie_insert_node(void parentp, struct pctrie_node parent, uint64_t *val)
	+static void
	+pctrie_init_node(struct pctrie_node *child, uint64_t index, uint64_t newind)
	{
	- struct pctrie_node *node;
	- uint64_t index, newind;

	/*
	- * Clear the last child pointer of the newly allocated parent. We want
	+ * Clear the last child pointer of the newly allocated child. We want
	* to clear it after the final section has exited so lookup can not
	* return false negatives. It is done here because it will be
	* cache-cold in the dtor callback.
	*/
	- if (parent->pn_popmap != 0) {
	- pctrie_node_store(&parent->pn_child[ffs(parent->pn_popmap) - 1],
	+ if (child->pn_popmap != 0) {
	+ pctrie_node_store(&child->pn_child[ffs(child->pn_popmap) - 1],
	PCTRIE_NULL, PCTRIE_UNSERIALIZED);
	- parent->pn_popmap = 0;
	+ child->pn_popmap = 0;
	}

	- /*
	- * Recover the values of the two children of the new parent node. If
	- * 'node' is not a leaf, this stores into 'newind' the 'owner' field,
	- * which must be first in the node.
	- */
	- index = *val;
	- node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED);
	- newind = *pctrie_toval(node);
	-
	/*
	* From the highest-order bit where the indexes differ,
	* compute the highest level in the trie where they differ. Then,
	@@ -456,17 +369,33 @@
	_Static_assert(sizeof(long long) >= sizeof(uint64_t),
	"uint64 too wide");
	_Static_assert(sizeof(uint64_t) * NBBY <=
	- (1 << (sizeof(parent->pn_clev) * NBBY)), "pn_clev too narrow");
	- parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);
	- parent->pn_owner = PCTRIE_COUNT;
	- parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev);
	+ (1 << (sizeof(child->pn_clev) * NBBY)), "pn_clev too narrow");
	+ child->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);
	+ child->pn_owner = PCTRIE_COUNT;
	+ child->pn_owner = index & -(child->pn_owner << child->pn_clev);
	+}
	+
	+/*
	+ * Uses new node to insert key-value pair into the trie at given location.
	+ */
	+void
	+pctrie_insert_node(smr_pctnode_t parentp, struct pctrie_node node,
	+ struct pctrie_node child, uint64_t val)
	+{
	+ uint64_t index, newind;

	+ /*
	+ * Recover the values of the two children of the new child node. If
	+ * 'node' is not a leaf, this stores into 'newind' the 'owner' field,
	+ * which must be first in the node.
	+ */
	+ index = *val;
	+ newind = *pctrie_toval(node);
	+ pctrie_init_node(child, index, newind);

	/* These writes are not yet visible due to ordering. */
	- pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
	- pctrie_addnode(parent, newind, node, PCTRIE_UNSERIALIZED);
	- /* Synchronize to make the above visible. */
	- pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
	+ pctrie_addnode(child, index, pctrie_toleaf(val));
	+ pctrie_addnode(child, newind, node);
	}

	/*
	@@ -597,35 +526,35 @@
	* to indicate where a new node must be allocated to complete insertion.
	* Assumes access is externally synchronized by a lock.
	*/
	-void *
	-pctrie_iter_insert_lookup(struct pctrie_iter it, uint64_t val)
	+smr_pctnode_t *
	+pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t index)
	{
	- struct pctrie_node *node;
	+ struct pctrie_node node, parent;
	+ int slot;

	- it->index = *val;
	- node = _pctrie_iter_lookup_node(it, *val, NULL, PCTRIE_LOCKED);
	- if (node == PCTRIE_NULL) {
	- if (it->top == 0)
	- pctrie_node_store(pctrie_root(it->ptree),
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	- else
	- pctrie_addnode(it->path[it->top - 1], it->index,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	- return (NULL);
	+ it->index = index;
	+ node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
	+ if (it->top == 0)
	+ parent = NULL;
	+ else {
	+ parent = it->path[it->top -1];
	+ slot = pctrie_slot(parent, index);
	}
	- if (__predict_false(pctrie_match_value(node, it->index) != NULL))
	- panic("%s: key %jx is already present", __func__,
	- (uintmax_t)it->index);
	+ if (node != PCTRIE_NULL) {
	+ if (__predict_false(
	+ pctrie_match_value(node, index) != NULL))
	+ panic("%s: key %jx is already present", __func__,
	+ (uintmax_t)index);
	+ } else if (parent != NULL)
	+ pctrie_setpop(parent, slot);

	/*
	- * 'node' must be replaced in the tree with a new branch node, with
	- * children 'node' and 'val'. Return the place that points to 'node'
	- * now, and will point to to the new branching node later.
	+ * 'node' must be replaced in the tree with a leaf 'val', or with a new
	+ * branch node, with children 'node' and 'val'. Return the place that
	+ * points to 'node' now, and will point to to the new node later.
	*/
	- if (it->top == 0)
	- return (pctrie_root(it->ptree));
	- node = it->path[it->top - 1];
	- return (&node->pn_child[pctrie_slot(node, it->index)]);
	+ return (parent == NULL ? pctrie_root(it->ptree) :
	+ &parent->pn_child[slot]);
	}

	/*
	@@ -1027,47 +956,31 @@
	}
	#endif

	-static void
	+static smr_pctnode_t *
	pctrie_remove(struct pctrie ptree, uint64_t index, struct pctrie_node parent,
	- struct pctrie_node node, struct pctrie_node *freenode)
	+ struct pctrie_node node, struct pctrie_node *child)
	{
	- struct pctrie_node *child;
	int slot;

	- if (node == NULL) {
	- pctrie_node_store(pctrie_root(ptree),
	- PCTRIE_NULL, PCTRIE_LOCKED);
	- return;
	- }
	+ *child = PCTRIE_NULL;
	+ if (node == NULL)
	+ return (pctrie_root(ptree));
	slot = pctrie_slot(node, index);
	KASSERT((node->pn_popmap & (1 << slot)) != 0,
	("%s: bad popmap slot %d in node %p",
	__func__, slot, node));
	node->pn_popmap ^= 1 << slot;
	- pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_LOCKED);
	if (!powerof2(node->pn_popmap))
	- return;
	+ return (&node->pn_child[slot]);
	+ pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL,
	+ PCTRIE_UNSERIALIZED);
	KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__));
	slot = ffs(node->pn_popmap) - 1;
	- child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED);
	- KASSERT(child != PCTRIE_NULL,
	+ *child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED);
	+ KASSERT(*child != PCTRIE_NULL,
	("%s: bad popmap slot %d in node %p", __func__, slot, node));
	- if (parent == NULL)
	- pctrie_node_store(pctrie_root(ptree), child, PCTRIE_LOCKED);
	- else {
	- slot = pctrie_slot(parent, index);
	- KASSERT(node ==
	- pctrie_node_load(&parent->pn_child[slot], NULL,
	- PCTRIE_LOCKED), ("%s: invalid child value", __func__));
	- pctrie_node_store(&parent->pn_child[slot], child,
	- PCTRIE_LOCKED);
	- }
	- /*
	- * The child is still valid and we can not zero the
	- * pointer until all SMR references are gone.
	- */
	- pctrie_node_put(node);
	- *freenode = node;
	+ return ((parent == NULL) ? pctrie_root(ptree) :
	+ &parent->pn_child[pctrie_slot(parent, index)]);
	}

	/*
	@@ -1076,25 +989,24 @@
	*/
	uint64_t *
	pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
	- struct pctrie_node **freenode)
	+ smr_pctnode_t parentp, struct pctrie_node child)
	{
	- struct pctrie_node child, node, *parent;
	+ struct pctrie_node next, node, *parent;
	uint64_t *m;
	int slot;

	DEBUG_POISON_POINTER(parent);
	- *freenode = node = NULL;
	- child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- while (!pctrie_isleaf(child)) {
	+ node = NULL;
	+ next = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	+ while (!pctrie_isleaf(next)) {
	parent = node;
	- node = child;
	+ node = next;
	slot = pctrie_slot(node, index);
	- child = pctrie_node_load(&node->pn_child[slot], NULL,
	+ next = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_LOCKED);
	}
	- m = pctrie_match_value(child, index);
	- if (m != NULL)
	- pctrie_remove(ptree, index, parent, node, freenode);
	+ if ((m = pctrie_match_value(next, index)) != NULL)
	+ *parentp = pctrie_remove(ptree, index, parent, node, child);
	return (m);
	}

	@@ -1103,29 +1015,30 @@
	* adjust the path if it's last member is to be freed.
	*/
	uint64_t *
	-pctrie_iter_remove(struct pctrie_iter it, struct pctrie_node *freenode)
	+pctrie_iter_remove(struct pctrie_iter *it,
	+ smr_pctnode_t parentp, struct pctrie_node child)
	{
	- struct pctrie_node child, node, *parent;
	+ struct pctrie_node next, node, *parent;
	uint64_t *m;
	int slot;

	DEBUG_POISON_POINTER(parent);
	- *freenode = NULL;
	if (it->top >= 1) {
	parent = (it->top >= 2) ? it->path[it->top - 2] : NULL;
	node = it->path[it->top - 1];
	slot = pctrie_slot(node, it->index);
	- child = pctrie_node_load(&node->pn_child[slot], NULL,
	+ next = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_LOCKED);
	} else {
	node = NULL;
	- child = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED);
	+ next = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED);
	+ }
	+ if ((m = pctrie_match_value(next, it->index)) != NULL) {
	+ *parentp = pctrie_remove(it->ptree, it->index, parent, node,
	+ child);
	+ if (*child != PCTRIE_NULL)
	+ --it->top;
	}
	- m = pctrie_match_value(child, it->index);
	- if (m != NULL)
	- pctrie_remove(it->ptree, it->index, parent, node, freenode);
	- if (*freenode != NULL)
	- --it->top;
	return (m);
	}

	@@ -1259,27 +1172,24 @@
	* Panics if there is not an old value in the trie at the new value's index.
	*/
	uint64_t *
	-pctrie_replace(struct pctrie ptree, uint64_t newval)
	+pctrie_replace(struct pctrie ptree, uint64_t newval,
	+ smr_pctnode_t parentp, struct pctrie_node child)
	{
	- struct pctrie_node leaf, parent, *node;
	+ struct pctrie_node parent, node;
	uint64_t *m;
	uint64_t index;
	int slot;

	- leaf = pctrie_toleaf(newval);
	+ *child = pctrie_toleaf(newval);
	index = *newval;
	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	parent = NULL;
	for (;;) {
	if (pctrie_isleaf(node)) {
	if ((m = pctrie_toval(node)) != NULL && *m == index) {
	- if (parent == NULL)
	- pctrie_node_store(pctrie_root(ptree),
	- leaf, PCTRIE_LOCKED);
	- else
	- pctrie_node_store(
	- &parent->pn_child[slot], leaf,
	- PCTRIE_LOCKED);
	+ *parentp = (parent == NULL) ?
	+ pctrie_root(ptree):
	+ &parent->pn_child[slot];
	return (m);
	}
	break;
	Index: sys/sys/pctrie.h
	===================================================================
	--- sys/sys/pctrie.h
	+++ sys/sys/pctrie.h
	@@ -33,13 +33,78 @@

	#include <sys/_pctrie.h>
	#include <sys/_smr.h>
	+#include <sys/proc.h> /* smr.h depends on struct thread. */
	+#include <sys/smr.h>
	+#include <sys/smr_types.h>
	+struct pctrie_node;
	+typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t;

	#ifdef _KERNEL

	typedef void (pctrie_cb_t)(void ptr, void *arg);

	+/*
	+ * 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
	+
	+enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
	+
	+/*
	+ * Fetch a node pointer from a slot.
	+ */
	+static __inline struct pctrie_node *
	+pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
	+{
	+ switch (access) {
	+ case PCTRIE_UNSERIALIZED:
	+ return (smr_unserialized_load(p, true));
	+ case PCTRIE_LOCKED:
	+ return (smr_serialized_load(p, true));
	+ case PCTRIE_SMR:
	+ return (smr_entered_load(p, smr));
	+ }
	+ __assert_unreachable();
	+}
	+
	+static __inline void
	+pctrie_node_store(smr_pctnode_t p, void v, enum pctrie_access access)
	+{
	+ switch (access) {
	+ case PCTRIE_UNSERIALIZED:
	+ smr_unserialized_store(p, v, true);
	+ break;
	+ case PCTRIE_LOCKED:
	+ smr_serialized_store(p, v, true);
	+ break;
	+ case PCTRIE_SMR:
	+ panic("%s: Not supported in SMR section.", __func__);
	+ break;
	+ default:
	+ __assert_unreachable();
	+ break;
	+ }
	+}
	+
	+/*
	+ * Returns val with leaf bit set.
	+ */
	+static __inline void *
	+pctrie_toleaf(uint64_t *val)
	+{
	+ return ((void *)((uintptr_t)val \| PCTRIE_ISLEAF));
	+}
	+
	+#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
	+ PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, \
	+ PCTRIE_UNSERIALIZED)
	+
	#define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \
	- PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
	+ PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, \
	+ PCTRIE_LOCKED) \
	\
	static __inline struct type * \
	name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
	@@ -47,7 +112,7 @@
	\
	return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \
	key, (smr))); \
	-} \
	+}

	#ifdef INVARIANTS
	void pctrie_subtree_lookup_gt_assert(struct pctrie_node *node,
	@@ -59,14 +124,14 @@
	#define pctrie_subtree_lookup_lt_assert(node, key, ptree, res)
	#endif

	-#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
	+#define PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, access) \
	\
	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); \
	+CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t)-1)) == 0); \
	\
	static __inline struct type * \
	name##_PCTRIE_VAL2PTR(uint64_t *val) \
	@@ -86,34 +151,38 @@
	} \
	\
	static __inline __unused int \
	-name##_PCTRIE_INSERT_BASE(struct pctrie ptree, void parentp, \
	+name##_PCTRIE_INSERT_BASE(struct pctrie ptree, smr_pctnode_t parentp, \
	uint64_t val, uint64_t found, struct type **found_out) \
	{ \
	- struct pctrie_node *parent; \
	+ struct pctrie_node child, node; \
	\
	if (__predict_false(found != NULL)) { \
	*found_out = name##_PCTRIE_VAL2PTR(found); \
	return (EEXIST); \
	} \
	- if (parentp != NULL) { \
	- parent = allocfn(ptree); \
	- if (__predict_false(parent == NULL)) { \
	+ node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); \
	+ if (node != PCTRIE_NULL) { \
	+ child = allocfn(ptree); \
	+ if (__predict_false(child == NULL)) { \
	if (found_out != NULL) \
	*found_out = NULL; \
	return (ENOMEM); \
	} \
	- pctrie_insert_node(parentp, parent, val); \
	- } \
	+ pctrie_insert_node(parentp, node, child, val); \
	+ } else \
	+ child = pctrie_toleaf(val); \
	+ /* Synchronize to make changes visible. */ \
	+ pctrie_node_store(parentp, child, access); \
	return (0); \
	} \
	\
	static __inline __unused int \
	name##_PCTRIE_INSERT(struct pctrie ptree, struct type ptr) \
	{ \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	\
	- parentp = pctrie_insert_lookup_strict(ptree, val); \
	+ parentp = pctrie_insert_lookup_strict(ptree, *val); \
	return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
	NULL, NULL)); \
	} \
	@@ -122,11 +191,11 @@
	name##_PCTRIE_FIND_OR_INSERT(struct pctrie ptree, struct type ptr, \
	struct type **found_out_opt) \
	{ \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	uint64_t *found; \
	\
	- parentp = pctrie_insert_lookup(ptree, val, &found); \
	+ parentp = pctrie_insert_lookup(ptree, *val, &found); \
	return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
	found, found_out_opt)); \
	} \
	@@ -136,12 +205,12 @@
	struct type **found_out) \
	{ \
	struct pctrie_node *neighbor; \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	uint64_t *found; \
	int retval; \
	\
	- parentp = pctrie_insert_lookup_gt(ptree, val, &found, \
	+ parentp = pctrie_insert_lookup_gt(ptree, *val, &found, \
	&neighbor); \
	retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
	found, found_out); \
	@@ -158,12 +227,12 @@
	struct type **found_out) \
	{ \
	struct pctrie_node *neighbor; \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	uint64_t *found; \
	int retval; \
	\
	- parentp = pctrie_insert_lookup_lt(ptree, val, &found, \
	+ parentp = pctrie_insert_lookup_lt(ptree, *val, &found, \
	&neighbor); \
	retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
	found, found_out); \
	@@ -229,18 +298,22 @@
	static __inline __unused int \
	name##_PCTRIE_ITER_INSERT(struct pctrie_iter it, struct type ptr) \
	{ \
	- struct pctrie_node *parent; \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	+ struct pctrie_node *node; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	+ int retval; \
	\
	- parentp = pctrie_iter_insert_lookup(it, val); \
	- if (parentp == NULL) \
	- return (0); \
	- parent = allocfn(it->ptree); \
	- if (__predict_false(parent == NULL)) \
	- return (ENOMEM); \
	- pctrie_insert_node(parentp, parent, val); \
	- it->path[it->top++] = parent; \
	+ parentp = pctrie_iter_insert_lookup(it, *val); \
	+ node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); \
	+ retval = name##_PCTRIE_INSERT_BASE(it->ptree, parentp, val, \
	+ NULL, NULL); \
	+ if (retval != 0) \
	+ return (retval); \
	+ if (node != PCTRIE_NULL) { \
	+ node = pctrie_node_load(parentp, NULL, \
	+ PCTRIE_UNSERIALIZED); \
	+ it->path[it->top++] = node; \
	+ } \
	return (0); \
	} \
	\
	@@ -312,8 +385,17 @@
	\
	static __inline __unused void \
	name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree, \
	- struct pctrie_node *freenode) \
	+ smr_pctnode_t parentp, struct pctrie_node child) \
	{ \
	+ struct pctrie_node *freenode; \
	+ \
	+ if (child != PCTRIE_NULL) { \
	+ freenode = pctrie_node_load(parentp, NULL, \
	+ PCTRIE_UNSERIALIZED); \
	+ } else \
	+ freenode = NULL; \
	+ /* Synchronize to make changes visible. */ \
	+ pctrie_node_store(parentp, child, access); \
	if (freenode != NULL) \
	freefn(ptree, freenode); \
	} \
	@@ -322,56 +404,68 @@
	name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
	{ \
	uint64_t *val; \
	- struct pctrie_node *freenode; \
	+ smr_pctnode_t *parentp; \
	+ struct pctrie_node *child; \
	\
	- val = pctrie_iter_remove(it, &freenode); \
	+ val = pctrie_iter_remove(it, &parentp, &child); \
	if (val == NULL) \
	panic("%s: key not found", __func__); \
	- name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
	+ name##_PCTRIE_REMOVE_BASE(it->ptree, parentp, child); \
	} \
	\
	static __inline __unused struct type * \
	name##_PCTRIE_REPLACE(struct pctrie ptree, struct type ptr) \
	{ \
	- \
	- return name##_PCTRIE_VAL2PTR( \
	- pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
	+ smr_pctnode_t *parentp; \
	+ struct type *res; \
	+ struct pctrie_node *child; \
	+ \
	+ res = name##_PCTRIE_VAL2PTR( \
	+ pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr), \
	+ &parentp, &child)); \
	+ /* Synchronize to make changes visible. */ \
	+ pctrie_node_store(parentp, child, access); \
	+ return (res); \
	} \
	\
	static __inline __unused void \
	name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
	{ \
	uint64_t *val; \
	- struct pctrie_node *freenode; \
	+ smr_pctnode_t *parentp; \
	+ struct pctrie_node *child; \
	\
	- val = pctrie_remove_lookup(ptree, key, &freenode); \
	+ val = pctrie_remove_lookup(ptree, key, &parentp, &child); \
	if (val == NULL) \
	panic("%s: key not found", __func__); \
	- name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
	+ name##_PCTRIE_REMOVE_BASE(ptree, parentp, child); \
	} \
	\
	static __inline __unused struct type * \
	name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
	{ \
	uint64_t *val; \
	- struct pctrie_node *freenode; \
	+ smr_pctnode_t *parentp; \
	+ struct pctrie_node *child; \
	\
	- val = pctrie_remove_lookup(ptree, key, &freenode); \
	- name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
	- return name##_PCTRIE_VAL2PTR(val); \
	+ val = pctrie_remove_lookup(ptree, key, &parentp, &child); \
	+ if (val != NULL) \
	+ name##_PCTRIE_REMOVE_BASE(ptree, parentp, child); \
	+ return (name##_PCTRIE_VAL2PTR(val)); \
	}

	struct pctrie_iter;
	-void pctrie_insert_lookup(struct pctrie ptree, uint64_t *val,
	+smr_pctnode_t pctrie_insert_lookup(struct pctrie ptree, uint64_t index,
	uint64_t **found_out);
	-void pctrie_insert_lookup_gt(struct pctrie ptree, uint64_t *val,
	+smr_pctnode_t pctrie_insert_lookup_gt(struct pctrie ptree, uint64_t index,
	uint64_t found_out, struct pctrie_node neighbor_out);
	-void pctrie_insert_lookup_lt(struct pctrie ptree, uint64_t *val,
	+smr_pctnode_t pctrie_insert_lookup_lt(struct pctrie ptree, uint64_t index,
	uint64_t found_out, struct pctrie_node neighbor_out);
	-void pctrie_insert_lookup_strict(struct pctrie ptree,
	+smr_pctnode_t pctrie_insert_lookup_strict(struct pctrie ptree,
	+ uint64_t index);
	+void pctrie_insert_node(smr_pctnode_t *parentp,
	+ struct pctrie_node node, struct pctrie_node child,
	uint64_t *val);
	-void pctrie_insert_node(void *parentp,
	- struct pctrie_node parent, uint64_t val);
	uint64_t pctrie_lookup(struct pctrie ptree, uint64_t key);
	uint64_t pctrie_lookup_unlocked(struct pctrie ptree, uint64_t key,
	smr_t smr);
	@@ -379,8 +473,8 @@
	uint64_t pctrie_iter_stride(struct pctrie_iter it, int stride);
	uint64_t pctrie_iter_next(struct pctrie_iter it);
	uint64_t pctrie_iter_prev(struct pctrie_iter it);
	-void pctrie_iter_insert_lookup(struct pctrie_iter it,
	- uint64_t *val);
	+smr_pctnode_t pctrie_iter_insert_lookup(struct pctrie_iter it,
	+ uint64_t index);
	uint64_t pctrie_lookup_ge(struct pctrie ptree, uint64_t key);
	uint64_t pctrie_subtree_lookup_gt(struct pctrie_node node,
	uint64_t key);
	@@ -400,22 +494,15 @@
	struct pctrie_node pctrie_reclaim_resume_cb(struct pctrie_node *pnode,
	pctrie_cb_t callback, int keyoff, void *arg);
	uint64_t pctrie_remove_lookup(struct pctrie ptree, uint64_t index,
	- struct pctrie_node **killnode);
	+ smr_pctnode_t parentp, struct pctrie_node child);
	uint64_t pctrie_iter_remove(struct pctrie_iter it,
	- struct pctrie_node **freenode);
	+ smr_pctnode_t parentp, struct pctrie_node child);
	uint64_t pctrie_iter_value(struct pctrie_iter it);
	-uint64_t pctrie_replace(struct pctrie ptree, uint64_t *newval);
	+uint64_t pctrie_replace(struct pctrie ptree, uint64_t *newval,
	+ smr_pctnode_t parentp, struct pctrie_node child);
	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)
	{

File Metadata

Mime Type: text/plain
Expires: Tue, Jan 14, 8:09 PM (7 h, 24 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 15800506
Default Alt Text: D46895.diff (31 KB)

D46895.diffNo OneTemporaryActions

D46895.diffView Options

File Metadata

Event Timeline

D46895.diff
No OneTemporary
Actions

D46895.diff
View Options