1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
/*
* Copyright (c) 2014 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#error do not #include this file!
/** \file
Bounded-index extensible hashing. The basic algorithm performs
thread-safe constant-time lookups in the face of a rational number
of hash collisions. The computed hash code h(k) must have
reasonable statistics with respect to the key space. It won't do
to have h(k) = 0 or 1, for all values of k.
Each bucket in the power-of-two bucket array contains the index
(in a private vppinfra memory heap) of the "backing store" for the
bucket, as well as a size field. The size field (log2_pages)
corresponds to 1, 2, 4, ... contiguous "pages" containing the
(key,value) pairs in the bucket.
When a single page fills, we allocate two contiguous pages. We
recompute h(k) for each (key,value) pair, using an additional bit
to deal the (key, value) pairs into the "top" and "bottom" pages.
At lookup time, we compute h(k), using lg(bucket-array-size) to
pick the bucket. We read the bucket to find the base of the
backing pages. We use an additional log2_pages' worth of bits
from h(k) to compute the offset of the page which will contain the
(key,value) pair we're trying to find.
*/
/** template key/value backing page structure */
typedef struct clib_bihash_value
{
union
{
clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */
clib_bihash_value *next_free; /**< used when a KVP page (or block thereof) is on a freelist */
};
} clib_bihash_value_t
/** bihash bucket structure */
typedef struct
{
union
{
struct
{
u32 offset; /**< backing page offset in the clib memory heap */
u8 pad[3]; /**< log2 (size of the packing page block) */
u8 log2_pages;
};
u64 as_u64;
};
} clib_bihash_bucket_t;
/** A bounded index extensible hash table */
typedef struct
{
clib_bihash_bucket_t *buckets; /**< Hash bucket vector, power-of-two in size */
volatile u32 *writer_lock; /**< Writer lock, in its own cache line */
BVT (clib_bihash_value) ** working_copies;
/**< Working copies (various sizes), to avoid locking against readers */
clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */
u32 nbuckets; /**< Number of hash buckets */
u32 log2_nbuckets; /**< lg(nbuckets) */
u8 *name; /**< hash table name */
BVT (clib_bihash_value) ** freelists;
/**< power of two freelist vector */
uword alloc_arena; /**< memory allocation arena */
uword alloc_arena_next; /**< first available mem chunk */
uword alloc_arena_size; /**< size of the arena */
} clib_bihash_t;
/** Get pointer to value page given its clib mheap offset */
static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
/** Get clib mheap offset given a pointer */
static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
/** initialize a bounded index extensible hash table
@param h - the bi-hash table to initialize
@param name - name of the hash table
@param nbuckets - the number of buckets, will be rounded up to
a power of two
@param memory_size - clib mheap size, in bytes
*/
void clib_bihash_init
(clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
/** Destroy a bounded index extensible hash table
@param h - the bi-hash table to free
*/
void clib_bihash_free (clib_bihash * h);
/** Add or delete a (key,value) pair from a bi-hash table
@param h - the bi-hash table to search
@param add_v - the (key,value) pair to add
@param is_add - add=1, delete=0
@returns 0 on success, < 0 on error
@note This function will replace an existing (key,value) pair if the
new key matches an existing key
*/
int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
/** Search a bi-hash table, use supplied hash code
@param h - the bi-hash table to search
@param hash - the hash code
@param in_out_kv - (key,value) pair containing the search key
@returns 0 on success (with in_out_kv set), < 0 on error
*/
int clib_bihash_search_inline_with_hash
(clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
/** Search a bi-hash table
@param h - the bi-hash table to search
@param in_out_kv - (key,value) pair containing the search key
@returns 0 on success (with in_out_kv set), < 0 on error
*/
int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
/** Prefetch a bi-hash bucket given a hash code
@param h - the bi-hash table to search
@param hash - the hash code
@note see also clib_bihash_hash to compute the code
*/
void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
/** Prefetch bi-hash (key,value) data given a hash code
@param h - the bi-hash table to search
@param hash - the hash code
@note assumes that the bucket has been prefetched, see
clib_bihash_prefetch_bucket
*/
void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
/** Search a bi-hash table
@param h - the bi-hash table to search
@param search_key - (key,value) pair containing the search key
@param valuep - (key,value) set to search result
@returns 0 on success (with valuep set), < 0 on error
@note used in situations where key modification is not desired
*/
int clib_bihash_search_inline_2
(clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
/** Visit active (key,value) pairs in a bi-hash table
@param h - the bi-hash table to search
@param callback - function to call with each active (key,value) pair
@param arg - arbitrary second argument passed to the callback function
First argument is the (key,value) pair to visit
@note Trying to supply a proper function prototype for the
callback function appears to be a fool's errand.
*/
void clib_bihash_foreach_key_value_pair (clib_bihash * h,
void *callback, void *arg);
/*
* fd.io coding-style-patch-verification: ON
*
* Local Variables:
* eval: (c-set-style "gnu")
* End:
*/
|
