X-Git-Url: http://git.cascardo.info/?a=blobdiff_plain;f=tests%2Ftest-classifier.c;h=e4eb0f436d2bd8e30072f13da7f2d9db1cfe38e4;hb=4a1f523f2d760e9e5751bc93519d1b70c5492b56;hp=1e0455099116159dbd6aff11b69a63cb9dd80848;hpb=b826639572ab3ef1ca2a0b1251b7980696a25c5b;p=cascardo%2Fovs.git diff --git a/tests/test-classifier.c b/tests/test-classifier.c index 1e0455099..e4eb0f436 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc. + * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -26,22 +26,24 @@ */ #include +#undef NDEBUG #include "classifier.h" +#include #include #include #include "byte-order.h" +#include "classifier-private.h" #include "command-line.h" #include "flow.h" #include "ofp-util.h" +#include "ovstest.h" #include "packets.h" #include "random.h" #include "unaligned.h" - -#undef NDEBUG -#include +#include "util.h" /* Fields in a rule. */ -#define CLS_FIELDS \ +#define CLS_FIELDS \ /* struct flow all-caps */ \ /* member name name */ \ /* ----------- -------- */ \ @@ -105,8 +107,7 @@ test_rule_destroy(struct test_rule *rule) } } -static struct test_rule *make_rule(int wc_fields, unsigned int priority, - int value_pat); +static struct test_rule *make_rule(int wc_fields, int priority, int value_pat); static void free_rule(struct test_rule *); static struct test_rule *clone_rule(const struct test_rule *); @@ -153,7 +154,7 @@ tcls_insert(struct tcls *tcls, const struct test_rule *rule) const struct cls_rule *pos = &tcls->rules[i]->cls_rule; if (cls_rule_equal(pos, &rule->cls_rule)) { /* Exact match. */ - free_rule(tcls->rules[i]); + ovsrcu_postpone(free_rule, tcls->rules[i]); tcls->rules[i] = clone_rule(rule); return tcls->rules[i]; } else if (pos->priority < rule->cls_rule.priority) { @@ -191,7 +192,7 @@ tcls_remove(struct tcls *cls, const struct test_rule *rule) return; } } - NOT_REACHED(); + OVS_NOT_REACHED(); } static bool @@ -245,7 +246,7 @@ match(const struct cls_rule *wild_, const struct flow *fixed) ^ wild.flow.in_port.ofp_port) & wild.wc.masks.in_port.ofp_port); } else { - NOT_REACHED(); + OVS_NOT_REACHED(); } if (!eq) { @@ -307,9 +308,11 @@ static ovs_be16 dl_type_values[] static ovs_be16 tp_src_values[] = { CONSTANT_HTONS(49362), CONSTANT_HTONS(80) }; static ovs_be16 tp_dst_values[] = { CONSTANT_HTONS(6667), CONSTANT_HTONS(22) }; -static uint8_t dl_src_values[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 }, +static uint8_t dl_src_values[][ETH_ADDR_LEN] = { + { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 }, { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } }; -static uint8_t dl_dst_values[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 }, +static uint8_t dl_dst_values[][ETH_ADDR_LEN] = { + { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 }, { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } }; static uint8_t nw_proto_values[] = { IPPROTO_TCP, IPPROTO_ICMP }; static uint8_t nw_dscp_values[] = { 48, 0 }; @@ -396,17 +399,18 @@ get_value(unsigned int *x, unsigned n_values) static void compare_classifiers(struct classifier *cls, struct tcls *tcls) - OVS_REQ_RDLOCK(cls->rwlock) { static const int confidence = 500; unsigned int i; assert(classifier_count(cls) == tcls->n_rules); for (i = 0; i < confidence; i++) { - struct cls_rule *cr0, *cr1; + const struct cls_rule *cr0, *cr1, *cr2; struct flow flow; + struct flow_wildcards wc; unsigned int x; + flow_wildcards_init_catchall(&wc); x = random_range(N_FLOW_VALUES); memset(&flow, 0, sizeof flow); flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)]; @@ -426,7 +430,10 @@ compare_classifiers(struct classifier *cls, struct tcls *tcls) flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)]; flow.nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)]; - cr0 = classifier_lookup(cls, &flow, NULL); + /* This assertion is here to suppress a GCC 4.9 array-bounds warning */ + ovs_assert(cls->n_tries <= CLS_MAX_TRIES); + + cr0 = classifier_lookup(cls, &flow, &wc); cr1 = tcls_lookup(tcls, &flow); assert((cr0 == NULL) == (cr1 == NULL)); if (cr0 != NULL) { @@ -436,48 +443,114 @@ compare_classifiers(struct classifier *cls, struct tcls *tcls) assert(cls_rule_equal(cr0, cr1)); assert(tr0->aux == tr1->aux); } + cr2 = classifier_lookup(cls, &flow, NULL); + assert(cr2 == cr0); } } static void destroy_classifier(struct classifier *cls) { - struct test_rule *rule, *next_rule; - struct cls_cursor cursor; - - ovs_rwlock_wrlock(&cls->rwlock); - cls_cursor_init(&cursor, cls, NULL); - CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cls_rule, &cursor) { - classifier_remove(cls, &rule->cls_rule); - free_rule(rule); + struct test_rule *rule; + + classifier_defer(cls); + CLS_FOR_EACH (rule, cls_rule, cls) { + if (classifier_remove(cls, &rule->cls_rule)) { + ovsrcu_postpone(free_rule, rule); + } } - ovs_rwlock_unlock(&cls->rwlock); classifier_destroy(cls); } +static void +pvector_verify(const struct pvector *pvec) +{ + void *ptr OVS_UNUSED; + int prev_priority = INT_MAX; + + PVECTOR_FOR_EACH (ptr, pvec) { + int priority = cursor__.vector[cursor__.entry_idx].priority; + if (priority > prev_priority) { + ovs_abort(0, "Priority vector is out of order (%u > %u)", + priority, prev_priority); + } + prev_priority = priority; + } +} + +static unsigned int +trie_verify(const rcu_trie_ptr *trie, unsigned int ofs, unsigned int n_bits) +{ + const struct trie_node *node = ovsrcu_get(struct trie_node *, trie); + + if (node) { + assert(node->n_rules == 0 || node->n_bits > 0); + ofs += node->n_bits; + assert((ofs > 0 || (ofs == 0 && node->n_bits == 0)) && ofs <= n_bits); + + return node->n_rules + + trie_verify(&node->edges[0], ofs, n_bits) + + trie_verify(&node->edges[1], ofs, n_bits); + } + return 0; +} + +static void +verify_tries(struct classifier *cls) + OVS_NO_THREAD_SAFETY_ANALYSIS +{ + unsigned int n_rules = 0; + int i; + + for (i = 0; i < cls->n_tries; i++) { + n_rules += trie_verify(&cls->tries[i].root, 0, + cls->tries[i].field->n_bits); + } + assert(n_rules <= cls->n_rules); +} + static void check_tables(const struct classifier *cls, int n_tables, int n_rules, - int n_dups) OVS_REQ_RDLOCK(cls->rwlock) + int n_dups) + OVS_NO_THREAD_SAFETY_ANALYSIS { - const struct cls_table *table; + const struct cls_subtable *table; struct test_rule *test_rule; - struct cls_cursor cursor; int found_tables = 0; int found_rules = 0; int found_dups = 0; int found_rules2 = 0; - HMAP_FOR_EACH (table, hmap_node, &cls->tables) { - const struct cls_rule *head; - unsigned int max_priority = 0; + pvector_verify(&cls->subtables); + CMAP_FOR_EACH (table, cmap_node, &cls->subtables_map) { + const struct cls_match *head; + int max_priority = INT_MIN; unsigned int max_count = 0; + bool found = false; + const struct cls_subtable *iter; + + /* Locate the subtable from 'subtables'. */ + PVECTOR_FOR_EACH (iter, &cls->subtables) { + if (iter == table) { + if (found) { + ovs_abort(0, "Subtable %p duplicated in 'subtables'.", + table); + } + found = true; + } + } + if (!found) { + ovs_abort(0, "Subtable %p not found from 'subtables'.", table); + } - assert(!hmap_is_empty(&table->rules)); + assert(!cmap_is_empty(&table->rules)); + assert(trie_verify(&table->ports_trie, 0, table->ports_mask_len) + == (table->ports_mask_len ? cmap_count(&table->rules) : 0)); found_tables++; - HMAP_FOR_EACH (head, hmap_node, &table->rules) { - unsigned int prev_priority = UINT_MAX; - const struct cls_rule *rule; + CMAP_FOR_EACH (head, cmap_node, &table->rules) { + int prev_priority = INT_MAX; + const struct cls_match *rule; if (head->priority > max_priority) { max_priority = head->priority; @@ -487,34 +560,35 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules, } found_rules++; - LIST_FOR_EACH (rule, list, &head->list) { + RCULIST_FOR_EACH (rule, list, &head->list) { assert(rule->priority < prev_priority); assert(rule->priority <= table->max_priority); prev_priority = rule->priority; found_rules++; found_dups++; - assert(classifier_find_rule_exactly(cls, rule) == rule); + assert(classifier_find_rule_exactly(cls, rule->cls_rule) + == rule->cls_rule); } } assert(table->max_priority == max_priority); assert(table->max_count == max_count); } - assert(found_tables == hmap_count(&cls->tables)); - assert(n_tables == -1 || n_tables == hmap_count(&cls->tables)); + assert(found_tables == cmap_count(&cls->subtables_map)); + assert(found_tables == pvector_count(&cls->subtables)); + assert(n_tables == -1 || n_tables == cmap_count(&cls->subtables_map)); assert(n_rules == -1 || found_rules == n_rules); assert(n_dups == -1 || found_dups == n_dups); - cls_cursor_init(&cursor, cls, NULL); - CLS_CURSOR_FOR_EACH (test_rule, cls_rule, &cursor) { + CLS_FOR_EACH (test_rule, cls_rule, cls) { found_rules2++; } assert(found_rules == found_rules2); } static struct test_rule * -make_rule(int wc_fields, unsigned int priority, int value_pat) +make_rule(int wc_fields, int priority, int value_pat) { const struct cls_field *f; struct test_rule *rule; @@ -554,12 +628,14 @@ make_rule(int wc_fields, unsigned int priority, int value_pat) } else if (f_idx == CLS_F_IDX_IN_PORT) { match.wc.masks.in_port.ofp_port = u16_to_ofp(UINT16_MAX); } else { - NOT_REACHED(); + OVS_NOT_REACHED(); } } rule = xzalloc(sizeof *rule); - cls_rule_init(&rule->cls_rule, &match, wc_fields ? priority : UINT_MAX); + cls_rule_init(&rule->cls_rule, &match, wc_fields + ? (priority == INT_MIN ? priority + 1 : priority) + : INT_MAX); return rule; } @@ -582,11 +658,11 @@ free_rule(struct test_rule *rule) } static void -shuffle(unsigned int *p, size_t n) +shuffle(int *p, size_t n) { for (; n > 1; n--, p++) { - unsigned int *q = &p[random_range(n)]; - unsigned int tmp = *p; + int *q = &p[random_range(n)]; + int tmp = *p; *p = *q; *q = tmp; } @@ -605,6 +681,18 @@ shuffle_u32s(uint32_t *p, size_t n) /* Classifier tests. */ +static enum mf_field_id trie_fields[2] = { + MFF_IPV4_DST, MFF_IPV4_SRC +}; + +static void +set_prefix_fields(struct classifier *cls) +{ + verify_tries(cls); + classifier_set_prefix_fields(cls, trie_fields, ARRAY_SIZE(trie_fields)); + verify_tries(cls); +} + /* Tests an empty classifier. */ static void test_empty(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) @@ -612,13 +700,12 @@ test_empty(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) struct classifier cls; struct tcls tcls; - classifier_init(&cls); - ovs_rwlock_rdlock(&cls.rwlock); + classifier_init(&cls, flow_segment_u32s); + set_prefix_fields(&cls); tcls_init(&tcls); assert(classifier_is_empty(&cls)); assert(tcls_is_empty(&tcls)); compare_classifiers(&cls, &tcls); - ovs_rwlock_unlock(&cls.rwlock); classifier_destroy(&cls); tcls_destroy(&tcls); } @@ -644,14 +731,14 @@ test_single_rule(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) rule = make_rule(wc_fields, hash_bytes(&wc_fields, sizeof wc_fields, 0), 0); - classifier_init(&cls); - ovs_rwlock_wrlock(&cls.rwlock); + classifier_init(&cls, flow_segment_u32s); + set_prefix_fields(&cls); tcls_init(&tcls); tcls_rule = tcls_insert(&tcls, rule); classifier_insert(&cls, &rule->cls_rule); - check_tables(&cls, 1, 1, 0); compare_classifiers(&cls, &tcls); + check_tables(&cls, 1, 1, 0); classifier_remove(&cls, &rule->cls_rule); tcls_remove(&tcls, tcls_rule); @@ -659,8 +746,7 @@ test_single_rule(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) assert(tcls_is_empty(&tcls)); compare_classifiers(&cls, &tcls); - free_rule(rule); - ovs_rwlock_unlock(&cls.rwlock); + ovsrcu_postpone(free_rule, rule); classifier_destroy(&cls); tcls_destroy(&tcls); } @@ -683,24 +769,27 @@ test_rule_replacement(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) rule2->aux += 5; rule2->aux += 5; - classifier_init(&cls); - ovs_rwlock_wrlock(&cls.rwlock); + classifier_init(&cls, flow_segment_u32s); + set_prefix_fields(&cls); tcls_init(&tcls); tcls_insert(&tcls, rule1); classifier_insert(&cls, &rule1->cls_rule); - check_tables(&cls, 1, 1, 0); compare_classifiers(&cls, &tcls); + check_tables(&cls, 1, 1, 0); tcls_destroy(&tcls); tcls_init(&tcls); tcls_insert(&tcls, rule2); + assert(test_rule_from_cls_rule( classifier_replace(&cls, &rule2->cls_rule)) == rule1); - free_rule(rule1); - check_tables(&cls, 1, 1, 0); + ovsrcu_postpone(free_rule, rule1); compare_classifiers(&cls, &tcls); + check_tables(&cls, 1, 1, 0); + classifier_defer(&cls); + classifier_remove(&cls, &rule2->cls_rule); + tcls_destroy(&tcls); - ovs_rwlock_unlock(&cls.rwlock); destroy_classifier(&cls); } } @@ -795,8 +884,8 @@ test_many_rules_in_one_list (int argc OVS_UNUSED, char *argv[] OVS_UNUSED) pri_rules[i] = -1; } - classifier_init(&cls); - ovs_rwlock_wrlock(&cls.rwlock); + classifier_init(&cls, flow_segment_u32s); + set_prefix_fields(&cls); tcls_init(&tcls); for (i = 0; i < ARRAY_SIZE(ops); i++) { @@ -825,23 +914,23 @@ test_many_rules_in_one_list (int argc OVS_UNUSED, char *argv[] OVS_UNUSED) tcls_rules[j] = NULL; pri_rules[pris[j]] = -1; } + compare_classifiers(&cls, &tcls); n = 0; for (m = 0; m < N_RULES; m++) { n += tcls_rules[m] != NULL; } check_tables(&cls, n > 0, n, n - 1); - - compare_classifiers(&cls, &tcls); } - ovs_rwlock_unlock(&cls.rwlock); - classifier_destroy(&cls); - tcls_destroy(&tcls); - + classifier_defer(&cls); for (i = 0; i < N_RULES; i++) { - free_rule(rules[i]); + if (classifier_remove(&cls, &rules[i]->cls_rule)) { + ovsrcu_postpone(free_rule, rules[i]); + } } + classifier_destroy(&cls); + tcls_destroy(&tcls); } while (next_permutation(ops, ARRAY_SIZE(ops))); assert(n_permutations == (factorial(N_RULES * 2) >> N_RULES)); } @@ -897,12 +986,12 @@ test_many_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) value_mask = ~wcf & ((1u << CLS_N_FIELDS) - 1); } while ((1 << count_ones(value_mask)) < N_RULES); - classifier_init(&cls); - ovs_rwlock_wrlock(&cls.rwlock); + classifier_init(&cls, flow_segment_u32s); + set_prefix_fields(&cls); tcls_init(&tcls); for (i = 0; i < N_RULES; i++) { - unsigned int priority = random_uint32(); + int priority = random_range(INT_MAX); do { value_pats[i] = random_uint32() & value_mask; @@ -910,22 +999,22 @@ test_many_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) rules[i] = make_rule(wcf, priority, value_pats[i]); tcls_rules[i] = tcls_insert(&tcls, rules[i]); + classifier_insert(&cls, &rules[i]->cls_rule); + compare_classifiers(&cls, &tcls); check_tables(&cls, 1, i + 1, 0); - compare_classifiers(&cls, &tcls); } for (i = 0; i < N_RULES; i++) { tcls_remove(&tcls, tcls_rules[i]); classifier_remove(&cls, &rules[i]->cls_rule); - free_rule(rules[i]); + compare_classifiers(&cls, &tcls); + ovsrcu_postpone(free_rule, rules[i]); check_tables(&cls, i < N_RULES - 1, N_RULES - (i + 1), 0); - compare_classifiers(&cls, &tcls); } - ovs_rwlock_unlock(&cls.rwlock); classifier_destroy(&cls); tcls_destroy(&tcls); } @@ -949,51 +1038,50 @@ test_many_rules_in_n_tables(int n_tables) } for (iteration = 0; iteration < 30; iteration++) { - unsigned int priorities[MAX_RULES]; + int priorities[MAX_RULES]; struct classifier cls; struct tcls tcls; random_set_seed(iteration + 1); for (i = 0; i < MAX_RULES; i++) { - priorities[i] = i * 129; + priorities[i] = (i * 129) & INT_MAX; } shuffle(priorities, ARRAY_SIZE(priorities)); - classifier_init(&cls); - ovs_rwlock_wrlock(&cls.rwlock); + classifier_init(&cls, flow_segment_u32s); + set_prefix_fields(&cls); tcls_init(&tcls); for (i = 0; i < MAX_RULES; i++) { struct test_rule *rule; - unsigned int priority = priorities[i]; + int priority = priorities[i]; int wcf = wcfs[random_range(n_tables)]; int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1); rule = make_rule(wcf, priority, value_pat); tcls_insert(&tcls, rule); classifier_insert(&cls, &rule->cls_rule); - check_tables(&cls, -1, i + 1, -1); compare_classifiers(&cls, &tcls); + check_tables(&cls, -1, i + 1, -1); } while (!classifier_is_empty(&cls)) { - struct test_rule *rule, *next_rule; struct test_rule *target; - struct cls_cursor cursor; + struct test_rule *rule; target = clone_rule(tcls.rules[random_range(tcls.n_rules)]); - cls_cursor_init(&cursor, &cls, &target->cls_rule); - CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cls_rule, &cursor) { - classifier_remove(&cls, &rule->cls_rule); - free_rule(rule); + CLS_FOR_EACH_TARGET (rule, cls_rule, &cls, &target->cls_rule) { + if (classifier_remove(&cls, &rule->cls_rule)) { + ovsrcu_postpone(free_rule, rule); + } } + tcls_delete_matches(&tcls, &target->cls_rule); compare_classifiers(&cls, &tcls); check_tables(&cls, -1, -1, -1); free_rule(target); } - ovs_rwlock_unlock(&cls.rwlock); destroy_classifier(&cls); tcls_destroy(&tcls); } @@ -1094,7 +1182,7 @@ next_random_flow(struct flow *flow, unsigned int idx) } } } - NOT_REACHED(); + OVS_NOT_REACHED(); } /* 16 randomly chosen flows with N >= 3 nonzero values. */ @@ -1184,7 +1272,8 @@ test_miniflow(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) /* Check that the flow equals its miniflow. */ assert(miniflow_get_vid(&miniflow) == vlan_tci_to_vid(flow.vlan_tci)); for (i = 0; i < FLOW_U32S; i++) { - assert(miniflow_get(&miniflow, i) == flow_u32[i]); + assert(MINIFLOW_GET_TYPE(&miniflow, uint32_t, i * 4) + == flow_u32[i]); } /* Check that the miniflow equals itself. */ @@ -1310,28 +1399,29 @@ test_minimask_combine(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) static const struct command commands[] = { /* Classifier tests. */ - {"empty", 0, 0, test_empty}, - {"destroy-null", 0, 0, test_destroy_null}, - {"single-rule", 0, 0, test_single_rule}, - {"rule-replacement", 0, 0, test_rule_replacement}, - {"many-rules-in-one-list", 0, 0, test_many_rules_in_one_list}, - {"many-rules-in-one-table", 0, 0, test_many_rules_in_one_table}, - {"many-rules-in-two-tables", 0, 0, test_many_rules_in_two_tables}, - {"many-rules-in-five-tables", 0, 0, test_many_rules_in_five_tables}, + {"empty", NULL, 0, 0, test_empty}, + {"destroy-null", NULL, 0, 0, test_destroy_null}, + {"single-rule", NULL, 0, 0, test_single_rule}, + {"rule-replacement", NULL, 0, 0, test_rule_replacement}, + {"many-rules-in-one-list", NULL, 0, 0, test_many_rules_in_one_list}, + {"many-rules-in-one-table", NULL, 0, 0, test_many_rules_in_one_table}, + {"many-rules-in-two-tables", NULL, 0, 0, test_many_rules_in_two_tables}, + {"many-rules-in-five-tables", NULL, 0, 0, test_many_rules_in_five_tables}, /* Miniflow and minimask tests. */ - {"miniflow", 0, 0, test_miniflow}, - {"minimask_has_extra", 0, 0, test_minimask_has_extra}, - {"minimask_combine", 0, 0, test_minimask_combine}, + {"miniflow", NULL, 0, 0, test_miniflow}, + {"minimask_has_extra", NULL, 0, 0, test_minimask_has_extra}, + {"minimask_combine", NULL, 0, 0, test_minimask_combine}, - {NULL, 0, 0, NULL}, + {NULL, NULL, 0, 0, NULL}, }; -int -main(int argc, char *argv[]) +static void +test_classifier_main(int argc, char *argv[]) { set_program_name(argv[0]); init_values(); run_command(argc - 1, argv + 1, commands); - return 0; } + +OVSTEST_REGISTER("test-classifier", test_classifier_main);