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   addr_t key;
  14   addr_t 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) (addr_t key);
  26     int (*eq_fn) (addr_t key1, addr_t key2);
  27 };
  28
  29
  30
  31 /* HASH FUNCTIONS */
  32
  33
  34
  35 uint_t do_hash(struct hashtable * htable, addr_t 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) (addr_t),
 163                                     int (*eq_fn) (addr_t, addr_t)) {
 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, addr_t key, addr_t 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, addr_t key, addr_t value, int free_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
 349           if (free_value) {
 350             V3_Free((void *)(tmp_entry->value));
 351           }
 352
 353           tmp_entry->value = value;
 354           return -1;
 355         }
 356         tmp_entry = tmp_entry->next;
 357     }
 358     return 0;
 359 }
 360
 361
 362
 363
 364 /*****************************************************************************/
 365 /* returns value associated with key */
 366 addr_t hashtable_search(struct hashtable * htable, addr_t key) {
 367   struct hash_entry * cursor;
 368   uint_t hash_value;
 369   uint_t index;
 370
 371   hash_value = do_hash(htable, key);
 372
 373   index = indexFor(htable->table_length, hash_value);
 374
 375   cursor = htable->table[index];
 376
 377   while (cursor != NULL) {
 378     /* Check hash value to short circuit heavier comparison */
 379     if ((hash_value == cursor->hash) &&
 380         (htable->eq_fn(key, cursor->key))) {
 381       return cursor->value;
 382     }
 383
 384     cursor = cursor->next;
 385   }
 386
 387   return (addr_t)NULL;
 388 }
 389
 390 /*****************************************************************************/
 391 /* returns value associated with key */
 392 addr_t hashtable_remove(struct hashtable * htable, addr_t key, int free_key) {
 393   /* TODO: consider compacting the table when the load factor drops enough,
 394    *       or provide a 'compact' method. */
 395
 396   struct hash_entry * cursor;
 397   struct hash_entry ** entry_ptr;
 398   addr_t value;
 399   uint_t hash_value;
 400   uint_t index;
 401
 402   hash_value = do_hash(htable, key);
 403
 404   index = indexFor(htable->table_length, hash_value);
 405
 406   entry_ptr = &(htable->table[index]);
 407   cursor = *entry_ptr;
 408
 409   while (cursor != NULL) {
 410     /* Check hash value to short circuit heavier comparison */
 411     if ((hash_value == cursor->hash) &&
 412         (htable->eq_fn(key, cursor->key))) {
 413
 414       *entry_ptr = cursor->next;
 415       htable->entry_count--;
 416       value = cursor->value;
 417
 418       if (free_key) {
 419         freekey((void *)(cursor->key));
 420       }
 421       V3_Free(cursor);
 422
 423       return value;
 424     }
 425
 426     entry_ptr = &(cursor->next);
 427     cursor = cursor->next;
 428   }
 429   return (addr_t)NULL;
 430 }
 431
 432 /*****************************************************************************/
 433 /* destroy */
 434 void hashtable_destroy(struct hashtable * htable, int free_values, int free_keys) {
 435   uint_t i;
 436   struct hash_entry * cursor;;
 437   struct hash_entry **table = htable->table;
 438
 439   if (free_values) {
 440     for (i = 0; i < htable->table_length; i++) {
 441       cursor = table[i];
 442
 443       while (cursor != NULL) {
 444         struct hash_entry * tmp;
 445
 446         tmp = cursor;
 447         cursor = cursor->next;
 448
 449         if (free_keys) {
 450           freekey((void *)(tmp->key));
 451         }
 452         V3_Free((void *)(tmp->value));
 453         V3_Free(tmp);
 454       }
 455     }
 456   } else {
 457     for (i = 0; i < htable->table_length; i++) {
 458       cursor = table[i];
 459
 460       while (cursor != NULL) {
 461         struct hash_entry * tmp;
 462
 463         tmp = cursor;
 464         cursor = cursor->next;
 465
 466         if (free_keys) {
 467           freekey((void *)(tmp->key));
 468         }
 469         V3_Free(tmp);
 470       }
 471     }
 472   }
 473
 474   V3_Free(htable->table);
 475   V3_Free(htable);
 476 }
 477
 478
 479
 480
 481 /* HASH TABLE ITERATORS */
 482
 483
 484
 485 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable) {
 486   uint_t i;
 487   uint_t table_length;
 488
 489   struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
 490
 491   if (iter == NULL) {
 492     return NULL;
 493   }
 494
 495   iter->htable = htable;
 496   iter->entry = NULL;
 497   iter->parent = NULL;
 498   table_length = htable->table_length;
 499   iter->index = table_length;
 500
 501   if (htable->entry_count == 0) {
 502     return iter;
 503   }
 504
 505   for (i = 0; i < table_length; i++) {
 506     if (htable->table[i] != NULL) {
 507       iter->entry = htable->table[i];
 508       iter->index = i;
 509       break;
 510     }
 511   }
 512
 513   return iter;
 514 }
 515
 516
 517 addr_t hashtable_get_iter_key(struct hashtable_iter * iter) {
 518   return iter->entry->key;
 519 }
 520
 521 addr_t hashtable_get_iter_value(struct hashtable_iter * iter) {
 522   return iter->entry->value;
 523 }
 524
 525
 526 /* advance - advance the iterator to the next element
 527  *           returns zero if advanced to end of table */
 528 int hashtable_iterator_advance(struct hashtable_iter * iter) {
 529   uint_t j;
 530   uint_t table_length;
 531   struct hash_entry ** table;
 532   struct hash_entry * next;
 533
 534   if (iter->entry == NULL) {
 535     return 0; /* stupidity check */
 536   }
 537
 538
 539   next = iter->entry->next;
 540
 541   if (next != NULL) {
 542     iter->parent = iter->entry;
 543     iter->entry = next;
 544     return -1;
 545   }
 546
 547   table_length = iter->htable->table_length;
 548   iter->parent = NULL;
 549
 550   if (table_length <= (j = ++(iter->index))) {
 551     iter->entry = NULL;
 552     return 0;
 553   }
 554
 555   table = iter->htable->table;
 556
 557   while ((next = table[j]) == NULL) {
 558     if (++j >= table_length) {
 559       iter->index = table_length;
 560       iter->entry = NULL;
 561       return 0;
 562     }
 563   }
 564
 565   iter->index = j;
 566   iter->entry = next;
 567
 568   return -1;
 569 }
 570
 571
 572 /* remove - remove the entry at the current iterator position
 573  *          and advance the iterator, if there is a successive
 574  *          element.
 575  *          If you want the value, read it before you remove:
 576  *          beware memory leaks if you don't.
 577  *          Returns zero if end of iteration. */
 578 int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key) {
 579   struct hash_entry * remember_entry;
 580   struct hash_entry * remember_parent;
 581   int ret;
 582
 583   /* Do the removal */
 584   if ((iter->parent) == NULL) {
 585     /* element is head of a chain */
 586     iter->htable->table[iter->index] = iter->entry->next;
 587   } else {
 588     /* element is mid-chain */
 589     iter->parent->next = iter->entry->next;
 590   }
 591
 592
 593   /* itr->e is now outside the hashtable */
 594   remember_entry = iter->entry;
 595   iter->htable->entry_count--;
 596   if (free_key) {
 597     freekey((void *)(remember_entry->key));
 598   }
 599
 600   /* Advance the iterator, correcting the parent */
 601   remember_parent = iter->parent;
 602   ret = hashtable_iterator_advance(iter);
 603
 604   if (iter->parent == remember_entry) {
 605     iter->parent = remember_parent;
 606   }
 607
 608   V3_Free(remember_entry);
 609   return ret;
 610 }
 611
 612
 613 /* returns zero if not found */
 614 int hashtable_iterator_search(struct hashtable_iter * iter,
 615                               struct hashtable * htable, addr_t key) {
 616   struct hash_entry * entry;
 617   struct hash_entry * parent;
 618   uint_t hash_value;
 619   uint_t index;
 620
 621   hash_value = do_hash(htable, key);
 622   index = indexFor(htable->table_length, hash_value);
 623
 624   entry = htable->table[index];
 625   parent = NULL;
 626
 627   while (entry != NULL) {
 628     /* Check hash value to short circuit heavier comparison */
 629     if ((hash_value == entry->hash) &&
 630         (htable->eq_fn(key, entry->key))) {
 631       iter->index = index;
 632       iter->entry = entry;
 633       iter->parent = parent;
 634       iter->htable = htable;
 635       return -1;
 636     }
 637     parent = entry;
 638     entry = entry->next;
 639   }
 640   return 0;
 641 }
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657 /*
 658  * Copyright (c) 2002, Christopher Clark
 659  * All rights reserved.
 660  *
 661  * Redistribution and use in source and binary forms, with or without
 662  * modification, are permitted provided that the following conditions
 663  * are met:
 664  *
 665  * * Redistributions of source code must retain the above copyright
 666  * notice, this list of conditions and the following disclaimer.
 667  *
 668  * * Redistributions in binary form must reproduce the above copyright
 669  * notice, this list of conditions and the following disclaimer in the
 670  * documentation and/or other materials provided with the distribution.
 671  *
 672  * * Neither the name of the original author; nor the names of any contributors
 673  * may be used to endorse or promote products derived from this software
 674  * without specific prior written permission.
 675  *
 676  *
 677  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 678  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 679  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 680  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 681  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 682  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 683  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 684  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 685  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 686  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 687  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 688 */