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