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_MAX_DEPTH    9       /* Maximum depth, including leafs */
  47
  48 /*
  49  * Entry for NULL node is at index 8 of the table. It is never encoded
  50  * in flags.
  51  */
  52 #define NODE_INDEX_NULL         8
  53
  54 /*
  55  * Number of removals needed on a fallback node before we try to shrink
  56  * it.
  57  */
  58 #define JA_FALLBACK_REMOVAL_COUNT       8
  59
  60 /* Never declared. Opaque type used to store flagged node pointers. */
  61 struct cds_ja_inode_flag;
  62 struct cds_ja_inode;
  63
  64 /*
  65  * Shadow node contains mutex and call_rcu head associated with a node.
  66  */
  67 struct cds_ja_shadow_node {
  68         struct cds_lfht_node ht_node;   /* hash table node */
  69         struct cds_ja_inode_flag *node_flag;    /* reverse mapping and hash table key */
  70         /*
  71          * mutual exclusion on all nodes belonging to the same tree
  72          * position (e.g. both nodes before and after recompaction
  73          * use the same lock).
  74          */
  75         pthread_mutex_t *lock;
  76         unsigned int nr_child;          /* number of children in node */
  77         struct rcu_head head;           /* for deferred node and shadow node reclaim */
  78         int fallback_removal_count;     /* removals left keeping fallback */
  79         int level;                      /* level in the tree */
  80         struct cds_ja *ja;              /* toplevel judy array */
  81 };
  82
  83 struct cds_ja {
  84         struct cds_ja_inode_flag *root;
  85         unsigned int tree_depth;
  86         uint64_t key_max;
  87         /*
  88          * We use a hash table to associate node keys to their
  89          * respective shadow node. This helps reducing lookup hot path
  90          * cache footprint, especially for very small nodes.
  91          */
  92         struct cds_lfht *ht;
  93         unsigned long nr_fallback;      /* Number of fallback nodes used */
  94 };
  95
  96 static inline
  97 struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node,
  98                 unsigned long type)
  99 {
 100         assert(type < (1UL << JA_TYPE_BITS));
 101         return (struct cds_ja_inode_flag *) (((unsigned long) node) | type);
 102 }
 103
 104 static inline
 105 struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node)
 106 {
 107         return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK);
 108 }
 109
 110 static inline
 111 unsigned long ja_node_type(struct cds_ja_inode_flag *node)
 112 {
 113         unsigned long type;
 114
 115         if (ja_node_ptr(node) == NULL) {
 116                 return NODE_INDEX_NULL;
 117         }
 118         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 119         assert(type < (1UL << JA_TYPE_BITS));
 120         return type;
 121 }
 122
 123 __attribute__((visibility("protected")))
 124 void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node,
 125                 struct cds_ja_inode_flag *node_flag,
 126                 void (*free_node_cb)(struct rcu_head *head));
 127
 128 __attribute__((visibility("protected")))
 129 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
 130                 struct cds_ja_inode_flag *node_flag);
 131
 132 __attribute__((visibility("protected")))
 133 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node);
 134
 135 __attribute__((visibility("protected")))
 136 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
 137                 struct cds_ja_inode_flag *new_node_flag,
 138                 struct cds_ja_shadow_node *inherit_from,
 139                 struct cds_ja *ja);
 140
 141 /* rcuja_shadow_clear flags */
 142 enum {
 143         RCUJA_SHADOW_CLEAR_FREE_NODE = (1U << 0),
 144         RCUJA_SHADOW_CLEAR_FREE_LOCK = (1U << 1),
 145 };
 146
 147 __attribute__((visibility("protected")))
 148 int rcuja_shadow_clear(struct cds_lfht *ht,
 149                 struct cds_ja_inode_flag *node_flag,
 150                 struct cds_ja_shadow_node *shadow_node,
 151                 unsigned int flags);
 152
 153 __attribute__((visibility("protected")))
 154 void rcuja_shadow_prune(struct cds_lfht *ht,
 155                 unsigned int flags,
 156                 void (*free_node_cb)(struct rcu_head *head));
 157
 158 __attribute__((visibility("protected")))
 159 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor);
 160
 161 __attribute__((visibility("protected")))
 162 int rcuja_delete_ht(struct cds_lfht *ht);
 163
 164 //#define DEBUG
 165
 166 #ifdef __linux__
 167 #include <syscall.h>
 168 #endif
 169
 170 #if defined(_syscall0)
 171 _syscall0(pid_t, gettid)
 172 #elif defined(__NR_gettid)
 173 static inline pid_t gettid(void)
 174 {
 175         return syscall(__NR_gettid);
 176 }
 177 #else
 178 #warning "use pid as tid"
 179 static inline pid_t gettid(void)
 180 {
 181         return getpid();
 182 }
 183 #endif
 184
 185 #ifdef DEBUG
 186 #define dbg_printf(fmt, args...)                                \
 187         fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt,    \
 188                 (unsigned long) gettid(), __func__,             \
 189                 __FILE__, __LINE__, ## args)
 190 #else
 191 #define dbg_printf(fmt, args...)                                \
 192 do {                                                            \
 193         /* do nothing but check printf format */                \
 194         if (0)                                                  \
 195                 fprintf(stderr, "[debug rcuja %lu %s()@%s:%u] " fmt, \
 196                         (unsigned long) gettid(), __func__,     \
 197                         __FILE__, __LINE__, ## args);           \
 198 } while (0)
 199 #endif
 200
 201 #endif /* _URCU_RCUJA_INTERNAL_H */