Page MenuHomeFreeBSD
Files F144312575

D51060.id159385.diff
No OneTemporary
Actions

D51060.id159385.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));
}
@@ -394,8 +406,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),
+ PCTRIE_LOCKED);
return (NULL);
}
if (__predict_false(pctrie_match_value(node, *val) != NULL)) {
@@ -408,6 +420,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));
}
@@ -632,8 +647,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);
}
/*
@@ -727,14 +746,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 *
@@ -824,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 *
@@ -840,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 *
@@ -925,10 +984,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)) {
*freenode = parent;
- else
+ parent = pctrie_parent(*freenode);
+ } else
*freenode = NULL;
+ pctrie_root_store(ptree, parent);
return (m);
}
@@ -945,7 +1006,11 @@
(uintmax_t)it->index));
if (pctrie_remove(it->ptree, it->node, it->index)) {
*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;
}
@@ -1028,6 +1093,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));
}
@@ -1076,6 +1143,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
@@ -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); \
+ 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); \
+ pctrie_root_store(ptree, parent); \
+ return (retval); \
} \
\
static __inline __unused int \
@@ -191,6 +197,7 @@
parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
found, found_out); \
+ pctrie_root_store(ptree, parent); \
if (retval != 0) \
return (retval); \
found = pctrie_subtree_lookup_lt(ptree, parent, *val); \
@@ -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;
@@ -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
Sun, Feb 8, 7:17 PM (14 h, 34 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
28487737
Default Alt Text
D51060.id159385.diff (9 KB)

Event Timeline