rcuja/rcuja-internal.h

   1 #ifndef _URCU_RCUJA_INTERNAL_H
   2 #define _URCU_RCUJA_INTERNAL_H
   3
   4 /*
   5  * rcuja/rcuja-internal.h
   6  *
   7  * Userspace RCU library - RCU Judy Array Internal Header
   8  *
   9  * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  24  */
  25
  26 #define _GNU_SOURCE
  27 #include <pthread.h>
  28 #include <stdio.h>
  29 #include <inttypes.h>
  30 #include <unistd.h>
  31 #include <urcu/rculfhash.h>
  32
  33 /*
  34  * Number of least significant pointer bits reserved to represent the
  35  * child type.
  36  */
  37 #define JA_TYPE_BITS    3
  38 #define JA_TYPE_MAX_NR  (1UL << JA_TYPE_BITS)
  39 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  40 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  41
  42 #define JA_ENTRY_PER_NODE       256UL
  43 #define JA_LOG2_BITS_PER_BYTE   3U
  44 #define JA_BITS_PER_BYTE        (1U << JA_LOG2_BITS_PER_BYTE)
  45
  46 #define JA_POOL_1D_MASK ((JA_BITS_PER_BYTE - 1) << JA_TYPE_BITS)
  47 #define JA_POOL_2D_MASK (JA_POOL_1D_MASK << JA_LOG2_BITS_PER_BYTE)
  48
  49 #define JA_MAX_DEPTH    9       /* Maximum depth, including leafs */
  50
  51 /*
  52  * Entry for NULL node is at index 8 of the table. It is never encoded
  53  * in flags.
  54  */
  55 #define NODE_INDEX_NULL         8
  56
  57 /*
  58  * Number of removals needed on a fallback node before we try to shrink
  59  * it.
  60  */
  61 #define JA_FALLBACK_REMOVAL_COUNT       8
  62
  63 /* Never declared. Opaque type used to store flagged node pointers. */
  64 struct cds_ja_inode_flag;
  65 struct cds_ja_inode;
  66
  67 /*
  68  * Shadow node contains mutex and call_rcu head associated with a node.
  69  */
  70 struct cds_ja_shadow_node {
  71         struct cds_lfht_node ht_node;   /* hash table node */
  72         struct cds_ja_inode_flag *node_flag;    /* reverse mapping and hash table key */
  73         /*
  74          * mutual exclusion on all nodes belonging to the same tree
  75          * position (e.g. both nodes before and after recompaction
  76          * use the same lock).
  77          */
  78         pthread_mutex_t *lock;
  79         unsigned int nr_child;          /* number of children in node */
  80         struct rcu_head head;           /* for deferred node and shadow node reclaim */
  81         int fallback_removal_count;     /* removals left keeping fallback */
  82         int level;                      /* level in the tree */
  83         struct cds_ja *ja;              /* toplevel judy array */
  84 };
  85
  86 struct cds_ja {
  87         struct cds_ja_inode_flag *root;
  88         unsigned int tree_depth;
  89         uint64_t key_max;
  90         /*
  91          * We use a hash table to associate node keys to their
  92          * respective shadow node. This helps reducing lookup hot path
  93          * cache footprint, especially for very small nodes.
  94          */
  95         struct cds_lfht *ht;
  96         unsigned long nr_fallback;      /* Number of fallback nodes used */
  97
  98         /* For debugging */
  99         unsigned long node_fallback_count_distribution[JA_ENTRY_PER_NODE];
 100         unsigned long nr_nodes_allocated, nr_nodes_freed;
 101 };
 102
 103 static inline
 104 struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node,
 105                 unsigned long type)
 106 {
 107         assert(type < (1UL << JA_TYPE_BITS));
 108         return (struct cds_ja_inode_flag *) (((unsigned long) node) | type);
 109 }
 110
 111 static inline
 112 struct cds_ja_inode_flag *ja_node_flag_pool_1d(struct cds_ja_inode *node,
 113                 unsigned long type, unsigned long bitsel)
 114 {
 115         assert(type < (1UL << JA_TYPE_BITS));
 116         assert(bitsel < JA_BITS_PER_BYTE);
 117         return (struct cds_ja_inode_flag *) (((unsigned long) node) | (bitsel << JA_TYPE_BITS) | type);
 118 }
 119
 120 static inline
 121 struct cds_ja_inode_flag *ja_node_flag_pool_2d(struct cds_ja_inode *node,
 122                 unsigned long type, unsigned int bitsel[2])
 123 {
 124         assert(type < (1UL << JA_TYPE_BITS));
 125         assert(bitsel[0] < JA_BITS_PER_BYTE);
 126         assert(bitsel[1] < JA_BITS_PER_BYTE);
 127         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);
 128 }
 129
 130 static inline
 131 unsigned long ja_node_pool_1d_bitsel(struct cds_ja_inode_flag *node)
 132 {
 133         return ((unsigned long) node & JA_POOL_1D_MASK) >> JA_TYPE_BITS;
 134 }
 135
 136 static inline
 137 void ja_node_pool_2d_bitsel(struct cds_ja_inode_flag *node, unsigned long *bits)
 138 {
 139         bits[0] = ((unsigned long) node & JA_POOL_2D_MASK) >> (JA_TYPE_BITS + JA_LOG2_BITS_PER_BYTE);
 140         bits[1] = ((unsigned long) node & JA_POOL_1D_MASK) >> JA_TYPE_BITS;
 141 }
 142
 143 __attribute__((visibility("protected")))
 144 unsigned long ja_node_type(struct cds_ja_inode_flag *node);
 145
 146 __attribute__((visibility("protected")))
 147 struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node);
 148
 149 __attribute__((visibility("protected")))
 150 void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node,
 151                 struct cds_ja_inode_flag *node_flag,
 152                 void (*free_node_cb)(struct rcu_head *head));
 153
 154 __attribute__((visibility("protected")))
 155 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
 156                 struct cds_ja_inode_flag *node_flag);
 157
 158 __attribute__((visibility("protected")))
 159 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node);
 160
 161 __attribute__((visibility("protected")))
 162 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
 163                 struct cds_ja_inode_flag *new_node_flag,
 164                 struct cds_ja_shadow_node *inherit_from,
 165                 struct cds_ja *ja, int level);
 166
 167 /* rcuja_shadow_clear flags */
 168 enum {
 169         RCUJA_SHADOW_CLEAR_FREE_NODE = (1U << 0),
 170         RCUJA_SHADOW_CLEAR_FREE_LOCK = (1U << 1),
 171 };
 172
 173 __attribute__((visibility("protected")))
 174 int rcuja_shadow_clear(struct cds_lfht *ht,
 175                 struct cds_ja_inode_flag *node_flag,
 176                 struct cds_ja_shadow_node *shadow_node,
 177                 unsigned int flags);
 178
 179 __attribute__((visibility("protected")))
 180 void rcuja_shadow_prune(struct cds_lfht *ht,
 181                 unsigned int flags,
 182                 void (*free_node_cb)(struct rcu_head *head));
 183
 184 __attribute__((visibility("protected")))
 185 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor);
 186
 187 __attribute__((visibility("protected")))
 188 int rcuja_delete_ht(struct cds_lfht *ht);
 189
 190 __attribute__((visibility("protected")))
 191 void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node);
 192
 193 //#define DEBUG
 194
 195 #ifdef __linux__
 196 #include <syscall.h>
 197 #endif
 198
 199 #if defined(_syscall0)
 200 _syscall0(pid_t, gettid)
 201 #elif defined(__NR_gettid)
 202 static inline pid_t gettid(void)
 203 {
 204         return syscall(__NR_gettid);
 205 }
 206 #else
 207 #warning "use pid as tid"
 208 static inline pid_t gettid(void)
 209 {
 210         return getpid();
 211 }
 212 #endif
 213
 214 #ifdef DEBUG
 215 #define dbg_printf(fmt, args...)                                \
 216         fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt,    \
 217                 (unsigned long) gettid(), __func__,             \
 218                 __FILE__, __LINE__, ## args)
 219 #else
 220 #define dbg_printf(fmt, args...)                                \
 221 do {                                                            \
 222         /* do nothing but check printf format */                \
 223         if (0)                                                  \
 224                 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
 225                         (unsigned long) gettid(), __func__,     \
 226                         __FILE__, __LINE__, ## args);           \
 227 } while (0)
 228 #endif
 229
 230 #endif /* _URCU_RCUJA_INTERNAL_H */