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.
6 * The V3VEE Project is a joint project between Northwestern University
7 * and the University of New Mexico. You can find out more at
10 * Copyright (c) 2011, Lei Xia <lxia@northwestern.edu>
11 * Copyright (c) 2011, The V3VEE Project <http://www.v3vee.org>
12 * All rights reserved.
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.
20 #include <linux/string.h>
21 #include <linux/errno.h>
22 #include <linux/preempt.h>
23 #include <linux/sched.h>
25 #include "util-hashtable.h"
32 struct hash_entry * next;
37 struct hash_entry ** table;
41 uint_t (*hash_fn) (addr_t key);
42 int (*eq_fn) (addr_t key1, addr_t key2);
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);
53 i ^= ((i >> 14) | (i << 18)); /* >>> */
55 i ^= ((i >> 10) | (i << 22)); /* >>> */
61 /* HASH AN UNSIGNED LONG */
62 /* LINUX UNSIGHED LONG HASH FUNCTION */
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
72 #error Define GOLDEN_RATIO_PRIME for your wordsize.
75 ulong_t palacios_hash_long(ulong_t val, uint_t bits) {
78 #ifdef __PALACIOS_64BIT__
79 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
94 /* On some cpus multiply is faster, on others gcc will do shifts */
95 hash *= GOLDEN_RATIO_PRIME;
98 /* High bits are more random, so use them. */
99 return hash >> (BITS_PER_LONG - bits);
102 /* HASH GENERIC MEMORY BUFFER */
103 /* ELF HEADER HASH FUNCTION */
104 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length) {
109 for (i = 0; i < length; i++) {
110 hash = (hash << 4) + *(msg + i) + i;
111 if ((temp = (hash & 0xF0000000))) {
112 hash ^= (temp >> 24);
120 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
121 return (hash_value % table_length);
124 #define freekey(X) kfree(X)
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);
130 if (new_buf == NULL) {
134 memcpy(new_buf, old_ptr, old_size);
142 Credit for primes table: Aaron Krowne
143 http://br.endernet.org/~akrowne/
144 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
146 static const uint_t primes[] = {
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 };
156 // this assumes that the max load factor is .65
157 static const uint_t load_factors[] = {
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 };
166 const uint_t prime_table_len = sizeof(primes) / sizeof(primes[0]);
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;
173 uint_t size = primes[0];
175 /* Check requested hashtable isn't too large */
176 if (min_size > (1u << 30)) {
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];
188 htable = (struct hashtable *)kmalloc(sizeof(struct hashtable), GFP_KERNEL);
190 if (htable == NULL) {
194 htable->table = (struct hash_entry **)kmalloc(sizeof(struct hash_entry*) * size, GFP_KERNEL);
196 if (htable->table == NULL) {
201 memset(htable->table, 0, size * sizeof(struct hash_entry *));
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];
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;
223 /* Check we're not hitting max capacity */
224 if (htable->prime_index == (prime_table_len - 1)) {
228 new_size = primes[++(htable->prime_index)];
230 new_table = (struct hash_entry **)kmalloc(sizeof(struct hash_entry*) * new_size, GFP_KERNEL);
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 */
237 for (i = 0; i < htable->table_length; i++) {
239 while ((tmp_entry = htable->table[i]) != NULL) {
240 htable->table[i] = tmp_entry->next;
242 index = indexFor(new_size, tmp_entry->hash);
244 tmp_entry->next = new_table[index];
246 new_table[index] = tmp_entry;
250 kfree(htable->table);
252 htable->table = new_table;
254 /* Plan B: realloc instead */
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 *));
260 if (new_table == NULL) {
261 (htable->prime_index)--;
265 htable->table = new_table;
267 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
269 for (i = 0; i < htable->table_length; i++) {
271 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
273 tmp_entry = *entry_ptr) {
275 index = indexFor(new_size, tmp_entry->hash);
278 entry_ptr = &(tmp_entry->next);
280 *entry_ptr = tmp_entry->next;
281 tmp_entry->next = new_table[index];
282 new_table[index] = tmp_entry;
288 htable->table_length = new_size;
290 htable->load_limit = load_factors[htable->prime_index];
295 uint_t palacios_htable_count(struct hashtable * htable) {
296 return htable->entry_count;
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 */
302 struct hash_entry * new_entry;
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);
312 new_entry = (struct hash_entry *)kmalloc(sizeof(struct hash_entry), GFP_KERNEL);
314 if (new_entry == NULL) {
315 (htable->entry_count)--;
319 new_entry->hash = do_hash(htable, key);
321 index = indexFor(htable->table_length, new_entry->hash);
323 new_entry->key = key;
324 new_entry->value = value;
326 new_entry->next = htable->table[index];
328 htable->table[index] = new_entry;
334 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
335 struct hash_entry * tmp_entry;
339 hash_value = do_hash(htable, key);
341 index = indexFor(htable->table_length, hash_value);
343 tmp_entry = htable->table[index];
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))) {
350 kfree((void *)(tmp_entry->value));
353 tmp_entry->value = value;
356 tmp_entry = tmp_entry->next;
363 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
364 struct hash_entry * tmp_entry;
368 hash_value = do_hash(htable, key);
370 index = indexFor(htable->table_length, hash_value);
372 tmp_entry = htable->table[index];
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))) {
378 tmp_entry->value += value;
381 tmp_entry = tmp_entry->next;
387 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
388 struct hash_entry * tmp_entry;
392 hash_value = do_hash(htable, key);
394 index = indexFor(htable->table_length, hash_value);
396 tmp_entry = htable->table[index];
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))) {
402 tmp_entry->value -= value;
405 tmp_entry = tmp_entry->next;
411 /* returns value associated with key */
412 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
413 struct hash_entry * cursor;
417 hash_value = do_hash(htable, key);
419 index = indexFor(htable->table_length, hash_value);
421 cursor = htable->table[index];
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;
430 cursor = cursor->next;
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. */
442 struct hash_entry * cursor;
443 struct hash_entry ** entry_ptr;
448 hash_value = do_hash(htable, key);
450 index = indexFor(htable->table_length, hash_value);
452 entry_ptr = &(htable->table[index]);
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))) {
460 *entry_ptr = cursor->next;
461 htable->entry_count--;
462 value = cursor->value;
465 freekey((void *)(cursor->key));
472 entry_ptr = &(cursor->next);
473 cursor = cursor->next;
480 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
482 struct hash_entry * cursor;
483 struct hash_entry * tmp;
484 struct hash_entry **table = htable->table;
487 for (i = 0; i < htable->table_length; i++) {
490 while (cursor != NULL) {
492 cursor = cursor->next;
495 freekey((void *)(tmp->key));
497 kfree((void *)(tmp->value));
502 for (i = 0; i < htable->table_length; i++) {
505 while (cursor != NULL) {
506 struct hash_entry * tmp;
509 cursor = cursor->next;
512 freekey((void *)(tmp->key));
519 kfree(htable->table);