FD.io VPP  v20.01-48-g3e0dafb74
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  clib_memset (h, 0, sizeof (h[0]));
206  h->n_key_bytes = n_key_bytes;
207 
209 
210  ASSERT (n_key_bytes < ARRAY_LEN (t));
211  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 }
218 
219 static uword
220 mhash_set_tmp_key (mhash_t * h, const void *key)
221 {
222  u8 *key_tmp;
223  int my_cpu = os_get_thread_index ();
224 
225  key_tmp = h->key_tmps[my_cpu];
226 
227  vec_reset_length (key_tmp);
228 
229  if (mhash_key_vector_is_heap (h))
230  {
231  uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
232 
233  if (is_c_string)
234  vec_add (key_tmp, key, strlen (key) + 1);
235  else
236  vec_add (key_tmp, key, vec_len (key));
237  }
238  else
239  vec_add (key_tmp, key, h->n_key_bytes);
240 
241  h->key_tmps[my_cpu] = key_tmp;
242 
243  return ~0;
244 }
245 
246 hash_pair_t *
247 mhash_get_pair (mhash_t * h, const void *key)
248 {
249  uword ikey;
251  ikey = mhash_set_tmp_key (h, key);
252  return hash_get_pair (h->hash, ikey);
253 }
254 
255 typedef struct
256 {
258 
259  /* Must coincide with vec_header. */
262 
263 uword
264 mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
265 {
266  u8 *k;
267  uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
268 
270 
271  if (mhash_key_vector_is_heap (h))
272  {
273  mhash_string_key_t *sk;
274  uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
275  uword handle;
276 
277  n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
278  i =
279  heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
280  handle);
281 
282  sk = (void *) (h->key_vector_or_heap + i);
283  sk->heap_handle = handle;
284  sk->vec.len = n_key_bytes;
285  clib_memcpy_fast (sk->vec.vector_data, key, n_key_bytes);
286 
287  /* Advance key past vector header. */
288  i += sizeof (sk[0]);
289  }
290  else
291  {
292  key_alloc_from_free_list = (l =
294  if (key_alloc_from_free_list)
295  {
296  i = h->key_vector_free_indices[l - 1];
298  _vec_len (h->key_vector_free_indices) = l - 1;
299  }
300  else
301  {
303  i = k - h->key_vector_or_heap;
304  }
305 
306  n_key_bytes = h->n_key_bytes;
307  clib_memcpy_fast (k, key, n_key_bytes);
308  }
309  ikey = i;
310 
311  old_n_elts = hash_elts (h->hash);
312  h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
313 
314  /* If element already existed remove duplicate key. */
315  if (hash_elts (h->hash) == old_n_elts)
316  {
317  hash_pair_t *p;
318 
319  /* Fetch old key for return value. */
320  p = hash_get_pair (h->hash, ikey);
321  ikey = p->key;
322 
323  /* Remove duplicate key. */
324  if (mhash_key_vector_is_heap (h))
325  {
326  mhash_string_key_t *sk;
327  sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
329  }
330  else
331  {
332  if (key_alloc_from_free_list)
333  {
334  h->key_vector_free_indices[l] = i;
335  _vec_len (h->key_vector_free_indices) = l + 1;
336  }
337  else
338  _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
339  }
340  }
341 
342  return ikey;
343 }
344 
345 uword
346 mhash_unset (mhash_t * h, void *key, uword * old_value)
347 {
348  hash_pair_t *p;
349  uword i;
350 
352  i = mhash_set_tmp_key (h, key);
353 
354  p = hash_get_pair (h->hash, i);
355  if (!p)
356  return 0;
357 
358  ASSERT (p->key != ~0);
359  i = p->key;
360 
361  if (mhash_key_vector_is_heap (h))
362  {
363  mhash_string_key_t *sk;
364  sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
366  }
367  else
369 
370  hash_unset3 (h->hash, i, old_value);
371  return 1;
372 }
373 
374 u8 *
375 format_mhash_key (u8 * s, va_list * va)
376 {
377  mhash_t *h = va_arg (*va, mhash_t *);
378  u32 ki = va_arg (*va, u32);
379  void *k = mhash_key_to_mem (h, ki);
380 
381  if (mhash_key_vector_is_heap (h))
382  {
383  uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
384  u32 l = is_c_string ? strlen (k) : vec_len (k);
385  vec_add (s, k, l);
386  }
387  else if (h->format_key)
388  s = format (s, "%U", h->format_key, k);
389  else
390  s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
391 
392  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  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:440
#define foreach_mhash_key_size
Definition: mhash.c:93
Definition: mhash.h:46
any user
Definition: hash.h:86
static u32 load_partial_u32(void *d, uword n)
Definition: mhash.c:41
a
Definition: bitmap.h:538
#define clib_memcpy_fast(a, b, c)
Definition: string.h:81
uword mhash_unset(mhash_t *h, void *key, uword *old_value)
Definition: mhash.c:346
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
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:523
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:561
int i
vec_header_t vec
Definition: mhash.c:260
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:424
static uword mhash_key_vector_is_heap(mhash_t *h)
Definition: mhash.h:143
#define hash_v3_mix32(a, b, c)
Definition: hash.h:554
unsigned char u8
Definition: types.h:56
#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:599
u8 ** key_tmps
Definition: mhash.h:56
#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:315
#define hash_get_pair(h, key)
Definition: hash.h:252
unsigned int u32
Definition: types.h:88
static hash_t * hash_header(void *v)
Definition: hash.h:111
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:264
unsigned short u16
Definition: types.h:57
#define hash_free(h)
Definition: hash.h:310
#define always_inline
Definition: ipsec.h:28
u32 * key_vector_free_indices
Definition: mhash.h:54
uword() hash_key_equal_function_t(struct hash_header *, uword key1, uword key2)
Definition: hash.h:50
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:342
static uword mhash_key_sum_vec_string(hash_t *h, uword key)
Definition: mhash.c:139
#define ARRAY_LEN(x)
Definition: clib.h:62
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:60
#define uword_to_pointer(u, type)
Definition: types.h:136
static uword hash_elts(void *v)
Definition: hash.h:118
#define ASSERT(truth)
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:220
u8 data[128]
Definition: ipsec_types.api:87
uword() hash_key_sum_function_t(struct hash_header *, uword key)
Definition: hash.h:48
#define hash_v3_finalize32(a, b, c)
Definition: hash.h:564
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
static uword pointer_to_uword(const void *p)
Definition: types.h:131
static uword mhash_key_equal_c_string(hash_t *h, uword key1, uword key2)
Definition: mhash.c:130
typedef key
Definition: ipsec_types.api:83
#define hash_create2(_elts, _user, _value_bytes, _key_sum, _key_equal, _format_pair, _format_pair_arg)
Definition: hash.h:494
u8 vector_data[0]
Vector data .
Definition: vec_bootstrap.h:63
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u64 uword
Definition: types.h:112
uword os_get_nthreads(void)
Definition: unix-misc.c:226
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:247
#define MHASH_VEC_STRING_KEY
Definition: mhash.h:61
u8 * format_mhash_key(u8 *s, va_list *va)
Definition: mhash.c:375
static uword key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:383
uword key
Definition: hash.h:162
#define hash_unset3(h, key, old_value)
Definition: hash.h:264
static uword mhash_key_equal_vec_string(hash_t *h, uword key1, uword key2)
Definition: mhash.c:147