FD.io VPP  v18.04-17-g3a0d853
Vector Packet Processing
mhash.c
Go to the documentation of this file.
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 
41 load_partial_u32 (void *d, uword n)
42 {
43  if (n == 4)
44  return ((u32 *) d)[0];
45  if (n == 3)
46  return ((u16 *) d)[0] | (((u8 *) d)[2] << 16);
47  if (n == 2)
48  return ((u16 *) d)[0];
49  if (n == 1)
50  return ((u8 *) d)[0];
51  ASSERT (0);
52  return 0;
53 }
54 
56 mhash_key_sum_inline (void *data, uword n_data_bytes, u32 seed)
57 {
58  u32 *d32 = data;
59  u32 a, b, c, n_left;
60 
61  a = b = c = seed;
62  n_left = n_data_bytes;
63  a ^= n_data_bytes;
64 
65  while (n_left > 12)
66  {
67  a += d32[0];
68  b += d32[1];
69  c += d32[2];
70  hash_v3_mix32 (a, b, c);
71  n_left -= 12;
72  d32 += 3;
73  }
74 
75  if (n_left > 8)
76  {
77  c += load_partial_u32 (d32 + 2, n_left - 8);
78  n_left = 8;
79  }
80  if (n_left > 4)
81  {
82  b += load_partial_u32 (d32 + 1, n_left - 4);
83  n_left = 4;
84  }
85  if (n_left > 0)
86  a += load_partial_u32 (d32 + 0, n_left - 0);
87 
88  hash_v3_finalize32 (a, b, c);
89 
90  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 
120 #undef _
121 static uword
123 {
124  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
125  void *k = mhash_key_to_mem (hv, key);
126  return mhash_key_sum_inline (k, strlen (k), hv->hash_seed);
127 }
128 
129 static uword
131 {
132  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
133  void *k1 = mhash_key_to_mem (hv, key1);
134  void *k2 = mhash_key_to_mem (hv, key2);
135  return strcmp (k1, k2) == 0;
136 }
137 
138 static uword
140 {
141  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
142  void *k = mhash_key_to_mem (hv, key);
143  return mhash_key_sum_inline (k, vec_len (k), hv->hash_seed);
144 }
145 
146 static uword
148 {
149  mhash_t *hv = uword_to_pointer (h->user, mhash_t *);
150  void *k1 = mhash_key_to_mem (hv, key1);
151  void *k2 = mhash_key_to_mem (hv, key2);
152  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
161 {
162  uword *hash = mh->hash;
163  hash_t *h = hash_header (hash);
164  h->user = pointer_to_uword (mh);
165 }
166 
167 void
168 mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes)
169 {
170  static struct
171  {
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 
183 #undef _
185  {
186  .key_sum = mhash_key_sum_c_string,.key_equal = mhash_key_equal_c_string,},
188  {
189  .key_sum = mhash_key_sum_vec_string,.key_equal =
191 
192  if (mhash_key_vector_is_heap (h))
194  else
197  {
198  int i;
199  for (i = 0; i < vec_len (h->key_tmps); i++)
200  vec_free (h->key_tmps[i]);
201  }
202  vec_free (h->key_tmps);
203  hash_free (h->hash);
204 
205  memset (h, 0, sizeof (h[0]));
206  h->n_key_bytes = n_key_bytes;
207 
208 #if 0
209  if (h->n_key_bytes > 0)
210  {
211  vec_validate (h->key_tmp, h->n_key_bytes - 1);
212  _vec_len (h->key_tmp) = 0;
213  }
214 #endif
215 
216  ASSERT (n_key_bytes < ARRAY_LEN (t));
217  h->hash = hash_create2 ( /* elts */ 0,
218  /* user */ pointer_to_uword (h),
219  /* value_bytes */ n_value_bytes,
220  t[n_key_bytes].key_sum, t[n_key_bytes].key_equal,
221  /* format pair/arg */
222  0, 0);
223 }
224 
225 static uword
226 mhash_set_tmp_key (mhash_t * h, const void *key)
227 {
228  u8 *key_tmp;
229  int my_cpu = os_get_thread_index ();
230 
231  vec_validate (h->key_tmps, my_cpu);
232  key_tmp = h->key_tmps[my_cpu];
233 
234  vec_reset_length (key_tmp);
235 
236  if (mhash_key_vector_is_heap (h))
237  {
238  uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
239 
240  if (is_c_string)
241  vec_add (key_tmp, key, strlen (key) + 1);
242  else
243  vec_add (key_tmp, key, vec_len (key));
244  }
245  else
246  vec_add (key_tmp, key, h->n_key_bytes);
247 
248  h->key_tmps[my_cpu] = key_tmp;
249 
250  return ~0;
251 }
252 
253 hash_pair_t *
254 mhash_get_pair (mhash_t * h, const void *key)
255 {
256  uword ikey;
258  ikey = mhash_set_tmp_key (h, key);
259  return hash_get_pair (h->hash, ikey);
260 }
261 
262 typedef struct
263 {
265 
266  /* Must conincide with vec_header. */
269 
270 uword
271 mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
272 {
273  u8 *k;
274  uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
275 
277 
278  if (mhash_key_vector_is_heap (h))
279  {
280  mhash_string_key_t *sk;
281  uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
282  uword handle;
283 
284  n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
285  i =
286  heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
287  handle);
288 
289  sk = (void *) (h->key_vector_or_heap + i);
290  sk->heap_handle = handle;
291  sk->vec.len = n_key_bytes;
292  clib_memcpy (sk->vec.vector_data, key, n_key_bytes);
293 
294  /* Advance key past vector header. */
295  i += sizeof (sk[0]);
296  }
297  else
298  {
299  key_alloc_from_free_list = (l =
301  if (key_alloc_from_free_list)
302  {
303  i = h->key_vector_free_indices[l - 1];
305  _vec_len (h->key_vector_free_indices) = l - 1;
306  }
307  else
308  {
310  i = k - h->key_vector_or_heap;
311  }
312 
313  n_key_bytes = h->n_key_bytes;
314  clib_memcpy (k, key, n_key_bytes);
315  }
316  ikey = i;
317 
318  old_n_elts = hash_elts (h->hash);
319  h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
320 
321  /* If element already existed remove duplicate key. */
322  if (hash_elts (h->hash) == old_n_elts)
323  {
324  hash_pair_t *p;
325 
326  /* Fetch old key for return value. */
327  p = hash_get_pair (h->hash, ikey);
328  ikey = p->key;
329 
330  /* Remove duplicate key. */
331  if (mhash_key_vector_is_heap (h))
332  {
333  mhash_string_key_t *sk;
334  sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
336  }
337  else
338  {
339  if (key_alloc_from_free_list)
340  {
341  h->key_vector_free_indices[l] = i;
342  _vec_len (h->key_vector_free_indices) = l + 1;
343  }
344  else
345  _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
346  }
347  }
348 
349  return ikey;
350 }
351 
352 uword
353 mhash_unset (mhash_t * h, void *key, uword * old_value)
354 {
355  hash_pair_t *p;
356  uword i;
357 
359  i = mhash_set_tmp_key (h, key);
360 
361  p = hash_get_pair (h->hash, i);
362  if (!p)
363  return 0;
364 
365  ASSERT (p->key != ~0);
366  i = p->key;
367 
368  if (mhash_key_vector_is_heap (h))
369  {
370  mhash_string_key_t *sk;
371  sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
373  }
374  else
376 
377  hash_unset3 (h->hash, i, old_value);
378  return 1;
379 }
380 
381 u8 *
382 format_mhash_key (u8 * s, va_list * va)
383 {
384  mhash_t *h = va_arg (*va, mhash_t *);
385  u32 ki = va_arg (*va, u32);
386  void *k = mhash_key_to_mem (h, ki);
387 
388  if (mhash_key_vector_is_heap (h))
389  {
390  uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
391  u32 l = is_c_string ? strlen (k) : vec_len (k);
392  vec_add (s, k, l);
393  }
394  else if (h->format_key)
395  s = format (s, "%U", h->format_key, k);
396  else
397  s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
398 
399  return s;
400 }
401 
402 /*
403  * fd.io coding-style-patch-verification: ON
404  *
405  * Local Variables:
406  * eval: (c-set-style "gnu")
407  * End:
408  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:434
#define foreach_mhash_key_size
Definition: mhash.c:93
Definition: mhash.h:46
any user
Definition: hash.h:85
static u32 load_partial_u32(void *d, uword n)
Definition: mhash.c:41
a
Definition: bitmap.h:516
uword mhash_unset(mhash_t *h, void *key, uword *old_value)
Definition: mhash.c:353
format_function_t * format_key
Definition: mhash.h:72
u32 n_key_bytes
Definition: mhash.h:63
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:520
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:559
int i
vec_header_t vec
Definition: mhash.c:267
static u32 mhash_key_sum_inline(void *data, uword n_data_bytes, u32 seed)
Definition: mhash.c:56
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
uword( hash_key_equal_function_t)(struct hash_header *, uword key1, uword key2)
Definition: hash.h:50
static uword mhash_key_vector_is_heap(mhash_t *h)
Definition: mhash.h:143
#define hash_v3_mix32(a, b, c)
Definition: hash.h:553
#define heap_free(v)
Definition: heap.h:347
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
u32 hash_seed
Definition: mhash.h:66
#define vec_add(V, E, N)
Add N elements to end of vector V (no header, unspecified alignment)
Definition: vec.h:597
u8 ** key_tmps
Definition: mhash.h:56
#define always_inline
Definition: clib.h:92
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
u8 * format_hex_bytes(u8 *s, va_list *va)
Definition: std-formats.c:84
static uword key_sum(hash_t *h, uword key)
Definition: hash.c:264
#define hash_get_pair(h, key)
Definition: hash.h:251
static uword pointer_to_uword(const void *p)
Definition: types.h:131
static hash_t * hash_header(void *v)
Definition: hash.h:110
static void mhash_sanitize_hash_user(mhash_t *mh)
Definition: mhash.c:160
uword mhash_set_mem(mhash_t *h, void *key, uword *new_value, uword *old_value)
Definition: mhash.c:271
#define hash_free(h)
Definition: hash.h:309
u32 * key_vector_free_indices
Definition: mhash.h:54
#define uword_to_pointer(u, type)
Definition: types.h:136
void mhash_init(mhash_t *h, uword n_value_bytes, uword n_key_bytes)
Definition: mhash.c:168
svmdb_client_t * c
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:336
static uword mhash_key_sum_vec_string(hash_t *h, uword key)
Definition: mhash.c:139
#define clib_memcpy(a, b, c)
Definition: string.h:75
#define ARRAY_LEN(x)
Definition: clib.h:59
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:60
#define hash_create2(_elts, _user, _value_bytes,_key_sum, _key_equal,_format_pair, _format_pair_arg)
Definition: hash.h:493
static uword hash_elts(void *v)
Definition: hash.h:117
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
u8 * key_vector_or_heap
Definition: mhash.h:50
static foreach_mhash_key_size uword mhash_key_sum_c_string(hash_t *h, uword key)
Definition: mhash.c:122
static uword mhash_set_tmp_key(mhash_t *h, const void *key)
Definition: mhash.c:226
#define hash_v3_finalize32(a, b, c)
Definition: hash.h:563
void heap_dealloc(void *v, uword handle)
Definition: heap.c:496
vector header structure
Definition: vec_bootstrap.h:55
#define heap_alloc(v, size, handle)
Definition: heap.h:337
uword * hash
Definition: mhash.h:69
u64 uword
Definition: types.h:112
static uword mhash_key_equal_c_string(hash_t *h, uword key1, uword key2)
Definition: mhash.c:130
uword( hash_key_sum_function_t)(struct hash_header *, uword key)
Definition: hash.h:48
unsigned short u16
Definition: types.h:57
u8 vector_data[0]
Vector data .
Definition: vec_bootstrap.h:62
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
static_always_inline uword os_get_thread_index(void)
Definition: os.h:62
static void * mhash_key_to_mem(mhash_t *h, uword key)
Definition: mhash.h:90
#define MHASH_C_STRING_KEY
Definition: mhash.h:62
hash_pair_t * mhash_get_pair(mhash_t *h, const void *key)
Definition: mhash.c:254
#define MHASH_VEC_STRING_KEY
Definition: mhash.h:61
u8 * format_mhash_key(u8 *s, va_list *va)
Definition: mhash.c:382
static uword key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:324
uword key
Definition: hash.h:161
#define hash_unset3(h, key, old_value)
Definition: hash.h:263
static uword mhash_key_equal_vec_string(hash_t *h, uword key1, uword key2)
Definition: mhash.c:147