56#include <sys/kernel.h>
57#include <sys/pctrie.h>
60#include <sys/smr_types.h>
66#define PCTRIE_MASK (PCTRIE_COUNT - 1)
67#define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1)
70#define PCTRIE_ISLEAF 0x1
71#define PCTRIE_FLAGS 0x1
72#define PCTRIE_PAD PCTRIE_FLAGS
75#define PCTRIE_UNITLEVEL(lev) \
76 ((uint64_t)1 << ((lev) * PCTRIE_WIDTH))
86 smr_pctnode_t pn_child[PCTRIE_COUNT];
98static struct pctrie_node *
100 uint16_t
count, uint16_t clevel)
102 struct pctrie_node *node;
104 node = allocfn(ptree);
113 if (node->pn_last != 0) {
118 node->pn_owner = owner;
119 node->pn_count =
count;
120 node->pn_clev = clevel;
129 pctrie_free_t freefn, int8_t last)
134 KASSERT(node->pn_count == 0,
135 (
"pctrie_node_put: node %p has %d children", node,
137 for (slot = 0; slot < PCTRIE_COUNT; slot++) {
140 KASSERT(smr_unserialized_load(&node->pn_child[slot],
true) ==
141 NULL, (
"pctrie_node_put: node %p has a child", node));
144 node->pn_last = last + 1;
159static __inline uint64_t
166 ret >>=
level * PCTRIE_WIDTH;
167 ret <<=
level * PCTRIE_WIDTH;
175static __inline
struct pctrie_node *
180 return (smr_unserialized_load(p,
true));
182 return (smr_serialized_load(p,
true));
184 return (smr_entered_load(p, smr));
186 __assert_unreachable();
194 smr_unserialized_store(p, v,
true);
197 smr_serialized_store(p, v,
true);
200 panic(
"%s: Not supported in SMR section.", __func__);
203 __assert_unreachable();
211static __inline
struct pctrie_node *
240static __inline uint64_t *
265static __inline uint16_t
270 KASSERT(index1 != index2, (
"%s: passing the same key value %jx",
271 __func__, (uintmax_t)index1));
289 return (idx != node->pn_owner);
300 pctrie_free_t freefn)
302 struct pctrie_node *
child;
305 KASSERT(node->pn_count <= PCTRIE_COUNT,
306 (
"pctrie_reclaim_allnodes_int: bad count in node %p", node));
307 for (slot = 0; node->pn_count != 0; slot++) {
327 struct pctrie_node *node;
331 memset(node->pn_child, 0,
sizeof(node->pn_child));
339 return (
sizeof(
struct pctrie_node));
349 uint64_t index, newind;
350 struct pctrie_node *node, *tmp;
351 smr_pctnode_t *parentp;
367 parentp = (smr_pctnode_t *)&ptree->pt_root;
372 panic(
"%s: key %jx is already present",
373 __func__, (uintmax_t)index);
389 parentp = &node->pn_child[slot];
405 newind = node->pn_owner;
425static __always_inline uint64_t *
429 struct pctrie_node *node;
434 while (node != NULL) {
487 struct pctrie_node *
child, *node;
514 if (index > node->pn_owner) {
516 KASSERT(++loops < 1000,
517 (
"pctrie_lookup_ge: too many loops"));
529 node->pn_clev) == (PCTRIE_COUNT - 1));
540 index = node->pn_owner;
542 (
"pctrie_lookup_ge: keybarr failed"));
551 }
else if (
child != NULL)
558 if (slot < (PCTRIE_COUNT - 1)) {
570 }
else if (
child != NULL)
572 }
while (slot < (PCTRIE_COUNT - 1));
575 (
"pctrie_lookup_ge: child is radix node"));
583 KASSERT(node->pn_clev > 0,
584 (
"pctrie_lookup_ge: pushing leaf's parent"));
586 (
"pctrie_lookup_ge: stack overflow"));
602 struct pctrie_node *
child, *node;
629 if (index > node->pn_owner) {
630 index = node->pn_owner + PCTRIE_COUNT *
634 KASSERT(++loops < 1000,
635 (
"pctrie_lookup_le: too many loops"));
647 node->pn_clev) == 0);
659 (
"pctrie_lookup_le: keybarr failed"));
668 }
else if (
child != NULL)
687 }
else if (
child != NULL)
692 (
"pctrie_lookup_le: child is radix node"));
700 KASSERT(node->pn_clev > 0,
701 (
"pctrie_lookup_le: pushing leaf's parent"));
703 (
"pctrie_lookup_le: stack overflow"));
716 struct pctrie_node *node, *
parent, *tmp;
724 panic(
"%s: invalid key found", __func__);
731 panic(
"pctrie_remove: impossible to locate the key");
738 panic(
"%s: invalid key found", __func__);
742 if (node->pn_count > 1)
744 for (i = 0; i < PCTRIE_COUNT; i++) {
750 KASSERT(i != PCTRIE_COUNT,
751 (
"%s: invalid node configuration", __func__));
757 &
parent->pn_child[slot], NULL,
759 (
"%s: invalid child value", __func__));
784 struct pctrie_node *root;
798DB_SHOW_COMMAND(pctrienode, db_show_pctrienode)
800 struct pctrie_node *node, *tmp;
805 node = (
struct pctrie_node *)
addr;
806 db_printf(
"node %p, owner %jx, children count %u, level %u:\n",
807 (
void *)node, (uintmax_t)node->pn_owner, node->pn_count,
809 for (i = 0; i < PCTRIE_COUNT; i++) {
813 db_printf(
"slot: %d, val: %p, value: %p, clev: %d\n",
const struct cf_level * level
void panic(const char *fmt,...)
size_t pctrie_node_size(void)
static __inline int pctrie_slot(uint64_t index, uint16_t level)
static __inline uint16_t pctrie_keydiff(uint64_t index1, uint64_t index2)
static __inline void pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node, enum pctrie_access access)
static __inline uint64_t pctrie_trimkey(uint64_t index, uint16_t level)
int pctrie_zone_init(void *mem, int size __unused, int flags __unused)
static __inline struct pctrie_node * pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
uint64_t * pctrie_lookup(struct pctrie *ptree, uint64_t index)
void pctrie_reclaim_allnodes(struct pctrie *ptree, pctrie_free_t freefn)
static __inline struct pctrie_node * pctrie_root_load(struct pctrie *ptree, smr_t smr, enum pctrie_access access)
static __inline void pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, uint64_t *val, enum pctrie_access access)
#define PCTRIE_UNITLEVEL(lev)
int pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
static __inline void pctrie_node_put(struct pctrie *ptree, struct pctrie_node *node, pctrie_free_t freefn, int8_t last)
typedef SMR_POINTER(struct pctrie_node *)
static struct pctrie_node * pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, uint16_t count, uint16_t clevel)
static __inline void pctrie_node_store(smr_pctnode_t *p, void *val, enum pctrie_access access)
static __inline bool pctrie_isleaf(struct pctrie_node *node)
static __always_inline uint64_t * _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, enum pctrie_access access)
static __inline bool pctrie_keybarr(struct pctrie_node *node, uint64_t idx)
uint64_t * pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr)
static __inline uint64_t * pctrie_toval(struct pctrie_node *node)
static void pctrie_reclaim_allnodes_int(struct pctrie *ptree, struct pctrie_node *node, pctrie_free_t freefn)
uint64_t * pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
uint64_t * pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
void pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)