Line data Source code
1 : /*
2 : * Copyright (c) 2015 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 : /*
16 : Copyright (c) 2010 Eliot Dresselhaus
17 :
18 : Permission is hereby granted, free of charge, to any person obtaining
19 : a copy of this software and associated documentation files (the
20 : "Software"), to deal in the Software without restriction, including
21 : without limitation the rights to use, copy, modify, merge, publish,
22 : distribute, sublicense, and/or sell copies of the Software, and to
23 : permit persons to whom the Software is furnished to do so, subject to
24 : the following conditions:
25 :
26 : The above copyright notice and this permission notice shall be
27 : included in all copies or substantial portions of the Software.
28 :
29 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 : EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 : MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 : NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 : OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 : WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 : */
37 :
38 : #include <vppinfra/mhash.h>
39 :
40 : always_inline u32
41 282662 : load_partial_u32 (void *d, uword n)
42 : {
43 282662 : if (n == 4)
44 281136 : return ((u32 *) d)[0];
45 1526 : if (n == 3)
46 218 : return ((u16 *) d)[0] | (((u8 *) d)[2] << 16);
47 1308 : if (n == 2)
48 48 : return ((u16 *) d)[0];
49 1260 : if (n == 1)
50 1260 : return ((u8 *) d)[0];
51 0 : ASSERT (0);
52 0 : return 0;
53 : }
54 :
55 : always_inline u32
56 123995 : mhash_key_sum_inline (void *data, uword n_data_bytes, u32 seed)
57 : {
58 123995 : u32 *d32 = data;
59 : u32 a, b, c, n_left;
60 :
61 123995 : a = b = c = seed;
62 123995 : n_left = n_data_bytes;
63 123995 : a ^= n_data_bytes;
64 :
65 236137 : while (n_left > 12)
66 : {
67 112142 : a += d32[0];
68 112142 : b += d32[1];
69 112142 : c += d32[2];
70 112142 : hash_v3_mix32 (a, b, c);
71 112142 : n_left -= 12;
72 112142 : d32 += 3;
73 : }
74 :
75 123995 : if (n_left > 8)
76 : {
77 68165 : c += load_partial_u32 (d32 + 2, n_left - 8);
78 68165 : n_left = 8;
79 : }
80 123995 : if (n_left > 4)
81 : {
82 90502 : b += load_partial_u32 (d32 + 1, n_left - 4);
83 90502 : n_left = 4;
84 : }
85 123995 : if (n_left > 0)
86 123995 : a += load_partial_u32 (d32 + 0, n_left - 0);
87 :
88 123995 : hash_v3_finalize32 (a, b, c);
89 :
90 123995 : return c;
91 : }
92 :
93 : #define foreach_mhash_key_size \
94 : _ (2) _ (3) _ (4) _ (5) _ (6) _ (7) \
95 : _ (8) _ (12) _ (16) _ (20) \
96 : _ (24) _ (28) _ (32) _ (36) \
97 : _ (40) _ (44) _ (48) _ (52) \
98 : _ (56) _ (60) _ (64)
99 :
100 : #define _(N_KEY_BYTES) \
101 : static uword \
102 : mhash_key_sum_##N_KEY_BYTES (hash_t * h, uword key) \
103 : { \
104 : mhash_t * hv = uword_to_pointer (h->user, mhash_t *); \
105 : return mhash_key_sum_inline (mhash_key_to_mem (hv, key), \
106 : (N_KEY_BYTES), \
107 : hv->hash_seed); \
108 : } \
109 : \
110 : static uword \
111 : mhash_key_equal_##N_KEY_BYTES (hash_t * h, uword key1, uword key2) \
112 : { \
113 : mhash_t * hv = uword_to_pointer (h->user, mhash_t *); \
114 : void * k1 = mhash_key_to_mem (hv, key1); \
115 : void * k2 = mhash_key_to_mem (hv, key2); \
116 : return ! memcmp (k1, k2, (N_KEY_BYTES)); \
117 : }
118 :
119 165106 : foreach_mhash_key_size
120 : #undef _
121 : static uword
122 16 : mhash_key_sum_c_string (hash_t * h, uword key)
123 : {
124 16 : mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
125 16 : void *k = mhash_key_to_mem (hv, key);
126 16 : return mhash_key_sum_inline (k, strlen (k), hv->hash_seed);
127 : }
128 :
129 : static uword
130 8 : mhash_key_equal_c_string (hash_t * h, uword key1, uword key2)
131 : {
132 8 : mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
133 8 : void *k1 = mhash_key_to_mem (hv, key1);
134 8 : void *k2 = mhash_key_to_mem (hv, key2);
135 8 : return strcmp (k1, k2) == 0;
136 : }
137 :
138 : static uword
139 1510 : mhash_key_sum_vec_string (hash_t * h, uword key)
140 : {
141 1510 : mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
142 1510 : void *k = mhash_key_to_mem (hv, key);
143 1510 : return mhash_key_sum_inline (k, vec_len (k), hv->hash_seed);
144 : }
145 :
146 : static uword
147 962 : mhash_key_equal_vec_string (hash_t * h, uword key1, uword key2)
148 : {
149 962 : mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
150 962 : void *k1 = mhash_key_to_mem (hv, key1);
151 962 : void *k2 = mhash_key_to_mem (hv, key2);
152 962 : return vec_len (k1) == vec_len (k2) && memcmp (k1, k2, vec_len (k1)) == 0;
153 : }
154 :
155 : /* The CLIB hash user pointer must always point to a valid mhash_t.
156 : Now, the address of mhash_t can change (think vec_resize).
157 : So we must always be careful that it points to the correct
158 : address. */
159 : always_inline void
160 107850 : mhash_sanitize_hash_user (mhash_t * mh)
161 : {
162 107850 : uword *hash = mh->hash;
163 107850 : hash_t *h = hash_header (hash);
164 107850 : h->user = pointer_to_uword (mh);
165 107850 : }
166 :
167 : __clib_export void
168 12584 : mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes)
169 : {
170 : static struct
171 : {
172 : hash_key_sum_function_t *key_sum;
173 : hash_key_equal_function_t *key_equal;
174 : } t[] =
175 : {
176 : #define _(N_KEY_BYTES) \
177 : [N_KEY_BYTES] = { \
178 : .key_sum = mhash_key_sum_##N_KEY_BYTES, \
179 : .key_equal = mhash_key_equal_##N_KEY_BYTES, \
180 : },
181 :
182 : foreach_mhash_key_size
183 : #undef _
184 : [MHASH_C_STRING_KEY] =
185 : {
186 : .key_sum = mhash_key_sum_c_string,.key_equal = mhash_key_equal_c_string,},
187 : [MHASH_VEC_STRING_KEY] =
188 : {
189 : .key_sum = mhash_key_sum_vec_string,.key_equal =
190 : mhash_key_equal_vec_string,},};
191 :
192 12584 : if (mhash_key_vector_is_heap (h))
193 12575 : heap_free (h->key_vector_or_heap);
194 : else
195 9 : vec_free (h->key_vector_or_heap);
196 12584 : vec_free (h->key_vector_free_indices);
197 : {
198 : int i;
199 12593 : for (i = 0; i < vec_len (h->key_tmps); i++)
200 9 : vec_free (h->key_tmps[i]);
201 : }
202 12584 : vec_free (h->key_tmps);
203 12584 : hash_free (h->hash);
204 :
205 12584 : clib_memset (h, 0, sizeof (h[0]));
206 12584 : h->n_key_bytes = n_key_bytes;
207 :
208 12584 : vec_validate (h->key_tmps, os_get_nthreads () - 1);
209 :
210 12584 : ASSERT (n_key_bytes < ARRAY_LEN (t));
211 25168 : h->hash = hash_create2 ( /* elts */ 0,
212 : /* user */ pointer_to_uword (h),
213 : /* value_bytes */ n_value_bytes,
214 : t[n_key_bytes].key_sum, t[n_key_bytes].key_equal,
215 : /* format pair/arg */
216 : 0, 0);
217 12584 : }
218 :
219 : static uword
220 90193 : mhash_set_tmp_key (mhash_t * h, const void *key)
221 : {
222 : u8 *key_tmp;
223 90193 : int my_cpu = os_get_thread_index ();
224 :
225 90193 : key_tmp = h->key_tmps[my_cpu];
226 :
227 90193 : vec_reset_length (key_tmp);
228 :
229 90193 : if (mhash_key_vector_is_heap (h))
230 : {
231 972 : uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
232 :
233 972 : if (is_c_string)
234 8 : vec_add (key_tmp, key, strlen (key) + 1);
235 : else
236 964 : vec_add (key_tmp, key, vec_len (key));
237 : }
238 : else
239 89221 : vec_add (key_tmp, key, h->n_key_bytes);
240 :
241 90193 : h->key_tmps[my_cpu] = key_tmp;
242 :
243 90193 : return ~0;
244 : }
245 :
246 : __clib_export hash_pair_t *
247 74048 : mhash_get_pair (mhash_t * h, const void *key)
248 : {
249 : uword ikey;
250 74048 : mhash_sanitize_hash_user (h);
251 74048 : ikey = mhash_set_tmp_key (h, key);
252 74048 : return hash_get_pair (h->hash, ikey);
253 : }
254 :
255 : typedef struct
256 : {
257 : u32 heap_handle;
258 :
259 : /* Must coincide with vec_header. */
260 : vec_header_t vec;
261 : } mhash_string_key_t;
262 :
263 : __clib_export uword
264 17657 : mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
265 : {
266 : u8 *k;
267 17657 : uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
268 :
269 17657 : mhash_sanitize_hash_user (h);
270 :
271 17657 : if (mhash_key_vector_is_heap (h))
272 : {
273 : mhash_string_key_t *sk;
274 278 : uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
275 : uword handle;
276 :
277 278 : n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
278 278 : i =
279 278 : heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
280 : handle);
281 :
282 278 : sk = (void *) (h->key_vector_or_heap + i);
283 278 : sk->heap_handle = handle;
284 278 : sk->vec.len = n_key_bytes;
285 278 : clib_memcpy_fast (sk->vec.vector_data, key, n_key_bytes);
286 :
287 : /* Advance key past vector header. */
288 278 : i += sizeof (sk[0]);
289 : }
290 : else
291 : {
292 17379 : key_alloc_from_free_list = (l =
293 17379 : vec_len (h->key_vector_free_indices)) > 0;
294 17379 : if (key_alloc_from_free_list)
295 : {
296 4401 : i = h->key_vector_free_indices[l - 1];
297 4401 : k = vec_elt_at_index (h->key_vector_or_heap, i);
298 4401 : vec_set_len (h->key_vector_free_indices, l - 1);
299 : }
300 : else
301 : {
302 12978 : vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
303 12978 : i = k - h->key_vector_or_heap;
304 : }
305 :
306 17379 : n_key_bytes = h->n_key_bytes;
307 17379 : clib_memcpy_fast (k, key, n_key_bytes);
308 : }
309 17657 : ikey = i;
310 :
311 17657 : old_n_elts = hash_elts (h->hash);
312 17657 : h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
313 :
314 : /* If element already existed remove duplicate key. */
315 17657 : if (hash_elts (h->hash) == old_n_elts)
316 : {
317 : hash_pair_t *p;
318 :
319 : /* Fetch old key for return value. */
320 0 : p = hash_get_pair (h->hash, ikey);
321 0 : ikey = p->key;
322 :
323 : /* Remove duplicate key. */
324 0 : if (mhash_key_vector_is_heap (h))
325 : {
326 : mhash_string_key_t *sk;
327 0 : sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
328 0 : heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
329 : }
330 : else
331 : {
332 0 : if (key_alloc_from_free_list)
333 : {
334 0 : h->key_vector_free_indices[l] = i;
335 0 : vec_set_len (h->key_vector_free_indices, l + 1);
336 : }
337 : else
338 0 : vec_dec_len (h->key_vector_or_heap, h->n_key_bytes);
339 : }
340 : }
341 :
342 17657 : return ikey;
343 : }
344 :
345 : __clib_export uword
346 16145 : mhash_unset (mhash_t * h, void *key, uword * old_value)
347 : {
348 : hash_pair_t *p;
349 : uword i;
350 :
351 16145 : mhash_sanitize_hash_user (h);
352 16145 : i = mhash_set_tmp_key (h, key);
353 :
354 16145 : p = hash_get_pair (h->hash, i);
355 16145 : if (!p)
356 0 : return 0;
357 :
358 16145 : ASSERT (p->key != ~0);
359 16145 : i = p->key;
360 :
361 16145 : if (mhash_key_vector_is_heap (h))
362 : {
363 : mhash_string_key_t *sk;
364 276 : sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
365 276 : heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
366 : }
367 : else
368 15869 : vec_add1 (h->key_vector_free_indices, i);
369 :
370 16145 : hash_unset3 (h->hash, i, old_value);
371 16145 : return 1;
372 : }
373 :
374 : u8 *
375 0 : format_mhash_key (u8 * s, va_list * va)
376 : {
377 0 : mhash_t *h = va_arg (*va, mhash_t *);
378 0 : u32 ki = va_arg (*va, u32);
379 0 : void *k = mhash_key_to_mem (h, ki);
380 :
381 0 : if (mhash_key_vector_is_heap (h))
382 : {
383 0 : uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
384 0 : u32 l = is_c_string ? strlen (k) : vec_len (k);
385 0 : vec_add (s, k, l);
386 : }
387 0 : else if (h->format_key)
388 0 : s = format (s, "%U", h->format_key, k);
389 : else
390 0 : s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
391 :
392 0 : return s;
393 : }
394 :
395 : /*
396 : * fd.io coding-style-patch-verification: ON
397 : *
398 : * Local Variables:
399 : * eval: (c-set-style "gnu")
400 : * End:
401 : */
|
