FD.io VPP  v21.06-3-gbb25fbf28
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 __clib_export 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 
193  heap_free (h->key_vector_or_heap);
194  else
195  vec_free (h->key_vector_or_heap);
196  vec_free (h->key_vector_free_indices);
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 
208  vec_validate (h->key_tmps, os_get_nthreads () - 1);
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 
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 __clib_export 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 __clib_export 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 
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 =
293  vec_len (h->key_vector_free_indices)) > 0;
294  if (key_alloc_from_free_list)
295  {
296  i = h->key_vector_free_indices[l - 1];
297  k = vec_elt_at_index (h->key_vector_or_heap, i);
298  _vec_len (h->key_vector_free_indices) = l - 1;
299  }
300  else
301  {
302  vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
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. */
325  {
326  mhash_string_key_t *sk;
327  sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
328  heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
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 __clib_export 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 
362  {
363  mhash_string_key_t *sk;
364  sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
365  heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
366  }
367  else
368  vec_add1 (h->key_vector_free_indices, i);
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 
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  */
vec_reset_length
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
Definition: vec_bootstrap.h:194
hash_header
Definition: hash.h:53
vec_add
#define vec_add(V, E, N)
Add N elements to end of vector V (no header, unspecified alignment)
Definition: vec.h:688
mhash.h
mhash_get_pair
__clib_export hash_pair_t * mhash_get_pair(mhash_t *h, const void *key)
Definition: mhash.c:247
mhash_t::hash
uword * hash
Definition: mhash.h:69
pointer_to_uword
static uword pointer_to_uword(const void *p)
Definition: types.h:131
mhash_key_to_mem
static void * mhash_key_to_mem(mhash_t *h, uword key)
Definition: mhash.h:90
mhash_string_key_t
Definition: mhash.c:255
hash_header
static hash_t * hash_header(void *v)
Definition: hash.h:111
format_hex_bytes
u8 * format_hex_bytes(u8 *s, va_list *va)
Definition: std-formats.c:84
mhash_t
Definition: mhash.h:46
format_mhash_key
u8 * format_mhash_key(u8 *s, va_list *va)
Definition: mhash.c:375
hash_get_pair
#define hash_get_pair(h, key)
Definition: hash.h:252
u16
unsigned short u16
Definition: types.h:57
hash_key_equal_function_t
uword() hash_key_equal_function_t(struct hash_header *, uword key1, uword key2)
Definition: hash.h:50
mhash_init
__clib_export void mhash_init(mhash_t *h, uword n_value_bytes, uword n_key_bytes)
Definition: mhash.c:168
clib_memcpy_fast
static_always_inline void * clib_memcpy_fast(void *restrict dst, const void *restrict src, size_t n)
Definition: string.h:92
load_partial_u32
static u32 load_partial_u32(void *d, uword n)
Definition: mhash.c:41
h
h
Definition: flowhash_template.h:372
key
typedef key
Definition: ipsec_types.api:88
MHASH_VEC_STRING_KEY
#define MHASH_VEC_STRING_KEY
Definition: mhash.h:61
hash_key_sum_function_t
uword() hash_key_sum_function_t(struct hash_header *, uword key)
Definition: hash.h:48
hash_unset3
#define hash_unset3(h, key, old_value)
Definition: hash.h:264
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
MHASH_C_STRING_KEY
#define MHASH_C_STRING_KEY
Definition: mhash.h:62
vec_add2
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:644
vec_add1
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:606
os_get_nthreads
uword os_get_nthreads(void)
Definition: unix-misc.c:225
mhash_key_sum_c_string
static foreach_mhash_key_size uword mhash_key_sum_c_string(hash_t *h, uword key)
Definition: mhash.c:122
hash_free
#define hash_free(h)
Definition: hash.h:310
vec_elt_at_index
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
Definition: vec_bootstrap.h:203
ARRAY_LEN
#define ARRAY_LEN(x)
Definition: clib.h:70
c
svmdb_client_t * c
Definition: vpp_get_metrics.c:48
foreach_mhash_key_size
#define foreach_mhash_key_size
Definition: mhash.c:93
uword
u64 uword
Definition: types.h:112
vec_header_t::vector_data
u8 vector_data[0]
Vector data .
Definition: vec_bootstrap.h:60
hash_create2
#define hash_create2(_elts, _user, _value_bytes, _key_sum, _key_equal, _format_pair, _format_pair_arg)
Definition: hash.h:493
mhash_key_equal_c_string
static uword mhash_key_equal_c_string(hash_t *h, uword key1, uword key2)
Definition: mhash.c:130
mhash_key_sum_vec_string
static uword mhash_key_sum_vec_string(hash_t *h, uword key)
Definition: mhash.c:139
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:261
mhash_key_vector_is_heap
static uword mhash_key_vector_is_heap(mhash_t *h)
Definition: mhash.h:143
vec_validate
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment)
Definition: vec.h:523
hash_v3_finalize32
#define hash_v3_finalize32(a, b, c)
Definition: hash.h:563
os_get_thread_index
static_always_inline uword os_get_thread_index(void)
Definition: os.h:63
mhash_set_tmp_key
static uword mhash_set_tmp_key(mhash_t *h, const void *key)
Definition: mhash.c:220
heap_free
#define heap_free(v)
Definition: heap.h:347
heap_dealloc
__clib_export void heap_dealloc(void *v, uword handle)
Definition: heap.c:500
data
u8 data[128]
Definition: ipsec_types.api:92
hash_elts
static uword hash_elts(void *v)
Definition: hash.h:118
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
mhash_t::hash_seed
u32 hash_seed
Definition: mhash.h:66
mhash_string_key_t::heap_handle
u32 heap_handle
Definition: mhash.c:257
format
description fragment has unexpected format
Definition: map.api:433
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
u32
unsigned int u32
Definition: types.h:88
hash_pair_t::key
uword key
Definition: hash.h:162
n_left
u32 n_left
Definition: interface_output.c:1078
mhash_key_sum_inline
static u32 mhash_key_sum_inline(void *data, uword n_data_bytes, u32 seed)
Definition: mhash.c:56
vec_header_t
vector header structure
Definition: vec_bootstrap.h:55
key_equal
static uword key_equal(hash_t *h, uword key1, uword key2)
Definition: hash.c:383
clib_memset
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
heap_alloc
#define heap_alloc(v, size, handle)
Definition: heap.h:337
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
mhash_key_equal_vec_string
static uword mhash_key_equal_vec_string(hash_t *h, uword key1, uword key2)
Definition: mhash.c:147
u8
unsigned char u8
Definition: types.h:56
a
a
Definition: bitmap.h:544
uword_to_pointer
#define uword_to_pointer(u, type)
Definition: types.h:136
mhash_string_key_t::vec
vec_header_t vec
Definition: mhash.c:260
mhash_sanitize_hash_user
static void mhash_sanitize_hash_user(mhash_t *mh)
Definition: mhash.c:160
vec_header_t::len
u32 len
Number of elements in vector (NOT its allocated length).
Definition: vec_bootstrap.h:57
hash_v3_mix32
#define hash_v3_mix32(a, b, c)
Definition: hash.h:553
mhash_set_mem
__clib_export uword mhash_set_mem(mhash_t *h, void *key, uword *new_value, uword *old_value)
Definition: mhash.c:264
mhash_unset
__clib_export uword mhash_unset(mhash_t *h, void *key, uword *old_value)
Definition: mhash.c:346
hash_pair_t
Definition: hash.h:159
key_sum
static uword key_sum(hash_t *h, uword key)
Definition: hash.c:315