D46895.id144465.diff
No OneTemporary
Actions

Size

17 KB

Referenced Files

None

Subscribers

None

D46895.id144465.diff
View Options

	Index: sys/kern/subr_pctrie.c
	===================================================================
	--- sys/kern/subr_pctrie.c
	+++ sys/kern/subr_pctrie.c
	@@ -149,22 +149,12 @@
	}

	static __inline void
	-pctrie_node_store(smr_pctnode_t p, void v, enum pctrie_access access)
	+pctrie_node_store(smr_pctnode_t p, void v, bool locked)
	{
	- switch (access) {
	- case PCTRIE_UNSERIALIZED:
	- smr_unserialized_store(p, v, true);
	- break;
	- case PCTRIE_LOCKED:
	+ if (locked)
	smr_serialized_store(p, v, true);
	- break;
	- case PCTRIE_SMR:
	- panic("%s: Not supported in SMR section.", __func__);
	- break;
	- default:
	- __assert_unreachable();
	- break;
	- }
	+ else
	+ smr_unserialized_store(p, v, true);
	}

	/*
	@@ -181,9 +171,9 @@
	*/
	static __inline void
	pctrie_root_store(struct pctrie ptree, struct pctrie_node node,
	- enum pctrie_access access)
	+ bool locked)
	{
	- pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access);
	+ pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, locked);
	}

	/*
	@@ -227,12 +217,12 @@
	*/
	static __inline void
	pctrie_addnode(struct pctrie_node *node, uint64_t index,
	- struct pctrie_node *child, enum pctrie_access access)
	+ struct pctrie_node *child, bool locked)
	{
	int slot;

	slot = pctrie_slot(node, index);
	- pctrie_node_store(&node->pn_child[slot], child, access);
	+ pctrie_node_store(&node->pn_child[slot], child, locked);
	node->pn_popmap ^= 1 << slot;
	KASSERT((node->pn_popmap & (1 << slot)) != 0,
	("%s: bad popmap slot %d in node %p", __func__, slot, node));
	@@ -249,8 +239,7 @@
	node = mem;
	node->pn_popmap = 0;
	for (int i = 0; i < nitems(node->pn_child); i++)
	- pctrie_node_store(&node->pn_child[i], PCTRIE_NULL,
	- PCTRIE_UNSERIALIZED);
	+ pctrie_node_store(&node->pn_child[i], PCTRIE_NULL, false);
	return (0);
	}

	@@ -286,7 +275,7 @@
	static __always_inline void *
	pctrie_insert_lookup_compound(struct pctrie ptree, uint64_t val,
	uint64_t found_out, struct pctrie_node neighbor_out,
	- enum pctrie_insert_neighbor_mode mode)
	+ enum pctrie_insert_neighbor_mode mode, bool hassmr)
	{
	uint64_t index;
	struct pctrie_node node, parent;
	@@ -305,10 +294,10 @@
	if (node == PCTRIE_NULL) {
	if (parent == NULL)
	pctrie_root_store(ptree,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	+ pctrie_toleaf(val), hassmr);
	else
	pctrie_addnode(parent, index,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	+ pctrie_toleaf(val), hassmr);
	return (NULL);
	}
	if (*pctrie_toval(node) == index) {
	@@ -363,14 +352,14 @@
	* if the key already exists, and do not look for neighboring entries.
	*/
	void *
	-pctrie_insert_lookup_strict(struct pctrie ptree, uint64_t val)
	+pctrie_insert_lookup_strict(struct pctrie ptree, uint64_t val, bool hassmr)
	{
	void *parentp;
	uint64_t *found;

	found = NULL;
	parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL,
	- PCTRIE_INSERT_NEIGHBOR_NONE);
	+ PCTRIE_INSERT_NEIGHBOR_NONE, hassmr);
	if (__predict_false(found != NULL))
	panic("%s: key %jx is already present", __func__,
	(uintmax_t)*val);
	@@ -383,11 +372,11 @@
	*/
	void *
	pctrie_insert_lookup(struct pctrie ptree, uint64_t val,
	- uint64_t **found_out)
	+ uint64_t **found_out, bool hassmr)
	{
	*found_out = NULL;
	return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
	- PCTRIE_INSERT_NEIGHBOR_NONE));
	+ PCTRIE_INSERT_NEIGHBOR_NONE, hassmr));
	}

	/*
	@@ -397,12 +386,12 @@
	*/
	void *
	pctrie_insert_lookup_gt(struct pctrie ptree, uint64_t val,
	- uint64_t found_out, struct pctrie_node neighbor_out)
	+ uint64_t found_out, struct pctrie_node neighbor_out, bool hassmr)
	{
	*found_out = NULL;
	*neighbor_out = NULL;
	return (pctrie_insert_lookup_compound(ptree, val, found_out,
	- neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
	+ neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT, hassmr));
	}

	/*
	@@ -412,19 +401,20 @@
	*/
	void *
	pctrie_insert_lookup_lt(struct pctrie ptree, uint64_t val,
	- uint64_t found_out, struct pctrie_node neighbor_out)
	+ uint64_t found_out, struct pctrie_node neighbor_out, bool hassmr)
	{
	*found_out = NULL;
	*neighbor_out = NULL;
	return (pctrie_insert_lookup_compound(ptree, val, found_out,
	- neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
	+ neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT, hassmr));
	}

	/*
	* Uses new node to insert key-value pair into the trie at given location.
	*/
	void
	-pctrie_insert_node(void parentp, struct pctrie_node parent, uint64_t *val)
	+pctrie_insert_node(void parentp, struct pctrie_node parent, uint64_t *val,
	+ bool hassmr)
	{
	struct pctrie_node *node;
	uint64_t index, newind;
	@@ -437,7 +427,7 @@
	*/
	if (parent->pn_popmap != 0) {
	pctrie_node_store(&parent->pn_child[ffs(parent->pn_popmap) - 1],
	- PCTRIE_NULL, PCTRIE_UNSERIALIZED);
	+ PCTRIE_NULL, false);
	parent->pn_popmap = 0;
	}

	@@ -465,10 +455,10 @@


	/* 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);
	+ pctrie_addnode(parent, index, pctrie_toleaf(val), false);
	+ pctrie_addnode(parent, newind, node, false);
	/* Synchronize to make the above visible. */
	- pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
	+ pctrie_node_store(parentp, parent, hassmr);
	}

	/*
	@@ -600,7 +590,7 @@
	* Assumes access is externally synchronized by a lock.
	*/
	void *
	-pctrie_iter_insert_lookup(struct pctrie_iter it, uint64_t val)
	+pctrie_iter_insert_lookup(struct pctrie_iter it, uint64_t val, bool hassmr)
	{
	struct pctrie_node *node;

	@@ -609,10 +599,10 @@
	if (node == PCTRIE_NULL) {
	if (it->top == 0)
	pctrie_root_store(it->ptree,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	+ pctrie_toleaf(val), hassmr);
	else
	pctrie_addnode(it->path[it->top - 1], it->index,
	- pctrie_toleaf(val), PCTRIE_LOCKED);
	+ pctrie_toleaf(val), hassmr);
	return (NULL);
	}
	if (__predict_false(pctrie_match_value(node, it->index) != NULL))
	@@ -1035,13 +1025,13 @@

	static void
	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 *freenode, bool hassmr)
	{
	struct pctrie_node *child;
	int slot;

	if (node == NULL) {
	- pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_LOCKED);
	+ pctrie_root_store(ptree, PCTRIE_NULL, hassmr);
	return;
	}
	slot = pctrie_slot(node, index);
	@@ -1049,7 +1039,7 @@
	("%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);
	+ pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, hassmr);
	if (!powerof2(node->pn_popmap))
	return;
	KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__));
	@@ -1058,14 +1048,13 @@
	KASSERT(child != PCTRIE_NULL,
	("%s: bad popmap slot %d in node %p", __func__, slot, node));
	if (parent == NULL)
	- pctrie_root_store(ptree, child, PCTRIE_LOCKED);
	+ pctrie_root_store(ptree, child, hassmr);
	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);
	+ pctrie_node_store(&parent->pn_child[slot], child, hassmr);
	}
	/*
	* The child is still valid and we can not zero the
	@@ -1081,7 +1070,7 @@
	*/
	uint64_t *
	pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
	- struct pctrie_node **freenode)
	+ struct pctrie_node **freenode, bool hassmr)
	{
	struct pctrie_node child, node, *parent;
	uint64_t *m;
	@@ -1099,7 +1088,7 @@
	}
	m = pctrie_match_value(child, index);
	if (m != NULL)
	- pctrie_remove(ptree, index, parent, node, freenode);
	+ pctrie_remove(ptree, index, parent, node, freenode, hassmr);
	return (m);
	}

	@@ -1108,7 +1097,8 @@
	* 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, struct pctrie_node *freenode,
	+ bool hassmr)
	{
	struct pctrie_node child, node, *parent;
	uint64_t *m;
	@@ -1128,7 +1118,8 @@
	}
	m = pctrie_match_value(child, it->index);
	if (m != NULL)
	- pctrie_remove(it->ptree, it->index, parent, node, freenode);
	+ pctrie_remove(it->ptree, it->index, parent, node, freenode,
	+ hassmr);
	if (*freenode != NULL)
	--it->top;
	return (m);
	@@ -1175,16 +1166,14 @@
	node->pn_popmap ^= 1 << slot;
	child = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_UNSERIALIZED);
	- pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL,
	- PCTRIE_UNSERIALIZED);
	+ pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, false);
	if (pctrie_isleaf(child)) {
	if (callback != NULL)
	callback(pctrie_toptr(child, keyoff), arg);
	continue;
	}
	/* Climb one level down the trie. */
	- pctrie_node_store(&node->pn_child[0], parent,
	- PCTRIE_UNSERIALIZED);
	+ pctrie_node_store(&node->pn_child[0], parent, false);
	parent = node;
	node = child;
	}
	@@ -1207,7 +1196,7 @@
	/* Climb one level up the trie. */
	parent = pctrie_node_load(&node->pn_child[0], NULL,
	PCTRIE_UNSERIALIZED);
	- pctrie_node_store(&node->pn_child[0], PCTRIE_NULL, PCTRIE_UNSERIALIZED);
	+ pctrie_node_store(&node->pn_child[0], PCTRIE_NULL, false);
	return (pctrie_reclaim_prune(pnode, parent, callback, keyoff, arg));
	}

	@@ -1222,7 +1211,7 @@
	struct pctrie_node *node;

	node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED);
	- pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_UNSERIALIZED);
	+ pctrie_root_store(ptree, PCTRIE_NULL, false);
	if (pctrie_isleaf(node)) {
	if (callback != NULL && node != PCTRIE_NULL)
	callback(pctrie_toptr(node, keyoff), arg);
	@@ -1264,7 +1253,7 @@
	* 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, bool hassmr)
	{
	struct pctrie_node leaf, parent, *node;
	uint64_t *m;
	@@ -1280,11 +1269,11 @@
	if ((m = pctrie_toval(node)) != NULL && *m == index) {
	if (parent == NULL)
	pctrie_root_store(ptree,
	- leaf, PCTRIE_LOCKED);
	+ leaf, hassmr);
	else
	pctrie_node_store(
	&parent->pn_child[slot], leaf,
	- PCTRIE_LOCKED);
	+ hassmr);
	return (m);
	}
	break;
	Index: sys/sys/pctrie.h
	===================================================================
	--- sys/sys/pctrie.h
	+++ sys/sys/pctrie.h
	@@ -38,8 +38,11 @@

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

	+#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
	+ PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, false) \
	+
	#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, true) \
	\
	static __inline struct type * \
	name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
	@@ -59,7 +62,7 @@
	#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, hassmr)\
	\
	CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \
	/* \
	@@ -92,13 +95,13 @@
	void *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	\
	- parentp = pctrie_insert_lookup_strict(ptree, val); \
	+ parentp = pctrie_insert_lookup_strict(ptree, val, hassmr); \
	if (parentp == NULL) \
	return (0); \
	parent = allocfn(ptree); \
	if (__predict_false(parent == NULL)) \
	return (ENOMEM); \
	- pctrie_insert_node(parentp, parent, val); \
	+ pctrie_insert_node(parentp, parent, val, hassmr); \
	return (0); \
	} \
	\
	@@ -111,7 +114,7 @@
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	uint64_t *found; \
	\
	- parentp = pctrie_insert_lookup(ptree, val, &found); \
	+ parentp = pctrie_insert_lookup(ptree, val, &found, hassmr); \
	if (found != NULL) { \
	if (found_out_opt != NULL) \
	*found_out_opt = name##_PCTRIE_VAL2PTR(found); \
	@@ -122,7 +125,7 @@
	parent = allocfn(ptree); \
	if (__predict_false(parent == NULL)) \
	return (ENOMEM); \
	- pctrie_insert_node(parentp, parent, val); \
	+ pctrie_insert_node(parentp, parent, val, hassmr); \
	return (0); \
	} \
	\
	@@ -136,7 +139,7 @@
	uint64_t *found; \
	\
	parentp = pctrie_insert_lookup_gt(ptree, val, &found, \
	- &neighbor); \
	+ &neighbor, hassmr); \
	if (__predict_false(found != NULL)) { \
	*found_out = name##_PCTRIE_VAL2PTR(found); \
	return (EEXIST); \
	@@ -149,7 +152,7 @@
	} \
	if (neighbor == parentp) \
	neighbor = parent; \
	- pctrie_insert_node(parentp, parent, val); \
	+ pctrie_insert_node(parentp, parent, val, hassmr); \
	} \
	found = pctrie_subtree_lookup_gt(neighbor, *val); \
	*found_out = name##_PCTRIE_VAL2PTR(found); \
	@@ -167,7 +170,7 @@
	uint64_t *found; \
	\
	parentp = pctrie_insert_lookup_lt(ptree, val, &found, \
	- &neighbor); \
	+ &neighbor, hassmr); \
	if (__predict_false(found != NULL)) { \
	*found_out = name##_PCTRIE_VAL2PTR(found); \
	return (EEXIST); \
	@@ -180,7 +183,7 @@
	} \
	if (neighbor == parentp) \
	neighbor = parent; \
	- pctrie_insert_node(parentp, parent, val); \
	+ pctrie_insert_node(parentp, parent, val, hassmr); \
	} \
	found = pctrie_subtree_lookup_lt(neighbor, *val); \
	*found_out = name##_PCTRIE_VAL2PTR(found); \
	@@ -246,13 +249,13 @@
	void *parentp; \
	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
	\
	- parentp = pctrie_iter_insert_lookup(it, val); \
	+ parentp = pctrie_iter_insert_lookup(it, val, hassmr); \
	if (parentp == NULL) \
	return (0); \
	parent = allocfn(it->ptree); \
	if (__predict_false(parent == NULL)) \
	return (ENOMEM); \
	- pctrie_insert_node(parentp, parent, val); \
	+ pctrie_insert_node(parentp, parent, val, hassmr); \
	it->path[it->top++] = parent; \
	return (0); \
	} \
	@@ -329,7 +332,7 @@
	uint64_t *val; \
	struct pctrie_node *freenode; \
	\
	- val = pctrie_iter_remove(it, &freenode); \
	+ val = pctrie_iter_remove(it, &freenode, hassmr); \
	if (val == NULL) \
	panic("%s: key not found", __func__); \
	if (freenode != NULL) \
	@@ -341,7 +344,7 @@
	{ \
	\
	return name##_PCTRIE_VAL2PTR( \
	- pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
	+ pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr), hassmr)); \
	} \
	\
	static __inline __unused void \
	@@ -350,7 +353,7 @@
	uint64_t *val; \
	struct pctrie_node *freenode; \
	\
	- val = pctrie_remove_lookup(ptree, key, &freenode); \
	+ val = pctrie_remove_lookup(ptree, key, &freenode, hassmr); \
	if (val == NULL) \
	panic("%s: key not found", __func__); \
	if (freenode != NULL) \
	@@ -363,7 +366,7 @@
	uint64_t *val; \
	struct pctrie_node *freenode; \
	\
	- val = pctrie_remove_lookup(ptree, key, &freenode); \
	+ val = pctrie_remove_lookup(ptree, key, &freenode, hassmr); \
	if (freenode != NULL) \
	freefn(ptree, freenode); \
	return name##_PCTRIE_VAL2PTR(val); \
	@@ -371,15 +374,17 @@

	struct pctrie_iter;
	void pctrie_insert_lookup(struct pctrie ptree, uint64_t *val,
	- uint64_t **found_out);
	+ uint64_t **found_out, bool hassmr);
	void pctrie_insert_lookup_gt(struct pctrie ptree, uint64_t *val,
	- uint64_t found_out, struct pctrie_node neighbor_out);
	+ uint64_t found_out, struct pctrie_node neighbor_out,
	+ bool hassmr);
	void pctrie_insert_lookup_lt(struct pctrie ptree, uint64_t *val,
	- uint64_t found_out, struct pctrie_node neighbor_out);
	+ uint64_t found_out, struct pctrie_node neighbor_out,
	+ bool hassmr);
	void pctrie_insert_lookup_strict(struct pctrie ptree,
	- uint64_t *val);
	-void pctrie_insert_node(void *parentp,
	- struct pctrie_node parent, uint64_t val);
	+ uint64_t *val, bool hassmr);
	+void pctrie_insert_node(void parentp, struct pctrie_node parent,
	+ uint64_t *val, bool hassmr);
	uint64_t pctrie_lookup(struct pctrie ptree, uint64_t key);
	uint64_t pctrie_lookup_unlocked(struct pctrie ptree, uint64_t key,
	smr_t smr);
	@@ -388,7 +393,7 @@
	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);
	+ uint64_t *val, bool hassmr);
	uint64_t pctrie_lookup_ge(struct pctrie ptree, uint64_t key);
	uint64_t pctrie_subtree_lookup_gt(struct pctrie_node node,
	uint64_t key);
	@@ -408,11 +413,12 @@
	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);
	+ struct pctrie_node **killnode, bool hassmr);
	uint64_t pctrie_iter_remove(struct pctrie_iter it,
	- struct pctrie_node **freenode);
	+ struct pctrie_node **freenode, bool hasssmr);
	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,
	+ bool hasssmr);
	size_t pctrie_node_size(void);
	int pctrie_zone_init(void *mem, int size, int flags);

File Metadata

Mime Type: text/plain
Expires: Thu, May 1, 5:24 AM (19 h, 34 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 17873683
Default Alt Text: D46895.id144465.diff (17 KB)

D46895.id144465.diffNo OneTemporaryActions

D46895.id144465.diffView Options

File Metadata

Event Timeline

D46895.id144465.diff
No OneTemporary
Actions

D46895.id144465.diff
View Options