Page MenuHomeFreeBSD
Files F160567016

D51060.id157806.diff
No OneTemporary
Actions

D51060.id157806.diff
View Options

Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -164,6 +164,17 @@
return (pctrie_node_load(pctrie_root(ptree), smr, access));
}
+/*
+ * Set the non-NULL root node for a tree. Assumes that a write lock is held.
+ */
+void
+pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node)
+{
+ if (node != NULL)
+ pctrie_node_store(pctrie_root(ptree), node, PCTRIE_LOCKED);
+}
+
+
/*
* Get the child of a node.
*/
@@ -294,9 +305,9 @@
struct pctrie_node *parent;
int slot;
- parent = node;
- if (parent == NULL)
+ if (node == NULL)
node = pctrie_root_load(ptree, smr, access);
+ parent = pctrie_isleaf(node) ? NULL : node;
/*
* Climb the search path to find the lowest node from which to start the
@@ -335,6 +346,7 @@
node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL,
PCTRIE_LOCKED);
+ pctrie_root_store(ptree, parent);
return (pctrie_match_value(node, index));
}
@@ -382,7 +394,8 @@
*/
static __always_inline void *
_pctrie_insert_lookup(struct pctrie *ptree, struct pctrie_node *parent,
- uint64_t *val, struct pctrie_node **parent_out, uint64_t **found_out)
+ uint64_t *val, struct pctrie_node **parent_out, uint64_t **found_out,
+ bool sync)
{
struct pctrie_node *node;
@@ -394,8 +407,8 @@
pctrie_node_store(pctrie_root(ptree),
pctrie_toleaf(val), PCTRIE_LOCKED);
else
- pctrie_addnode(*parent_out, *val,
- pctrie_toleaf(val), PCTRIE_LOCKED);
+ pctrie_addnode(*parent_out, *val, pctrie_toleaf(val),
+ sync ? PCTRIE_LOCKED : PCTRIE_UNSERIALIZED);
return (NULL);
}
if (__predict_false(pctrie_match_value(node, *val) != NULL)) {
@@ -408,6 +421,9 @@
* children 'node' and 'val'. Return the place that points to 'node'
* now, and will point to to the new branching node later.
*/
+ if (*parent_out == NULL)
+ pctrie_node_store(pctrie_root(ptree), node,
+ PCTRIE_UNSERIALIZED);
return (pctrie_child(ptree, *parent_out, *val));
}
@@ -422,7 +438,8 @@
void *parentp;
uint64_t *found;
- parentp = _pctrie_insert_lookup(ptree, NULL, val, parent_out, &found);
+ parentp = _pctrie_insert_lookup(ptree, NULL, val, parent_out, &found,
+ false);
if (__predict_false(found != NULL))
panic("%s: key %jx is already present", __func__,
(uintmax_t)*val);
@@ -437,7 +454,8 @@
pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
struct pctrie_node **parent_out, uint64_t **found_out)
{
- return (_pctrie_insert_lookup(ptree, NULL, val, parent_out, found_out));
+ return (_pctrie_insert_lookup(ptree, NULL, val, parent_out, found_out,
+ false));
}
/*
@@ -453,7 +471,7 @@
it->index = *val;
res = _pctrie_insert_lookup(it->ptree, it->node, val, &it->node,
- &found);
+ &found, true);
if (__predict_false(found != NULL))
panic("%s: key %jx is already present", __func__,
(uintmax_t)it->index);
@@ -467,7 +485,7 @@
*/
void
pctrie_insert_node(uint64_t *val, struct pctrie_node *parent, void *parentp,
- struct pctrie_node *child)
+ struct pctrie_node *child, bool sync)
{
struct pctrie_node *node;
uint64_t index, newind;
@@ -514,7 +532,8 @@
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_node_store(parentp, child,
+ sync ? PCTRIE_LOCKED : PCTRIE_UNSERIALIZED);
}
/*
@@ -632,8 +651,12 @@
pctrie_lookup_range(struct pctrie *ptree, uint64_t index,
uint64_t *value[], int count)
{
- return (_pctrie_lookup_range(ptree, NULL, index, value, count, NULL,
- NULL, PCTRIE_LOCKED));
+ struct pctrie_node *parent;
+
+ count = _pctrie_lookup_range(ptree, NULL, index, value, count, &parent,
+ NULL, PCTRIE_LOCKED);
+ pctrie_root_store(ptree, parent);
+ return (count);
}
/*
@@ -725,14 +748,43 @@
return (m);
}
+/*
+ * Find first leaf >= index, assuming access is externally synchronized by a
+ * lock, and set root to the parent of that leaf.
+ *
+ * If no such leaf exists, NULL is returned.
+ */
uint64_t *
pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
{
- return (_pctrie_lookup_ge(ptree, NULL, index, NULL, 0));
+ struct pctrie_node *parent;
+ uint64_t *m;
+
+ m = _pctrie_lookup_ge(ptree, NULL, index, &parent, 0);
+ pctrie_root_store(ptree, parent);
+ return (m);
}
/*
- * Find first leaf >= index, and fill iter with the path to the parent of that
+ * Find next leaf > m, assuming access is externally synchronized by a lock, and
+ * set root to the parent of that leaf.
+ *
+ * If no such leaf exists, NULL is returned.
+ */
+uint64_t *
+pctrie_lookup_ge_step(struct pctrie *ptree, uint64_t *m)
+{
+ struct pctrie_node *parent;
+
+ if (*m + 1 == 0)
+ return (NULL);
+ m = _pctrie_lookup_ge(ptree, NULL, *m + 1, &parent, 0);
+ pctrie_root_store(ptree, parent);
+ return (m);
+}
+
+/*
+ * Find first leaf >= index, and set iter->node to the parent of that
* leaf. Return NULL if there is no such leaf less than limit.
*/
uint64_t *
@@ -820,10 +872,21 @@
return (m);
}
+/*
+ * Find first leaf <= index, assuming access is externally synchronized by a
+ * lock, and set root to the parent of that leaf.
+ *
+ * If no such leaf exists, NULL is returned.
+ */
uint64_t *
pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
{
- return (_pctrie_lookup_le(ptree, NULL, index, NULL, 0));
+ struct pctrie_node *parent;
+ uint64_t *m;
+
+ m = _pctrie_lookup_le(ptree, NULL, index, &parent, 0);
+ pctrie_root_store(ptree, parent);
+ return (m);
}
uint64_t *
@@ -836,7 +899,7 @@
}
/*
- * Find first leaf <= index, and fill iter with the path to the parent of that
+ * Find first leaf <= index, and iter->node to the parent of that
* leaf. Return NULL if there is no such leaf greater than limit.
*/
uint64_t *
@@ -873,12 +936,15 @@
* pctrie and save it in *freenode for later disposal.
*/
static bool
-pctrie_remove(struct pctrie *ptree, struct pctrie_node *node, uint64_t index)
+pctrie_remove(struct pctrie *ptree, struct pctrie_node *node, uint64_t index,
+ bool sync)
{
smr_pctnode_t *parentp;
struct pctrie_node *child;
int slot;
+ enum pctrie_access access;
+ access = sync ? PCTRIE_LOCKED : PCTRIE_UNSERIALIZED;
parentp = pctrie_child(ptree, node, index);
if (node == NULL) {
pctrie_node_store(parentp, PCTRIE_NULL, PCTRIE_LOCKED);
@@ -890,7 +956,7 @@
__func__, slot, node));
node->pn_popmap ^= 1 << slot;
if (!powerof2(node->pn_popmap)) {
- pctrie_node_store(parentp, PCTRIE_NULL, PCTRIE_LOCKED);
+ pctrie_node_store(parentp, PCTRIE_NULL, access);
return (false);
}
pctrie_node_store(parentp, PCTRIE_NULL, PCTRIE_UNSERIALIZED);
@@ -903,7 +969,7 @@
if (!pctrie_isleaf(child))
pctrie_setparent(child, node);
parentp = pctrie_child(ptree, node, index);
- pctrie_node_store(parentp, child, PCTRIE_LOCKED);
+ pctrie_node_store(parentp, child, access);
return (true);
}
@@ -921,10 +987,12 @@
node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL,
PCTRIE_LOCKED);
m = pctrie_match_value(node, index);
- if (m != NULL && pctrie_remove(ptree, parent, index))
+ if (m != NULL && pctrie_remove(ptree, parent, index, false)) {
*freenode = parent;
- else
+ parent = pctrie_parent(*freenode);
+ } else
*freenode = NULL;
+ pctrie_root_store(ptree, parent);
return (m);
}
@@ -939,9 +1007,13 @@
it->ptree, it->node, it->index), NULL, PCTRIE_LOCKED), it->index),
("%s: removing value %jx not at iter", __func__,
(uintmax_t)it->index));
- if (pctrie_remove(it->ptree, it->node, it->index)) {
+ if (pctrie_remove(it->ptree, it->node, it->index, true)) {
*freenode = it->node;
- it->node = pctrie_parent(it->node);
+ it->node = pctrie_parent(*freenode);
+ if (*freenode == pctrie_root_load(it->ptree, NULL,
+ PCTRIE_LOCKED))
+ pctrie_node_store(pctrie_root(it->ptree), it->node,
+ PCTRIE_LOCKED);
} else
*freenode = NULL;
}
@@ -1024,6 +1096,8 @@
callback(pctrie_toptr(node, keyoff), arg);
return (NULL);
}
+ while (pctrie_parent(node) != NULL)
+ node = pctrie_parent(node);
*pnode = node;
return (pctrie_reclaim_prune(pnode, NULL, callback, keyoff, arg));
}
@@ -1072,6 +1146,7 @@
panic("%s: original replacing value not found", __func__);
pctrie_node_store(pctrie_child(ptree, parent, *newval),
pctrie_toleaf(newval), PCTRIE_LOCKED);
+ pctrie_root_store(ptree, parent);
return (m);
}
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -131,7 +131,7 @@
static __inline __unused int \
name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, uint64_t *val, \
struct pctrie_node **parent, void *parentp, \
- uint64_t *found, struct type **found_out) \
+ uint64_t *found, struct type **found_out, bool sync) \
{ \
struct pctrie_node *child; \
\
@@ -146,7 +146,7 @@
*found_out = NULL; \
return (ENOMEM); \
} \
- pctrie_insert_node(val, *parent, parentp, child); \
+ pctrie_insert_node(val, *parent, parentp, child, sync); \
*parent = child; \
} \
return (0); \
@@ -158,10 +158,13 @@
void *parentp; \
struct pctrie_node *parent; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
+ int retval; \
\
parentp = pctrie_insert_lookup_strict(ptree, val, &parent); \
- return (name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
- NULL, NULL)); \
+ retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,\
+ NULL, NULL, false); \
+ pctrie_root_store(ptree, parent); \
+ return (retval); \
} \
\
static __inline __unused int \
@@ -172,10 +175,13 @@
struct pctrie_node *parent; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
uint64_t *found; \
+ int retval; \
\
parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
- return (name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
- found, found_out_opt)); \
+ retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,\
+ found, found_out_opt, false); \
+ pctrie_root_store(ptree, parent); \
+ return (retval); \
} \
\
static __inline __unused int \
@@ -190,7 +196,8 @@
\
parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
- found, found_out); \
+ found, found_out, false); \
+ pctrie_root_store(ptree, parent); \
if (retval != 0) \
return (retval); \
found = pctrie_subtree_lookup_lt(ptree, parent, *val); \
@@ -206,7 +213,7 @@
\
parentp = pctrie_iter_insert_lookup(it, val); \
return (name##_PCTRIE_INSERT_BASE(it->ptree, val, &it->node, \
- parentp, NULL, NULL)); \
+ parentp, NULL, NULL, true)); \
} \
\
static __inline __unused struct type * \
@@ -254,6 +261,14 @@
return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \
} \
\
+static __inline __unused struct type * \
+name##_PCTRIE_LOOKUP_GE_STEP(struct pctrie *ptree, struct type *ptr) \
+{ \
+ \
+ return name##_PCTRIE_VAL2PTR( \
+ pctrie_lookup_ge_step(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
+} \
+ \
static __inline __unused void \
name##_PCTRIE_RECLAIM(struct pctrie *ptree) \
{ \
@@ -359,23 +374,6 @@
} \
\
static __inline __unused void \
-name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
-{ \
- struct pctrie_node *freenode; \
- \
- pctrie_iter_remove(it, &freenode); \
- name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
-} \
- \
-static __inline __unused struct type * \
-name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
-{ \
- \
- return name##_PCTRIE_VAL2PTR( \
- pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
-} \
- \
-static __inline __unused void \
name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
{ \
uint64_t *val; \
@@ -396,6 +394,23 @@
val = pctrie_remove_lookup(ptree, key, &freenode); \
name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
return name##_PCTRIE_VAL2PTR(val); \
+} \
+ \
+static __inline __unused void \
+name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
+{ \
+ struct pctrie_node *freenode; \
+ \
+ pctrie_iter_remove(it, &freenode); \
+ name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
+} \
+ \
+static __inline __unused struct type * \
+name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
+{ \
+ \
+ return name##_PCTRIE_VAL2PTR( \
+ pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
}
struct pctrie_iter;
@@ -404,7 +419,7 @@
void *pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val,
struct pctrie_node **parent_out);
void pctrie_insert_node(uint64_t *val, struct pctrie_node *parent,
- void *parentp, struct pctrie_node *child);
+ void *parentp, struct pctrie_node *child, bool sync);
uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
smr_t smr);
@@ -421,6 +436,7 @@
void *pctrie_iter_insert_lookup(struct pctrie_iter *it,
uint64_t *val);
uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
+uint64_t *pctrie_lookup_ge_step(struct pctrie *ptree, uint64_t *m);
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);
uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
@@ -438,6 +454,8 @@
pctrie_cb_t callback, int keyoff, void *arg);
uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **killnode);
+void pctrie_root_store(struct pctrie *ptree,
+ struct pctrie_node *node);
void pctrie_iter_remove(struct pctrie_iter *it,
struct pctrie_node **freenode);
uint64_t *pctrie_iter_value(struct pctrie_iter *it);

File Metadata

Mime Type
text/plain
Expires
Fri, Jun 26, 6:29 PM (2 h, 31 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
34365220
Default Alt Text
D51060.id157806.diff (14 KB)

Event Timeline