Changeset View
Changeset View
Standalone View
Standalone View
sys/kern/subr_pctrie.c
Show First 20 Lines • Show All 49 Lines • ▼ Show 20 Lines | |||||
__FBSDID("$FreeBSD$"); | __FBSDID("$FreeBSD$"); | ||||
#include "opt_ddb.h" | #include "opt_ddb.h" | ||||
#include <sys/param.h> | #include <sys/param.h> | ||||
#include <sys/systm.h> | #include <sys/systm.h> | ||||
#include <sys/kernel.h> | #include <sys/kernel.h> | ||||
#include <sys/pctrie.h> | #include <sys/pctrie.h> | ||||
#include <sys/proc.h> /* smr.h depends on struct thread. */ | |||||
#include <sys/smr.h> | |||||
#include <sys/smr_types.h> | |||||
#ifdef DDB | #ifdef DDB | ||||
#include <ddb/ddb.h> | #include <ddb/ddb.h> | ||||
#endif | #endif | ||||
#define PCTRIE_MASK (PCTRIE_COUNT - 1) | #define PCTRIE_MASK (PCTRIE_COUNT - 1) | ||||
#define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1) | #define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1) | ||||
/* Flag bits stored in node pointers. */ | /* Flag bits stored in node pointers. */ | ||||
#define PCTRIE_ISLEAF 0x1 | #define PCTRIE_ISLEAF 0x1 | ||||
#define PCTRIE_FLAGS 0x1 | #define PCTRIE_FLAGS 0x1 | ||||
#define PCTRIE_PAD PCTRIE_FLAGS | #define PCTRIE_PAD PCTRIE_FLAGS | ||||
/* Returns one unit associated with specified level. */ | /* Returns one unit associated with specified level. */ | ||||
#define PCTRIE_UNITLEVEL(lev) \ | #define PCTRIE_UNITLEVEL(lev) \ | ||||
((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) | ((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) | ||||
struct pctrie_node; | |||||
typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t; | |||||
struct pctrie_node { | struct pctrie_node { | ||||
uint64_t pn_owner; /* Owner of record. */ | uint64_t pn_owner; /* Owner of record. */ | ||||
uint16_t pn_count; /* Valid children. */ | uint16_t pn_count; /* Valid children. */ | ||||
uint16_t pn_clev; /* Current level. */ | uint8_t pn_clev; /* Current level. */ | ||||
void *pn_child[PCTRIE_COUNT]; /* Child nodes. */ | int8_t pn_last; /* Zero last ptr. */ | ||||
smr_pctnode_t pn_child[PCTRIE_COUNT]; /* Child nodes. */ | |||||
}; | }; | ||||
enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED }; | |||||
static __inline void pctrie_node_store(smr_pctnode_t *p, void *val, | |||||
enum pctrie_access access); | |||||
/* | /* | ||||
* Allocate a node. Pre-allocation should ensure that the request | * Allocate a node. Pre-allocation should ensure that the request | ||||
* will always be satisfied. | * will always be satisfied. | ||||
*/ | */ | ||||
static __inline struct pctrie_node * | static struct pctrie_node * | ||||
pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, | pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, | ||||
uint16_t count, uint16_t clevel) | uint16_t count, uint16_t clevel) | ||||
{ | { | ||||
struct pctrie_node *node; | struct pctrie_node *node; | ||||
node = allocfn(ptree); | node = allocfn(ptree); | ||||
if (node == NULL) | if (node == NULL) | ||||
return (NULL); | return (NULL); | ||||
markj: I think the comment from vm_radix_node_get() should be duplicated as well. | |||||
Done Inline ActionsSure, will do. cem: Sure, will do. | |||||
/* | |||||
* We want to clear the last child pointer after the final section | |||||
* has exited so lookup can not return false negatives. It is done | |||||
* here because it will be cache-cold in the dtor callback. | |||||
*/ | |||||
if (node->pn_last != 0) { | |||||
pctrie_node_store(&node->pn_child[node->pn_last - 1], NULL, | |||||
PCTRIE_UNSERIALIZED); | |||||
node->pn_last = 0; | |||||
} | |||||
node->pn_owner = owner; | node->pn_owner = owner; | ||||
node->pn_count = count; | node->pn_count = count; | ||||
node->pn_clev = clevel; | node->pn_clev = clevel; | ||||
return (node); | return (node); | ||||
} | } | ||||
/* | /* | ||||
* Free radix node. | * Free radix node. | ||||
*/ | */ | ||||
static __inline void | static __inline void | ||||
pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, | pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, | ||||
pctrie_free_t freefn) | pctrie_free_t freefn, int8_t last) | ||||
{ | { | ||||
#ifdef INVARIANTS | #ifdef INVARIANTS | ||||
int slot; | int slot; | ||||
KASSERT(node->pn_count == 0, | KASSERT(node->pn_count == 0, | ||||
("pctrie_node_put: node %p has %d children", node, | ("pctrie_node_put: node %p has %d children", node, | ||||
node->pn_count)); | node->pn_count)); | ||||
for (slot = 0; slot < PCTRIE_COUNT; slot++) | for (slot = 0; slot < PCTRIE_COUNT; slot++) { | ||||
KASSERT(node->pn_child[slot] == NULL, | if (slot == last) | ||||
("pctrie_node_put: node %p has a child", node)); | continue; | ||||
KASSERT(smr_unserialized_load(&node->pn_child[slot], true) == | |||||
NULL, ("pctrie_node_put: node %p has a child", node)); | |||||
} | |||||
#endif | #endif | ||||
node->pn_last = last + 1; | |||||
freefn(ptree, node); | freefn(ptree, node); | ||||
} | } | ||||
/* | /* | ||||
* Return the position in the array for a given level. | * Return the position in the array for a given level. | ||||
*/ | */ | ||||
static __inline int | static __inline int | ||||
pctrie_slot(uint64_t index, uint16_t level) | pctrie_slot(uint64_t index, uint16_t level) | ||||
Show All 12 Lines | pctrie_trimkey(uint64_t index, uint16_t level) | ||||
if (level > 0) { | if (level > 0) { | ||||
ret >>= level * PCTRIE_WIDTH; | ret >>= level * PCTRIE_WIDTH; | ||||
ret <<= level * PCTRIE_WIDTH; | ret <<= level * PCTRIE_WIDTH; | ||||
} | } | ||||
return (ret); | return (ret); | ||||
} | } | ||||
/* | /* | ||||
* Get the root node for a tree. | * Fetch a node pointer from a slot. | ||||
*/ | */ | ||||
static __inline struct pctrie_node * | static __inline struct pctrie_node * | ||||
pctrie_getroot(struct pctrie *ptree) | pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access) | ||||
{ | { | ||||
switch (access) { | |||||
case PCTRIE_UNSERIALIZED: | |||||
return (smr_unserialized_load(p, true)); | |||||
case PCTRIE_LOCKED: | |||||
return (smr_serialized_load(p, true)); | |||||
case PCTRIE_SMR: | |||||
return (smr_entered_load(p, smr)); | |||||
} | |||||
__assert_unreachable(); | |||||
} | |||||
return ((struct pctrie_node *)ptree->pt_root); | static __inline void | ||||
pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access) | |||||
{ | |||||
switch (access) { | |||||
case PCTRIE_UNSERIALIZED: | |||||
smr_unserialized_store(p, v, true); | |||||
break; | |||||
case PCTRIE_LOCKED: | |||||
smr_serialized_store(p, v, true); | |||||
break; | |||||
case PCTRIE_SMR: | |||||
panic("%s: Not supported in SMR section.", __func__); | |||||
break; | |||||
default: | |||||
__assert_unreachable(); | |||||
break; | |||||
} | } | ||||
} | |||||
/* | /* | ||||
* Get the root node for a tree. | |||||
*/ | |||||
static __inline struct pctrie_node * | |||||
pctrie_root_load(struct pctrie *ptree, smr_t smr, enum pctrie_access access) | |||||
{ | |||||
return (pctrie_node_load((smr_pctnode_t *)&ptree->pt_root, smr, access)); | |||||
} | |||||
/* | |||||
* Set the root node for a tree. | * Set the root node for a tree. | ||||
*/ | */ | ||||
static __inline void | static __inline void | ||||
pctrie_setroot(struct pctrie *ptree, struct pctrie_node *node) | pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node, | ||||
enum pctrie_access access) | |||||
{ | { | ||||
pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access); | |||||
ptree->pt_root = (uintptr_t)node; | |||||
} | } | ||||
/* | /* | ||||
* Returns TRUE if the specified node is a leaf and FALSE otherwise. | * Returns TRUE if the specified node is a leaf and FALSE otherwise. | ||||
*/ | */ | ||||
static __inline bool | static __inline bool | ||||
pctrie_isleaf(struct pctrie_node *node) | pctrie_isleaf(struct pctrie_node *node) | ||||
{ | { | ||||
Show All 11 Lines | pctrie_toval(struct pctrie_node *node) | ||||
return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); | return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); | ||||
} | } | ||||
/* | /* | ||||
* Adds the val as a child of the provided node. | * Adds the val as a child of the provided node. | ||||
*/ | */ | ||||
static __inline void | static __inline void | ||||
pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, | pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, | ||||
uint64_t *val) | uint64_t *val, enum pctrie_access access) | ||||
{ | { | ||||
int slot; | int slot; | ||||
slot = pctrie_slot(index, clev); | slot = pctrie_slot(index, clev); | ||||
node->pn_child[slot] = (void *)((uintptr_t)val | PCTRIE_ISLEAF); | pctrie_node_store(&node->pn_child[slot], | ||||
(void *)((uintptr_t)val | PCTRIE_ISLEAF), access); | |||||
} | } | ||||
/* | /* | ||||
* Returns the slot where two keys differ. | * Returns the slot where two keys differ. | ||||
* It cannot accept 2 equal keys. | * It cannot accept 2 equal keys. | ||||
*/ | */ | ||||
static __inline uint16_t | static __inline uint16_t | ||||
pctrie_keydiff(uint64_t index1, uint64_t index2) | pctrie_keydiff(uint64_t index1, uint64_t index2) | ||||
Show All 27 Lines | |||||
/* | /* | ||||
* Internal helper for pctrie_reclaim_allnodes(). | * Internal helper for pctrie_reclaim_allnodes(). | ||||
* This function is recursive. | * This function is recursive. | ||||
*/ | */ | ||||
static void | static void | ||||
pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, | pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, | ||||
pctrie_free_t freefn) | pctrie_free_t freefn) | ||||
{ | { | ||||
struct pctrie_node *child; | |||||
int slot; | int slot; | ||||
KASSERT(node->pn_count <= PCTRIE_COUNT, | KASSERT(node->pn_count <= PCTRIE_COUNT, | ||||
("pctrie_reclaim_allnodes_int: bad count in node %p", node)); | ("pctrie_reclaim_allnodes_int: bad count in node %p", node)); | ||||
for (slot = 0; node->pn_count != 0; slot++) { | for (slot = 0; node->pn_count != 0; slot++) { | ||||
if (node->pn_child[slot] == NULL) | child = pctrie_node_load(&node->pn_child[slot], NULL, | ||||
PCTRIE_UNSERIALIZED); | |||||
if (child == NULL) | |||||
continue; | continue; | ||||
if (!pctrie_isleaf(node->pn_child[slot])) | if (!pctrie_isleaf(child)) | ||||
pctrie_reclaim_allnodes_int(ptree, | pctrie_reclaim_allnodes_int(ptree, child, freefn); | ||||
node->pn_child[slot], freefn); | pctrie_node_store(&node->pn_child[slot], NULL, | ||||
node->pn_child[slot] = NULL; | PCTRIE_UNSERIALIZED); | ||||
node->pn_count--; | node->pn_count--; | ||||
} | } | ||||
pctrie_node_put(ptree, node, freefn); | pctrie_node_put(ptree, node, freefn, -1); | ||||
} | } | ||||
/* | /* | ||||
* pctrie node zone initializer. | * pctrie node zone initializer. | ||||
*/ | */ | ||||
int | int | ||||
pctrie_zone_init(void *mem, int size __unused, int flags __unused) | pctrie_zone_init(void *mem, int size __unused, int flags __unused) | ||||
{ | { | ||||
struct pctrie_node *node; | struct pctrie_node *node; | ||||
node = mem; | node = mem; | ||||
node->pn_last = 0; | |||||
memset(node->pn_child, 0, sizeof(node->pn_child)); | memset(node->pn_child, 0, sizeof(node->pn_child)); | ||||
return (0); | return (0); | ||||
} | } | ||||
size_t | size_t | ||||
pctrie_node_size(void) | pctrie_node_size(void) | ||||
{ | { | ||||
return (sizeof(struct pctrie_node)); | return (sizeof(struct pctrie_node)); | ||||
} | } | ||||
/* | /* | ||||
* Inserts the key-value pair into the trie. | * Inserts the key-value pair into the trie. | ||||
* Panics if the key already exists. | * Panics if the key already exists. | ||||
*/ | */ | ||||
int | int | ||||
pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) | pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) | ||||
{ | { | ||||
uint64_t index, newind; | uint64_t index, newind; | ||||
void **parentp; | |||||
struct pctrie_node *node, *tmp; | struct pctrie_node *node, *tmp; | ||||
smr_pctnode_t *parentp; | |||||
uint64_t *m; | uint64_t *m; | ||||
int slot; | int slot; | ||||
uint16_t clev; | uint16_t clev; | ||||
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_getroot(ptree); | node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); | ||||
if (node == NULL) { | if (node == NULL) { | ||||
ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF; | ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF; | ||||
return (0); | return (0); | ||||
} | } | ||||
parentp = (void **)&ptree->pt_root; | parentp = (smr_pctnode_t *)&ptree->pt_root; | ||||
for (;;) { | for (;;) { | ||||
if (pctrie_isleaf(node)) { | if (pctrie_isleaf(node)) { | ||||
m = pctrie_toval(node); | m = pctrie_toval(node); | ||||
if (*m == index) | if (*m == index) | ||||
panic("%s: key %jx is already present", | panic("%s: key %jx is already present", | ||||
__func__, (uintmax_t)index); | __func__, (uintmax_t)index); | ||||
clev = pctrie_keydiff(*m, index); | clev = pctrie_keydiff(*m, index); | ||||
tmp = pctrie_node_get(ptree, allocfn, | tmp = pctrie_node_get(ptree, allocfn, | ||||
pctrie_trimkey(index, clev + 1), 2, clev); | pctrie_trimkey(index, clev + 1), 2, clev); | ||||
if (tmp == NULL) | if (tmp == NULL) | ||||
return (ENOMEM); | return (ENOMEM); | ||||
*parentp = tmp; | /* These writes are not yet visible due to ordering. */ | ||||
pctrie_addval(tmp, index, clev, val); | pctrie_addval(tmp, index, clev, val, | ||||
pctrie_addval(tmp, *m, clev, m); | PCTRIE_UNSERIALIZED); | ||||
pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED); | |||||
/* Synchronize to make leaf visible. */ | |||||
pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); | |||||
return (0); | return (0); | ||||
} else if (pctrie_keybarr(node, index)) | } else if (pctrie_keybarr(node, index)) | ||||
break; | break; | ||||
slot = pctrie_slot(index, node->pn_clev); | slot = pctrie_slot(index, node->pn_clev); | ||||
if (node->pn_child[slot] == NULL) { | parentp = &node->pn_child[slot]; | ||||
tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); | |||||
if (tmp == NULL) { | |||||
node->pn_count++; | node->pn_count++; | ||||
pctrie_addval(node, index, node->pn_clev, val); | pctrie_addval(node, index, node->pn_clev, val, | ||||
PCTRIE_LOCKED); | |||||
return (0); | return (0); | ||||
} | } | ||||
parentp = &node->pn_child[slot]; | node = tmp; | ||||
node = node->pn_child[slot]; | |||||
} | } | ||||
/* | /* | ||||
* A new node is needed because the right insertion level is reached. | * A new node is needed because the right insertion level is reached. | ||||
* Setup the new intermediate node and add the 2 children: the | * Setup the new intermediate node and add the 2 children: the | ||||
* new object and the older edge. | * new object and the older edge. | ||||
*/ | */ | ||||
newind = node->pn_owner; | newind = node->pn_owner; | ||||
clev = pctrie_keydiff(newind, index); | clev = pctrie_keydiff(newind, index); | ||||
tmp = pctrie_node_get(ptree, allocfn, | tmp = pctrie_node_get(ptree, allocfn, | ||||
pctrie_trimkey(index, clev + 1), 2, clev); | pctrie_trimkey(index, clev + 1), 2, clev); | ||||
if (tmp == NULL) | if (tmp == NULL) | ||||
return (ENOMEM); | return (ENOMEM); | ||||
*parentp = tmp; | |||||
pctrie_addval(tmp, index, clev, val); | |||||
slot = pctrie_slot(newind, clev); | slot = pctrie_slot(newind, clev); | ||||
tmp->pn_child[slot] = node; | /* These writes are not yet visible due to ordering. */ | ||||
pctrie_addval(tmp, index, clev, val, PCTRIE_UNSERIALIZED); | |||||
pctrie_node_store(&tmp->pn_child[slot], node, PCTRIE_UNSERIALIZED); | |||||
/* Synchronize to make the above visible. */ | |||||
pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); | |||||
return (0); | return (0); | ||||
} | } | ||||
/* | /* | ||||
* Returns the value stored at the index. If the index is not present, | * Returns the value stored at the index. If the index is not present, | ||||
* NULL is returned. | * NULL is returned. | ||||
*/ | */ | ||||
uint64_t * | static __always_inline uint64_t * | ||||
pctrie_lookup(struct pctrie *ptree, uint64_t index) | _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, | ||||
enum pctrie_access access) | |||||
{ | { | ||||
struct pctrie_node *node; | struct pctrie_node *node; | ||||
uint64_t *m; | uint64_t *m; | ||||
int slot; | int slot; | ||||
node = pctrie_getroot(ptree); | node = pctrie_root_load(ptree, smr, access); | ||||
while (node != NULL) { | while (node != NULL) { | ||||
if (pctrie_isleaf(node)) { | if (pctrie_isleaf(node)) { | ||||
m = pctrie_toval(node); | m = pctrie_toval(node); | ||||
if (*m == index) | if (*m == index) | ||||
return (m); | return (m); | ||||
else | |||||
break; | break; | ||||
} else if (pctrie_keybarr(node, index)) | } | ||||
if (pctrie_keybarr(node, index)) | |||||
break; | break; | ||||
slot = pctrie_slot(index, node->pn_clev); | slot = pctrie_slot(index, node->pn_clev); | ||||
node = node->pn_child[slot]; | node = pctrie_node_load(&node->pn_child[slot], smr, access); | ||||
} | } | ||||
return (NULL); | return (NULL); | ||||
} | } | ||||
/* | /* | ||||
* Look up the nearest entry at a position bigger than or equal to index. | * Returns the value stored at the index, assuming access is externally | ||||
* synchronized by a lock. | |||||
* | |||||
* If the index is not present, NULL is returned. | |||||
*/ | */ | ||||
uint64_t * | uint64_t * | ||||
pctrie_lookup(struct pctrie *ptree, uint64_t index) | |||||
{ | |||||
return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED)); | |||||
} | |||||
/* | |||||
* Returns the value stored at the index without requiring an external lock. | |||||
* | |||||
* If the index is not present, NULL is returned. | |||||
*/ | |||||
uint64_t * | |||||
pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr) | |||||
{ | |||||
uint64_t *res; | |||||
smr_enter(smr); | |||||
res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR); | |||||
smr_exit(smr); | |||||
return (res); | |||||
} | |||||
/* | |||||
* Look up the nearest entry at a position bigger than or equal to index, | |||||
* assuming access is externally synchronized by a lock. | |||||
*/ | |||||
uint64_t * | |||||
pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) | pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) | ||||
{ | { | ||||
struct pctrie_node *stack[PCTRIE_LIMIT]; | struct pctrie_node *stack[PCTRIE_LIMIT]; | ||||
uint64_t inc; | uint64_t inc; | ||||
uint64_t *m; | uint64_t *m; | ||||
struct pctrie_node *child, *node; | struct pctrie_node *child, *node; | ||||
#ifdef INVARIANTS | #ifdef INVARIANTS | ||||
int loops = 0; | int loops = 0; | ||||
#endif | #endif | ||||
unsigned tos; | unsigned tos; | ||||
int slot; | int slot; | ||||
node = pctrie_getroot(ptree); | node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); | ||||
if (node == NULL) | if (node == NULL) | ||||
return (NULL); | return (NULL); | ||||
else if (pctrie_isleaf(node)) { | else if (pctrie_isleaf(node)) { | ||||
m = pctrie_toval(node); | m = pctrie_toval(node); | ||||
if (*m >= index) | if (*m >= index) | ||||
return (m); | return (m); | ||||
else | else | ||||
return (NULL); | return (NULL); | ||||
} | } | ||||
tos = 0; | tos = 0; | ||||
for (;;) { | for (;;) { | ||||
/* | /* | ||||
* If the keys differ before the current bisection node, | * If the keys differ before the current bisection node, | ||||
* then the search key might rollback to the earliest | * then the search key might rollback to the earliest | ||||
* available bisection node or to the smallest key | * available bisection node or to the smallest key | ||||
* in the current node (if the owner is bigger than the | * in the current node (if the owner is greater than the | ||||
* search key). | * search key). | ||||
*/ | */ | ||||
if (pctrie_keybarr(node, index)) { | if (pctrie_keybarr(node, index)) { | ||||
if (index > node->pn_owner) { | if (index > node->pn_owner) { | ||||
ascend: | ascend: | ||||
KASSERT(++loops < 1000, | KASSERT(++loops < 1000, | ||||
("pctrie_lookup_ge: too many loops")); | ("pctrie_lookup_ge: too many loops")); | ||||
Show All 18 Lines | ascend: | ||||
node->pn_clev); | node->pn_clev); | ||||
index += PCTRIE_UNITLEVEL(node->pn_clev); | index += PCTRIE_UNITLEVEL(node->pn_clev); | ||||
} else | } else | ||||
index = node->pn_owner; | index = node->pn_owner; | ||||
KASSERT(!pctrie_keybarr(node, index), | KASSERT(!pctrie_keybarr(node, index), | ||||
("pctrie_lookup_ge: keybarr failed")); | ("pctrie_lookup_ge: keybarr failed")); | ||||
} | } | ||||
slot = pctrie_slot(index, node->pn_clev); | slot = pctrie_slot(index, node->pn_clev); | ||||
child = node->pn_child[slot]; | child = pctrie_node_load(&node->pn_child[slot], NULL, | ||||
PCTRIE_LOCKED); | |||||
if (pctrie_isleaf(child)) { | if (pctrie_isleaf(child)) { | ||||
m = pctrie_toval(child); | m = pctrie_toval(child); | ||||
if (*m >= index) | if (*m >= index) | ||||
return (m); | return (m); | ||||
} else if (child != NULL) | } else if (child != NULL) | ||||
goto descend; | goto descend; | ||||
/* | /* | ||||
* Look for an available edge or val within the current | * Look for an available edge or val within the current | ||||
* bisection node. | * bisection node. | ||||
*/ | */ | ||||
if (slot < (PCTRIE_COUNT - 1)) { | if (slot < (PCTRIE_COUNT - 1)) { | ||||
inc = PCTRIE_UNITLEVEL(node->pn_clev); | inc = PCTRIE_UNITLEVEL(node->pn_clev); | ||||
index = pctrie_trimkey(index, node->pn_clev); | index = pctrie_trimkey(index, node->pn_clev); | ||||
do { | do { | ||||
index += inc; | index += inc; | ||||
slot++; | slot++; | ||||
child = node->pn_child[slot]; | child = pctrie_node_load(&node->pn_child[slot], | ||||
NULL, PCTRIE_LOCKED); | |||||
if (pctrie_isleaf(child)) { | if (pctrie_isleaf(child)) { | ||||
m = pctrie_toval(child); | m = pctrie_toval(child); | ||||
if (*m >= index) | if (*m >= index) | ||||
return (m); | return (m); | ||||
} else if (child != NULL) | } else if (child != NULL) | ||||
goto descend; | goto descend; | ||||
} while (slot < (PCTRIE_COUNT - 1)); | } while (slot < (PCTRIE_COUNT - 1)); | ||||
} | } | ||||
KASSERT(child == NULL || pctrie_isleaf(child), | KASSERT(child == NULL || pctrie_isleaf(child), | ||||
("pctrie_lookup_ge: child is radix node")); | ("pctrie_lookup_ge: child is radix node")); | ||||
/* | /* | ||||
* If a value or edge bigger than the search slot is not found | * If a value or edge greater than the search slot is not found | ||||
* in the current node, ascend to the next higher-level node. | * in the current node, ascend to the next higher-level node. | ||||
*/ | */ | ||||
goto ascend; | goto ascend; | ||||
descend: | descend: | ||||
KASSERT(node->pn_clev > 0, | KASSERT(node->pn_clev > 0, | ||||
("pctrie_lookup_ge: pushing leaf's parent")); | ("pctrie_lookup_ge: pushing leaf's parent")); | ||||
KASSERT(tos < PCTRIE_LIMIT, | KASSERT(tos < PCTRIE_LIMIT, | ||||
("pctrie_lookup_ge: stack overflow")); | ("pctrie_lookup_ge: stack overflow")); | ||||
stack[tos++] = node; | stack[tos++] = node; | ||||
node = child; | node = child; | ||||
} | } | ||||
} | } | ||||
/* | /* | ||||
* Look up the nearest entry at a position less than or equal to index. | * Look up the nearest entry at a position less than or equal to index, | ||||
* assuming access is externally synchronized by a lock. | |||||
*/ | */ | ||||
uint64_t * | uint64_t * | ||||
pctrie_lookup_le(struct pctrie *ptree, uint64_t index) | pctrie_lookup_le(struct pctrie *ptree, uint64_t index) | ||||
{ | { | ||||
struct pctrie_node *stack[PCTRIE_LIMIT]; | struct pctrie_node *stack[PCTRIE_LIMIT]; | ||||
uint64_t inc; | uint64_t inc; | ||||
uint64_t *m; | uint64_t *m; | ||||
struct pctrie_node *child, *node; | struct pctrie_node *child, *node; | ||||
#ifdef INVARIANTS | #ifdef INVARIANTS | ||||
int loops = 0; | int loops = 0; | ||||
#endif | #endif | ||||
unsigned tos; | unsigned tos; | ||||
int slot; | int slot; | ||||
node = pctrie_getroot(ptree); | node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); | ||||
if (node == NULL) | if (node == NULL) | ||||
return (NULL); | return (NULL); | ||||
else if (pctrie_isleaf(node)) { | else if (pctrie_isleaf(node)) { | ||||
m = pctrie_toval(node); | m = pctrie_toval(node); | ||||
if (*m <= index) | if (*m <= index) | ||||
return (m); | return (m); | ||||
else | else | ||||
return (NULL); | return (NULL); | ||||
Show All 36 Lines | ascend: | ||||
index = pctrie_trimkey(index, | index = pctrie_trimkey(index, | ||||
node->pn_clev); | node->pn_clev); | ||||
} | } | ||||
index--; | index--; | ||||
KASSERT(!pctrie_keybarr(node, index), | KASSERT(!pctrie_keybarr(node, index), | ||||
("pctrie_lookup_le: keybarr failed")); | ("pctrie_lookup_le: keybarr failed")); | ||||
} | } | ||||
slot = pctrie_slot(index, node->pn_clev); | slot = pctrie_slot(index, node->pn_clev); | ||||
child = node->pn_child[slot]; | child = pctrie_node_load(&node->pn_child[slot], NULL, | ||||
PCTRIE_LOCKED); | |||||
if (pctrie_isleaf(child)) { | if (pctrie_isleaf(child)) { | ||||
m = pctrie_toval(child); | m = pctrie_toval(child); | ||||
if (*m <= index) | if (*m <= index) | ||||
return (m); | return (m); | ||||
} else if (child != NULL) | } else if (child != NULL) | ||||
goto descend; | goto descend; | ||||
/* | /* | ||||
* Look for an available edge or value within the current | * Look for an available edge or value within the current | ||||
* bisection node. | * bisection node. | ||||
*/ | */ | ||||
if (slot > 0) { | if (slot > 0) { | ||||
inc = PCTRIE_UNITLEVEL(node->pn_clev); | inc = PCTRIE_UNITLEVEL(node->pn_clev); | ||||
index |= inc - 1; | index |= inc - 1; | ||||
do { | do { | ||||
index -= inc; | index -= inc; | ||||
slot--; | slot--; | ||||
child = node->pn_child[slot]; | child = pctrie_node_load(&node->pn_child[slot], | ||||
NULL, PCTRIE_LOCKED); | |||||
if (pctrie_isleaf(child)) { | if (pctrie_isleaf(child)) { | ||||
m = pctrie_toval(child); | m = pctrie_toval(child); | ||||
if (*m <= index) | if (*m <= index) | ||||
return (m); | return (m); | ||||
} else if (child != NULL) | } else if (child != NULL) | ||||
goto descend; | goto descend; | ||||
} while (slot > 0); | } while (slot > 0); | ||||
} | } | ||||
Show All 17 Lines | |||||
/* | /* | ||||
* Remove the specified index from the tree. | * Remove the specified index from the tree. | ||||
* Panics if the key is not present. | * Panics if the key is not present. | ||||
*/ | */ | ||||
void | void | ||||
pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) | pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) | ||||
{ | { | ||||
struct pctrie_node *node, *parent; | struct pctrie_node *node, *parent, *tmp; | ||||
Not Done Inline ActionsWouldn't child be a better name than tmp? Ditto below. markj: Wouldn't `child` be a better name than `tmp`? Ditto below. | |||||
Done Inline Actionstmp matches vm_radix_remove(). As the codebases are mostly complete duplicates, I'd prefer to keep these in sync. cem: `tmp` matches `vm_radix_remove()`. As the codebases are mostly complete duplicates, I'd prefer… | |||||
uint64_t *m; | uint64_t *m; | ||||
int i, slot; | int i, slot; | ||||
node = pctrie_getroot(ptree); | node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); | ||||
if (pctrie_isleaf(node)) { | if (pctrie_isleaf(node)) { | ||||
m = pctrie_toval(node); | m = pctrie_toval(node); | ||||
if (*m != index) | if (*m != index) | ||||
panic("%s: invalid key found", __func__); | panic("%s: invalid key found", __func__); | ||||
pctrie_setroot(ptree, NULL); | pctrie_root_store(ptree, NULL, PCTRIE_LOCKED); | ||||
return; | return; | ||||
} | } | ||||
parent = NULL; | parent = NULL; | ||||
for (;;) { | for (;;) { | ||||
if (node == NULL) | if (node == NULL) | ||||
panic("pctrie_remove: impossible to locate the key"); | panic("pctrie_remove: impossible to locate the key"); | ||||
slot = pctrie_slot(index, node->pn_clev); | slot = pctrie_slot(index, node->pn_clev); | ||||
if (pctrie_isleaf(node->pn_child[slot])) { | tmp = pctrie_node_load(&node->pn_child[slot], NULL, | ||||
m = pctrie_toval(node->pn_child[slot]); | PCTRIE_LOCKED); | ||||
if (pctrie_isleaf(tmp)) { | |||||
m = pctrie_toval(tmp); | |||||
if (*m != index) | if (*m != index) | ||||
panic("%s: invalid key found", __func__); | panic("%s: invalid key found", __func__); | ||||
node->pn_child[slot] = NULL; | pctrie_node_store(&node->pn_child[slot], NULL, | ||||
PCTRIE_LOCKED); | |||||
node->pn_count--; | node->pn_count--; | ||||
if (node->pn_count > 1) | if (node->pn_count > 1) | ||||
break; | break; | ||||
for (i = 0; i < PCTRIE_COUNT; i++) | for (i = 0; i < PCTRIE_COUNT; i++) { | ||||
if (node->pn_child[i] != NULL) | tmp = pctrie_node_load(&node->pn_child[i], | ||||
NULL, PCTRIE_LOCKED); | |||||
if (tmp != NULL) | |||||
break; | break; | ||||
} | |||||
KASSERT(i != PCTRIE_COUNT, | KASSERT(i != PCTRIE_COUNT, | ||||
("%s: invalid node configuration", __func__)); | ("%s: invalid node configuration", __func__)); | ||||
if (parent == NULL) | if (parent == NULL) | ||||
pctrie_setroot(ptree, node->pn_child[i]); | pctrie_root_store(ptree, tmp, PCTRIE_LOCKED); | ||||
else { | else { | ||||
slot = pctrie_slot(index, parent->pn_clev); | slot = pctrie_slot(index, parent->pn_clev); | ||||
KASSERT(parent->pn_child[slot] == node, | KASSERT(pctrie_node_load( | ||||
&parent->pn_child[slot], NULL, | |||||
PCTRIE_LOCKED) == node, | |||||
("%s: invalid child value", __func__)); | ("%s: invalid child value", __func__)); | ||||
parent->pn_child[slot] = node->pn_child[i]; | 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. | |||||
*/ | |||||
node->pn_count--; | node->pn_count--; | ||||
node->pn_child[i] = NULL; | pctrie_node_put(ptree, node, freefn, i); | ||||
pctrie_node_put(ptree, node, freefn); | |||||
break; | break; | ||||
} | } | ||||
parent = node; | parent = node; | ||||
node = node->pn_child[slot]; | node = tmp; | ||||
} | } | ||||
} | } | ||||
/* | /* | ||||
* Remove and free all the nodes from the tree. | * Remove and free all the nodes from the tree. | ||||
* This function is recursive but there is a tight control on it as the | * This function is recursive but there is a tight control on it as the | ||||
* maximum depth of the tree is fixed. | * maximum depth of the tree is fixed. | ||||
*/ | */ | ||||
void | void | ||||
pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) | pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn) | ||||
{ | { | ||||
struct pctrie_node *root; | struct pctrie_node *root; | ||||
root = pctrie_getroot(ptree); | root = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); | ||||
if (root == NULL) | if (root == NULL) | ||||
return; | return; | ||||
pctrie_setroot(ptree, NULL); | pctrie_root_store(ptree, NULL, PCTRIE_UNSERIALIZED); | ||||
if (!pctrie_isleaf(root)) | if (!pctrie_isleaf(root)) | ||||
pctrie_reclaim_allnodes_int(ptree, root, freefn); | pctrie_reclaim_allnodes_int(ptree, root, freefn); | ||||
} | } | ||||
#ifdef DDB | #ifdef DDB | ||||
/* | /* | ||||
* Show details about the given node. | * Show details about the given node. | ||||
*/ | */ | ||||
DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) | DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) | ||||
{ | { | ||||
struct pctrie_node *node; | struct pctrie_node *node, *tmp; | ||||
int i; | int i; | ||||
if (!have_addr) | if (!have_addr) | ||||
return; | return; | ||||
node = (struct pctrie_node *)addr; | node = (struct pctrie_node *)addr; | ||||
db_printf("node %p, owner %jx, children count %u, level %u:\n", | db_printf("node %p, owner %jx, children count %u, level %u:\n", | ||||
(void *)node, (uintmax_t)node->pn_owner, node->pn_count, | (void *)node, (uintmax_t)node->pn_owner, node->pn_count, | ||||
node->pn_clev); | node->pn_clev); | ||||
for (i = 0; i < PCTRIE_COUNT; i++) | for (i = 0; i < PCTRIE_COUNT; i++) { | ||||
if (node->pn_child[i] != NULL) | tmp = pctrie_node_load(&node->pn_child[i], NULL, | ||||
PCTRIE_UNSERIALIZED); | |||||
if (tmp != NULL) | |||||
db_printf("slot: %d, val: %p, value: %p, clev: %d\n", | db_printf("slot: %d, val: %p, value: %p, clev: %d\n", | ||||
i, (void *)node->pn_child[i], | i, (void *)tmp, | ||||
pctrie_isleaf(node->pn_child[i]) ? | pctrie_isleaf(tmp) ? pctrie_toval(tmp) : NULL, | ||||
pctrie_toval(node->pn_child[i]) : NULL, | |||||
node->pn_clev); | node->pn_clev); | ||||
} | |||||
} | } | ||||
#endif /* DDB */ | #endif /* DDB */ |
I think the comment from vm_radix_node_get() should be duplicated as well.