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