Page MenuHomeFreeBSD
Files F107902767

D45510.diff
No OneTemporary
Actions

D45510.diff
View Options

Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -285,7 +285,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)
+ void **parentp_out, enum pctrie_insert_neighbor_mode mode)
{
uint64_t index;
struct pctrie_node *node, *parent;
@@ -302,6 +302,11 @@
for (;;) {
if (pctrie_isleaf(node)) {
if (node == PCTRIE_NULL) {
+ if (parentp_out != NULL) {
+ *parentp_out = (parent == NULL) ?
+ (smr_pctnode_t *)&ptree->pt_root :
+ &parent->pn_child[slot];
+ }
if (parent == NULL)
ptree->pt_root = pctrie_toleaf(val);
else
@@ -367,7 +372,7 @@
uint64_t *found;
found = NULL;
- parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL,
+ parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL, NULL,
PCTRIE_INSERT_NEIGHBOR_NONE);
if (__predict_false(found != NULL))
panic("%s: key %jx is already present", __func__,
@@ -384,7 +389,7 @@
uint64_t **found_out)
{
*found_out = NULL;
- return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
+ return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL, NULL,
PCTRIE_INSERT_NEIGHBOR_NONE));
}
@@ -400,7 +405,7 @@
*found_out = NULL;
*neighbor_out = NULL;
return (pctrie_insert_lookup_compound(ptree, val, found_out,
- neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
+ neighbor_out, NULL, PCTRIE_INSERT_NEIGHBOR_GT));
}
/*
@@ -415,14 +420,55 @@
*found_out = NULL;
*neighbor_out = NULL;
return (pctrie_insert_lookup_compound(ptree, val, found_out,
- neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
+ neighbor_out, NULL, PCTRIE_INSERT_NEIGHBOR_LT));
+}
+
+/*
+ * 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, and the address of the pointer to the
+ * newly inserted node.
+ */
+void *
+pctrie_insert_lookup_gt_parent(struct pctrie *ptree, uint64_t *val,
+ uint64_t **found_out, struct pctrie_node **neighbor_out,
+ void **pparent_out)
+{
+ *found_out = NULL;
+ *neighbor_out = NULL;
+ return (pctrie_insert_lookup_compound(ptree, val, found_out,
+ neighbor_out, pparent_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, and the address of the pointer to the
+ * newly inserted node..
+ */
+void *
+pctrie_insert_lookup_lt_parent(struct pctrie *ptree, uint64_t *val,
+ uint64_t **found_out, struct pctrie_node **neighbor_out,
+ void **pparent_out)
+{
+ *found_out = NULL;
+ *neighbor_out = NULL;
+ return (pctrie_insert_lookup_compound(ptree, val, found_out,
+ neighbor_out, pparent_out, PCTRIE_INSERT_NEIGHBOR_LT));
}
/*
* Uses new node to insert key-value pair into the trie at given location.
+ *
+ * With parentp_out set, store the insertion location in the newly allocated
+ * parent of the newly inserted node.
+ *
+ * This procedure is expected to be inlined into callers with extraneous code
+ * optimized out.
*/
-void
-pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val)
+static __inline void
+pctrie_insert_node_compound(void *parentp, struct pctrie_node *parent,
+ uint64_t *val, void **parentp_out)
{
struct pctrie_node *node;
uint64_t index, newind;
@@ -460,7 +506,10 @@
parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);
parent->pn_owner = PCTRIE_COUNT;
parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev);
-
+ if (parentp_out != NULL) {
+ int slot = pctrie_slot(parent, index);
+ *parentp_out = &parent->pn_child[slot];
+ }
/* These writes are not yet visible due to ordering. */
pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
@@ -469,6 +518,28 @@
pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
}
+/*
+ * Wrap pctrie_insert_node_compound to use a 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_compound(parentp, parent, val, NULL);
+}
+
+/*
+ * Wrap pctrie_insert_node_compound to use a new node to insert key-value pair
+ * into the trie at given location, and recover the address of the pointer
+ * that points to the new node, to allow fast replacement.
+ */
+void
+pctrie_insert_node_parent(void *parentp, struct pctrie_node *parent,
+ uint64_t *val, void **parentp_out)
+{
+ pctrie_insert_node_compound(parentp, parent, val, parentp_out);
+}
+
/*
* Returns the value stored at the index. If the index is not present,
* NULL is returned.
@@ -897,6 +968,16 @@
panic("%s: original replacing value not found", __func__);
}
+/*
+ * Given parentp, the address of a pointer to a leaf in the trie, replace the
+ * value that parentp points to with a new one.
+ */
+void
+pctrie_fast_replace(void *parentp, uint64_t *val)
+{
+ pctrie_node_store(parentp, pctrie_toleaf(val), PCTRIE_LOCKED);
+}
+
#ifdef DDB
/*
* Show details about the given node.
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -186,6 +186,70 @@
return (0); \
} \
\
+static __inline __unused int \
+name##_PCTRIE_INSERT_LOOKUP_GE_PARENT(struct pctrie *ptree, \
+ struct type *ptr, struct type **found_out, void **pparent_out) \
+{ \
+ struct pctrie_node *parent, *neighbor; \
+ void *parentp; \
+ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
+ uint64_t *found; \
+ \
+ parentp = pctrie_insert_lookup_gt_parent(ptree, val, &found, \
+ &neighbor, pparent_out); \
+ if (__predict_false(found != NULL)) { \
+ *found_out = name##_PCTRIE_VAL2PTR(found); \
+ return (EEXIST); \
+ } \
+ if (parentp != NULL) { \
+ parent = allocfn(ptree); \
+ if (__predict_false(parent == NULL)) { \
+ *found_out = NULL; \
+ return (ENOMEM); \
+ } \
+ if (neighbor == parentp) \
+ neighbor = parent; \
+ pctrie_insert_node_parent(parentp, parent, val, \
+ pparent_out); \
+ } \
+ found = pctrie_subtree_lookup_gt(neighbor, *val); \
+ *found_out = name##_PCTRIE_VAL2PTR(found); \
+ pctrie_subtree_lookup_gt_assert(neighbor, *val, ptree, found); \
+ return (0); \
+} \
+ \
+static __inline __unused int \
+name##_PCTRIE_INSERT_LOOKUP_LE_PARENT(struct pctrie *ptree, \
+ struct type *ptr, struct type **found_out, void **pparent_out) \
+{ \
+ struct pctrie_node *parent, *neighbor; \
+ void *parentp; \
+ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
+ uint64_t *found; \
+ \
+ parentp = pctrie_insert_lookup_lt_parent(ptree, val, &found, \
+ &neighbor, pparent_out); \
+ if (__predict_false(found != NULL)) { \
+ *found_out = name##_PCTRIE_VAL2PTR(found); \
+ return (EEXIST); \
+ } \
+ if (parentp != NULL) { \
+ parent = allocfn(ptree); \
+ if (__predict_false(parent == NULL)) { \
+ *found_out = NULL; \
+ return (ENOMEM); \
+ } \
+ if (neighbor == parentp) \
+ neighbor = parent; \
+ pctrie_insert_node_parent(parentp, parent, val, \
+ pparent_out); \
+ } \
+ found = pctrie_subtree_lookup_lt(neighbor, *val); \
+ *found_out = name##_PCTRIE_VAL2PTR(found); \
+ pctrie_subtree_lookup_lt_assert(neighbor, *val, ptree, found); \
+ return (0); \
+} \
+ \
static __inline __unused struct type * \
name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
{ \
@@ -227,6 +291,13 @@
} \
\
static __inline __unused void \
+name##_PCTRIE_FAST_REPLACE(void *parentp, struct type *ptr) \
+{ \
+ \
+ pctrie_fast_replace(parentp, name##_PCTRIE_PTR2VAL(ptr)); \
+} \
+ \
+static __inline __unused void \
name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
{ \
uint64_t *val; \
@@ -257,10 +328,21 @@
uint64_t **found_out, struct pctrie_node **neighbor_out);
void *pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
uint64_t **found_out, struct pctrie_node **neighbor_out);
+void *pctrie_insert_lookup_gt_parent(struct pctrie *ptree,
+ uint64_t *val, uint64_t **found_out,
+ struct pctrie_node **neighbor_out,
+ void **pparent_out);
+void *pctrie_insert_lookup_lt_parent(struct pctrie *ptree,
+ uint64_t *val, uint64_t **found_out,
+ struct pctrie_node **neighbor_out,
+ void **pparent_out);
void *pctrie_insert_lookup_strict(struct pctrie *ptree,
uint64_t *val);
void pctrie_insert_node(void *parentp,
struct pctrie_node *parent, uint64_t *val);
+void pctrie_insert_node_parent(void *parentp,
+ struct pctrie_node *parent, uint64_t *val,
+ void **parentp_out);
uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
@@ -272,6 +354,7 @@
uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **killnode);
uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
+void pctrie_fast_replace(void *parentp, uint64_t *val);
uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node,
uint64_t key);
uint64_t *pctrie_subtree_lookup_lt(struct pctrie_node *node,
Index: sys/vm/vm_radix.h
===================================================================
--- sys/vm/vm_radix.h
+++ sys/vm/vm_radix.h
@@ -89,6 +89,30 @@
return (error);
}
+/*
+ * Insert the a dummy page into the vm_radix tree with index as the key.
+ * Panic if the pindex already exists. Return zero on success or a non-zero
+ * error on memory allocation failure. Set the out parameter mpred to the
+ * previous page in the tree as if found by a previous call to
+ * vm_radix_lookup_le with the new page pindex. Set the out parameter
+ * pparent_ptr to the address of the pointer to the dummy page, so that the
+ * dummy page can be replaced directly.
+ */
+static __inline int
+vm_radix_insert_lookup_lt_parent(struct vm_radix *rtree, vm_pindex_t index,
+ vm_page_t *mpred, void **pparent_ptr)
+{
+ struct vm_page page = {.pindex = index};
+ int error;
+
+ error = VM_RADIX_PCTRIE_INSERT_LOOKUP_LE_PARENT(&rtree->rt_trie,
+ &page, mpred, pparent_ptr);
+ if (__predict_false(error == EEXIST))
+ panic("vm_radix_insert_lookup_lt: page already present, %p",
+ *mpred);
+ return (error);
+}
+
/*
* Returns the value stored at the index assuming there is an external lock.
*
@@ -155,8 +179,8 @@
}
/*
- * Replace an existing page in the trie with another one.
- * Panics if there is not an old page in the trie at the new page's index.
+ * Replace an existing page in the trie with another one, after searching for
+ * it. Panics if there is not an old page in the trie at the new page's index.
*/
static __inline vm_page_t
vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage)
@@ -164,5 +188,16 @@
return (VM_RADIX_PCTRIE_REPLACE(&rtree->rt_trie, newpage));
}
+/*
+ * Replace an existing page in the trie with another one, given the address of
+ * the pointer to the existing page. Panics if there is not an old page in the
+ * trie at the new page's index.
+ */
+static __inline void
+vm_radix_fast_replace(void *parentp, vm_page_t newpage)
+{
+ VM_RADIX_PCTRIE_FAST_REPLACE(parentp, newpage);
+}
+
#endif /* _KERNEL */
#endif /* !_VM_RADIX_H_ */

File Metadata

Mime Type
text/plain
Expires
Mon, Jan 20, 5:12 AM (20 h, 48 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
15974796
Default Alt Text
D45510.diff (11 KB)

Event Timeline