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     if (prime_index==prime_table_len) {
 207         // cannot build large enough hash table
 208         return NULL;
 209     }
 210
 211     htable = (struct hashtable *)palacios_alloc(sizeof(struct hashtable));
 212
 213     if (htable == NULL) {
 214         return NULL; /*oom*/
 215     }
 216
 217     htable->table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * size);
 218
 219     if (htable->table == NULL) {
 220         palacios_free(htable);
 221         return NULL;  /*oom*/
 222     }
 223
 224     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 225
 226     htable->table_length  = size;
 227     htable->prime_index   = prime_index;
 228     htable->entry_count   = 0;
 229     htable->hash_fn       = hash_fn;
 230     htable->eq_fn         = eq_fn;
 231     htable->load_limit    = load_factors[prime_index];
 232
 233     return htable;
 234 }
 235
 236
 237 static int hashtable_expand(struct hashtable * htable) {
 238     /* Double the size of the table to accomodate more entries */
 239     struct hash_entry ** new_table;
 240     struct hash_entry * tmp_entry;
 241     struct hash_entry ** entry_ptr;
 242     uint_t new_size;
 243     uint_t i;
 244     uint_t index;
 245
 246     /* Check we're not hitting max capacity */
 247     if (htable->prime_index == (prime_table_len - 1)) {
 248         return 0;
 249     }
 250
 251     new_size = primes[++(htable->prime_index)];
 252
 253     new_table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * new_size);
 254
 255     if (new_table != NULL) {
 256         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 257         /* This algorithm is not 'stable'. ie. it reverses the list
 258          * when it transfers entries between the tables */
 259
 260         for (i = 0; i < htable->table_length; i++) {
 261
 262             while ((tmp_entry = htable->table[i]) != NULL) {
 263                 htable->table[i] = tmp_entry->next;
 264
 265                 index = indexFor(new_size, tmp_entry->hash);
 266
 267                 tmp_entry->next = new_table[index];
 268
 269                 new_table[index] = tmp_entry;
 270             }
 271         }
 272
 273         palacios_free(htable->table);
 274
 275         htable->table = new_table;
 276     } else {
 277         /* Plan B: realloc instead */
 278
 279         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 280         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 281                                                       new_size * sizeof(struct hash_entry *));
 282
 283         if (new_table == NULL) {
 284             (htable->prime_index)--;
 285             return 0;
 286         }
 287
 288         htable->table = new_table;
 289
 290         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 291
 292         for (i = 0; i < htable->table_length; i++) {
 293
 294             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 295                  tmp_entry != NULL;
 296                  tmp_entry = *entry_ptr) {
 297
 298                 index = indexFor(new_size, tmp_entry->hash);
 299
 300                 if (i == index) {
 301                     entry_ptr = &(tmp_entry->next);
 302                 } else {
 303                     *entry_ptr = tmp_entry->next;
 304                     tmp_entry->next = new_table[index];
 305                     new_table[index] = tmp_entry;
 306                 }
 307             }
 308         }
 309     }
 310
 311     htable->table_length = new_size;
 312
 313     htable->load_limit   = load_factors[htable->prime_index];
 314
 315     return -1;
 316 }
 317
 318 uint_t palacios_htable_count(struct hashtable * htable) {
 319     return htable->entry_count;
 320 }
 321
 322 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 323     /* This method allows duplicate keys - but they shouldn't be used */
 324     uint_t index;
 325     struct hash_entry * new_entry;
 326
 327     if (++(htable->entry_count) > htable->load_limit) {
 328         /* Ignore the return value. If expand fails, we should
 329          * still try cramming just this value into the existing table
 330          * -- we may not have memory for a larger table, but one more
 331          * element may be ok. Next time we insert, we'll try expanding again.*/
 332         hashtable_expand(htable);
 333     }
 334
 335     new_entry = (struct hash_entry *)palacios_alloc(sizeof(struct hash_entry));
 336
 337     if (new_entry == NULL) {
 338         (htable->entry_count)--;
 339         return 0; /*oom*/
 340     }
 341
 342     new_entry->hash = do_hash(htable, key);
 343
 344     index = indexFor(htable->table_length, new_entry->hash);
 345
 346     new_entry->key = key;
 347     new_entry->value = value;
 348
 349     new_entry->next = htable->table[index];
 350
 351     htable->table[index] = new_entry;
 352
 353     return -1;
 354 }
 355
 356
 357 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
 358     struct hash_entry * tmp_entry;
 359     uint_t hash_value;
 360     uint_t index;
 361
 362     hash_value = do_hash(htable, key);
 363
 364     index = indexFor(htable->table_length, hash_value);
 365
 366     tmp_entry = htable->table[index];
 367
 368     while (tmp_entry != NULL) {
 369         /* Check hash value to short circuit heavier comparison */
 370         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 371
 372             if (free_value) {
 373                 palacios_free((void *)(tmp_entry->value));
 374             }
 375
 376             tmp_entry->value = value;
 377             return -1;
 378         }
 379         tmp_entry = tmp_entry->next;
 380     }
 381     return 0;
 382 }
 383
 384
 385
 386 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
 387     struct hash_entry * tmp_entry;
 388     uint_t hash_value;
 389     uint_t index;
 390
 391     hash_value = do_hash(htable, key);
 392
 393     index = indexFor(htable->table_length, hash_value);
 394
 395     tmp_entry = htable->table[index];
 396
 397     while (tmp_entry != NULL) {
 398         /* Check hash value to short circuit heavier comparison */
 399         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 400
 401             tmp_entry->value += value;
 402             return -1;
 403         }
 404         tmp_entry = tmp_entry->next;
 405     }
 406     return 0;
 407 }
 408
 409
 410 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
 411     struct hash_entry * tmp_entry;
 412     uint_t hash_value;
 413     uint_t index;
 414
 415     hash_value = do_hash(htable, key);
 416
 417     index = indexFor(htable->table_length, hash_value);
 418
 419     tmp_entry = htable->table[index];
 420
 421     while (tmp_entry != NULL) {
 422         /* Check hash value to short circuit heavier comparison */
 423         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 424
 425             tmp_entry->value -= value;
 426             return -1;
 427         }
 428         tmp_entry = tmp_entry->next;
 429     }
 430     return 0;
 431 }
 432
 433
 434 /* returns value associated with key */
 435 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
 436     struct hash_entry * cursor;
 437     uint_t hash_value;
 438     uint_t index;
 439
 440     hash_value = do_hash(htable, key);
 441
 442     index = indexFor(htable->table_length, hash_value);
 443
 444     cursor = htable->table[index];
 445
 446     while (cursor != NULL) {
 447         /* Check hash value to short circuit heavier comparison */
 448         if ((hash_value == cursor->hash) &&
 449             (htable->eq_fn(key, cursor->key))) {
 450             return cursor->value;
 451         }
 452
 453         cursor = cursor->next;
 454     }
 455
 456     return (addr_t)NULL;
 457 }
 458
 459
 460 /* returns value associated with key */
 461 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 462     /* TODO: consider compacting the table when the load factor drops enough,
 463      *       or provide a 'compact' method. */
 464
 465     struct hash_entry * cursor;
 466     struct hash_entry ** entry_ptr;
 467     addr_t value;
 468     uint_t hash_value;
 469     uint_t index;
 470
 471     hash_value = do_hash(htable, key);
 472
 473     index = indexFor(htable->table_length, hash_value);
 474
 475     entry_ptr = &(htable->table[index]);
 476     cursor = *entry_ptr;
 477
 478     while (cursor != NULL) {
 479         /* Check hash value to short circuit heavier comparison */
 480         if ((hash_value == cursor->hash) &&
 481             (htable->eq_fn(key, cursor->key))) {
 482
 483             *entry_ptr = cursor->next;
 484             htable->entry_count--;
 485             value = cursor->value;
 486
 487             if (free_key) {
 488                 freekey((void *)(cursor->key));
 489             }
 490             palacios_free(cursor);
 491
 492             return value;
 493         }
 494
 495         entry_ptr = &(cursor->next);
 496         cursor = cursor->next;
 497     }
 498     return (addr_t)NULL;
 499 }
 500
 501
 502 /* destroy */
 503 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 504     uint_t i;
 505     struct hash_entry * cursor;
 506     struct hash_entry * tmp;
 507     struct hash_entry **table = htable->table;
 508
 509     if (free_values) {
 510         for (i = 0; i < htable->table_length; i++) {
 511             cursor = table[i];
 512
 513             while (cursor != NULL) {
 514                 tmp = cursor;
 515                 cursor = cursor->next;
 516
 517                 if (free_keys) {
 518                     freekey((void *)(tmp->key));
 519                 }
 520                 palacios_free((void *)(tmp->value));
 521                 palacios_free(tmp);
 522             }
 523         }
 524     } else {
 525         for (i = 0; i < htable->table_length; i++) {
 526             cursor = table[i];
 527
 528             while (cursor != NULL) {
 529                 struct hash_entry * tmp;
 530
 531                 tmp = cursor;
 532                 cursor = cursor->next;
 533
 534                 if (free_keys) {
 535                     freekey((void *)(tmp->key));
 536                 }
 537                 palacios_free(tmp);
 538             }
 539         }
 540     }
 541
 542     palacios_free(htable->table);
 543     palacios_free(htable);
 544 }
 545