Page MenuHomeFreeBSD
Differential D45394 Diff 139545 sys/sys/pctrie.h

Changeset View

Standalone View

View Options

sys/sys/pctrie.h

Show First 20 Lines • Show All 41 Lines • ▼ Show 20 Lines
static __inline struct type * \ static __inline struct type * \
name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \ name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
{ \ { \
\ \
return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \ return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \
key, (smr))); \ key, (smr))); \
} \ } \
#ifdef INVARIANTS
void pctrie_subtree_lookup_gt_assert(struct pctrie_node *node,
uint64_t key, struct pctrie *ptree, uint64_t *res);
void pctrie_subtree_lookup_lt_assert(struct pctrie_node *node,
uint64_t key, struct pctrie *ptree, uint64_t *res);
#else
#define pctrie_subtree_lookup_gt_assert(node, key, ptree, res)
#define pctrie_subtree_lookup_lt_assert(node, key, ptree, res)
#endif
#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
\ \
CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \ CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \
/* \ /* \
* XXX This assert protects flag bits, it does not enforce natural \ * XXX This assert protects flag bits, it does not enforce natural \
* alignment. 32bit architectures do not naturally align 64bit fields. \ * alignment. 32bit architectures do not naturally align 64bit fields. \
*/ \ */ \
CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \ CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
Show All 10 Lines return (struct type *) \
\ \
static __inline uint64_t * \ static __inline uint64_t * \
name##_PCTRIE_PTR2VAL(struct type *ptr) \ name##_PCTRIE_PTR2VAL(struct type *ptr) \
{ \ { \
\ \
return &ptr->field; \ return &ptr->field; \
} \ } \
\ \
static __inline int \ static __inline __unused int \
name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \ name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \
{ \ { \
struct pctrie_node *parent; \ struct pctrie_node *parent; \
void *parentp; \ void *parentp; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
\ \
parentp = pctrie_insert_lookup(ptree, val); \ parentp = pctrie_insert_lookup_strict(ptree, val); \
if (parentp == NULL) \ if (parentp == NULL) \
return (0); \ return (0); \
parent = allocfn(ptree); \ parent = allocfn(ptree); \
if (__predict_false(parent == NULL)) \ if (__predict_false(parent == NULL)) \
dougmUnsubmitted
Done
Inline Actions

if __predict_false is useful for all the other ENOMEM tests, it's useful here too.

dougm: if __predict_false is useful for all the other ENOMEM tests, it's useful here too.
rlibbyAuthorUnsubmitted
Done
Inline Actions

I agree, I was thinking to do that in a separate commit, for more flexibility with MFC. I'll put that up for review tonight.

I can tell you that clang produced some code paths that were, let's say, non-optimal, without the predictions, when I examined the code gen for bgetvp.

rlibby: I agree, I was thinking to do that in a separate commit, for more flexibility with MFC. I'll…
return (ENOMEM); \ return (ENOMEM); \
pctrie_insert_node(parentp, parent, val); \ pctrie_insert_node(parentp, parent, val); \
return (0); \ return (0); \
} \ } \
\ \
static __inline __unused int \
name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr, \
struct type **found_out_opt) \
{ \
struct pctrie_node *parent; \
void *parentp; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
uint64_t *found; \
\
parentp = pctrie_insert_lookup(ptree, val, &found); \
if (found != NULL) { \
if (found_out_opt != NULL) \
*found_out_opt = name##_PCTRIE_VAL2PTR(found); \
return (EEXIST); \
} \
if (parentp == NULL) \
return (0); \
parent = allocfn(ptree); \
if (__predict_false(parent == NULL)) \
return (ENOMEM); \
pctrie_insert_node(parentp, parent, val); \
return (0); \
} \
\
static __inline __unused int \
name##_PCTRIE_INSERT_LOOKUP_GE(struct pctrie *ptree, struct type *ptr, \
struct type **found_out) \
{ \
struct pctrie_node *parent, *neighbor; \
void *parentp; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
uint64_t *found; \
\
parentp = pctrie_insert_lookup_gt(ptree, val, &found, \
&neighbor); \
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) \
dougmUnsubmitted
Not Done
Inline Actions

I'm concerned that this line does not do what is intended. While neighbor is a pointer to a pctrie_node, parentp is the (void*) cast of a pointer to an smr_pctnode_t, which can be used with pctrie_load_node to retrieve a pointer to a pctrie_node. So this test is never true, and the assignment to neighbor will never happen.

dougm: I'm concerned that this line does not do what is intended. While neighbor is a pointer to a…
dougmUnsubmitted
Not Done
Inline Actions

Upon further consideration, I think it's good that this assignment never happens, because all it would do is back one level up the search path, so that the first step in the neighbor search would be back to the neighbor value that was just replaced. So I think it's a de-optimization, but not a bug.

dougm: Upon further consideration, I think it's good that this assignment never happens, because all…
neighbor = parent; \
pctrie_insert_node(parentp, parent, val); \
} \
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(struct pctrie *ptree, struct type *ptr, \
struct type **found_out) \
{ \
struct pctrie_node *parent, *neighbor; \
void *parentp; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
uint64_t *found; \
\
parentp = pctrie_insert_lookup_lt(ptree, val, &found, \
&neighbor); \
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(parentp, parent, val); \
} \
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 * \ static __inline __unused struct type * \
name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \ name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
{ \ { \
\ \
return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \ return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \
} \ } \
\ \
static __inline __unused struct type * \ static __inline __unused struct type * \
▲ Show 20 Lines • Show All 49 Lines • ▼ Show 20 Linesname##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
struct pctrie_node *freenode; \ struct pctrie_node *freenode; \
\ \
val = pctrie_remove_lookup(ptree, key, &freenode); \ val = pctrie_remove_lookup(ptree, key, &freenode); \
if (freenode != NULL) \ if (freenode != NULL) \
freefn(ptree, freenode); \ freefn(ptree, freenode); \
return name##_PCTRIE_VAL2PTR(val); \ return name##_PCTRIE_VAL2PTR(val); \
} }
void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val); void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
uint64_t **found_out);
void *pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
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_strict(struct pctrie *ptree,
uint64_t *val);
void pctrie_insert_node(void *parentp, void pctrie_insert_node(void *parentp,
struct pctrie_node *parent, uint64_t *val); struct pctrie_node *parent, uint64_t *val);
uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); 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_ge(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
smr_t smr); smr_t smr);
struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode, struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
struct pctrie *ptree); struct pctrie *ptree);
struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode); struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index, uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **killnode); struct pctrie_node **killnode);
uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval); uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node,
uint64_t key);
uint64_t *pctrie_subtree_lookup_lt(struct pctrie_node *node,
uint64_t key);
size_t pctrie_node_size(void); size_t pctrie_node_size(void);
int pctrie_zone_init(void *mem, int size, int flags); int pctrie_zone_init(void *mem, int size, int flags);
/* /*
* Each search path in the trie terminates at a leaf, which is a pointer to a * Each search path in the trie terminates at a leaf, which is a pointer to a
* value marked with a set 1-bit. A leaf may be associated with a null pointer * value marked with a set 1-bit. A leaf may be associated with a null pointer
* to indicate no value there. * to indicate no value there.
*/ */
Show All 35 Lines