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