datapath: Avoid pskb_may_pull() checks where not needed.
[openvswitch] / tests / test-classifier.c
1 /*
2  * Copyright (c) 2009, 2010 Nicira Networks.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 /* "White box" tests for classifier.
18  *
19  * With very few exceptions, these tests obtain complete coverage of every
20  * basic block and every branch in the classifier implementation, e.g. a clean
21  * report from "gcov -b".  (Covering the exceptions would require finding
22  * collisions in the hash function used for flow data, etc.)
23  *
24  * This test should receive a clean report from "valgrind --leak-check=full":
25  * it frees every heap block that it allocates.
26  */
27
28 #include <config.h>
29 #include "classifier.h"
30 #include <errno.h>
31 #include <limits.h>
32 #include "command-line.h"
33 #include "flow.h"
34 #include "packets.h"
35
36 #undef NDEBUG
37 #include <assert.h>
38
39 struct test_rule {
40     int aux;                    /* Auxiliary data. */
41     struct cls_rule cls_rule;   /* Classifier rule data. */
42 };
43
44 static struct test_rule *
45 test_rule_from_cls_rule(const struct cls_rule *rule)
46 {
47     return rule ? CONTAINER_OF(rule, struct test_rule, cls_rule) : NULL;
48 }
49
50 /* Trivial (linear) classifier. */
51 struct tcls {
52     size_t n_rules;
53     size_t allocated_rules;
54     struct test_rule **rules;
55 };
56
57 static void
58 tcls_init(struct tcls *tcls)
59 {
60     tcls->n_rules = 0;
61     tcls->allocated_rules = 0;
62     tcls->rules = NULL;
63 }
64
65 static void
66 tcls_destroy(struct tcls *tcls)
67 {
68     if (tcls) {
69         size_t i;
70
71         for (i = 0; i < tcls->n_rules; i++) {
72             free(tcls->rules[i]);
73         }
74         free(tcls->rules);
75     }
76 }
77
78 static int
79 tcls_count_exact(const struct tcls *tcls)
80 {
81     int n_exact;
82     size_t i;
83
84     n_exact = 0;
85     for (i = 0; i < tcls->n_rules; i++) {
86         n_exact += tcls->rules[i]->cls_rule.wc.wildcards == 0;
87     }
88     return n_exact;
89 }
90
91 static bool
92 tcls_is_empty(const struct tcls *tcls)
93 {
94     return tcls->n_rules == 0;
95 }
96
97 static struct test_rule *
98 tcls_insert(struct tcls *tcls, const struct test_rule *rule)
99 {
100     size_t i;
101
102     assert(rule->cls_rule.wc.wildcards || rule->cls_rule.priority == UINT_MAX);
103     for (i = 0; i < tcls->n_rules; i++) {
104         const struct cls_rule *pos = &tcls->rules[i]->cls_rule;
105         if (pos->priority == rule->cls_rule.priority
106             && pos->wc.wildcards == rule->cls_rule.wc.wildcards
107             && flow_equal(&pos->flow, &rule->cls_rule.flow)) {
108             /* Exact match.
109              * XXX flow_equal should ignore wildcarded fields */
110             free(tcls->rules[i]);
111             tcls->rules[i] = xmemdup(rule, sizeof *rule);
112             return tcls->rules[i];
113         } else if (pos->priority < rule->cls_rule.priority) {
114             break;
115         }
116     }
117
118     if (tcls->n_rules >= tcls->allocated_rules) {
119         tcls->rules = x2nrealloc(tcls->rules, &tcls->allocated_rules,
120                                  sizeof *tcls->rules);
121     }
122     if (i != tcls->n_rules) {
123         memmove(&tcls->rules[i + 1], &tcls->rules[i],
124                 sizeof *tcls->rules * (tcls->n_rules - i));
125     }
126     tcls->rules[i] = xmemdup(rule, sizeof *rule);
127     tcls->n_rules++;
128     return tcls->rules[i];
129 }
130
131 static void
132 tcls_remove(struct tcls *cls, const struct test_rule *rule)
133 {
134     size_t i;
135
136     for (i = 0; i < cls->n_rules; i++) {
137         struct test_rule *pos = cls->rules[i];
138         if (pos == rule) {
139             free(pos);
140             memmove(&cls->rules[i], &cls->rules[i + 1],
141                     sizeof *cls->rules * (cls->n_rules - i - 1));
142             cls->n_rules--;
143             return;
144         }
145     }
146     NOT_REACHED();
147 }
148
149 static uint32_t
150 read_uint32(const void *p)
151 {
152     uint32_t x;
153     memcpy(&x, p, sizeof x);
154     return x;
155 }
156
157 static bool
158 match(const struct cls_rule *wild, const flow_t *fixed)
159 {
160     int f_idx;
161
162     for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) {
163         const struct cls_field *f = &cls_fields[f_idx];
164         void *wild_field = (char *) &wild->flow + f->ofs;
165         void *fixed_field = (char *) fixed + f->ofs;
166
167         if ((wild->wc.wildcards & f->wildcards) == f->wildcards ||
168             !memcmp(wild_field, fixed_field, f->len)) {
169             /* Definite match. */
170             continue;
171         }
172
173         if (wild->wc.wildcards & f->wildcards) {
174             uint32_t test = read_uint32(wild_field);
175             uint32_t ip = read_uint32(fixed_field);
176             int shift = (f_idx == CLS_F_IDX_NW_SRC
177                          ? OFPFW_NW_SRC_SHIFT : OFPFW_NW_DST_SHIFT);
178             uint32_t mask = flow_nw_bits_to_mask(wild->wc.wildcards, shift);
179             if (!((test ^ ip) & mask)) {
180                 continue;
181             }
182         }
183
184         return false;
185     }
186     return true;
187 }
188
189 static struct cls_rule *
190 tcls_lookup(const struct tcls *cls, const flow_t *flow, int include)
191 {
192     size_t i;
193
194     for (i = 0; i < cls->n_rules; i++) {
195         struct test_rule *pos = cls->rules[i];
196         uint32_t wildcards = pos->cls_rule.wc.wildcards;
197         if (include & (wildcards ? CLS_INC_WILD : CLS_INC_EXACT)
198             && match(&pos->cls_rule, flow)) {
199             return &pos->cls_rule;
200         }
201     }
202     return NULL;
203 }
204
205 static void
206 tcls_delete_matches(struct tcls *cls,
207                     const struct cls_rule *target,
208                     int include)
209 {
210     size_t i;
211
212     for (i = 0; i < cls->n_rules; ) {
213         struct test_rule *pos = cls->rules[i];
214         uint32_t wildcards = pos->cls_rule.wc.wildcards;
215         if (include & (wildcards ? CLS_INC_WILD : CLS_INC_EXACT)
216             && match(target, &pos->cls_rule.flow)) {
217             tcls_remove(cls, pos);
218         } else {
219             i++;
220         }
221     }
222 }
223 \f
224 #ifdef WORDS_BIGENDIAN
225 #define T_HTONL(VALUE) ((uint32_t) (VALUE))
226 #define T_HTONS(VALUE) ((uint32_t) (VALUE))
227 #else
228 #define T_HTONL(VALUE) (((((uint32_t) (VALUE)) & 0x000000ff) << 24) | \
229                       ((((uint32_t) (VALUE)) & 0x0000ff00) <<  8) | \
230                       ((((uint32_t) (VALUE)) & 0x00ff0000) >>  8) | \
231                       ((((uint32_t) (VALUE)) & 0xff000000) >> 24))
232 #define T_HTONS(VALUE) (((((uint16_t) (VALUE)) & 0xff00) >> 8) |  \
233                       ((((uint16_t) (VALUE)) & 0x00ff) << 8))
234 #endif
235
236 static uint32_t nw_src_values[] = { T_HTONL(0xc0a80001),
237                                     T_HTONL(0xc0a04455) };
238 static uint32_t nw_dst_values[] = { T_HTONL(0xc0a80002),
239                                     T_HTONL(0xc0a04455) };
240 static uint32_t tun_id_values[] = { 0, 0xffff0000 };
241 static uint16_t in_port_values[] = { T_HTONS(1), T_HTONS(OFPP_LOCAL) };
242 static uint16_t dl_vlan_values[] = { T_HTONS(101), T_HTONS(0) };
243 static uint8_t dl_vlan_pcp_values[] = { 7, 0 };
244 static uint16_t dl_type_values[]
245             = { T_HTONS(ETH_TYPE_IP), T_HTONS(ETH_TYPE_ARP) };
246 static uint16_t tp_src_values[] = { T_HTONS(49362), T_HTONS(80) };
247 static uint16_t tp_dst_values[] = { T_HTONS(6667), T_HTONS(22) };
248 static uint8_t dl_src_values[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 },
249                                       { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } };
250 static uint8_t dl_dst_values[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 },
251                                       { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
252 static uint8_t nw_proto_values[] = { IP_TYPE_TCP, IP_TYPE_ICMP };
253 static uint8_t nw_tos_values[] = { 49, 0 };
254
255 static void *values[CLS_N_FIELDS][2];
256
257 static void
258 init_values(void)
259 {
260     values[CLS_F_IDX_TUN_ID][0] = &tun_id_values[0];
261     values[CLS_F_IDX_TUN_ID][1] = &tun_id_values[1];
262
263     values[CLS_F_IDX_IN_PORT][0] = &in_port_values[0];
264     values[CLS_F_IDX_IN_PORT][1] = &in_port_values[1];
265
266     values[CLS_F_IDX_DL_VLAN][0] = &dl_vlan_values[0];
267     values[CLS_F_IDX_DL_VLAN][1] = &dl_vlan_values[1];
268
269     values[CLS_F_IDX_DL_VLAN_PCP][0] = &dl_vlan_pcp_values[0];
270     values[CLS_F_IDX_DL_VLAN_PCP][1] = &dl_vlan_pcp_values[1];
271
272     values[CLS_F_IDX_DL_SRC][0] = dl_src_values[0];
273     values[CLS_F_IDX_DL_SRC][1] = dl_src_values[1];
274
275     values[CLS_F_IDX_DL_DST][0] = dl_dst_values[0];
276     values[CLS_F_IDX_DL_DST][1] = dl_dst_values[1];
277
278     values[CLS_F_IDX_DL_TYPE][0] = &dl_type_values[0];
279     values[CLS_F_IDX_DL_TYPE][1] = &dl_type_values[1];
280
281     values[CLS_F_IDX_NW_SRC][0] = &nw_src_values[0];
282     values[CLS_F_IDX_NW_SRC][1] = &nw_src_values[1];
283
284     values[CLS_F_IDX_NW_DST][0] = &nw_dst_values[0];
285     values[CLS_F_IDX_NW_DST][1] = &nw_dst_values[1];
286
287     values[CLS_F_IDX_NW_PROTO][0] = &nw_proto_values[0];
288     values[CLS_F_IDX_NW_PROTO][1] = &nw_proto_values[1];
289
290     values[CLS_F_IDX_NW_TOS][0] = &nw_tos_values[0];
291     values[CLS_F_IDX_NW_TOS][1] = &nw_tos_values[1];
292
293     values[CLS_F_IDX_TP_SRC][0] = &tp_src_values[0];
294     values[CLS_F_IDX_TP_SRC][1] = &tp_src_values[1];
295
296     values[CLS_F_IDX_TP_DST][0] = &tp_dst_values[0];
297     values[CLS_F_IDX_TP_DST][1] = &tp_dst_values[1];
298 }
299
300 #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
301 #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
302 #define N_TUN_ID_VALUES ARRAY_SIZE(tun_id_values)
303 #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
304 #define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values)
305 #define N_DL_VLAN_PCP_VALUES ARRAY_SIZE(dl_vlan_pcp_values)
306 #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
307 #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
308 #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
309 #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
310 #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
311 #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
312 #define N_NW_TOS_VALUES ARRAY_SIZE(nw_tos_values)
313
314 #define N_FLOW_VALUES (N_NW_SRC_VALUES *        \
315                        N_NW_DST_VALUES *        \
316                        N_TUN_ID_VALUES *        \
317                        N_IN_PORT_VALUES *       \
318                        N_DL_VLAN_VALUES *       \
319                        N_DL_VLAN_PCP_VALUES *   \
320                        N_DL_TYPE_VALUES *       \
321                        N_TP_SRC_VALUES *        \
322                        N_TP_DST_VALUES *        \
323                        N_DL_SRC_VALUES *        \
324                        N_DL_DST_VALUES *        \
325                        N_NW_PROTO_VALUES *      \
326                        N_NW_TOS_VALUES)
327
328 static unsigned int
329 get_value(unsigned int *x, unsigned n_values)
330 {
331     unsigned int rem = *x % n_values;
332     *x /= n_values;
333     return rem;
334 }
335
336 static struct cls_rule *
337 lookup_with_include_bits(const struct classifier *cls,
338                          const flow_t *flow, int include)
339 {
340     switch (include) {
341     case CLS_INC_WILD:
342         return classifier_lookup_wild(cls, flow);
343     case CLS_INC_EXACT:
344         return classifier_lookup_exact(cls, flow);
345     case CLS_INC_WILD | CLS_INC_EXACT:
346         return classifier_lookup(cls, flow);
347     default:
348         abort();
349     }
350 }
351
352 static void
353 compare_classifiers(struct classifier *cls, struct tcls *tcls)
354 {
355     static const int confidence = 500;
356     unsigned int i;
357
358     assert(classifier_count(cls) == tcls->n_rules);
359     assert(classifier_count_exact(cls) == tcls_count_exact(tcls));
360     for (i = 0; i < confidence; i++) {
361         struct cls_rule *cr0, *cr1;
362         flow_t flow;
363         unsigned int x;
364         int include;
365
366         x = rand () % N_FLOW_VALUES;
367         flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)];
368         flow.nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)];
369         flow.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)];
370         flow.in_port = in_port_values[get_value(&x, N_IN_PORT_VALUES)];
371         flow.dl_vlan = dl_vlan_values[get_value(&x, N_DL_VLAN_VALUES)];
372         flow.dl_vlan_pcp = dl_vlan_pcp_values[get_value(&x,
373                 N_DL_VLAN_PCP_VALUES)];
374         flow.dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)];
375         flow.tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)];
376         flow.tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)];
377         memcpy(flow.dl_src, dl_src_values[get_value(&x, N_DL_SRC_VALUES)],
378                ETH_ADDR_LEN);
379         memcpy(flow.dl_dst, dl_dst_values[get_value(&x, N_DL_DST_VALUES)],
380                ETH_ADDR_LEN);
381         flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)];
382         flow.nw_tos = nw_tos_values[get_value(&x, N_NW_TOS_VALUES)];
383         memset(flow.reserved, 0, sizeof flow.reserved);
384
385         for (include = 1; include <= 3; include++) {
386             cr0 = lookup_with_include_bits(cls, &flow, include);
387             cr1 = tcls_lookup(tcls, &flow, include);
388             assert((cr0 == NULL) == (cr1 == NULL));
389             if (cr0 != NULL) {
390                 const struct test_rule *tr0 = test_rule_from_cls_rule(cr0);
391                 const struct test_rule *tr1 = test_rule_from_cls_rule(cr1);
392
393                 assert(flow_equal(&cr0->flow, &cr1->flow));
394                 assert(cr0->wc.wildcards == cr1->wc.wildcards);
395                 assert(cr0->priority == cr1->priority);
396                 /* Skip nw_src_mask and nw_dst_mask, because they are derived
397                  * members whose values are used only for optimization. */
398                 assert(tr0->aux == tr1->aux);
399             }
400         }
401     }
402 }
403
404 static void
405 free_rule(struct cls_rule *cls_rule, void *cls)
406 {
407     classifier_remove(cls, cls_rule);
408     free(test_rule_from_cls_rule(cls_rule));
409 }
410
411 static void
412 destroy_classifier(struct classifier *cls)
413 {
414     classifier_for_each(cls, CLS_INC_ALL, free_rule, cls);
415     classifier_destroy(cls);
416 }
417
418 static void
419 check_tables(const struct classifier *cls,
420              int n_tables, int n_buckets, int n_rules)
421 {
422     int found_tables = 0;
423     int found_buckets = 0;
424     int found_rules = 0;
425     int i;
426
427     BUILD_ASSERT(CLS_N_FIELDS == ARRAY_SIZE(cls->tables));
428     for (i = 0; i < CLS_N_FIELDS; i++) {
429         const struct cls_bucket *bucket;
430         if (!hmap_is_empty(&cls->tables[i])) {
431             found_tables++;
432         }
433         HMAP_FOR_EACH (bucket, struct cls_bucket, hmap_node, &cls->tables[i]) {
434             found_buckets++;
435             assert(!list_is_empty(&bucket->rules));
436             found_rules += list_size(&bucket->rules);
437         }
438     }
439
440     if (!hmap_is_empty(&cls->exact_table)) {
441         found_tables++;
442         found_buckets++;
443         found_rules += hmap_count(&cls->exact_table);
444     }
445
446     assert(n_tables == -1 || found_tables == n_tables);
447     assert(n_rules == -1 || found_rules == n_rules);
448     assert(n_buckets == -1 || found_buckets == n_buckets);
449 }
450
451 static struct test_rule *
452 make_rule(int wc_fields, unsigned int priority, int value_pat)
453 {
454     const struct cls_field *f;
455     struct test_rule *rule;
456     uint32_t wildcards;
457     flow_t flow;
458
459     wildcards = 0;
460     memset(&flow, 0, sizeof flow);
461     for (f = &cls_fields[0]; f < &cls_fields[CLS_N_FIELDS]; f++) {
462         int f_idx = f - cls_fields;
463         if (wc_fields & (1u << f_idx)) {
464             wildcards |= f->wildcards;
465         } else {
466             int value_idx = (value_pat & (1u << f_idx)) != 0;
467             memcpy((char *) &flow + f->ofs, values[f_idx][value_idx], f->len);
468         }
469     }
470
471     rule = xzalloc(sizeof *rule);
472     cls_rule_from_flow(&flow, wildcards, !wildcards ? UINT_MAX : priority,
473                        &rule->cls_rule);
474     return rule;
475 }
476
477 static void
478 shuffle(unsigned int *p, size_t n)
479 {
480     for (; n > 1; n--, p++) {
481         unsigned int *q = &p[rand() % n];
482         unsigned int tmp = *p;
483         *p = *q;
484         *q = tmp;
485     }
486 }
487 \f
488 /* Tests an empty classifier. */
489 static void
490 test_empty(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
491 {
492     struct classifier cls;
493     struct tcls tcls;
494
495     classifier_init(&cls);
496     tcls_init(&tcls);
497     assert(classifier_is_empty(&cls));
498     assert(tcls_is_empty(&tcls));
499     compare_classifiers(&cls, &tcls);
500     classifier_destroy(&cls);
501     tcls_destroy(&tcls);
502 }
503
504 /* Destroys a null classifier. */
505 static void
506 test_destroy_null(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
507 {
508     classifier_destroy(NULL);
509 }
510
511 /* Tests classification with one rule at a time. */
512 static void
513 test_single_rule(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
514 {
515     unsigned int wc_fields;     /* Hilarious. */
516
517     for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) {
518         struct classifier cls;
519         struct test_rule *rule, *tcls_rule;
520         struct tcls tcls;
521
522         rule = make_rule(wc_fields,
523                          hash_bytes(&wc_fields, sizeof wc_fields, 0), 0);
524
525         classifier_init(&cls);
526         tcls_init(&tcls);
527
528         tcls_rule = tcls_insert(&tcls, rule);
529         if (wc_fields) {
530             assert(!classifier_insert(&cls, &rule->cls_rule));
531         } else {
532             classifier_insert_exact(&cls, &rule->cls_rule);
533         }
534         check_tables(&cls, 1, 1, 1);
535         compare_classifiers(&cls, &tcls);
536
537         classifier_remove(&cls, &rule->cls_rule);
538         tcls_remove(&tcls, tcls_rule);
539         assert(classifier_is_empty(&cls));
540         assert(tcls_is_empty(&tcls));
541         compare_classifiers(&cls, &tcls);
542
543         free(rule);
544         classifier_destroy(&cls);
545         tcls_destroy(&tcls);
546     }
547 }
548
549 /* Tests replacing one rule by another. */
550 static void
551 test_rule_replacement(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
552 {
553     unsigned int wc_fields;
554
555     for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) {
556         struct classifier cls;
557         struct test_rule *rule1;
558         struct test_rule *rule2;
559         struct tcls tcls;
560
561         rule1 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX);
562         rule2 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX);
563         rule2->aux += 5;
564         rule2->aux += 5;
565
566         classifier_init(&cls);
567         tcls_init(&tcls);
568         tcls_insert(&tcls, rule1);
569         assert(!classifier_insert(&cls, &rule1->cls_rule));
570         check_tables(&cls, 1, 1, 1);
571         compare_classifiers(&cls, &tcls);
572         tcls_destroy(&tcls);
573
574         tcls_init(&tcls);
575         tcls_insert(&tcls, rule2);
576         assert(test_rule_from_cls_rule(
577                    classifier_insert(&cls, &rule2->cls_rule)) == rule1);
578         free(rule1);
579         check_tables(&cls, 1, 1, 1);
580         compare_classifiers(&cls, &tcls);
581         tcls_destroy(&tcls);
582         destroy_classifier(&cls);
583     }
584 }
585
586 static int
587 table_mask(int table)
588 {
589     return ((1u << CLS_N_FIELDS) - 1) & ~((1u << table) - 1);
590 }
591
592 static int
593 random_wcf_in_table(int table, int seed)
594 {
595     int wc_fields = (1u << table) | hash_int(seed, 0);
596     return wc_fields & table_mask(table);
597 }
598
599 /* Tests classification with two rules at a time that fall into the same
600  * bucket. */
601 static void
602 test_two_rules_in_one_bucket(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
603 {
604     int table, rel_pri, wcf_pat, value_pat;
605
606     for (table = 0; table <= CLS_N_FIELDS; table++) {
607         for (rel_pri = -1; rel_pri <= +1; rel_pri++) {
608             for (wcf_pat = 0; wcf_pat < 4; wcf_pat++) {
609                 int n_value_pats = table == CLS_N_FIELDS - 1 ? 1 : 2;
610                 for (value_pat = 0; value_pat < n_value_pats; value_pat++) {
611                     struct test_rule *rule1, *tcls_rule1;
612                     struct test_rule *rule2, *tcls_rule2;
613                     struct test_rule *displaced_rule;
614                     struct classifier cls;
615                     struct tcls tcls;
616                     unsigned int pri1, pri2;
617                     int wcf1, wcf2;
618
619                     if (table != CLS_F_IDX_EXACT) {
620                         /* We can use identical priorities in this test because
621                          * the classifier always chooses the rule added later
622                          * for equal-priority rules that fall into the same
623                          * bucket.  */
624                         pri1 = table * 257 + 50;
625                         pri2 = pri1 + rel_pri;
626
627                         wcf1 = (wcf_pat & 1
628                                 ? random_wcf_in_table(table, pri1)
629                                 : 1u << table);
630                         wcf2 = (wcf_pat & 2
631                                 ? random_wcf_in_table(table, pri2)
632                                 : 1u << table);
633                         if (value_pat) {
634                             wcf1 &= ~(1u << (CLS_N_FIELDS - 1));
635                             wcf2 &= ~(1u << (CLS_N_FIELDS - 1));
636                         }
637                     } else {
638                         /* This classifier always puts exact-match rules at
639                          * maximum priority.  */
640                         pri1 = pri2 = UINT_MAX;
641
642                         /* No wildcard fields. */
643                         wcf1 = wcf2 = 0;
644                     }
645
646                     rule1 = make_rule(wcf1, pri1, 0);
647                     rule2 = make_rule(wcf2, pri2,
648                                       value_pat << (CLS_N_FIELDS - 1));
649
650                     classifier_init(&cls);
651                     tcls_init(&tcls);
652
653                     tcls_rule1 = tcls_insert(&tcls, rule1);
654                     tcls_rule2 = tcls_insert(&tcls, rule2);
655                     assert(!classifier_insert(&cls, &rule1->cls_rule));
656                     displaced_rule = test_rule_from_cls_rule(
657                         classifier_insert(&cls, &rule2->cls_rule));
658                     if (wcf1 != wcf2 || pri1 != pri2 || value_pat) {
659                         assert(!displaced_rule);
660
661                         check_tables(&cls, 1, 1, 2);
662                         compare_classifiers(&cls, &tcls);
663
664                         classifier_remove(&cls, &rule1->cls_rule);
665                         tcls_remove(&tcls, tcls_rule1);
666                         check_tables(&cls, 1, 1, 1);
667                         compare_classifiers(&cls, &tcls);
668                     } else {
669                         assert(displaced_rule == rule1);
670                         check_tables(&cls, 1, 1, 1);
671                         compare_classifiers(&cls, &tcls);
672                     }
673                     free(rule1);
674
675                     classifier_remove(&cls, &rule2->cls_rule);
676                     tcls_remove(&tcls, tcls_rule2);
677                     compare_classifiers(&cls, &tcls);
678                     free(rule2);
679
680                     destroy_classifier(&cls);
681                     tcls_destroy(&tcls);
682                 }
683             }
684         }
685     }
686 }
687
688 /* Tests classification with two rules at a time that fall into the same
689  * table but different buckets. */
690 static void
691 test_two_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
692 {
693     int table, rel_pri, wcf_pat;
694
695     /* Skip tables 0 and CLS_F_IDX_EXACT because they have one bucket. */
696     for (table = 1; table < CLS_N_FIELDS; table++) {
697         for (rel_pri = -1; rel_pri <= +1; rel_pri++) {
698             for (wcf_pat = 0; wcf_pat < 5; wcf_pat++) {
699                 struct test_rule *rule1, *tcls_rule1;
700                 struct test_rule *rule2, *tcls_rule2;
701                 struct classifier cls;
702                 struct tcls tcls;
703                 unsigned int pri1, pri2;
704                 int wcf1, wcf2;
705                 int value_mask, value_pat1, value_pat2;
706                 int i;
707
708                 /* We can use identical priorities in this test because the
709                  * classifier always chooses the rule added later for
710                  * equal-priority rules that fall into the same table.  */
711                 pri1 = table * 257 + 50;
712                 pri2 = pri1 + rel_pri;
713
714                 if (wcf_pat & 4) {
715                     wcf1 = wcf2 = random_wcf_in_table(table, pri1);
716                 } else {
717                     wcf1 = (wcf_pat & 1
718                             ? random_wcf_in_table(table, pri1)
719                             : 1u << table);
720                     wcf2 = (wcf_pat & 2
721                             ? random_wcf_in_table(table, pri2)
722                             : 1u << table);
723                 }
724
725                 /* Generate value patterns that will put the two rules into
726                  * different buckets. */
727                 value_mask = ((1u << table) - 1);
728                 value_pat1 = hash_int(pri1, 1) & value_mask;
729                 i = 0;
730                 do {
731                     value_pat2 = (hash_int(pri2, i++) & value_mask);
732                 } while (value_pat1 == value_pat2);
733                 rule1 = make_rule(wcf1, pri1, value_pat1);
734                 rule2 = make_rule(wcf2, pri2, value_pat2);
735
736                 classifier_init(&cls);
737                 tcls_init(&tcls);
738
739                 tcls_rule1 = tcls_insert(&tcls, rule1);
740                 tcls_rule2 = tcls_insert(&tcls, rule2);
741                 assert(!classifier_insert(&cls, &rule1->cls_rule));
742                 assert(!classifier_insert(&cls, &rule2->cls_rule));
743                 check_tables(&cls, 1, 2, 2);
744                 compare_classifiers(&cls, &tcls);
745
746                 classifier_remove(&cls, &rule1->cls_rule);
747                 tcls_remove(&tcls, tcls_rule1);
748                 check_tables(&cls, 1, 1, 1);
749                 compare_classifiers(&cls, &tcls);
750                 free(rule1);
751
752                 classifier_remove(&cls, &rule2->cls_rule);
753                 tcls_remove(&tcls, tcls_rule2);
754                 compare_classifiers(&cls, &tcls);
755                 free(rule2);
756
757                 classifier_destroy(&cls);
758                 tcls_destroy(&tcls);
759             }
760         }
761     }
762 }
763
764 /* Tests classification with two rules at a time that fall into different
765  * tables. */
766 static void
767 test_two_rules_in_different_tables(int argc OVS_UNUSED,
768                                    char *argv[] OVS_UNUSED)
769 {
770     int table1, table2, rel_pri, wcf_pat;
771
772     for (table1 = 0; table1 < CLS_N_FIELDS; table1++) {
773         for (table2 = table1 + 1; table2 <= CLS_N_FIELDS; table2++) {
774             for (rel_pri = 0; rel_pri < 2; rel_pri++) {
775                 for (wcf_pat = 0; wcf_pat < 4; wcf_pat++) {
776                     struct test_rule *rule1, *tcls_rule1;
777                     struct test_rule *rule2, *tcls_rule2;
778                     struct classifier cls;
779                     struct tcls tcls;
780                     unsigned int pri1, pri2;
781                     int wcf1, wcf2;
782
783                     /* We must use unique priorities in this test because the
784                      * classifier makes the rule choice undefined for rules of
785                      * equal priority that fall into different tables.  (In
786                      * practice, lower-numbered tables win.)  */
787                     pri1 = table1 * 257 + 50;
788                     pri2 = rel_pri ? pri1 - 1 : pri1 + 1;
789
790                     wcf1 = (wcf_pat & 1
791                             ? random_wcf_in_table(table1, pri1)
792                             : 1u << table1);
793                     wcf2 = (wcf_pat & 2
794                             ? random_wcf_in_table(table2, pri2)
795                             : 1u << table2);
796
797                     if (table2 == CLS_F_IDX_EXACT) {
798                         pri2 = UINT16_MAX;
799                         wcf2 = 0;
800                     }
801
802                     rule1 = make_rule(wcf1, pri1, 0);
803                     rule2 = make_rule(wcf2, pri2, 0);
804
805                     classifier_init(&cls);
806                     tcls_init(&tcls);
807
808                     tcls_rule1 = tcls_insert(&tcls, rule1);
809                     tcls_rule2 = tcls_insert(&tcls, rule2);
810                     assert(!classifier_insert(&cls, &rule1->cls_rule));
811                     assert(!classifier_insert(&cls, &rule2->cls_rule));
812                     check_tables(&cls, 2, 2, 2);
813                     compare_classifiers(&cls, &tcls);
814
815                     classifier_remove(&cls, &rule1->cls_rule);
816                     tcls_remove(&tcls, tcls_rule1);
817                     check_tables(&cls, 1, 1, 1);
818                     compare_classifiers(&cls, &tcls);
819                     free(rule1);
820
821                     classifier_remove(&cls, &rule2->cls_rule);
822                     tcls_remove(&tcls, tcls_rule2);
823                     compare_classifiers(&cls, &tcls);
824                     free(rule2);
825
826                     classifier_destroy(&cls);
827                     tcls_destroy(&tcls);
828                 }
829             }
830         }
831     }
832 }
833
834 /* Tests classification with many rules at a time that fall into the same
835  * bucket but have unique priorities (and various wildcards). */
836 static void
837 test_many_rules_in_one_bucket(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
838 {
839     enum { MAX_RULES = 50 };
840     int iteration, table;
841
842     for (iteration = 0; iteration < 3; iteration++) {
843         for (table = 0; table <= CLS_N_FIELDS; table++) {
844             unsigned int priorities[MAX_RULES];
845             struct classifier cls;
846             struct tcls tcls;
847             int i;
848
849             srand(hash_int(table, iteration));
850             for (i = 0; i < MAX_RULES; i++) {
851                 priorities[i] = i * 129;
852             }
853             shuffle(priorities, ARRAY_SIZE(priorities));
854
855             classifier_init(&cls);
856             tcls_init(&tcls);
857
858             for (i = 0; i < MAX_RULES; i++) {
859                 struct test_rule *rule;
860                 unsigned int priority = priorities[i];
861                 int wcf;
862
863                 wcf = random_wcf_in_table(table, priority);
864                 rule = make_rule(wcf, priority,
865                                  table == CLS_F_IDX_EXACT ? i : 1234);
866                 tcls_insert(&tcls, rule);
867                 assert(!classifier_insert(&cls, &rule->cls_rule));
868                 check_tables(&cls, 1, 1, i + 1);
869                 compare_classifiers(&cls, &tcls);
870             }
871
872             destroy_classifier(&cls);
873             tcls_destroy(&tcls);
874         }
875     }
876 }
877
878 /* Tests classification with many rules at a time that fall into the same
879  * table but random buckets. */
880 static void
881 test_many_rules_in_one_table(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
882 {
883     enum { MAX_RULES = 50 };
884     int iteration, table;
885
886     for (iteration = 0; iteration < 3; iteration++) {
887         for (table = 0; table < CLS_N_FIELDS; table++) {
888             unsigned int priorities[MAX_RULES];
889             struct classifier cls;
890             struct tcls tcls;
891             int i;
892
893             srand(hash_int(table, iteration));
894             for (i = 0; i < MAX_RULES; i++) {
895                 priorities[i] = i * 129;
896             }
897             shuffle(priorities, ARRAY_SIZE(priorities));
898
899             classifier_init(&cls);
900             tcls_init(&tcls);
901
902             for (i = 0; i < MAX_RULES; i++) {
903                 struct test_rule *rule;
904                 unsigned int priority = priorities[i];
905                 int wcf;
906
907                 wcf = random_wcf_in_table(table, priority);
908                 rule = make_rule(wcf, priority, hash_int(priority, 1));
909                 tcls_insert(&tcls, rule);
910                 assert(!classifier_insert(&cls, &rule->cls_rule));
911                 check_tables(&cls, 1, -1, i + 1);
912                 compare_classifiers(&cls, &tcls);
913             }
914
915             destroy_classifier(&cls);
916             tcls_destroy(&tcls);
917         }
918     }
919 }
920
921 /* Tests classification with many rules at a time that fall into random buckets
922  * in random tables. */
923 static void
924 test_many_rules_in_different_tables(int argc OVS_UNUSED,
925                                     char *argv[] OVS_UNUSED)
926 {
927     enum { MAX_RULES = 50 };
928     int iteration;
929
930     for (iteration = 0; iteration < 30; iteration++) {
931         unsigned int priorities[MAX_RULES];
932         struct classifier cls;
933         struct tcls tcls;
934         int i;
935
936         srand(iteration);
937         for (i = 0; i < MAX_RULES; i++) {
938             priorities[i] = i * 129;
939         }
940         shuffle(priorities, ARRAY_SIZE(priorities));
941
942         classifier_init(&cls);
943         tcls_init(&tcls);
944
945         for (i = 0; i < MAX_RULES; i++) {
946             struct test_rule *rule;
947             unsigned int priority = priorities[i];
948             int table = rand() % (CLS_N_FIELDS + 1);
949             int wcf = random_wcf_in_table(table, rand());
950             int value_pat = rand() & ((1u << CLS_N_FIELDS) - 1);
951             rule = make_rule(wcf, priority, value_pat);
952             tcls_insert(&tcls, rule);
953             assert(!classifier_insert(&cls, &rule->cls_rule));
954             check_tables(&cls, -1, -1, i + 1);
955             compare_classifiers(&cls, &tcls);
956         }
957
958         while (!classifier_is_empty(&cls)) {
959             struct test_rule *rule = xmemdup(tcls.rules[rand() % tcls.n_rules],
960                                              sizeof(struct test_rule));
961             int include = rand() % 2 ? CLS_INC_WILD : CLS_INC_EXACT;
962             include |= (rule->cls_rule.wc.wildcards
963                         ? CLS_INC_WILD : CLS_INC_EXACT);
964             classifier_for_each_match(&cls, &rule->cls_rule, include,
965                                       free_rule, &cls);
966             tcls_delete_matches(&tcls, &rule->cls_rule, include);
967             compare_classifiers(&cls, &tcls);
968             free(rule);
969         }
970
971         destroy_classifier(&cls);
972         tcls_destroy(&tcls);
973     }
974 }
975 \f
976 static const struct command commands[] = {
977     {"empty", 0, 0, test_empty},
978     {"destroy-null", 0, 0, test_destroy_null},
979     {"single-rule", 0, 0, test_single_rule},
980     {"rule-replacement", 0, 0, test_rule_replacement},
981     {"two-rules-in-one-bucket", 0, 0, test_two_rules_in_one_bucket},
982     {"two-rules-in-one-table", 0, 0, test_two_rules_in_one_table},
983     {"two-rules-in-different-tables", 0, 0,
984      test_two_rules_in_different_tables},
985     {"many-rules-in-one-bucket", 0, 0, test_many_rules_in_one_bucket},
986     {"many-rules-in-one-table", 0, 0, test_many_rules_in_one_table},
987     {"many-rules-in-different-tables", 0, 0,
988      test_many_rules_in_different_tables},
989     {NULL, 0, 0, NULL},
990 };
991
992 int
993 main(int argc, char *argv[])
994 {
995     init_values();
996     run_command(argc - 1, argv + 1, commands);
997     return 0;
998 }