Differential D45394 Diff 139545 sys/kern/subr_pctrie.c

Changeset View

Standalone View

sys/kern/subr_pctrie.c

Show First 20 Lines • Show All 254 Lines • ▼ Show 20 Lines

size_t		size_t
pctrie_node_size(void)		pctrie_node_size(void)
{		{

return (sizeof(struct pctrie_node));		return (sizeof(struct pctrie_node));
}		}

		enum pctrie_insert_neighbor_mode {
		PCTRIE_INSERT_NEIGHBOR_NONE,
		PCTRIE_INSERT_NEIGHBOR_LT,
		PCTRIE_INSERT_NEIGHBOR_GT,
		};

/*		/*
* Looks for where to insert the key-value pair into the trie. Completes the		* Look for where to insert the key-value pair into the trie. Complete the
* insertion if it replaces a null leaf; otherwise, returns insertion location		* insertion if it replaces a null leaf. Return the insertion location if the
* to caller. Panics if the key already exists.		* insertion needs to 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().
		*
		* With mode PCTRIE_INSERT_NEIGHBOR_GT or PCTRIE_INSERT_NEIGHBOR_LT, set
		* *neighbor_out to the lowest level node we encounter during the insert lookup
		* that is a parent of the next greater or lesser entry. The value is not
		* defined if the key was already present in the trie.
		*
		markjUnsubmitted Not Done Inline Actions I'm not sure if it matters anymore, but at one point making `mode` const helped ensure that constant folding would happen during inlining. markj: I'm not sure if it matters anymore, but at one point making `mode` const helped ensure that…
		rlibbyAuthorUnsubmitted Done Inline Actions I did look at output of in-tree clang on amd64 to check that it did the extraneous code removal. If I can remember how to get the cross build set up, I can check gcc too. rlibby: I did look at output of in-tree clang on amd64 to check that it did the extraneous code removal.
		markjUnsubmitted Done Inline Actions To build with gcc, install amd64-gcc13 and `make buildkernel CROSS_TOOLCHAIN=amd64-gcc13`. markj: To build with gcc, install amd64-gcc13 and `make buildkernel CROSS_TOOLCHAIN=amd64-gcc13`.
		rlibbyAuthorUnsubmitted Done Inline Actions Thanks. I checked that gcc13 also removes the extraneous code here. However, over in D45486, the situation is a little different, clang only inlined vm_page_insert_after (which with the patch is now just a wrapper). Marking bool lookup as const didn't change behavior, but marking vm_page_insert_lookup as __always_inline instead of inline did. I'll comment on the other diff. rlibby: Thanks. I checked that gcc13 also removes the extraneous code here. However, over in D45486…
		* 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.
		markjUnsubmitted Done Inline Actions ... or NULL if the slot is already populated. markj: ... or NULL if the slot is already populated.
		rlibbyAuthorUnsubmitted Done Inline Actions I'll add some words to that effect. rlibby: I'll add some words to that effect.
*/		*/
void *		static __always_inline void *
pctrie_insert_lookup(struct pctrie ptree, uint64_t val)		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)
{		{
uint64_t index;		uint64_t index;
struct pctrie_node node, parent;		struct pctrie_node node, parent;
int slot;		int slot;

index = *val;		index = *val;

/*		/*
* The owner of record for root is not really important because it		* The owner of record for root is not really important because it
* will never be used.		* will never be used.
*/		*/
node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);		node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
parent = NULL;		parent = NULL;
for (;;) {		for (;;) {
if (pctrie_isleaf(node)) {		if (pctrie_isleaf(node)) {
if (node == PCTRIE_NULL) {		if (node == PCTRIE_NULL) {
if (parent == NULL)		if (parent == NULL)
ptree->pt_root = pctrie_toleaf(val);		ptree->pt_root = pctrie_toleaf(val);
else		else
pctrie_addnode(parent, index,		pctrie_addnode(parent, index,
pctrie_toleaf(val), PCTRIE_LOCKED);		pctrie_toleaf(val), PCTRIE_LOCKED);
return (NULL);		return (NULL);
}		}
if (*pctrie_toval(node) == index)		if (*pctrie_toval(node) == index) {
panic("%s: key %jx is already present",		*found_out = pctrie_toval(node);
		markjUnsubmitted Done Inline Actions Do you need this NULL check, in light of the lack of such checks for `neighbor_out`? markj: Do you need this NULL check, in light of the lack of such checks for `neighbor_out`?
		rlibbyAuthorUnsubmitted Done Inline Actions I believe you're right that I don't. Will remove. I made the typed out param to name##_PCTRIE_FIND_OR_INSERT optional, but the double pointer to the index is never NULL. rlibby: I believe you're right that I don't. Will remove. I made the //typed// out param to…
__func__, (uintmax_t)index);		return (NULL);
		}
break;		break;
}		}
if (pctrie_keybarr(node, index, &slot))		if (pctrie_keybarr(node, index, &slot))
break;		break;
		/*
		* Descend. If we're tracking the next neighbor and this node
		* contains a neighboring entry in the right direction, record
		* it.
		*/
		if (mode == PCTRIE_INSERT_NEIGHBOR_LT) {
		if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
		*neighbor_out = node;
		} else if (mode == PCTRIE_INSERT_NEIGHBOR_GT) {
		if ((node->pn_popmap >> slot) > 1)
		*neighbor_out = node;
		}
parent = node;		parent = node;
node = pctrie_node_load(&node->pn_child[slot], NULL,		node = pctrie_node_load(&node->pn_child[slot], NULL,
PCTRIE_LOCKED);		PCTRIE_LOCKED);
}		}

/*		/*
		* 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 (mode == PCTRIE_INSERT_NEIGHBOR_LT) {
		if (*pctrie_toval(node) < index)
		*neighbor_out = node;
		} else if (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		* 'node' must be replaced in the tree with a new branch node, with
* children 'node' and 'val'. Return the place that points to 'node'		* children 'node' and 'val'. Return the place that points to 'node'
* now, and will point to to the new branching node later.		* now, and will point to to the new branching node later.
*/		*/
return ((parent != NULL) ? &parent->pn_child[slot]:		return ((parent != NULL) ? &parent->pn_child[slot]:
(smr_pctnode_t *)&ptree->pt_root);		(smr_pctnode_t *)&ptree->pt_root);
}		}

