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