rculfhash: reorder cds_lfht for smaller cache footprint in fast-paths
[urcu.git] / rculfhash-internal.h
CommitLineData
0b6aa001
LJ
1#ifndef _URCU_RCULFHASH_INTERNAL_H
2#define _URCU_RCULFHASH_INTERNAL_H
3
4/*
5 * urcu/rculfhash-internal.h
6 *
7 * Internal header for Lock-Free RCU Hash Table
8 *
9 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
10 * Copyright 2011 - Lai Jiangshan <laijs@cn.fujitsu.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 <urcu/rculfhash.h>
28
29#ifdef DEBUG
30#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
31#else
32#define dbg_printf(fmt, args...)
33#endif
34
35#if (CAA_BITS_PER_LONG == 32)
36#define MAX_TABLE_ORDER 32
37#else
38#define MAX_TABLE_ORDER 64
39#endif
40
308d1cb3
LJ
41#define MAX_CHUNK_TABLE (1UL << 10)
42
0b6aa001
LJ
43#ifndef min
44#define min(a, b) ((a) < (b) ? (a) : (b))
45#endif
46
47#ifndef max
48#define max(a, b) ((a) > (b) ? (a) : (b))
49#endif
50
51struct ht_items_count;
52
53/*
54 * cds_lfht: Top-level data structure representing a lock-free hash
55 * table. Defined in the implementation file to make it be an opaque
56 * cookie to users.
57 */
58struct cds_lfht {
0b6aa001 59 /*
3fd3f554 60 * Variables needed for the lookup, add and remove fast-paths.
0b6aa001 61 */
3fd3f554 62 unsigned long size; /* always a power of 2, shared (RCU) */
0b6aa001
LJ
63 union {
64 /*
65 * Contains the per order-index-level bucket node table.
66 * The size of each bucket node table is half the number
67 * of hashes contained in this order (except for order 0).
68 * The minimum allocation buckets size parameter allows
69 * combining the bucket node arrays of the lowermost
70 * levels to improve cache locality for small index orders.
71 */
72 struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
308d1cb3
LJ
73
74 /*
75 * Contains the bucket node chunks. The size of each
76 * bucket node chunk is ->min_alloc_size (we avoid to
77 * allocate chunks with different size). Chunks improve
78 * cache locality for small index orders, and are more
79 * friendly with environments where allocation of large
80 * contiguous memory areas is challenging due to memory
81 * fragmentation concerns or inability to use virtual
82 * memory addressing.
83 */
84 struct cds_lfht_node *tbl_chunk[0];
b0b55251
LJ
85
86 /*
87 * Memory mapping with room for all possible buckets.
88 * Their memory is allocated when needed.
89 */
90 struct cds_lfht_node *tbl_mmap;
0b6aa001 91 };
3fd3f554
MD
92 /*
93 * bucket_at pointer is kept here to skip the extra level of
94 * dereference needed to get to "mm" (this is a fast-path).
95 */
96 struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
97 unsigned long index);
98 /*
99 * End of variables needed for lookup fast-path.
100 */
101
102 struct ht_items_count *split_count; /* split item count */
103 /*
104 * End of variables needed for add/remove fast-path.
105 */
106
107 /* Initial configuration items */
108 int flags;
109 unsigned long min_alloc_buckets_order;
110 unsigned long min_nr_alloc_buckets;
111 unsigned long max_nr_buckets;
112 const struct cds_lfht_mm_type *mm; /* memory management plugin */
113 const struct rcu_flavor_struct *flavor; /* RCU flavor */
114
115 long count; /* global approximate item count */
116
117 /*
118 * We need to put the work threads offline (QSBR) when taking this
119 * mutex, because we use synchronize_rcu within this mutex critical
120 * section, which waits on read-side critical sections, and could
121 * therefore cause grace-period deadlock if we hold off RCU G.P.
122 * completion.
123 */
124 pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
125 pthread_attr_t *resize_attr; /* Resize threads attributes */
126 unsigned int in_progress_resize, in_progress_destroy;
127 unsigned long resize_target;
128 int resize_initiated;
0b6aa001
LJ
129};
130
131extern unsigned int fls_ulong(unsigned long x);
132extern int get_count_order_ulong(unsigned long x);
133
134#ifdef POISON_FREE
135#define poison_free(ptr) \
136 do { \
137 if (ptr) { \
138 memset(ptr, 0x42, sizeof(*(ptr))); \
139 free(ptr); \
140 } \
141 } while (0)
142#else
143#define poison_free(ptr) free(ptr)
144#endif
145
146#endif /* _URCU_RCULFHASH_INTERNAL_H */
This page took 0.039265 seconds and 4 git commands to generate.