X-Git-Url: http://git.lttng.org./?a=blobdiff_plain;f=rcuja%2Frcuja-internal.h;h=cf4ef96fcc71a0f0f86ba6b69a6ac24a100d9131;hb=021c72c06fe01ac99afb234e7aa7c4301d6fddee;hp=551cad68cbe0ccf6711a9f535373a10cac8ece6f;hpb=be9a7474cac017c7d0bed96efdb86e50ed0f6376;p=userspace-rcu.git diff --git a/rcuja/rcuja-internal.h b/rcuja/rcuja-internal.h index 551cad6..cf4ef96 100644 --- a/rcuja/rcuja-internal.h +++ b/rcuja/rcuja-internal.h @@ -23,18 +23,53 @@ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ +#define _GNU_SOURCE #include +#include +#include +#include #include +/* + * Number of least significant pointer bits reserved to represent the + * child type. + */ +#define JA_TYPE_BITS 3 +#define JA_TYPE_MAX_NR (1UL << JA_TYPE_BITS) +#define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1) +#define JA_PTR_MASK (~JA_TYPE_MASK) + +#define JA_ENTRY_PER_NODE 256UL +#define JA_LOG2_BITS_PER_BYTE 3U +#define JA_BITS_PER_BYTE (1U << JA_LOG2_BITS_PER_BYTE) + +#define JA_POOL_1D_MASK ((JA_BITS_PER_BYTE - 1) << JA_TYPE_BITS) +#define JA_POOL_2D_MASK (JA_POOL_1D_MASK << JA_LOG2_BITS_PER_BYTE) + +#define JA_MAX_DEPTH 9 /* Maximum depth, including leafs */ + +/* + * Entry for NULL node is at index 8 of the table. It is never encoded + * in flags. + */ +#define NODE_INDEX_NULL 8 + +/* + * Number of removals needed on a fallback node before we try to shrink + * it. + */ +#define JA_FALLBACK_REMOVAL_COUNT 8 + /* Never declared. Opaque type used to store flagged node pointers. */ -struct cds_ja_node_flag; +struct cds_ja_inode_flag; +struct cds_ja_inode; /* * Shadow node contains mutex and call_rcu head associated with a node. */ struct cds_ja_shadow_node { struct cds_lfht_node ht_node; /* hash table node */ - struct cds_ja_node *node; /* reverse mapping and hash table key */ + struct cds_ja_inode_flag *node_flag; /* reverse mapping and hash table key */ /* * mutual exclusion on all nodes belonging to the same tree * position (e.g. both nodes before and after recompaction @@ -43,29 +78,91 @@ struct cds_ja_shadow_node { pthread_mutex_t *lock; unsigned int nr_child; /* number of children in node */ struct rcu_head head; /* for deferred node and shadow node reclaim */ + int fallback_removal_count; /* removals left keeping fallback */ + int level; /* level in the tree */ + struct cds_ja *ja; /* toplevel judy array */ }; struct cds_ja { - struct cds_ja_node_flag *root; + struct cds_ja_inode_flag *root; + unsigned int tree_depth; + uint64_t key_max; /* * We use a hash table to associate node keys to their * respective shadow node. This helps reducing lookup hot path * cache footprint, especially for very small nodes. */ struct cds_lfht *ht; + unsigned long nr_fallback; /* Number of fallback nodes used */ + + /* For debugging */ + unsigned long node_fallback_count_distribution[JA_ENTRY_PER_NODE]; + unsigned long nr_nodes_allocated, nr_nodes_freed; }; +static inline +struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node, + unsigned long type) +{ + assert(type < (1UL << JA_TYPE_BITS)); + return (struct cds_ja_inode_flag *) (((unsigned long) node) | type); +} + +static inline +struct cds_ja_inode_flag *ja_node_flag_pool_1d(struct cds_ja_inode *node, + unsigned long type, unsigned long bitsel) +{ + assert(type < (1UL << JA_TYPE_BITS)); + assert(bitsel < JA_BITS_PER_BYTE); + return (struct cds_ja_inode_flag *) (((unsigned long) node) | (bitsel << JA_TYPE_BITS) | type); +} + +static inline +struct cds_ja_inode_flag *ja_node_flag_pool_2d(struct cds_ja_inode *node, + unsigned long type, unsigned int bitsel[2]) +{ + assert(type < (1UL << JA_TYPE_BITS)); + assert(bitsel[0] < JA_BITS_PER_BYTE); + assert(bitsel[1] < JA_BITS_PER_BYTE); + return (struct cds_ja_inode_flag *) (((unsigned long) node) | (bitsel[0] << (JA_TYPE_BITS + JA_LOG2_BITS_PER_BYTE)) | (bitsel[1] << JA_TYPE_BITS) | type); +} + +static inline +unsigned long ja_node_pool_1d_bitsel(struct cds_ja_inode_flag *node) +{ + return ((unsigned long) node & JA_POOL_1D_MASK) >> JA_TYPE_BITS; +} + +static inline +void ja_node_pool_2d_bitsel(struct cds_ja_inode_flag *node, unsigned long *bits) +{ + bits[0] = ((unsigned long) node & JA_POOL_2D_MASK) >> (JA_TYPE_BITS + JA_LOG2_BITS_PER_BYTE); + bits[1] = ((unsigned long) node & JA_POOL_1D_MASK) >> JA_TYPE_BITS; +} + +__attribute__((visibility("protected"))) +unsigned long ja_node_type(struct cds_ja_inode_flag *node); + +__attribute__((visibility("protected"))) +struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node); + +__attribute__((visibility("protected"))) +void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, + struct cds_ja_inode_flag *node_flag, + void (*free_node_cb)(struct rcu_head *head)); + __attribute__((visibility("protected"))) struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, - struct cds_ja_node *node); + struct cds_ja_inode_flag *node_flag); __attribute__((visibility("protected"))) void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node); __attribute__((visibility("protected"))) -int rcuja_shadow_set(struct cds_lfht *ht, - struct cds_ja_node *new_node, - struct cds_ja_shadow_node *inherit_from); +struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, + struct cds_ja_inode_flag *new_node_flag, + struct cds_ja_shadow_node *inherit_from, + struct cds_ja *ja, int level); /* rcuja_shadow_clear flags */ enum { @@ -75,12 +172,14 @@ enum { __attribute__((visibility("protected"))) int rcuja_shadow_clear(struct cds_lfht *ht, - struct cds_ja_node *node, + struct cds_ja_inode_flag *node_flag, + struct cds_ja_shadow_node *shadow_node, unsigned int flags); __attribute__((visibility("protected"))) void rcuja_shadow_prune(struct cds_lfht *ht, - unsigned int flags); + unsigned int flags, + void (*free_node_cb)(struct rcu_head *head)); __attribute__((visibility("protected"))) struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor); @@ -88,4 +187,44 @@ struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor); __attribute__((visibility("protected"))) int rcuja_delete_ht(struct cds_lfht *ht); +__attribute__((visibility("protected"))) +void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node); + +//#define DEBUG + +#ifdef __linux__ +#include +#endif + +#if defined(_syscall0) +_syscall0(pid_t, gettid) +#elif defined(__NR_gettid) +static inline pid_t gettid(void) +{ + return syscall(__NR_gettid); +} +#else +#warning "use pid as tid" +static inline pid_t gettid(void) +{ + return getpid(); +} +#endif + +#ifdef DEBUG +#define dbg_printf(fmt, args...) \ + fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \ + (unsigned long) gettid(), __func__, \ + __FILE__, __LINE__, ## args) +#else +#define dbg_printf(fmt, args...) \ +do { \ + /* do nothing but check printf format */ \ + if (0) \ + fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \ + (unsigned long) gettid(), __func__, \ + __FILE__, __LINE__, ## args); \ +} while (0) +#endif + #endif /* _URCU_RCUJA_INTERNAL_H */