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
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>
19 table_name(struct sw_table *table)
21 struct sw_table_stats stats;
22 table->stats(table, &stats);
26 static unsigned long int
27 table_max_flows(struct sw_table *table)
29 struct sw_table_stats stats;
30 table->stats(table, &stats);
31 return stats.max_flows;
34 static struct sw_flow *flow_zalloc(int n_actions, gfp_t flags)
36 struct sw_flow *flow = flow_alloc(n_actions, flags);
38 struct ofp_action *actions = flow->actions;
39 memset(flow, 0, sizeof *flow);
40 flow->actions = actions;
46 simple_insert_delete(struct sw_table *swt, uint16_t wildcards)
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;
53 unit_fail("table creation failed");
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;
61 a_flow->key.nw_src = 0xdeadbeef;
62 b_flow->key.nw_src = 0x001dd0d0;
64 a_flow->key.wildcards = wildcards;
65 b_flow->key.wildcards = wildcards;
67 if (!(swt->insert(swt, a_flow)))
68 unit_fail("insert failed");
69 found = swt->lookup(swt, &a_flow->key);
71 unit_fail("%p != %p", found, a_flow);
72 if (swt->lookup(swt, &b_flow->key))
73 unit_fail("lookup should not succeed (1)");
75 swt->delete(swt, &a_flow->key, 0);
76 if (swt->lookup(swt, &a_flow->key))
77 unit_fail("lookup should not succeed (3)");
84 multiple_insert_destroy(struct sw_table *swt, int inserts, uint16_t wildcards,
85 int min_collisions, int max_collisions)
91 unit_fail("table creation failed");
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;
103 if(!swt->insert(swt, a_flow)) {
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);
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");
127 set_random_key(struct sw_flow_key *key, uint16_t wildcards)
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();
144 struct flow_key_entry {
145 struct sw_flow_key key;
146 struct list_head node;
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.)
158 static struct flow_key_entry *
159 allocate_random_keys(int n_keys, uint16_t wildcards)
161 struct flow_key_entry *entries, *pos;
162 struct list_head *keys;
167 entries = vmalloc((n_keys+1) * sizeof *entries);
168 if (entries == NULL) {
169 unit_fail("cannot allocate memory for %u keys",
174 keys = &entries->node;
175 INIT_LIST_HEAD(keys);
177 for(pos = entries+1; pos < (entries + n_keys + 1); pos++) {
178 set_random_key(&pos->key, wildcards);
179 list_add(&pos->node, keys);
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
195 insert_flows(struct sw_table *swt, struct list_head *keys, struct list_head *added, int n_flows)
197 struct flow_key_entry *pos, *next;
203 list_for_each_entry_safe (pos, next, keys, node) {
204 struct sw_flow *flow = flow_zalloc(0, GFP_KERNEL);
206 unit_fail("Could only allocate %u flows", cnt);
210 flow->key = pos->key;
212 if (!swt->insert(swt, flow)) {
214 list_del(&pos->node);
216 list_del(&pos->node);
217 list_add(&pos->node, added);
219 if (n_flows != -1 && cnt == n_flows)
228 * Finds and returns the flow_key_entry in list 'keys' matching the passed in
229 * flow's key. If not found, returns NULL.
232 static struct flow_key_entry *
233 find_flow(struct list_head *keys, struct sw_flow *flow)
235 struct flow_key_entry *pos;
237 list_for_each_entry(pos, keys, node) {
238 if(!memcmp(&pos->key, &flow->key, sizeof(struct sw_flow_key)))
246 * Checks that all flow_key_entrys in list 'keys' return successful lookups on
251 check_lookup(struct sw_table *swt, struct list_head *keys)
253 struct flow_key_entry *pos;
255 list_for_each_entry(pos, keys, node) {
256 if(swt->lookup(swt, &pos->key) == NULL)
264 * Checks that all flow_key_entrys in list 'keys' DO NOT return successful
265 * lookups in the 'swt' table.
269 check_no_lookup(struct sw_table *swt, struct list_head *keys)
271 struct flow_key_entry *pos;
273 list_for_each_entry(pos, keys, node) {
274 if(swt->lookup(swt, &pos->key) != NULL)
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)
294 check_iteration(struct sw_table *swt, struct list_head *to_find, struct list_head *found)
296 struct swt_iterator iter;
297 struct flow_key_entry *entry;
301 if (!swt->iterator(swt, &iter)) {
303 unit_fail("Could not initialize iterator");
307 while (iter.flow != NULL) {
308 entry = find_flow(to_find, iter.flow);
310 unit_fail("UNKNOWN ITERATOR FLOW %p",
312 swt->iterator_destroy(&iter);
317 list_del(&entry->node);
318 list_add(&entry->node, found);
319 swt->iterator_next(&iter);
322 swt->iterator_destroy(&iter);
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
337 delete_flows(struct sw_table *swt, struct list_head *keys,
338 struct list_head *deleted, uint8_t del_all)
340 struct flow_key_entry *pos, *next;
341 int i, n_del, total_del;
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);
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");
355 list_del(&pos->node);
356 list_add(&pos->node, deleted);
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.
375 check_lookup_and_iter(struct sw_table *swt, struct list_head *deleted,
376 struct list_head **added, struct list_head **tmp)
378 struct list_head *tmp2;
381 if (check_no_lookup(swt, deleted) < 0) {
382 unit_fail("Uninserted flows returning lookup");
386 if (check_lookup(swt, *added) < 0) {
387 unit_fail("Inserted flows not returning lookup");
391 ret = check_iteration(swt, *added, *tmp);
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;
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'.
413 iterator_test(struct sw_table *swt, int n_flows, uint16_t wildcards)
415 struct flow_key_entry *allocated, h1, h2;
416 struct list_head *added, *deleted, *tmp;
417 int ret, n_del, success;
419 INIT_LIST_HEAD(&h1.node);
420 INIT_LIST_HEAD(&h2.node);
424 allocated = allocate_random_keys(n_flows, wildcards);
425 if(allocated == NULL)
428 deleted = &allocated->node;
432 ret = insert_flows(swt, deleted, added, -1);
434 goto iterator_test_destr;
438 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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",
445 goto iterator_test_destr;
448 n_del = delete_flows(swt, added, deleted, 0);
450 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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;
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",
467 goto iterator_test_destr;
470 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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",
477 goto iterator_test_destr;
483 allocated->key.wildcards = OFPFW_ALL;
484 swt->delete(swt, &allocated->key, 0);
491 * Checks lookup and iteration consistency after adding one flow, adding the
492 * flow again, and then deleting the flow from table 'swt'.
496 add_test(struct sw_table *swt, uint16_t wildcards)
498 struct flow_key_entry *allocated, h1, h2;
499 struct list_head *added, *deleted, *tmp, *tmp2;
500 int ret, success = -1;
502 INIT_LIST_HEAD(&h1.node);
503 INIT_LIST_HEAD(&h2.node);
505 allocated = allocate_random_keys(2, wildcards);
506 if (allocated == NULL)
509 deleted = &allocated->node;
513 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
515 unit_fail("Bad lookup before table modification");
517 } else if (ret != 0) {
518 unit_fail("Iterator on empty table found %d flows",
523 if (insert_flows(swt, deleted, added, 1) != 1) {
524 unit_fail("Cannot add one flow to table");
528 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
530 unit_fail("Bad lookup after single add");
532 } else if (ret != 1) {
533 unit_fail("Iterator on single add found %d flows",
539 if (insert_flows(swt, added, tmp, 1) != 1) {
540 unit_fail("Cannot insert same flow twice");
548 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
550 unit_fail("Bad lookup after double add");
552 } else if (ret != 1) {
553 unit_fail("Iterator on double add found %d flows",
558 ret = delete_flows(swt, added, deleted, 1);
560 unit_fail("Unexpected %d flows deleted", ret);
564 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
566 unit_fail("Bad lookup after delete.");
568 } else if (ret != 0) {
569 unit_fail("unexpected %d flows found delete", ret);
576 allocated->key.wildcards = OFPFW_ALL;
577 swt->delete(swt, &allocated->key, 0);
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'.
589 delete_test(struct sw_table *swt, uint16_t wildcards)
591 struct flow_key_entry *allocated, h1, h2;
592 struct list_head *added, *deleted, *tmp, *tmp2;
593 int i, ret, success = -1;
595 INIT_LIST_HEAD(&h1.node);
596 INIT_LIST_HEAD(&h2.node);
598 allocated = allocate_random_keys(2, wildcards);
599 if (allocated == NULL)
602 /* Not really added...*/
604 added = &allocated->node;
608 ret = delete_flows(swt, added, deleted, 1);
610 unit_fail("Deleting non-existent keys from table returned unexpected value %d",
612 goto delete_test_destr;
615 for (i = 0; i < 3; i++) {
616 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
619 unit_fail("Loop %d. Bad lookup before modification.", i);
621 unit_fail("Loop %d. Bad lookup after delete.", i);
622 goto delete_test_destr;
623 } else if (ret != 0) {
625 unit_fail("Loop %d. Unexpected %d flows found before modification",
628 unit_fail("Loop %d. Unexpected %d flows found after delete",
630 goto delete_test_destr;
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;
641 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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",
648 goto delete_test_destr;
651 ret = delete_flows(swt, added, deleted, 1);
653 unit_fail("loop %d: deleting inserted key from table returned unexpected value %d",
655 goto delete_test_destr;
660 ret = delete_flows(swt, deleted, tmp, 1);
666 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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;
678 allocated->key.wildcards = OFPFW_ALL;
679 swt->delete(swt, &allocated->key, 0);
685 * Randomly adds and deletes from a set of size 'n_flows', looping for 'i'
690 complex_add_delete_test(struct sw_table *swt, int n_flows, int i, uint16_t wildcards)
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;
697 INIT_LIST_HEAD(&h1.node);
698 INIT_LIST_HEAD(&h2.node);
700 allocated = allocate_random_keys(n_flows, wildcards);
701 if (allocated == NULL)
704 deleted = &allocated->node;
712 if (n_deleted != 0 && random32() % 2 == 0) {
713 cnt = random32() % n_deleted;
714 cnt = insert_flows(swt, deleted, added, cnt);
716 goto complex_test_destr;
720 if (random32() % 7 == 0)
724 cnt = delete_flows(swt, added, deleted, del_all);
729 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
731 unit_fail("Bad lookup on iteration %d.", i);
732 goto complex_test_destr;
736 delete_flows(swt, added, deleted, 1);
737 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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;
749 allocated->key.wildcards = OFPFW_ALL;
750 swt->delete(swt, &allocated->key, 0);
756 void run_table_t(void)
758 int mac_buckets, mac_max, linear_max, hash_buckets, hash2_buckets1;
759 int hash2_buckets2, num_flows, num_iterations;
762 struct sw_table *swt;
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);
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);
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);
788 /* Hash table operations. */
789 multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 1024, 0,
791 multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 2048, 0,
793 multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 8192, 0,
795 multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 65536, 0,
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);
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);
824 hash2_buckets1 = 1024;
825 hash2_buckets2 = 1024;
828 num_iterations = 100;
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);
838 for (i = 0; i < 4; i++) {
839 unsigned int mask = i == 0 ? : 0;
847 swt = table_mac_create(mac_buckets, mac_max);
848 mask = OFPFW_ALL & ~OFPFW_DL_SRC;
851 swt = table_linear_create(linear_max);
854 swt = table_hash_create (0x04C11DB7, hash_buckets);
857 swt = table_hash2_create(0x04C11DB7, hash2_buckets1,
858 0x1EDC6F41, hash2_buckets2);
866 unit_fail("failed to allocate table %d", i);
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);
874 delete_test(swt, mask);
875 complex_add_delete_test(swt, num_flows, num_iterations, mask);