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, uint16_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);
  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, uint16_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, uint16_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, uint16_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 /*
 283  * Compares an iterator's view of the 'swt' table to the list of
 284  * flow_key_entrys in 'to_find'.  flow_key_entrys that are matched are removed
 285  * from the 'to_find' list and placed in the 'found' list.  Returns -1 if the
 286  * iterator cannot be initialized or it encounters a flow with a key not in
 287  * 'to_find'.  Else returns the number of flows found by the iterator
 288  * (i.e. there might still be flow keys in the 'to_find' list that were not
 289  * encountered by the iterator.  it is up to the caller to determine if that is
 290  * acceptable behavior)
 291  */
 292
 293 static int
 294 check_iteration(struct sw_table *swt, struct list_head *to_find, struct list_head *found)
 295 {
 296         struct swt_iterator iter;
 297         struct flow_key_entry *entry;
 298         int n_found = 0;
 299
 300         rcu_read_lock();
 301         if (!swt->iterator(swt, &iter)) {
 302                 rcu_read_unlock();
 303                 unit_fail("Could not initialize iterator");
 304                 return -1;
 305         }
 306
 307         while (iter.flow != NULL) {
 308                 entry = find_flow(to_find, iter.flow);
 309                 if (entry == NULL) {
 310                         unit_fail("UNKNOWN ITERATOR FLOW %p",
 311                                   iter.flow);
 312                         swt->iterator_destroy(&iter);
 313                         rcu_read_unlock();
 314                         return -1;
 315                 }
 316                 n_found++;
 317                 list_del(&entry->node);
 318                 list_add(&entry->node, found);
 319                 swt->iterator_next(&iter);
 320         }
 321
 322         swt->iterator_destroy(&iter);
 323         rcu_read_unlock();
 324
 325         return n_found;
 326 }
 327
 328 /*
 329  * Deletes from table 'swt' keys from the list of flow_key_entrys 'keys'.
 330  * Removes flow_key_entrys of deleted flows from 'keys' and places them in the
 331  * 'deleted' list.  If 'del_all' == 1, all flows in 'keys' will be deleted,
 332  * else only every third key will be deleted.  Returns the number flows deleted
 333  * from the table.
 334  */
 335
 336 static int
 337 delete_flows(struct sw_table *swt, struct list_head *keys,
 338                  struct list_head *deleted, uint8_t del_all)
 339 {
 340         struct flow_key_entry *pos, *next;
 341         int i, n_del, total_del;
 342
 343         total_del = 0;
 344         i = 0;
 345
 346         list_for_each_entry_safe (pos, next, keys, node) {
 347                 if (del_all == 1 || i % 3 == 0) {
 348                         n_del = swt->delete(swt, &pos->key, 0);
 349                         if (n_del > 1) {
 350                                 unit_fail("%d flows deleted for one entry", n_del);
 351                                 unit_fail("\tfuture 'errors' could just be product duplicate flow_key_entries");
 352                                 unit_fail("THIS IS VERY UNLIKELY...SHOULDN'T HAPPEN OFTEN");
 353                         }
 354                         total_del += n_del;
 355                         list_del(&pos->node);
 356                         list_add(&pos->node, deleted);
 357                 }
 358                 i++;
 359         }
 360
 361         return total_del;
 362 }
 363
 364 /*
 365  * Checks that both iteration and lookups are consistent with the caller's view
 366  * of the table.  In particular, checks that all keys in flow_key_entry list
 367  * 'deleted' do not show up in lookup or iteration, and keys in flow_key_entry
 368  * list 'added' do show up.  'tmp' should be an empty list that can be used for
 369  * iteration.  References to list_head pointers are needed for 'added' and 'tmp'
 370  * because iteration will cause the list_heads to change.  Function thus
 371  * switches 'added' to point to the list of added keys after the iteration.
 372  */
 373
 374 static int
 375 check_lookup_and_iter(struct sw_table *swt, struct list_head *deleted,
 376                           struct list_head **added, struct list_head **tmp)
 377 {
 378         struct list_head *tmp2;
 379         int ret;
 380
 381         if (check_no_lookup(swt, deleted) < 0) {
 382                 unit_fail("Uninserted flows returning lookup");
 383                 return -1;
 384         }
 385
 386         if (check_lookup(swt, *added) < 0) {
 387                 unit_fail("Inserted flows not returning lookup");
 388                 return -1;
 389         }
 390
 391         ret = check_iteration(swt, *added, *tmp);
 392
 393         tmp2 = *added;
 394         *added = *tmp;
 395         *tmp = tmp2;
 396
 397         if ((*tmp)->next != *tmp) {
 398                 unit_fail("WARNING: not all flows in 'added' found by iterator");
 399                 unit_fail("\tcould be a product of duplicate flow_key_entrys, though should be VERY rare.");
 400                 /* To avoid reoccurence */
 401                 (*tmp)->next = (*tmp)->prev = *tmp;
 402         }
 403
 404         return ret;
 405 }
 406
 407 /*
 408  * Verifies iteration and lookup after inserting 'n_flows', then after deleting
 409  * some flows, and once again after deleting all flows in table 'swt'.
 410  */
 411
 412 static int
 413 iterator_test(struct sw_table *swt, int n_flows, uint16_t wildcards)
 414 {
 415         struct flow_key_entry *allocated, h1, h2;
 416         struct list_head *added, *deleted, *tmp;
 417         int ret, n_del, success;
 418
 419         INIT_LIST_HEAD(&h1.node);
 420         INIT_LIST_HEAD(&h2.node);
 421
 422         success = -1;
 423
 424         allocated = allocate_random_keys(n_flows, wildcards);
 425         if(allocated == NULL)
 426                 return success;
 427
 428         deleted = &allocated->node;
 429         added = &h1.node;
 430         tmp = &h2.node;
 431
 432         ret = insert_flows(swt, deleted, added, -1);
 433         if (ret < 0)
 434                 goto iterator_test_destr;
 435
 436         n_flows = ret;
 437
 438         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 439         if (ret < 0) {
 440                 unit_fail("Bad lookup after insertion");
 441                 goto iterator_test_destr;
 442         } else if (ret != n_flows) {
 443                 unit_fail("Iterator only found %d of %d flows",
 444                           ret, n_flows);
 445                 goto iterator_test_destr;
 446         }
 447
 448         n_del = delete_flows(swt, added, deleted, 0);
 449
 450         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 451         if (ret < 0) {
 452                 unit_fail("Bad lookup after some deletion");
 453                 goto iterator_test_destr;
 454         } else if (ret + n_del != n_flows) {
 455                 unit_fail("iterator after deletion inconsistent");
 456                 unit_fail("\tn_del = %d, n_found = %d, n_flows = %d",
 457                           n_del, ret, n_flows);
 458                 goto iterator_test_destr;
 459         }
 460
 461         n_flows -= n_del;
 462
 463         n_del = delete_flows(swt, added, deleted, 1);
 464         if (n_del != n_flows) {
 465                 unit_fail("Not all flows deleted - only %d of %d",
 466                           n_del, n_flows);
 467                 goto iterator_test_destr;
 468         }
 469
 470         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 471         if (ret < 0) {
 472                 unit_fail("Bad lookup after all deletion");
 473                 goto iterator_test_destr;
 474         } else if (ret != 0) {
 475                 unit_fail("Empty table iterator failed.  %d flows found",
 476                           ret);
 477                 goto iterator_test_destr;
 478         }
 479
 480         success = 0;
 481
 482 iterator_test_destr:
 483         allocated->key.wildcards = OFPFW_ALL;
 484         swt->delete(swt, &allocated->key, 0);
 485         vfree(allocated);
 486         return success;
 487 }
 488
 489
 490 /*
 491  * Checks lookup and iteration consistency after adding one flow, adding the
 492  * flow again, and then deleting the flow from table 'swt'.
 493  */
 494
 495 static int
 496 add_test(struct sw_table *swt, uint16_t wildcards)
 497 {
 498         struct flow_key_entry *allocated, h1, h2;
 499         struct list_head *added, *deleted, *tmp, *tmp2;
 500         int ret, success = -1;
 501
 502         INIT_LIST_HEAD(&h1.node);
 503         INIT_LIST_HEAD(&h2.node);
 504
 505         allocated = allocate_random_keys(2, wildcards);
 506         if (allocated == NULL)
 507                 return success;
 508
 509         deleted = &allocated->node;
 510         added = &h1.node;
 511         tmp = &h2.node;
 512
 513         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 514         if (ret < 0) {
 515                 unit_fail("Bad lookup before table modification");
 516                 goto add_test_destr;
 517         } else if (ret != 0) {
 518                 unit_fail("Iterator on empty table found %d flows",
 519                           ret);
 520                 goto add_test_destr;
 521         }
 522
 523         if (insert_flows(swt, deleted, added, 1) != 1) {
 524                 unit_fail("Cannot add one flow to table");
 525                 goto add_test_destr;
 526         }
 527
 528         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 529         if (ret < 0) {
 530                 unit_fail("Bad lookup after single add");
 531                 goto add_test_destr;
 532         } else if (ret != 1) {
 533                 unit_fail("Iterator on single add found %d flows",
 534                           ret);
 535                 goto add_test_destr;
 536         }
 537
 538         /* Re-adding flow */
 539         if (insert_flows(swt, added, tmp, 1) != 1) {
 540                 unit_fail("Cannot insert same flow twice");
 541                 goto add_test_destr;
 542         }
 543
 544         tmp2 = added;
 545         added = tmp;
 546         tmp = tmp2;
 547
 548         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 549         if (ret < 0) {
 550                 unit_fail("Bad lookup after double add");
 551                 goto add_test_destr;
 552         } else if (ret != 1) {
 553                 unit_fail("Iterator on double add found %d flows",
 554                           ret);
 555                 goto add_test_destr;
 556         }
 557
 558         ret = delete_flows(swt, added, deleted, 1);
 559         if (ret != 1) {
 560                 unit_fail("Unexpected %d flows deleted", ret);
 561                 goto add_test_destr;
 562         }
 563
 564         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 565         if (ret < 0) {
 566                 unit_fail("Bad lookup after delete.");
 567                 goto add_test_destr;
 568         } else if (ret != 0) {
 569                 unit_fail("unexpected %d flows found delete", ret);
 570                 goto add_test_destr;
 571         }
 572
 573         success = 0;
 574
 575 add_test_destr:
 576         allocated->key.wildcards = OFPFW_ALL;
 577         swt->delete(swt, &allocated->key, 0);
 578         vfree(allocated);
 579         return success;
 580 }
 581
 582 /*
 583  * Checks lookup and iteration consistency after each deleting a non-existent
 584  * flow, adding and then deleting a flow, adding the flow again, and then
 585  * deleting the flow twice in table 'swt'.
 586  */
 587
 588 static int
 589 delete_test(struct sw_table *swt, uint16_t wildcards)
 590 {
 591         struct flow_key_entry *allocated, h1, h2;
 592         struct list_head *added, *deleted, *tmp, *tmp2;
 593         int i, ret, success = -1;
 594
 595         INIT_LIST_HEAD(&h1.node);
 596         INIT_LIST_HEAD(&h2.node);
 597
 598         allocated = allocate_random_keys(2, wildcards);
 599         if (allocated == NULL)
 600                 return success;
 601
 602         /* Not really added...*/
 603
 604         added = &allocated->node;
 605         deleted = &h1.node;
 606         tmp = &h2.node;
 607
 608         ret = delete_flows(swt, added, deleted, 1);
 609         if (ret != 0) {
 610                 unit_fail("Deleting non-existent keys from table returned unexpected value %d",
 611                           ret);
 612                         goto delete_test_destr;
 613         }
 614
 615         for (i = 0; i < 3; i++) {
 616                 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 617                 if (ret < 0) {
 618                         if (i == 0)
 619                                 unit_fail("Loop %d. Bad lookup before modification.", i);
 620                         else
 621                                 unit_fail("Loop %d. Bad lookup after delete.", i);
 622                         goto delete_test_destr;
 623                 } else if (ret != 0) {
 624                         if(i == 0)
 625                                 unit_fail("Loop %d. Unexpected %d flows found before modification",
 626                                           i, ret);
 627                         else
 628                                 unit_fail("Loop %d. Unexpected %d flows found after delete",
 629                                           i, ret);
 630                         goto delete_test_destr;
 631                 }
 632
 633                 if(i == 2)
 634                         break;
 635
 636                 if (insert_flows(swt, deleted, added, 1) != 1) {
 637                         unit_fail("loop %d: cannot add flow to table", i);
 638                         goto delete_test_destr;
 639                 }
 640
 641                 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 642                 if (ret < 0) {
 643                         unit_fail("loop %d: bad lookup after single add.", i);
 644                         goto delete_test_destr;
 645                 } else if (ret != 1) {
 646                         unit_fail("loop %d: unexpected %d flows found after single add",
 647                                   i, ret);
 648                         goto delete_test_destr;
 649                 }
 650
 651                 ret = delete_flows(swt, added, deleted, 1);
 652                 if (ret != 1) {
 653                         unit_fail("loop %d: deleting inserted key from table returned unexpected value %d",
 654                                                 i, ret);
 655                         goto delete_test_destr;
 656                 }
 657         }
 658
 659
 660         ret = delete_flows(swt, deleted, tmp, 1);
 661
 662         tmp2 = deleted;
 663         deleted = tmp2;
 664         tmp = tmp2;
 665
 666         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 667         if (ret < 0) {
 668                 unit_fail("Bad lookup after double delete.");
 669                 goto delete_test_destr;
 670         } else if (ret != 0) {
 671                 unit_fail("Unexpected %d flows found after double delete", ret);
 672                 goto delete_test_destr;
 673         }
 674
 675         success = 0;
 676
 677 delete_test_destr:
 678         allocated->key.wildcards = OFPFW_ALL;
 679         swt->delete(swt, &allocated->key, 0);
 680         vfree(allocated);
 681         return success;
 682 }
 683
 684 /*
 685  * Randomly adds and deletes from a set of size 'n_flows', looping for 'i'
 686  * iterations.
 687  */
 688
 689 static int
 690 complex_add_delete_test(struct sw_table *swt, int n_flows, int i, uint16_t wildcards)
 691 {
 692         struct flow_key_entry *allocated, h1, h2;
 693         struct list_head *added, *deleted, *tmp;
 694         int cnt, ret, n_added, n_deleted, success = -1;
 695         uint8_t del_all;
 696
 697         INIT_LIST_HEAD(&h1.node);
 698         INIT_LIST_HEAD(&h2.node);
 699
 700         allocated = allocate_random_keys(n_flows, wildcards);
 701         if (allocated == NULL)
 702                 return success;
 703
 704         deleted = &allocated->node;
 705         added = &h1.node;
 706         tmp = &h2.node;
 707
 708         n_deleted = n_flows;
 709         n_added = 0;
 710
 711         for (;i > 0; i--) {
 712                 if (n_deleted != 0 && random32() % 2 == 0) {
 713                         cnt = random32() % n_deleted;
 714                         cnt = insert_flows(swt, deleted, added, cnt);
 715                         if (cnt < 0)
 716                                 goto complex_test_destr;
 717                         n_deleted -= cnt;
 718                         n_added += cnt;
 719                 } else {
 720                         if (random32() % 7 == 0)
 721                                 del_all = 1;
 722                         else
 723                                 del_all = 0;
 724                         cnt = delete_flows(swt, added, deleted, del_all);
 725                         n_deleted += cnt;
 726                         n_added -= cnt;
 727                 }
 728
 729                 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 730                 if (ret < 0) {
 731                         unit_fail("Bad lookup on iteration %d.", i);
 732                         goto complex_test_destr;
 733                 }
 734         }
 735
 736         delete_flows(swt, added, deleted, 1);
 737         ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
 738         if (ret < 0) {
 739                 unit_fail("Bad lookup on end deletion.");
 740                 goto complex_test_destr;
 741         } else if (ret != 0) {
 742                 unit_fail("Unexpected %d flows found on end deletion", ret);
 743                 goto complex_test_destr;
 744         }
 745
 746         success = 0;
 747
 748 complex_test_destr:
 749         allocated->key.wildcards = OFPFW_ALL;
 750         swt->delete(swt, &allocated->key, 0);
 751         vfree(allocated);
 752         return success;
 753
 754 }
 755
 756 void run_table_t(void)
 757 {
 758         int mac_buckets, mac_max, linear_max, hash_buckets, hash2_buckets1;
 759         int hash2_buckets2, num_flows, num_iterations;
 760         int i;
 761
 762         struct sw_table *swt;
 763
 764         /* Most basic operations. */
 765         simple_insert_delete(table_mac_create(2048, 65536),
 766                          OFPFW_ALL & ~OFPFW_DL_SRC);
 767         simple_insert_delete(table_linear_create(2048), 0);
 768         simple_insert_delete(table_hash_create(0x04C11DB7, 2048), 0);
 769         simple_insert_delete(table_hash2_create(0x04C11DB7, 2048,
 770                                                 0x1EDC6F41, 2048), 0);
 771
 772         /* MAC table operations. */
 773         multiple_insert_destroy(table_mac_create(2048, 65536), 1024,
 774                                 OFPFW_ALL & ~OFPFW_DL_SRC, 0, 0);
 775         multiple_insert_destroy(table_mac_create(2048, 65536), 2048,
 776                                 OFPFW_ALL & ~OFPFW_DL_SRC, 0, 0);
 777         multiple_insert_destroy(table_mac_create(2048, 65536), 65535,
 778                                 OFPFW_ALL & ~OFPFW_DL_SRC, 0, 0);
 779         multiple_insert_destroy(table_mac_create(2048, 65536),
 780                                 131072, OFPFW_ALL & ~OFPFW_DL_SRC, 65536, 65536);
 781
 782         /* Linear table operations. */
 783         multiple_insert_destroy(table_linear_create(2048), 1024, 0, 0, 0);
 784         multiple_insert_destroy(table_linear_create(2048), 2048, 0, 0, 0);
 785         multiple_insert_destroy(table_linear_create(2048), 8192, 0,
 786                                 8192 - 2048, 8192 - 2048);
 787
 788         /* Hash table operations. */
 789         multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 1024, 0,
 790                                 100, 300);
 791         multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 2048, 0,
 792                                 500, 1000);
 793         multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 8192, 0,
 794                                 0, 50);
 795         multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 65536, 0,
 796                                 1500, 3000);
 797
 798         /* Hash table 2, two hash functions. */
 799         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 800                                                 0x1EDC6F41, 2048), 1024, 0, 0, 20);
 801         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 802                                                 0x1EDC6F41, 2048), 2048, 0, 50, 200);
 803         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 804                                                 0x1EDC6F41, 1<<20), 8192, 0, 0, 20);
 805         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 806                                                 0x1EDC6F41, 1<<20), 65536, 0, 0, 20);
 807
 808         /* Hash table 2, one hash function. */
 809         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 810                                                 0x04C11DB7, 2048), 1024, 0, 0, 50);
 811         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 2048,
 812                                                 0x04C11DB7, 2048), 2048, 0, 100, 300);
 813         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 814                                                 0x04C11DB7, 1<<20), 8192, 0, 0, 20);
 815         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 816                                                 0x04C11DB7, 1<<20), 65536, 0, 0, 100);
 817         multiple_insert_destroy(table_hash2_create(0x04C11DB7, 1<<20,
 818                                                 0x04C11DB7, 1<<20), 1<<16, 0, 0, 100);
 819
 820         mac_buckets = 1024;
 821         mac_max = 2048;
 822         linear_max = 2048;
 823         hash_buckets = 2048;
 824         hash2_buckets1 = 1024;
 825         hash2_buckets2 = 1024;
 826
 827         num_flows = 2300;
 828         num_iterations = 100;
 829
 830         printk("\nTesting on each table type:\n");
 831         printk("  iteration_test on 0 flows\n");
 832         printk("  iteration_test on %d flows\n", num_flows);
 833         printk("  add_test\n");
 834         printk("  delete_test\n");
 835         printk("  complex_add_delete_test with %d flows and %d iterations\n\n",
 836                                 num_flows, num_iterations);
 837
 838         for (i = 0; i < 4; i++) {
 839                 unsigned int mask = i == 0 ?  : 0;
 840
 841                 if (unit_failed())
 842                         return;
 843
 844                 mask = 0;
 845                 switch (i) {
 846                 case 0:
 847                         swt = table_mac_create(mac_buckets, mac_max);
 848                         mask = OFPFW_ALL & ~OFPFW_DL_SRC;
 849                         break;
 850                 case 1:
 851                         swt = table_linear_create(linear_max);
 852                         break;
 853                 case 2:
 854                         swt = table_hash_create (0x04C11DB7, hash_buckets);
 855                         break;
 856                 case 3:
 857                         swt = table_hash2_create(0x04C11DB7, hash2_buckets1,
 858                                                  0x1EDC6F41, hash2_buckets2);
 859                         break;
 860                 default:
 861                         BUG();
 862                         return;
 863                 }
 864
 865                 if (swt == NULL) {
 866                         unit_fail("failed to allocate table %d", i);
 867                         return;
 868                 }
 869                 printk("Testing %s table with %d buckets and %d max flows...\n",
 870                                         table_name(swt), mac_buckets, mac_max);
 871                 iterator_test(swt, 0, mask);
 872                 iterator_test(swt, num_flows, mask);
 873                 add_test(swt, mask);
 874                 delete_test(swt, mask);
 875                 complex_add_delete_test(swt, num_flows, num_iterations, mask);
 876                 swt->destroy(swt);
 877         }
 878 }
 879