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 void
 168 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   if (mhash_key_vector_is_heap (h))
 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
 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;
 250   mhash_sanitize_hash_user (h);
 251   ikey = mhash_set_tmp_key (h, key);
 252   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 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
 269   mhash_sanitize_hash_user (h);
 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 =
 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. */
 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]));
 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 uword
 346 mhash_unset (mhash_t * h, void *key, uword * old_value)
 347 {
 348   hash_pair_t *p;
 349   uword i;
 350
 351   mhash_sanitize_hash_user (h);
 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]);
 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
 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  */