vppinfra/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
 121 #undef _
 122
 123 static uword
 124 mhash_key_sum_c_string (hash_t * h, uword key)
 125 {
 126   mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
 127   void * k = mhash_key_to_mem (hv, key);
 128   return mhash_key_sum_inline (k, strlen (k), hv->hash_seed);
 129 }
 130
 131 static uword
 132 mhash_key_equal_c_string (hash_t * h, uword key1, uword key2)
 133 {
 134   mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
 135   void * k1 = mhash_key_to_mem (hv, key1);
 136   void * k2 = mhash_key_to_mem (hv, key2);
 137   return strcmp (k1, k2) == 0;
 138 }
 139
 140 static uword
 141 mhash_key_sum_vec_string (hash_t * h, uword key)
 142 {
 143   mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
 144   void * k = mhash_key_to_mem (hv, key);
 145   return mhash_key_sum_inline (k, vec_len (k), hv->hash_seed);
 146 }
 147
 148 static uword
 149 mhash_key_equal_vec_string (hash_t * h, uword key1, uword key2)
 150 {
 151   mhash_t * hv = uword_to_pointer (h->user, mhash_t *);
 152   void * k1 = mhash_key_to_mem (hv, key1);
 153   void * k2 = mhash_key_to_mem (hv, key2);
 154   return vec_len (k1) == vec_len (k2) && memcmp (k1, k2, vec_len (k1)) == 0;
 155 }
 156
 157 /* The CLIB hash user pointer must always point to a valid mhash_t.
 158    Now, the address of mhash_t can change (think vec_resize).
 159    So we must always be careful that it points to the correct
 160    address. */
 161 always_inline void
 162 mhash_sanitize_hash_user (mhash_t * mh)
 163 {
 164   uword * hash = mh->hash;
 165   hash_t * h = hash_header (hash);
 166   h->user = pointer_to_uword (mh);
 167 }
 168
 169 void mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes)
 170 {
 171   static struct {
 172     hash_key_sum_function_t * key_sum;
 173     hash_key_equal_function_t * key_equal;
 174   } t[] = {
 175 #define _(N_KEY_BYTES)                                  \
 176     [N_KEY_BYTES] = {                                   \
 177       .key_sum = mhash_key_sum_##N_KEY_BYTES,           \
 178       .key_equal = mhash_key_equal_##N_KEY_BYTES,       \
 179     },
 180
 181     foreach_mhash_key_size
 182
 183 #undef _
 184
 185     [MHASH_C_STRING_KEY] = {
 186       .key_sum = mhash_key_sum_c_string,
 187       .key_equal = mhash_key_equal_c_string,
 188     },
 189
 190     [MHASH_VEC_STRING_KEY] = {
 191       .key_sum = mhash_key_sum_vec_string,
 192       .key_equal = mhash_key_equal_vec_string,
 193     },
 194   };
 195
 196   if (mhash_key_vector_is_heap (h))
 197     heap_free (h->key_vector_or_heap);
 198   else
 199     vec_free (h->key_vector_or_heap);
 200   vec_free (h->key_vector_free_indices);
 201   {
 202     int i;
 203     for (i = 0; i < vec_len (h->key_tmps); i++)
 204       vec_free (h->key_tmps[i]);
 205   }
 206   vec_free (h->key_tmps);
 207   hash_free (h->hash);
 208
 209   memset (h, 0, sizeof (h[0]));
 210   h->n_key_bytes = n_key_bytes;
 211
 212 #if 0
 213   if (h->n_key_bytes > 0)
 214     {
 215       vec_validate (h->key_tmp, h->n_key_bytes-1);
 216       _vec_len(h->key_tmp) = 0;
 217     }
 218 #endif
 219
 220   ASSERT (n_key_bytes < ARRAY_LEN (t));
 221   h->hash = hash_create2 (/* elts */ 0,
 222                           /* user */ pointer_to_uword (h),
 223                           /* value_bytes */ n_value_bytes,
 224                           t[n_key_bytes].key_sum,
 225                           t[n_key_bytes].key_equal,
 226                           /* format pair/arg */
 227                           0, 0);
 228 }
 229
 230 static uword mhash_set_tmp_key (mhash_t * h, void * key)
 231 {
 232   u8 * key_tmp;
 233   int my_cpu = os_get_cpu_number();
 234
 235   vec_validate(h->key_tmps, my_cpu);
 236   key_tmp = h->key_tmps[my_cpu];
 237
 238   vec_reset_length (key_tmp);
 239
 240   if (mhash_key_vector_is_heap (h))
 241     {
 242       uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
 243
 244       if (is_c_string)
 245         vec_add (key_tmp, key, strlen (key) + 1);
 246       else
 247         vec_add (key_tmp, key, vec_len (key));
 248     }
 249   else
 250     vec_add (key_tmp, key, h->n_key_bytes);
 251
 252   h->key_tmps[my_cpu] = key_tmp;
 253
 254   return ~0;
 255 }
 256
 257 hash_pair_t * mhash_get_pair (mhash_t * h, void * key)
 258 {
 259   uword ikey;
 260   mhash_sanitize_hash_user (h);
 261   ikey = mhash_set_tmp_key (h, key);
 262   return hash_get_pair (h->hash, ikey);
 263 }
 264
 265 typedef struct {
 266   u32 heap_handle;
 267
 268   /* Must conincide with vec_header. */
 269   vec_header_t vec;
 270 } mhash_string_key_t;
 271
 272 uword mhash_set_mem (mhash_t * h, void * key, uword * new_value, uword * old_value)
 273 {
 274   u8 * k;
 275   uword ikey, i, l=0, n_key_bytes, old_n_elts, key_alloc_from_free_list = 0;
 276
 277   mhash_sanitize_hash_user (h);
 278
 279   if (mhash_key_vector_is_heap (h))
 280     {
 281       mhash_string_key_t * sk;
 282       uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
 283       uword handle;
 284
 285       n_key_bytes = is_c_string ? (strlen (key) + 1) : vec_len (key);
 286       i = heap_alloc (h->key_vector_or_heap, n_key_bytes + sizeof (sk[0]), handle);
 287
 288       sk = (void *) (h->key_vector_or_heap + i);
 289       sk->heap_handle = handle;
 290       sk->vec.len = n_key_bytes;
 291       memcpy (sk->vec.vector_data, key, n_key_bytes);
 292
 293       /* Advance key past vector header. */
 294       i += sizeof (sk[0]);
 295     }
 296   else
 297     {
 298       key_alloc_from_free_list = (l = vec_len (h->key_vector_free_indices)) > 0;
 299       if (key_alloc_from_free_list)
 300         {
 301           i = h->key_vector_free_indices[l - 1];
 302           k = vec_elt_at_index (h->key_vector_or_heap, i);
 303           _vec_len (h->key_vector_free_indices) = l - 1;
 304         }
 305       else
 306         {
 307           vec_add2 (h->key_vector_or_heap, k, h->n_key_bytes);
 308           i = k - h->key_vector_or_heap;
 309         }
 310
 311       n_key_bytes = h->n_key_bytes;
 312       memcpy (k, key, n_key_bytes);
 313     }
 314   ikey = i;
 315
 316   old_n_elts = hash_elts (h->hash);
 317   h->hash = _hash_set3 (h->hash, ikey, new_value, old_value);
 318
 319   /* If element already existed remove duplicate key. */
 320   if (hash_elts (h->hash) == old_n_elts)
 321     {
 322       hash_pair_t * p;
 323
 324       /* Fetch old key for return value. */
 325       p = hash_get_pair (h->hash, ikey);
 326       ikey = p->key;
 327
 328       /* Remove duplicate key. */
 329       if (mhash_key_vector_is_heap (h))
 330         {
 331           mhash_string_key_t * sk;
 332           sk = (void *) (h->key_vector_or_heap + i - sizeof (sk[0]));
 333           heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
 334         }
 335       else
 336         {
 337           if (key_alloc_from_free_list)
 338             {
 339               h->key_vector_free_indices[l] = i;
 340               _vec_len (h->key_vector_free_indices) = l + 1;
 341             }
 342           else
 343             _vec_len (h->key_vector_or_heap) -= h->n_key_bytes;
 344         }
 345     }
 346
 347   return ikey;
 348 }
 349
 350 uword mhash_unset (mhash_t * h, void * key, uword * old_value)
 351 {
 352   hash_pair_t * p;
 353   uword i;
 354
 355   mhash_sanitize_hash_user (h);
 356   i = mhash_set_tmp_key (h, key);
 357
 358   p = hash_get_pair (h->hash, i);
 359   if (! p)
 360     return 0;
 361
 362   ASSERT (p->key != ~0);
 363   i = p->key;
 364
 365   if (mhash_key_vector_is_heap (h))
 366     {
 367       mhash_string_key_t * sk;
 368       sk = (void *) (h->key_vector_or_heap + i) - sizeof (sk[0]);
 369       heap_dealloc (h->key_vector_or_heap, sk->heap_handle);
 370     }
 371   else
 372     vec_add1 (h->key_vector_free_indices, i);
 373
 374   hash_unset3 (h->hash, i, old_value);
 375   return 1;
 376 }
 377
 378 u8 * format_mhash_key (u8 * s, va_list * va)
 379 {
 380   mhash_t * h = va_arg (*va, mhash_t *);
 381   u32 ki = va_arg (*va, u32);
 382   void * k = mhash_key_to_mem (h, ki);
 383
 384   if (mhash_key_vector_is_heap (h))
 385     {
 386       uword is_c_string = h->n_key_bytes == MHASH_C_STRING_KEY;
 387       u32 l = is_c_string ? strlen (k) : vec_len (k);
 388       vec_add (s, k, l);
 389     }
 390   else if (h->format_key)
 391     s = format (s, "%U", h->format_key, k);
 392   else
 393     s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes);
 394
 395   return s;
 396 }