Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
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 : : #undef NDEBUG
30 : : #include "classifier.h"
31 : : #include <assert.h>
32 : : #include <errno.h>
33 : : #include <limits.h>
34 : : #include "byte-order.h"
35 : : #include "classifier-private.h"
36 : : #include "command-line.h"
37 : : #include "fatal-signal.h"
38 : : #include "flow.h"
39 : : #include "openvswitch/ofp-util.h"
40 : : #include "ovstest.h"
41 : : #include "ovs-atomic.h"
42 : : #include "ovs-thread.h"
43 : : #include "packets.h"
44 : : #include "random.h"
45 : : #include "timeval.h"
46 : : #include "unaligned.h"
47 : : #include "util.h"
48 : :
49 : : static bool versioned = false;
50 : :
51 : : /* Fields in a rule. */
52 : : #define CLS_FIELDS \
53 : : /* struct flow all-caps */ \
54 : : /* member name name */ \
55 : : /* ----------- -------- */ \
56 : : CLS_FIELD(tunnel.tun_id, TUN_ID) \
57 : : CLS_FIELD(metadata, METADATA) \
58 : : CLS_FIELD(nw_src, NW_SRC) \
59 : : CLS_FIELD(nw_dst, NW_DST) \
60 : : CLS_FIELD(in_port.ofp_port, IN_PORT) \
61 : : CLS_FIELD(vlan_tci, VLAN_TCI) \
62 : : CLS_FIELD(dl_type, DL_TYPE) \
63 : : CLS_FIELD(tp_src, TP_SRC) \
64 : : CLS_FIELD(tp_dst, TP_DST) \
65 : : CLS_FIELD(dl_src, DL_SRC) \
66 : : CLS_FIELD(dl_dst, DL_DST) \
67 : : CLS_FIELD(nw_proto, NW_PROTO) \
68 : : CLS_FIELD(nw_tos, NW_DSCP)
69 : :
70 : : /* Field indexes.
71 : : *
72 : : * (These are also indexed into struct classifier's 'tables' array.) */
73 : : enum {
74 : : #define CLS_FIELD(MEMBER, NAME) CLS_F_IDX_##NAME,
75 : : CLS_FIELDS
76 : : #undef CLS_FIELD
77 : : CLS_N_FIELDS
78 : : };
79 : :
80 : : /* Field information. */
81 : : struct cls_field {
82 : : int ofs; /* Offset in struct flow. */
83 : : int len; /* Length in bytes. */
84 : : const char *name; /* Name (for debugging). */
85 : : };
86 : :
87 : : static const struct cls_field cls_fields[CLS_N_FIELDS] = {
88 : : #define CLS_FIELD(MEMBER, NAME) \
89 : : { offsetof(struct flow, MEMBER), \
90 : : sizeof ((struct flow *)0)->MEMBER, \
91 : : #NAME },
92 : : CLS_FIELDS
93 : : #undef CLS_FIELD
94 : : };
95 : :
96 : : struct test_rule {
97 : : struct ovs_list list_node;
98 : : int aux; /* Auxiliary data. */
99 : : struct cls_rule cls_rule; /* Classifier rule data. */
100 : : };
101 : :
102 : : static struct test_rule *
103 : 64366 : test_rule_from_cls_rule(const struct cls_rule *rule)
104 : : {
105 [ + + ]: 64366 : return rule ? CONTAINER_OF(rule, struct test_rule, cls_rule) : NULL;
106 : : }
107 : :
108 : : static void
109 : 33920 : test_rule_destroy(struct test_rule *rule)
110 : : {
111 [ + - ]: 33920 : if (rule) {
112 : 33920 : cls_rule_destroy(&rule->cls_rule);
113 : 33920 : free(rule);
114 : : }
115 : 33920 : }
116 : :
117 : : static struct test_rule *make_rule(int wc_fields, int priority, int value_pat);
118 : : static void free_rule(struct test_rule *);
119 : : static struct test_rule *clone_rule(const struct test_rule *);
120 : :
121 : : /* Trivial (linear) classifier. */
122 : : struct tcls {
123 : : size_t n_rules;
124 : : size_t allocated_rules;
125 : : struct test_rule **rules;
126 : : };
127 : :
128 : : static void
129 : 25337 : tcls_init(struct tcls *tcls)
130 : : {
131 : 25337 : tcls->n_rules = 0;
132 : 25337 : tcls->allocated_rules = 0;
133 : 25337 : tcls->rules = NULL;
134 : 25337 : }
135 : :
136 : : static void
137 : 25337 : tcls_destroy(struct tcls *tcls)
138 : : {
139 [ + - ]: 25337 : if (tcls) {
140 : : size_t i;
141 : :
142 [ + + ]: 41985 : for (i = 0; i < tcls->n_rules; i++) {
143 : 16648 : test_rule_destroy(tcls->rules[i]);
144 : : }
145 : 25337 : free(tcls->rules);
146 : : }
147 : 25337 : }
148 : :
149 : : static bool
150 : 8193 : tcls_is_empty(const struct tcls *tcls)
151 : : {
152 : 8193 : return tcls->n_rules == 0;
153 : : }
154 : :
155 : : static struct test_rule *
156 : 34736 : tcls_insert(struct tcls *tcls, const struct test_rule *rule)
157 : : {
158 : : size_t i;
159 : :
160 [ + + ]: 118764 : for (i = 0; i < tcls->n_rules; i++) {
161 : 92149 : const struct cls_rule *pos = &tcls->rules[i]->cls_rule;
162 [ + + ]: 92149 : if (cls_rule_equal(pos, &rule->cls_rule)) {
163 : : /* Exact match. */
164 : 816 : ovsrcu_postpone(free_rule, tcls->rules[i]);
165 : 816 : tcls->rules[i] = clone_rule(rule);
166 : 816 : return tcls->rules[i];
167 [ + + ]: 91333 : } else if (pos->priority < rule->cls_rule.priority) {
168 : 7305 : break;
169 : : }
170 : : }
171 : :
172 [ + + ]: 33920 : if (tcls->n_rules >= tcls->allocated_rules) {
173 : 26952 : tcls->rules = x2nrealloc(tcls->rules, &tcls->allocated_rules,
174 : : sizeof *tcls->rules);
175 : : }
176 [ + + ]: 33920 : if (i != tcls->n_rules) {
177 : 7305 : memmove(&tcls->rules[i + 1], &tcls->rules[i],
178 : 7305 : sizeof *tcls->rules * (tcls->n_rules - i));
179 : : }
180 : 33920 : tcls->rules[i] = clone_rule(rule);
181 : 33920 : tcls->n_rules++;
182 : 33920 : return tcls->rules[i];
183 : : }
184 : :
185 : : static void
186 : 17272 : tcls_remove(struct tcls *cls, const struct test_rule *rule)
187 : : {
188 : : size_t i;
189 : :
190 [ + - ]: 99740 : for (i = 0; i < cls->n_rules; i++) {
191 : 99740 : struct test_rule *pos = cls->rules[i];
192 [ + + ]: 99740 : if (pos == rule) {
193 : 17272 : test_rule_destroy(pos);
194 : :
195 : 17272 : memmove(&cls->rules[i], &cls->rules[i + 1],
196 : 17272 : sizeof *cls->rules * (cls->n_rules - i - 1));
197 : :
198 : 17272 : cls->n_rules--;
199 : 17272 : return;
200 : : }
201 : : }
202 : 0 : OVS_NOT_REACHED();
203 : : }
204 : :
205 : : static bool
206 : 221542293 : match(const struct cls_rule *wild_, const struct flow *fixed)
207 : : {
208 : : struct match wild;
209 : : int f_idx;
210 : :
211 : 221542293 : minimatch_expand(&wild_->match, &wild);
212 [ + + ]: 443068545 : for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) {
213 : : bool eq;
214 : :
215 [ + + ]: 443035538 : if (f_idx == CLS_F_IDX_NW_SRC) {
216 : 55378077 : eq = !((fixed->nw_src ^ wild.flow.nw_src)
217 : 55378077 : & wild.wc.masks.nw_src);
218 [ + + ]: 387657461 : } else if (f_idx == CLS_F_IDX_NW_DST) {
219 : 27697239 : eq = !((fixed->nw_dst ^ wild.flow.nw_dst)
220 : 27697239 : & wild.wc.masks.nw_dst);
221 [ + + ]: 359960222 : } else if (f_idx == CLS_F_IDX_TP_SRC) {
222 : 1731853 : eq = !((fixed->tp_src ^ wild.flow.tp_src)
223 : 1731853 : & wild.wc.masks.tp_src);
224 [ + + ]: 358228369 : } else if (f_idx == CLS_F_IDX_TP_DST) {
225 : 868534 : eq = !((fixed->tp_dst ^ wild.flow.tp_dst)
226 : 868534 : & wild.wc.masks.tp_dst);
227 [ + + ]: 357359835 : } else if (f_idx == CLS_F_IDX_DL_SRC) {
228 : 435915 : eq = eth_addr_equal_except(fixed->dl_src, wild.flow.dl_src,
229 : : wild.wc.masks.dl_src);
230 [ + + ]: 356923920 : } else if (f_idx == CLS_F_IDX_DL_DST) {
231 : 220728 : eq = eth_addr_equal_except(fixed->dl_dst, wild.flow.dl_dst,
232 : : wild.wc.masks.dl_dst);
233 [ + + ]: 356703192 : } else if (f_idx == CLS_F_IDX_VLAN_TCI) {
234 : 6920739 : eq = !((fixed->vlan_tci ^ wild.flow.vlan_tci)
235 : 6920739 : & wild.wc.masks.vlan_tci);
236 [ + + ]: 349782453 : } else if (f_idx == CLS_F_IDX_TUN_ID) {
237 : 221542293 : eq = !((fixed->tunnel.tun_id ^ wild.flow.tunnel.tun_id)
238 : 221542293 : & wild.wc.masks.tunnel.tun_id);
239 [ + + ]: 128240160 : } else if (f_idx == CLS_F_IDX_METADATA) {
240 : 110765866 : eq = !((fixed->metadata ^ wild.flow.metadata)
241 : 110765866 : & wild.wc.masks.metadata);
242 [ + + ]: 17474294 : } else if (f_idx == CLS_F_IDX_NW_DSCP) {
243 : 59021 : eq = !((fixed->nw_tos ^ wild.flow.nw_tos) &
244 : 59021 : (wild.wc.masks.nw_tos & IP_DSCP_MASK));
245 [ + + ]: 17415273 : } else if (f_idx == CLS_F_IDX_NW_PROTO) {
246 : 112241 : eq = !((fixed->nw_proto ^ wild.flow.nw_proto)
247 : 112241 : & wild.wc.masks.nw_proto);
248 [ + + ]: 17303032 : } else if (f_idx == CLS_F_IDX_DL_TYPE) {
249 : 3456780 : eq = !((fixed->dl_type ^ wild.flow.dl_type)
250 : 3456780 : & wild.wc.masks.dl_type);
251 [ + - ]: 13846252 : } else if (f_idx == CLS_F_IDX_IN_PORT) {
252 : 13846252 : eq = !((fixed->in_port.ofp_port
253 : 13846252 : ^ wild.flow.in_port.ofp_port)
254 : 13846252 : & wild.wc.masks.in_port.ofp_port);
255 : : } else {
256 : 0 : OVS_NOT_REACHED();
257 : : }
258 : :
259 [ + + ]: 443035538 : if (!eq) {
260 : 221509286 : return false;
261 : : }
262 : : }
263 : 221542293 : return true;
264 : : }
265 : :
266 : : static struct cls_rule *
267 : 29492500 : tcls_lookup(const struct tcls *cls, const struct flow *flow)
268 : : {
269 : : size_t i;
270 : :
271 [ + + ]: 250855642 : for (i = 0; i < cls->n_rules; i++) {
272 : 221390149 : struct test_rule *pos = cls->rules[i];
273 [ + + ]: 221390149 : if (match(&pos->cls_rule, flow)) {
274 : 27007 : return &pos->cls_rule;
275 : : }
276 : : }
277 : 29465493 : return NULL;
278 : : }
279 : :
280 : : static void
281 : 5976 : tcls_delete_matches(struct tcls *cls, const struct cls_rule *target)
282 : : {
283 : : size_t i;
284 : :
285 [ + + ]: 158120 : for (i = 0; i < cls->n_rules; ) {
286 : 152144 : struct test_rule *pos = cls->rules[i];
287 [ + - ]: 152144 : if (!minimask_has_extra(pos->cls_rule.match.mask,
288 : 152144 : target->match.mask)) {
289 : : struct flow flow;
290 : :
291 : 152144 : miniflow_expand(pos->cls_rule.match.flow, &flow);
292 [ + + ]: 152144 : if (match(target, &flow)) {
293 : 6000 : tcls_remove(cls, pos);
294 : 152144 : continue;
295 : : }
296 : : }
297 : 146144 : i++;
298 : : }
299 : 5976 : }
300 : :
301 : : static ovs_be32 nw_src_values[] = { CONSTANT_HTONL(0xc0a80001),
302 : : CONSTANT_HTONL(0xc0a04455) };
303 : : static ovs_be32 nw_dst_values[] = { CONSTANT_HTONL(0xc0a80002),
304 : : CONSTANT_HTONL(0xc0a04455) };
305 : : static ovs_be64 tun_id_values[] = {
306 : : 0,
307 : : CONSTANT_HTONLL(UINT64_C(0xfedcba9876543210)) };
308 : : static ovs_be64 metadata_values[] = {
309 : : 0,
310 : : CONSTANT_HTONLL(UINT64_C(0xfedcba9876543210)) };
311 : : static ofp_port_t in_port_values[] = { OFP_PORT_C(1), OFPP_LOCAL };
312 : : static ovs_be16 vlan_tci_values[] = { CONSTANT_HTONS(101), CONSTANT_HTONS(0) };
313 : : static ovs_be16 dl_type_values[]
314 : : = { CONSTANT_HTONS(ETH_TYPE_IP), CONSTANT_HTONS(ETH_TYPE_ARP) };
315 : : static ovs_be16 tp_src_values[] = { CONSTANT_HTONS(49362),
316 : : CONSTANT_HTONS(80) };
317 : : static ovs_be16 tp_dst_values[] = { CONSTANT_HTONS(6667), CONSTANT_HTONS(22) };
318 : : static struct eth_addr dl_src_values[] = {
319 : : { { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 } } },
320 : : { { { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } } } };
321 : : static struct eth_addr dl_dst_values[] = {
322 : : { { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 } } },
323 : : { { { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } } } };
324 : : static uint8_t nw_proto_values[] = { IPPROTO_TCP, IPPROTO_ICMP };
325 : : static uint8_t nw_dscp_values[] = { 48, 0 };
326 : :
327 : : static void *values[CLS_N_FIELDS][2];
328 : :
329 : : static void
330 : 15 : init_values(void)
331 : : {
332 : 15 : values[CLS_F_IDX_TUN_ID][0] = &tun_id_values[0];
333 : 15 : values[CLS_F_IDX_TUN_ID][1] = &tun_id_values[1];
334 : :
335 : 15 : values[CLS_F_IDX_METADATA][0] = &metadata_values[0];
336 : 15 : values[CLS_F_IDX_METADATA][1] = &metadata_values[1];
337 : :
338 : 15 : values[CLS_F_IDX_IN_PORT][0] = &in_port_values[0];
339 : 15 : values[CLS_F_IDX_IN_PORT][1] = &in_port_values[1];
340 : :
341 : 15 : values[CLS_F_IDX_VLAN_TCI][0] = &vlan_tci_values[0];
342 : 15 : values[CLS_F_IDX_VLAN_TCI][1] = &vlan_tci_values[1];
343 : :
344 : 15 : values[CLS_F_IDX_DL_SRC][0] = &dl_src_values[0];
345 : 15 : values[CLS_F_IDX_DL_SRC][1] = &dl_src_values[1];
346 : :
347 : 15 : values[CLS_F_IDX_DL_DST][0] = &dl_dst_values[0];
348 : 15 : values[CLS_F_IDX_DL_DST][1] = &dl_dst_values[1];
349 : :
350 : 15 : values[CLS_F_IDX_DL_TYPE][0] = &dl_type_values[0];
351 : 15 : values[CLS_F_IDX_DL_TYPE][1] = &dl_type_values[1];
352 : :
353 : 15 : values[CLS_F_IDX_NW_SRC][0] = &nw_src_values[0];
354 : 15 : values[CLS_F_IDX_NW_SRC][1] = &nw_src_values[1];
355 : :
356 : 15 : values[CLS_F_IDX_NW_DST][0] = &nw_dst_values[0];
357 : 15 : values[CLS_F_IDX_NW_DST][1] = &nw_dst_values[1];
358 : :
359 : 15 : values[CLS_F_IDX_NW_PROTO][0] = &nw_proto_values[0];
360 : 15 : values[CLS_F_IDX_NW_PROTO][1] = &nw_proto_values[1];
361 : :
362 : 15 : values[CLS_F_IDX_NW_DSCP][0] = &nw_dscp_values[0];
363 : 15 : values[CLS_F_IDX_NW_DSCP][1] = &nw_dscp_values[1];
364 : :
365 : 15 : values[CLS_F_IDX_TP_SRC][0] = &tp_src_values[0];
366 : 15 : values[CLS_F_IDX_TP_SRC][1] = &tp_src_values[1];
367 : :
368 : 15 : values[CLS_F_IDX_TP_DST][0] = &tp_dst_values[0];
369 : 15 : values[CLS_F_IDX_TP_DST][1] = &tp_dst_values[1];
370 : 15 : }
371 : :
372 : : #define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
373 : : #define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
374 : : #define N_TUN_ID_VALUES ARRAY_SIZE(tun_id_values)
375 : : #define N_METADATA_VALUES ARRAY_SIZE(metadata_values)
376 : : #define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
377 : : #define N_VLAN_TCI_VALUES ARRAY_SIZE(vlan_tci_values)
378 : : #define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
379 : : #define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
380 : : #define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
381 : : #define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
382 : : #define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
383 : : #define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
384 : : #define N_NW_DSCP_VALUES ARRAY_SIZE(nw_dscp_values)
385 : :
386 : : #define N_FLOW_VALUES (N_NW_SRC_VALUES * \
387 : : N_NW_DST_VALUES * \
388 : : N_TUN_ID_VALUES * \
389 : : N_IN_PORT_VALUES * \
390 : : N_VLAN_TCI_VALUES * \
391 : : N_DL_TYPE_VALUES * \
392 : : N_TP_SRC_VALUES * \
393 : : N_TP_DST_VALUES * \
394 : : N_DL_SRC_VALUES * \
395 : : N_DL_DST_VALUES * \
396 : : N_NW_PROTO_VALUES * \
397 : : N_NW_DSCP_VALUES)
398 : :
399 : : static unsigned int
400 : 383402500 : get_value(unsigned int *x, unsigned n_values)
401 : : {
402 : 383402500 : unsigned int rem = *x % n_values;
403 : 383402500 : *x /= n_values;
404 : 383402500 : return rem;
405 : : }
406 : :
407 : : static void
408 : 58985 : compare_classifiers(struct classifier *cls, size_t n_invisible_rules,
409 : : ovs_version_t version, struct tcls *tcls)
410 : : {
411 : : static const int confidence = 500;
412 : : unsigned int i;
413 : :
414 [ - + ]: 58985 : assert(classifier_count(cls) == tcls->n_rules + n_invisible_rules);
415 [ + + ]: 29551485 : for (i = 0; i < confidence; i++) {
416 : : const struct cls_rule *cr0, *cr1, *cr2;
417 : : struct flow flow;
418 : : struct flow_wildcards wc;
419 : : unsigned int x;
420 : :
421 : 29492500 : flow_wildcards_init_catchall(&wc);
422 : 29492500 : x = random_range(N_FLOW_VALUES);
423 : 29492500 : memset(&flow, 0, sizeof flow);
424 : 29492500 : flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)];
425 : 29492500 : flow.nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)];
426 : 29492500 : flow.tunnel.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)];
427 : 29492500 : flow.metadata = metadata_values[get_value(&x, N_METADATA_VALUES)];
428 : 29492500 : flow.in_port.ofp_port = in_port_values[get_value(&x,
429 : : N_IN_PORT_VALUES)];
430 : 29492500 : flow.vlan_tci = vlan_tci_values[get_value(&x, N_VLAN_TCI_VALUES)];
431 : 29492500 : flow.dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)];
432 : 29492500 : flow.tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)];
433 : 29492500 : flow.tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)];
434 : 29492500 : flow.dl_src = dl_src_values[get_value(&x, N_DL_SRC_VALUES)];
435 : 29492500 : flow.dl_dst = dl_dst_values[get_value(&x, N_DL_DST_VALUES)];
436 : 29492500 : flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)];
437 : 29492500 : flow.nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)];
438 : :
439 : : /* This assertion is here to suppress a GCC 4.9 array-bounds warning */
440 [ - + ]: 29492500 : ovs_assert(cls->n_tries <= CLS_MAX_TRIES);
441 : :
442 : 29492500 : cr0 = classifier_lookup(cls, version, &flow, &wc);
443 : 29492500 : cr1 = tcls_lookup(tcls, &flow);
444 [ - + ]: 29492500 : assert((cr0 == NULL) == (cr1 == NULL));
445 [ + + ]: 29492500 : if (cr0 != NULL) {
446 : 27007 : const struct test_rule *tr0 = test_rule_from_cls_rule(cr0);
447 : 27007 : const struct test_rule *tr1 = test_rule_from_cls_rule(cr1);
448 : :
449 [ - + ]: 27007 : assert(cls_rule_equal(cr0, cr1));
450 [ - + ]: 27007 : assert(tr0->aux == tr1->aux);
451 : :
452 : : /* Make sure the rule should have been visible. */
453 [ - + ]: 27007 : assert(cls_rule_visible_in_version(cr0, version));
454 : : }
455 : 29492500 : cr2 = classifier_lookup(cls, version, &flow, NULL);
456 [ - + ]: 29492500 : assert(cr2 == cr0);
457 : : }
458 : 58985 : }
459 : :
460 : : static void
461 : 8312 : destroy_classifier(struct classifier *cls)
462 : : {
463 : : struct test_rule *rule;
464 : :
465 : 8312 : classifier_defer(cls);
466 [ - + ][ - + ]: 8312 : CLS_FOR_EACH (rule, cls_rule, cls) {
467 [ # # ]: 0 : if (classifier_remove(cls, &rule->cls_rule)) {
468 : 0 : ovsrcu_postpone(free_rule, rule);
469 : : }
470 : : }
471 : 8312 : classifier_destroy(cls);
472 : 8312 : }
473 : :
474 : : static void
475 : 50792 : pvector_verify(const struct pvector *pvec)
476 : : {
477 : : void *ptr OVS_UNUSED;
478 : 50792 : int prev_priority = INT_MAX;
479 : :
480 [ + + ]: 101060 : PVECTOR_FOR_EACH (ptr, pvec) {
481 : 50268 : int priority = cursor__.vector[cursor__.entry_idx].priority;
482 [ - + ]: 50268 : if (priority > prev_priority) {
483 : 0 : ovs_abort(0, "Priority vector is out of order (%u > %u)",
484 : : priority, prev_priority);
485 : : }
486 : 50268 : prev_priority = priority;
487 : : }
488 : 50792 : }
489 : :
490 : : static unsigned int
491 : 410098 : trie_verify(const rcu_trie_ptr *trie, unsigned int ofs, unsigned int n_bits)
492 : : {
493 : 410098 : const struct trie_node *node = ovsrcu_get(struct trie_node *, trie);
494 : :
495 [ + + ]: 410098 : if (node) {
496 [ + + ][ - + ]: 162770 : assert(node->n_rules == 0 || node->n_bits > 0);
497 : 162770 : ofs += node->n_bits;
498 [ + + ][ + - ]: 162770 : assert((ofs > 0 || (ofs == 0 && node->n_bits == 0)) && ofs <= n_bits);
[ + - ][ - + ]
499 : :
500 : 162770 : return node->n_rules
501 : 162770 : + trie_verify(&node->edges[0], ofs, n_bits)
502 : 162770 : + trie_verify(&node->edges[1], ofs, n_bits);
503 : : }
504 : 247328 : return 0;
505 : : }
506 : :
507 : : static void
508 : 34290 : verify_tries(struct classifier *cls)
509 : : OVS_NO_THREAD_SAFETY_ANALYSIS
510 : : {
511 : 34290 : unsigned int n_rules = 0;
512 : : int i;
513 : :
514 [ + + ]: 68580 : for (i = 0; i < cls->n_tries; i++) {
515 : 34290 : n_rules += trie_verify(&cls->tries[i].root, 0,
516 : 34290 : cls->tries[i].field->n_bits);
517 : : }
518 [ - + ]: 34290 : assert(n_rules <= cls->n_rules);
519 : 34290 : }
520 : :
521 : : static void
522 : 50792 : check_tables(const struct classifier *cls, int n_tables, int n_rules,
523 : : int n_dups, int n_invisible, ovs_version_t version)
524 : : OVS_NO_THREAD_SAFETY_ANALYSIS
525 : : {
526 : : const struct cls_subtable *table;
527 : : struct test_rule *test_rule;
528 : 50792 : int found_tables = 0;
529 : 50792 : int found_tables_with_visible_rules = 0;
530 : 50792 : int found_rules = 0;
531 : 50792 : int found_dups = 0;
532 : 50792 : int found_invisible = 0;
533 : 50792 : int found_visible_but_removable = 0;
534 : 50792 : int found_rules2 = 0;
535 : :
536 : 50792 : pvector_verify(&cls->subtables);
537 [ + + ][ + + ]: 101060 : CMAP_FOR_EACH (table, cmap_node, &cls->subtables_map) {
538 : : const struct cls_match *head;
539 : 50268 : int max_priority = INT_MIN;
540 : 50268 : unsigned int max_count = 0;
541 : 50268 : bool found = false;
542 : 50268 : bool found_visible_rules = false;
543 : : const struct cls_subtable *iter;
544 : :
545 : : /* Locate the subtable from 'subtables'. */
546 [ + + ]: 100536 : PVECTOR_FOR_EACH (iter, &cls->subtables) {
547 [ + - ]: 50268 : if (iter == table) {
548 [ - + ]: 50268 : if (found) {
549 : 0 : ovs_abort(0, "Subtable %p duplicated in 'subtables'.",
550 : : table);
551 : : }
552 : 50268 : found = true;
553 : : }
554 : : }
555 [ - + ]: 50268 : if (!found) {
556 : 0 : ovs_abort(0, "Subtable %p not found from 'subtables'.", table);
557 : : }
558 : :
559 [ - + ]: 50268 : assert(!cmap_is_empty(&table->rules));
560 [ + - ][ - + ]: 50268 : assert(trie_verify(&table->ports_trie, 0, table->ports_mask_len)
561 : : == (table->ports_mask_len ? cmap_count(&table->rules) : 0));
562 : :
563 : 50268 : found_tables++;
564 : :
565 [ + + ][ + + ]: 734774 : CMAP_FOR_EACH (head, cmap_node, &table->rules) {
566 : 684506 : int prev_priority = INT_MAX;
567 : 684506 : ovs_version_t prev_version = 0;
568 : : const struct cls_match *rule, *prev;
569 : 684506 : bool found_visible_rules_in_list = false;
570 : :
571 [ - + ]: 684506 : assert(head->priority <= table->max_priority);
572 : :
573 [ + + ]: 684506 : if (head->priority > max_priority) {
574 : 114604 : max_priority = head->priority;
575 : 114604 : max_count = 0;
576 : : }
577 : :
578 [ + + ]: 1372332 : FOR_EACH_RULE_IN_LIST_PROTECTED(rule, prev, head) {
579 : : ovs_version_t rule_version;
580 : : const struct cls_rule *found_rule;
581 : :
582 : : /* Priority may not increase. */
583 [ - + ]: 687826 : assert(rule->priority <= prev_priority);
584 : :
585 [ + + ]: 687826 : if (rule->priority == max_priority) {
586 : 115012 : ++max_count;
587 : : }
588 : :
589 : : /* Count invisible rules and visible duplicates. */
590 [ + + ]: 687826 : if (!cls_match_visible_in_version(rule, version)) {
591 : 244258 : found_invisible++;
592 : : } else {
593 [ + + ]: 443568 : if (cls_match_is_eventually_invisible(rule)) {
594 : 3012 : found_visible_but_removable++;
595 : : }
596 [ + + ]: 443568 : if (found_visible_rules_in_list) {
597 : 1678 : found_dups++;
598 : : }
599 : 443568 : found_visible_rules_in_list = true;
600 : 443568 : found_visible_rules = true;
601 : : }
602 : :
603 : : /* Rule must be visible in the version it was inserted. */
604 : 687826 : rule_version = rule->versions.add_version;
605 [ - + ]: 687826 : assert(cls_match_visible_in_version(rule, rule_version));
606 : :
607 : : /* We should always find the latest version of the rule,
608 : : * unless all rules have been marked for removal.
609 : : * Later versions must always be later in the list. */
610 : 687826 : found_rule = classifier_find_rule_exactly(cls, rule->cls_rule,
611 : : rule_version);
612 [ + - ][ - + ]: 687826 : if (found_rule && found_rule != rule->cls_rule) {
613 : : struct cls_match *cls_match;
614 : 0 : cls_match = get_cls_match_protected(found_rule);
615 : :
616 [ # # ]: 0 : assert(found_rule->priority == rule->priority);
617 : :
618 : : /* Found rule may not have a lower version. */
619 [ # # ]: 0 : assert(cls_match->versions.add_version >= rule_version);
620 : :
621 : : /* This rule must not be visible in the found rule's
622 : : * version. */
623 [ # # ]: 0 : assert(!cls_match_visible_in_version(
624 : : rule, cls_match->versions.add_version));
625 : : }
626 : :
627 [ + + ]: 687826 : if (rule->priority == prev_priority) {
628 : : /* Exact duplicate rule may not have a lower version. */
629 [ - + ]: 408 : assert(rule_version >= prev_version);
630 : :
631 : : /* Previous rule must not be visible in rule's version. */
632 [ - + ]: 408 : assert(!cls_match_visible_in_version(prev, rule_version));
633 : : }
634 : :
635 : 687826 : prev_priority = rule->priority;
636 : 687826 : prev_version = rule_version;
637 : 687826 : found_rules++;
638 : : }
639 : : }
640 : :
641 [ + + ]: 50268 : if (found_visible_rules) {
642 : 45964 : found_tables_with_visible_rules++;
643 : : }
644 : :
645 [ - + ]: 50268 : assert(table->max_priority == max_priority);
646 [ - + ]: 50268 : assert(table->max_count == max_count);
647 : : }
648 : :
649 [ - + ]: 50792 : assert(found_tables == cmap_count(&cls->subtables_map));
650 [ - + ]: 50792 : assert(found_tables == pvector_count(&cls->subtables));
651 [ + + ][ - + ]: 50792 : assert(n_tables == -1 || n_tables == found_tables_with_visible_rules);
652 [ + + ][ - + ]: 50792 : assert(n_rules == -1 || found_rules == n_rules + found_invisible);
653 [ + + ][ - + ]: 50792 : assert(n_dups == -1 || found_dups == n_dups);
654 [ - + ]: 50792 : assert(found_invisible == n_invisible);
655 : :
656 [ + + ][ + + ]: 491348 : CLS_FOR_EACH (test_rule, cls_rule, cls) {
657 : 440556 : found_rules2++;
658 : : }
659 : : /* Iteration does not see removable rules. */
660 [ - + ]: 50792 : assert(found_rules
661 : : == found_rules2 + found_visible_but_removable + found_invisible);
662 : 50792 : }
663 : :
664 : : static struct test_rule *
665 : 34196 : make_rule(int wc_fields, int priority, int value_pat)
666 : : {
667 : : const struct cls_field *f;
668 : : struct test_rule *rule;
669 : : struct match match;
670 : :
671 : 34196 : match_init_catchall(&match);
672 [ + + ]: 478744 : for (f = &cls_fields[0]; f < &cls_fields[CLS_N_FIELDS]; f++) {
673 : 444548 : int f_idx = f - cls_fields;
674 : 444548 : int value_idx = (value_pat & (1u << f_idx)) != 0;
675 : 889096 : memcpy((char *) &match.flow + f->ofs,
676 : 889096 : values[f_idx][value_idx], f->len);
677 : :
678 [ + + ]: 444548 : if (f_idx == CLS_F_IDX_NW_SRC) {
679 : 34196 : match.wc.masks.nw_src = OVS_BE32_MAX;
680 [ + + ]: 410352 : } else if (f_idx == CLS_F_IDX_NW_DST) {
681 : 34196 : match.wc.masks.nw_dst = OVS_BE32_MAX;
682 [ + + ]: 376156 : } else if (f_idx == CLS_F_IDX_TP_SRC) {
683 : 34196 : match.wc.masks.tp_src = OVS_BE16_MAX;
684 [ + + ]: 341960 : } else if (f_idx == CLS_F_IDX_TP_DST) {
685 : 34196 : match.wc.masks.tp_dst = OVS_BE16_MAX;
686 [ + + ]: 307764 : } else if (f_idx == CLS_F_IDX_DL_SRC) {
687 : 34196 : WC_MASK_FIELD(&match.wc, dl_src);
688 [ + + ]: 273568 : } else if (f_idx == CLS_F_IDX_DL_DST) {
689 : 34196 : WC_MASK_FIELD(&match.wc, dl_dst);
690 [ + + ]: 239372 : } else if (f_idx == CLS_F_IDX_VLAN_TCI) {
691 : 34196 : match.wc.masks.vlan_tci = OVS_BE16_MAX;
692 [ + + ]: 205176 : } else if (f_idx == CLS_F_IDX_TUN_ID) {
693 : 34196 : match.wc.masks.tunnel.tun_id = OVS_BE64_MAX;
694 [ + + ]: 170980 : } else if (f_idx == CLS_F_IDX_METADATA) {
695 : 34196 : match.wc.masks.metadata = OVS_BE64_MAX;
696 [ + + ]: 136784 : } else if (f_idx == CLS_F_IDX_NW_DSCP) {
697 : 34196 : match.wc.masks.nw_tos |= IP_DSCP_MASK;
698 [ + + ]: 102588 : } else if (f_idx == CLS_F_IDX_NW_PROTO) {
699 : 34196 : match.wc.masks.nw_proto = UINT8_MAX;
700 [ + + ]: 68392 : } else if (f_idx == CLS_F_IDX_DL_TYPE) {
701 : 34196 : match.wc.masks.dl_type = OVS_BE16_MAX;
702 [ + - ]: 34196 : } else if (f_idx == CLS_F_IDX_IN_PORT) {
703 : 34196 : match.wc.masks.in_port.ofp_port = u16_to_ofp(UINT16_MAX);
704 : : } else {
705 : 0 : OVS_NOT_REACHED();
706 : : }
707 : : }
708 : :
709 : 34196 : rule = xzalloc(sizeof *rule);
710 [ + + ]: 68389 : cls_rule_init(&rule->cls_rule, &match, wc_fields
711 [ - + ]: 68386 : ? (priority == INT_MIN ? priority + 1 :
712 [ - + ]: 34193 : priority == INT_MAX ? priority - 1 : priority)
713 : : : 0);
714 : 34196 : return rule;
715 : : }
716 : :
717 : : static struct test_rule *
718 : 40712 : clone_rule(const struct test_rule *src)
719 : : {
720 : : struct test_rule *dst;
721 : :
722 : 40712 : dst = xmalloc(sizeof *dst);
723 : 40712 : dst->aux = src->aux;
724 : 40712 : cls_rule_clone(&dst->cls_rule, &src->cls_rule);
725 : 40712 : return dst;
726 : : }
727 : :
728 : : static void
729 : 5976 : free_rule(struct test_rule *rule)
730 : : {
731 : 5976 : cls_rule_destroy(&rule->cls_rule);
732 : 5976 : free(rule);
733 : 5976 : }
734 : :
735 : : static void
736 : 120 : shuffle(int *p, size_t n)
737 : : {
738 [ + + ]: 6000 : for (; n > 1; n--, p++) {
739 : 5880 : int *q = &p[random_range(n)];
740 : 5880 : int tmp = *p;
741 : 5880 : *p = *q;
742 : 5880 : *q = tmp;
743 : : }
744 : 120 : }
745 : :
746 : : static void
747 : 11397 : shuffle_u32s(uint32_t *p, size_t n)
748 : : {
749 [ + + ]: 1663962 : for (; n > 1; n--, p++) {
750 : 1652565 : uint32_t *q = &p[random_range(n)];
751 : 1652565 : uint32_t tmp = *p;
752 : 1652565 : *p = *q;
753 : 1652565 : *q = tmp;
754 : : }
755 : 11397 : }
756 : :
757 : : /* Classifier tests. */
758 : :
759 : : static enum mf_field_id trie_fields[2] = {
760 : : MFF_IPV4_DST, MFF_IPV4_SRC
761 : : };
762 : :
763 : : static void
764 : 17145 : set_prefix_fields(struct classifier *cls)
765 : : {
766 : 17145 : verify_tries(cls);
767 : 17145 : classifier_set_prefix_fields(cls, trie_fields, ARRAY_SIZE(trie_fields));
768 : 17145 : verify_tries(cls);
769 : 17145 : }
770 : :
771 : : /* Tests an empty classifier. */
772 : : static void
773 : 1 : test_empty(struct ovs_cmdl_context *ctx OVS_UNUSED)
774 : : {
775 : : struct classifier cls;
776 : : struct tcls tcls;
777 : :
778 : 1 : classifier_init(&cls, flow_segment_u64s);
779 : 1 : set_prefix_fields(&cls);
780 : 1 : tcls_init(&tcls);
781 [ - + ]: 1 : assert(classifier_is_empty(&cls));
782 [ - + ]: 1 : assert(tcls_is_empty(&tcls));
783 : 1 : compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls);
784 : 1 : classifier_destroy(&cls);
785 : 1 : tcls_destroy(&tcls);
786 : 1 : }
787 : :
788 : : /* Destroys a null classifier. */
789 : : static void
790 : 1 : test_destroy_null(struct ovs_cmdl_context *ctx OVS_UNUSED)
791 : : {
792 : 1 : classifier_destroy(NULL);
793 : 1 : }
794 : :
795 : : /* Tests classification with one rule at a time. */
796 : : static void
797 : 1 : test_single_rule(struct ovs_cmdl_context *ctx OVS_UNUSED)
798 : : {
799 : : unsigned int wc_fields; /* Hilarious. */
800 : :
801 [ + + ]: 8193 : for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) {
802 : : struct classifier cls;
803 : : struct test_rule *rule, *tcls_rule;
804 : : struct tcls tcls;
805 : :
806 : 8192 : rule = make_rule(wc_fields,
807 : 8192 : hash_bytes(&wc_fields, sizeof wc_fields, 0), 0);
808 : 8192 : classifier_init(&cls, flow_segment_u64s);
809 : 8192 : set_prefix_fields(&cls);
810 : 8192 : tcls_init(&tcls);
811 : 8192 : tcls_rule = tcls_insert(&tcls, rule);
812 : :
813 : 8192 : classifier_insert(&cls, &rule->cls_rule, OVS_VERSION_MIN, NULL, 0);
814 : 8192 : compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls);
815 : 8192 : check_tables(&cls, 1, 1, 0, 0, OVS_VERSION_MIN);
816 : :
817 : 8192 : classifier_remove(&cls, &rule->cls_rule);
818 : 8192 : tcls_remove(&tcls, tcls_rule);
819 [ - + ]: 8192 : assert(classifier_is_empty(&cls));
820 [ - + ]: 8192 : assert(tcls_is_empty(&tcls));
821 : 8192 : compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls);
822 : :
823 : 8192 : ovsrcu_postpone(free_rule, rule);
824 : 8192 : classifier_destroy(&cls);
825 : 8192 : tcls_destroy(&tcls);
826 : : }
827 : 1 : }
828 : :
829 : : /* Tests replacing one rule by another. */
830 : : static void
831 : 1 : test_rule_replacement(struct ovs_cmdl_context *ctx OVS_UNUSED)
832 : : {
833 : : unsigned int wc_fields;
834 : :
835 [ + + ]: 8193 : for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) {
836 : : struct classifier cls;
837 : : struct test_rule *rule1;
838 : : struct test_rule *rule2;
839 : : struct tcls tcls;
840 : :
841 : 8192 : rule1 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX);
842 : 8192 : rule2 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX);
843 : 8192 : rule2->aux += 5;
844 : 8192 : rule2->aux += 5;
845 : :
846 : 8192 : classifier_init(&cls, flow_segment_u64s);
847 : 8192 : set_prefix_fields(&cls);
848 : 8192 : tcls_init(&tcls);
849 : 8192 : tcls_insert(&tcls, rule1);
850 : 8192 : classifier_insert(&cls, &rule1->cls_rule, OVS_VERSION_MIN, NULL, 0);
851 : 8192 : compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls);
852 : 8192 : check_tables(&cls, 1, 1, 0, 0, OVS_VERSION_MIN);
853 : 8192 : tcls_destroy(&tcls);
854 : :
855 : 8192 : tcls_init(&tcls);
856 : 8192 : tcls_insert(&tcls, rule2);
857 : :
858 [ - + ]: 8192 : assert(test_rule_from_cls_rule(
859 : : classifier_replace(&cls, &rule2->cls_rule, OVS_VERSION_MIN,
860 : : NULL, 0)) == rule1);
861 : 8192 : ovsrcu_postpone(free_rule, rule1);
862 : 8192 : compare_classifiers(&cls, 0, OVS_VERSION_MIN, &tcls);
863 : 8192 : check_tables(&cls, 1, 1, 0, 0, OVS_VERSION_MIN);
864 : 8192 : classifier_defer(&cls);
865 : 8192 : classifier_remove(&cls, &rule2->cls_rule);
866 : :
867 : 8192 : tcls_destroy(&tcls);
868 : 8192 : destroy_classifier(&cls);
869 : : }
870 : 1 : }
871 : :
872 : : static int
873 : 6 : factorial(int n_items)
874 : : {
875 : : int n, i;
876 : :
877 : 6 : n = 1;
878 [ + + ]: 36 : for (i = 2; i <= n_items; i++) {
879 : 30 : n *= i;
880 : : }
881 : 6 : return n;
882 : : }
883 : :
884 : : static void
885 : 900 : swap(int *a, int *b)
886 : : {
887 : 900 : int tmp = *a;
888 : 900 : *a = *b;
889 : 900 : *b = tmp;
890 : 900 : }
891 : :
892 : : static void
893 : 534 : reverse(int *a, int n)
894 : : {
895 : : int i;
896 : :
897 [ + + ]: 900 : for (i = 0; i < n / 2; i++) {
898 : 366 : int j = n - (i + 1);
899 : 366 : swap(&a[i], &a[j]);
900 : : }
901 : 534 : }
902 : :
903 : : static bool
904 : 540 : next_permutation(int *a, int n)
905 : : {
906 : : int k;
907 : :
908 [ + + ]: 1086 : for (k = n - 2; k >= 0; k--) {
909 [ + + ]: 1080 : if (a[k] < a[k + 1]) {
910 : : int l;
911 : :
912 : 534 : for (l = n - 1; ; l--) {
913 [ + + ]: 792 : if (a[l] > a[k]) {
914 : 534 : swap(&a[k], &a[l]);
915 : 534 : reverse(a + (k + 1), n - (k + 1));
916 : 534 : return true;
917 : : }
918 : 258 : }
919 : : }
920 : : }
921 : 6 : return false;
922 : : }
923 : :
924 : : /* Tests classification with rules that have the same matching criteria. */
925 : : static void
926 : 2 : test_many_rules_in_one_list (struct ovs_cmdl_context *ctx OVS_UNUSED)
927 : : {
928 : : enum { N_RULES = 3 };
929 : : int n_pris;
930 : :
931 [ + + ]: 8 : for (n_pris = N_RULES; n_pris >= 1; n_pris--) {
932 : : int ops[N_RULES * 2];
933 : : int pris[N_RULES];
934 : : int n_permutations;
935 : : int i;
936 : :
937 : 6 : pris[0] = 0;
938 [ + + ]: 18 : for (i = 1; i < N_RULES; i++) {
939 : 12 : pris[i] = pris[i - 1] + (n_pris > i);
940 : : }
941 : :
942 [ + + ]: 42 : for (i = 0; i < N_RULES * 2; i++) {
943 : 36 : ops[i] = i / 2;
944 : : }
945 : :
946 : 6 : n_permutations = 0;
947 : : do {
948 : : struct test_rule *rules[N_RULES];
949 : : struct test_rule *tcls_rules[N_RULES];
950 : : int pri_rules[N_RULES];
951 : : struct classifier cls;
952 : : struct tcls tcls;
953 : 540 : ovs_version_t version = OVS_VERSION_MIN;
954 : 540 : size_t n_invisible_rules = 0;
955 : :
956 : 540 : n_permutations++;
957 : :
958 [ + + ]: 2160 : for (i = 0; i < N_RULES; i++) {
959 : 1620 : rules[i] = make_rule(456, pris[i], 0);
960 : 1620 : tcls_rules[i] = NULL;
961 : 1620 : pri_rules[i] = -1;
962 : : }
963 : :
964 : 540 : classifier_init(&cls, flow_segment_u64s);
965 : 540 : set_prefix_fields(&cls);
966 : 540 : tcls_init(&tcls);
967 : :
968 [ + + ]: 3780 : for (i = 0; i < ARRAY_SIZE(ops); i++) {
969 : 3240 : struct test_rule *displaced_rule = NULL;
970 : 3240 : struct cls_rule *removable_rule = NULL;
971 : 3240 : int j = ops[i];
972 : : int m, n;
973 : :
974 [ + + ]: 3240 : if (!tcls_rules[j]) {
975 : 2160 : tcls_rules[j] = tcls_insert(&tcls, rules[j]);
976 [ + + ]: 2160 : if (versioned) {
977 : : /* Insert the new rule in the next version. */
978 : 1080 : ++version;
979 : :
980 : 1080 : displaced_rule = test_rule_from_cls_rule(
981 : : classifier_find_rule_exactly(&cls,
982 : 1080 : &rules[j]->cls_rule,
983 : : version));
984 [ + + ]: 1080 : if (displaced_rule) {
985 : : /* Mark the old rule for removal after the current
986 : : * version. */
987 : 408 : cls_rule_make_invisible_in_version(
988 : 408 : &displaced_rule->cls_rule, version);
989 : 408 : n_invisible_rules++;
990 : 408 : removable_rule = &displaced_rule->cls_rule;
991 : : }
992 : 1080 : classifier_insert(&cls, &rules[j]->cls_rule, version,
993 : : NULL, 0);
994 : : } else {
995 : 1080 : displaced_rule = test_rule_from_cls_rule(
996 : 1080 : classifier_replace(&cls, &rules[j]->cls_rule,
997 : : version, NULL, 0));
998 : : }
999 [ + + ]: 2160 : if (pri_rules[pris[j]] >= 0) {
1000 : 816 : int k = pri_rules[pris[j]];
1001 [ - + ]: 816 : assert(displaced_rule != NULL);
1002 [ - + ]: 816 : assert(displaced_rule != rules[j]);
1003 [ - + ]: 816 : assert(pris[j] == displaced_rule->cls_rule.priority);
1004 : 816 : tcls_rules[k] = NULL;
1005 : : } else {
1006 [ - + ]: 1344 : assert(displaced_rule == NULL);
1007 : : }
1008 : 2160 : pri_rules[pris[j]] = j;
1009 : : } else {
1010 [ + + ]: 1080 : if (versioned) {
1011 : : /* Mark the rule for removal after the current
1012 : : * version. */
1013 : 540 : ++version;
1014 : 540 : cls_rule_make_invisible_in_version(
1015 : 540 : &rules[j]->cls_rule, version);
1016 : 540 : n_invisible_rules++;
1017 : 540 : removable_rule = &rules[j]->cls_rule;
1018 : : } else {
1019 : 540 : classifier_remove(&cls, &rules[j]->cls_rule);
1020 : : }
1021 : 1080 : tcls_remove(&tcls, tcls_rules[j]);
1022 : 1080 : tcls_rules[j] = NULL;
1023 : 1080 : pri_rules[pris[j]] = -1;
1024 : : }
1025 : 3240 : compare_classifiers(&cls, n_invisible_rules, version, &tcls);
1026 : 3240 : n = 0;
1027 [ + + ]: 12960 : for (m = 0; m < N_RULES; m++) {
1028 : 9720 : n += tcls_rules[m] != NULL;
1029 : : }
1030 : 3240 : check_tables(&cls, n > 0, n, n - 1, n_invisible_rules,
1031 : : version);
1032 : :
1033 [ + + ][ + + ]: 3240 : if (versioned && removable_rule) {
1034 : 948 : struct cls_match *cls_match =
1035 : : get_cls_match_protected(removable_rule);
1036 : :
1037 : : /* Removable rule is no longer visible. */
1038 [ - + ]: 948 : assert(cls_match);
1039 [ - + ]: 948 : assert(!cls_match_visible_in_version(cls_match, version));
1040 : 948 : classifier_remove(&cls, removable_rule);
1041 : 948 : n_invisible_rules--;
1042 : : }
1043 : : }
1044 : :
1045 : 540 : classifier_defer(&cls);
1046 [ + + ]: 2160 : for (i = 0; i < N_RULES; i++) {
1047 [ + + ]: 1620 : if (classifier_remove(&cls, &rules[i]->cls_rule)) {
1048 : 264 : ovsrcu_postpone(free_rule, rules[i]);
1049 : : }
1050 : : }
1051 : 540 : classifier_destroy(&cls);
1052 : 540 : tcls_destroy(&tcls);
1053 [ + + ]: 540 : } while (next_permutation(ops, ARRAY_SIZE(ops)));
1054 [ - + ]: 6 : assert(n_permutations == (factorial(N_RULES * 2) >> N_RULES));
1055 : : }
1056 : 2 : }
1057 : :
1058 : : static int
1059 : 114 : count_ones(unsigned long int x)
1060 : : {
1061 : 114 : int n = 0;
1062 : :
1063 [ + + ]: 867 : while (x) {
1064 : 753 : x = zero_rightmost_1bit(x);
1065 : 753 : n++;
1066 : : }
1067 : :
1068 : 114 : return n;
1069 : : }
1070 : :
1071 : : static bool
1072 : 2337 : array_contains(int *array, int n, int value)
1073 : : {
1074 : : int i;
1075 : :
1076 [ + + ]: 23272 : for (i = 0; i < n; i++) {
1077 [ + + ]: 21258 : if (array[i] == value) {
1078 : 323 : return true;
1079 : : }
1080 : : }
1081 : :
1082 : 2014 : return false;
1083 : : }
1084 : :
1085 : : /* Tests classification with two rules at a time that fall into the same
1086 : : * table but different lists. */
1087 : : static void
1088 : 2 : test_many_rules_in_one_table(struct ovs_cmdl_context *ctx OVS_UNUSED)
1089 : : {
1090 : : int iteration;
1091 : :
1092 [ + + ]: 102 : for (iteration = 0; iteration < 50; iteration++) {
1093 : : enum { N_RULES = 20 };
1094 : : struct test_rule *rules[N_RULES];
1095 : : struct test_rule *tcls_rules[N_RULES];
1096 : : struct classifier cls;
1097 : : struct tcls tcls;
1098 : 100 : ovs_version_t version = OVS_VERSION_MIN;
1099 : 100 : size_t n_invisible_rules = 0;
1100 : : int value_pats[N_RULES];
1101 : : int value_mask;
1102 : : int wcf;
1103 : : int i;
1104 : :
1105 : : do {
1106 : 114 : wcf = random_uint32() & ((1u << CLS_N_FIELDS) - 1);
1107 : 114 : value_mask = ~wcf & ((1u << CLS_N_FIELDS) - 1);
1108 [ + + ]: 114 : } while ((1 << count_ones(value_mask)) < N_RULES);
1109 : :
1110 : 100 : classifier_init(&cls, flow_segment_u64s);
1111 : 100 : set_prefix_fields(&cls);
1112 : 100 : tcls_init(&tcls);
1113 : :
1114 [ + + ]: 2100 : for (i = 0; i < N_RULES; i++) {
1115 : 2000 : int priority = random_range(INT_MAX);
1116 : :
1117 : : do {
1118 : 2323 : value_pats[i] = random_uint32() & value_mask;
1119 [ + + ]: 2323 : } while (array_contains(value_pats, i, value_pats[i]));
1120 : :
1121 : 2000 : ++version;
1122 : 2000 : rules[i] = make_rule(wcf, priority, value_pats[i]);
1123 : 2000 : tcls_rules[i] = tcls_insert(&tcls, rules[i]);
1124 : :
1125 : 2000 : classifier_insert(&cls, &rules[i]->cls_rule, version, NULL, 0);
1126 : 2000 : compare_classifiers(&cls, n_invisible_rules, version, &tcls);
1127 : :
1128 : 2000 : check_tables(&cls, 1, i + 1, 0, n_invisible_rules, version);
1129 : : }
1130 : :
1131 [ + + ]: 2100 : for (i = 0; i < N_RULES; i++) {
1132 : 2000 : tcls_remove(&tcls, tcls_rules[i]);
1133 [ + + ]: 2000 : if (versioned) {
1134 : : /* Mark the rule for removal after the current version. */
1135 : 1000 : ++version;
1136 : 1000 : cls_rule_make_invisible_in_version(&rules[i]->cls_rule,
1137 : : version);
1138 : 1000 : n_invisible_rules++;
1139 : : } else {
1140 : 1000 : classifier_remove(&cls, &rules[i]->cls_rule);
1141 : : }
1142 : 2000 : compare_classifiers(&cls, n_invisible_rules, version, &tcls);
1143 : 2000 : check_tables(&cls, i < N_RULES - 1, N_RULES - (i + 1), 0,
1144 : : n_invisible_rules, version);
1145 [ + + ]: 2000 : if (!versioned) {
1146 : 1000 : ovsrcu_postpone(free_rule, rules[i]);
1147 : : }
1148 : : }
1149 : :
1150 [ + + ]: 100 : if (versioned) {
1151 [ + + ]: 1050 : for (i = 0; i < N_RULES; i++) {
1152 : 1000 : classifier_remove(&cls, &rules[i]->cls_rule);
1153 : 1000 : n_invisible_rules--;
1154 : :
1155 : 1000 : compare_classifiers(&cls, n_invisible_rules, version, &tcls);
1156 : 1000 : check_tables(&cls, 0, 0, 0, n_invisible_rules, version);
1157 : 1000 : ovsrcu_postpone(free_rule, rules[i]);
1158 : : }
1159 : : }
1160 : :
1161 : 100 : classifier_destroy(&cls);
1162 : 100 : tcls_destroy(&tcls);
1163 : : }
1164 : 2 : }
1165 : :
1166 : : /* Tests classification with many rules at a time that fall into random lists
1167 : : * in 'n' tables. */
1168 : : static void
1169 : 4 : test_many_rules_in_n_tables(int n_tables)
1170 : : {
1171 : : enum { MAX_RULES = 50 };
1172 : : int wcfs[10];
1173 : : int iteration;
1174 : : int i;
1175 : :
1176 [ - + ]: 4 : assert(n_tables < 10);
1177 [ + + ]: 18 : for (i = 0; i < n_tables; i++) {
1178 : : do {
1179 : 14 : wcfs[i] = random_uint32() & ((1u << CLS_N_FIELDS) - 1);
1180 [ - + ]: 14 : } while (array_contains(wcfs, i, wcfs[i]));
1181 : : }
1182 : :
1183 [ + + ]: 124 : for (iteration = 0; iteration < 30; iteration++) {
1184 : : int priorities[MAX_RULES];
1185 : : struct classifier cls;
1186 : : struct tcls tcls;
1187 : 120 : ovs_version_t version = OVS_VERSION_MIN;
1188 : 120 : size_t n_invisible_rules = 0;
1189 : 120 : struct ovs_list list = OVS_LIST_INITIALIZER(&list);
1190 : :
1191 : 120 : random_set_seed(iteration + 1);
1192 [ + + ]: 6120 : for (i = 0; i < MAX_RULES; i++) {
1193 : 6000 : priorities[i] = (i * 129) & INT_MAX;
1194 : : }
1195 : 120 : shuffle(priorities, ARRAY_SIZE(priorities));
1196 : :
1197 : 120 : classifier_init(&cls, flow_segment_u64s);
1198 : 120 : set_prefix_fields(&cls);
1199 : 120 : tcls_init(&tcls);
1200 : :
1201 [ + + ]: 6120 : for (i = 0; i < MAX_RULES; i++) {
1202 : : struct test_rule *rule;
1203 : 6000 : int priority = priorities[i];
1204 : 6000 : int wcf = wcfs[random_range(n_tables)];
1205 : 6000 : int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1);
1206 : 6000 : rule = make_rule(wcf, priority, value_pat);
1207 : 6000 : tcls_insert(&tcls, rule);
1208 : 6000 : classifier_insert(&cls, &rule->cls_rule, version, NULL, 0);
1209 : 6000 : compare_classifiers(&cls, n_invisible_rules, version, &tcls);
1210 : 6000 : check_tables(&cls, -1, i + 1, -1, n_invisible_rules, version);
1211 : : }
1212 : :
1213 [ + + ]: 6096 : while (classifier_count(&cls) - n_invisible_rules > 0) {
1214 : : struct test_rule *target;
1215 : : struct test_rule *rule;
1216 : 5976 : size_t n_removable_rules = 0;
1217 : :
1218 : 5976 : target = clone_rule(tcls.rules[random_range(tcls.n_rules)]);
1219 : :
1220 [ + + ][ + + ]: 11976 : CLS_FOR_EACH_TARGET (rule, cls_rule, &cls, &target->cls_rule,
1221 : : version) {
1222 [ + + ]: 6000 : if (versioned) {
1223 : : /* Mark the rule for removal after the current version. */
1224 : 3000 : cls_rule_make_invisible_in_version(&rule->cls_rule,
1225 : : version + 1);
1226 : 3000 : n_removable_rules++;
1227 : 3000 : compare_classifiers(&cls, n_invisible_rules, version,
1228 : : &tcls);
1229 : 3000 : check_tables(&cls, -1, -1, -1, n_invisible_rules, version);
1230 : :
1231 : 3000 : ovs_list_push_back(&list, &rule->list_node);
1232 [ + - ]: 3000 : } else if (classifier_remove(&cls, &rule->cls_rule)) {
1233 : 3000 : ovsrcu_postpone(free_rule, rule);
1234 : : }
1235 : : }
1236 : :
1237 : 5976 : ++version;
1238 : 5976 : n_invisible_rules += n_removable_rules;
1239 : :
1240 : 5976 : tcls_delete_matches(&tcls, &target->cls_rule);
1241 : 5976 : free_rule(target);
1242 : :
1243 : 5976 : compare_classifiers(&cls, n_invisible_rules, version, &tcls);
1244 : 5976 : check_tables(&cls, -1, -1, -1, n_invisible_rules, version);
1245 : : }
1246 [ + + ]: 120 : if (versioned) {
1247 : : struct test_rule *rule;
1248 : :
1249 : : /* Remove rules that are no longer visible. */
1250 [ + + ]: 3060 : LIST_FOR_EACH_POP (rule, list_node, &list) {
1251 : 3000 : classifier_remove(&cls, &rule->cls_rule);
1252 : 3000 : n_invisible_rules--;
1253 : :
1254 : 3000 : compare_classifiers(&cls, n_invisible_rules, version,
1255 : : &tcls);
1256 : 3000 : check_tables(&cls, -1, -1, -1, n_invisible_rules, version);
1257 : : }
1258 : : }
1259 : :
1260 : 120 : destroy_classifier(&cls);
1261 : 120 : tcls_destroy(&tcls);
1262 : : }
1263 : 4 : }
1264 : :
1265 : : static void
1266 : 2 : test_many_rules_in_two_tables(struct ovs_cmdl_context *ctx OVS_UNUSED)
1267 : : {
1268 : 2 : test_many_rules_in_n_tables(2);
1269 : 2 : }
1270 : :
1271 : : static void
1272 : 2 : test_many_rules_in_five_tables(struct ovs_cmdl_context *ctx OVS_UNUSED)
1273 : : {
1274 : 2 : test_many_rules_in_n_tables(5);
1275 : 2 : }
1276 : :
1277 : : /* Classifier benchmarks. */
1278 : :
1279 : : static int n_rules; /* Number of rules to insert. */
1280 : : static int n_priorities; /* Number of priorities to use. */
1281 : : static int n_tables; /* Number of subtables. */
1282 : : static int n_threads; /* Number of threads to search and mutate. */
1283 : : static int n_lookups; /* Number of lookups each thread performs. */
1284 : :
1285 : : static void benchmark(bool use_wc);
1286 : :
1287 : : static int
1288 : 0 : elapsed(const struct timeval *start)
1289 : : {
1290 : : struct timeval end;
1291 : :
1292 : 0 : xgettimeofday(&end);
1293 : 0 : return timeval_to_msec(&end) - timeval_to_msec(start);
1294 : : }
1295 : :
1296 : : static void
1297 : 0 : run_benchmarks(struct ovs_cmdl_context *ctx)
1298 : : {
1299 [ # # ]: 0 : if (ctx->argc < 5
1300 [ # # ][ # # ]: 0 : || (ctx->argc > 1 && !strcmp(ctx->argv[1], "--help"))) {
1301 : 0 : printf(
1302 : : "usage: ovstest %s benchmark <n_rules> <n_priorities> <n_subtables> <n_threads> <n_lookups>\n"
1303 : : "\n"
1304 : : "where:\n"
1305 : : "\n"
1306 : : "<n_rules> - The number of rules to install for lookups. More rules\n"
1307 : : " makes misses less likely.\n"
1308 : : "<n_priorities> - How many different priorities to use. Using only 1\n"
1309 : : " priority will force lookups to continue through all\n"
1310 : : " subtables.\n"
1311 : : "<n_subtables> - Number of subtables to use. Normally a classifier has\n"
1312 : : " rules with different kinds of masks, resulting in\n"
1313 : : " multiple subtables (one per mask). However, in some\n"
1314 : : " special cases a table may consist of only one kind of\n"
1315 : : " rules, so there will be only one subtable.\n"
1316 : : "<n_threads> - How many lookup threads to use. Using one thread should\n"
1317 : : " give less variance accross runs, but classifier\n"
1318 : : " scaling can be tested with multiple threads.\n"
1319 : : "<n_lookups> - How many lookups each thread should perform.\n"
1320 : : "\n", program_name);
1321 : 0 : return;
1322 : : }
1323 : :
1324 : 0 : n_rules = strtol(ctx->argv[1], NULL, 10);
1325 : 0 : n_priorities = strtol(ctx->argv[2], NULL, 10);
1326 : 0 : n_tables = strtol(ctx->argv[3], NULL, 10);
1327 : 0 : n_threads = strtol(ctx->argv[4], NULL, 10);
1328 : 0 : n_lookups = strtol(ctx->argv[5], NULL, 10);
1329 : :
1330 : 0 : printf("\nBenchmarking with:\n"
1331 : : "%d rules with %d priorities in %d tables, "
1332 : : "%d threads doing %d lookups each\n",
1333 : : n_rules, n_priorities, n_tables, n_threads, n_lookups);
1334 : :
1335 : 0 : puts("\nWithout wildcards: \n");
1336 : 0 : benchmark(false);
1337 : 0 : puts("\nWith wildcards: \n");
1338 : 0 : benchmark(true);
1339 : : }
1340 : :
1341 : : struct cls_aux {
1342 : : const struct classifier *cls;
1343 : : size_t n_lookup_flows;
1344 : : struct flow *lookup_flows;
1345 : : bool use_wc;
1346 : : atomic_int hits;
1347 : : atomic_int misses;
1348 : : };
1349 : :
1350 : : static void *
1351 : 0 : lookup_classifier(void *aux_)
1352 : : {
1353 : 0 : struct cls_aux *aux = aux_;
1354 : 0 : ovs_version_t version = OVS_VERSION_MIN;
1355 : 0 : int hits = 0, old_hits;
1356 : 0 : int misses = 0, old_misses;
1357 : : size_t i;
1358 : :
1359 : 0 : random_set_seed(1);
1360 : :
1361 [ # # ]: 0 : for (i = 0; i < n_lookups; i++) {
1362 : : const struct cls_rule *cr;
1363 : : struct flow_wildcards wc;
1364 : : unsigned int x;
1365 : :
1366 : 0 : x = random_range(aux->n_lookup_flows);
1367 : :
1368 [ # # ]: 0 : if (aux->use_wc) {
1369 : 0 : flow_wildcards_init_catchall(&wc);
1370 : 0 : cr = classifier_lookup(aux->cls, version, &aux->lookup_flows[x],
1371 : : &wc);
1372 : : } else {
1373 : 0 : cr = classifier_lookup(aux->cls, version, &aux->lookup_flows[x],
1374 : : NULL);
1375 : : }
1376 [ # # ]: 0 : if (cr) {
1377 : 0 : hits++;
1378 : : } else {
1379 : 0 : misses++;
1380 : : }
1381 : : }
1382 : 0 : atomic_add(&aux->hits, hits, &old_hits);
1383 : 0 : atomic_add(&aux->misses, misses, &old_misses);
1384 : 0 : return NULL;
1385 : : }
1386 : :
1387 : : /* Benchmark classification. */
1388 : : static void
1389 : 0 : benchmark(bool use_wc)
1390 : : {
1391 : : struct classifier cls;
1392 : 0 : ovs_version_t version = OVS_VERSION_MIN;
1393 : : struct cls_aux aux;
1394 : 0 : int *wcfs = xmalloc(n_tables * sizeof *wcfs);
1395 : 0 : int *priorities = xmalloc(n_priorities * sizeof *priorities);
1396 : : struct timeval start;
1397 : : pthread_t *threads;
1398 : : int i;
1399 : :
1400 : 0 : fatal_signal_init();
1401 : :
1402 : 0 : random_set_seed(1);
1403 : :
1404 [ # # ]: 0 : for (i = 0; i < n_tables; i++) {
1405 : : do {
1406 : 0 : wcfs[i] = random_uint32() & ((1u << CLS_N_FIELDS) - 1);
1407 [ # # ]: 0 : } while (array_contains(wcfs, i, wcfs[i]));
1408 : : }
1409 : :
1410 [ # # ]: 0 : for (i = 0; i < n_priorities; i++) {
1411 : 0 : priorities[i] = (i * 129) & INT_MAX;
1412 : : }
1413 : 0 : shuffle(priorities, n_priorities);
1414 : :
1415 : 0 : classifier_init(&cls, flow_segment_u64s);
1416 : 0 : set_prefix_fields(&cls);
1417 : :
1418 : : /* Create lookup flows. */
1419 : 0 : aux.use_wc = use_wc;
1420 : 0 : aux.cls = &cls;
1421 : 0 : aux.n_lookup_flows = 2 * N_FLOW_VALUES;
1422 : 0 : aux.lookup_flows = xzalloc(aux.n_lookup_flows * sizeof *aux.lookup_flows);
1423 [ # # ]: 0 : for (i = 0; i < aux.n_lookup_flows; i++) {
1424 : 0 : struct flow *flow = &aux.lookup_flows[i];
1425 : : unsigned int x;
1426 : :
1427 : 0 : x = random_range(N_FLOW_VALUES);
1428 : 0 : flow->nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)];
1429 : 0 : flow->nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)];
1430 : 0 : flow->tunnel.tun_id = tun_id_values[get_value(&x, N_TUN_ID_VALUES)];
1431 : 0 : flow->metadata = metadata_values[get_value(&x, N_METADATA_VALUES)];
1432 : 0 : flow->in_port.ofp_port = in_port_values[get_value(&x,
1433 : : N_IN_PORT_VALUES)];
1434 : 0 : flow->vlan_tci = vlan_tci_values[get_value(&x, N_VLAN_TCI_VALUES)];
1435 : 0 : flow->dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)];
1436 : 0 : flow->tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)];
1437 : 0 : flow->tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)];
1438 : 0 : flow->dl_src = dl_src_values[get_value(&x, N_DL_SRC_VALUES)];
1439 : 0 : flow->dl_dst = dl_dst_values[get_value(&x, N_DL_DST_VALUES)];
1440 : 0 : flow->nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)];
1441 : 0 : flow->nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)];
1442 : : }
1443 : 0 : atomic_init(&aux.hits, 0);
1444 : 0 : atomic_init(&aux.misses, 0);
1445 : :
1446 : : /* Rule insertion. */
1447 [ # # ]: 0 : for (i = 0; i < n_rules; i++) {
1448 : : struct test_rule *rule;
1449 : : const struct cls_rule *old_cr;
1450 : :
1451 : 0 : int priority = priorities[random_range(n_priorities)];
1452 : 0 : int wcf = wcfs[random_range(n_tables)];
1453 : 0 : int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1);
1454 : :
1455 : 0 : rule = make_rule(wcf, priority, value_pat);
1456 : 0 : old_cr = classifier_find_rule_exactly(&cls, &rule->cls_rule, version);
1457 [ # # ]: 0 : if (!old_cr) {
1458 : 0 : classifier_insert(&cls, &rule->cls_rule, version, NULL, 0);
1459 : : } else {
1460 : 0 : free_rule(rule);
1461 : : }
1462 : : }
1463 : :
1464 : : /* Lookup. */
1465 : 0 : xgettimeofday(&start);
1466 : 0 : threads = xmalloc(n_threads * sizeof *threads);
1467 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
1468 : 0 : threads[i] = ovs_thread_create("lookups", lookup_classifier, &aux);
1469 : : }
1470 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
1471 : 0 : xpthread_join(threads[i], NULL);
1472 : : }
1473 : :
1474 : 0 : int elapsed_msec = elapsed(&start);
1475 : :
1476 : 0 : free(threads);
1477 : :
1478 : : int hits, misses;
1479 : 0 : atomic_read(&aux.hits, &hits);
1480 : 0 : atomic_read(&aux.misses, &misses);
1481 : 0 : printf("hits: %d, misses: %d\n", hits, misses);
1482 : :
1483 : 0 : printf("classifier lookups: %5d ms, %"PRId64" lookups/sec\n",
1484 : : elapsed_msec,
1485 : 0 : (((uint64_t)hits + misses) * 1000) / elapsed_msec);
1486 : :
1487 : 0 : destroy_classifier(&cls);
1488 : 0 : free(aux.lookup_flows);
1489 : 0 : free(priorities);
1490 : 0 : free(wcfs);
1491 : 0 : }
1492 : :
1493 : : /* Miniflow tests. */
1494 : :
1495 : : static uint32_t
1496 : 975031 : random_value(void)
1497 : : {
1498 : : static const uint32_t values[] =
1499 : : { 0xffffffff, 0xaaaaaaaa, 0x55555555, 0x80000000,
1500 : : 0x00000001, 0xface0000, 0x00d00d1e, 0xdeadbeef };
1501 : :
1502 : 975031 : return values[random_range(ARRAY_SIZE(values))];
1503 : : }
1504 : :
1505 : : static bool
1506 : 273377902 : choose(unsigned int n, unsigned int *idxp)
1507 : : {
1508 [ + + ]: 273377902 : if (*idxp < n) {
1509 : 131989 : return true;
1510 : : } else {
1511 : 273245913 : *idxp -= n;
1512 : 273245913 : return false;
1513 : : }
1514 : : }
1515 : :
1516 : : #define FLOW_U32S (FLOW_U64S * 2)
1517 : :
1518 : : static bool
1519 : 593001 : init_consecutive_values(int n_consecutive, struct flow *flow,
1520 : : unsigned int *idxp)
1521 : : {
1522 : 593001 : uint32_t *flow_u32 = (uint32_t *) flow;
1523 : :
1524 [ + + ]: 593001 : if (choose(FLOW_U32S - n_consecutive + 1, idxp)) {
1525 : : int i;
1526 : :
1527 [ + + ]: 48119 : for (i = 0; i < n_consecutive; i++) {
1528 : 31838 : flow_u32[*idxp + i] = random_value();
1529 : : }
1530 : 16281 : return true;
1531 : : } else {
1532 : 576720 : return false;
1533 : : }
1534 : : }
1535 : :
1536 : : static bool
1537 : 79840 : next_random_flow(struct flow *flow, unsigned int idx)
1538 : : {
1539 : 79840 : uint32_t *flow_u32 = (uint32_t *) flow;
1540 : : int i;
1541 : :
1542 : 79840 : memset(flow, 0, sizeof *flow);
1543 : :
1544 : : /* Empty flow. */
1545 [ + + ]: 79840 : if (choose(1, &idx)) {
1546 : 5 : return true;
1547 : : }
1548 : :
1549 : : /* All flows with a small number of consecutive nonzero values. */
1550 [ + + ]: 338683 : for (i = 1; i <= 4; i++) {
1551 [ + + ]: 275050 : if (init_consecutive_values(i, flow, &idx)) {
1552 : 16202 : return true;
1553 : : }
1554 : : }
1555 : :
1556 : : /* All flows with a large number of consecutive nonzero values. */
1557 [ + + ]: 381505 : for (i = FLOW_U32S - 4; i <= FLOW_U32S; i++) {
1558 [ + + ]: 317951 : if (init_consecutive_values(i, flow, &idx)) {
1559 : 79 : return true;
1560 : : }
1561 : : }
1562 : :
1563 : : /* All flows with exactly two nonconsecutive nonzero values. */
1564 [ + + ]: 63554 : if (choose((FLOW_U32S - 1) * (FLOW_U32S - 2) / 2, &idx)) {
1565 : : int ofs1;
1566 : :
1567 [ + - ]: 2542218 : for (ofs1 = 0; ofs1 < FLOW_U32S - 2; ofs1++) {
1568 : : int ofs2;
1569 : :
1570 [ + + ]: 275120171 : for (ofs2 = ofs1 + 2; ofs2 < FLOW_U32S; ofs2++) {
1571 [ + + ]: 272630106 : if (choose(1, &idx)) {
1572 : 52153 : flow_u32[ofs1] = random_value();
1573 : 52153 : flow_u32[ofs2] = random_value();
1574 : 52153 : return true;
1575 : : }
1576 : : }
1577 : : }
1578 : 0 : OVS_NOT_REACHED();
1579 : : }
1580 : :
1581 : : /* 16 randomly chosen flows with N >= 3 nonzero values. */
1582 [ + + ]: 11401 : if (choose(16 * (FLOW_U32S - 4), &idx)) {
1583 : 11397 : int n = idx / 16 + 3;
1584 : : int i;
1585 : :
1586 [ + + ]: 850284 : for (i = 0; i < n; i++) {
1587 : 838887 : flow_u32[i] = random_value();
1588 : : }
1589 : 11397 : shuffle_u32s(flow_u32, FLOW_U32S);
1590 : :
1591 : 11397 : return true;
1592 : : }
1593 : :
1594 : 4 : return false;
1595 : : }
1596 : :
1597 : : static void
1598 : 13306 : any_random_flow(struct flow *flow)
1599 : : {
1600 : : static unsigned int max;
1601 [ + + ]: 13306 : if (!max) {
1602 [ + + ]: 13307 : while (next_random_flow(flow, max)) {
1603 : 13306 : max++;
1604 : : }
1605 : : }
1606 : :
1607 : 13306 : next_random_flow(flow, random_range(max));
1608 : 13306 : }
1609 : :
1610 : : static void
1611 : 13306 : toggle_masked_flow_bits(struct flow *flow, const struct flow_wildcards *mask)
1612 : : {
1613 : 13306 : const uint32_t *mask_u32 = (const uint32_t *) &mask->masks;
1614 : 13306 : uint32_t *flow_u32 = (uint32_t *) flow;
1615 : : int i;
1616 : :
1617 [ + + ]: 1955982 : for (i = 0; i < FLOW_U32S; i++) {
1618 [ + + ]: 1942676 : if (mask_u32[i] != 0) {
1619 : : uint32_t bit;
1620 : :
1621 : : do {
1622 : 125185 : bit = 1u << random_range(32);
1623 [ + + ]: 125185 : } while (!(bit & mask_u32[i]));
1624 : 13306 : flow_u32[i] ^= bit;
1625 : : }
1626 : : }
1627 : 13306 : }
1628 : :
1629 : : static void
1630 : 13305 : wildcard_extra_bits(struct flow_wildcards *mask)
1631 : : {
1632 : 13305 : uint32_t *mask_u32 = (uint32_t *) &mask->masks;
1633 : : int i;
1634 : :
1635 [ + + ]: 1955835 : for (i = 0; i < FLOW_U32S; i++) {
1636 [ + + ]: 1942530 : if (mask_u32[i] != 0) {
1637 : : uint32_t bit;
1638 : :
1639 : : do {
1640 : 1839338 : bit = 1u << random_range(32);
1641 [ + + ]: 1839338 : } while (!(bit & mask_u32[i]));
1642 : 191462 : mask_u32[i] &= ~bit;
1643 : : }
1644 : : }
1645 : 13305 : }
1646 : :
1647 : : /* Returns a copy of 'src'. The caller must eventually free the returned
1648 : : * miniflow with free(). */
1649 : : static struct miniflow *
1650 : 13306 : miniflow_clone__(const struct miniflow *src)
1651 : : {
1652 : : struct miniflow *dst;
1653 : : size_t data_size;
1654 : :
1655 : 13306 : data_size = miniflow_alloc(&dst, 1, src);
1656 : 13306 : miniflow_clone(dst, src, data_size / sizeof(uint64_t));
1657 : 13306 : return dst;
1658 : : }
1659 : :
1660 : : /* Returns a hash value for 'flow', given 'basis'. */
1661 : : static inline uint32_t
1662 : 39918 : miniflow_hash__(const struct miniflow *flow, uint32_t basis)
1663 : : {
1664 : 39918 : const uint64_t *p = miniflow_get_values(flow);
1665 : 39918 : size_t n_values = miniflow_n_values(flow);
1666 : 39918 : struct flowmap hash_map = FLOWMAP_EMPTY_INITIALIZER;
1667 : 39918 : uint32_t hash = basis;
1668 : : size_t idx;
1669 : :
1670 [ + + ]: 323304 : FLOWMAP_FOR_EACH_INDEX(idx, flow->map) {
1671 : 283386 : uint64_t value = *p++;
1672 : :
1673 [ + - ]: 283386 : if (value) {
1674 : 283386 : hash = hash_add64(hash, value);
1675 : 283386 : flowmap_set(&hash_map, idx, 1);
1676 : : }
1677 : : }
1678 : : map_t map;
1679 [ + + ]: 119754 : FLOWMAP_FOR_EACH_MAP (map, hash_map) {
1680 : 79836 : hash = hash_add64(hash, map);
1681 : : }
1682 : :
1683 : 39918 : return hash_finish(hash, n_values);
1684 : : }
1685 : :
1686 : : static void
1687 : 1 : test_miniflow(struct ovs_cmdl_context *ctx OVS_UNUSED)
1688 : : {
1689 : : struct flow flow;
1690 : : unsigned int idx;
1691 : :
1692 : 1 : random_set_seed(0xb3faca38);
1693 [ + + ]: 13307 : for (idx = 0; next_random_flow(&flow, idx); idx++) {
1694 : 13306 : const uint64_t *flow_u64 = (const uint64_t *) &flow;
1695 : : struct miniflow *miniflow, *miniflow2, *miniflow3;
1696 : : struct flow flow2, flow3;
1697 : : struct flow_wildcards mask;
1698 : : struct minimask *minimask;
1699 : : int i;
1700 : :
1701 : : /* Convert flow to miniflow. */
1702 : 13306 : miniflow = miniflow_create(&flow);
1703 : :
1704 : : /* Check that the flow equals its miniflow. */
1705 [ - + ]: 13306 : assert(miniflow_get_vid(miniflow) == vlan_tci_to_vid(flow.vlan_tci));
1706 [ + + ]: 984644 : for (i = 0; i < FLOW_U64S; i++) {
1707 [ - + ]: 971338 : assert(miniflow_get(miniflow, i) == flow_u64[i]);
1708 : : }
1709 : :
1710 : : /* Check that the miniflow equals itself. */
1711 [ - + ]: 13306 : assert(miniflow_equal(miniflow, miniflow));
1712 : :
1713 : : /* Convert miniflow back to flow and verify that it's the same. */
1714 : 13306 : miniflow_expand(miniflow, &flow2);
1715 [ - + ]: 13306 : assert(flow_equal(&flow, &flow2));
1716 : :
1717 : : /* Check that copying a miniflow works properly. */
1718 : 13306 : miniflow2 = miniflow_clone__(miniflow);
1719 [ - + ]: 13306 : assert(miniflow_equal(miniflow, miniflow2));
1720 [ - + ]: 13306 : assert(miniflow_hash__(miniflow, 0) == miniflow_hash__(miniflow2, 0));
1721 : 13306 : miniflow_expand(miniflow2, &flow3);
1722 [ - + ]: 13306 : assert(flow_equal(&flow, &flow3));
1723 : :
1724 : : /* Check that masked matches work as expected for identical flows and
1725 : : * miniflows. */
1726 : : do {
1727 : 13306 : next_random_flow(&mask.masks, 1);
1728 [ - + ]: 13306 : } while (flow_wildcards_is_catchall(&mask));
1729 : 13306 : minimask = minimask_create(&mask);
1730 [ - + ]: 13306 : assert(minimask_is_catchall(minimask)
1731 : : == flow_wildcards_is_catchall(&mask));
1732 [ - + ]: 13306 : assert(miniflow_equal_in_minimask(miniflow, miniflow2, minimask));
1733 [ - + ]: 13306 : assert(miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask));
1734 [ - + ]: 13306 : assert(miniflow_hash_in_minimask(miniflow, minimask, 0x12345678) ==
1735 : : flow_hash_in_minimask(&flow, minimask, 0x12345678));
1736 [ - + ]: 13306 : assert(minimask_hash(minimask, 0) ==
1737 : : miniflow_hash__(&minimask->masks, 0));
1738 : :
1739 : : /* Check that masked matches work as expected for differing flows and
1740 : : * miniflows. */
1741 : 13306 : toggle_masked_flow_bits(&flow2, &mask);
1742 [ - + ]: 13306 : assert(!miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask));
1743 : 13306 : miniflow3 = miniflow_create(&flow2);
1744 [ - + ]: 13306 : assert(!miniflow_equal_in_minimask(miniflow, miniflow3, minimask));
1745 : :
1746 : : /* Clean up. */
1747 : 13306 : free(miniflow);
1748 : 13306 : free(miniflow2);
1749 : 13306 : free(miniflow3);
1750 : 13306 : free(minimask);
1751 : : }
1752 : 1 : }
1753 : :
1754 : : static void
1755 : 1 : test_minimask_has_extra(struct ovs_cmdl_context *ctx OVS_UNUSED)
1756 : : {
1757 : : struct flow_wildcards catchall;
1758 : : struct minimask *minicatchall;
1759 : : struct flow flow;
1760 : : unsigned int idx;
1761 : :
1762 : 1 : flow_wildcards_init_catchall(&catchall);
1763 : 1 : minicatchall = minimask_create(&catchall);
1764 [ - + ]: 1 : assert(minimask_is_catchall(minicatchall));
1765 : :
1766 : 1 : random_set_seed(0x2ec7905b);
1767 [ + + ]: 13307 : for (idx = 0; next_random_flow(&flow, idx); idx++) {
1768 : : struct flow_wildcards mask;
1769 : : struct minimask *minimask;
1770 : :
1771 : 13306 : mask.masks = flow;
1772 : 13306 : minimask = minimask_create(&mask);
1773 [ - + ]: 13306 : assert(!minimask_has_extra(minimask, minimask));
1774 [ - + ]: 13306 : assert(minimask_has_extra(minicatchall, minimask)
1775 : : == !minimask_is_catchall(minimask));
1776 [ + + ]: 13306 : if (!minimask_is_catchall(minimask)) {
1777 : : struct minimask *minimask2;
1778 : :
1779 : 13305 : wildcard_extra_bits(&mask);
1780 : 13305 : minimask2 = minimask_create(&mask);
1781 [ - + ]: 13305 : assert(minimask_has_extra(minimask2, minimask));
1782 [ - + ]: 13305 : assert(!minimask_has_extra(minimask, minimask2));
1783 : 13305 : free(minimask2);
1784 : : }
1785 : :
1786 : 13306 : free(minimask);
1787 : : }
1788 : :
1789 : 1 : free(minicatchall);
1790 : 1 : }
1791 : :
1792 : : static void
1793 : 1 : test_minimask_combine(struct ovs_cmdl_context *ctx OVS_UNUSED)
1794 : : {
1795 : : struct flow_wildcards catchall;
1796 : : struct minimask *minicatchall;
1797 : : struct flow flow;
1798 : : unsigned int idx;
1799 : :
1800 : 1 : flow_wildcards_init_catchall(&catchall);
1801 : 1 : minicatchall = minimask_create(&catchall);
1802 [ - + ]: 1 : assert(minimask_is_catchall(minicatchall));
1803 : :
1804 : 1 : random_set_seed(0x181bf0cd);
1805 [ + + ]: 13307 : for (idx = 0; next_random_flow(&flow, idx); idx++) {
1806 : : struct minimask *minimask, *minimask2;
1807 : : struct flow_wildcards mask, mask2, combined, combined2;
1808 : : struct {
1809 : : struct minimask minicombined;
1810 : : uint64_t storage[FLOW_U64S];
1811 : : } m;
1812 : : struct flow flow2;
1813 : :
1814 : 13306 : mask.masks = flow;
1815 : 13306 : minimask = minimask_create(&mask);
1816 : :
1817 : 13306 : minimask_combine(&m.minicombined, minimask, minicatchall, m.storage);
1818 [ - + ]: 13306 : assert(minimask_is_catchall(&m.minicombined));
1819 : :
1820 : 13306 : any_random_flow(&flow2);
1821 : 13306 : mask2.masks = flow2;
1822 : 13306 : minimask2 = minimask_create(&mask2);
1823 : :
1824 : 13306 : minimask_combine(&m.minicombined, minimask, minimask2, m.storage);
1825 : 13306 : flow_wildcards_and(&combined, &mask, &mask2);
1826 : 13306 : minimask_expand(&m.minicombined, &combined2);
1827 [ - + ]: 13306 : assert(flow_wildcards_equal(&combined, &combined2));
1828 : :
1829 : 13306 : free(minimask);
1830 : 13306 : free(minimask2);
1831 : : }
1832 : :
1833 : 1 : free(minicatchall);
1834 : 1 : }
1835 : :
1836 : :
1837 : : static void help(struct ovs_cmdl_context *ctx);
1838 : :
1839 : : static const struct ovs_cmdl_command commands[] = {
1840 : : /* Classifier tests. */
1841 : : {"empty", NULL, 0, 0, test_empty, OVS_RO },
1842 : : {"destroy-null", NULL, 0, 0, test_destroy_null, OVS_RO },
1843 : : {"single-rule", NULL, 0, 0, test_single_rule, OVS_RO },
1844 : : {"rule-replacement", NULL, 0, 0, test_rule_replacement, OVS_RO },
1845 : : {"many-rules-in-one-list", NULL, 0, 1, test_many_rules_in_one_list, OVS_RO },
1846 : : {"many-rules-in-one-table", NULL, 0, 1, test_many_rules_in_one_table, OVS_RO },
1847 : : {"many-rules-in-two-tables", NULL, 0, 0, test_many_rules_in_two_tables, OVS_RO },
1848 : : {"many-rules-in-five-tables", NULL, 0, 0, test_many_rules_in_five_tables, OVS_RO },
1849 : : {"benchmark", NULL, 0, 5, run_benchmarks, OVS_RO },
1850 : :
1851 : : /* Miniflow and minimask tests. */
1852 : : {"miniflow", NULL, 0, 0, test_miniflow, OVS_RO },
1853 : : {"minimask_has_extra", NULL, 0, 0, test_minimask_has_extra, OVS_RO },
1854 : : {"minimask_combine", NULL, 0, 0, test_minimask_combine, OVS_RO },
1855 : :
1856 : : {"--help", NULL, 0, 0, help, OVS_RO },
1857 : : {NULL, NULL, 0, 0, NULL, OVS_RO },
1858 : : };
1859 : :
1860 : : static void
1861 : 0 : help(struct ovs_cmdl_context *ctx OVS_UNUSED)
1862 : : {
1863 : : const struct ovs_cmdl_command *p;
1864 : 0 : struct ds test_names = DS_EMPTY_INITIALIZER;
1865 : 0 : const int linesize = 80;
1866 : :
1867 : 0 : printf("usage: ovstest %s TEST [TESTARGS]\n"
1868 : : "where TEST is one of the following:\n\n",
1869 : : program_name);
1870 : :
1871 [ # # ]: 0 : for (p = commands; p->name != NULL; p++) {
1872 [ # # ]: 0 : if (*p->name != '-') { /* Skip internal commands */
1873 [ # # ]: 0 : if (test_names.length > 1
1874 [ # # ]: 0 : && test_names.length + strlen(p->name) + 1 >= linesize) {
1875 : 0 : test_names.length -= 1;
1876 : 0 : printf ("%s\n", ds_cstr(&test_names));
1877 : 0 : ds_clear(&test_names);
1878 : : }
1879 : 0 : ds_put_format(&test_names, "%s, ", p->name);
1880 : : }
1881 : : }
1882 [ # # ]: 0 : if (test_names.length > 2) {
1883 : 0 : test_names.length -= 2;
1884 : 0 : printf("%s\n", ds_cstr(&test_names));
1885 : : }
1886 : 0 : ds_destroy(&test_names);
1887 : 0 : }
1888 : :
1889 : : static void
1890 : 15 : test_classifier_main(int argc, char *argv[])
1891 : : {
1892 : 45 : struct ovs_cmdl_context ctx = {
1893 : 15 : .argc = argc - 1,
1894 : 15 : .argv = argv + 1,
1895 : : };
1896 : 15 : set_program_name(argv[0]);
1897 : :
1898 [ + - ][ + + ]: 15 : if (argc > 1 && !strcmp(argv[1], "--versioned")) {
1899 : 4 : versioned = true;
1900 : 4 : ctx.argc--;
1901 : 4 : ctx.argv++;
1902 : : }
1903 : :
1904 : 15 : init_values();
1905 : 15 : ovs_cmdl_run_command(&ctx, commands);
1906 : 15 : }
1907 : :
1908 : 1204 : OVSTEST_REGISTER("test-classifier", test_classifier_main);
|
