linux_module/util-hashtable.c

   1 /*
   2  * This file is part of the Palacios Virtual Machine Monitor developed
   3  * by the V3VEE Project with funding from the United States National
   4  * Science Foundation and the Department of Energy.
   5  *
   6  * The V3VEE Project is a joint project between Northwestern University
   7  * and the University of New Mexico.  You can find out more at
   8  * http://www.v3vee.org
   9  *
  10  * Copyright (c) 2011, Lei Xia <lxia@northwestern.edu>
  11  * Copyright (c) 2011, The V3VEE Project <http://www.v3vee.org>
  12  * All rights reserved.
  13  *
  14  * This is free software.  You are permitted to use, redistribute,
  15  * and modify it under the terms of the GNU General Public License
  16  * Version 2 (GPLv2).  The accompanying COPYING file contains the
  17  * full text of the license.
  18  */
  19
  20 #include <linux/string.h>
  21 #include <linux/errno.h>
  22 #include <linux/preempt.h>
  23 #include <linux/sched.h>
  24
  25 #include "util-hashtable.h"
  26
  27
  28 struct hash_entry {
  29     addr_t key;
  30     addr_t value;
  31     uint_t hash;
  32     struct hash_entry * next;
  33 };
  34
  35 struct hashtable {
  36     uint_t table_length;
  37     struct hash_entry ** table;
  38     uint_t entry_count;
  39     uint_t load_limit;
  40     uint_t prime_index;
  41     uint_t (*hash_fn) (addr_t key);
  42     int (*eq_fn) (addr_t key1, addr_t key2);
  43 };
  44
  45
  46 /* HASH FUNCTIONS */
  47
  48 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
  49     /* Aim to protect against poor hash functions by adding logic here
  50      * - logic taken from java 1.4 hashtable source */
  51     uint_t i = htable->hash_fn(key);
  52     i += ~(i << 9);
  53     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  54     i +=  (i << 4);
  55     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  56
  57     return i;
  58 }
  59
  60
  61 /* HASH AN UNSIGNED LONG */
  62 /* LINUX UNSIGHED LONG HASH FUNCTION */
  63 #ifdef __32BIT__
  64 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  65 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  66 //#define BITS_PER_LONG 32
  67 #elif  defined(__64BIT__)
  68 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  69 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  70 //#define BITS_PER_LONG 64
  71 #else
  72 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  73 #endif
  74
  75 ulong_t palacios_hash_long(ulong_t val, uint_t bits) {
  76     ulong_t hash = val;
  77
  78 #ifdef __PALACIOS_64BIT__
  79     /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
  80     ulong_t n = hash;
  81     n <<= 18;
  82     hash -= n;
  83     n <<= 33;
  84     hash -= n;
  85     n <<= 3;
  86     hash += n;
  87     n <<= 3;
  88     hash -= n;
  89     n <<= 4;
  90     hash += n;
  91     n <<= 2;
  92     hash += n;
  93 #else
  94     /* On some cpus multiply is faster, on others gcc will do shifts */
  95     hash *= GOLDEN_RATIO_PRIME;
  96 #endif
  97
  98     /* High bits are more random, so use them. */
  99     return hash >> (BITS_PER_LONG - bits);
 100 }
 101
 102 /* HASH GENERIC MEMORY BUFFER */
 103 /* ELF HEADER HASH FUNCTION */
 104 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length) {
 105     ulong_t hash = 0;
 106     ulong_t temp = 0;
 107     uint_t i;
 108
 109     for (i = 0; i < length; i++) {
 110         hash = (hash << 4) + *(msg + i) + i;
 111         if ((temp = (hash & 0xF0000000))) {
 112             hash ^= (temp >> 24);
 113         }
 114         hash &= ~temp;
 115     }
 116     return hash;
 117 }
 118
 119 /* indexFor */
 120 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
 121     return (hash_value % table_length);
 122 };
 123
 124 #define freekey(X) kfree(X)
 125
 126
 127 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
 128     void * new_buf = kmalloc(new_size, GFP_KERNEL);
 129
 130     if (new_buf == NULL) {
 131         return NULL;
 132     }
 133
 134     memcpy(new_buf, old_ptr, old_size);
 135     kfree(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 // this assumes that the max load factor is .65
 157 static const uint_t load_factors[] = {
 158     35, 64, 126, 253,
 159     500, 1003, 2002, 3999,
 160     7988, 15986, 31953, 63907,
 161     127799, 255607, 511182, 1022365,
 162     2044731, 4089455, 8178897, 16357798,
 163     32715575, 65431158, 130862298, 261724573,
 164     523449198, 1046898282 };
 165
 166 const uint_t prime_table_len = sizeof(primes) / sizeof(primes[0]);
 167
 168 struct hashtable * palacios_create_htable(uint_t min_size,
 169                                     uint_t (*hash_fn) (addr_t),
 170                                     int (*eq_fn) (addr_t, addr_t)) {
 171     struct hashtable * htable;
 172     uint_t prime_index;
 173     uint_t size = primes[0];
 174
 175     /* Check requested hashtable isn't too large */
 176     if (min_size > (1u << 30)) {
 177         return NULL;
 178     }
 179
 180     /* Enforce size as prime */
 181     for (prime_index = 0; prime_index < prime_table_len; prime_index++) {
 182         if (primes[prime_index] > min_size) {
 183             size = primes[prime_index];
 184             break;
 185         }
 186     }
 187
 188     htable = (struct hashtable *)kmalloc(sizeof(struct hashtable), GFP_KERNEL);
 189
 190     if (htable == NULL) {
 191         return NULL; /*oom*/
 192     }
 193
 194     htable->table = (struct hash_entry **)kmalloc(sizeof(struct hash_entry*) * size, GFP_KERNEL);
 195
 196     if (htable->table == NULL) {
 197         kfree(htable);
 198         return NULL;  /*oom*/
 199     }
 200
 201     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 202
 203     htable->table_length  = size;
 204     htable->prime_index   = prime_index;
 205     htable->entry_count   = 0;
 206     htable->hash_fn       = hash_fn;
 207     htable->eq_fn         = eq_fn;
 208     htable->load_limit    = load_factors[prime_index];
 209
 210     return htable;
 211 }
 212
 213
 214 static int hashtable_expand(struct hashtable * htable) {
 215     /* Double the size of the table to accomodate more entries */
 216     struct hash_entry ** new_table;
 217     struct hash_entry * tmp_entry;
 218     struct hash_entry ** entry_ptr;
 219     uint_t new_size;
 220     uint_t i;
 221     uint_t index;
 222
 223     /* Check we're not hitting max capacity */
 224     if (htable->prime_index == (prime_table_len - 1)) {
 225         return 0;
 226     }
 227
 228     new_size = primes[++(htable->prime_index)];
 229
 230     new_table = (struct hash_entry **)kmalloc(sizeof(struct hash_entry*) * new_size, GFP_KERNEL);
 231
 232     if (new_table != NULL) {
 233         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 234         /* This algorithm is not 'stable'. ie. it reverses the list
 235          * when it transfers entries between the tables */
 236
 237         for (i = 0; i < htable->table_length; i++) {
 238
 239             while ((tmp_entry = htable->table[i]) != NULL) {
 240                 htable->table[i] = tmp_entry->next;
 241
 242                 index = indexFor(new_size, tmp_entry->hash);
 243
 244                 tmp_entry->next = new_table[index];
 245
 246                 new_table[index] = tmp_entry;
 247             }
 248         }
 249
 250         kfree(htable->table);
 251
 252         htable->table = new_table;
 253     } else {
 254         /* Plan B: realloc instead */
 255
 256         //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 257         new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 258                                                       new_size * sizeof(struct hash_entry *));
 259
 260         if (new_table == NULL) {
 261             (htable->prime_index)--;
 262             return 0;
 263         }
 264
 265         htable->table = new_table;
 266
 267         memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 268
 269         for (i = 0; i < htable->table_length; i++) {
 270
 271             for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 272                  tmp_entry != NULL;
 273                  tmp_entry = *entry_ptr) {
 274
 275                 index = indexFor(new_size, tmp_entry->hash);
 276
 277                 if (i == index) {
 278                     entry_ptr = &(tmp_entry->next);
 279                 } else {
 280                     *entry_ptr = tmp_entry->next;
 281                     tmp_entry->next = new_table[index];
 282                     new_table[index] = tmp_entry;
 283                 }
 284             }
 285         }
 286     }
 287
 288     htable->table_length = new_size;
 289
 290     htable->load_limit   = load_factors[htable->prime_index];
 291
 292     return -1;
 293 }
 294
 295 uint_t palacios_htable_count(struct hashtable * htable) {
 296     return htable->entry_count;
 297 }
 298
 299 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 300     /* This method allows duplicate keys - but they shouldn't be used */
 301     uint_t index;
 302     struct hash_entry * new_entry;
 303
 304     if (++(htable->entry_count) > htable->load_limit) {
 305         /* Ignore the return value. If expand fails, we should
 306          * still try cramming just this value into the existing table
 307          * -- we may not have memory for a larger table, but one more
 308          * element may be ok. Next time we insert, we'll try expanding again.*/
 309         hashtable_expand(htable);
 310     }
 311
 312     new_entry = (struct hash_entry *)kmalloc(sizeof(struct hash_entry), GFP_KERNEL);
 313
 314     if (new_entry == NULL) {
 315         (htable->entry_count)--;
 316         return 0; /*oom*/
 317     }
 318
 319     new_entry->hash = do_hash(htable, key);
 320
 321     index = indexFor(htable->table_length, new_entry->hash);
 322
 323     new_entry->key = key;
 324     new_entry->value = value;
 325
 326     new_entry->next = htable->table[index];
 327
 328     htable->table[index] = new_entry;
 329
 330     return -1;
 331 }
 332
 333
 334 int palacios_htable_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                 kfree((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 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
 364     struct hash_entry * tmp_entry;
 365     uint_t hash_value;
 366     uint_t index;
 367
 368     hash_value = do_hash(htable, key);
 369
 370     index = indexFor(htable->table_length, hash_value);
 371
 372     tmp_entry = htable->table[index];
 373
 374     while (tmp_entry != NULL) {
 375         /* Check hash value to short circuit heavier comparison */
 376         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 377
 378             tmp_entry->value += value;
 379             return -1;
 380         }
 381         tmp_entry = tmp_entry->next;
 382     }
 383     return 0;
 384 }
 385
 386
 387 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
 388     struct hash_entry * tmp_entry;
 389     uint_t hash_value;
 390     uint_t index;
 391
 392     hash_value = do_hash(htable, key);
 393
 394     index = indexFor(htable->table_length, hash_value);
 395
 396     tmp_entry = htable->table[index];
 397
 398     while (tmp_entry != NULL) {
 399         /* Check hash value to short circuit heavier comparison */
 400         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 401
 402             tmp_entry->value -= value;
 403             return -1;
 404         }
 405         tmp_entry = tmp_entry->next;
 406     }
 407     return 0;
 408 }
 409
 410
 411 /* returns value associated with key */
 412 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
 413     struct hash_entry * cursor;
 414     uint_t hash_value;
 415     uint_t index;
 416
 417     hash_value = do_hash(htable, key);
 418
 419     index = indexFor(htable->table_length, hash_value);
 420
 421     cursor = htable->table[index];
 422
 423     while (cursor != NULL) {
 424         /* Check hash value to short circuit heavier comparison */
 425         if ((hash_value == cursor->hash) &&
 426             (htable->eq_fn(key, cursor->key))) {
 427             return cursor->value;
 428         }
 429
 430         cursor = cursor->next;
 431     }
 432
 433     return (addr_t)NULL;
 434 }
 435
 436
 437 /* returns value associated with key */
 438 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
 439     /* TODO: consider compacting the table when the load factor drops enough,
 440      *       or provide a 'compact' method. */
 441
 442     struct hash_entry * cursor;
 443     struct hash_entry ** entry_ptr;
 444     addr_t value;
 445     uint_t hash_value;
 446     uint_t index;
 447
 448     hash_value = do_hash(htable, key);
 449
 450     index = indexFor(htable->table_length, hash_value);
 451
 452     entry_ptr = &(htable->table[index]);
 453     cursor = *entry_ptr;
 454
 455     while (cursor != NULL) {
 456         /* Check hash value to short circuit heavier comparison */
 457         if ((hash_value == cursor->hash) &&
 458             (htable->eq_fn(key, cursor->key))) {
 459
 460             *entry_ptr = cursor->next;
 461             htable->entry_count--;
 462             value = cursor->value;
 463
 464             if (free_key) {
 465                 freekey((void *)(cursor->key));
 466             }
 467             kfree(cursor);
 468
 469             return value;
 470         }
 471
 472         entry_ptr = &(cursor->next);
 473         cursor = cursor->next;
 474     }
 475     return (addr_t)NULL;
 476 }
 477
 478
 479 /* destroy */
 480 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
 481     uint_t i;
 482     struct hash_entry * cursor;
 483     struct hash_entry * tmp;
 484     struct hash_entry **table = htable->table;
 485
 486     if (free_values) {
 487         for (i = 0; i < htable->table_length; i++) {
 488             cursor = table[i];
 489
 490             while (cursor != NULL) {
 491                 tmp = cursor;
 492                 cursor = cursor->next;
 493
 494                 if (free_keys) {
 495                     freekey((void *)(tmp->key));
 496                 }
 497                 kfree((void *)(tmp->value));
 498                 kfree(tmp);
 499             }
 500         }
 501     } else {
 502         for (i = 0; i < htable->table_length; i++) {
 503             cursor = table[i];
 504
 505             while (cursor != NULL) {
 506                 struct hash_entry * tmp;
 507
 508                 tmp = cursor;
 509                 cursor = cursor->next;
 510
 511                 if (free_keys) {
 512                     freekey((void *)(tmp->key));
 513                 }
 514                 kfree(tmp);
 515             }
 516         }
 517     }
 518
 519     kfree(htable->table);
 520     kfree(htable);
 521 }
 522