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 #include <pthread.h>
  27 #include <stdio.h>
  28 #include <inttypes.h>
  29 #include <urcu/rculfhash.h>
  30
  31 /*
  32  * Number of least significant pointer bits reserved to represent the
  33  * child type.
  34  */
  35 #define JA_TYPE_BITS    3
  36 #define JA_TYPE_MAX_NR  (1UL << JA_TYPE_BITS)
  37 #define JA_TYPE_MASK    (JA_TYPE_MAX_NR - 1)
  38 #define JA_PTR_MASK     (~JA_TYPE_MASK)
  39
  40 #define JA_ENTRY_PER_NODE       256UL
  41 #define JA_LOG2_BITS_PER_BYTE   3U
  42 #define JA_BITS_PER_BYTE        (1U << JA_LOG2_BITS_PER_BYTE)
  43
  44 #define JA_MAX_DEPTH    9       /* Maximum depth, including leafs */
  45
  46 /*
  47  * Entry for NULL node is at index 8 of the table. It is never encoded
  48  * in flags.
  49  */
  50 #define NODE_INDEX_NULL         8
  51
  52 /*
  53  * Number of removals needed on a fallback node before we try to shrink
  54  * it.
  55  */
  56 #define JA_FALLBACK_REMOVAL_COUNT       8
  57
  58 /* Never declared. Opaque type used to store flagged node pointers. */
  59 struct cds_ja_inode_flag;
  60 struct cds_ja_inode;
  61
  62 /*
  63  * Shadow node contains mutex and call_rcu head associated with a node.
  64  */
  65 struct cds_ja_shadow_node {
  66         struct cds_lfht_node ht_node;   /* hash table node */
  67         struct cds_ja_inode_flag *node_flag;    /* reverse mapping and hash table key */
  68         /*
  69          * mutual exclusion on all nodes belonging to the same tree
  70          * position (e.g. both nodes before and after recompaction
  71          * use the same lock).
  72          */
  73         pthread_mutex_t *lock;
  74         unsigned int nr_child;          /* number of children in node */
  75         struct rcu_head head;           /* for deferred node and shadow node reclaim */
  76         int fallback_removal_count;     /* removals left keeping fallback */
  77         int level;                      /* level in the tree */
  78         struct cds_ja *ja;              /* toplevel judy array */
  79 };
  80
  81 struct cds_ja {
  82         struct cds_ja_inode_flag *root;
  83         unsigned int tree_depth;
  84         uint64_t key_max;
  85         /*
  86          * We use a hash table to associate node keys to their
  87          * respective shadow node. This helps reducing lookup hot path
  88          * cache footprint, especially for very small nodes.
  89          */
  90         struct cds_lfht *ht;
  91         unsigned long nr_fallback;      /* Number of fallback nodes used */
  92 };
  93
  94 static inline
  95 struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node,
  96                 unsigned long type)
  97 {
  98         assert(type < (1UL << JA_TYPE_BITS));
  99         return (struct cds_ja_inode_flag *) (((unsigned long) node) | type);
 100 }
 101
 102 static inline
 103 struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node)
 104 {
 105         return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK);
 106 }
 107
 108 static inline
 109 unsigned long ja_node_type(struct cds_ja_inode_flag *node)
 110 {
 111         unsigned long type;
 112
 113         if (ja_node_ptr(node) == NULL) {
 114                 return NODE_INDEX_NULL;
 115         }
 116         type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK);
 117         assert(type < (1UL << JA_TYPE_BITS));
 118         return type;
 119 }
 120
 121 __attribute__((visibility("protected")))
 122 void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node,
 123                 struct cds_ja_inode_flag *node_flag,
 124                 void (*free_node_cb)(struct rcu_head *head));
 125
 126 __attribute__((visibility("protected")))
 127 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
 128                 struct cds_ja_inode_flag *node_flag);
 129
 130 __attribute__((visibility("protected")))
 131 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node);
 132
 133 __attribute__((visibility("protected")))
 134 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
 135                 struct cds_ja_inode_flag *new_node_flag,
 136                 struct cds_ja_shadow_node *inherit_from,
 137                 struct cds_ja *ja);
 138
 139 /* rcuja_shadow_clear flags */
 140 enum {
 141         RCUJA_SHADOW_CLEAR_FREE_NODE = (1U << 0),
 142         RCUJA_SHADOW_CLEAR_FREE_LOCK = (1U << 1),
 143 };
 144
 145 __attribute__((visibility("protected")))
 146 int rcuja_shadow_clear(struct cds_lfht *ht,
 147                 struct cds_ja_inode_flag *node_flag,
 148                 struct cds_ja_shadow_node *shadow_node,
 149                 unsigned int flags);
 150
 151 __attribute__((visibility("protected")))
 152 void rcuja_shadow_prune(struct cds_lfht *ht,
 153                 unsigned int flags,
 154                 void (*free_node_cb)(struct rcu_head *head));
 155
 156 __attribute__((visibility("protected")))
 157 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor);
 158
 159 __attribute__((visibility("protected")))
 160 int rcuja_delete_ht(struct cds_lfht *ht);
 161
 162 #define DEBUG
 163
 164 #ifdef DEBUG
 165 #define dbg_printf(fmt, args...)     printf("[debug rcuja] " fmt, ## args)
 166 #else
 167 #define dbg_printf(fmt, args...)                                \
 168 do {                                                            \
 169         /* do nothing but check printf format */                \
 170         if (0)                                                  \
 171                 printf("[debug rcuja] " fmt, ## args);  \
 172 } while (0)
 173 #endif
 174
 175 #endif /* _URCU_RCUJA_INTERNAL_H */