X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja-internal.h;h=d3793482402c85892be5effbdee0df05a557543c;hb=refs%2Fheads%2Furcu%2Frcuja-range;hp=6b8da15a1a6131b249c3f70e3d3a45b3df99716d;hpb=1a0c0717179caba65cc3de374b93af5027fcab9d;p=userspace-rcu.git diff --git a/rcuja/rcuja-internal.h b/rcuja/rcuja-internal.h index 6b8da15..d379348 100644 --- a/rcuja/rcuja-internal.h +++ b/rcuja/rcuja-internal.h @@ -6,7 +6,8 @@ * * Userspace RCU library - RCU Judy Array Internal Header * - * Copyright 2012 - Mathieu Desnoyers + * Copyright (C) 2000 - 2002 Hewlett-Packard Company + * Copyright 2012-2013 - Mathieu Desnoyers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -23,9 +24,11 @@ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ +#define _GNU_SOURCE #include #include #include +#include #include /* @@ -41,6 +44,9 @@ #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 */ /* @@ -89,6 +95,10 @@ struct cds_ja { */ 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 @@ -100,28 +110,71 @@ struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node, } static inline -struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) +struct cds_ja_inode_flag *ja_node_flag_pool_1d(struct cds_ja_inode *node, + unsigned long type, unsigned long bitsel) { - return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK); + 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 -unsigned long ja_node_type(struct cds_ja_inode_flag *node) +struct cds_ja_inode_flag *ja_node_flag_pool_2d(struct cds_ja_inode *node, + unsigned long type, unsigned int bitsel[2]) { - unsigned long type; + 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); +} - if (ja_node_ptr(node) == NULL) { - return NODE_INDEX_NULL; +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; +} + +/* Hardcoded pool indexes for fast path */ +#define RCU_JA_POOL_IDX_5 5 +#define RCU_JA_POOL_IDX_6 6 +static inline +struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) +{ + unsigned long v, type_idx; + + if (!node) + return NULL; /* RCU_JA_NULL */ + v = (unsigned long) node; + type_idx = v & JA_TYPE_MASK; + + switch (type_idx) { + case RCU_JA_POOL_IDX_5: + v &= ~(JA_POOL_1D_MASK | JA_TYPE_MASK); + break; + case RCU_JA_POOL_IDX_6: + v &= ~(JA_POOL_2D_MASK | JA_POOL_1D_MASK | JA_TYPE_MASK); + break; + default: + /* RCU_JA_LINEAR or RCU_JA_PIGEON */ + v &= JA_PTR_MASK; + break; } - type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK); - assert(type < (1UL << JA_TYPE_BITS)); - return type; + return (struct cds_ja_inode *) v; } +__attribute__((visibility("protected"))) +unsigned long ja_node_type(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)); + struct cds_ja_inode_flag *node_flag); __attribute__((visibility("protected"))) struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, @@ -134,7 +187,7 @@ __attribute__((visibility("protected"))) 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); + struct cds_ja *ja, int level); /* rcuja_shadow_clear flags */ enum { @@ -150,8 +203,7 @@ int rcuja_shadow_clear(struct cds_lfht *ht, __attribute__((visibility("protected"))) void rcuja_shadow_prune(struct cds_lfht *ht, - unsigned int flags, - void (*free_node_cb)(struct rcu_head *head)); + unsigned int flags); __attribute__((visibility("protected"))) struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor); @@ -159,17 +211,68 @@ 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); + +/* + * Iterate through duplicates returned by cds_ja_lookup*() + * Receives a struct cds_ja_node * as parameter, which is used as start + * of duplicate list and loop cursor. + */ +#define cds_ja_for_each_duplicate(pos) \ + for (; (pos) != NULL; (pos) = (pos)->next) + //#define DEBUG +//#define DEBUG_COUNTERS + +#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...) printf("[debug rcuja] " fmt, ## args) +#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) \ - printf("[debug rcuja] " fmt, ## args); \ + fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \ + (unsigned long) gettid(), __func__, \ + __FILE__, __LINE__, ## args); \ } while (0) #endif +#ifdef DEBUG_COUNTERS +static inline +int ja_debug_counters(void) +{ + return 1; +} +#else +static inline +int ja_debug_counters(void) +{ + return 0; +} +#endif + #endif /* _URCU_RCUJA_INTERNAL_H */