src/vppinfra/mhash.c

   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 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
  55 always_inline u32
  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
 119 foreach_mhash_key_size
 120 #undef _
 121 static uword
 122 mhash_key_sum_c_string (hash_t * h, uword key)
 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
 130 mhash_key_equal_c_string (hash_t * h, uword key1, uword key2)
 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
 139 mhash_key_sum_vec_string (hash_t * h, uword key)
 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
 147 mhash_key_equal_vec_string (hash_t * h, uword key1, uword key2)
 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
 160 mhash_sanitize_hash_user (mhash_t * mh)
 161 {
 162   uword *hash = mh->hash;
 163   hash_t *h = hash_header (hash);
 164   h->user = pointer_to_uword (mh);
 165 }
 166
 167 static u8 *mhash_format_pair_default (u8 *s, va_list *args);
 168
 169 __clib_export void
 170 mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes)
 171 {
 172   static struct
 173   {
 174     hash_key_sum_function_t *key_sum;
 175     hash_key_equal_function_t *key_equal;
 176   } t[] =
 177   {
 178 #define _(N_KEY_BYTES)                                  \
 179     [N_KEY_BYTES] = {                                   \
 180       .key_sum = mhash_key_sum_##N_KEY_BYTES,           \
 181       .key_equal = mhash_key_equal_##N_KEY_BYTES,       \
 182     },
 183
 184     foreach_mhash_key_size
 185 #undef _
 186       [MHASH_C_STRING_KEY] =
 187     {
 188     .key_sum = mhash_key_sum_c_string,.key_equal = mhash_key_equal_c_string,},
 189       [MHASH_VEC_STRING_KEY] =
 190     {
 191   .key_sum = mhash_key_sum_vec_string,.key_equal =
 192         mhash_key_equal_vec_string,},};
 193
 194   if (mhash_key_vector_is_heap (h))
 195     heap_free (h->key_vector_or_heap);
 196   else
 197     vec_free (h->key_vector_or_heap);
 198   vec_free (h->key_vector_free_indices);
 199   {
 200     int i;
 201     for (i = 0; i < vec_len (h->key_tmps); i++)
 202       vec_free (h->key_tmps[i]);
 203   }
 204   vec_free (h->key_tmps);
 205   hash_free (h->hash);
 206
 207   clib_memset (h, 0, sizeof (h[0]));
 208   h->n_key_bytes = n_key_bytes;
 209
 210   vec_validate (h->key_tmps, os_get_nthreads () - 1);
 211
 212   ASSERT (n_key_bytes < ARRAY_LEN (t));
 213   h->hash = hash_create2 (/* elts */ 0,
 214                           /* user */ pointer_to_uword (h),
 215                           /* value_bytes */ n_value_bytes,
 216                           t[n_key_bytes].key_sum, t[n_key_bytes].key_equal,
 217                           /* format pair/arg */
 218                           mhash_format_pair_default, 0);
 219 }
 220
 221 static uword
 222 mhash_set_tmp_key (mhash_t * h, const void *key)
 223 {
 224   u8 *key_tmp;
 225   int my_cpu = os_get_thread_index ();
 226
 227   key_tmp = h->key_tmps[my_cpu];
 228
 229   vec_reset_length (key_tmp);
 230
 231   if (mhash_key_vector_is_heap (h))
 232     {
 233       uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
 234
 235       if (is_c_string)
 236         vec_add (key_tmp, key, strlen (key) + 1);
 237       else
 238         vec_add (key_tmp, key, vec_len (key));
 239     }
 240   else
 241     vec_add (key_tmp, key, h->n_key_bytes);
 242
 243   h->key_tmps[my_cpu] = key_tmp;
 244
 245   return ~0;
 246 }
 247
 248 __clib_export hash_pair_t *
 249 mhash_get_pair (mhash_t * h, const void *key)
 250 {
 251   uword ikey;
 252   mhash_sanitize_hash_user (h);
 253   ikey = mhash_set_tmp_key (h, key);
 254   return hash_get_pair (h->hash, ikey);
 255 }
 256
 257 typedef struct
 258 {
 259   u32 heap_handle;
 260
 261   /* Must coincide with vec_header. */
 262   vec_header_t vec;
 263 } mhash_string_key_t;
 264
 265 __clib_export uword
 266 mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value)
 267 {
 268   u8 *k;
 269   uword ikey, i, l = 0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
 270
 271   mhash_sanitize_hash_user (h);
 272
 273   if (mhash_key_vector_is_heap (h))
 274     {
 275       mhash_string_key_t *sk;
 276       uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
 277       uword handle;
 278
 279       n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
 280       i =
 281         heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]),
 282                     handle);
 283
 284       sk = (void *) (h->key_vector_or_heap + i);
 285       sk->heap_handle = handle;
 286       sk->vec.len = n_key_bytes;
 287       clib_memcpy_fast (sk->vec.vector_data, key, n_key_bytes);
 288
 289       /* Advance key past vector header. */
 290       i += sizeof (sk[0]);
 291     }
 292   else
 293     {
 294       key_alloc_from_free_list = (l =
 295                                   vec_len (h->key_vector_free_indices)) > 0;
 296       if (key_alloc_from_free_list)
 297         {
 298           i = h->key_vector_free_indices[l - 1];
 299           k = vec_elt_at_index (h->key_vector_or_heap, i);
 300           vec_set_len (h->key_vector_free_indices, l - 1);
 301         }
 302       else
 303         {
 304           vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
 305           i = k - h->key_vector_or_heap;
 306         }
 307
 308       n_key_bytes = h->n_key_bytes;
 309       clib_memcpy_fast (k, key, n_key_bytes);
 310     }
 311   ikey = i;
 312
 313   old_n_elts = hash_elts (h->hash);
 314   h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
 315
 316   /* If element already existed remove duplicate key. */
 317   if (hash_elts (h->hash) == old_n_elts)
 318     {
 319       hash_pair_t *p;
 320
 321       /* Fetch old key for return value. */
 322       p = hash_get_pair (h->hash, ikey);
 323       ikey = p->key;
 324
 325       /* Remove duplicate key. */
 326       if (mhash_key_vector_is_heap (h))
 327         {
 328           mhash_string_key_t *sk;
 329           sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
 330           heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
 331         }
 332       else
 333         {
 334           if (key_alloc_from_free_list)
 335             {
 336               vec_set_len (h->key_vector_free_indices, l);
 337               h->key_vector_free_indices[l - 1] = i;
 338             }
 339           else
 340             vec_dec_len (h->key_vector_or_heap, h->n_key_bytes);
 341         }
 342     }
 343
 344   return ikey;
 345 }
 346
 347 __clib_export uword
 348 mhash_unset (mhash_t * h, void *key, uword * old_value)
 349 {
 350   hash_pair_t *p;
 351   uword i;
 352
 353   mhash_sanitize_hash_user (h);
 354   i = mhash_set_tmp_key (h, key);
 355
 356   p = hash_get_pair (h->hash, i);
 357   if (!p)
 358     return 0;
 359
 360   ASSERT (p->key != ~0);
 361   i = p->key;
 362
 363   if (mhash_key_vector_is_heap (h))
 364     {
 365       mhash_string_key_t *sk;
 366       sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
 367       heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
 368     }
 369   else
 370     vec_add1 (h->key_vector_free_indices, i);
 371
 372   hash_unset3 (h->hash, i, old_value);
 373   return 1;
 374 }
 375
 376 __clib_export u8 *
 377 format_mhash_key (u8 *s, va_list *va)
 378 {
 379   mhash_t *h = va_arg (*va, mhash_t *);
 380   u32 ki = va_arg (*va, u32);
 381   void *k = mhash_key_to_mem (h, ki);
 382
 383   if (mhash_key_vector_is_heap (h))
 384     {
 385       uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
 386       u32 l = is_c_string ? strlen (k) : vec_len (k);
 387       vec_add (s, k, l);
 388     }
 389   else if (h->format_key)
 390     s = format (s, "%U", h->format_key, k);
 391   else
 392     s = format (s, "0x%U", format_hex_bytes, k, h->n_key_bytes);
 393
 394   return s;
 395 }
 396
 397 static u8 *
 398 mhash_format_pair_default (u8 *s, va_list *args)
 399 {
 400   void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
 401   void *v = va_arg (*args, void *);
 402   hash_pair_t *p = va_arg (*args, hash_pair_t *);
 403   hash_t *h = hash_header (v);
 404   mhash_t *mh = uword_to_pointer (h->user, mhash_t *);
 405
 406   s = format (s, "%U", format_mhash_key, mh, (u32) p->key);
 407   if (hash_value_bytes (h) > 0)
 408     s = format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
 409                 hash_value_bytes (h));
 410   return s;
 411 }
 412
 413 __clib_export u8 *
 414 format_mhash (u8 *s, va_list *va)
 415 {
 416   mhash_t *h = va_arg (*va, mhash_t *);
 417   int verbose = va_arg (*va, int);
 418
 419   s = format (s, "mhash %p, %wd elts, \n", h, mhash_elts (h));
 420   if (mhash_key_vector_is_heap (h))
 421     s = format (s, "  %U", format_heap, h->key_vector_or_heap, verbose);
 422   else
 423     s = format (s, "  keys %wd elts, %wd size, %wd free, %wd bytes used\n",
 424                 vec_len (h->key_vector_or_heap) / h->n_key_bytes,
 425                 h->n_key_bytes, vec_len (h->key_vector_free_indices),
 426                 vec_bytes (h->key_vector_or_heap) +
 427                   vec_bytes (h->key_vector_free_indices));
 428   s = format (s, "  %U", format_hash, h->hash, verbose);
 429
 430   return s;
 431 }
 432
 433 /*
 434  * fd.io coding-style-patch-verification: ON
 435  *
 436  * Local Variables:
 437  * eval: (c-set-style "gnu")
 438  * End:
 439  */