2 * Copyright (c) 2009, 2010 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 /* "White box" tests for classifier.
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.)
24 * This test should receive a clean report from "valgrind --leak-check=full":
25 * it frees every heap block that it allocates.
30 #include "classifier.h"
41 int aux
; /* Auxiliary data. */
42 struct cls_rule cls_rule
; /* Classifier rule data. */
45 static struct test_rule
*
46 test_rule_from_cls_rule(const struct cls_rule
*rule
)
48 return rule
? CONTAINER_OF(rule
, struct test_rule
, cls_rule
) : NULL
;
51 /* Trivial (linear) classifier. */
54 size_t allocated_rules
;
55 struct test_rule
**rules
;
59 tcls_init(struct tcls
*tcls
)
62 tcls
->allocated_rules
= 0;
67 tcls_destroy(struct tcls
*tcls
)
72 for (i
= 0; i
< tcls
->n_rules
; i
++) {
80 tcls_count_exact(const struct tcls
*tcls
)
86 for (i
= 0; i
< tcls
->n_rules
; i
++) {
87 n_exact
+= tcls
->rules
[i
]->cls_rule
.wc
.wildcards
== 0;
93 tcls_is_empty(const struct tcls
*tcls
)
95 return tcls
->n_rules
== 0;
98 static struct test_rule
*
99 tcls_insert(struct tcls
*tcls
, const struct test_rule
*rule
)
103 assert(rule
->cls_rule
.wc
.wildcards
|| rule
->cls_rule
.priority
== UINT_MAX
);
104 for (i
= 0; i
< tcls
->n_rules
; i
++) {
105 const struct cls_rule
*pos
= &tcls
->rules
[i
]->cls_rule
;
106 if (pos
->priority
== rule
->cls_rule
.priority
107 && pos
->wc
.wildcards
== rule
->cls_rule
.wc
.wildcards
108 && flow_equal(&pos
->flow
, &rule
->cls_rule
.flow
)) {
110 * XXX flow_equal should ignore wildcarded fields */
111 free(tcls
->rules
[i
]);
112 tcls
->rules
[i
] = xmemdup(rule
, sizeof *rule
);
113 return tcls
->rules
[i
];
114 } else if (pos
->priority
< rule
->cls_rule
.priority
) {
119 if (tcls
->n_rules
>= tcls
->allocated_rules
) {
120 tcls
->rules
= x2nrealloc(tcls
->rules
, &tcls
->allocated_rules
,
121 sizeof *tcls
->rules
);
123 if (i
!= tcls
->n_rules
) {
124 memmove(&tcls
->rules
[i
+ 1], &tcls
->rules
[i
],
125 sizeof *tcls
->rules
* (tcls
->n_rules
- i
));
127 tcls
->rules
[i
] = xmemdup(rule
, sizeof *rule
);
129 return tcls
->rules
[i
];
133 tcls_remove(struct tcls
*cls
, const struct test_rule
*rule
)
137 for (i
= 0; i
< cls
->n_rules
; i
++) {
138 struct test_rule
*pos
= cls
->rules
[i
];
141 memmove(&cls
->rules
[i
], &cls
->rules
[i
+ 1],
142 sizeof *cls
->rules
* (cls
->n_rules
- i
- 1));
151 read_uint32(const void *p
)
154 memcpy(&x
, p
, sizeof x
);
159 match(const struct cls_rule
*wild
, const flow_t
*fixed
)
163 for (f_idx
= 0; f_idx
< CLS_N_FIELDS
; f_idx
++) {
164 const struct cls_field
*f
= &cls_fields
[f_idx
];
165 void *wild_field
= (char *) &wild
->flow
+ f
->ofs
;
166 void *fixed_field
= (char *) fixed
+ f
->ofs
;
168 if ((wild
->wc
.wildcards
& f
->wildcards
) == f
->wildcards
||
169 !memcmp(wild_field
, fixed_field
, f
->len
)) {
170 /* Definite match. */
174 if (wild
->wc
.wildcards
& f
->wildcards
) {
175 uint32_t test
= read_uint32(wild_field
);
176 uint32_t ip
= read_uint32(fixed_field
);
177 int shift
= (f_idx
== CLS_F_IDX_NW_SRC
178 ? OFPFW_NW_SRC_SHIFT
: OFPFW_NW_DST_SHIFT
);
179 uint32_t mask
= flow_nw_bits_to_mask(wild
->wc
.wildcards
, shift
);
180 if (!((test
^ ip
) & mask
)) {
190 static struct cls_rule
*
191 tcls_lookup(const struct tcls
*cls
, const flow_t
*flow
, int include
)
195 for (i
= 0; i
< cls
->n_rules
; i
++) {
196 struct test_rule
*pos
= cls
->rules
[i
];
197 uint32_t wildcards
= pos
->cls_rule
.wc
.wildcards
;
198 if (include
& (wildcards
? CLS_INC_WILD
: CLS_INC_EXACT
)
199 && match(&pos
->cls_rule
, flow
)) {
200 return &pos
->cls_rule
;
207 tcls_delete_matches(struct tcls
*cls
,
208 const struct cls_rule
*target
,
213 for (i
= 0; i
< cls
->n_rules
; ) {
214 struct test_rule
*pos
= cls
->rules
[i
];
215 uint32_t wildcards
= pos
->cls_rule
.wc
.wildcards
;
216 if (include
& (wildcards
? CLS_INC_WILD
: CLS_INC_EXACT
)
217 && match(target
, &pos
->cls_rule
.flow
)) {
218 tcls_remove(cls
, pos
);
225 #ifdef WORDS_BIGENDIAN
226 #define T_HTONL(VALUE) ((uint32_t) (VALUE))
227 #define T_HTONS(VALUE) ((uint32_t) (VALUE))
229 #define T_HTONL(VALUE) (((((uint32_t) (VALUE)) & 0x000000ff) << 24) | \
230 ((((uint32_t) (VALUE)) & 0x0000ff00) << 8) | \
231 ((((uint32_t) (VALUE)) & 0x00ff0000) >> 8) | \
232 ((((uint32_t) (VALUE)) & 0xff000000) >> 24))
233 #define T_HTONS(VALUE) (((((uint16_t) (VALUE)) & 0xff00) >> 8) | \
234 ((((uint16_t) (VALUE)) & 0x00ff) << 8))
237 static uint32_t nw_src_values
[] = { T_HTONL(0xc0a80001),
238 T_HTONL(0xc0a04455) };
239 static uint32_t nw_dst_values
[] = { T_HTONL(0xc0a80002),
240 T_HTONL(0xc0a04455) };
241 static uint32_t tun_id_values
[] = { 0, 0xffff0000 };
242 static uint16_t in_port_values
[] = { T_HTONS(1), T_HTONS(OFPP_LOCAL
) };
243 static uint16_t dl_vlan_values
[] = { T_HTONS(101), T_HTONS(0) };
244 static uint8_t dl_vlan_pcp_values
[] = { 7, 0 };
245 static uint16_t dl_type_values
[]
246 = { T_HTONS(ETH_TYPE_IP
), T_HTONS(ETH_TYPE_ARP
) };
247 static uint16_t tp_src_values
[] = { T_HTONS(49362), T_HTONS(80) };
248 static uint16_t tp_dst_values
[] = { T_HTONS(6667), T_HTONS(22) };
249 static uint8_t dl_src_values
[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 },
250 { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } };
251 static uint8_t dl_dst_values
[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 },
252 { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
253 static uint8_t nw_proto_values
[] = { IP_TYPE_TCP
, IP_TYPE_ICMP
};
254 static uint8_t nw_tos_values
[] = { 49, 0 };
256 static void *values
[CLS_N_FIELDS
][2];
261 values
[CLS_F_IDX_TUN_ID
][0] = &tun_id_values
[0];
262 values
[CLS_F_IDX_TUN_ID
][1] = &tun_id_values
[1];
264 values
[CLS_F_IDX_IN_PORT
][0] = &in_port_values
[0];
265 values
[CLS_F_IDX_IN_PORT
][1] = &in_port_values
[1];
267 values
[CLS_F_IDX_DL_VLAN
][0] = &dl_vlan_values
[0];
268 values
[CLS_F_IDX_DL_VLAN
][1] = &dl_vlan_values
[1];
270 values
[CLS_F_IDX_DL_VLAN_PCP
][0] = &dl_vlan_pcp_values
[0];
271 values
[CLS_F_IDX_DL_VLAN_PCP
][1] = &dl_vlan_pcp_values
[1];
273 values
[CLS_F_IDX_DL_SRC
][0] = dl_src_values
[0];
274 values
[CLS_F_IDX_DL_SRC
][1] = dl_src_values
[1];
276 values
[CLS_F_IDX_DL_DST
][0] = dl_dst_values
[0];
277 values
[CLS_F_IDX_DL_DST
][1] = dl_dst_values
[1];
279 values
[CLS_F_IDX_DL_TYPE
][0] = &dl_type_values
[0];
280 values
[CLS_F_IDX_DL_TYPE
][1] = &dl_type_values
[1];
282 values
[CLS_F_IDX_NW_SRC
][0] = &nw_src_values
[0];
283 values
[CLS_F_IDX_NW_SRC
][1] = &nw_src_values
[1];
285 values
[CLS_F_IDX_NW_DST
][0] = &nw_dst_values
[0];
286 values
[CLS_F_IDX_NW_DST
][1] = &nw_dst_values
[1];
288 values
[CLS_F_IDX_NW_PROTO
][0] = &nw_proto_values
[0];
289 values
[CLS_F_IDX_NW_PROTO
][1] = &nw_proto_values
[1];
291 values
[CLS_F_IDX_NW_TOS
][0] = &nw_tos_values
[0];
292 values
[CLS_F_IDX_NW_TOS
][1] = &nw_tos_values
[1];
294 values
[CLS_F_IDX_TP_SRC
][0] = &tp_src_values
[0];
295 values
[CLS_F_IDX_TP_SRC
][1] = &tp_src_values
[1];
297 values
[CLS_F_IDX_TP_DST
][0] = &tp_dst_values
[0];
298 values
[CLS_F_IDX_TP_DST
][1] = &tp_dst_values
[1];
301 #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
302 #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
303 #define N_TUN_ID_VALUES ARRAY_SIZE(tun_id_values)
304 #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
305 #define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values)
306 #define N_DL_VLAN_PCP_VALUES ARRAY_SIZE(dl_vlan_pcp_values)
307 #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
308 #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
309 #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
310 #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
311 #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
312 #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
313 #define N_NW_TOS_VALUES ARRAY_SIZE(nw_tos_values)
315 #define N_FLOW_VALUES (N_NW_SRC_VALUES * \
320 N_DL_VLAN_PCP_VALUES * \
326 N_NW_PROTO_VALUES * \
330 get_value(unsigned int *x
, unsigned n_values
)
332 unsigned int rem
= *x
% n_values
;
337 static struct cls_rule
*
338 lookup_with_include_bits(const struct classifier
*cls
,
339 const flow_t
*flow
, int include
)
343 return classifier_lookup_wild(cls
, flow
);
345 return classifier_lookup_exact(cls
, flow
);
346 case CLS_INC_WILD
| CLS_INC_EXACT
:
347 return classifier_lookup(cls
, flow
);
354 compare_classifiers(struct classifier
*cls
, struct tcls
*tcls
)
358 assert(classifier_count(cls
) == tcls
->n_rules
);
359 assert(classifier_count_exact(cls
) == tcls_count_exact(tcls
));
360 for (i
= 0; i
< N_FLOW_VALUES
; i
++) {
361 struct cls_rule
*cr0
, *cr1
;
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
)],
379 memcpy(flow
.dl_dst
, dl_dst_values
[get_value(&x
, N_DL_DST_VALUES
)],
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
);
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
));
390 const struct test_rule
*tr0
= test_rule_from_cls_rule(cr0
);
391 const struct test_rule
*tr1
= test_rule_from_cls_rule(cr1
);
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
);
405 free_rule(struct cls_rule
*cls_rule
, void *cls
)
407 classifier_remove(cls
, cls_rule
);
408 free(test_rule_from_cls_rule(cls_rule
));
412 destroy_classifier(struct classifier
*cls
)
414 classifier_for_each(cls
, CLS_INC_ALL
, free_rule
, cls
);
415 classifier_destroy(cls
);
419 check_tables(const struct classifier
*cls
,
420 int n_tables
, int n_buckets
, int n_rules
)
422 int found_tables
= 0;
423 int found_buckets
= 0;
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
])) {
433 HMAP_FOR_EACH (bucket
, struct cls_bucket
, hmap_node
, &cls
->tables
[i
]) {
435 assert(!list_is_empty(&bucket
->rules
));
436 found_rules
+= list_size(&bucket
->rules
);
440 if (!hmap_is_empty(&cls
->exact_table
)) {
443 found_rules
+= hmap_count(&cls
->exact_table
);
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
);
451 static struct test_rule
*
452 make_rule(int wc_fields
, unsigned int priority
, int value_pat
)
454 const struct cls_field
*f
;
455 struct test_rule
*rule
;
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
;
466 int value_idx
= (value_pat
& (1u << f_idx
)) != 0;
467 memcpy((char *) &flow
+ f
->ofs
, values
[f_idx
][value_idx
], f
->len
);
471 rule
= xzalloc(sizeof *rule
);
472 cls_rule_from_flow(&flow
, wildcards
, !wildcards
? UINT_MAX
: priority
,
478 shuffle(unsigned int *p
, size_t n
)
480 for (; n
> 1; n
--, p
++) {
481 unsigned int *q
= &p
[rand() % n
];
482 unsigned int tmp
= *p
;
488 /* Tests an empty classifier. */
492 struct classifier cls
;
495 classifier_init(&cls
);
497 assert(classifier_is_empty(&cls
));
498 assert(tcls_is_empty(&tcls
));
499 compare_classifiers(&cls
, &tcls
);
500 classifier_destroy(&cls
);
504 /* Destroys a null classifier. */
506 test_destroy_null(void)
508 classifier_destroy(NULL
);
511 /* Tests classification with one rule at a time. */
513 test_single_rule(void)
515 unsigned int wc_fields
; /* Hilarious. */
517 for (wc_fields
= 0; wc_fields
< (1u << CLS_N_FIELDS
); wc_fields
++) {
518 struct classifier cls
;
519 struct test_rule
*rule
, *tcls_rule
;
522 rule
= make_rule(wc_fields
,
523 hash_bytes(&wc_fields
, sizeof wc_fields
, 0), 0);
525 classifier_init(&cls
);
528 tcls_rule
= tcls_insert(&tcls
, rule
);
530 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
532 classifier_insert_exact(&cls
, &rule
->cls_rule
);
534 check_tables(&cls
, 1, 1, 1);
535 compare_classifiers(&cls
, &tcls
);
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
);
544 classifier_destroy(&cls
);
549 /* Tests replacing one rule by another. */
551 test_rule_replacement(void)
553 unsigned int wc_fields
;
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
;
561 rule1
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
562 rule2
= make_rule(wc_fields
, OFP_DEFAULT_PRIORITY
, UINT_MAX
);
566 classifier_init(&cls
);
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
);
575 tcls_insert(&tcls
, rule2
);
576 assert(test_rule_from_cls_rule(
577 classifier_insert(&cls
, &rule2
->cls_rule
)) == rule1
);
579 check_tables(&cls
, 1, 1, 1);
580 compare_classifiers(&cls
, &tcls
);
582 destroy_classifier(&cls
);
587 table_mask(int table
)
589 return ((1u << CLS_N_FIELDS
) - 1) & ~((1u << table
) - 1);
593 random_wcf_in_table(int table
, int seed
)
595 int wc_fields
= (1u << table
) | hash_int(seed
, 0);
596 return wc_fields
& table_mask(table
);
599 /* Tests classification with two rules at a time that fall into the same
602 test_two_rules_in_one_bucket(void)
604 int table
, rel_pri
, wcf_pat
, value_pat
;
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
;
616 unsigned int pri1
, pri2
;
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
624 pri1
= table
* 257 + 50;
625 pri2
= pri1
+ rel_pri
;
628 ? random_wcf_in_table(table
, pri1
)
631 ? random_wcf_in_table(table
, pri2
)
634 wcf1
&= ~(1u << (CLS_N_FIELDS
- 1));
635 wcf2
&= ~(1u << (CLS_N_FIELDS
- 1));
638 /* This classifier always puts exact-match rules at
639 * maximum priority. */
640 pri1
= pri2
= UINT_MAX
;
642 /* No wildcard fields. */
646 rule1
= make_rule(wcf1
, pri1
, 0);
647 rule2
= make_rule(wcf2
, pri2
,
648 value_pat
<< (CLS_N_FIELDS
- 1));
650 classifier_init(&cls
);
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
);
661 check_tables(&cls
, 1, 1, 2);
662 compare_classifiers(&cls
, &tcls
);
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
);
669 assert(displaced_rule
== rule1
);
670 check_tables(&cls
, 1, 1, 1);
671 compare_classifiers(&cls
, &tcls
);
675 classifier_remove(&cls
, &rule2
->cls_rule
);
676 tcls_remove(&tcls
, tcls_rule2
);
677 compare_classifiers(&cls
, &tcls
);
680 destroy_classifier(&cls
);
688 /* Tests classification with two rules at a time that fall into the same
689 * table but different buckets. */
691 test_two_rules_in_one_table(void)
693 int table
, rel_pri
, wcf_pat
;
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
;
703 unsigned int pri1
, pri2
;
705 int value_mask
, value_pat1
, value_pat2
;
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
;
715 wcf1
= wcf2
= random_wcf_in_table(table
, pri1
);
718 ? random_wcf_in_table(table
, pri1
)
721 ? random_wcf_in_table(table
, pri2
)
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
;
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
);
736 classifier_init(&cls
);
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
);
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
);
752 classifier_remove(&cls
, &rule2
->cls_rule
);
753 tcls_remove(&tcls
, tcls_rule2
);
754 compare_classifiers(&cls
, &tcls
);
757 classifier_destroy(&cls
);
764 /* Tests classification with two rules at a time that fall into different
767 test_two_rules_in_different_tables(void)
769 int table1
, table2
, rel_pri
, wcf_pat
;
771 for (table1
= 0; table1
< CLS_N_FIELDS
; table1
++) {
772 for (table2
= table1
+ 1; table2
<= CLS_N_FIELDS
; table2
++) {
773 for (rel_pri
= 0; rel_pri
< 2; rel_pri
++) {
774 for (wcf_pat
= 0; wcf_pat
< 4; wcf_pat
++) {
775 struct test_rule
*rule1
, *tcls_rule1
;
776 struct test_rule
*rule2
, *tcls_rule2
;
777 struct classifier cls
;
779 unsigned int pri1
, pri2
;
782 /* We must use unique priorities in this test because the
783 * classifier makes the rule choice undefined for rules of
784 * equal priority that fall into different tables. (In
785 * practice, lower-numbered tables win.) */
786 pri1
= table1
* 257 + 50;
787 pri2
= rel_pri
? pri1
- 1 : pri1
+ 1;
790 ? random_wcf_in_table(table1
, pri1
)
793 ? random_wcf_in_table(table2
, pri2
)
796 if (table2
== CLS_F_IDX_EXACT
) {
801 rule1
= make_rule(wcf1
, pri1
, 0);
802 rule2
= make_rule(wcf2
, pri2
, 0);
804 classifier_init(&cls
);
807 tcls_rule1
= tcls_insert(&tcls
, rule1
);
808 tcls_rule2
= tcls_insert(&tcls
, rule2
);
809 assert(!classifier_insert(&cls
, &rule1
->cls_rule
));
810 assert(!classifier_insert(&cls
, &rule2
->cls_rule
));
811 check_tables(&cls
, 2, 2, 2);
812 compare_classifiers(&cls
, &tcls
);
814 classifier_remove(&cls
, &rule1
->cls_rule
);
815 tcls_remove(&tcls
, tcls_rule1
);
816 check_tables(&cls
, 1, 1, 1);
817 compare_classifiers(&cls
, &tcls
);
820 classifier_remove(&cls
, &rule2
->cls_rule
);
821 tcls_remove(&tcls
, tcls_rule2
);
822 compare_classifiers(&cls
, &tcls
);
825 classifier_destroy(&cls
);
833 /* Tests classification with many rules at a time that fall into the same
834 * bucket but have unique priorities (and various wildcards). */
836 test_many_rules_in_one_bucket(void)
838 enum { MAX_RULES
= 50 };
839 int iteration
, table
;
841 for (iteration
= 0; iteration
< 3; iteration
++) {
842 for (table
= 0; table
<= CLS_N_FIELDS
; table
++) {
843 unsigned int priorities
[MAX_RULES
];
844 struct classifier cls
;
848 srand(hash_int(table
, iteration
));
849 for (i
= 0; i
< MAX_RULES
; i
++) {
850 priorities
[i
] = i
* 129;
852 shuffle(priorities
, ARRAY_SIZE(priorities
));
854 classifier_init(&cls
);
857 for (i
= 0; i
< MAX_RULES
; i
++) {
858 struct test_rule
*rule
;
859 unsigned int priority
= priorities
[i
];
862 wcf
= random_wcf_in_table(table
, priority
);
863 rule
= make_rule(wcf
, priority
,
864 table
== CLS_F_IDX_EXACT
? i
: 1234);
865 tcls_insert(&tcls
, rule
);
866 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
867 check_tables(&cls
, 1, 1, i
+ 1);
868 compare_classifiers(&cls
, &tcls
);
871 destroy_classifier(&cls
);
877 /* Tests classification with many rules at a time that fall into the same
878 * table but random buckets. */
880 test_many_rules_in_one_table(void)
882 enum { MAX_RULES
= 50 };
883 int iteration
, table
;
885 for (iteration
= 0; iteration
< 3; iteration
++) {
886 for (table
= 0; table
< CLS_N_FIELDS
; table
++) {
887 unsigned int priorities
[MAX_RULES
];
888 struct classifier cls
;
892 srand(hash_int(table
, iteration
));
893 for (i
= 0; i
< MAX_RULES
; i
++) {
894 priorities
[i
] = i
* 129;
896 shuffle(priorities
, ARRAY_SIZE(priorities
));
898 classifier_init(&cls
);
901 for (i
= 0; i
< MAX_RULES
; i
++) {
902 struct test_rule
*rule
;
903 unsigned int priority
= priorities
[i
];
906 wcf
= random_wcf_in_table(table
, priority
);
907 rule
= make_rule(wcf
, priority
, hash_int(priority
, 1));
908 tcls_insert(&tcls
, rule
);
909 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
910 check_tables(&cls
, 1, -1, i
+ 1);
911 compare_classifiers(&cls
, &tcls
);
914 destroy_classifier(&cls
);
920 /* Tests classification with many rules at a time that fall into random buckets
921 * in random tables. */
923 test_many_rules_in_different_tables(void)
925 enum { MAX_RULES
= 50 };
928 for (iteration
= 0; iteration
< 30; iteration
++) {
929 unsigned int priorities
[MAX_RULES
];
930 struct classifier cls
;
935 for (i
= 0; i
< MAX_RULES
; i
++) {
936 priorities
[i
] = i
* 129;
938 shuffle(priorities
, ARRAY_SIZE(priorities
));
940 classifier_init(&cls
);
943 for (i
= 0; i
< MAX_RULES
; i
++) {
944 struct test_rule
*rule
;
945 unsigned int priority
= priorities
[i
];
946 int table
= rand() % (CLS_N_FIELDS
+ 1);
947 int wcf
= random_wcf_in_table(table
, rand());
948 int value_pat
= rand() & ((1u << CLS_N_FIELDS
) - 1);
949 rule
= make_rule(wcf
, priority
, value_pat
);
950 tcls_insert(&tcls
, rule
);
951 assert(!classifier_insert(&cls
, &rule
->cls_rule
));
952 check_tables(&cls
, -1, -1, i
+ 1);
953 compare_classifiers(&cls
, &tcls
);
956 while (!classifier_is_empty(&cls
)) {
957 struct test_rule
*rule
= xmemdup(tcls
.rules
[rand() % tcls
.n_rules
],
958 sizeof(struct test_rule
));
959 int include
= rand() % 2 ? CLS_INC_WILD
: CLS_INC_EXACT
;
960 include
|= (rule
->cls_rule
.wc
.wildcards
961 ? CLS_INC_WILD
: CLS_INC_EXACT
);
962 classifier_for_each_match(&cls
, &rule
->cls_rule
, include
,
964 tcls_delete_matches(&tcls
, &rule
->cls_rule
, include
);
965 compare_classifiers(&cls
, &tcls
);
971 destroy_classifier(&cls
);
977 run_test(void (*function
)(void))
988 run_test(test_empty
);
989 run_test(test_destroy_null
);
990 run_test(test_single_rule
);
991 run_test(test_rule_replacement
);
992 run_test(test_two_rules_in_one_bucket
);
993 run_test(test_two_rules_in_one_table
);
994 run_test(test_two_rules_in_different_tables
);
995 run_test(test_many_rules_in_one_bucket
);
996 run_test(test_many_rules_in_one_table
);
997 run_test(test_many_rules_in_different_tables
);