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