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, uint32_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, 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, uint32_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, uint32_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, uint32_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)
282 struct check_iteration_state
285 struct list_head *to_find;
286 struct list_head *found;
290 check_iteration_callback(struct sw_flow *flow, void *private)
292 struct check_iteration_state *s = private;
293 struct flow_key_entry *entry;
295 entry = find_flow(s->to_find, flow);
297 unit_fail("UNKNOWN ITERATOR FLOW %p", flow);
302 list_del(&entry->node);
303 list_add(&entry->node, s->found);
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)
319 check_iteration(struct sw_table *swt, struct list_head *to_find, struct list_head *found)
321 struct sw_flow_key key;
322 struct sw_table_position position;
323 struct check_iteration_state state;
325 memset(&key, 0, sizeof key);
328 memset(&position, 0, sizeof position);
331 state.to_find = to_find;
335 swt->iterate(swt, &key, &position, check_iteration_callback, &state);
338 return state.n_found;
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
350 delete_flows(struct sw_table *swt, struct list_head *keys,
351 struct list_head *deleted, uint8_t del_all)
353 struct flow_key_entry *pos, *next;
354 int i, n_del, total_del;
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);
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");
368 list_del(&pos->node);
369 list_add(&pos->node, deleted);
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.
388 check_lookup_and_iter(struct sw_table *swt, struct list_head *deleted,
389 struct list_head **added, struct list_head **tmp)
391 struct list_head *tmp2;
394 if (check_no_lookup(swt, deleted) < 0) {
395 unit_fail("Uninserted flows returning lookup");
399 if (check_lookup(swt, *added) < 0) {
400 unit_fail("Inserted flows not returning lookup");
404 ret = check_iteration(swt, *added, *tmp);
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;
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'.
426 iterator_test(struct sw_table *swt, int n_flows, uint32_t wildcards)
428 struct flow_key_entry *allocated, h1, h2;
429 struct list_head *added, *deleted, *tmp;
430 int ret, n_del, success;
432 INIT_LIST_HEAD(&h1.node);
433 INIT_LIST_HEAD(&h2.node);
437 allocated = allocate_random_keys(n_flows, wildcards);
438 if(allocated == NULL)
441 deleted = &allocated->node;
445 ret = insert_flows(swt, deleted, added, -1);
447 goto iterator_test_destr;
451 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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",
458 goto iterator_test_destr;
461 n_del = delete_flows(swt, added, deleted, 0);
463 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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;
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",
480 goto iterator_test_destr;
483 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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",
490 goto iterator_test_destr;
496 allocated->key.wildcards = OFPFW_ALL;
497 swt->delete(swt, &allocated->key, 0, 0);
504 * Checks lookup and iteration consistency after adding one flow, adding the
505 * flow again, and then deleting the flow from table 'swt'.
509 add_test(struct sw_table *swt, uint32_t wildcards)
511 struct flow_key_entry *allocated, h1, h2;
512 struct list_head *added, *deleted, *tmp, *tmp2;
513 int ret, success = -1;
515 INIT_LIST_HEAD(&h1.node);
516 INIT_LIST_HEAD(&h2.node);
518 allocated = allocate_random_keys(2, wildcards);
519 if (allocated == NULL)
522 deleted = &allocated->node;
526 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
528 unit_fail("Bad lookup before table modification");
530 } else if (ret != 0) {
531 unit_fail("Iterator on empty table found %d flows",
536 if (insert_flows(swt, deleted, added, 1) != 1) {
537 unit_fail("Cannot add one flow to table");
541 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
543 unit_fail("Bad lookup after single add");
545 } else if (ret != 1) {
546 unit_fail("Iterator on single add found %d flows",
552 if (insert_flows(swt, added, tmp, 1) != 1) {
553 unit_fail("Cannot insert same flow twice");
561 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
563 unit_fail("Bad lookup after double add");
565 } else if (ret != 1) {
566 unit_fail("Iterator on double add found %d flows",
571 ret = delete_flows(swt, added, deleted, 1);
573 unit_fail("Unexpected %d flows deleted", ret);
577 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
579 unit_fail("Bad lookup after delete.");
581 } else if (ret != 0) {
582 unit_fail("unexpected %d flows found delete", ret);
589 allocated->key.wildcards = OFPFW_ALL;
590 swt->delete(swt, &allocated->key, 0, 0);
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'.
602 delete_test(struct sw_table *swt, uint32_t wildcards)
604 struct flow_key_entry *allocated, h1, h2;
605 struct list_head *added, *deleted, *tmp, *tmp2;
606 int i, ret, success = -1;
608 INIT_LIST_HEAD(&h1.node);
609 INIT_LIST_HEAD(&h2.node);
611 allocated = allocate_random_keys(2, wildcards);
612 if (allocated == NULL)
615 /* Not really added...*/
617 added = &allocated->node;
621 ret = delete_flows(swt, added, deleted, 1);
623 unit_fail("Deleting non-existent keys from table returned unexpected value %d",
625 goto delete_test_destr;
628 for (i = 0; i < 3; i++) {
629 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
632 unit_fail("Loop %d. Bad lookup before modification.", i);
634 unit_fail("Loop %d. Bad lookup after delete.", i);
635 goto delete_test_destr;
636 } else if (ret != 0) {
638 unit_fail("Loop %d. Unexpected %d flows found before modification",
641 unit_fail("Loop %d. Unexpected %d flows found after delete",
643 goto delete_test_destr;
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;
654 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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",
661 goto delete_test_destr;
664 ret = delete_flows(swt, added, deleted, 1);
666 unit_fail("loop %d: deleting inserted key from table returned unexpected value %d",
668 goto delete_test_destr;
673 ret = delete_flows(swt, deleted, tmp, 1);
679 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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;
691 allocated->key.wildcards = OFPFW_ALL;
692 swt->delete(swt, &allocated->key, 0, 0);
698 * Randomly adds and deletes from a set of size 'n_flows', looping for 'i'
703 complex_add_delete_test(struct sw_table *swt, int n_flows, int i, uint32_t wildcards)
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;
710 INIT_LIST_HEAD(&h1.node);
711 INIT_LIST_HEAD(&h2.node);
713 allocated = allocate_random_keys(n_flows, wildcards);
714 if (allocated == NULL)
717 deleted = &allocated->node;
725 if (n_deleted != 0 && random32() % 2 == 0) {
726 cnt = random32() % n_deleted;
727 cnt = insert_flows(swt, deleted, added, cnt);
729 goto complex_test_destr;
733 if (random32() % 7 == 0)
737 cnt = delete_flows(swt, added, deleted, del_all);
742 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
744 unit_fail("Bad lookup on iteration %d.", i);
745 goto complex_test_destr;
749 delete_flows(swt, added, deleted, 1);
750 ret = check_lookup_and_iter(swt, deleted, &added, &tmp);
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;
762 allocated->key.wildcards = OFPFW_ALL;
763 swt->delete(swt, &allocated->key, 0, 0);
769 void run_table_t(void)
771 int linear_max, hash_buckets, hash2_buckets1;
772 int hash2_buckets2, num_flows, num_iterations;
775 struct sw_table *swt;
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);
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);
789 /* Hash table operations. */
790 multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 1024, 0,
792 multiple_insert_destroy(table_hash_create(0x04C11DB7, 2048), 2048, 0,
794 multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 8192, 0,
796 multiple_insert_destroy(table_hash_create(0x04C11DB7, 1 << 20), 65536, 0,
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);
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);
823 hash2_buckets1 = 1024;
824 hash2_buckets2 = 1024;
827 num_iterations = 100;
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);
837 for (i = 0; i < 3; i++) {
838 unsigned int mask = i == 0 ? : 0;
846 swt = table_linear_create(linear_max);
849 swt = table_hash_create (0x04C11DB7, hash_buckets);
852 swt = table_hash2_create(0x04C11DB7, hash2_buckets1,
853 0x1EDC6F41, hash2_buckets2);
861 unit_fail("failed to allocate table %d", i);
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);
869 delete_test(swt, mask);
870 complex_add_delete_test(swt, num_flows, num_iterations, mask);