D40979.id124525.diff
No OneTemporary
Actions

Size

27 KB

Referenced Files

None

Subscribers

None

D40979.id124525.diff
View Options

	Index: sys/kern/subr_pctrie.c
	===================================================================
	--- sys/kern/subr_pctrie.c
	+++ sys/kern/subr_pctrie.c
	@@ -80,7 +80,6 @@
	"pn_popmap_t too wide");

	/* Flag bits stored in node pointers. */
	-#define PCTRIE_ISLEAF 0x1
	#define PCTRIE_FLAGS 0x1
	#define PCTRIE_PAD PCTRIE_FLAGS

	@@ -97,6 +96,7 @@
	uint8_t pn_clev; /* Current level. */
	smr_pctnode_t pn_child[PCTRIE_COUNT]; /* Child nodes. */
	};
	+#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF

	enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };

	@@ -140,7 +140,7 @@
	*/
	if (node->pn_popmap != 0) {
	pctrie_node_store(&node->pn_child[ffs(node->pn_popmap) - 1],
	- NULL, PCTRIE_UNSERIALIZED);
	+ PCTRIE_NULL, PCTRIE_UNSERIALIZED);
	node->pn_popmap = 0;
	}
	node->pn_owner = pctrie_trimkey(index, clevel + 1);
	@@ -165,7 +165,8 @@
	if ((node->pn_popmap & (1 << slot)) != 0)
	continue;
	KASSERT(smr_unserialized_load(&node->pn_child[slot], true) ==
	- NULL, ("pctrie_node_put: node %p has a child", node));
	+ PCTRIE_NULL,
	+ ("pctrie_node_put: node %p has a child", node));
	}
	#endif
	freefn(ptree, node);
	@@ -177,20 +178,29 @@
	static __inline struct pctrie_node *
	pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
	{
	+ struct pctrie_node *node;
	+
	switch (access) {
	case PCTRIE_UNSERIALIZED:
	- return (smr_unserialized_load(p, true));
	+ node = smr_unserialized_load(p, true);
	+ break;
	case PCTRIE_LOCKED:
	- return (smr_serialized_load(p, true));
	+ node = smr_serialized_load(p, true);
	+ break;
	case PCTRIE_SMR:
	- return (smr_entered_load(p, smr));
	+ node = smr_entered_load(p, smr);
	+ break;
	+ default:
	+ __assert_unreachable();
	}
	- __assert_unreachable();
	+ KASSERT(node != NULL, ("%s: NULL node", __func__));
	+ return (node);
	}

	static __inline void
	pctrie_node_store(smr_pctnode_t p, void v, enum pctrie_access access)
	{
	+ KASSERT(v != NULL, ("%s: NULL node", __func__));
	switch (access) {
	case PCTRIE_UNSERIALIZED:
	smr_unserialized_store(p, v, true);
	@@ -320,12 +330,13 @@
	slot = ffs(node->pn_popmap) - 1;
	child = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_UNSERIALIZED);
	- KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p",
	+ KASSERT(child != PCTRIE_NULL,
	+ ("%s: bad popmap slot %d in node %p",
	__func__, slot, node));
	if (!pctrie_isleaf(child))
	pctrie_reclaim_allnodes_int(ptree, child, freefn);
	node->pn_popmap ^= 1 << slot;
	- pctrie_node_store(&node->pn_child[slot], NULL,
	+ pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL,
	PCTRIE_UNSERIALIZED);
	}
	pctrie_node_put(ptree, node, freefn);
	@@ -341,7 +352,9 @@

	node = mem;
	node->pn_popmap = 0;
	- memset(node->pn_child, 0, sizeof(node->pn_child));
	+ for (int i = 0; i < nitems(node->pn_child); i++)
	+ pctrie_node_store(&node->pn_child[i], PCTRIE_NULL,
	+ PCTRIE_UNSERIALIZED);
	return (0);
	}

	@@ -360,7 +373,7 @@
	pctrie_insert(struct pctrie ptree, uint64_t val, pctrie_alloc_t allocfn)
	{
	uint64_t index, newind;
	- struct pctrie_node leaf, node, *tmp;
	+ struct pctrie_node leaf, parent, *node;
	smr_pctnode_t *parentp;
	int slot;
	uint16_t clev;
	@@ -373,30 +386,29 @@
	* will never be used.
	*/
	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- if (node == NULL) {
	+ if (node == PCTRIE_NULL) {
	ptree->pt_root = (uintptr_t)leaf;
	return (0);
	}
	- for (parentp = (smr_pctnode_t *)&ptree->pt_root;; node = tmp) {
	- if (pctrie_isleaf(node)) {
	- newind = *pctrie_toval(node);
	- if (newind == index)
	- panic("%s: key %jx is already present",
	- __func__, (uintmax_t)index);
	- break;
	- } else if (pctrie_keybarr(node, index)) {
	- newind = node->pn_owner;
	- break;
	- }
	- slot = pctrie_slot(index, node->pn_clev);
	- parentp = &node->pn_child[slot];
	- tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED);
	- if (tmp == NULL) {
	- pctrie_addnode(node, index, node->pn_clev, leaf,
	- PCTRIE_LOCKED);
	- return (0);
	- }
	+ parentp = (smr_pctnode_t *)&ptree->pt_root;
	+ while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index)) {
	+ parent = node;
	+ slot = pctrie_slot(index, parent->pn_clev);
	+ parentp = &parent->pn_child[slot];
	+ node = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED);
	}
	+ if (node == PCTRIE_NULL) {
	+ pctrie_addnode(parent, index, parent->pn_clev, leaf,
	+ PCTRIE_LOCKED);
	+ return (0);
	+ }
	+ if (pctrie_isleaf(node)) {
	+ newind = *pctrie_toval(node);
	+ if (newind == index)
	+ panic("%s: key %jx is already present",
	+ __func__, (uintmax_t)index);
	+ } else
	+ newind = node->pn_owner;

	/*
	* A new node is needed because the right insertion level is reached.
	@@ -404,14 +416,14 @@
	* new object and the older edge or object.
	*/
	clev = pctrie_keydiff(newind, index);
	- tmp = pctrie_node_get(ptree, allocfn, index, clev);
	- if (tmp == NULL)
	+ parent = pctrie_node_get(ptree, allocfn, index, clev);
	+ if (parent == NULL)
	return (ENOMEM);
	/* These writes are not yet visible due to ordering. */
	- pctrie_addnode(tmp, index, clev, leaf, PCTRIE_UNSERIALIZED);
	- pctrie_addnode(tmp, newind, clev, node, PCTRIE_UNSERIALIZED);
	+ pctrie_addnode(parent, index, clev, leaf, PCTRIE_UNSERIALIZED);
	+ pctrie_addnode(parent, newind, clev, node, PCTRIE_UNSERIALIZED);
	/* Synchronize to make the above visible. */
	- pctrie_node_store(parentp, tmp, PCTRIE_LOCKED);
	+ pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
	return (0);
	}

	@@ -428,18 +440,13 @@
	int slot;

	node = pctrie_root_load(ptree, smr, access);
	- while (node != NULL) {
	- if (pctrie_isleaf(node)) {
	- m = pctrie_toval(node);
	- if (*m == index)
	- return (m);
	- break;
	- }
	- if (pctrie_keybarr(node, index))
	- break;
	+ while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index)) {
	slot = pctrie_slot(index, node->pn_clev);
	node = pctrie_node_load(&node->pn_child[slot], smr, access);
	}
	+ if (pctrie_isleaf(node) && (m = pctrie_toval(node)) != NULL &&
	+ *m == index)
	+ return (m);
	return (NULL);
	}

	@@ -488,14 +495,10 @@
	int slot;

	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- if (node == NULL)
	- return (NULL);
	- else if (pctrie_isleaf(node)) {
	- m = pctrie_toval(node);
	- if (*m >= index)
	+ if (pctrie_isleaf(node)) {
	+ if ((m = pctrie_toval(node)) != NULL && *m >= index)
	return (m);
	- else
	- return (NULL);
	+ return (NULL);
	}
	tos = 0;
	for (;;) {
	@@ -540,12 +543,10 @@
	slot = pctrie_slot(index, node->pn_clev);
	child = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_LOCKED);
	- if (pctrie_isleaf(child)) {
	- m = pctrie_toval(child);
	- if (*m >= index)
	- return (m);
	- } else if (child != NULL)
	+ if (!pctrie_isleaf(child))
	goto descend;
	+ if ((m = pctrie_toval(child)) != NULL && *m >= index)
	+ return (m);

	/* Find the first set bit beyond the first slot+1 bits. */
	slot = ffs(node->pn_popmap & (-2 << slot)) - 1;
	@@ -559,7 +560,8 @@
	}
	child = pctrie_node_load(&node->pn_child[slot],
	NULL, PCTRIE_LOCKED);
	- KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p",
	+ KASSERT(child != PCTRIE_NULL,
	+ ("%s: bad popmap slot %d in node %p",
	__func__, slot, node));
	if (pctrie_isleaf(child))
	return (pctrie_toval(child));
	@@ -592,14 +594,10 @@
	int slot;

	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- if (node == NULL)
	- return (NULL);
	- else if (pctrie_isleaf(node)) {
	- m = pctrie_toval(node);
	- if (*m <= index)
	+ if (pctrie_isleaf(node)) {
	+ if ((m = pctrie_toval(node)) != NULL && *m <= index)
	return (m);
	- else
	- return (NULL);
	+ return (NULL);
	}
	tos = 0;
	for (;;) {
	@@ -646,12 +644,10 @@
	slot = pctrie_slot(index, node->pn_clev);
	child = pctrie_node_load(&node->pn_child[slot], NULL,
	PCTRIE_LOCKED);
	- if (pctrie_isleaf(child)) {
	- m = pctrie_toval(child);
	- if (*m <= index)
	- return (m);
	- } else if (child != NULL)
	+ if (!pctrie_isleaf(child))
	goto descend;
	+ if ((m = pctrie_toval(child)) != NULL && *m <= index)
	+ return (m);

	/* Find the last set bit among the first slot bits. */
	slot = fls(node->pn_popmap & ((1 << slot) - 1)) - 1;
	@@ -665,6 +661,9 @@
	}
	child = pctrie_node_load(&node->pn_child[slot],
	NULL, PCTRIE_LOCKED);
	+ KASSERT(child != PCTRIE_NULL,
	+ ("%s: bad popmap slot %d in rnode %p",
	+ __func__, slot, node));
	if (pctrie_isleaf(child))
	return (pctrie_toval(child));
	index = pctrie_trimkey(index, node->pn_clev + 1) +
	@@ -686,66 +685,55 @@
	void
	pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
	{
	- struct pctrie_node node, parent, *tmp;
	+ struct pctrie_node child, node, *parent;
	uint64_t *m;
	int slot;

	- node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- if (pctrie_isleaf(node)) {
	- m = pctrie_toval(node);
	- if (*m != index)
	- panic("%s: invalid key found", __func__);
	- pctrie_root_store(ptree, NULL, PCTRIE_LOCKED);
	- return;
	+ node = NULL;
	+ child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	+ if (pctrie_isleaf(child)) {
	+ if ((m = pctrie_toval(child)) != NULL && *m == index) {
	+ pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_LOCKED);
	+ return;
	+ }
	+ panic("%s: key not found", __func__);
	}
	- parent = NULL;
	- for (;;) {
	- if (node == NULL)
	- panic("pctrie_remove: impossible to locate the key");
	+ do {
	+ parent = node;
	+ node = child;
	slot = pctrie_slot(index, node->pn_clev);
	- tmp = pctrie_node_load(&node->pn_child[slot], NULL,
	+ child = pctrie_node_load(&node->pn_child[slot], NULL,
	+ PCTRIE_LOCKED);
	+ } while (!pctrie_isleaf(child));
	+ if ((m = pctrie_toval(child)) == NULL \|\| *m != index)
	+ panic("%s: key not found", __func__);
	+ 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;
	+ 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,
	+ ("%s: bad popmap slot %d in node %p", __func__, slot, node));
	+ if (parent == NULL)
	+ pctrie_root_store(ptree, child, PCTRIE_LOCKED);
	+ else {
	+ slot = pctrie_slot(index, parent->pn_clev);
	+ 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);
	- if (pctrie_isleaf(tmp)) {
	- m = pctrie_toval(tmp);
	- if (*m != index)
	- panic("%s: invalid key found", __func__);
	- 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], NULL,
	- PCTRIE_LOCKED);
	- if (!powerof2(node->pn_popmap))
	- break;
	- KASSERT(node->pn_popmap != 0,
	- ("%s: bad popmap all zeroes", __func__));
	- slot = ffs(node->pn_popmap) - 1;
	- tmp = pctrie_node_load(&node->pn_child[slot],
	- NULL, PCTRIE_LOCKED);
	- KASSERT(tmp != NULL,
	- ("%s: bad popmap slot %d in node %p",
	- __func__, slot, node));
	- if (parent == NULL)
	- pctrie_root_store(ptree, tmp, PCTRIE_LOCKED);
	- else {
	- slot = pctrie_slot(index, parent->pn_clev);
	- KASSERT(pctrie_node_load(
	- &parent->pn_child[slot], NULL,
	- PCTRIE_LOCKED) == node,
	- ("%s: invalid child value", __func__));
	- pctrie_node_store(&parent->pn_child[slot], tmp,
	- PCTRIE_LOCKED);
	- }
	- /*
	- * The child is still valid and we can not zero the
	- * pointer until all SMR references are gone.
	- */
	- pctrie_node_put(ptree, node, freefn);
	- break;
	- }
	- parent = node;
	- node = tmp;
	}
	+ /*
	+ * The child is still valid and we can not zero the
	+ * pointer until all SMR references are gone.
	+ */
	+ pctrie_node_put(ptree, node, freefn);
	}

	/*
	@@ -759,11 +747,11 @@
	struct pctrie_node *root;

	root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	- if (root == NULL)
	+ if (root == PCTRIE_NULL)
	return;
	- pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED);
	if (!pctrie_isleaf(root))
	pctrie_reclaim_allnodes_int(ptree, root, freefn);
	+ pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_UNSERIALIZED);
	}

	#ifdef DDB
	Index: sys/sys/pctrie.h
	===================================================================
	--- sys/sys/pctrie.h
	+++ sys/sys/pctrie.h
	@@ -134,19 +134,20 @@
	pctrie_free_t freefn);
	size_t pctrie_node_size(void);
	int pctrie_zone_init(void *mem, int size, int flags);
	+#define PCTRIE_ISLEAF 0x1

	static __inline void
	pctrie_init(struct pctrie *ptree)
	{

	- ptree->pt_root = 0;
	+ ptree->pt_root = PCTRIE_ISLEAF;
	}

	static __inline bool
	pctrie_is_empty(struct pctrie *ptree)
	{

	- return (ptree->pt_root == 0);
	+ return (ptree->pt_root == PCTRIE_ISLEAF);
	}

	/*
	Index: sys/vm/vm_radix.h
	===================================================================
	--- sys/vm/vm_radix.h
	+++ sys/vm/vm_radix.h
	@@ -47,19 +47,20 @@
	vm_page_t vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index);
	vm_page_t vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage);
	void vm_radix_zinit(void);
	+#define VM_RADIX_ISLEAF 0x1

	static __inline void
	vm_radix_init(struct vm_radix *rtree)
	{

	- rtree->rt_root = 0;
	+ rtree->rt_root = VM_RADIX_ISLEAF;
	}

	static __inline bool
	vm_radix_is_empty(struct vm_radix *rtree)
	{

	- return (rtree->rt_root == 0);
	+ return (rtree->rt_root == (uintptr_t)VM_RADIX_ISLEAF);
	}

	#endif /* _KERNEL */
	Index: sys/vm/vm_radix.c
	===================================================================
	--- sys/vm/vm_radix.c
	+++ sys/vm/vm_radix.c
	@@ -104,7 +104,6 @@
	"rn_popmap_t too wide");

	/* Flag bits stored in node pointers. */
	-#define VM_RADIX_ISLEAF 0x1
	#define VM_RADIX_FLAGS 0x1
	#define VM_RADIX_PAD VM_RADIX_FLAGS

	@@ -123,6 +122,7 @@
	uint8_t rn_clev; /* Current level. */
	smrnode_t rn_child[VM_RADIX_COUNT]; /* Child nodes. */
	};
	+#define VM_RADIX_NULL (struct vm_radix_node *)VM_RADIX_ISLEAF

	static uma_zone_t vm_radix_node_zone;
	static smr_t vm_radix_smr;
	@@ -165,7 +165,7 @@
	*/
	if (rnode->rn_popmap != 0) {
	vm_radix_node_store(&rnode->rn_child[ffs(rnode->rn_popmap) - 1],
	- NULL, UNSERIALIZED);
	+ VM_RADIX_NULL, UNSERIALIZED);
	rnode->rn_popmap = 0;
	}
	rnode->rn_owner = vm_radix_trimkey(index, clevel + 1);
	@@ -189,7 +189,8 @@
	if ((rnode->rn_popmap & (1 << slot)) != 0)
	continue;
	KASSERT(smr_unserialized_load(&rnode->rn_child[slot], true) ==
	- NULL, ("vm_radix_node_put: rnode %p has a child", rnode));
	+ VM_RADIX_NULL,
	+ ("vm_radix_node_put: rnode %p has a child", rnode));
	}
	#endif
	uma_zfree_smr(vm_radix_node_zone, rnode);
	@@ -201,23 +202,30 @@
	static __inline struct vm_radix_node *
	vm_radix_node_load(smrnode_t *p, enum vm_radix_access access)
	{
	+ struct vm_radix_node *rnode;

	switch (access) {
	case UNSERIALIZED:
	- return (smr_unserialized_load(p, true));
	+ rnode = smr_unserialized_load(p, true);
	+ break;
	case LOCKED:
	- return (smr_serialized_load(p, true));
	+ rnode = smr_serialized_load(p, true);
	+ break;
	case SMR:
	- return (smr_entered_load(p, vm_radix_smr));
	+ rnode = smr_entered_load(p, vm_radix_smr);
	+ break;
	+ default:
	+ __assert_unreachable();
	}
	- __assert_unreachable();
	+ KASSERT(rnode != NULL, ("%s: NULL node", __func__));
	+ return (rnode);
	}

	static __inline void
	vm_radix_node_store(smrnode_t p, struct vm_radix_node v,
	enum vm_radix_access access)
	{
	-
	+ KASSERT(v != NULL, ("%s: NULL node", __func__));
	switch (access) {
	case UNSERIALIZED:
	smr_unserialized_store(p, v, true);
	@@ -344,17 +352,34 @@
	slot = ffs(rnode->rn_popmap) - 1;
	child = vm_radix_node_load(&rnode->rn_child[slot],
	UNSERIALIZED);
	- KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p",
	+ KASSERT(child != VM_RADIX_NULL,
	+ ("%s: bad popmap slot %d in rnode %p",
	__func__, slot, rnode));
	if (!vm_radix_isleaf(child))
	vm_radix_reclaim_allnodes_int(child);
	rnode->rn_popmap ^= 1 << slot;
	- vm_radix_node_store(&rnode->rn_child[slot], NULL,
	+ vm_radix_node_store(&rnode->rn_child[slot], VM_RADIX_NULL,
	UNSERIALIZED);
	}
	vm_radix_node_put(rnode);
	}

	+/*
	+ * radix node zone initializer.
	+ */
	+static int
	+vm_radix_zone_init(void *mem, int size, int flags)
	+{
	+ struct vm_radix_node *rnode;
	+
	+ rnode = mem;
	+ rnode->rn_popmap = 0;
	+ for (int i = 0; i < nitems(rnode->rn_child); i++)
	+ vm_radix_node_store(&rnode->rn_child[i], VM_RADIX_NULL,
	+ UNSERIALIZED);
	+ return (0);
	+}
	+
	#ifndef UMA_MD_SMALL_ALLOC
	void vm_radix_reserve_kva(void);
	/*
	@@ -387,8 +412,8 @@
	{

	vm_radix_node_zone = uma_zcreate("RADIX NODE",
	- sizeof(struct vm_radix_node), NULL, NULL, NULL, NULL,
	- VM_RADIX_PAD, UMA_ZONE_VM \| UMA_ZONE_SMR \| UMA_ZONE_ZINIT);
	+ sizeof(struct vm_radix_node), NULL, NULL, vm_radix_zone_init, NULL,
	+ VM_RADIX_PAD, UMA_ZONE_VM \| UMA_ZONE_SMR);
	vm_radix_smr = uma_zone_get_smr(vm_radix_node_zone);
	}

	@@ -400,7 +425,7 @@
	vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
	{
	vm_pindex_t index, newind;
	- struct vm_radix_node leaf, rnode, *tmp;
	+ struct vm_radix_node leaf, parent, *rnode;
	smrnode_t *parentp;
	int slot;
	uint16_t clev;
	@@ -413,30 +438,28 @@
	* will never be used.
	*/
	rnode = vm_radix_root_load(rtree, LOCKED);
	- if (rnode == NULL) {
	+ if (rnode == VM_RADIX_NULL) {
	rtree->rt_root = (uintptr_t)leaf;
	return (0);
	}
	- for (parentp = (smrnode_t *)&rtree->rt_root;; rnode = tmp) {
	- if (vm_radix_isleaf(rnode)) {
	- newind = vm_radix_topage(rnode)->pindex;
	- if (newind == index)
	- panic("%s: key %jx is already present",
	- __func__, (uintmax_t)index);
	- break;
	- } else if (vm_radix_keybarr(rnode, index)) {
	- newind = rnode->rn_owner;
	- break;
	- }
	- slot = vm_radix_slot(index, rnode->rn_clev);
	- parentp = &rnode->rn_child[slot];
	- tmp = vm_radix_node_load(parentp, LOCKED);
	- if (tmp == NULL) {
	- vm_radix_addnode(rnode, index, rnode->rn_clev, leaf,
	- LOCKED);
	- return (0);
	- }
	+ parentp = (smrnode_t *)&rtree->rt_root;
	+ while (!vm_radix_isleaf(rnode) && !vm_radix_keybarr(rnode, index)) {
	+ parent = rnode;
	+ slot = vm_radix_slot(index, parent->rn_clev);
	+ parentp = &parent->rn_child[slot];
	+ rnode = vm_radix_node_load(parentp, LOCKED);
	+ }
	+ if (rnode == VM_RADIX_NULL) {
	+ vm_radix_addnode(parent, index, parent->rn_clev, leaf, LOCKED);
	+ return (0);
	}
	+ if (vm_radix_isleaf(rnode)) {
	+ newind = vm_radix_topage(rnode)->pindex;
	+ if (newind == index)
	+ panic("%s: key %jx is already present",
	+ __func__, (uintmax_t)index);
	+ } else
	+ newind = rnode->rn_owner;

	/*
	* A new node is needed because the right insertion level is reached.
	@@ -444,14 +467,14 @@
	* new object and the older edge or object.
	*/
	clev = vm_radix_keydiff(newind, index);
	- tmp = vm_radix_node_get(index, clev);
	- if (tmp == NULL)
	+ parent = vm_radix_node_get(index, clev);
	+ if (parent == NULL)
	return (ENOMEM);
	/* These writes are not yet visible due to ordering. */
	- vm_radix_addnode(tmp, index, clev, leaf, UNSERIALIZED);
	- vm_radix_addnode(tmp, newind, clev, rnode, UNSERIALIZED);
	+ vm_radix_addnode(parent, index, clev, leaf, UNSERIALIZED);
	+ vm_radix_addnode(parent, newind, clev, rnode, UNSERIALIZED);
	/* Serializing write to make the above visible. */
	- vm_radix_node_store(parentp, tmp, LOCKED);
	+ vm_radix_node_store(parentp, parent, LOCKED);
	return (0);
	}

	@@ -468,18 +491,14 @@
	int slot;

	rnode = vm_radix_root_load(rtree, access);
	- while (rnode != NULL) {
	- if (vm_radix_isleaf(rnode)) {
	- m = vm_radix_topage(rnode);
	- if (m->pindex == index)
	- return (m);
	- break;
	- }
	- if (vm_radix_keybarr(rnode, index))
	- break;
	+ while (!vm_radix_isleaf(rnode) && !vm_radix_keybarr(rnode, index)) {
	slot = vm_radix_slot(index, rnode->rn_clev);
	rnode = vm_radix_node_load(&rnode->rn_child[slot], access);
	}
	+ if (vm_radix_isleaf(rnode) &&
	+ (m = vm_radix_topage(rnode)) != NULL &&
	+ m->pindex == index)
	+ return (m);
	return (NULL);
	}

	@@ -527,14 +546,10 @@
	int slot, tos;

	rnode = vm_radix_root_load(rtree, LOCKED);
	- if (rnode == NULL)
	- return (NULL);
	- else if (vm_radix_isleaf(rnode)) {
	- m = vm_radix_topage(rnode);
	- if (m->pindex >= index)
	+ if (vm_radix_isleaf(rnode)) {
	+ if ((m = vm_radix_topage(rnode)) != NULL && m->pindex >= index)
	return (m);
	- else
	- return (NULL);
	+ return (NULL);
	}
	tos = 0;
	for (;;) {
	@@ -578,12 +593,10 @@
	}
	slot = vm_radix_slot(index, rnode->rn_clev);
	child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- if (vm_radix_isleaf(child)) {
	- m = vm_radix_topage(child);
	- if (m->pindex >= index)
	- return (m);
	- } else if (child != NULL)
	+ if (!vm_radix_isleaf(child))
	goto descend;
	+ if ((m = vm_radix_topage(child)) != NULL && m->pindex >= index)
	+ return (m);

	/* Find the first set bit beyond the first slot+1 bits. */
	slot = ffs(rnode->rn_popmap & (-2 << slot)) - 1;
	@@ -596,7 +609,8 @@
	goto ascend;
	}
	child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p",
	+ KASSERT(child != VM_RADIX_NULL,
	+ ("%s: bad popmap slot %d in rnode %p",
	__func__, slot, rnode));
	if (vm_radix_isleaf(child))
	return (vm_radix_topage(child));
	@@ -627,14 +641,10 @@
	int slot, tos;

	rnode = vm_radix_root_load(rtree, LOCKED);
	- if (rnode == NULL)
	- return (NULL);
	- else if (vm_radix_isleaf(rnode)) {
	- m = vm_radix_topage(rnode);
	- if (m->pindex <= index)
	+ if (vm_radix_isleaf(rnode)) {
	+ if ((m = vm_radix_topage(rnode)) != NULL && m->pindex <= index)
	return (m);
	- else
	- return (NULL);
	+ return (NULL);
	}
	tos = 0;
	for (;;) {
	@@ -680,12 +690,10 @@
	}
	slot = vm_radix_slot(index, rnode->rn_clev);
	child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- if (vm_radix_isleaf(child)) {
	- m = vm_radix_topage(child);
	- if (m->pindex <= index)
	- return (m);
	- } else if (child != NULL)
	+ if (!vm_radix_isleaf(child))
	goto descend;
	+ if ((m = vm_radix_topage(child)) != NULL && m->pindex <= index)
	+ return (m);

	/* Find the last set bit among the first slot bits. */
	slot = fls(rnode->rn_popmap & ((1 << slot) - 1)) - 1;
	@@ -698,7 +706,8 @@
	goto ascend;
	}
	child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p",
	+ KASSERT(child != VM_RADIX_NULL,
	+ ("%s: bad popmap slot %d in rnode %p",
	__func__, slot, rnode));
	if (vm_radix_isleaf(child))
	return (vm_radix_topage(child));
	@@ -721,63 +730,54 @@
	vm_page_t
	vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
	{
	- struct vm_radix_node rnode, parent, *tmp;
	+ struct vm_radix_node child, rnode, *parent;
	vm_page_t m;
	int slot;

	- rnode = vm_radix_root_load(rtree, LOCKED);
	- if (vm_radix_isleaf(rnode)) {
	- m = vm_radix_topage(rnode);
	- if (m->pindex != index)
	- return (NULL);
	- vm_radix_root_store(rtree, NULL, LOCKED);
	- return (m);
	- }
	- parent = NULL;
	- for (;;) {
	- if (rnode == NULL)
	- return (NULL);
	- slot = vm_radix_slot(index, rnode->rn_clev);
	- tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- if (vm_radix_isleaf(tmp)) {
	- m = vm_radix_topage(tmp);
	- if (m->pindex != index)
	- return (NULL);
	- KASSERT((rnode->rn_popmap & (1 << slot)) != 0,
	- ("%s: bad popmap slot %d in rnode %p",
	- __func__, slot, rnode));
	- rnode->rn_popmap ^= 1 << slot;
	- vm_radix_node_store(
	- &rnode->rn_child[slot], NULL, LOCKED);
	- if (!powerof2(rnode->rn_popmap))
	- return (m);
	- KASSERT(rnode->rn_popmap != 0,
	- ("%s: bad popmap all zeroes", __func__));
	- slot = ffs(rnode->rn_popmap) - 1;
	- tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- KASSERT(tmp != NULL,
	- ("%s: bad popmap slot %d in rnode %p",
	- __func__, slot, rnode));
	- if (parent == NULL)
	- vm_radix_root_store(rtree, tmp, LOCKED);
	- else {
	- slot = vm_radix_slot(index, parent->rn_clev);
	- KASSERT(vm_radix_node_load(
	- &parent->rn_child[slot], LOCKED) == rnode,
	- ("%s: invalid child value", __func__));
	- vm_radix_node_store(&parent->rn_child[slot],
	- tmp, LOCKED);
	- }
	- /*
	- * The child is still valid and we can not zero the
	- * pointer until all smr references are gone.
	- */
	- vm_radix_node_put(rnode);
	+ rnode = NULL;
	+ child = vm_radix_root_load(rtree, LOCKED);
	+ if (vm_radix_isleaf(child)) {
	+ if ((m = vm_radix_topage(child)) != NULL &&
	+ m->pindex == index) {
	+ vm_radix_root_store(rtree, VM_RADIX_NULL, LOCKED);
	return (m);
	}
	+ return (NULL);
	+ }
	+ do {
	parent = rnode;
	- rnode = tmp;
	+ rnode = child;
	+ slot = vm_radix_slot(index, rnode->rn_clev);
	+ child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	+ } while (!vm_radix_isleaf(child));
	+ if ((m = vm_radix_topage(child)) == NULL \|\| m->pindex != index)
	+ return (NULL);
	+ KASSERT((rnode->rn_popmap & (1 << slot)) != 0,
	+ ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode));
	+ rnode->rn_popmap ^= 1 << slot;
	+ vm_radix_node_store(&rnode->rn_child[slot], VM_RADIX_NULL, LOCKED);
	+ if (!powerof2(rnode->rn_popmap))
	+ return (m);
	+ KASSERT(rnode->rn_popmap != 0, ("%s: bad popmap all zeroes", __func__));
	+ slot = ffs(rnode->rn_popmap) - 1;
	+ child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	+ KASSERT(child != VM_RADIX_NULL,
	+ ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode));
	+ if (parent == NULL)
	+ vm_radix_root_store(rtree, child, LOCKED);
	+ else {
	+ slot = vm_radix_slot(index, parent->rn_clev);
	+ KASSERT(rnode ==
	+ vm_radix_node_load(&parent->rn_child[slot], LOCKED),
	+ ("%s: invalid child value", __func__));
	+ vm_radix_node_store(&parent->rn_child[slot], child, LOCKED);
	}
	+ /*
	+ * The child is still valid and we can not zero the
	+ * pointer until all smr references are gone.
	+ */
	+ vm_radix_node_put(rnode);
	+ return (m);
	}

	/*
	@@ -791,11 +791,11 @@
	struct vm_radix_node *root;

	root = vm_radix_root_load(rtree, LOCKED);
	- if (root == NULL)
	+ if (root == VM_RADIX_NULL)
	return;
	- vm_radix_root_store(rtree, NULL, UNSERIALIZED);
	if (!vm_radix_isleaf(root))
	vm_radix_reclaim_allnodes_int(root);
	+ vm_radix_root_store(rtree, VM_RADIX_NULL, UNSERIALIZED);
	}

	/*
	@@ -805,36 +805,30 @@
	vm_page_t
	vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage)
	{
	- struct vm_radix_node rnode, tmp;
	+ struct vm_radix_node leaf, parent, *rnode;
	vm_page_t m;
	vm_pindex_t index;
	int slot;

	+ leaf = vm_radix_toleaf(newpage);
	index = newpage->pindex;
	rnode = vm_radix_root_load(rtree, LOCKED);
	- if (rnode == NULL)
	- panic("%s: replacing page on an empty trie", __func__);
	if (vm_radix_isleaf(rnode)) {
	- m = vm_radix_topage(rnode);
	- if (m->pindex != index)
	- panic("%s: original replacing root key not found",
	- __func__);
	- rtree->rt_root = (uintptr_t)vm_radix_toleaf(newpage);
	- return (m);
	- }
	- for (;;) {
	- slot = vm_radix_slot(index, rnode->rn_clev);
	- tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED);
	- if (vm_radix_isleaf(tmp)) {
	- m = vm_radix_topage(tmp);
	- if (m->pindex != index)
	- break;
	- vm_radix_node_store(&rnode->rn_child[slot],
	- vm_radix_toleaf(newpage), LOCKED);
	+ if ((m = vm_radix_topage(rnode)) != NULL && m->pindex == index) {
	+ rtree->rt_root = (uintptr_t)leaf;
	return (m);
	- } else if (tmp == NULL \|\| vm_radix_keybarr(tmp, index))
	- break;
	- rnode = tmp;
	+ }
	+ panic("%s: original replacing page not found at root", __func__);
	+ }
	+ do {
	+ parent = rnode;
	+ slot = vm_radix_slot(index, parent->rn_clev);
	+ rnode = vm_radix_node_load(&parent->rn_child[slot], LOCKED);
	+ } while (!vm_radix_isleaf(rnode) && !vm_radix_keybarr(rnode, index));
	+ if (vm_radix_isleaf(rnode) && (m = vm_radix_topage(rnode)) != NULL &&
	+ m->pindex == index) {
	+ vm_radix_node_store(&parent->rn_child[slot], leaf, LOCKED);
	+ return (m);
	}
	panic("%s: original replacing page not found", __func__);
	}

File Metadata

Mime Type: text/plain
Expires: Thu, May 1, 6:53 AM (1 h, 48 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 17875407
Default Alt Text: D40979.id124525.diff (27 KB)

D40979.id124525.diffNo OneTemporaryActions

D40979.id124525.diffView Options

File Metadata

Event Timeline

D40979.id124525.diff
No OneTemporary
Actions

D40979.id124525.diff
View Options