drivers/xen/sfc_netutil/accel_cuckoo_hash.c

   1 /****************************************************************************
   2  * Solarflare driver for Xen network acceleration
   3  *
   4  * Copyright 2006-2008: Solarflare Communications Inc,
   5  *                      9501 Jeronimo Road, Suite 250,
   6  *                      Irvine, CA 92618, USA
   7  *
   8  * Maintained by Solarflare Communications <linux-xen-drivers@solarflare.com>
   9  *
  10  * This program is free software; you can redistribute it and/or modify it
  11  * under the terms of the GNU General Public License version 2 as published
  12  * by the Free Software Foundation, incorporated herein by reference.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  22  ****************************************************************************
  23  */
  24
  25 #include <linux/types.h> /* needed for linux/random.h */
  26 #include <linux/random.h>
  27 #include <linux/slab.h>
  28
  29 #include "accel_cuckoo_hash.h"
  30 #include "accel_util.h"
  31
  32 static inline int cuckoo_hash_key_compare(cuckoo_hash_table *hashtab,
  33                                           cuckoo_hash_key *key1,
  34                                           cuckoo_hash_key *key2)
  35 {
  36         return !memcmp(key1, key2, hashtab->key_length);
  37 }
  38
  39
  40 static inline void cuckoo_hash_key_set(cuckoo_hash_key *key1,
  41                                        cuckoo_hash_key *key2)
  42 {
  43         *key1 = *key2;
  44 }
  45
  46
  47 /*
  48  * Sets hash function parameters.  Chooses "a" to be odd, 0 < a < 2^w
  49  * where w is the length of the key
  50  */
  51 static void set_hash_parameters(cuckoo_hash_table *hashtab)
  52 {
  53  again:
  54         hashtab->a0 = hashtab->a1 = 0;
  55
  56         /* Make sure random */
  57         get_random_bytes(&hashtab->a0, hashtab->key_length);
  58         get_random_bytes(&hashtab->a1, hashtab->key_length);
  59
  60         /* Make sure odd */
  61         hashtab->a0 |= 1;
  62         hashtab->a1 |= 1;
  63
  64         /* Being different is good */
  65         if (hashtab->a0 != hashtab->a1)
  66                 return;
  67
  68         goto again;
  69 }
  70
  71 int cuckoo_hash_init(cuckoo_hash_table *hashtab, unsigned length_bits,
  72                      unsigned key_length)
  73 {
  74         char *table_mem;
  75         unsigned length = 1 << length_bits;
  76
  77         BUG_ON(length_bits >= sizeof(unsigned) * 8);
  78         BUG_ON(key_length > sizeof(cuckoo_hash_key));
  79
  80         table_mem = kzalloc(sizeof(cuckoo_hash_entry) * 2 * length, GFP_KERNEL);
  81
  82         if (table_mem == NULL)
  83                 return -ENOMEM;
  84
  85         hashtab->length = length;
  86         hashtab->length_bits = length_bits;
  87         hashtab->key_length = key_length;
  88         hashtab->entries = 0;
  89
  90         hashtab->table0 = (cuckoo_hash_entry *)table_mem;
  91         hashtab->table1 = (cuckoo_hash_entry *)
  92                 (table_mem + length * sizeof(cuckoo_hash_entry));
  93
  94         set_hash_parameters(hashtab);
  95
  96         return 0;
  97 }
  98 EXPORT_SYMBOL_GPL(cuckoo_hash_init);
  99
 100 void cuckoo_hash_destroy(cuckoo_hash_table *hashtab)
 101 {
 102         if (hashtab->table0 != NULL)
 103                 kfree(hashtab->table0);
 104 }
 105
 106 EXPORT_SYMBOL_GPL(cuckoo_hash_destroy);
 107
 108 /*
 109  * This computes sizeof(cuckoo_hash) bits of hash, not all will be
 110  * necessarily used, but the hash function throws away any that
 111  * aren't
 112  */
 113 static inline void cuckoo_compute_hash_helper(cuckoo_hash_table *hashtab,
 114                                               cuckoo_hash_key *a,
 115                                               cuckoo_hash_key *x,
 116                                               cuckoo_hash *result)
 117 {
 118         u64 multiply_result = 0, a_temp, x_temp;
 119         u32 carry = 0;
 120         u32 *a_words;
 121         u32 *x_words;
 122         int i;
 123
 124         /*
 125          * As the mod and div operations in the function effectively
 126          * reduce and shift the bits of the product down to just the
 127          * third word, we need only compute that and return it as a
 128          * result.
 129          *
 130          * Do enough long multiplication to get the word we need
 131          */
 132
 133         /* This assumes things about the sizes of the key and hash */
 134         BUG_ON(hashtab->key_length % sizeof(u32) != 0);
 135         BUG_ON(sizeof(cuckoo_hash) != sizeof(u32));
 136
 137         a_words = (u32 *)a;
 138         x_words = (u32 *)x;
 139
 140         for (i = 0; i < hashtab->key_length / sizeof(u32); i++) {
 141                 a_temp = a_words[i];
 142                 x_temp = x_words[i];
 143
 144                 multiply_result = (a_temp * x_temp) + carry;
 145                 carry = (multiply_result >> 32) & 0xffffffff;
 146         }
 147
 148         *result = multiply_result & 0xffffffff;
 149 }
 150
 151
 152 /*
 153  * Want to implement (ax mod 2^w) div 2^(w-q) for odd a, 0 < a < 2^w;
 154  * w is the length of the key, q is the length of the hash, I think.
 155  * See http://www.it-c.dk/people/pagh/papers/cuckoo-jour.pdf
 156  */
 157 static cuckoo_hash cuckoo_compute_hash(cuckoo_hash_table *hashtab,
 158                                        cuckoo_hash_key *key,
 159                                        cuckoo_hash_key *a)
 160 {
 161         unsigned q = hashtab->length_bits;
 162         unsigned shift = 32 - q;
 163         unsigned mask = ((1 << q) - 1) << shift;
 164         cuckoo_hash hash;
 165
 166         cuckoo_compute_hash_helper(hashtab, a, key, &hash);
 167
 168         /*
 169          * Take the top few bits to get the right length for this
 170          * hash table
 171          */
 172         hash = (hash & mask) >> shift;
 173
 174         BUG_ON(hash >= hashtab->length);
 175
 176         return hash;
 177 }
 178
 179
 180 static int cuckoo_hash_lookup0(cuckoo_hash_table *hashtab,
 181                                cuckoo_hash_key *key,
 182                                cuckoo_hash_value *value)
 183 {
 184         cuckoo_hash hash = cuckoo_compute_hash(hashtab, key, &hashtab->a0);
 185
 186         if ((hashtab->table0[hash].state == CUCKOO_HASH_STATE_OCCUPIED)
 187             && cuckoo_hash_key_compare(hashtab, &(hashtab->table0[hash].key),
 188                                        key)) {
 189                 *value = hashtab->table0[hash].value;
 190                 return 1;
 191         }
 192
 193         return 0;
 194 }
 195
 196 static int cuckoo_hash_lookup1(cuckoo_hash_table *hashtab,
 197                                cuckoo_hash_key *key,
 198                                cuckoo_hash_value *value)
 199 {
 200         cuckoo_hash hash = cuckoo_compute_hash(hashtab, key, &hashtab->a1);
 201
 202         if ((hashtab->table1[hash].state == CUCKOO_HASH_STATE_OCCUPIED)
 203             && cuckoo_hash_key_compare(hashtab, &(hashtab->table1[hash].key),
 204                                        key)) {
 205                 *value = hashtab->table1[hash].value;
 206                 return 1;
 207         }
 208
 209         return 0;
 210 }
 211
 212
 213 int cuckoo_hash_lookup(cuckoo_hash_table *hashtab, cuckoo_hash_key *key,
 214                        cuckoo_hash_value *value)
 215 {
 216         return cuckoo_hash_lookup0(hashtab, key, value)
 217                 || cuckoo_hash_lookup1(hashtab, key, value);
 218 }
 219 EXPORT_SYMBOL_GPL(cuckoo_hash_lookup);
 220
 221
 222 /* Transfer any active entries from "old_table" into hashtab */
 223 static int cuckoo_hash_transfer_entries(cuckoo_hash_table *hashtab,
 224                                         cuckoo_hash_entry *old_table,
 225                                         unsigned capacity)
 226 {
 227         int i, rc;
 228         cuckoo_hash_entry *entry;
 229
 230         hashtab->entries = 0;
 231
 232         for (i = 0; i < capacity; i++) {
 233                 entry = &old_table[i];
 234                 if (entry->state == CUCKOO_HASH_STATE_OCCUPIED) {
 235                         rc = cuckoo_hash_add(hashtab, &(entry->key),
 236                                              entry->value, 0);
 237                         if (rc != 0) {
 238                                 return rc;
 239                         }
 240                 }
 241         }
 242
 243         return 0;
 244 }
 245
 246
 247 int cuckoo_hash_rehash(cuckoo_hash_table *hashtab)
 248 {
 249         cuckoo_hash_entry *new_table;
 250         cuckoo_hash_table old_hashtab;
 251         int resize = 0, rc, rehash_count;
 252
 253         /*
 254          * Store old tables so we can access the existing values and
 255          * copy across
 256          */
 257         memcpy(&old_hashtab, hashtab, sizeof(cuckoo_hash_table));
 258
 259         /* resize if hashtable is more than half full */
 260         if (old_hashtab.entries > old_hashtab.length &&
 261             old_hashtab.length_bits < 32)
 262                 resize = 1;
 263
 264  resize:
 265         if (resize) {
 266                 new_table = kmalloc(sizeof(cuckoo_hash_entry) * 4 * hashtab->length,
 267                                     GFP_ATOMIC);
 268                 if (new_table == NULL) {
 269                         rc = -ENOMEM;
 270                         goto err;
 271                 }
 272
 273                 hashtab->length = 2 * hashtab->length;
 274                 hashtab->length_bits++;
 275         } else {
 276                 new_table = kmalloc(sizeof(cuckoo_hash_entry) * 2 * hashtab->length,
 277                                     GFP_ATOMIC);
 278                 if (new_table == NULL) {
 279                         rc = -ENOMEM;
 280                         goto err;
 281                 }
 282         }
 283
 284         /*
 285          * Point hashtab to new memory region so we can try to
 286          * construct new table
 287          */
 288         hashtab->table0 = new_table;
 289         hashtab->table1 = (cuckoo_hash_entry *)
 290                 ((char *)new_table + hashtab->length * sizeof(cuckoo_hash_entry));
 291
 292         rehash_count = 0;
 293
 294  again:
 295         /* Zero the new tables */
 296         memset(new_table, 0, hashtab->length * 2 * sizeof(cuckoo_hash_entry));
 297
 298         /* Choose new parameters for the hash functions */
 299         set_hash_parameters(hashtab);
 300
 301         /*
 302          * Multiply old_table_length by 2 as the length refers to each
 303          * table, and there are two of them.  This assumes that they
 304          * are arranged sequentially in memory, so assert it
 305          */
 306         BUG_ON(((char *)old_hashtab.table1) !=
 307                ((char *)old_hashtab.table0 + old_hashtab.length
 308                 * sizeof(cuckoo_hash_entry)));
 309         rc = cuckoo_hash_transfer_entries(hashtab, old_hashtab.table0,
 310                                           old_hashtab.length * 2);
 311         if (rc < 0) {
 312                 /* Problem */
 313                 if (rc == -ENOSPC) {
 314                         ++rehash_count;
 315                         if (rehash_count < CUCKOO_HASH_MAX_LOOP) {
 316                                 /*
 317                                  * Wanted to rehash, but rather than
 318                                  * recurse we can just do it here
 319                                  */
 320                                 goto again;
 321                         } else {
 322                                 /*
 323                                  * Didn't manage to rehash, so let's
 324                                  * go up a size (if we haven't already
 325                                  * and there's space)
 326                                  */
 327                                 if (!resize && hashtab->length_bits < 32) {
 328                                         resize = 1;
 329                                         kfree(new_table);
 330                                         goto resize;
 331                                 }
 332                                 else
 333                                         goto err;
 334                         }
 335                 }
 336                 else
 337                         goto err;
 338         }
 339
 340         /* Success, I think.  Free up the old table */
 341         kfree(old_hashtab.table0);
 342
 343         /* We should have put all the entries from old table in the new one */
 344         BUG_ON(hashtab->entries != old_hashtab.entries);
 345
 346         return 0;
 347  err:
 348         EPRINTK("%s: Rehash failed, giving up\n", __FUNCTION__);
 349         /* Some other error, give up, at least restore table to how it was */
 350         memcpy(hashtab, &old_hashtab, sizeof(cuckoo_hash_table));
 351         if (new_table)
 352                 kfree(new_table);
 353         return rc;
 354 }
 355 EXPORT_SYMBOL_GPL(cuckoo_hash_rehash);
 356
 357
 358 static int
 359 cuckoo_hash_insert_or_displace(cuckoo_hash_entry *table, unsigned hash,
 360                                cuckoo_hash_key *key,
 361                                cuckoo_hash_value value,
 362                                cuckoo_hash_key *displaced_key,
 363                                cuckoo_hash_value *displaced_value)
 364 {
 365         if (table[hash].state == CUCKOO_HASH_STATE_VACANT) {
 366                 cuckoo_hash_key_set(&(table[hash].key), key);
 367                 table[hash].value = value;
 368                 table[hash].state = CUCKOO_HASH_STATE_OCCUPIED;
 369
 370                 return 1;
 371         } else {
 372                 cuckoo_hash_key_set(displaced_key, &(table[hash].key));
 373                 *displaced_value = table[hash].value;
 374                 cuckoo_hash_key_set(&(table[hash].key), key);
 375                 table[hash].value = value;
 376
 377                 return 0;
 378         }
 379 }
 380
 381
 382 int cuckoo_hash_add(cuckoo_hash_table *hashtab, cuckoo_hash_key *key,
 383                      cuckoo_hash_value value, int can_rehash)
 384 {
 385         cuckoo_hash hash0, hash1;
 386         int i, rc;
 387         cuckoo_hash_key key1, key2;
 388
 389         cuckoo_hash_key_set(&key1, key);
 390
 391  again:
 392         i = 0;
 393         do {
 394                 hash0 = cuckoo_compute_hash(hashtab, &key1, &hashtab->a0);
 395                 if (cuckoo_hash_insert_or_displace(hashtab->table0, hash0,
 396                                                    &key1, value, &key2,
 397                                                    &value)) {
 398                         /* Success */
 399                         hashtab->entries++;
 400                         return 0;
 401                 }
 402
 403                 hash1 = cuckoo_compute_hash(hashtab, &key2, &hashtab->a1);
 404                 if (cuckoo_hash_insert_or_displace(hashtab->table1, hash1,
 405                                                    &key2, value, &key1,
 406                                                    &value)) {
 407                         /* Success */
 408                         hashtab->entries++;
 409                         return 0;
 410                 }
 411         } while (++i < CUCKOO_HASH_MAX_LOOP);
 412
 413         if (can_rehash) {
 414                 if ((rc = cuckoo_hash_rehash(hashtab)) < 0) {
 415                         /*
 416                          * Give up - this will drop whichever
 417                          * key/value pair we have currently displaced
 418                          * on the floor
 419                          */
 420                         return rc;
 421                 }
 422                 goto again;
 423         }
 424
 425         EPRINTK("%s: failed hash add\n", __FUNCTION__);
 426         /*
 427          * Couldn't do it - bad as we've now removed some random thing
 428          * from the table, and will just drop it on the floor.  Better
 429          * would be to somehow revert the table to the state it was in
 430          * at the start
 431          */
 432         return -ENOSPC;
 433 }
 434 EXPORT_SYMBOL_GPL(cuckoo_hash_add);
 435
 436
 437 int cuckoo_hash_add_check(cuckoo_hash_table *hashtab,
 438                           cuckoo_hash_key *key, cuckoo_hash_value value,
 439                           int can_rehash)
 440 {
 441         int stored_value;
 442
 443         if (cuckoo_hash_lookup(hashtab, key, &stored_value))
 444                 return -EBUSY;
 445
 446         return cuckoo_hash_add(hashtab, key, value, can_rehash);
 447 }
 448 EXPORT_SYMBOL_GPL(cuckoo_hash_add_check);
 449
 450
 451 int cuckoo_hash_remove(cuckoo_hash_table *hashtab, cuckoo_hash_key *key)
 452 {
 453         cuckoo_hash hash;
 454
 455         hash = cuckoo_compute_hash(hashtab, key, &hashtab->a0);
 456         if ((hashtab->table0[hash].state == CUCKOO_HASH_STATE_OCCUPIED) &&
 457             cuckoo_hash_key_compare(hashtab, &(hashtab->table0[hash].key),
 458                                     key)) {
 459                 hashtab->table0[hash].state = CUCKOO_HASH_STATE_VACANT;
 460                 hashtab->entries--;
 461                 return 0;
 462         }
 463
 464         hash = cuckoo_compute_hash(hashtab, key, &hashtab->a1);
 465         if ((hashtab->table1[hash].state == CUCKOO_HASH_STATE_OCCUPIED) &&
 466             cuckoo_hash_key_compare(hashtab, &(hashtab->table1[hash].key),
 467                                     key)) {
 468                 hashtab->table1[hash].state = CUCKOO_HASH_STATE_VACANT;
 469                 hashtab->entries--;
 470                 return 0;
 471         }
 472
 473         return -EINVAL;
 474 }
 475 EXPORT_SYMBOL_GPL(cuckoo_hash_remove);
 476
 477
 478 int cuckoo_hash_update(cuckoo_hash_table *hashtab, cuckoo_hash_key *key,
 479                        cuckoo_hash_value value)
 480 {
 481         cuckoo_hash hash;
 482
 483         hash = cuckoo_compute_hash(hashtab, key, &hashtab->a0);
 484         if ((hashtab->table0[hash].state == CUCKOO_HASH_STATE_OCCUPIED) &&
 485             cuckoo_hash_key_compare(hashtab, &(hashtab->table0[hash].key),
 486                                     key)) {
 487                 hashtab->table0[hash].value = value;
 488                 return 0;
 489         }
 490
 491         hash = cuckoo_compute_hash(hashtab, key, &hashtab->a1);
 492         if ((hashtab->table1[hash].state == CUCKOO_HASH_STATE_OCCUPIED) &&
 493             cuckoo_hash_key_compare(hashtab, &(hashtab->table1[hash].key),
 494                                     key)) {
 495                 hashtab->table1[hash].value = value;
 496                 return 0;
 497         }
 498
 499         return -EINVAL;
 500 }
 501 EXPORT_SYMBOL_GPL(cuckoo_hash_update);
 502
 503
 504 void cuckoo_hash_iterate_reset(cuckoo_hash_table *hashtab)
 505 {
 506         hashtab->iterate_index = 0;
 507 }
 508 EXPORT_SYMBOL_GPL(cuckoo_hash_iterate_reset);
 509
 510
 511 int cuckoo_hash_iterate(cuckoo_hash_table *hashtab,
 512                         cuckoo_hash_key *key, cuckoo_hash_value *value)
 513 {
 514         unsigned index;
 515
 516         while (hashtab->iterate_index < hashtab->length) {
 517                 index = hashtab->iterate_index;
 518                 ++hashtab->iterate_index;
 519                 if (hashtab->table0[index].state == CUCKOO_HASH_STATE_OCCUPIED) {
 520                         *key = hashtab->table0[index].key;
 521                         *value = hashtab->table0[index].value;
 522                         return 0;
 523                 }
 524         }
 525
 526         while (hashtab->iterate_index >= hashtab->length &&
 527                hashtab->iterate_index < hashtab->length * 2) {
 528                 index = hashtab->iterate_index - hashtab->length;
 529                 ++hashtab->iterate_index;
 530                 if (hashtab->table1[index].state == CUCKOO_HASH_STATE_OCCUPIED) {
 531                         *key = hashtab->table1[index].key;
 532                         *value = hashtab->table1[index].value;
 533                         return 0;
 534                 }
 535         }
 536
 537         return -ENOSPC;
 538 }
 539 EXPORT_SYMBOL_GPL(cuckoo_hash_iterate);
 540
 541
 542 #if 0
 543 void cuckoo_hash_valid(cuckoo_hash_table *hashtab)
 544 {
 545         int i, entry_count = 0;
 546
 547         for (i=0; i < hashtab->length; i++) {
 548                 EPRINTK_ON(hashtab->table0[i].state != CUCKOO_HASH_STATE_VACANT &&
 549                            hashtab->table0[i].state != CUCKOO_HASH_STATE_OCCUPIED);
 550                 if (hashtab->table0[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 551                         entry_count++;
 552                 EPRINTK_ON(hashtab->table1[i].state != CUCKOO_HASH_STATE_VACANT &&
 553                            hashtab->table1[i].state != CUCKOO_HASH_STATE_OCCUPIED);
 554                 if (hashtab->table1[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 555                         entry_count++;
 556         }
 557
 558         if (entry_count != hashtab->entries) {
 559                 EPRINTK("%s: bad count\n", __FUNCTION__);
 560                 cuckoo_hash_dump(hashtab);
 561                 return;
 562         }
 563
 564         for (i=0; i< hashtab->length; i++) {
 565                 if (hashtab->table0[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 566                         if (i != cuckoo_compute_hash(hashtab,
 567                                                      &hashtab->table0[i].key,
 568                                                      &hashtab->a0)) {
 569                                 EPRINTK("%s: Bad key table 0 index %d\n",
 570                                         __FUNCTION__, i);
 571                                 cuckoo_hash_dump(hashtab);
 572                                 return;
 573                         }
 574                 if (hashtab->table1[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 575                         if (i != cuckoo_compute_hash(hashtab,
 576                                                      &hashtab->table1[i].key,
 577                                                      &hashtab->a1)) {
 578                                 EPRINTK("%s: Bad key table 1 index %d\n",
 579                                         __FUNCTION__, i);
 580                                 cuckoo_hash_dump(hashtab);
 581                                 return;
 582                         }
 583         }
 584
 585 }
 586 EXPORT_SYMBOL_GPL(cuckoo_hash_valid);
 587
 588
 589 void cuckoo_hash_dump(cuckoo_hash_table *hashtab)
 590 {
 591         int i, entry_count;
 592
 593         entry_count = 0;
 594         for (i=0; i < hashtab->length; i++) {
 595                 EPRINTK_ON(hashtab->table0[i].state != CUCKOO_HASH_STATE_VACANT &&
 596                            hashtab->table0[i].state != CUCKOO_HASH_STATE_OCCUPIED);
 597                 if (hashtab->table0[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 598                         entry_count++;
 599                 EPRINTK_ON(hashtab->table1[i].state != CUCKOO_HASH_STATE_VACANT &&
 600                            hashtab->table1[i].state != CUCKOO_HASH_STATE_OCCUPIED);
 601                 if (hashtab->table1[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 602                         entry_count++;
 603         }
 604
 605         EPRINTK("======================\n");
 606         EPRINTK("Cuckoo hash table dump\n");
 607         EPRINTK("======================\n");
 608         EPRINTK("length: %d; length_bits: %d; key_length: %d\n", hashtab->length,
 609                 hashtab->length_bits, hashtab->key_length);
 610         EPRINTK("Recorded entries: %d\n", hashtab->entries);
 611         EPRINTK("Counted entries: %d\n", entry_count);
 612         EPRINTK("a0: %llx; a1: %llx\n", hashtab->a0, hashtab->a1);
 613         EPRINTK("-----------------------------------------\n");
 614         EPRINTK("Index  Occupied  Key  Value Index0 Index1\n");
 615         EPRINTK("-----------------------------------------\n");
 616         for (i=0; i< hashtab->length; i++) {
 617                 if (hashtab->table0[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 618                 EPRINTK("%d %d %llx %d %d %d\n", i,
 619                         hashtab->table0[i].state == CUCKOO_HASH_STATE_OCCUPIED,
 620                         hashtab->table0[i].key, hashtab->table0[i].value,
 621                         cuckoo_compute_hash(hashtab, &hashtab->table0[i].key,
 622                                             &hashtab->a0),
 623                         cuckoo_compute_hash(hashtab, &hashtab->table0[i].key,
 624                                             &hashtab->a1));
 625                 else
 626                 EPRINTK("%d %d - - - -\n", i,
 627                         hashtab->table0[i].state == CUCKOO_HASH_STATE_OCCUPIED);
 628
 629         }
 630         EPRINTK("-----------------------------------------\n");
 631         EPRINTK("Index  Occupied  Key  Value Index0 Index1\n");
 632         EPRINTK("-----------------------------------------\n");
 633         for (i=0; i< hashtab->length; i++) {
 634                 if (hashtab->table1[i].state == CUCKOO_HASH_STATE_OCCUPIED)
 635                 EPRINTK("%d %d %llx %d %d %d\n", i,
 636                         hashtab->table1[i].state == CUCKOO_HASH_STATE_OCCUPIED,
 637                         hashtab->table1[i].key, hashtab->table1[i].value,
 638                         cuckoo_compute_hash(hashtab, &hashtab->table1[i].key,
 639                                             &hashtab->a0),
 640                         cuckoo_compute_hash(hashtab, &hashtab->table1[i].key,
 641                                             &hashtab->a1));
 642                 else
 643                 EPRINTK("%d %d - - - -\n", i,
 644                         hashtab->table1[i].state == CUCKOO_HASH_STATE_OCCUPIED);
 645         }
 646         EPRINTK("======================\n");
 647 }
 648 EXPORT_SYMBOL_GPL(cuckoo_hash_dump);
 649 #endif