datapath/table_t.c

   1 /*
   2  * Distributed under the terms of the GNU GPL version 2.
   3  * Copyright (c) 2007, 2008 The Board of Trustees of The Leland
   4  * Stanford Junior University
   5  */
   6
   7 #include <linux/module.h>
   8 #include <linux/slab.h>
   9 #include <linux/vmalloc.h>
  10 #include <linux/random.h>
  11 #include <linux/rcupdate.h>
  12
  13 #include "flow.h"
  14 #include "table.h"
  15 #include "openflow.h"
  16 #include "unit.h"
  17
  18 static const char *
  19 table_name(struct sw_table *table)
  20 {
  21         struct sw_table_stats stats;
  22         table->stats(table, &stats);
  23         return stats.name;
  24 }
  25
  26 static unsigned long int
  27 table_max_flows(struct sw_table *table)
  28 {
  29         struct sw_table_stats stats;
  30         table->stats(table, &stats);
  31         return stats.max_flows;
  32 }
  33
  34 static struct sw_flow *flow_zalloc(int n_actions, gfp_t flags)
  35 {
  36         struct sw_flow *flow = flow_alloc(n_actions, flags);
  37         if (flow) {
  38                 struct ofp_action *actions = flow->actions;
  39                 memset(flow, 0, sizeof *flow);
  40                 flow->actions = actions;
  41         }
  42         return flow;
  43 }
  44
  45 static void
  46 simple_insert_delete(struct sw_table *swt, uint32_t wildcards)
  47 {
  48         struct sw_flow *a_flow = flow_zalloc(0, GFP_KERNEL);
  49         struct sw_flow *b_flow = flow_zalloc(0, GFP_KERNEL);
  50         struct sw_flow *found;
  51
  52         if (!swt) {
  53                 unit_fail("table creation failed");
  54                 return;
  55         }
  56
  57         printk("simple_insert_delete: testing %s table\n", table_name(swt));
  58         *((uint32_t*)a_flow->key.dl_src) = 0x12345678;
  59         *((uint32_t*)b_flow->key.dl_src) = 0x87654321;
  60
  61         a_flow->key.nw_src      = 0xdeadbeef;
  62         b_flow->key.nw_src      = 0x001dd0d0;
  63
  64         a_flow->key.wildcards = wildcards;
  65         b_flow->key.wildcards = wildcards;
  66
  67         if (!(swt->insert(swt, a_flow)))
  68                 unit_fail("insert failed");
  69         found = swt->lookup(swt, &a_flow->key);
  70         if(found != a_flow)
  71                 unit_fail("%p != %p", found, a_flow);
  72         if (swt->lookup(swt, &b_flow->key))
  73                 unit_fail("lookup should not succeed (1)");
  74
  75         swt->delete(swt, &a_flow->key, 0, 0);
  76         if (swt->lookup(swt, &a_flow->key))
  77                 unit_fail("lookup should not succeed (3)");
  78
  79         flow_free(b_flow);
  80         swt->destroy(swt);
  81 }
  82
  83 static void
  84 multiple_insert_destroy(struct sw_table *swt, int inserts, uint32_t wildcards,
  85                         int min_collisions, int max_collisions)
  86 {
  87         int i;
  88         int col = 0;
  89
  90         if (!swt) {
  91                 unit_fail("table creation failed");
  92                 return;
  93         }
  94
  95         printk("inserting %d flows into %s table with max %lu flows: ",
  96                                 inserts, table_name(swt), table_max_flows(swt));
  97         for(i = 0; i < inserts; ++i){
  98                 struct sw_flow *a_flow = flow_zalloc(0, GFP_KERNEL);
  99                 *((uint32_t*)&(a_flow->key.dl_src[0])) = random32();
 100                 a_flow->key.nw_src    = random32();
 101                 a_flow->key.wildcards = wildcards;
 102
 103                 if(!swt->insert(swt, a_flow)) {
 104                         col++;
 105                         flow_free(a_flow);
 106                 }
 107         }
 108         printk("%d failures\n", col);
 109         if (min_collisions <= col && col <= max_collisions)
 110                 printk("\tmin = %d <= %d <= %d = max, OK.\n",
 111                                         min_collisions, col, max_collisions);
 112         else {
 113                 if (col < min_collisions)
 114                         unit_fail("too few collisions (%d < %d)",
 115                                   col, min_collisions);
 116                 else if (col > max_collisions)
 117                         unit_fail("too many collisions (%d > %d)",
 118                                   col, max_collisions);
 119                 printk("(This is statistically possible "
 120                                         "but should not occur often.)\n");
 121         }
 122
 123         swt->destroy(swt);
 124 }
 125
 126 static void
 127 set_random_key(struct sw_flow_key *key, uint32_t wildcards)
 128 {
 129         key->nw_src = random32();
 130         key->nw_dst = random32();
 131         key->in_port = (uint16_t) random32();
 132         key->dl_vlan = (uint16_t) random32();
 133         key->dl_type = (uint16_t) random32();
 134         key->tp_src = (uint16_t) random32();
 135         key->tp_dst = (uint16_t) random32();
 136         key->wildcards = wildcards;
 137         *((uint32_t*)key->dl_src) = random32();
 138         *(((uint32_t*)key->dl_src) + 1) = random32();
 139         *((uint32_t*)key->dl_dst) = random32();
 140         *(((uint32_t*)key->dl_dst) + 1) = random32();
 141         key->nw_proto = (uint8_t) random32();
 142 }
 143
 144 struct flow_key_entry {
 145         struct sw_flow_key key;
 146         struct list_head node;
 147 };
 148
 149 /*
 150  * Allocates memory for 'n_keys' flow_key_entrys.  Initializes the allocated
 151  * keys with random values, setting their wildcard values to 'wildcards', and
 152  * places them all in a list.  Returns a pointer to a flow_key_entry that
 153  * serves solely as the list's head (its key has not been set).  If allocation
 154  * fails, returns NULL.  Returned pointer should be freed with vfree (which
 155  * frees the memory associated with the keys as well.)
 156  */
 157
 158 static struct flow_key_entry *
 159 allocate_random_keys(int n_keys, uint32_t wildcards)
 160 {
 161         struct flow_key_entry *entries, *pos;
 162         struct list_head *keys;
 163
 164         if (n_keys < 0)
 165                 return NULL;
 166
 167         entries = vmalloc((n_keys+1) * sizeof *entries);
 168         if (entries == NULL) {
 169                 unit_fail("cannot allocate memory for %u keys",
 170                                         n_keys);
 171                 return NULL;
 172         }
 173
 174         keys = &entries->node;
 175         INIT_LIST_HEAD(keys);
 176
 177         for(pos = entries+1; pos < (entries + n_keys + 1); pos++) {
 178                 set_random_key(&pos->key, wildcards);
 179                 list_add(&pos->node, keys);
 180         }
 181
 182         return entries;
 183 }
 184
 185 /*
 186  * Attempts to insert the first 'n_flows' flow keys in list 'keys' into table
 187  * 'swt', where 'keys' is a list of flow_key_entrys.  key_entrys that are
 188  * inserted into the table are removed from the 'keys' list and placed in
 189  * 'added' list.  Returns -1 if flow memory allocation fails, else returns the
 190  * number of flows that were actually inserted (some attempts might fail due to
 191  * collisions).
 192  */
 193
 194 static int
 195 insert_flows(struct sw_table *swt, struct list_head *keys, struct list_head *added, int n_flows)
 196 {
 197         struct flow_key_entry *pos, *next;
 198         int cnt;
 199
 200         cnt = 0;
 201
 202
 203         list_for_each_entry_safe (pos, next, keys, node) {
 204                 struct sw_flow *flow = flow_zalloc(0, GFP_KERNEL);
 205                 if (flow == NULL) {
 206                         unit_fail("Could only allocate %u flows", cnt);
 207                         return -1;
 208                 }
 209
 210                 flow->key = pos->key;
 211
 212                 if (!swt->insert(swt, flow)) {
 213                         flow_free(flow);
 214                         list_del(&pos->node);
 215                 } else {
 216                         list_del(&pos->node);
 217                         list_add(&pos->node, added);
 218                         cnt++;
 219                         if (n_flows != -1 && cnt == n_flows)
 220                                 break;
 221                 }
 222         }
 223
 224         return cnt;
 225 }
 226
 227 /*
 228  * Finds and returns the flow_key_entry in list 'keys' matching the passed in
 229  * flow's key.  If not found, returns NULL.
 230  */
 231
 232 static struct flow_key_entry *
 233 find_flow(struct list_head *keys, struct sw_flow *flow)
 234 {
 235         struct flow_key_entry *pos;
 236
 237         list_for_each_entry(pos, keys, node) {
 238                 if(!memcmp(&pos->key, &flow->key, sizeof(struct sw_flow_key)))
 239                         return pos;
 240         }
 241
 242         return NULL;
 243 }
 244
 245 /*
 246  * Checks that all flow_key_entrys in list 'keys' return successful lookups on
 247  * the table 'swt'.
 248  */
 249
 250 static int
 251 check_lookup(struct sw_table *swt, struct list_head *keys)
 252 {
 253         struct flow_key_entry *pos;
 254
 255         list_for_each_entry(pos, keys, node) {
 256                 if(swt->lookup(swt, &pos->key) == NULL)
 257                         return -1;
 258         }
 259
 260         return 0;
 261 }
 262
 263 /*
 264  * Checks that all flow_key_entrys in list 'keys' DO NOT return successful
 265  * lookups in the 'swt' table.
 266  */
 267
 268 static int
 269 check_no_lookup(struct sw_table *swt, struct list_head *keys)
 270 {
 271         struct flow_key_entry *pos;
 272
 273         list_for_each_entry(pos, keys, node) {
 274                 if(swt->lookup(swt, &pos->key) != NULL)
 275                         return -1;
 276         }
 277
 278         return 0;
 279 }
 280
 281
 282 struct check_iteration_state
 283 {
 284         int n_found;
 285         struct list_head *to_find;
 286         struct list_head *found;
 287 };
 288
 289 static int
 290 check_iteration_callback(struct sw_flow *flow, void *private)
 291 {
 292         struct check_iteration_state *s = private;
 293         struct flow_key_entry *entry;
 294
 295         entry = find_flow(s->to_find, flow);
 296         if (entry == NULL) {
 297                 unit_fail("UNKNOWN ITERATOR FLOW %p", flow);
 298                 rcu_read_unlock();
 299                 return 1;
 300         }
 301         s->n_found++;
 302         list_del(&entry->node);
 303         list_add(&entry->node, s->found);
 304         return 0;
 305 }
 306
 307 /*
 308  * Compares an iterator's view of the 'swt' table to the list of
 309  * flow_key_entrys in 'to_find'.  flow_key_entrys that are matched are removed
 310  * from the 'to_find' list and placed in the 'found' list.  Returns -1 if the
 311  * iterator cannot be initialized or it encounters a flow with a key not in
 312  * 'to_find'.  Else returns the number of flows found by the iterator
 313  * (i.e. there might still be flow keys in the 'to_find' list that were not
 314  * encountered by the iterator.  it is up to the caller to determine if that is
 315  * acceptable behavior)
 316  */
 317
 318 static int
 319 check_iteration(struct sw_table *swt, struct list_head *to_find, struct list_head *found)
 320 {
 321         struct sw_flow_key key;
 322         struct sw_table_position position;
 323         struct check_iteration_state state;
 324
 325         memset(&key, 0, sizeof key);
 326         key.wildcards = -1;
 327
 328         memset(&position, 0, sizeof position);
 329
 330         state.n_found = 0;
 331         state.to_find = to_find;
 332         state.found = found;
 333
 334         rcu_read_lock();
 335         swt->iterate(swt, &key, &position, check_iteration_callback, &state);
 336         rcu_read_unlock();
 337
 338         return state.n_found;
 339 }
 340
 341 /*
 342  * Deletes from table 'swt' keys from the list of flow_key_entrys 'keys'.
 343  * Removes flow_key_entrys of deleted flows from 'keys' and places them in the
 344  * 'deleted' list.  If 'del_all' == 1, all flows in 'keys' will be deleted,
 345  * else only every third key will be deleted.  Returns the number flows deleted
 346  * from the table.
 347  */
 348
 349 static int
 350 delete_flows(struct sw_table *swt, struct list_head *keys,
 351                  struct list_head *deleted, uint8_t del_all)
 352 {
 353         struct flow_key_entry *pos, *next;
 354         int i, n_del, total_del;
 355
 356         total_del = 0;
 357         i = 0;
 358
 359         list_for_each_entry_safe (pos, next, keys, node) {
 360                 if (del_all == 1 || i % 3 == 0) {
 361                         n_del = swt->delete(swt, &pos->key, 0, 0);
 362                         if (n_del > 1) {
 363                                 unit_fail("%d flows deleted for one entry", n_del);
 364                                 unit_fail("\tfuture 'errors' could just be product duplicate flow_key_entries");
 365                                 unit_fail("THIS IS VERY UNLIKELY...SHOULDN'T HAPPEN OFTEN");
 366                         }
 367                         total_del += n_del;
 368                         list_del(&pos->node);
 369                         list_add(&pos->node, deleted);
 370                 }
 371                 i++;
 372         }
 373
 374         return total_del;
 375 }
 376
 377 /*
 378  * Checks that both iteration and lookups are consistent with the caller's view
 379  * of the table.  In particular, checks that all keys in flow_key_entry list
 380  * 'deleted' do not show up in lookup or iteration, and keys in flow_key_entry
 381  * list 'added' do show up.  'tmp' should be an empty list that can be used for
 382  * iteration.  References to list_head pointers are needed for 'added' and 'tmp'
 383  * because iteration will cause the list_heads to change.  Function thus
 384  * switches 'added' to point to the list of added keys after the iteration.
 385  */
 386
 387 static int
 388 check_lookup_and_iter(struct sw_table *swt, struct list_head *deleted,
 389                           struct list_head **added, struct list_head **tmp)
 390 {
 391         struct list_head *tmp2;
 392         int ret;
 393
 394         if (check_no_lookup(swt, deleted) < 0) {
 395                 unit_fail("Uninserted flows returning lookup");
 396                 return -1;
 397         }
 398
 399         if (check_lookup(swt, *added) < 0) {
 400                 unit_fail("Inserted flows not returning lookup");
 401                 return -1;
 402         }
 403
 404         ret = check_iteration(swt, *added, *tmp);
 405
 406         tmp2 = *added;
 407         *added = *tmp;
 408         *tmp = tmp2;
 409
 410         if ((*tmp)->next != *tmp) {
 411                 unit_fail("WARNING: not all flows in 'added' found by iterator");
 412                 unit_fail("\tcould be a product of duplicate flow_key_entrys, though should be VERY rare.");
 413                 /* To avoid reoccurence */
 414                 (*tmp)->next = (*tmp)->prev = *tmp;
 415         }
 416
 417         return ret;
 418 }
 419
 420 /*
 421  * Verifies iteration and lookup after inserting 'n_flows', then after deleting
 422  * some flows, and once again after deleting all flows in table 'swt'.
 423  */
 424
 425 static int
 426 iterator_test(struct sw_table *swt, int n_flows, uint32_t wildcards)
 427 {
 428         struct flow_key_entry *allocated, h1, h2;
 429         struct list_head *added, *deleted, *tmp;
 430         int ret, n_del, success;
 431
 432         INIT_LIST_HEAD(&h1.node);
 433         INIT_LIST_HEAD(&h2.node);
 434
 435         success = -1;
 436
 437         allocated = allocate_random_keys(n_flows, wildcards);
 438         if(allocated == NULL)
 439                 return success;
 440
 441         deleted = &allocated->node;
 442         added = &h1.node;
 443         tmp = &h2.node;
 444
 445         ret = insert_flows(swt, deleted, added, -1);
 446         if (ret < 0)
 447                 goto iterator_test_destr;
 448
 449         n_flows = ret;
 450
 451         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 452         if (ret < 0) {
 453                 unit_fail("Bad lookup after insertion");
 454                 goto iterator_test_destr;
 455         } else if (ret != n_flows) {
 456                 unit_fail("Iterator only found %d of %d flows",
 457                           ret, n_flows);
 458                 goto iterator_test_destr;
 459         }
 460
 461         n_del = delete_flows(swt, added, deleted, 0);
 462
 463         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 464         if (ret < 0) {
 465                 unit_fail("Bad lookup after some deletion");
 466                 goto iterator_test_destr;
 467         } else if (ret + n_del != n_flows) {
 468                 unit_fail("iterator after deletion inconsistent");
 469                 unit_fail("\tn_del = %d, n_found = %d, n_flows = %d",
 470                           n_del, ret, n_flows);
 471                 goto iterator_test_destr;
 472         }
 473
 474         n_flows -= n_del;
 475
 476         n_del = delete_flows(swt, added, deleted, 1);
 477         if (n_del != n_flows) {
 478                 unit_fail("Not all flows deleted - only %d of %d",
 479                           n_del, n_flows);
 480                 goto iterator_test_destr;
 481         }
 482
 483         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 484         if (ret < 0) {
 485                 unit_fail("Bad lookup after all deletion");
 486                 goto iterator_test_destr;
 487         } else if (ret != 0) {
 488                 unit_fail("Empty table iterator failed.  %d flows found",
 489                           ret);
 490                 goto iterator_test_destr;
 491         }
 492
 493         success = 0;
 494
 495 iterator_test_destr:
 496         allocated->key.wildcards = OFPFW_ALL;
 497         swt->delete(swt, &allocated->key, 0, 0);
 498         vfree(allocated);
 499         return success;
 500 }
 501
 502
 503 /*
 504  * Checks lookup and iteration consistency after adding one flow, adding the
 505  * flow again, and then deleting the flow from table 'swt'.
 506  */
 507
 508 static int
 509 add_test(struct sw_table *swt, uint32_t wildcards)
 510 {
 511         struct flow_key_entry *allocated, h1, h2;
 512         struct list_head *added, *deleted, *tmp, *tmp2;
 513         int ret, success = -1;
 514
 515         INIT_LIST_HEAD(&h1.node);
 516         INIT_LIST_HEAD(&h2.node);
 517
 518         allocated = allocate_random_keys(2, wildcards);
 519         if (allocated == NULL)
 520                 return success;
 521
 522         deleted = &allocated->node;
 523         added = &h1.node;
 524         tmp = &h2.node;
 525
 526         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 527         if (ret < 0) {
 528                 unit_fail("Bad lookup before table modification");
 529                 goto add_test_destr;
 530         } else if (ret != 0) {
 531                 unit_fail("Iterator on empty table found %d flows",
 532                           ret);
 533                 goto add_test_destr;
 534         }
 535
 536         if (insert_flows(swt, deleted, added, 1) != 1) {
 537                 unit_fail("Cannot add one flow to table");
 538                 goto add_test_destr;
 539         }
 540
 541         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 542         if (ret < 0) {
 543                 unit_fail("Bad lookup after single add");
 544                 goto add_test_destr;
 545         } else if (ret != 1) {
 546                 unit_fail("Iterator on single add found %d flows",
 547                           ret);
 548                 goto add_test_destr;
 549         }
 550
 551         /* Re-adding flow */
 552         if (insert_flows(swt, added, tmp, 1) != 1) {
 553                 unit_fail("Cannot insert same flow twice");
 554                 goto add_test_destr;
 555         }
 556
 557         tmp2 = added;
 558         added = tmp;
 559         tmp = tmp2;
 560
 561         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 562         if (ret < 0) {
 563                 unit_fail("Bad lookup after double add");
 564                 goto add_test_destr;
 565         } else if (ret != 1) {
 566                 unit_fail("Iterator on double add found %d flows",
 567                           ret);
 568                 goto add_test_destr;
 569         }
 570
 571         ret = delete_flows(swt, added, deleted, 1);
 572         if (ret != 1) {
 573                 unit_fail("Unexpected %d flows deleted", ret);
 574                 goto add_test_destr;
 575         }
 576
 577         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 578         if (ret < 0) {
 579                 unit_fail("Bad lookup after delete.");
 580                 goto add_test_destr;
 581         } else if (ret != 0) {
 582                 unit_fail("unexpected %d flows found delete", ret);
 583                 goto add_test_destr;
 584         }
 585
 586         success = 0;
 587
 588 add_test_destr:
 589         allocated->key.wildcards = OFPFW_ALL;
 590         swt->delete(swt, &allocated->key, 0, 0);
 591         vfree(allocated);
 592         return success;
 593 }
 594
 595 /*
 596  * Checks lookup and iteration consistency after each deleting a non-existent
 597  * flow, adding and then deleting a flow, adding the flow again, and then
 598  * deleting the flow twice in table 'swt'.
 599  */
 600
 601 static int
 602 delete_test(struct sw_table *swt, uint32_t wildcards)
 603 {
 604         struct flow_key_entry *allocated, h1, h2;
 605         struct list_head *added, *deleted, *tmp, *tmp2;
 606         int i, ret, success = -1;
 607
 608         INIT_LIST_HEAD(&h1.node);
 609         INIT_LIST_HEAD(&h2.node);
 610
 611         allocated = allocate_random_keys(2, wildcards);
 612         if (allocated == NULL)
 613                 return success;
 614
 615         /* Not really added...*/
 616
 617         added = &allocated->node;
 618         deleted = &h1.node;
 619         tmp = &h2.node;
 620
 621         ret = delete_flows(swt, added, deleted, 1);
 622         if (ret != 0) {
 623                 unit_fail("Deleting non-existent keys from table returned unexpected value %d",
 624                           ret);
 625                         goto delete_test_destr;
 626         }
 627
 628         for (i = 0; i < 3; i++) {
 629                 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 630                 if (ret < 0) {
 631                         if (i == 0)
 632                                 unit_fail("Loop %d. Bad lookup before modification.", i);
 633                         else
 634                                 unit_fail("Loop %d. Bad lookup after delete.", i);
 635                         goto delete_test_destr;
 636                 } else if (ret != 0) {
 637                         if(i == 0)
 638                                 unit_fail("Loop %d. Unexpected %d flows found before modification",
 639                                           i, ret);
 640                         else
 641                                 unit_fail("Loop %d. Unexpected %d flows found after delete",
 642                                           i, ret);
 643                         goto delete_test_destr;
 644                 }
 645
 646                 if(i == 2)
 647                         break;
 648
 649                 if (insert_flows(swt, deleted, added, 1) != 1) {
 650                         unit_fail("loop %d: cannot add flow to table", i);
 651                         goto delete_test_destr;
 652                 }
 653
 654                 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 655                 if (ret < 0) {
 656                         unit_fail("loop %d: bad lookup after single add.", i);
 657                         goto delete_test_destr;
 658                 } else if (ret != 1) {
 659                         unit_fail("loop %d: unexpected %d flows found after single add",
 660                                   i, ret);
 661                         goto delete_test_destr;
 662                 }
 663
 664                 ret = delete_flows(swt, added, deleted, 1);
 665                 if (ret != 1) {
 666                         unit_fail("loop %d: deleting inserted key from table returned unexpected value %d",
 667                                                 i, ret);
 668                         goto delete_test_destr;
 669                 }
 670         }
 671
 672
 673         ret = delete_flows(swt, deleted, tmp, 1);
 674
 675         tmp2 = deleted;
 676         deleted = tmp2;
 677         tmp = tmp2;
 678
 679         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 680         if (ret < 0) {
 681                 unit_fail("Bad lookup after double delete.");
 682                 goto delete_test_destr;
 683         } else if (ret != 0) {
 684                 unit_fail("Unexpected %d flows found after double delete", ret);
 685                 goto delete_test_destr;
 686         }
 687
 688         success = 0;
 689
 690 delete_test_destr:
 691         allocated->key.wildcards = OFPFW_ALL;
 692         swt->delete(swt, &allocated->key, 0, 0);
 693         vfree(allocated);
 694         return success;
 695 }
 696
 697 /*
 698  * Randomly adds and deletes from a set of size 'n_flows', looping for 'i'
 699  * iterations.
 700  */
 701
 702 static int
 703 complex_add_delete_test(struct sw_table *swt, int n_flows, int i, uint32_t wildcards)
 704 {
 705         struct flow_key_entry *allocated, h1, h2;
 706         struct list_head *added, *deleted, *tmp;
 707         int cnt, ret, n_added, n_deleted, success = -1;
 708         uint8_t del_all;
 709
 710         INIT_LIST_HEAD(&h1.node);
 711         INIT_LIST_HEAD(&h2.node);
 712
 713         allocated = allocate_random_keys(n_flows, wildcards);
 714         if (allocated == NULL)
 715                 return success;
 716
 717         deleted = &allocated->node;
 718         added = &h1.node;
 719         tmp = &h2.node;
 720
 721         n_deleted = n_flows;
 722         n_added = 0;
 723
 724         for (;i > 0; i--) {
 725                 if (n_deleted != 0 && random32() % 2 == 0) {
 726                         cnt = random32() % n_deleted;
 727                         cnt = insert_flows(swt, deleted, added, cnt);
 728                         if (cnt < 0)
 729                                 goto complex_test_destr;
 730                         n_deleted -= cnt;
 731                         n_added += cnt;
 732                 } else {
 733                         if (random32() % 7 == 0)
 734                                 del_all = 1;
 735                         else
 736                                 del_all = 0;
 737                         cnt = delete_flows(swt, added, deleted, del_all);
 738                         n_deleted += cnt;
 739                         n_added -= cnt;
 740                 }
 741
 742                 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 743                 if (ret < 0) {
 744                         unit_fail("Bad lookup on iteration %d.", i);
 745                         goto complex_test_destr;
 746                 }
 747         }
 748
 749         delete_flows(swt, added, deleted, 1);
 750         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 751         if (ret < 0) {
 752                 unit_fail("Bad lookup on end deletion.");
 753                 goto complex_test_destr;
 754         } else if (ret != 0) {
 755                 unit_fail("Unexpected %d flows found on end deletion", ret);
 756                 goto complex_test_destr;
 757         }
 758
 759         success = 0;
 760
 761 complex_test_destr:
 762         allocated->key.wildcards = OFPFW_ALL;
 763         swt->delete(swt, &allocated->key, 0, 0);
 764         vfree(allocated);
 765         return success;
 766
 767 }
 768
 769 void run_table_t(void)
 770 {
 771         int linear_max, hash_buckets, hash2_buckets1;
 772         int hash2_buckets2, num_flows, num_iterations;
 773         int i;
 774
 775         struct sw_table *swt;
 776
 777         /* Most basic operations. */
 778         simple_insert_delete(table_linear_create(2048), 0);
 779         simple_insert_delete(table_hash_create(0x04C11DB7, 2048), 0);
 780         simple_insert_delete(table_hash2_create(0x04C11DB7, 2048,
 781                                                 0x1EDC6F41, 2048), 0);
 782
 783         /* Linear table operations. */
 784         multiple_insert_destroy(table_linear_create(2048), 1024, 0, 0, 0);
 785         multiple_insert_destroy(table_linear_create(2048), 2048, 0, 0, 0);
 786         multiple_insert_destroy(table_linear_create(2048), 8192, 0,
 787                                 8192 - 2048, 8192 - 2048);
 788
 789         /* Hash table operations. */
 790         multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 1024, 0,
 791                                 100, 300);
 792         multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 2048, 0,
 793                                 500, 1000);
 794         multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 8192, 0,
 795                                 0, 50);
 796         multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 65536, 0,
 797                                 1500, 3000);
 798
 799         /* Hash table 2, two hash functions. */
 800         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 801                                                 0x1EDC6F41, 2048), 1024, 0, 0, 20);
 802         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 803                                                 0x1EDC6F41, 2048), 2048, 0, 50, 200);
 804         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 805                                                 0x1EDC6F41, 1<<20), 8192, 0, 0, 20);
 806         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 807                                                 0x1EDC6F41, 1<<20), 65536, 0, 0, 20);
 808
 809         /* Hash table 2, one hash function. */
 810         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 811                                                 0x04C11DB7, 2048), 1024, 0, 0, 50);
 812         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 813                                                 0x04C11DB7, 2048), 2048, 0, 100, 300);
 814         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 815                                                 0x04C11DB7, 1<<20), 8192, 0, 0, 20);
 816         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 817                                                 0x04C11DB7, 1<<20), 65536, 0, 0, 100);
 818         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 819                                                 0x04C11DB7, 1<<20), 1<<16, 0, 0, 100);
 820
 821         linear_max = 2048;
 822         hash_buckets = 2048;
 823         hash2_buckets1 = 1024;
 824         hash2_buckets2 = 1024;
 825
 826         num_flows = 2300;
 827         num_iterations = 100;
 828
 829         printk("\nTesting on each table type:\n");
 830         printk("  iteration_test on 0 flows\n");
 831         printk("  iteration_test on %d flows\n", num_flows);
 832         printk("  add_test\n");
 833         printk("  delete_test\n");
 834         printk("  complex_add_delete_test with %d flows and %d iterations\n\n",
 835                                 num_flows, num_iterations);
 836
 837         for (i = 0; i < 3; i++) {
 838                 unsigned int mask = i == 0 ?  : 0;
 839
 840                 if (unit_failed())
 841                         return;
 842
 843                 mask = 0;
 844                 switch (i) {
 845                 case 0:
 846                         swt = table_linear_create(linear_max);
 847                         break;
 848                 case 1:
 849                         swt = table_hash_create (0x04C11DB7, hash_buckets);
 850                         break;
 851                 case 2:
 852                         swt = table_hash2_create(0x04C11DB7, hash2_buckets1,
 853                                                  0x1EDC6F41, hash2_buckets2);
 854                         break;
 855                 default:
 856                         BUG();
 857                         return;
 858                 }
 859
 860                 if (swt == NULL) {
 861                         unit_fail("failed to allocate table %d", i);
 862                         return;
 863                 }
 864                 printk("Testing %s table with %d buckets and %d max flows...\n",
 865                                         table_name(swt), hash_buckets, num_flows);
 866                 iterator_test(swt, 0, mask);
 867                 iterator_test(swt, num_flows, mask);
 868                 add_test(swt, mask);
 869                 delete_test(swt, mask);
 870                 complex_add_delete_test(swt, num_flows, num_iterations, mask);
 871                 swt->destroy(swt);
 872         }
 873 }
 874