D46895.id151008.diff
No OneTemporary
Actions

Size

26 KB

Referenced Files

None

Subscribers

None

D46895.id151008.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. */
	@@ -108,44 +102,6 @@
	return (false);
	}

	-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.
	*/
	@@ -167,6 +123,12 @@
	/*
	* Get the child of a node.
	*/
	+static __inline smr_pctnode_t *
	+pctrie_child_slot(struct pctrie ptree, struct pctrie_node node, int slot)
	+{
	+ return (node == NULL ? pctrie_root(ptree) : &node->pn_child[slot]);
	+}
	+
	static __inline smr_pctnode_t *
	pctrie_child(struct pctrie ptree, struct pctrie_node node, uint64_t index)
	{
	@@ -183,15 +145,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.
	*/
	@@ -227,21 +180,29 @@
	{
	return (pctrie_node_load(&node->pn_parent, NULL, PCTRIE_UNSERIALIZED));
	}
	+/*
	+ * 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);
	}

	/*
	@@ -268,22 +229,22 @@
	}

	/*
	- * Look for where to insert the key-value pair into the trie. Complete the
	- * insertion if it replaces a null leaf. Return the insertion location if the
	- * insertion needs to be completed by the caller; otherwise return NULL.
	+ * Look for where to insert the key-value pair into the trie. Return the
	+ * insertion location so that the insertion can be completed by the caller;
	+ * otherwise return NULL.
	*
	* If the key is already present in the trie, populate *found_out as if by
	* pctrie_lookup().
	*/
	-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,
	struct pctrie_node parent_out, uint64_t found_out)
	{
	- uint64_t index;
	struct pctrie_node node, parent;
	int slot;

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

	/*
	* The owner of record for root is not really important because it
	@@ -291,58 +252,46 @@
	*/
	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	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);
	- *parent_out = parent;
	- return (NULL);
	- }
	+ while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
	+ parent = node;
	+ node = pctrie_node_load(&node->pn_child[slot], NULL,
	+ PCTRIE_LOCKED);
	+ }
	+ if (pctrie_isleaf(node)) {
	+ if (node != PCTRIE_NULL) {
	if (*pctrie_toval(node) == index) {
	*found_out = pctrie_toval(node);
	- *parent_out = parent;
	return (NULL);
	}
	- break;
	- }
	- if (pctrie_keybarr(node, index, &slot))
	- break;
	- parent = node;
	- node = pctrie_node_load(&node->pn_child[slot], NULL,
	- PCTRIE_LOCKED);
	+ } 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 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.
	*/
	*parent_out = parent;
	- return ((parent == NULL) ? pctrie_root(ptree): &parent->pn_child[slot]);
	+ return (pctrie_child_slot(ptree, parent, slot));
	}

	/*
	* 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,
	struct pctrie_node **parent_out)
	{
	- void *parentp;
	+ smr_pctnode_t *parentp;
	uint64_t *found;

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

	@@ -350,12 +299,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,
	struct pctrie_node parent_out, uint64_t found_out)
	{
	- *found_out = NULL;
	- return (pctrie_insert_lookup_compound(ptree, val, parent_out,
	+ return (pctrie_insert_lookup_compound(ptree, index, parent_out,
	found_out));
	}

	@@ -365,10 +313,9 @@
	* was at 'parentp' to begin with.
	*/
	void
	-pctrie_insert_node(uint64_t val, struct pctrie_node parent, void *parentp,
	- struct pctrie_node *child)
	+pctrie_insert_node(uint64_t val, struct pctrie_node parent,
	+ struct pctrie_node node, struct pctrie_node child)
	{
	- struct pctrie_node *node;
	uint64_t index, newind;

	/*
	@@ -389,7 +336,6 @@
	* which must be first in the node.
	*/
	index = *val;
	- node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED);
	pctrie_setparent(child, parent);
	if (!pctrie_isleaf(node))
	pctrie_setparent(node, child);
	@@ -410,10 +356,8 @@


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

	/*
	@@ -548,31 +492,25 @@
	* 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;

	- it->index = *val;
	- node = _pctrie_lookup_node(it->ptree, it->node, *val, &it->node,
	+ it->index = index;
	+ node = _pctrie_lookup_node(it->ptree, it->node, index, &it->node,
	NULL, PCTRIE_LOCKED);
	- if (node == PCTRIE_NULL) {
	- if (it->node == NULL)
	- pctrie_node_store(pctrie_root(it->ptree),
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	- else
	- pctrie_addnode(it->node, it->index,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	- return (NULL);
	- }
	- 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 (it->node != NULL)
	+ pctrie_setpop(it->node, pctrie_slot(it->node, index));

	/*
	- * '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.
	*/
	return (pctrie_child(it->ptree, it->node, it->index));
	}
	@@ -826,47 +764,38 @@
	}

	/*
	- * If 'child', a leaf and a child of 'parent', is not NULL and has key 'index',
	- * then remove it from the pctrie and return its value. If doing so produces an
	- * internal node with only one child, purge it from the pctrie and save it in
	- * *freenode for later disposal.
	+ * Use 'index' to identify a to-be-removed child of 'node' and return the
	+ * address of the pointer to that child; set 'child' to the value that will
	+ * stored at that address to complete the removal. If 'child' is an internal
	+ * node, reset its parent pointer.
	*/
	-static uint64_t *
	+static smr_pctnode_t *
	pctrie_remove(struct pctrie ptree, struct pctrie_node node, uint64_t index,
	- struct pctrie_node child, struct pctrie_node *freenode)
	+ struct pctrie_node **child)
	{
	- uint64_t *m;
	int slot;

	- *freenode = NULL;
	- m = pctrie_match_value(child, index);
	- if (m == NULL)
	- return (m);
	- if (node == NULL) {
	- pctrie_node_store(pctrie_root(ptree),
	- PCTRIE_NULL, PCTRIE_LOCKED);
	- return (m);
	- }
	+ *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 (m);
	+ 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));
	- *freenode = node;
	node = pctrie_parent(node);
	- if (!pctrie_isleaf(child))
	- pctrie_setparent(child, node);
	- pctrie_node_store(pctrie_child(ptree, node, index), child,
	- PCTRIE_LOCKED);
	- return (m);
	+ if (!pctrie_isleaf(*child))
	+ pctrie_setparent(*child, node);
	+ return (pctrie_child(ptree, node, index));
	}

	/*
	@@ -875,38 +804,40 @@
	*/
	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;
	+ struct pctrie_node next, node;
	+ uint64_t *m;
	int slot;

	node = NULL;
	- child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- while (!pctrie_isleaf(child)) {
	- node = child;
	+ next = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	+ while (!pctrie_isleaf(next)) {
	+ 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);
	}
	- return (pctrie_remove(ptree, node, index, child, freenode));
	+ if ((m = pctrie_match_value(next, index)) != NULL)
	+ *parentp = pctrie_remove(ptree, node, index, child);
	+ return (m);
	}

	/*
	* Remove from the trie the leaf last chosen by the iterator, and
	* 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)
	+smr_pctnode_t *
	+pctrie_iter_remove(struct pctrie_iter it, struct pctrie_node *child)
	{
	- struct pctrie_node *child;
	- uint64_t *m;
	-
	- child = pctrie_node_load(pctrie_child(it->ptree, it->node, it->index),
	- NULL, PCTRIE_LOCKED);
	- m = pctrie_remove(it->ptree, it->node, it->index, child, freenode);
	- if (*freenode != NULL)
	+ KASSERT(NULL != pctrie_match_value(pctrie_node_load(pctrie_child(
	+ it->ptree, it->node, it->index), NULL, PCTRIE_LOCKED), it->index),
	+ ("%s: removing value %lx not at iter", __func__, it->index));
	+ smr_pctnode_t *parentp =
	+ pctrie_remove(it->ptree, it->node, it->index, child);
	+ if (*child != PCTRIE_NULL)
	it->node = pctrie_parent(it->node);
	- return (m);
	+ return (parentp);
	}

	/*
	@@ -1023,37 +954,29 @@
	* 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);
	- return (m);
	- }
	- break;
	- }
	- if (pctrie_keybarr(node, index, &slot))
	- break;
	+ while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
	parent = node;
	node = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_LOCKED);
	}
	+ if (pctrie_isleaf(node) &&
	+ (m = pctrie_toval(node)) != NULL && *m == index) {
	+ *parentp = pctrie_child_slot(ptree, parent, slot);
	+ return (m);
	+ }
	+
	panic("%s: original replacing value not found", __func__);
	}

	Index: sys/sys/pctrie.h
	===================================================================
	--- sys/sys/pctrie.h
	+++ sys/sys/pctrie.h
	@@ -33,6 +33,11 @@

	#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;

	struct pctrie_iter {
	struct pctrie *ptree;
	@@ -67,8 +72,69 @@

	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) \
	@@ -76,9 +142,9 @@
	\
	return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \
	key, (smr))); \
	-} \
	+}

	-#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)); \
	/* \
	@@ -106,35 +172,39 @@
	\
	static __inline __unused int \
	name##_PCTRIE_INSERT_BASE(struct pctrie ptree, uint64_t val, \
	- struct pctrie_node parent, void parentp, \
	+ struct pctrie_node parent, smr_pctnode_t parentp, \
	uint64_t found, struct type *found_out) \
	{ \
	- struct pctrie_node *child; \
	+ struct pctrie_node child, node; \
	\
	if (__predict_false(found != NULL)) { \
	*found_out = name##_PCTRIE_VAL2PTR(found); \
	return (EEXIST); \
	} \
	- if (parentp != 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(val, parent, parentp, child); \
	- } \
	+ pctrie_insert_node(val, parent, node, child); \
	+ } 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; \
	struct pctrie_node *parent; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	\
	- parentp = pctrie_insert_lookup_strict(ptree, val, &parent); \
	+ parentp = pctrie_insert_lookup_strict(ptree, *val, &parent); \
	return (name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
	NULL, NULL)); \
	} \
	@@ -143,12 +213,12 @@
	name##_PCTRIE_FIND_OR_INSERT(struct pctrie ptree, struct type ptr, \
	struct type **found_out_opt) \
	{ \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	struct pctrie_node *parent; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	uint64_t *found; \
	\
	- parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
	+ parentp = pctrie_insert_lookup(ptree, *val, &parent, &found); \
	return (name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
	found, found_out_opt)); \
	} \
	@@ -158,12 +228,12 @@
	struct type **found_out) \
	{ \
	struct pctrie_node *parent; \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	uint64_t *found; \
	int retval; \
	\
	- parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
	+ parentp = pctrie_insert_lookup(ptree, *val, &parent, &found); \
	retval = name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
	found, found_out); \
	if (retval != 0) \
	@@ -176,10 +246,10 @@
	static __inline __unused int \
	name##_PCTRIE_ITER_INSERT(struct pctrie_iter it, struct type ptr) \
	{ \
	- void *parentp; \
	+ smr_pctnode_t *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	\
	- parentp = pctrie_iter_insert_lookup(it, val); \
	+ parentp = pctrie_iter_insert_lookup(it, *val); \
	return (name##_PCTRIE_INSERT_BASE(it->ptree, val, it->node, \
	parentp, NULL, NULL)); \
	} \
	@@ -303,62 +373,78 @@
	\
	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); \
	} \
	\
	static __inline __unused void \
	-name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
	+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_iter_remove(it, &freenode); \
	+ val = pctrie_remove_lookup(ptree, key, &parentp, &child); \
	if (val == NULL) \
	panic("%s: key not found", __func__); \
	- name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
	+ name##_PCTRIE_REMOVE_BASE(ptree, parentp, child); \
	} \
	\
	static __inline __unused struct type * \
	-name##_PCTRIE_REPLACE(struct pctrie ptree, struct type ptr) \
	+name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
	{ \
	+ uint64_t *val; \
	+ smr_pctnode_t *parentp; \
	+ struct pctrie_node *child; \
	\
	- return name##_PCTRIE_VAL2PTR( \
	- pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
	+ val = pctrie_remove_lookup(ptree, key, &parentp, &child); \
	+ if (val != NULL) \
	+ name##_PCTRIE_REMOVE_BASE(ptree, parentp, child); \
	+ return (name##_PCTRIE_VAL2PTR(val)); \
	} \
	\
	static __inline __unused void \
	-name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
	+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_remove_lookup(ptree, key, &freenode); \
	- if (val == NULL) \
	- panic("%s: key not found", __func__); \
	- name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
	+ parentp = pctrie_iter_remove(it, &child); \
	+ name##_PCTRIE_REMOVE_BASE(it->ptree, parentp, child); \
	} \
	\
	static __inline __unused struct type * \
	-name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
	+name##_PCTRIE_REPLACE(struct pctrie ptree, struct type ptr) \
	{ \
	- uint64_t *val; \
	- struct pctrie_node *freenode; \
	+ smr_pctnode_t *parentp; \
	+ struct type *res; \
	+ struct pctrie_node *child; \
	\
	- val = pctrie_remove_lookup(ptree, key, &freenode); \
	- name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
	- return name##_PCTRIE_VAL2PTR(val); \
	+ 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); \
	}

	-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,
	struct pctrie_node parent_out, uint64_t found_out);
	-void pctrie_insert_lookup_strict(struct pctrie ptree, uint64_t *val,
	- struct pctrie_node **parent_out);
	+smr_pctnode_t pctrie_insert_lookup_strict(struct pctrie ptree,
	+ uint64_t index, struct pctrie_node **parent_out);
	void pctrie_insert_node(uint64_t val, struct pctrie_node parent,
	- void parentp, struct pctrie_node child);
	+ struct pctrie_node node, struct pctrie_node child);
	uint64_t pctrie_lookup(struct pctrie ptree, uint64_t key);
	uint64_t pctrie_lookup_unlocked(struct pctrie ptree, uint64_t key,
	smr_t smr);
	@@ -366,8 +452,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_iter_lookup_ge(struct pctrie_iter it, uint64_t index);
	uint64_t pctrie_iter_jump_ge(struct pctrie_iter it, int64_t jump);
	@@ -385,22 +471,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);
	-uint64_t pctrie_iter_remove(struct pctrie_iter it,
	- struct pctrie_node **freenode);
	+ smr_pctnode_t parentp, struct pctrie_node child);
	+smr_pctnode_t pctrie_iter_remove(struct pctrie_iter it,
	+ 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: Sat, Feb 22, 10:46 AM (46 m, 50 s)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 16769812
Default Alt Text: D46895.id151008.diff (26 KB)

D46895.id151008.diffNo OneTemporaryActions

D46895.id151008.diffView Options

File Metadata

Event Timeline

D46895.id151008.diff
No OneTemporary
Actions

D46895.id151008.diff
View Options