linux_module/util-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 Lei Xia */
  35
  36 #include <linux/string.h>
  37 #include <linux/errno.h>
  38 #include <linux/preempt.h>
  39 #include <linux/sched.h>
  40 #include <linux/slab.h>
  41
  42 #include "palacios.h"
  43 #include "util-hashtable.h"
  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 /* HASH FUNCTIONS */
  65
  66 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
  67     /* Aim to protect against poor hash functions by adding logic here
  68      * - logic taken from java 1.4 hashtable source */
  69     uint_t i = htable->hash_fn(key);
  70     i += ~(i << 9);
  71     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  72     i +=  (i << 4);
  73     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  74
  75     return i;
  76 }
  77
  78
  79 /* HASH AN UNSIGNED LONG */
  80 /* LINUX UNSIGHED LONG HASH FUNCTION */
  81 #ifdef __32BIT__
  82 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  83 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  84 //#define BITS_PER_LONG 32
  85 #elif  defined(__64BIT__)
  86 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  87 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  88 //#define BITS_PER_LONG 64
  89 #else
  90 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  91 #endif
  92
  93 ulong_t palacios_hash_long(ulong_t val, uint_t bits) {
  94     ulong_t hash = val;
  95
  96 #ifdef __PALACIOS_64BIT__
  97     /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
  98     ulong_t n = hash;
  99     n <<= 18;
 100     hash -= n;
 101     n <<= 33;
 102     hash -= n;
 103     n <<= 3;
 104     hash += n;
 105     n <<= 3;
 106     hash -= n;
 107     n <<= 4;
 108     hash += n;
 109     n <<= 2;
 110     hash += n;
 111 #else
 112     /* On some cpus multiply is faster, on others gcc will do shifts */
 113     hash *= GOLDEN_RATIO_PRIME;
 114 #endif
 115
 116     /* High bits are more random, so use them. */
 117     return hash >> (BITS_PER_LONG - bits);
 118 }
 119
 120 /* HASH GENERIC MEMORY BUFFER */
 121 /* ELF HEADER HASH FUNCTION */
 122 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length) {
 123     ulong_t hash = 0;
 124     ulong_t temp = 0;
 125     uint_t i;
 126
 127     for (i = 0; i < length; i++) {
 128         hash = (hash << 4) + *(msg + i) + i;
 129         if ((temp = (hash & 0xF0000000))) {
 130             hash ^= (temp >> 24);
 131         }
 132         hash &= ~temp;
 133     }
 134     return hash;
 135 }
 136
 137 /* indexFor */
 138 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
 139     return (hash_value % table_length);
 140 };
 141
 142 #define freekey(X) palacios_free(X)
 143
 144
 145 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
 146     void * new_buf = palacios_alloc(new_size);
 147
 148     if (new_buf == NULL) {
 149         return NULL;
 150     }
 151
 152     memcpy(new_buf, old_ptr, old_size);
 153     palacios_free(old_ptr);
 154
 155     return new_buf;
 156 }
 157
 158
 159 /*
 160   Credit for primes table: Aaron Krowne
 161   http://br.endernet.org/~akrowne/
 162   http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 163 */
 164 static const uint_t primes[] = {
 165     53, 97, 193, 389,
 166     769, 1543, 3079, 6151,
 167     12289, 24593, 49157, 98317,
 168     196613, 393241, 786433, 1572869,
 169     3145739, 6291469, 12582917, 25165843,
 170     50331653, 100663319, 201326611, 402653189,
 171     805306457, 1610612741 };
 172
 173
 174 // this assumes that the max load factor is .65
 175 static const uint_t load_factors[] = {
 176     35, 64, 126, 253,
 177     500, 1003, 2002, 3999,
 178     7988, 15986, 31953, 63907,
 179     127799, 255607, 511182, 1022365,
 180     2044731, 4089455, 8178897, 16357798,
 181     32715575, 65431158, 130862298, 261724573,
 182     523449198, 1046898282 };
 183
 184 const uint_t prime_table_len = sizeof(primes) / sizeof(primes[0]);
 185
 186 struct hashtable * palacios_create_htable(uint_t min_size,
 187                                     uint_t (*hash_fn) (addr_t),
 188                                     int (*eq_fn) (addr_t, addr_t)) {
 189     struct hashtable * htable;
 190     uint_t prime_index;
 191     uint_t size = primes[0];
 192
 193     /* Check requested hashtable isn't too large */
 194     if (min_size > (1u << 30)) {
 195         return NULL;
 196     }
 197
 198     /* Enforce size as prime */
 199     for (prime_index = 0; prime_index < prime_table_len; prime_index++) {
 200         if (primes[prime_index] > min_size) {
 201             size = primes[prime_index];
 202             break;
 203         }
 204     }
 205
 206     htable = (struct hashtable *)palacios_alloc(sizeof(struct hashtable));
 207
 208     if (htable == NULL) {
 209         return NULL; /*oom*/
 210     }
 211
 212     htable->table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * size);
 213
 214     if (htable->table == NULL) {
 215         palacios_free(htable);
 216         return NULL;  /*oom*/
 217     }
 218
 219     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 220
 221     htable->table_length  = size;
 222     htable->prime_index   = prime_index;
 223     htable->entry_count   = 0;
 224     htable->hash_fn       = hash_fn;
 225     htable->eq_fn         = eq_fn;
 226     htable->load_limit    = load_factors[prime_index];
 227
 228     return htable;
 229 }
 230
 231
 232 static int hashtable_expand(struct hashtable * htable) {
 233     /* Double the size of the table to accomodate more entries */
 234     struct hash_entry ** new_table;
 235     struct hash_entry * tmp_entry;
 236     struct hash_entry ** entry_ptr;
 237     uint_t new_size;
 238     uint_t i;
 239     uint_t index;
 240
 241     /* Check we're not hitting max capacity */
 242     if (htable->prime_index == (prime_table_len - 1)) {
 243         return 0;
 244     }
 245
 246     new_size = primes[++(htable->prime_index)];
 247
 248     new_table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * new_size);
 249
 250     if (new_table != NULL) {
 251         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 252         /* This algorithm is not 'stable'. ie. it reverses the list
 253          * when it transfers entries between the tables */
 254
 255         for (i = 0; i < htable->table_length; i++) {
 256
 257             while ((tmp_entry = htable->table[i]) != NULL) {
 258                 htable->table[i] = tmp_entry->next;
 259
 260                 index = indexFor(new_size, tmp_entry->hash);
 261
 262                 tmp_entry->next = new_table[index];
 263
 264                 new_table[index] = tmp_entry;
 265             }
 266         }
 267
 268         palacios_free(htable->table);
 269
 270         htable->table = new_table;
 271     } else {
 272         /* Plan B: realloc instead */
 273
 274         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 275         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 276                                                       new_size * sizeof(struct hash_entry *));
 277
 278         if (new_table == NULL) {
 279             (htable->prime_index)--;
 280             return 0;
 281         }
 282
 283         htable->table = new_table;
 284
 285         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 286
 287         for (i = 0; i < htable->table_length; i++) {
 288
 289             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 290                  tmp_entry != NULL;
 291                  tmp_entry = *entry_ptr) {
 292
 293                 index = indexFor(new_size, tmp_entry->hash);
 294
 295                 if (i == index) {
 296                     entry_ptr = &(tmp_entry->next);
 297                 } else {
 298                     *entry_ptr = tmp_entry->next;
 299                     tmp_entry->next = new_table[index];
 300                     new_table[index] = tmp_entry;
 301                 }
 302             }
 303         }
 304     }
 305
 306     htable->table_length = new_size;
 307
 308     htable->load_limit   = load_factors[htable->prime_index];
 309
 310     return -1;
 311 }
 312
 313 uint_t palacios_htable_count(struct hashtable * htable) {
 314     return htable->entry_count;
 315 }
 316
 317 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 318     /* This method allows duplicate keys - but they shouldn't be used */
 319     uint_t index;
 320     struct hash_entry * new_entry;
 321
 322     if (++(htable->entry_count) > htable->load_limit) {
 323         /* Ignore the return value. If expand fails, we should
 324          * still try cramming just this value into the existing table
 325          * -- we may not have memory for a larger table, but one more
 326          * element may be ok. Next time we insert, we'll try expanding again.*/
 327         hashtable_expand(htable);
 328     }
 329
 330     new_entry = (struct hash_entry *)palacios_alloc(sizeof(struct hash_entry));
 331
 332     if (new_entry == NULL) {
 333         (htable->entry_count)--;
 334         return 0; /*oom*/
 335     }
 336
 337     new_entry->hash = do_hash(htable, key);
 338
 339     index = indexFor(htable->table_length, new_entry->hash);
 340
 341     new_entry->key = key;
 342     new_entry->value = value;
 343
 344     new_entry->next = htable->table[index];
 345
 346     htable->table[index] = new_entry;
 347
 348     return -1;
 349 }
 350
 351
 352 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
 353     struct hash_entry * tmp_entry;
 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     tmp_entry = htable->table[index];
 362
 363     while (tmp_entry != NULL) {
 364         /* Check hash value to short circuit heavier comparison */
 365         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 366
 367             if (free_value) {
 368                 palacios_free((void *)(tmp_entry->value));
 369             }
 370
 371             tmp_entry->value = value;
 372             return -1;
 373         }
 374         tmp_entry = tmp_entry->next;
 375     }
 376     return 0;
 377 }
 378
 379
 380
 381 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
 382     struct hash_entry * tmp_entry;
 383     uint_t hash_value;
 384     uint_t index;
 385
 386     hash_value = do_hash(htable, key);
 387
 388     index = indexFor(htable->table_length, hash_value);
 389
 390     tmp_entry = htable->table[index];
 391
 392     while (tmp_entry != NULL) {
 393         /* Check hash value to short circuit heavier comparison */
 394         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 395
 396             tmp_entry->value += value;
 397             return -1;
 398         }
 399         tmp_entry = tmp_entry->next;
 400     }
 401     return 0;
 402 }
 403
 404
 405 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
 406     struct hash_entry * tmp_entry;
 407     uint_t hash_value;
 408     uint_t index;
 409
 410     hash_value = do_hash(htable, key);
 411
 412     index = indexFor(htable->table_length, hash_value);
 413
 414     tmp_entry = htable->table[index];
 415
 416     while (tmp_entry != NULL) {
 417         /* Check hash value to short circuit heavier comparison */
 418         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 419
 420             tmp_entry->value -= value;
 421             return -1;
 422         }
 423         tmp_entry = tmp_entry->next;
 424     }
 425     return 0;
 426 }
 427
 428
 429 /* returns value associated with key */
 430 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
 431     struct hash_entry * cursor;
 432     uint_t hash_value;
 433     uint_t index;
 434
 435     hash_value = do_hash(htable, key);
 436
 437     index = indexFor(htable->table_length, hash_value);
 438
 439     cursor = htable->table[index];
 440
 441     while (cursor != NULL) {
 442         /* Check hash value to short circuit heavier comparison */
 443         if ((hash_value == cursor->hash) &&
 444             (htable->eq_fn(key, cursor->key))) {
 445             return cursor->value;
 446         }
 447
 448         cursor = cursor->next;
 449     }
 450
 451     return (addr_t)NULL;
 452 }
 453
 454
 455 /* returns value associated with key */
 456 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 457     /* TODO: consider compacting the table when the load factor drops enough,
 458      *       or provide a 'compact' method. */
 459
 460     struct hash_entry * cursor;
 461     struct hash_entry ** entry_ptr;
 462     addr_t value;
 463     uint_t hash_value;
 464     uint_t index;
 465
 466     hash_value = do_hash(htable, key);
 467
 468     index = indexFor(htable->table_length, hash_value);
 469
 470     entry_ptr = &(htable->table[index]);
 471     cursor = *entry_ptr;
 472
 473     while (cursor != NULL) {
 474         /* Check hash value to short circuit heavier comparison */
 475         if ((hash_value == cursor->hash) &&
 476             (htable->eq_fn(key, cursor->key))) {
 477
 478             *entry_ptr = cursor->next;
 479             htable->entry_count--;
 480             value = cursor->value;
 481
 482             if (free_key) {
 483                 freekey((void *)(cursor->key));
 484             }
 485             palacios_free(cursor);
 486
 487             return value;
 488         }
 489
 490         entry_ptr = &(cursor->next);
 491         cursor = cursor->next;
 492     }
 493     return (addr_t)NULL;
 494 }
 495
 496
 497 /* destroy */
 498 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 499     uint_t i;
 500     struct hash_entry * cursor;
 501     struct hash_entry * tmp;
 502     struct hash_entry **table = htable->table;
 503
 504     if (free_values) {
 505         for (i = 0; i < htable->table_length; i++) {
 506             cursor = table[i];
 507
 508             while (cursor != NULL) {
 509                 tmp = cursor;
 510                 cursor = cursor->next;
 511
 512                 if (free_keys) {
 513                     freekey((void *)(tmp->key));
 514                 }
 515                 palacios_free((void *)(tmp->value));
 516                 palacios_free(tmp);
 517             }
 518         }
 519     } else {
 520         for (i = 0; i < htable->table_length; i++) {
 521             cursor = table[i];
 522
 523             while (cursor != NULL) {
 524                 struct hash_entry * tmp;
 525
 526                 tmp = cursor;
 527                 cursor = cursor->next;
 528
 529                 if (free_keys) {
 530                     freekey((void *)(tmp->key));
 531                 }
 532                 palacios_free(tmp);
 533             }
 534         }
 535     }
 536
 537     palacios_free(htable->table);
 538     palacios_free(htable);
 539 }
 540