palacios/src/vnet/vnet_hashtable.c

   1 /*
   2   Copyright (c) 2002, 2004, Christopher Clark
   3   All rights reserved.
   4
   5   Redistribution and use in source and binary forms, with or without
   6   modification, are permitted provided that the following conditions
   7   are met:
   8
   9   * Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11
  12   * Redistributions in binary form must reproduce the above copyright
  13     notice, this list of conditions and the following disclaimer in the
  14     documentation and/or other materials provided with the distribution.
  15
  16   * Neither the name of the original author; nor the names of any contributors
  17     may be used to endorse or promote products derived from this software
  18     without specific prior written permission.
  19
  20
  21   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  25   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  26   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  27   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  28   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  29   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  30   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  31   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32 */
  33 /* Modifications made by Lei Xia <lxia@northwestern.edu> */
  34
  35 #include <vnet/vnet_host.h>
  36 #include <vnet/vnet_vmm.h>
  37 #include <vnet/vnet_hashtable.h>
  38
  39 struct hash_entry {
  40     addr_t key;
  41     addr_t value;
  42     uint_t hash;
  43     struct hash_entry * next;
  44 };
  45
  46 struct hashtable {
  47     uint_t table_length;
  48     struct hash_entry ** table;
  49     uint_t entry_count;
  50     uint_t load_limit;
  51     uint_t prime_index;
  52     uint_t (*hash_fn) (addr_t key);
  53     int (*eq_fn) (addr_t key1, addr_t key2);
  54 };
  55
  56
  57
  58 /* HASH FUNCTIONS */
  59 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
  60     /* Aim to protect against poor hash functions by adding logic here
  61      * - logic taken from java 1.4 hashtable source */
  62     uint_t i = htable->hash_fn(key);
  63     i += ~(i << 9);
  64     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  65     i +=  (i << 4);
  66     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  67
  68     return i;
  69 }
  70
  71
  72 /* HASH AN UNSIGNED LONG */
  73 /* LINUX UNSIGHED LONG HASH FUNCTION */
  74 #ifdef __V3_32BIT__
  75 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  76 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  77 #define BITS_PER_LONG 32
  78 #elif  defined(__V3_64BIT__)
  79 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  80 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  81 #define BITS_PER_LONG 64
  82 #else
  83 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  84 #endif
  85
  86 ulong_t vnet_hash_long(ulong_t val, uint_t bits) {
  87     ulong_t hash = val;
  88
  89 #ifdef __V3_64BIT__
  90     /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
  91     ulong_t n = hash;
  92     n <<= 18;
  93     hash -= n;
  94     n <<= 33;
  95     hash -= n;
  96     n <<= 3;
  97     hash += n;
  98     n <<= 3;
  99     hash -= n;
 100     n <<= 4;
 101     hash += n;
 102     n <<= 2;
 103     hash += n;
 104 #else
 105     /* On some cpus multiply is faster, on others gcc will do shifts */
 106     hash *= GOLDEN_RATIO_PRIME;
 107 #endif
 108
 109     /* High bits are more random, so use them. */
 110     return hash >> (BITS_PER_LONG - bits);
 111 }
 112
 113 /* HASH GENERIC MEMORY BUFFER */
 114 /* ELF HEADER HASH FUNCTION */
 115 ulong_t vnet_hash_buffer(uchar_t * msg, uint_t length) {
 116     ulong_t hash = 0;
 117     ulong_t temp = 0;
 118     uint_t i;
 119
 120     for (i = 0; i < length; i++) {
 121         hash = (hash << 4) + *(msg + i) + i;
 122         if ((temp = (hash & 0xF0000000))) {
 123             hash ^= (temp >> 24);
 124         }
 125         hash &= ~temp;
 126     }
 127     return hash;
 128 }
 129
 130 /* indexFor */
 131 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
 132     return (hash_value % table_length);
 133 };
 134
 135 #define freekey(X) Vnet_Free(X)
 136
 137
 138 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
 139     void * new_buf = Vnet_Malloc(new_size);
 140
 141     if (new_buf == NULL) {
 142         return NULL;
 143     }
 144
 145     memcpy(new_buf, old_ptr, old_size);
 146     Vnet_Free(old_ptr);
 147
 148     return new_buf;
 149 }
 150
 151
 152 /*
 153   Credit for primes table: Aaron Krowne
 154   http://br.endernet.org/~akrowne/
 155   http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 156 */
 157 static const uint_t primes[] = {
 158     53, 97, 193, 389,
 159     769, 1543, 3079, 6151,
 160     12289, 24593, 49157, 98317,
 161     196613, 393241, 786433, 1572869,
 162     3145739, 6291469, 12582917, 25165843,
 163     50331653, 100663319, 201326611, 402653189,
 164     805306457, 1610612741 };
 165
 166
 167 // this assumes that the max load factor is .65
 168 static const uint_t load_factors[] = {
 169     35, 64, 126, 253,
 170     500, 1003, 2002, 3999,
 171     7988, 15986, 31953, 63907,
 172     127799, 255607, 511182, 1022365,
 173     2044731, 4089455, 8178897, 16357798,
 174     32715575, 65431158, 130862298, 261724573,
 175     523449198, 1046898282 };
 176
 177 static const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
 178
 179 struct hashtable * vnet_create_htable(uint_t min_size,
 180                                       uint_t (*hash_fn) (addr_t),
 181                                       int (*eq_fn) (addr_t, addr_t)) {
 182     struct hashtable * htable;
 183     uint_t prime_index;
 184     uint_t size = primes[0];
 185
 186     /* Check requested hashtable isn't too large */
 187     if (min_size > (1u << 30)) {
 188         return NULL;
 189     }
 190
 191     /* Enforce size as prime */
 192     for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
 193         if (primes[prime_index] > min_size) {
 194             size = primes[prime_index];
 195             break;
 196         }
 197     }
 198
 199     htable = (struct hashtable *)Vnet_Malloc(sizeof(struct hashtable));
 200
 201     if (htable == NULL) {
 202         return NULL; /*oom*/
 203     }
 204
 205     htable->table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * size);
 206
 207     if (htable->table == NULL) {
 208         V3_Free(htable);
 209         return NULL;  /*oom*/
 210     }
 211
 212     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 213
 214     htable->table_length  = size;
 215     htable->prime_index   = prime_index;
 216     htable->entry_count   = 0;
 217     htable->hash_fn       = hash_fn;
 218     htable->eq_fn         = eq_fn;
 219     htable->load_limit    = load_factors[prime_index];
 220
 221     return htable;
 222 }
 223
 224
 225
 226 static int hashtable_expand(struct hashtable * htable) {
 227     /* Double the size of the table to accomodate more entries */
 228     struct hash_entry ** new_table;
 229     struct hash_entry * tmp_entry;
 230     struct hash_entry ** entry_ptr;
 231     uint_t new_size;
 232     uint_t i;
 233     uint_t index;
 234
 235     /* Check we're not hitting max capacity */
 236     if (htable->prime_index == (prime_table_length - 1)) {
 237         return 0;
 238     }
 239
 240     new_size = primes[++(htable->prime_index)];
 241
 242     new_table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * new_size);
 243
 244     if (new_table != NULL) {
 245         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 246         /* This algorithm is not 'stable'. ie. it reverses the list
 247          * when it transfers entries between the tables */
 248
 249         for (i = 0; i < htable->table_length; i++) {
 250
 251             while ((tmp_entry = htable->table[i]) != NULL) {
 252                 htable->table[i] = tmp_entry->next;
 253
 254                 index = indexFor(new_size, tmp_entry->hash);
 255
 256                 tmp_entry->next = new_table[index];
 257
 258                 new_table[index] = tmp_entry;
 259             }
 260         }
 261
 262         Vnet_Free(htable->table);
 263
 264         htable->table = new_table;
 265     } else {
 266         /* Plan B: realloc instead */
 267
 268         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 269         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 270                                                       new_size * sizeof(struct hash_entry *));
 271
 272         if (new_table == NULL) {
 273             (htable->prime_index)--;
 274             return 0;
 275         }
 276
 277         htable->table = new_table;
 278
 279         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 280
 281         for (i = 0; i < htable->table_length; i++) {
 282
 283             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 284                  tmp_entry != NULL;
 285                  tmp_entry = *entry_ptr) {
 286
 287                 index = indexFor(new_size, tmp_entry->hash);
 288
 289                 if (i == index) {
 290                     entry_ptr = &(tmp_entry->next);
 291                 } else {
 292                     *entry_ptr = tmp_entry->next;
 293                     tmp_entry->next = new_table[index];
 294                     new_table[index] = tmp_entry;
 295                 }
 296             }
 297         }
 298     }
 299
 300     htable->table_length = new_size;
 301
 302     htable->load_limit   = load_factors[htable->prime_index];
 303
 304     return -1;
 305 }
 306
 307 uint_t vnet_htable_count(struct hashtable * htable) {
 308     return htable->entry_count;
 309 }
 310
 311 int vnet_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 312     /* This method allows duplicate keys - but they shouldn't be used */
 313     uint_t index;
 314     struct hash_entry * new_entry;
 315
 316     if (++(htable->entry_count) > htable->load_limit) {
 317         /* Ignore the return value. If expand fails, we should
 318          * still try cramming just this value into the existing table
 319          * -- we may not have memory for a larger table, but one more
 320          * element may be ok. Next time we insert, we'll try expanding again.*/
 321         hashtable_expand(htable);
 322     }
 323
 324
 325     new_entry = (struct hash_entry *)Vnet_Malloc(sizeof(struct hash_entry));
 326
 327     if (new_entry == NULL) {
 328         (htable->entry_count)--;
 329         return 0; /*oom*/
 330     }
 331
 332     new_entry->hash = do_hash(htable, key);
 333
 334     index = indexFor(htable->table_length, new_entry->hash);
 335
 336     new_entry->key = key;
 337     new_entry->value = value;
 338
 339     new_entry->next = htable->table[index];
 340
 341     htable->table[index] = new_entry;
 342
 343     return -1;
 344 }
 345
 346
 347 /* returns value associated with key */
 348 addr_t vnet_htable_search(struct hashtable * htable, addr_t key) {
 349     struct hash_entry * cursor;
 350     uint_t hash_value;
 351     uint_t index;
 352
 353     hash_value = do_hash(htable, key);
 354
 355     index = indexFor(htable->table_length, hash_value);
 356
 357     cursor = htable->table[index];
 358
 359     while (cursor != NULL) {
 360         /* Check hash value to short circuit heavier comparison */
 361         if ((hash_value == cursor->hash) &&
 362             (htable->eq_fn(key, cursor->key))) {
 363             return cursor->value;
 364         }
 365
 366         cursor = cursor->next;
 367     }
 368
 369     return (addr_t)NULL;
 370 }
 371
 372 /* returns value associated with key */
 373 addr_t vnet_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 374     /* TODO: consider compacting the table when the load factor drops enough,
 375      *       or provide a 'compact' method. */
 376
 377     struct hash_entry * cursor;
 378     struct hash_entry ** entry_ptr;
 379     addr_t value;
 380     uint_t hash_value;
 381     uint_t index;
 382
 383     hash_value = do_hash(htable, key);
 384
 385     index = indexFor(htable->table_length, hash_value);
 386
 387     entry_ptr = &(htable->table[index]);
 388     cursor = *entry_ptr;
 389
 390     while (cursor != NULL) {
 391         /* Check hash value to short circuit heavier comparison */
 392         if ((hash_value == cursor->hash) &&
 393             (htable->eq_fn(key, cursor->key))) {
 394
 395             *entry_ptr = cursor->next;
 396             htable->entry_count--;
 397             value = cursor->value;
 398
 399             if (free_key) {
 400                 freekey((void *)(cursor->key));
 401             }
 402             Vnet_Free(cursor);
 403
 404             return value;
 405         }
 406
 407         entry_ptr = &(cursor->next);
 408         cursor = cursor->next;
 409     }
 410     return (addr_t)NULL;
 411 }
 412
 413 /* destroy */
 414 void vnet_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 415     uint_t i;
 416     struct hash_entry * cursor;;
 417     struct hash_entry **table = htable->table;
 418
 419     if (free_values) {
 420         for (i = 0; i < htable->table_length; i++) {
 421             cursor = table[i];
 422
 423             while (cursor != NULL) {
 424                 struct hash_entry * tmp;
 425
 426                 tmp = cursor;
 427                 cursor = cursor->next;
 428
 429                 if (free_keys) {
 430                     freekey((void *)(tmp->key));
 431                 }
 432                 Vnet_Free((void *)(tmp->value));
 433                 Vnet_Free(tmp);
 434             }
 435         }
 436     } else {
 437         for (i = 0; i < htable->table_length; i++) {
 438             cursor = table[i];
 439
 440             while (cursor != NULL) {
 441                 struct hash_entry * tmp;
 442
 443                 tmp = cursor;
 444                 cursor = cursor->next;
 445
 446                 if (free_keys) {
 447                     freekey((void *)(tmp->key));
 448                 }
 449                 Vnet_Free(tmp);
 450             }
 451         }
 452     }
 453
 454     Vnet_Free(htable->table);
 455     Vnet_Free(htable);
 456 }
 457
 458
 459 /*
 460  * Copyright (c) 2002, Christopher Clark
 461  * All rights reserved.
 462  *
 463  * Redistribution and use in source and binary forms, with or without
 464  * modification, are permitted provided that the following conditions
 465  * are met:
 466  *
 467  * * Redistributions of source code must retain the above copyright
 468  * notice, this list of conditions and the following disclaimer.
 469  *
 470  * * Redistributions in binary form must reproduce the above copyright
 471  * notice, this list of conditions and the following disclaimer in the
 472  * documentation and/or other materials provided with the distribution.
 473  *
 474  * * Neither the name of the original author; nor the names of any contributors
 475  * may be used to endorse or promote products derived from this software
 476  * without specific prior written permission.
 477  *
 478  *
 479  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 480  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 481  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 482  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 483  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 484  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 485  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 486  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 487  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 488  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 489  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 490  */