src/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 #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 /* Hardcoded pool indexes for fast path */
 144 #define RCU_JA_POOL_IDX_5       5
 145 #define RCU_JA_POOL_IDX_6       6
 146 static inline
 147 struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node)
 148 {
 149         unsigned long v, type_idx;
 150
 151         if (!node)
 152                 return NULL;    /* RCU_JA_NULL */
 153         v = (unsigned long) node;
 154         type_idx = v & JA_TYPE_MASK;
 155
 156         switch (type_idx) {
 157         case RCU_JA_POOL_IDX_5:
 158                 v &= ~(JA_POOL_1D_MASK | JA_TYPE_MASK);
 159                 break;
 160         case RCU_JA_POOL_IDX_6:
 161                 v &= ~(JA_POOL_2D_MASK | JA_POOL_1D_MASK | JA_TYPE_MASK);
 162                 break;
 163         default:
 164                 /* RCU_JA_LINEAR or RCU_JA_PIGEON */
 165                 v &= JA_PTR_MASK;
 166                 break;
 167         }
 168         return (struct cds_ja_inode *) v;
 169 }
 170
 171 __attribute__((visibility("protected")))
 172 unsigned long ja_node_type(struct cds_ja_inode_flag *node);
 173
 174 __attribute__((visibility("protected")))
 175 void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node,
 176                 struct cds_ja_inode_flag *node_flag);
 177
 178 __attribute__((visibility("protected")))
 179 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
 180                 struct cds_ja_inode_flag *node_flag);
 181
 182 __attribute__((visibility("protected")))
 183 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node);
 184
 185 __attribute__((visibility("protected")))
 186 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
 187                 struct cds_ja_inode_flag *new_node_flag,
 188                 struct cds_ja_shadow_node *inherit_from,
 189                 struct cds_ja *ja, int level);
 190
 191 /* rcuja_shadow_clear flags */
 192 enum {
 193         RCUJA_SHADOW_CLEAR_FREE_NODE = (1U << 0),
 194         RCUJA_SHADOW_CLEAR_FREE_LOCK = (1U << 1),
 195 };
 196
 197 __attribute__((visibility("protected")))
 198 int rcuja_shadow_clear(struct cds_lfht *ht,
 199                 struct cds_ja_inode_flag *node_flag,
 200                 struct cds_ja_shadow_node *shadow_node,
 201                 unsigned int flags);
 202
 203 __attribute__((visibility("protected")))
 204 void rcuja_shadow_prune(struct cds_lfht *ht,
 205                 unsigned int flags);
 206
 207 __attribute__((visibility("protected")))
 208 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor);
 209
 210 __attribute__((visibility("protected")))
 211 int rcuja_delete_ht(struct cds_lfht *ht);
 212
 213 __attribute__((visibility("protected")))
 214 void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node);
 215
 216 /*
 217  * Iterate through duplicates returned by cds_ja_lookup*()
 218  * Receives a struct cds_ja_node * as parameter, which is used as start
 219  * of duplicate list and loop cursor.
 220  */
 221 #define cds_ja_for_each_duplicate(pos)                          \
 222        for (; (pos) != NULL; (pos) = (pos)->next)
 223
 224 //#define DEBUG
 225 //#define DEBUG_COUNTERS
 226
 227 #ifdef __linux__
 228 #include <syscall.h>
 229 #endif
 230
 231 #if defined(_syscall0)
 232 _syscall0(pid_t, gettid)
 233 #elif defined(__NR_gettid)
 234 static inline pid_t gettid(void)
 235 {
 236         return syscall(__NR_gettid);
 237 }
 238 #else
 239 #warning "use pid as tid"
 240 static inline pid_t gettid(void)
 241 {
 242         return getpid();
 243 }
 244 #endif
 245
 246 #ifdef DEBUG
 247 #define dbg_printf(fmt, args...)                                \
 248         fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt,    \
 249                 (unsigned long) gettid(), __func__,             \
 250                 __FILE__, __LINE__, ## args)
 251
 252 #else
 253 #define dbg_printf(fmt, args...)                                \
 254 do {                                                            \
 255         /* do nothing but check printf format */                \
 256         if (0)                                                  \
 257                 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
 258                         (unsigned long) gettid(), __func__,     \
 259                         __FILE__, __LINE__, ## args);           \
 260 } while (0)
 261 #endif
 262
 263 #ifdef DEBUG_COUNTERS
 264 static inline
 265 int ja_debug_counters(void)
 266 {
 267         return 1;
 268 }
 269 #else
 270 static inline
 271 int ja_debug_counters(void)
 272 {
 273         return 0;
 274 }
 275 #endif
 276
 277 #endif /* _URCU_RCUJA_INTERNAL_H */