linux_module/util-hashtable.c

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