socket-util: Move get_max_fds() to process.c.
[sliver-openvswitch.git] / lib / classifier.c
1 /*
2  * Copyright (c) 2009, 2010, 2011, 2012, 2013 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 #include <config.h>
18 #include "classifier.h"
19 #include <errno.h>
20 #include <netinet/in.h>
21 #include "byte-order.h"
22 #include "dynamic-string.h"
23 #include "flow.h"
24 #include "hash.h"
25 #include "odp-util.h"
26 #include "ofp-util.h"
27 #include "ovs-thread.h"
28 #include "packets.h"
29 #include "vlog.h"
30
31 VLOG_DEFINE_THIS_MODULE(classifier);
32
33 struct trie_ctx;
34 static struct cls_subtable *find_subtable(const struct classifier *,
35                                           const struct minimask *);
36 static struct cls_subtable *insert_subtable(struct classifier *,
37                                             const struct minimask *);
38
39 static void destroy_subtable(struct classifier *, struct cls_subtable *);
40
41 static void update_subtables_after_insertion(struct classifier *,
42                                              struct cls_subtable *,
43                                              unsigned int new_priority);
44 static void update_subtables_after_removal(struct classifier *,
45                                            struct cls_subtable *,
46                                            unsigned int del_priority);
47
48 static struct cls_rule *find_match_wc(const struct cls_subtable *,
49                                       const struct flow *, struct trie_ctx *,
50                                       unsigned int n_tries,
51                                       struct flow_wildcards *);
52 static struct cls_rule *find_equal(struct cls_subtable *,
53                                    const struct miniflow *, uint32_t hash);
54 static struct cls_rule *insert_rule(struct classifier *,
55                                     struct cls_subtable *, struct cls_rule *);
56
57 /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
58 #define FOR_EACH_RULE_IN_LIST(RULE, HEAD)                               \
59     for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE))
60 #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD)                    \
61     for ((RULE) = (HEAD);                                               \
62          (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true);    \
63          (RULE) = (NEXT))
64
65 static struct cls_rule *next_rule_in_list__(struct cls_rule *);
66 static struct cls_rule *next_rule_in_list(struct cls_rule *);
67
68 static unsigned int minimask_get_prefix_len(const struct minimask *,
69                                             const struct mf_field *);
70 static void trie_init(struct classifier *, int trie_idx,
71                       const struct mf_field *);
72 static unsigned int trie_lookup(const struct cls_trie *, const struct flow *,
73                                 unsigned int *checkbits);
74
75 static void trie_destroy(struct trie_node *);
76 static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen);
77 static void trie_remove(struct cls_trie *, const struct cls_rule *, int mlen);
78 static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs,
79                                  unsigned int nbits);
80 static bool mask_prefix_bits_set(const struct flow_wildcards *,
81                                  uint8_t be32ofs, unsigned int nbits);
82 \f
83 /* cls_rule. */
84
85 /* Initializes 'rule' to match packets specified by 'match' at the given
86  * 'priority'.  'match' must satisfy the invariant described in the comment at
87  * the definition of struct match.
88  *
89  * The caller must eventually destroy 'rule' with cls_rule_destroy().
90  *
91  * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but
92  * internally Open vSwitch supports a wider range.) */
93 void
94 cls_rule_init(struct cls_rule *rule,
95               const struct match *match, unsigned int priority)
96 {
97     minimatch_init(&rule->match, match);
98     rule->priority = priority;
99 }
100
101 /* Same as cls_rule_init() for initialization from a "struct minimatch". */
102 void
103 cls_rule_init_from_minimatch(struct cls_rule *rule,
104                              const struct minimatch *match,
105                              unsigned int priority)
106 {
107     minimatch_clone(&rule->match, match);
108     rule->priority = priority;
109 }
110
111 /* Initializes 'dst' as a copy of 'src'.
112  *
113  * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
114 void
115 cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
116 {
117     minimatch_clone(&dst->match, &src->match);
118     dst->priority = src->priority;
119 }
120
121 /* Initializes 'dst' with the data in 'src', destroying 'src'.
122  *
123  * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
124 void
125 cls_rule_move(struct cls_rule *dst, struct cls_rule *src)
126 {
127     minimatch_move(&dst->match, &src->match);
128     dst->priority = src->priority;
129 }
130
131 /* Frees memory referenced by 'rule'.  Doesn't free 'rule' itself (it's
132  * normally embedded into a larger structure).
133  *
134  * ('rule' must not currently be in a classifier.) */
135 void
136 cls_rule_destroy(struct cls_rule *rule)
137 {
138     minimatch_destroy(&rule->match);
139 }
140
141 /* Returns true if 'a' and 'b' match the same packets at the same priority,
142  * false if they differ in some way. */
143 bool
144 cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
145 {
146     return a->priority == b->priority && minimatch_equal(&a->match, &b->match);
147 }
148
149 /* Returns a hash value for 'rule', folding in 'basis'. */
150 uint32_t
151 cls_rule_hash(const struct cls_rule *rule, uint32_t basis)
152 {
153     return minimatch_hash(&rule->match, hash_int(rule->priority, basis));
154 }
155
156 /* Appends a string describing 'rule' to 's'. */
157 void
158 cls_rule_format(const struct cls_rule *rule, struct ds *s)
159 {
160     minimatch_format(&rule->match, s, rule->priority);
161 }
162
163 /* Returns true if 'rule' matches every packet, false otherwise. */
164 bool
165 cls_rule_is_catchall(const struct cls_rule *rule)
166 {
167     return minimask_is_catchall(&rule->match.mask);
168 }
169 \f
170 /* Initializes 'cls' as a classifier that initially contains no classification
171  * rules. */
172 void
173 classifier_init(struct classifier *cls, const uint8_t *flow_segments)
174 {
175     cls->n_rules = 0;
176     hmap_init(&cls->subtables);
177     list_init(&cls->subtables_priority);
178     hmap_init(&cls->partitions);
179     fat_rwlock_init(&cls->rwlock);
180     cls->n_flow_segments = 0;
181     if (flow_segments) {
182         while (cls->n_flow_segments < CLS_MAX_INDICES
183                && *flow_segments < FLOW_U32S) {
184             cls->flow_segments[cls->n_flow_segments++] = *flow_segments++;
185         }
186     }
187     cls->n_tries = 0;
188 }
189
190 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
191  * caller's responsibility. */
192 void
193 classifier_destroy(struct classifier *cls)
194 {
195     if (cls) {
196         struct cls_subtable *partition, *next_partition;
197         struct cls_subtable *subtable, *next_subtable;
198         int i;
199
200         for (i = 0; i < cls->n_tries; i++) {
201             trie_destroy(cls->tries[i].root);
202         }
203
204         HMAP_FOR_EACH_SAFE (subtable, next_subtable, hmap_node,
205                             &cls->subtables) {
206             destroy_subtable(cls, subtable);
207         }
208         hmap_destroy(&cls->subtables);
209
210         HMAP_FOR_EACH_SAFE (partition, next_partition, hmap_node,
211                             &cls->partitions) {
212             hmap_remove(&cls->partitions, &partition->hmap_node);
213             free(partition);
214         }
215         hmap_destroy(&cls->partitions);
216         fat_rwlock_destroy(&cls->rwlock);
217     }
218 }
219
220 /* We use uint64_t as a set for the fields below. */
221 BUILD_ASSERT_DECL(MFF_N_IDS <= 64);
222
223 /* Set the fields for which prefix lookup should be performed. */
224 void
225 classifier_set_prefix_fields(struct classifier *cls,
226                              const enum mf_field_id *trie_fields,
227                              unsigned int n_fields)
228 {
229     uint64_t fields = 0;
230     int i, trie;
231
232     for (i = 0, trie = 0; i < n_fields && trie < CLS_MAX_TRIES; i++) {
233         const struct mf_field *field = mf_from_id(trie_fields[i]);
234         if (field->flow_be32ofs < 0 || field->n_bits % 32) {
235             /* Incompatible field.  This is the only place where we
236              * enforce these requirements, but the rest of the trie code
237              * depends on the flow_be32ofs to be non-negative and the
238              * field length to be a multiple of 32 bits. */
239             continue;
240         }
241
242         if (fields & (UINT64_C(1) << trie_fields[i])) {
243             /* Duplicate field, there is no need to build more than
244              * one index for any one field. */
245             continue;
246         }
247         fields |= UINT64_C(1) << trie_fields[i];
248
249         if (trie >= cls->n_tries || field != cls->tries[trie].field) {
250             trie_init(cls, trie, field);
251         }
252         trie++;
253     }
254
255     /* Destroy the rest. */
256     for (i = trie; i < cls->n_tries; i++) {
257         trie_init(cls, i, NULL);
258     }
259     cls->n_tries = trie;
260 }
261
262 static void
263 trie_init(struct classifier *cls, int trie_idx,
264           const struct mf_field *field)
265 {
266     struct cls_trie *trie = &cls->tries[trie_idx];
267     struct cls_subtable *subtable;
268
269     if (trie_idx < cls->n_tries) {
270         trie_destroy(trie->root);
271     }
272     trie->root = NULL;
273     trie->field = field;
274
275     /* Add existing rules to the trie. */
276     LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
277         unsigned int plen;
278
279         plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0;
280         /* Initialize subtable's prefix length on this field. */
281         subtable->trie_plen[trie_idx] = plen;
282
283         if (plen) {
284             struct cls_rule *head;
285
286             HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
287                 struct cls_rule *rule;
288
289                 FOR_EACH_RULE_IN_LIST (rule, head) {
290                     trie_insert(trie, rule, plen);
291                 }
292             }
293         }
294     }
295 }
296
297 /* Returns true if 'cls' contains no classification rules, false otherwise. */
298 bool
299 classifier_is_empty(const struct classifier *cls)
300 {
301     return cls->n_rules == 0;
302 }
303
304 /* Returns the number of rules in 'cls'. */
305 int
306 classifier_count(const struct classifier *cls)
307 {
308     return cls->n_rules;
309 }
310
311 static uint32_t
312 hash_metadata(ovs_be64 metadata_)
313 {
314     uint64_t metadata = (OVS_FORCE uint64_t) metadata_;
315     return hash_2words(metadata, metadata >> 32);
316 }
317
318 static struct cls_partition *
319 find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash)
320 {
321     struct cls_partition *partition;
322
323     HMAP_FOR_EACH_IN_BUCKET (partition, hmap_node, hash, &cls->partitions) {
324         if (partition->metadata == metadata) {
325             return partition;
326         }
327     }
328
329     return NULL;
330 }
331
332 static struct cls_partition *
333 create_partition(struct classifier *cls, struct cls_subtable *subtable,
334                  ovs_be64 metadata)
335 {
336     uint32_t hash = hash_metadata(metadata);
337     struct cls_partition *partition = find_partition(cls, metadata, hash);
338     if (!partition) {
339         partition = xmalloc(sizeof *partition);
340         partition->metadata = metadata;
341         partition->tags = 0;
342         tag_tracker_init(&partition->tracker);
343         hmap_insert(&cls->partitions, &partition->hmap_node, hash);
344     }
345     tag_tracker_add(&partition->tracker, &partition->tags, subtable->tag);
346     return partition;
347 }
348
349 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
350  * must not modify or free it.
351  *
352  * If 'cls' already contains an identical rule (including wildcards, values of
353  * fixed fields, and priority), replaces the old rule by 'rule' and returns the
354  * rule that was replaced.  The caller takes ownership of the returned rule and
355  * is thus responsible for destroying it with cls_rule_destroy(), freeing the
356  * memory block in which it resides, etc., as necessary.
357  *
358  * Returns NULL if 'cls' does not contain a rule with an identical key, after
359  * inserting the new rule.  In this case, no rules are displaced by the new
360  * rule, even rules that cannot have any effect because the new rule matches a
361  * superset of their flows and has higher priority. */
362 struct cls_rule *
363 classifier_replace(struct classifier *cls, struct cls_rule *rule)
364 {
365     struct cls_rule *old_rule;
366     struct cls_subtable *subtable;
367
368     subtable = find_subtable(cls, &rule->match.mask);
369     if (!subtable) {
370         subtable = insert_subtable(cls, &rule->match.mask);
371     }
372
373     old_rule = insert_rule(cls, subtable, rule);
374     if (!old_rule) {
375         int i;
376
377         if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
378             ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
379             rule->partition = create_partition(cls, subtable, metadata);
380         } else {
381             rule->partition = NULL;
382         }
383
384         subtable->n_rules++;
385         cls->n_rules++;
386
387         for (i = 0; i < cls->n_tries; i++) {
388             if (subtable->trie_plen[i]) {
389                 trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
390             }
391         }
392     } else {
393         rule->partition = old_rule->partition;
394     }
395     return old_rule;
396 }
397
398 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
399  * must not modify or free it.
400  *
401  * 'cls' must not contain an identical rule (including wildcards, values of
402  * fixed fields, and priority).  Use classifier_find_rule_exactly() to find
403  * such a rule. */
404 void
405 classifier_insert(struct classifier *cls, struct cls_rule *rule)
406 {
407     struct cls_rule *displaced_rule = classifier_replace(cls, rule);
408     ovs_assert(!displaced_rule);
409 }
410
411 /* Removes 'rule' from 'cls'.  It is the caller's responsibility to destroy
412  * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule'
413  * resides, etc., as necessary. */
414 void
415 classifier_remove(struct classifier *cls, struct cls_rule *rule)
416 {
417     struct cls_partition *partition;
418     struct cls_rule *head;
419     struct cls_subtable *subtable;
420     int i;
421
422     subtable = find_subtable(cls, &rule->match.mask);
423
424     for (i = 0; i < cls->n_tries; i++) {
425         if (subtable->trie_plen[i]) {
426             trie_remove(&cls->tries[i], rule, subtable->trie_plen[i]);
427         }
428     }
429
430     /* Remove rule node from indices. */
431     for (i = 0; i < subtable->n_indices; i++) {
432         hindex_remove(&subtable->indices[i], &rule->index_nodes[i]);
433     }
434
435     head = find_equal(subtable, &rule->match.flow, rule->hmap_node.hash);
436     if (head != rule) {
437         list_remove(&rule->list);
438     } else if (list_is_empty(&rule->list)) {
439         hmap_remove(&subtable->rules, &rule->hmap_node);
440     } else {
441         struct cls_rule *next = CONTAINER_OF(rule->list.next,
442                                              struct cls_rule, list);
443
444         list_remove(&rule->list);
445         hmap_replace(&subtable->rules, &rule->hmap_node, &next->hmap_node);
446     }
447
448     partition = rule->partition;
449     if (partition) {
450         tag_tracker_subtract(&partition->tracker, &partition->tags,
451                              subtable->tag);
452         if (!partition->tags) {
453             hmap_remove(&cls->partitions, &partition->hmap_node);
454             free(partition);
455         }
456     }
457
458     if (--subtable->n_rules == 0) {
459         destroy_subtable(cls, subtable);
460     } else {
461         update_subtables_after_removal(cls, subtable, rule->priority);
462     }
463
464     cls->n_rules--;
465 }
466
467 /* Prefix tree context.  Valid when 'lookup_done' is true.  Can skip all
468  * subtables which have more than 'match_plen' bits in their corresponding
469  * field at offset 'be32ofs'.  If skipped, 'maskbits' prefix bits should be
470  * unwildcarded to quarantee datapath flow matches only packets it should. */
471 struct trie_ctx {
472     const struct cls_trie *trie;
473     bool lookup_done;        /* Status of the lookup. */
474     uint8_t be32ofs;         /* U32 offset of the field in question. */
475     unsigned int match_plen; /* Longest prefix than could possibly match. */
476     unsigned int maskbits;   /* Prefix length needed to avoid false matches. */
477 };
478
479 static void
480 trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
481 {
482     ctx->trie = trie;
483     ctx->be32ofs = trie->field->flow_be32ofs;
484     ctx->lookup_done = false;
485 }
486
487 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
488  * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
489  * of equal priority match 'flow', returns one arbitrarily.
490  *
491  * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
492  * set of bits that were significant in the lookup.  At some point
493  * earlier, 'wc' should have been initialized (e.g., by
494  * flow_wildcards_init_catchall()). */
495 struct cls_rule *
496 classifier_lookup(const struct classifier *cls, const struct flow *flow,
497                   struct flow_wildcards *wc)
498 {
499     const struct cls_partition *partition;
500     struct cls_subtable *subtable;
501     struct cls_rule *best;
502     tag_type tags;
503     struct trie_ctx trie_ctx[CLS_MAX_TRIES];
504     int i;
505
506     /* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them,
507      * then 'flow' cannot possibly match in 'subtable':
508      *
509      *     - If flow->metadata maps to a given 'partition', then we can use
510      *       'tags' for 'partition->tags'.
511      *
512      *     - If flow->metadata has no partition, then no rule in 'cls' has an
513      *       exact-match for flow->metadata.  That means that we don't need to
514      *       search any subtable that includes flow->metadata in its mask.
515      *
516      * In either case, we always need to search any cls_subtables that do not
517      * include flow->metadata in its mask.  One way to do that would be to
518      * check the "cls_subtable"s explicitly for that, but that would require an
519      * extra branch per subtable.  Instead, we mark such a cls_subtable's
520      * 'tags' as TAG_ALL and make sure that 'tags' is never empty.  This means
521      * that 'tags' always intersects such a cls_subtable's 'tags', so we don't
522      * need a special case.
523      */
524     partition = (hmap_is_empty(&cls->partitions)
525                  ? NULL
526                  : find_partition(cls, flow->metadata,
527                                   hash_metadata(flow->metadata)));
528     tags = partition ? partition->tags : TAG_ARBITRARY;
529
530     /* Initialize trie contexts for match_find_wc(). */
531     for (i = 0; i < cls->n_tries; i++) {
532         trie_ctx_init(&trie_ctx[i], &cls->tries[i]);
533     }
534     best = NULL;
535     LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
536         struct cls_rule *rule;
537
538         if (!tag_intersects(tags, subtable->tag)) {
539             continue;
540         }
541
542         rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc);
543         if (rule) {
544             best = rule;
545             LIST_FOR_EACH_CONTINUE (subtable, list_node,
546                                     &cls->subtables_priority) {
547                 if (subtable->max_priority <= best->priority) {
548                     /* Subtables are in descending priority order,
549                      * can not find anything better. */
550                     return best;
551                 }
552                 if (!tag_intersects(tags, subtable->tag)) {
553                     continue;
554                 }
555
556                 rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries,
557                                      wc);
558                 if (rule && rule->priority > best->priority) {
559                     best = rule;
560                 }
561             }
562             break;
563         }
564     }
565
566     return best;
567 }
568
569 /* Finds and returns a rule in 'cls' with exactly the same priority and
570  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
571  * contain an exact match. */
572 struct cls_rule *
573 classifier_find_rule_exactly(const struct classifier *cls,
574                              const struct cls_rule *target)
575 {
576     struct cls_rule *head, *rule;
577     struct cls_subtable *subtable;
578
579     subtable = find_subtable(cls, &target->match.mask);
580     if (!subtable) {
581         return NULL;
582     }
583
584     /* Skip if there is no hope. */
585     if (target->priority > subtable->max_priority) {
586         return NULL;
587     }
588
589     head = find_equal(subtable, &target->match.flow,
590                       miniflow_hash_in_minimask(&target->match.flow,
591                                                 &target->match.mask, 0));
592     FOR_EACH_RULE_IN_LIST (rule, head) {
593         if (target->priority >= rule->priority) {
594             return target->priority == rule->priority ? rule : NULL;
595         }
596     }
597     return NULL;
598 }
599
600 /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
601  * same matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
602  * contain an exact match. */
603 struct cls_rule *
604 classifier_find_match_exactly(const struct classifier *cls,
605                               const struct match *target,
606                               unsigned int priority)
607 {
608     struct cls_rule *retval;
609     struct cls_rule cr;
610
611     cls_rule_init(&cr, target, priority);
612     retval = classifier_find_rule_exactly(cls, &cr);
613     cls_rule_destroy(&cr);
614
615     return retval;
616 }
617
618 /* Checks if 'target' would overlap any other rule in 'cls'.  Two rules are
619  * considered to overlap if both rules have the same priority and a packet
620  * could match both. */
621 bool
622 classifier_rule_overlaps(const struct classifier *cls,
623                          const struct cls_rule *target)
624 {
625     struct cls_subtable *subtable;
626
627     /* Iterate subtables in the descending max priority order. */
628     LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
629         uint32_t storage[FLOW_U32S];
630         struct minimask mask;
631         struct cls_rule *head;
632
633         if (target->priority > subtable->max_priority) {
634             break; /* Can skip this and the rest of the subtables. */
635         }
636
637         minimask_combine(&mask, &target->match.mask, &subtable->mask, storage);
638         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
639             struct cls_rule *rule;
640
641             FOR_EACH_RULE_IN_LIST (rule, head) {
642                 if (rule->priority < target->priority) {
643                     break; /* Rules in descending priority order. */
644                 }
645                 if (rule->priority == target->priority
646                     && miniflow_equal_in_minimask(&target->match.flow,
647                                                   &rule->match.flow, &mask)) {
648                     return true;
649                 }
650             }
651         }
652     }
653
654     return false;
655 }
656
657 /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
658  * specific than 'criteria'.  That is, 'rule' matches 'criteria' and this
659  * function returns true if, for every field:
660  *
661  *   - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
662  *     field, or
663  *
664  *   - 'criteria' wildcards the field,
665  *
666  * Conversely, 'rule' does not match 'criteria' and this function returns false
667  * if, for at least one field:
668  *
669  *   - 'criteria' and 'rule' specify different values for the field, or
670  *
671  *   - 'criteria' specifies a value for the field but 'rule' wildcards it.
672  *
673  * Equivalently, the truth table for whether a field matches is:
674  *
675  *                                     rule
676  *
677  *                   c         wildcard    exact
678  *                   r        +---------+---------+
679  *                   i   wild |   yes   |   yes   |
680  *                   t   card |         |         |
681  *                   e        +---------+---------+
682  *                   r  exact |    no   |if values|
683  *                   i        |         |are equal|
684  *                   a        +---------+---------+
685  *
686  * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
687  * commands and by OpenFlow 1.0 aggregate and flow stats.
688  *
689  * Ignores rule->priority. */
690 bool
691 cls_rule_is_loose_match(const struct cls_rule *rule,
692                         const struct minimatch *criteria)
693 {
694     return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
695             && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
696                                           &criteria->mask));
697 }
698 \f
699 /* Iteration. */
700
701 static bool
702 rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
703 {
704     return (!target
705             || miniflow_equal_in_minimask(&rule->match.flow,
706                                           &target->match.flow,
707                                           &target->match.mask));
708 }
709
710 static struct cls_rule *
711 search_subtable(const struct cls_subtable *subtable,
712                 const struct cls_rule *target)
713 {
714     if (!target || !minimask_has_extra(&subtable->mask, &target->match.mask)) {
715         struct cls_rule *rule;
716
717         HMAP_FOR_EACH (rule, hmap_node, &subtable->rules) {
718             if (rule_matches(rule, target)) {
719                 return rule;
720             }
721         }
722     }
723     return NULL;
724 }
725
726 /* Initializes 'cursor' for iterating through rules in 'cls':
727  *
728  *     - If 'target' is null, the cursor will visit every rule in 'cls'.
729  *
730  *     - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
731  *       such that cls_rule_is_loose_match(rule, target) returns true.
732  *
733  * Ignores target->priority. */
734 void
735 cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
736                 const struct cls_rule *target)
737 {
738     cursor->cls = cls;
739     cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL;
740 }
741
742 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
743  * pointer if there are no matches. */
744 struct cls_rule *
745 cls_cursor_first(struct cls_cursor *cursor)
746 {
747     struct cls_subtable *subtable;
748
749     HMAP_FOR_EACH (subtable, hmap_node, &cursor->cls->subtables) {
750         struct cls_rule *rule = search_subtable(subtable, cursor->target);
751         if (rule) {
752             cursor->subtable = subtable;
753             return rule;
754         }
755     }
756
757     return NULL;
758 }
759
760 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
761  * pointer if there are no more matches. */
762 struct cls_rule *
763 cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_)
764 {
765     struct cls_rule *rule = CONST_CAST(struct cls_rule *, rule_);
766     const struct cls_subtable *subtable;
767     struct cls_rule *next;
768
769     next = next_rule_in_list__(rule);
770     if (next->priority < rule->priority) {
771         return next;
772     }
773
774     /* 'next' is the head of the list, that is, the rule that is included in
775      * the subtable's hmap.  (This is important when the classifier contains
776      * rules that differ only in priority.) */
777     rule = next;
778     HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->subtable->rules) {
779         if (rule_matches(rule, cursor->target)) {
780             return rule;
781         }
782     }
783
784     subtable = cursor->subtable;
785     HMAP_FOR_EACH_CONTINUE (subtable, hmap_node, &cursor->cls->subtables) {
786         rule = search_subtable(subtable, cursor->target);
787         if (rule) {
788             cursor->subtable = subtable;
789             return rule;
790         }
791     }
792
793     return NULL;
794 }
795 \f
796 static struct cls_subtable *
797 find_subtable(const struct classifier *cls, const struct minimask *mask)
798 {
799     struct cls_subtable *subtable;
800
801     HMAP_FOR_EACH_IN_BUCKET (subtable, hmap_node, minimask_hash(mask, 0),
802                              &cls->subtables) {
803         if (minimask_equal(mask, &subtable->mask)) {
804             return subtable;
805         }
806     }
807     return NULL;
808 }
809
810 static struct cls_subtable *
811 insert_subtable(struct classifier *cls, const struct minimask *mask)
812 {
813     uint32_t hash = minimask_hash(mask, 0);
814     struct cls_subtable *subtable;
815     int i, index = 0;
816     struct flow_wildcards old, new;
817     uint8_t prev;
818
819     subtable = xzalloc(sizeof *subtable);
820     hmap_init(&subtable->rules);
821     minimask_clone(&subtable->mask, mask);
822
823     /* Init indices for segmented lookup, if any. */
824     flow_wildcards_init_catchall(&new);
825     old = new;
826     prev = 0;
827     for (i = 0; i < cls->n_flow_segments; i++) {
828         flow_wildcards_fold_minimask_range(&new, mask, prev,
829                                            cls->flow_segments[i]);
830         /* Add an index if it adds mask bits. */
831         if (!flow_wildcards_equal(&new, &old)) {
832             hindex_init(&subtable->indices[index]);
833             subtable->index_ofs[index] = cls->flow_segments[i];
834             index++;
835             old = new;
836         }
837         prev = cls->flow_segments[i];
838     }
839     /* Check if the rest of the subtable's mask adds any bits,
840      * and remove the last index if it doesn't. */
841     if (index > 0) {
842         flow_wildcards_fold_minimask_range(&new, mask, prev, FLOW_U32S);
843         if (flow_wildcards_equal(&new, &old)) {
844             --index;
845             subtable->index_ofs[index] = 0;
846             hindex_destroy(&subtable->indices[index]);
847         }
848     }
849     subtable->n_indices = index;
850
851     hmap_insert(&cls->subtables, &subtable->hmap_node, hash);
852     list_push_back(&cls->subtables_priority, &subtable->list_node);
853     subtable->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX
854                      ? tag_create_deterministic(hash)
855                      : TAG_ALL);
856
857     for (i = 0; i < cls->n_tries; i++) {
858         subtable->trie_plen[i] = minimask_get_prefix_len(mask,
859                                                          cls->tries[i].field);
860     }
861
862     return subtable;
863 }
864
865 static void
866 destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
867 {
868     int i;
869
870     for (i = 0; i < subtable->n_indices; i++) {
871         hindex_destroy(&subtable->indices[i]);
872     }
873     minimask_destroy(&subtable->mask);
874     hmap_remove(&cls->subtables, &subtable->hmap_node);
875     hmap_destroy(&subtable->rules);
876     list_remove(&subtable->list_node);
877     free(subtable);
878 }
879
880 /* This function performs the following updates for 'subtable' in 'cls'
881  * following the addition of a new rule with priority 'new_priority' to
882  * 'subtable':
883  *
884  *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
885  *
886  *    - Update 'subtable''s position in 'cls->subtables_priority' if necessary.
887  *
888  * This function should only be called after adding a new rule, not after
889  * replacing a rule by an identical one or modifying a rule in-place. */
890 static void
891 update_subtables_after_insertion(struct classifier *cls,
892                                  struct cls_subtable *subtable,
893                                  unsigned int new_priority)
894 {
895     if (new_priority == subtable->max_priority) {
896         ++subtable->max_count;
897     } else if (new_priority > subtable->max_priority) {
898         struct cls_subtable *iter;
899
900         subtable->max_priority = new_priority;
901         subtable->max_count = 1;
902
903         /* Possibly move 'subtable' earlier in the priority list.  If we break
904          * out of the loop, then 'subtable' should be moved just after that
905          * 'iter'.  If the loop terminates normally, then 'iter' will be the
906          * list head and we'll move subtable just after that (e.g. to the front
907          * of the list). */
908         iter = subtable;
909         LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node,
910                                         &cls->subtables_priority) {
911             if (iter->max_priority >= subtable->max_priority) {
912                 break;
913             }
914         }
915
916         /* Move 'subtable' just after 'iter' (unless it's already there). */
917         if (iter->list_node.next != &subtable->list_node) {
918             list_splice(iter->list_node.next,
919                         &subtable->list_node, subtable->list_node.next);
920         }
921     }
922 }
923
924 /* This function performs the following updates for 'subtable' in 'cls'
925  * following the deletion of a rule with priority 'del_priority' from
926  * 'subtable':
927  *
928  *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
929  *
930  *    - Update 'subtable''s position in 'cls->subtables_priority' if necessary.
931  *
932  * This function should only be called after removing a rule, not after
933  * replacing a rule by an identical one or modifying a rule in-place. */
934 static void
935 update_subtables_after_removal(struct classifier *cls,
936                                struct cls_subtable *subtable,
937                                unsigned int del_priority)
938 {
939     struct cls_subtable *iter;
940
941     if (del_priority == subtable->max_priority && --subtable->max_count == 0) {
942         struct cls_rule *head;
943
944         subtable->max_priority = 0;
945         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
946             if (head->priority > subtable->max_priority) {
947                 subtable->max_priority = head->priority;
948                 subtable->max_count = 1;
949             } else if (head->priority == subtable->max_priority) {
950                 ++subtable->max_count;
951             }
952         }
953
954         /* Possibly move 'subtable' later in the priority list.  If we break
955          * out of the loop, then 'subtable' should be moved just before that
956          * 'iter'.  If the loop terminates normally, then 'iter' will be the
957          * list head and we'll move subtable just before that (e.g. to the back
958          * of the list). */
959         iter = subtable;
960         LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->subtables_priority) {
961             if (iter->max_priority <= subtable->max_priority) {
962                 break;
963             }
964         }
965
966         /* Move 'subtable' just before 'iter' (unless it's already there). */
967         if (iter->list_node.prev != &subtable->list_node) {
968             list_splice(&iter->list_node,
969                         &subtable->list_node, subtable->list_node.next);
970         }
971     }
972 }
973
974 struct range {
975     uint8_t start;
976     uint8_t end;
977 };
978
979 /* Return 'true' if can skip rest of the subtable based on the prefix trie
980  * lookup results. */
981 static inline bool
982 check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
983             const unsigned int field_plen[CLS_MAX_TRIES],
984             const struct range ofs, const struct flow *flow,
985             struct flow_wildcards *wc)
986 {
987     int j;
988
989     /* Check if we could avoid fully unwildcarding the next level of
990      * fields using the prefix tries.  The trie checks are done only as
991      * needed to avoid folding in additional bits to the wildcards mask. */
992     for (j = 0; j < n_tries; j++) {
993         /* Is the trie field relevant for this subtable? */
994         if (field_plen[j]) {
995             struct trie_ctx *ctx = &trie_ctx[j];
996             uint8_t be32ofs = ctx->be32ofs;
997
998             /* Is the trie field within the current range of fields? */
999             if (be32ofs >= ofs.start && be32ofs < ofs.end) {
1000                 /* On-demand trie lookup. */
1001                 if (!ctx->lookup_done) {
1002                     ctx->match_plen = trie_lookup(ctx->trie, flow,
1003                                                   &ctx->maskbits);
1004                     ctx->lookup_done = true;
1005                 }
1006                 /* Possible to skip the rest of the subtable if subtable's
1007                  * prefix on the field is longer than what is known to match
1008                  * based on the trie lookup. */
1009                 if (field_plen[j] > ctx->match_plen) {
1010                     /* RFC: We want the trie lookup to never result in
1011                      * unwildcarding any bits that would not be unwildcarded
1012                      * otherwise.  Since the trie is shared by the whole
1013                      * classifier, it is possible that the 'maskbits' contain
1014                      * bits that are irrelevant for the partition of the
1015                      * classifier relevant for the current flow. */
1016
1017                     /* Can skip if the field is already unwildcarded. */
1018                     if (mask_prefix_bits_set(wc, be32ofs, ctx->maskbits)) {
1019                         return true;
1020                     }
1021                     /* Check that the trie result will not unwildcard more bits
1022                      * than this stage will. */
1023                     if (ctx->maskbits <= field_plen[j]) {
1024                         /* Unwildcard the bits and skip the rest. */
1025                         mask_set_prefix_bits(wc, be32ofs, ctx->maskbits);
1026                         /* Note: Prerequisite already unwildcarded, as the only
1027                          * prerequisite of the supported trie lookup fields is
1028                          * the ethertype, which is currently always
1029                          * unwildcarded.
1030                          */
1031                         return true;
1032                     }
1033                 }
1034             }
1035         }
1036     }
1037     return false;
1038 }
1039
1040 static inline struct cls_rule *
1041 find_match(const struct cls_subtable *subtable, const struct flow *flow,
1042            uint32_t hash)
1043 {
1044     struct cls_rule *rule;
1045
1046     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
1047         if (minimatch_matches_flow(&rule->match, flow)) {
1048             return rule;
1049         }
1050     }
1051
1052     return NULL;
1053 }
1054
1055 static struct cls_rule *
1056 find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
1057               struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
1058               struct flow_wildcards *wc)
1059 {
1060     uint32_t basis = 0, hash;
1061     struct cls_rule *rule = NULL;
1062     int i;
1063     struct range ofs;
1064
1065     if (!wc) {
1066         return find_match(subtable, flow,
1067                           flow_hash_in_minimask(flow, &subtable->mask, 0));
1068     }
1069
1070     ofs.start = 0;
1071     /* Try to finish early by checking fields in segments. */
1072     for (i = 0; i < subtable->n_indices; i++) {
1073         struct hindex_node *inode;
1074         ofs.end = subtable->index_ofs[i];
1075
1076         if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow,
1077                         wc)) {
1078             goto range_out;
1079         }
1080         hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
1081                                            ofs.end, &basis);
1082         ofs.start = ofs.end;
1083         inode = hindex_node_with_hash(&subtable->indices[i], hash);
1084         if (!inode) {
1085             /* No match, can stop immediately, but must fold in the mask
1086              * covered so far. */
1087             goto range_out;
1088         }
1089
1090         /* If we have narrowed down to a single rule already, check whether
1091          * that rule matches.  If it does match, then we're done.  If it does
1092          * not match, then we know that we will never get a match, but we do
1093          * not yet know how many wildcards we need to fold into 'wc' so we
1094          * continue iterating through indices to find that out.  (We won't
1095          * waste time calling minimatch_matches_flow() again because we've set
1096          * 'rule' nonnull.)
1097          *
1098          * This check shows a measurable benefit with non-trivial flow tables.
1099          *
1100          * (Rare) hash collisions may cause us to miss the opportunity for this
1101          * optimization. */
1102         if (!inode->s && !rule) {
1103             ASSIGN_CONTAINER(rule, inode - i, index_nodes);
1104             if (minimatch_matches_flow(&rule->match, flow)) {
1105                 goto out;
1106             }
1107         }
1108     }
1109     ofs.end = FLOW_U32S;
1110     /* Trie check for the final range. */
1111     if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow, wc)) {
1112         goto range_out;
1113     }
1114     if (!rule) {
1115         /* Multiple potential matches exist, look for one. */
1116         hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
1117                                            ofs.end, &basis);
1118         rule = find_match(subtable, flow, hash);
1119     } else {
1120         /* We already narrowed the matching candidates down to just 'rule',
1121          * but it didn't match. */
1122         rule = NULL;
1123     }
1124  out:
1125     /* Must unwildcard all the fields, as they were looked at. */
1126     flow_wildcards_fold_minimask(wc, &subtable->mask);
1127     return rule;
1128
1129  range_out:
1130     /* Must unwildcard the fields looked up so far, if any. */
1131     if (ofs.start) {
1132         flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0, ofs.start);
1133     }
1134     return NULL;
1135 }
1136
1137 static struct cls_rule *
1138 find_equal(struct cls_subtable *subtable, const struct miniflow *flow,
1139            uint32_t hash)
1140 {
1141     struct cls_rule *head;
1142
1143     HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &subtable->rules) {
1144         if (miniflow_equal(&head->match.flow, flow)) {
1145             return head;
1146         }
1147     }
1148     return NULL;
1149 }
1150
1151 static struct cls_rule *
1152 insert_rule(struct classifier *cls, struct cls_subtable *subtable,
1153             struct cls_rule *new)
1154 {
1155     struct cls_rule *head;
1156     struct cls_rule *old = NULL;
1157     int i;
1158     uint32_t basis = 0, hash;
1159     uint8_t prev_be32ofs = 0;
1160
1161     /* Add new node to segment indices. */
1162     for (i = 0; i < subtable->n_indices; i++) {
1163         hash = minimatch_hash_range(&new->match, prev_be32ofs,
1164                                     subtable->index_ofs[i], &basis);
1165         hindex_insert(&subtable->indices[i], &new->index_nodes[i], hash);
1166         prev_be32ofs = subtable->index_ofs[i];
1167     }
1168     hash = minimatch_hash_range(&new->match, prev_be32ofs, FLOW_U32S, &basis);
1169     head = find_equal(subtable, &new->match.flow, hash);
1170     if (!head) {
1171         hmap_insert(&subtable->rules, &new->hmap_node, hash);
1172         list_init(&new->list);
1173         goto out;
1174     } else {
1175         /* Scan the list for the insertion point that will keep the list in
1176          * order of decreasing priority. */
1177         struct cls_rule *rule;
1178
1179         new->hmap_node.hash = hash; /* Otherwise done by hmap_insert. */
1180
1181         FOR_EACH_RULE_IN_LIST (rule, head) {
1182             if (new->priority >= rule->priority) {
1183                 if (rule == head) {
1184                     /* 'new' is the new highest-priority flow in the list. */
1185                     hmap_replace(&subtable->rules,
1186                                  &rule->hmap_node, &new->hmap_node);
1187                 }
1188
1189                 if (new->priority == rule->priority) {
1190                     list_replace(&new->list, &rule->list);
1191                     old = rule;
1192                     goto out;
1193                 } else {
1194                     list_insert(&rule->list, &new->list);
1195                     goto out;
1196                 }
1197             }
1198         }
1199
1200         /* Insert 'new' at the end of the list. */
1201         list_push_back(&head->list, &new->list);
1202     }
1203
1204  out:
1205     if (!old) {
1206         update_subtables_after_insertion(cls, subtable, new->priority);
1207     } else {
1208         /* Remove old node from indices. */
1209         for (i = 0; i < subtable->n_indices; i++) {
1210             hindex_remove(&subtable->indices[i], &old->index_nodes[i]);
1211         }
1212     }
1213     return old;
1214 }
1215
1216 static struct cls_rule *
1217 next_rule_in_list__(struct cls_rule *rule)
1218 {
1219     struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list);
1220     return next;
1221 }
1222
1223 static struct cls_rule *
1224 next_rule_in_list(struct cls_rule *rule)
1225 {
1226     struct cls_rule *next = next_rule_in_list__(rule);
1227     return next->priority < rule->priority ? next : NULL;
1228 }
1229 \f
1230 /* A longest-prefix match tree. */
1231 struct trie_node {
1232     uint32_t prefix;           /* Prefix bits for this node, MSB first. */
1233     uint8_t  nbits;            /* Never zero, except for the root node. */
1234     unsigned int n_rules;      /* Number of rules that have this prefix. */
1235     struct trie_node *edges[2]; /* Both NULL if leaf. */
1236 };
1237
1238 /* Max bits per node.  Must fit in struct trie_node's 'prefix'.
1239  * Also tested with 16, 8, and 5 to stress the implementation. */
1240 #define TRIE_PREFIX_BITS 32
1241
1242 /* Return at least 'plen' bits of the 'prefix', starting at bit offset 'ofs'.
1243  * Prefixes are in the network byte order, and the offset 0 corresponds to
1244  * the most significant bit of the first byte.  The offset can be read as
1245  * "how many bits to skip from the start of the prefix starting at 'pr'". */
1246 static uint32_t
1247 raw_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
1248 {
1249     uint32_t prefix;
1250
1251     pr += ofs / 32; /* Where to start. */
1252     ofs %= 32;      /* How many bits to skip at 'pr'. */
1253
1254     prefix = ntohl(*pr) << ofs; /* Get the first 32 - ofs bits. */
1255     if (plen > 32 - ofs) {      /* Need more than we have already? */
1256         prefix |= ntohl(*++pr) >> (32 - ofs);
1257     }
1258     /* Return with possible unwanted bits at the end. */
1259     return prefix;
1260 }
1261
1262 /* Return min(TRIE_PREFIX_BITS, plen) bits of the 'prefix', starting at bit
1263  * offset 'ofs'.  Prefixes are in the network byte order, and the offset 0
1264  * corresponds to the most significant bit of the first byte.  The offset can
1265  * be read as "how many bits to skip from the start of the prefix starting at
1266  * 'pr'". */
1267 static uint32_t
1268 trie_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
1269 {
1270     if (!plen) {
1271         return 0;
1272     }
1273     if (plen > TRIE_PREFIX_BITS) {
1274         plen = TRIE_PREFIX_BITS; /* Get at most TRIE_PREFIX_BITS. */
1275     }
1276     /* Return with unwanted bits cleared. */
1277     return raw_get_prefix(pr, ofs, plen) & ~0u << (32 - plen);
1278 }
1279
1280 /* Return the number of equal bits in 'nbits' of 'prefix's MSBs and a 'value'
1281  * starting at "MSB 0"-based offset 'ofs'. */
1282 static unsigned int
1283 prefix_equal_bits(uint32_t prefix, unsigned int nbits, const ovs_be32 value[],
1284                   unsigned int ofs)
1285 {
1286     uint64_t diff = prefix ^ raw_get_prefix(value, ofs, nbits);
1287     /* Set the bit after the relevant bits to limit the result. */
1288     return raw_clz64(diff << 32 | UINT64_C(1) << (63 - nbits));
1289 }
1290
1291 /* Return the number of equal bits in 'node' prefix and a 'prefix' of length
1292  * 'plen', starting at "MSB 0"-based offset 'ofs'. */
1293 static unsigned int
1294 trie_prefix_equal_bits(const struct trie_node *node, const ovs_be32 prefix[],
1295                        unsigned int ofs, unsigned int plen)
1296 {
1297     return prefix_equal_bits(node->prefix, MIN(node->nbits, plen - ofs),
1298                              prefix, ofs);
1299 }
1300
1301 /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int.  'ofs' can
1302  * be greater than 31. */
1303 static unsigned int
1304 be_get_bit_at(const ovs_be32 value[], unsigned int ofs)
1305 {
1306     return (((const uint8_t *)value)[ofs / 8] >> (7 - ofs % 8)) & 1u;
1307 }
1308
1309 /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int.  'ofs' must
1310  * be between 0 and 31, inclusive. */
1311 static unsigned int
1312 get_bit_at(const uint32_t prefix, unsigned int ofs)
1313 {
1314     return (prefix >> (31 - ofs)) & 1u;
1315 }
1316
1317 /* Create new branch. */
1318 static struct trie_node *
1319 trie_branch_create(const ovs_be32 *prefix, unsigned int ofs, unsigned int plen,
1320                    unsigned int n_rules)
1321 {
1322     struct trie_node *node = xmalloc(sizeof *node);
1323
1324     node->prefix = trie_get_prefix(prefix, ofs, plen);
1325
1326     if (plen <= TRIE_PREFIX_BITS) {
1327         node->nbits = plen;
1328         node->edges[0] = NULL;
1329         node->edges[1] = NULL;
1330         node->n_rules = n_rules;
1331     } else { /* Need intermediate nodes. */
1332         struct trie_node *subnode = trie_branch_create(prefix,
1333                                                        ofs + TRIE_PREFIX_BITS,
1334                                                        plen - TRIE_PREFIX_BITS,
1335                                                        n_rules);
1336         int bit = get_bit_at(subnode->prefix, 0);
1337         node->nbits = TRIE_PREFIX_BITS;
1338         node->edges[bit] = subnode;
1339         node->edges[!bit] = NULL;
1340         node->n_rules = 0;
1341     }
1342     return node;
1343 }
1344
1345 static void
1346 trie_node_destroy(struct trie_node *node)
1347 {
1348     free(node);
1349 }
1350
1351 static void
1352 trie_destroy(struct trie_node *node)
1353 {
1354     if (node) {
1355         trie_destroy(node->edges[0]);
1356         trie_destroy(node->edges[1]);
1357         free(node);
1358     }
1359 }
1360
1361 static bool
1362 trie_is_leaf(const struct trie_node *trie)
1363 {
1364     return !trie->edges[0] && !trie->edges[1]; /* No children. */
1365 }
1366
1367 static void
1368 mask_set_prefix_bits(struct flow_wildcards *wc, uint8_t be32ofs,
1369                      unsigned int nbits)
1370 {
1371     ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs];
1372     unsigned int i;
1373
1374     for (i = 0; i < nbits / 32; i++) {
1375         mask[i] = OVS_BE32_MAX;
1376     }
1377     if (nbits % 32) {
1378         mask[i] |= htonl(~0u << (32 - nbits % 32));
1379     }
1380 }
1381
1382 static bool
1383 mask_prefix_bits_set(const struct flow_wildcards *wc, uint8_t be32ofs,
1384                      unsigned int nbits)
1385 {
1386     ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs];
1387     unsigned int i;
1388     ovs_be32 zeroes = 0;
1389
1390     for (i = 0; i < nbits / 32; i++) {
1391         zeroes |= ~mask[i];
1392     }
1393     if (nbits % 32) {
1394         zeroes |= ~mask[i] & htonl(~0u << (32 - nbits % 32));
1395     }
1396
1397     return !zeroes; /* All 'nbits' bits set. */
1398 }
1399
1400 static struct trie_node **
1401 trie_next_edge(struct trie_node *node, const ovs_be32 value[],
1402                unsigned int ofs)
1403 {
1404     return node->edges + be_get_bit_at(value, ofs);
1405 }
1406
1407 static const struct trie_node *
1408 trie_next_node(const struct trie_node *node, const ovs_be32 value[],
1409                unsigned int ofs)
1410 {
1411     return node->edges[be_get_bit_at(value, ofs)];
1412 }
1413
1414 /* Return the prefix mask length necessary to find the longest-prefix match for
1415  * the '*value' in the prefix tree 'node'.
1416  * '*checkbits' is set to the number of bits in the prefix mask necessary to
1417  * determine a mismatch, in case there are longer prefixes in the tree below
1418  * the one that matched.
1419  */
1420 static unsigned int
1421 trie_lookup_value(const struct trie_node *node, const ovs_be32 value[],
1422                   unsigned int *checkbits)
1423 {
1424     unsigned int plen = 0, match_len = 0;
1425     const struct trie_node *prev = NULL;
1426
1427     for (; node; prev = node, node = trie_next_node(node, value, plen)) {
1428         unsigned int eqbits;
1429         /* Check if this edge can be followed. */
1430         eqbits = prefix_equal_bits(node->prefix, node->nbits, value, plen);
1431         plen += eqbits;
1432         if (eqbits < node->nbits) { /* Mismatch, nothing more to be found. */
1433             /* Bit at offset 'plen' differed. */
1434             *checkbits = plen + 1; /* Includes the first mismatching bit. */
1435             return match_len;
1436         }
1437         /* Full match, check if rules exist at this prefix length. */
1438         if (node->n_rules > 0) {
1439             match_len = plen;
1440         }
1441     }
1442     /* Dead end, exclude the other branch if it exists. */
1443     *checkbits = !prev || trie_is_leaf(prev) ? plen : plen + 1;
1444     return match_len;
1445 }
1446
1447 static unsigned int
1448 trie_lookup(const struct cls_trie *trie, const struct flow *flow,
1449             unsigned int *checkbits)
1450 {
1451     const struct mf_field *mf = trie->field;
1452
1453     /* Check that current flow matches the prerequisites for the trie
1454      * field.  Some match fields are used for multiple purposes, so we
1455      * must check that the trie is relevant for this flow. */
1456     if (mf_are_prereqs_ok(mf, flow)) {
1457         return trie_lookup_value(trie->root,
1458                                  &((ovs_be32 *)flow)[mf->flow_be32ofs],
1459                                  checkbits);
1460     }
1461     *checkbits = 0; /* Value not used in this case. */
1462     return UINT_MAX;
1463 }
1464
1465 /* Returns the length of a prefix match mask for the field 'mf' in 'minimask'.
1466  * Returns the u32 offset to the miniflow data in '*miniflow_index', if
1467  * 'miniflow_index' is not NULL. */
1468 static unsigned int
1469 minimask_get_prefix_len(const struct minimask *minimask,
1470                         const struct mf_field *mf)
1471 {
1472     unsigned int nbits = 0, mask_tz = 0; /* Non-zero when end of mask seen. */
1473     uint8_t u32_ofs = mf->flow_be32ofs;
1474     uint8_t u32_end = u32_ofs + mf->n_bytes / 4;
1475
1476     for (; u32_ofs < u32_end; ++u32_ofs) {
1477         uint32_t mask;
1478         mask = ntohl((OVS_FORCE ovs_be32)minimask_get(minimask, u32_ofs));
1479
1480         /* Validate mask, count the mask length. */
1481         if (mask_tz) {
1482             if (mask) {
1483                 return 0; /* No bits allowed after mask ended. */
1484             }
1485         } else {
1486             if (~mask & (~mask + 1)) {
1487                 return 0; /* Mask not contiguous. */
1488             }
1489             mask_tz = ctz32(mask);
1490             nbits += 32 - mask_tz;
1491         }
1492     }
1493
1494     return nbits;
1495 }
1496
1497 /*
1498  * This is called only when mask prefix is known to be CIDR and non-zero.
1499  * Relies on the fact that the flow and mask have the same map, and since
1500  * the mask is CIDR, the storage for the flow field exists even if it
1501  * happened to be zeros.
1502  */
1503 static const ovs_be32 *
1504 minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf)
1505 {
1506     return (OVS_FORCE const ovs_be32 *)match->flow.values +
1507         count_1bits(match->flow.map & ((UINT64_C(1) << mf->flow_be32ofs) - 1));
1508 }
1509
1510 /* Insert rule in to the prefix tree.
1511  * 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
1512  * in 'rule'. */
1513 static void
1514 trie_insert(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
1515 {
1516     const ovs_be32 *prefix = minimatch_get_prefix(&rule->match, trie->field);
1517     struct trie_node *node;
1518     struct trie_node **edge;
1519     int ofs = 0;
1520
1521     /* Walk the tree. */
1522     for (edge = &trie->root;
1523          (node = *edge) != NULL;
1524          edge = trie_next_edge(node, prefix, ofs)) {
1525         unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
1526         ofs += eqbits;
1527         if (eqbits < node->nbits) {
1528             /* Mismatch, new node needs to be inserted above. */
1529             int old_branch = get_bit_at(node->prefix, eqbits);
1530
1531             /* New parent node. */
1532             *edge = trie_branch_create(prefix, ofs - eqbits, eqbits,
1533                                        ofs == mlen ? 1 : 0);
1534
1535             /* Adjust old node for its new position in the tree. */
1536             node->prefix <<= eqbits;
1537             node->nbits -= eqbits;
1538             (*edge)->edges[old_branch] = node;
1539
1540             /* Check if need a new branch for the new rule. */
1541             if (ofs < mlen) {
1542                 (*edge)->edges[!old_branch]
1543                     = trie_branch_create(prefix, ofs, mlen - ofs, 1);
1544             }
1545             return;
1546         }
1547         /* Full match so far. */
1548
1549         if (ofs == mlen) {
1550             /* Full match at the current node, rule needs to be added here. */
1551             node->n_rules++;
1552             return;
1553         }
1554     }
1555     /* Must insert a new tree branch for the new rule. */
1556     *edge = trie_branch_create(prefix, ofs, mlen - ofs, 1);
1557 }
1558
1559 /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
1560  * in 'rule'. */
1561 static void
1562 trie_remove(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
1563 {
1564     const ovs_be32 *prefix = minimatch_get_prefix(&rule->match, trie->field);
1565     struct trie_node *node;
1566     struct trie_node **edges[sizeof(union mf_value) * 8];
1567     int depth = 0, ofs = 0;
1568
1569     /* Walk the tree. */
1570     for (edges[depth] = &trie->root;
1571          (node = *edges[depth]) != NULL;
1572          edges[++depth] = trie_next_edge(node, prefix, ofs)) {
1573         unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
1574         if (eqbits < node->nbits) {
1575             /* Mismatch, nothing to be removed.  This should never happen, as
1576              * only rules in the classifier are ever removed. */
1577             break; /* Log a warning. */
1578         }
1579         /* Full match so far. */
1580         ofs += eqbits;
1581
1582         if (ofs == mlen) {
1583             /* Full prefix match at the current node, remove rule here. */
1584             if (!node->n_rules) {
1585                 break; /* Log a warning. */
1586             }
1587             node->n_rules--;
1588
1589             /* Check if can prune the tree. */
1590             while (!node->n_rules && !(node->edges[0] && node->edges[1])) {
1591                 /* No rules and at most one child node, remove this node. */
1592                 struct trie_node *next;
1593                 next = node->edges[0] ? node->edges[0] : node->edges[1];
1594
1595                 if (next) {
1596                     if (node->nbits + next->nbits > TRIE_PREFIX_BITS) {
1597                         break;   /* Cannot combine. */
1598                     }
1599                     /* Combine node with next. */
1600                     next->prefix = node->prefix | next->prefix >> node->nbits;
1601                     next->nbits += node->nbits;
1602                 }
1603                 trie_node_destroy(node);
1604                 /* Update the parent's edge. */
1605                 *edges[depth] = next;
1606                 if (next || !depth) {
1607                     /* Branch not pruned or at root, nothing more to do. */
1608                     break;
1609                 }
1610                 node = *edges[--depth];
1611             }
1612             return;
1613         }
1614     }
1615     /* Cannot go deeper. This should never happen, since only rules
1616      * that actually exist in the classifier are ever removed. */
1617     VLOG_WARN("Trying to remove non-existing rule from a prefix trie.");
1618 }