palacios/src/palacios/vmm_hashtable.c

   1 /* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
   2 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
   3
   4 #include <palacios/vmm.h>
   5 #include <palacios/vmm_hashtable.h>
   6 #include <palacios/vmm_string.h>
   7
   8
   9
  10
  11
  12 struct hash_entry {
  13   void * key;
  14   void * value;
  15   uint_t hash;
  16   struct hash_entry * next;
  17 };
  18
  19 struct hashtable {
  20     uint_t table_length;
  21     struct hash_entry ** table;
  22     uint_t entry_count;
  23     uint_t load_limit;
  24     uint_t prime_index;
  25     uint_t (*hash_fn) (void * key);
  26     int (*eq_fn) (void * key1, void * key2);
  27 };
  28
  29
  30
  31 /* HASH FUNCTIONS */
  32
  33
  34
  35 uint_t do_hash(struct hashtable * htable, void * key) {
  36   /* Aim to protect against poor hash functions by adding logic here
  37    * - logic taken from java 1.4 hashtable source */
  38   uint_t i = htable->hash_fn(key);
  39   i += ~(i << 9);
  40   i ^=  ((i >> 14) | (i << 18)); /* >>> */
  41   i +=  (i << 4);
  42   i ^=  ((i >> 10) | (i << 22)); /* >>> */
  43
  44   return i;
  45 }
  46
  47
  48 /* HASH AN UNSIGNED LONG */
  49 /* LINUX UNSIGHED LONG HASH FUNCTION */
  50 #ifdef __V3_32BIT__
  51 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  52 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  53 #define BITS_PER_LONG 32
  54 #elif  defined(__V3_64BIT__)
  55 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  56 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  57 #define BITS_PER_LONG 64
  58 #else
  59 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  60 #endif
  61
  62 ulong_t hash_long(ulong_t val, uint_t bits) {
  63   ulong_t hash = val;
  64
  65 #ifdef __V3_64BIT__
  66   /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
  67   ulong_t n = hash;
  68   n <<= 18;
  69   hash -= n;
  70   n <<= 33;
  71   hash -= n;
  72   n <<= 3;
  73   hash += n;
  74   n <<= 3;
  75   hash -= n;
  76   n <<= 4;
  77   hash += n;
  78   n <<= 2;
  79   hash += n;
  80 #else
  81   /* On some cpus multiply is faster, on others gcc will do shifts */
  82   hash *= GOLDEN_RATIO_PRIME;
  83 #endif
  84
  85   /* High bits are more random, so use them. */
  86   return hash >> (BITS_PER_LONG - bits);
  87 }
  88
  89 /* HASH GENERIC MEMORY BUFFER */
  90 /* ELF HEADER HASH FUNCTION */
  91 ulong_t hash_buffer(uchar_t * msg, uint_t length) {
  92   ulong_t hash = 0;
  93   ulong_t temp = 0;
  94   int i;
  95
  96   for (i = 0; i < length; i++) {
  97     hash = (hash << 4) + *(msg + i) + i;
  98     if ((temp = (hash & 0xF0000000))) {
  99       hash ^= (temp >> 24);
 100     }
 101     hash &= ~temp;
 102   }
 103   return hash;
 104 }
 105
 106
 107
 108 /*****************************************************************************/
 109 /* indexFor */
 110 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
 111   return (hash_value % table_length);
 112 };
 113
 114 /* Only works if table_length == 2^N */
 115 /*
 116   static inline uint_t indexFor(uint_t table_length, uint_t hashvalue)
 117   {
 118   return (hashvalue & (table_length - 1u));
 119   }
 120 */
 121
 122 /*****************************************************************************/
 123 #define freekey(X) V3_Free(X)
 124 /*define freekey(X) ; */
 125
 126
 127 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
 128   void * new_buf = V3_Malloc(new_size);
 129
 130   if (new_buf == NULL) {
 131     return NULL;
 132   }
 133
 134   memcpy(new_buf, old_ptr, old_size);
 135   V3_Free(old_ptr);
 136
 137   return new_buf;
 138 }
 139
 140
 141 /*
 142 Credit for primes table: Aaron Krowne
 143  http://br.endernet.org/~akrowne/
 144  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 145 */
 146 static const uint_t primes[] = {
 147   53, 97, 193, 389,
 148   769, 1543, 3079, 6151,
 149   12289, 24593, 49157, 98317,
 150   196613, 393241, 786433, 1572869,
 151   3145739, 6291469, 12582917, 25165843,
 152   50331653, 100663319, 201326611, 402653189,
 153   805306457, 1610612741 };
 154
 155
 156 const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
 157
 158 const float max_load_factor = 0.65;
 159
 160 /*****************************************************************************/
 161 struct hashtable * create_hashtable(uint_t min_size,
 162                                     uint_t (*hash_fn) (void *),
 163                                     int (*eq_fn) (void *, void *)) {
 164     struct hashtable * htable;
 165     uint_t prime_index;
 166     uint_t size = primes[0];
 167
 168     /* Check requested hashtable isn't too large */
 169     if (min_size > (1u << 30)) {
 170       return NULL;
 171     }
 172
 173     /* Enforce size as prime */
 174     for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
 175         if (primes[prime_index] > min_size) {
 176           size = primes[prime_index];
 177           break;
 178         }
 179     }
 180
 181     htable = (struct hashtable *)V3_Malloc(sizeof(struct hashtable));
 182
 183     if (htable == NULL) {
 184       return NULL; /*oom*/
 185     }
 186
 187     htable->table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * size);
 188
 189     if (htable->table == NULL) {
 190       V3_Free(htable);
 191       return NULL;  /*oom*/
 192     }
 193
 194
 195     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 196
 197     htable->table_length  = size;
 198     htable->prime_index   = prime_index;
 199     htable->entry_count   = 0;
 200     htable->hash_fn       = hash_fn;
 201     htable->eq_fn         = eq_fn;
 202     htable->load_limit    = (uint_t) ceil((double)(size * max_load_factor));
 203
 204     return htable;
 205 }
 206
 207
 208
 209 /*****************************************************************************/
 210 static int hashtable_expand(struct hashtable * htable) {
 211     /* Double the size of the table to accomodate more entries */
 212     struct hash_entry ** new_table;
 213     struct hash_entry * tmp_entry;
 214     struct hash_entry ** entry_ptr;
 215     uint_t new_size;
 216     uint_t i;
 217     uint_t index;
 218
 219     /* Check we're not hitting max capacity */
 220     if (htable->prime_index == (prime_table_length - 1)) {
 221       return 0;
 222     }
 223
 224     new_size = primes[++(htable->prime_index)];
 225
 226     new_table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * new_size);
 227
 228     if (new_table != NULL) {
 229         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 230         /* This algorithm is not 'stable'. ie. it reverses the list
 231          * when it transfers entries between the tables */
 232
 233         for (i = 0; i < htable->table_length; i++) {
 234
 235           while ((tmp_entry = htable->table[i]) != NULL) {
 236             htable->table[i] = tmp_entry->next;
 237
 238             index = indexFor(new_size, tmp_entry->hash);
 239
 240             tmp_entry->next = new_table[index];
 241
 242             new_table[index] = tmp_entry;
 243           }
 244         }
 245
 246         V3_Free(htable->table);
 247
 248         htable->table = new_table;
 249     } else {
 250       /* Plan B: realloc instead */
 251
 252       //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 253       new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 254                                                new_size * sizeof(struct hash_entry *));
 255
 256       if (new_table == NULL) {
 257         (htable->prime_index)--;
 258         return 0;
 259       }
 260
 261       htable->table = new_table;
 262
 263       memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 264
 265       for (i = 0; i < htable->table_length; i++) {
 266
 267         for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 268              tmp_entry != NULL;
 269              tmp_entry = *entry_ptr) {
 270
 271           index = indexFor(new_size, tmp_entry->hash);
 272
 273           if (i == index) {
 274             entry_ptr = &(tmp_entry->next);
 275           } else {
 276             *entry_ptr = tmp_entry->next;
 277             tmp_entry->next = new_table[index];
 278             new_table[index] = tmp_entry;
 279           }
 280         }
 281       }
 282     }
 283
 284     htable->table_length = new_size;
 285
 286     htable->load_limit   = (uint_t) ceil(new_size * max_load_factor);
 287
 288     return -1;
 289 }
 290
 291 /*****************************************************************************/
 292 uint_t hashtable_count(struct hashtable * htable) {
 293     return htable->entry_count;
 294 }
 295
 296 /*****************************************************************************/
 297 int hashtable_insert(struct hashtable * htable, void * key, void * value) {
 298     /* This method allows duplicate keys - but they shouldn't be used */
 299     uint_t index;
 300     struct hash_entry * new_entry;
 301
 302     if (++(htable->entry_count) > htable->load_limit) {
 303       /* Ignore the return value. If expand fails, we should
 304        * still try cramming just this value into the existing table
 305        * -- we may not have memory for a larger table, but one more
 306        * element may be ok. Next time we insert, we'll try expanding again.*/
 307       hashtable_expand(htable);
 308     }
 309
 310
 311     new_entry = (struct hash_entry *)V3_Malloc(sizeof(struct hash_entry));
 312
 313     if (new_entry == NULL) {
 314       (htable->entry_count)--;
 315       return 0; /*oom*/
 316     }
 317
 318     new_entry->hash = do_hash(htable, key);
 319
 320     index = indexFor(htable->table_length, new_entry->hash);
 321
 322     new_entry->key = key;
 323     new_entry->value = value;
 324
 325     new_entry->next = htable->table[index];
 326
 327     htable->table[index] = new_entry;
 328
 329     return -1;
 330 }
 331
 332
 333
 334 int hashtable_change(struct hashtable * htable, void * key, void * value) {
 335     struct hash_entry * tmp_entry;
 336     uint_t hash_value;
 337     uint_t index;
 338
 339     hash_value = do_hash(htable, key);
 340
 341     index = indexFor(htable->table_length, hash_value);
 342
 343     tmp_entry = htable->table[index];
 344
 345     while (tmp_entry != NULL) {
 346         /* Check hash value to short circuit heavier comparison */
 347         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 348             V3_Free(tmp_entry->value);
 349             tmp_entry->value = value;
 350
 351             return -1;
 352         }
 353         tmp_entry = tmp_entry->next;
 354     }
 355     return 0;
 356 }
 357
 358
 359
 360
 361 /*****************************************************************************/
 362 /* returns value associated with key */
 363 void * hashtable_search(struct hashtable * htable, void * key) {
 364   struct hash_entry * cursor;
 365   uint_t hash_value;
 366   uint_t index;
 367
 368   hash_value = do_hash(htable, key);
 369
 370   index = indexFor(htable->table_length, hash_value);
 371
 372   cursor = htable->table[index];
 373
 374   while (cursor != NULL) {
 375     /* Check hash value to short circuit heavier comparison */
 376     if ((hash_value == cursor->hash) &&
 377         (htable->eq_fn(key, cursor->key))) {
 378       return cursor->value;
 379     }
 380
 381     cursor = cursor->next;
 382   }
 383
 384   return NULL;
 385 }
 386
 387 /*****************************************************************************/
 388 /* returns value associated with key */
 389 void * hashtable_remove(struct hashtable * htable, void * key) {
 390   /* TODO: consider compacting the table when the load factor drops enough,
 391    *       or provide a 'compact' method. */
 392
 393   struct hash_entry * cursor;
 394   struct hash_entry ** entry_ptr;
 395   void * value;
 396   uint_t hash_value;
 397   uint_t index;
 398
 399   hash_value = do_hash(htable, key);
 400
 401   index = indexFor(htable->table_length, hash_value);
 402
 403   entry_ptr = &(htable->table[index]);
 404   cursor = *entry_ptr;
 405
 406   while (cursor != NULL) {
 407     /* Check hash value to short circuit heavier comparison */
 408     if ((hash_value == cursor->hash) &&
 409         (htable->eq_fn(key, cursor->key))) {
 410
 411       *entry_ptr = cursor->next;
 412       htable->entry_count--;
 413       value = cursor->value;
 414
 415       freekey(cursor->key);
 416       V3_Free(cursor);
 417
 418       return value;
 419     }
 420
 421     entry_ptr = &(cursor->next);
 422     cursor = cursor->next;
 423   }
 424   return NULL;
 425 }
 426
 427 /*****************************************************************************/
 428 /* destroy */
 429 void hashtable_destroy(struct hashtable * htable, int free_values) {
 430   uint_t i;
 431   struct hash_entry * cursor;;
 432   struct hash_entry **table = htable->table;
 433
 434   if (free_values) {
 435     for (i = 0; i < htable->table_length; i++) {
 436       cursor = table[i];
 437
 438       while (cursor != NULL) {
 439         struct hash_entry * tmp;
 440
 441         tmp = cursor;
 442         cursor = cursor->next;
 443
 444         freekey(tmp->key);
 445         V3_Free(tmp->value);
 446         V3_Free(tmp);
 447       }
 448     }
 449   } else {
 450     for (i = 0; i < htable->table_length; i++) {
 451       cursor = table[i];
 452
 453       while (cursor != NULL) {
 454         struct hash_entry * tmp;
 455
 456         tmp = cursor;
 457         cursor = cursor->next;
 458
 459         freekey(tmp->key);
 460         V3_Free(tmp);
 461       }
 462     }
 463   }
 464
 465   V3_Free(htable->table);
 466   V3_Free(htable);
 467 }
 468
 469
 470
 471
 472 /* HASH TABLE ITERATORS */
 473
 474
 475
 476 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable) {
 477   uint_t i;
 478   uint_t table_length;
 479
 480   struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
 481
 482   if (iter == NULL) {
 483     return NULL;
 484   }
 485
 486   iter->htable = htable;
 487   iter->entry = NULL;
 488   iter->parent = NULL;
 489   table_length = htable->table_length;
 490   iter->index = table_length;
 491
 492   if (htable->entry_count == 0) {
 493     return iter;
 494   }
 495
 496   for (i = 0; i < table_length; i++) {
 497     if (htable->table[i] != NULL) {
 498       iter->entry = htable->table[i];
 499       iter->index = i;
 500       break;
 501     }
 502   }
 503
 504   return iter;
 505 }
 506
 507
 508 void * hashtable_get_iter_key(struct hashtable_iter * iter) {
 509   return iter->entry->key;
 510 }
 511
 512 void * hashtable_get_iter_value(struct hashtable_iter * iter) {
 513   return iter->entry->value;
 514 }
 515
 516
 517 /* advance - advance the iterator to the next element
 518  *           returns zero if advanced to end of table */
 519 int hashtable_iterator_advance(struct hashtable_iter * iter) {
 520   uint_t j;
 521   uint_t table_length;
 522   struct hash_entry ** table;
 523   struct hash_entry * next;
 524
 525   if (iter->entry == NULL) {
 526     return 0; /* stupidity check */
 527   }
 528
 529
 530   next = iter->entry->next;
 531
 532   if (next != NULL) {
 533     iter->parent = iter->entry;
 534     iter->entry = next;
 535     return -1;
 536   }
 537
 538   table_length = iter->htable->table_length;
 539   iter->parent = NULL;
 540
 541   if (table_length <= (j = ++(iter->index))) {
 542     iter->entry = NULL;
 543     return 0;
 544   }
 545
 546   table = iter->htable->table;
 547
 548   while ((next = table[j]) == NULL) {
 549     if (++j >= table_length) {
 550       iter->index = table_length;
 551       iter->entry = NULL;
 552       return 0;
 553     }
 554   }
 555
 556   iter->index = j;
 557   iter->entry = next;
 558
 559   return -1;
 560 }
 561
 562
 563 /* remove - remove the entry at the current iterator position
 564  *          and advance the iterator, if there is a successive
 565  *          element.
 566  *          If you want the value, read it before you remove:
 567  *          beware memory leaks if you don't.
 568  *          Returns zero if end of iteration. */
 569 int hashtable_iterator_remove(struct hashtable_iter * iter) {
 570   struct hash_entry * remember_entry;
 571   struct hash_entry * remember_parent;
 572   int ret;
 573
 574   /* Do the removal */
 575   if ((iter->parent) == NULL) {
 576     /* element is head of a chain */
 577     iter->htable->table[iter->index] = iter->entry->next;
 578   } else {
 579     /* element is mid-chain */
 580     iter->parent->next = iter->entry->next;
 581   }
 582
 583
 584   /* itr->e is now outside the hashtable */
 585   remember_entry = iter->entry;
 586   iter->htable->entry_count--;
 587   freekey(remember_entry->key);
 588
 589   /* Advance the iterator, correcting the parent */
 590   remember_parent = iter->parent;
 591   ret = hashtable_iterator_advance(iter);
 592
 593   if (iter->parent == remember_entry) {
 594     iter->parent = remember_parent;
 595   }
 596
 597   V3_Free(remember_entry);
 598   return ret;
 599 }
 600
 601
 602 /* returns zero if not found */
 603 int hashtable_iterator_search(struct hashtable_iter * iter,
 604                               struct hashtable * htable, void * key) {
 605   struct hash_entry * entry;
 606   struct hash_entry * parent;
 607   uint_t hash_value;
 608   uint_t index;
 609
 610   hash_value = do_hash(htable, key);
 611   index = indexFor(htable->table_length, hash_value);
 612
 613   entry = htable->table[index];
 614   parent = NULL;
 615
 616   while (entry != NULL) {
 617     /* Check hash value to short circuit heavier comparison */
 618     if ((hash_value == entry->hash) &&
 619         (htable->eq_fn(key, entry->key))) {
 620       iter->index = index;
 621       iter->entry = entry;
 622       iter->parent = parent;
 623       iter->htable = htable;
 624       return -1;
 625     }
 626     parent = entry;
 627     entry = entry->next;
 628   }
 629   return 0;
 630 }
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646 /*
 647  * Copyright (c) 2002, Christopher Clark
 648  * All rights reserved.
 649  *
 650  * Redistribution and use in source and binary forms, with or without
 651  * modification, are permitted provided that the following conditions
 652  * are met:
 653  *
 654  * * Redistributions of source code must retain the above copyright
 655  * notice, this list of conditions and the following disclaimer.
 656  *
 657  * * Redistributions in binary form must reproduce the above copyright
 658  * notice, this list of conditions and the following disclaimer in the
 659  * documentation and/or other materials provided with the distribution.
 660  *
 661  * * Neither the name of the original author; nor the names of any contributors
 662  * may be used to endorse or promote products derived from this software
 663  * without specific prior written permission.
 664  *
 665  *
 666  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 667  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 668  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 669  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 670  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 671  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 672  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 673  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 674  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 675  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 676  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 677 */