/*		/*
		* 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)
		{
		void *parentp;
		uint64_t *found;

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

		/*
		* 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,
		uint64_t **found_out)
		{
		*found_out = NULL;
		return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
		PCTRIE_INSERT_NEIGHBOR_NONE));
		}

		/*
		* Wrap pctrie_insert_lookup_compound to implement find or insert and find next
		* 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,
		uint64_t found_out, struct pctrie_node neighbor_out)
		{
		*found_out = NULL;
		*neighbor_out = NULL;
		return (pctrie_insert_lookup_compound(ptree, val, found_out,
		neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
		}

		/*
		* Wrap pctrie_insert_lookup_compound to implement find or insert and find next
		* 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,
		uint64_t found_out, struct pctrie_node neighbor_out)
		{
		*found_out = NULL;
		*neighbor_out = NULL;
		return (pctrie_insert_lookup_compound(ptree, val, found_out,
		neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
		}

		/*
* Uses new node to insert key-value pair into the trie at given location.		* Uses new node to insert key-value pair into the trie at given location.
*/		*/
void		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)
{		{
struct pctrie_node *node;		struct pctrie_node *node;
uint64_t index, newind;		uint64_t index, newind;

▲ Show 20 Lines • Show All 94 Lines • ▼ Show 20 Lines
}		}

