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     if (prime_index==prime_table_length) {
 200         return NULL;
 201     }
 202
 203     htable = (struct hashtable *)Vnet_Malloc(sizeof(struct hashtable));
 204
 205     if (htable == NULL) {
 206         return NULL; /*oom*/
 207     }
 208
 209     htable->table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * size);
 210
 211     if (htable->table == NULL) {
 212         V3_Free(htable);
 213         return NULL;  /*oom*/
 214     }
 215
 216     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 217
 218     htable->table_length  = size;
 219     htable->prime_index   = prime_index;
 220     htable->entry_count   = 0;
 221     htable->hash_fn       = hash_fn;
 222     htable->eq_fn         = eq_fn;
 223     htable->load_limit    = load_factors[prime_index];
 224
 225     return htable;
 226 }
 227
 228
 229
 230 static int hashtable_expand(struct hashtable * htable) {
 231     /* Double the size of the table to accomodate more entries */
 232     struct hash_entry ** new_table;
 233     struct hash_entry * tmp_entry;
 234     struct hash_entry ** entry_ptr;
 235     uint_t new_size;
 236     uint_t i;
 237     uint_t index;
 238
 239     /* Check we're not hitting max capacity */
 240     if (htable->prime_index == (prime_table_length - 1)) {
 241         return 0;
 242     }
 243
 244     new_size = primes[++(htable->prime_index)];
 245
 246     new_table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * new_size);
 247
 248     if (new_table != NULL) {
 249         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 250         /* This algorithm is not 'stable'. ie. it reverses the list
 251          * when it transfers entries between the tables */
 252
 253         for (i = 0; i < htable->table_length; i++) {
 254
 255             while ((tmp_entry = htable->table[i]) != NULL) {
 256                 htable->table[i] = tmp_entry->next;
 257
 258                 index = indexFor(new_size, tmp_entry->hash);
 259
 260                 tmp_entry->next = new_table[index];
 261
 262                 new_table[index] = tmp_entry;
 263             }
 264         }
 265
 266         Vnet_Free(htable->table);
 267
 268         htable->table = new_table;
 269     } else {
 270         /* Plan B: realloc instead */
 271
 272         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 273         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 274                                                       new_size * sizeof(struct hash_entry *));
 275
 276         if (new_table == NULL) {
 277             (htable->prime_index)--;
 278             return 0;
 279         }
 280
 281         htable->table = new_table;
 282
 283         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 284
 285         for (i = 0; i < htable->table_length; i++) {
 286
 287             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 288                  tmp_entry != NULL;
 289                  tmp_entry = *entry_ptr) {
 290
 291                 index = indexFor(new_size, tmp_entry->hash);
 292
 293                 if (i == index) {
 294                     entry_ptr = &(tmp_entry->next);
 295                 } else {
 296                     *entry_ptr = tmp_entry->next;
 297                     tmp_entry->next = new_table[index];
 298                     new_table[index] = tmp_entry;
 299                 }
 300             }
 301         }
 302     }
 303
 304     htable->table_length = new_size;
 305
 306     htable->load_limit   = load_factors[htable->prime_index];
 307
 308     return -1;
 309 }
 310
 311 uint_t vnet_htable_count(struct hashtable * htable) {
 312     return htable->entry_count;
 313 }
 314
 315 int vnet_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 316     /* This method allows duplicate keys - but they shouldn't be used */
 317     uint_t index;
 318     struct hash_entry * new_entry;
 319
 320     if (++(htable->entry_count) > htable->load_limit) {
 321         /* Ignore the return value. If expand fails, we should
 322          * still try cramming just this value into the existing table
 323          * -- we may not have memory for a larger table, but one more
 324          * element may be ok. Next time we insert, we'll try expanding again.*/
 325         hashtable_expand(htable);
 326     }
 327
 328
 329     new_entry = (struct hash_entry *)Vnet_Malloc(sizeof(struct hash_entry));
 330
 331     if (new_entry == NULL) {
 332         (htable->entry_count)--;
 333         return 0; /*oom*/
 334     }
 335
 336     new_entry->hash = do_hash(htable, key);
 337
 338     index = indexFor(htable->table_length, new_entry->hash);
 339
 340     new_entry->key = key;
 341     new_entry->value = value;
 342
 343     new_entry->next = htable->table[index];
 344
 345     htable->table[index] = new_entry;
 346
 347     return -1;
 348 }
 349
 350
 351 /* returns value associated with key */
 352 addr_t vnet_htable_search(struct hashtable * htable, addr_t key) {
 353     struct hash_entry * cursor;
 354     uint_t hash_value;
 355     uint_t index;
 356
 357     hash_value = do_hash(htable, key);
 358
 359     index = indexFor(htable->table_length, hash_value);
 360
 361     cursor = htable->table[index];
 362
 363     while (cursor != NULL) {
 364         /* Check hash value to short circuit heavier comparison */
 365         if ((hash_value == cursor->hash) &&
 366             (htable->eq_fn(key, cursor->key))) {
 367             return cursor->value;
 368         }
 369
 370         cursor = cursor->next;
 371     }
 372
 373     return (addr_t)NULL;
 374 }
 375
 376 /* returns value associated with key */
 377 addr_t vnet_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 378     /* TODO: consider compacting the table when the load factor drops enough,
 379      *       or provide a 'compact' method. */
 380
 381     struct hash_entry * cursor;
 382     struct hash_entry ** entry_ptr;
 383     addr_t value;
 384     uint_t hash_value;
 385     uint_t index;
 386
 387     hash_value = do_hash(htable, key);
 388
 389     index = indexFor(htable->table_length, hash_value);
 390
 391     entry_ptr = &(htable->table[index]);
 392     cursor = *entry_ptr;
 393
 394     while (cursor != NULL) {
 395         /* Check hash value to short circuit heavier comparison */
 396         if ((hash_value == cursor->hash) &&
 397             (htable->eq_fn(key, cursor->key))) {
 398
 399             *entry_ptr = cursor->next;
 400             htable->entry_count--;
 401             value = cursor->value;
 402
 403             if (free_key) {
 404                 freekey((void *)(cursor->key));
 405             }
 406             Vnet_Free(cursor);
 407
 408             return value;
 409         }
 410
 411         entry_ptr = &(cursor->next);
 412         cursor = cursor->next;
 413     }
 414     return (addr_t)NULL;
 415 }
 416
 417 /* destroy */
 418 void vnet_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 419     uint_t i;
 420     struct hash_entry * cursor;;
 421     struct hash_entry **table = htable->table;
 422
 423     if (free_values) {
 424         for (i = 0; i < htable->table_length; i++) {
 425             cursor = table[i];
 426
 427             while (cursor != NULL) {
 428                 struct hash_entry * tmp;
 429
 430                 tmp = cursor;
 431                 cursor = cursor->next;
 432
 433                 if (free_keys) {
 434                     freekey((void *)(tmp->key));
 435                 }
 436                 Vnet_Free((void *)(tmp->value));
 437                 Vnet_Free(tmp);
 438             }
 439         }
 440     } else {
 441         for (i = 0; i < htable->table_length; i++) {
 442             cursor = table[i];
 443
 444             while (cursor != NULL) {
 445                 struct hash_entry * tmp;
 446
 447                 tmp = cursor;
 448                 cursor = cursor->next;
 449
 450                 if (free_keys) {
 451                     freekey((void *)(tmp->key));
 452                 }
 453                 Vnet_Free(tmp);
 454             }
 455         }
 456     }
 457
 458     Vnet_Free(htable->table);
 459     Vnet_Free(htable);
 460 }
 461
 462
 463 /*
 464  * Copyright (c) 2002, Christopher Clark
 465  * All rights reserved.
 466  *
 467  * Redistribution and use in source and binary forms, with or without
 468  * modification, are permitted provided that the following conditions
 469  * are met:
 470  *
 471  * * Redistributions of source code must retain the above copyright
 472  * notice, this list of conditions and the following disclaimer.
 473  *
 474  * * Redistributions in binary form must reproduce the above copyright
 475  * notice, this list of conditions and the following disclaimer in the
 476  * documentation and/or other materials provided with the distribution.
 477  *
 478  * * Neither the name of the original author; nor the names of any contributors
 479  * may be used to endorse or promote products derived from this software
 480  * without specific prior written permission.
 481  *
 482  *
 483  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 484  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 485  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 486  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 487  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 488  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 489  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 490  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 491  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 492  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 493  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 494  */