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   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;
 257   mhash_sanitize_hash_user (h);
 258   ikey = mhash_set_tmp_key (h, key);
 259   return hash_get_pair (h->hash, ikey);
 260 }
 261
 262 typedef struct
 263 {
 264   u32 heap_handle;
 265
 266   /* Must coincide with vec_header. */
 267   vec_header_t vec;
 268 } mhash_string_key_t;
 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
 276   mhash_sanitize_hash_user (h);
 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 =
 300                                   vec_len (h->key_vector_free_indices)) > 0;
 301       if (key_alloc_from_free_list)
 302         {
 303           i = h->key_vector_free_indices[l - 1];
 304           k = vec_elt_at_index (h->key_vector_or_heap, i);
 305           _vec_len (h->key_vector_free_indices) = l - 1;
 306         }
 307       else
 308         {
 309           vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
 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]));
 335           heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
 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
 358   mhash_sanitize_hash_user (h);
 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]);
 372       heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
 373     }
 374   else
 375     vec_add1 (h->key_vector_free_indices, i);
 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  */