/*		/*
* Returns the value with the least index that is greater than or equal to the		* Returns the value with the least index that is greater than or equal to the
* specified index, or NULL if there are no such values.		* specified index, or NULL if there are no such values.
*		*
* Requires that access be externally synchronized by a lock.		* Requires that access be externally synchronized by a lock.
*/		*/
uint64_t *		static __inline uint64_t *
pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)		pctrie_lookup_ge_node(struct pctrie_node *node, uint64_t index)
{		{
struct pctrie_node node, succ;		struct pctrie_node *succ;
uint64_t *m;		uint64_t *m;
int slot;		int slot;

/*		/*
* Descend the trie as if performing an ordinary lookup for the		* Descend the trie as if performing an ordinary lookup for the
* specified value. However, unlike an ordinary lookup, as we descend		* specified value. However, unlike an ordinary lookup, as we descend
* the trie, we use "succ" to remember the last branching-off point,		* the trie, we use "succ" to remember the last branching-off point,
* that is, the interior node under which the least value that is both		* that is, the interior node under which the least value that is both
* outside our current path down the trie and greater than the specified		* outside our current path down the trie and greater than the specified
* index resides. (The node's popmap makes it fast and easy to		* index resides. (The node's popmap makes it fast and easy to
* recognize a branching-off point.) If our ordinary lookup fails to		* recognize a branching-off point.) If our ordinary lookup fails to
* yield a value that is greater than or equal to the specified index,		* yield a value that is greater than or equal to the specified index,
* then we will exit this loop and perform a lookup starting from		* then we will exit this loop and perform a lookup starting from
* "succ". If "succ" is not NULL, then that lookup is guaranteed to		* "succ". If "succ" is not NULL, then that lookup is guaranteed to
* succeed.		* succeed.
*/		*/
node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
succ = NULL;		succ = NULL;
for (;;) {		for (;;) {
if (pctrie_isleaf(node)) {		if (pctrie_isleaf(node)) {
if ((m = pctrie_toval(node)) != NULL && *m >= index)		if ((m = pctrie_toval(node)) != NULL && *m >= index)
return (m);		return (m);
break;		break;
}		}
if (pctrie_keybarr(node, index, &slot)) {		if (pctrie_keybarr(node, index, &slot)) {
▲ Show 20 Lines • Show All 46 Lines • ▼ Show 20 Lines	KASSERT(succ->pn_popmap != 0,
("%s: no popmap children in node %p", __func__, succ));		("%s: no popmap children in node %p", __func__, succ));
slot = ffs(succ->pn_popmap) - 1;		slot = ffs(succ->pn_popmap) - 1;
succ = pctrie_node_load(&succ->pn_child[slot], NULL,		succ = pctrie_node_load(&succ->pn_child[slot], NULL,
PCTRIE_LOCKED);		PCTRIE_LOCKED);
}		}
return (pctrie_toval(succ));		return (pctrie_toval(succ));
}		}

		uint64_t *
		pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
		{
		return (pctrie_lookup_ge_node(
		pctrie_root_load(ptree, NULL, PCTRIE_LOCKED), index));
		}

		uint64_t *
		pctrie_subtree_lookup_gt(struct pctrie_node *node, uint64_t index)
		{
		if (node == NULL \|\| index + 1 == 0)
		return (NULL);
		return (pctrie_lookup_ge_node(node, index + 1));
		}

		#ifdef INVARIANTS
		void
		pctrie_subtree_lookup_gt_assert(struct pctrie_node *node, uint64_t index,
		struct pctrie ptree, uint64_t res)
		{
		uint64_t *expected;

		if (index + 1 == 0)
		expected = NULL;
		else
		expected = pctrie_lookup_ge(ptree, index + 1);
		KASSERT(res == expected,
		("pctrie subtree lookup gt result different from root lookup: "
		"ptree %p, index %ju, subtree %p, found %p, expected %p", ptree,
		(uintmax_t)index, node, res, expected));
		}
		#endif

/*		/*
* Returns the value with the greatest index that is less than or equal to the		* Returns the value with the greatest index that is less than or equal to the
* specified index, or NULL if there are no such values.		* specified index, or NULL if there are no such values.
*		*
* Requires that access be externally synchronized by a lock.		* Requires that access be externally synchronized by a lock.
*/		*/
uint64_t *		static __inline uint64_t *
pctrie_lookup_le(struct pctrie *ptree, uint64_t index)		pctrie_lookup_le_node(struct pctrie_node *node, uint64_t index)
{		{
struct pctrie_node node, pred;		struct pctrie_node *pred;
uint64_t *m;		uint64_t *m;
int slot;		int slot;

/*		/*
* Mirror the implementation of pctrie_lookup_ge, described above.		* Mirror the implementation of pctrie_lookup_ge_node, described above.
*/		*/
node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
pred = NULL;		pred = NULL;
for (;;) {		for (;;) {
if (pctrie_isleaf(node)) {		if (pctrie_isleaf(node)) {
if ((m = pctrie_toval(node)) != NULL && *m <= index)		if ((m = pctrie_toval(node)) != NULL && *m <= index)
return (m);		return (m);
break;		break;
}		}
if (pctrie_keybarr(node, index, &slot)) {		if (pctrie_keybarr(node, index, &slot)) {
Show All 21 Lines	while (!pctrie_isleaf(pred)) {
KASSERT(pred->pn_popmap != 0,		KASSERT(pred->pn_popmap != 0,
("%s: no popmap children in node %p", __func__, pred));		("%s: no popmap children in node %p", __func__, pred));
slot = ilog2(pred->pn_popmap);		slot = ilog2(pred->pn_popmap);
pred = pctrie_node_load(&pred->pn_child[slot], NULL,		pred = pctrie_node_load(&pred->pn_child[slot], NULL,
PCTRIE_LOCKED);		PCTRIE_LOCKED);
}		}
return (pctrie_toval(pred));		return (pctrie_toval(pred));
}		}

		uint64_t *
		pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
		{
		return (pctrie_lookup_le_node(
		pctrie_root_load(ptree, NULL, PCTRIE_LOCKED), index));
		}

		uint64_t *
		pctrie_subtree_lookup_lt(struct pctrie_node *node, uint64_t index)
		{
		if (node == NULL \|\| index == 0)
		return (NULL);
		return (pctrie_lookup_le_node(node, index - 1));
		}

		#ifdef INVARIANTS
		void
		pctrie_subtree_lookup_lt_assert(struct pctrie_node *node, uint64_t index,
		struct pctrie ptree, uint64_t res)
		{
		uint64_t *expected;

		if (index == 0)
		expected = NULL;
		else
		expected = pctrie_lookup_le(ptree, index - 1);
		KASSERT(res == expected,
		("pctrie subtree lookup lt result different from root lookup: "
		"ptree %p, index %ju, subtree %p, found %p, expected %p", ptree,
		(uintmax_t)index, node, res, expected));
		}
		#endif

/*		/*
* Remove the specified index from the tree, and return the value stored at		* Remove the specified index from the tree, and return the value stored at
* that index. If the index is not present, return NULL.		* that index. If the index is not present, return NULL.
*/		*/
uint64_t *		uint64_t *
pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,		pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **freenode)		struct pctrie_node **freenode)
▲ Show 20 Lines • Show All 186 Lines • Show Last 20 Lines