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_node;
  34 struct trie_ctx;
  35
  36 /* Ports trie depends on both ports sharing the same ovs_be32. */
  37 #define TP_PORTS_OFS32 (offsetof(struct flow, tp_src) / 4)
  38 BUILD_ASSERT_DECL(TP_PORTS_OFS32 == offsetof(struct flow, tp_dst) / 4);
  39
  40 /* Prefix trie for a 'field' */
  41 struct cls_trie {
  42     const struct mf_field *field; /* Trie field, or NULL. */
  43     struct trie_node *root;       /* NULL if none. */
  44 };
  45
  46 struct cls_subtable_entry {
  47     struct cls_subtable *subtable;
  48     tag_type tag;
  49     unsigned int max_priority;
  50 };
  51
  52 struct cls_subtable_cache {
  53     struct cls_subtable_entry *subtables;
  54     size_t alloc_size;     /* Number of allocated elements. */
  55     size_t size;           /* One past last valid array element. */
  56 };
  57
  58 enum {
  59     CLS_MAX_INDICES = 3   /* Maximum number of lookup indices per subtable. */
  60 };
  61
  62 struct cls_classifier {
  63     int n_rules;                /* Total number of rules. */
  64     uint8_t n_flow_segments;
  65     uint8_t flow_segments[CLS_MAX_INDICES]; /* Flow segment boundaries to use
  66                                              * for staged lookup. */
  67     struct hmap subtables;      /* Contains "struct cls_subtable"s.  */
  68     struct cls_subtable_cache subtables_priority;
  69     struct hmap partitions;     /* Contains "struct cls_partition"s. */
  70     struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */
  71     unsigned int n_tries;
  72 };
  73
  74 /* A set of rules that all have the same fields wildcarded. */
  75 struct cls_subtable {
  76     struct hmap_node hmap_node; /* Within struct cls_classifier 'subtables'
  77                                  * hmap. */
  78     struct hmap rules;          /* Contains "struct cls_rule"s. */
  79     int n_rules;                /* Number of rules, including duplicates. */
  80     unsigned int max_priority;  /* Max priority of any rule in the subtable. */
  81     unsigned int max_count;     /* Count of max_priority rules. */
  82     tag_type tag;               /* Tag generated from mask for partitioning. */
  83     uint8_t n_indices;           /* How many indices to use. */
  84     uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 flow segment boundaries. */
  85     struct hindex indices[CLS_MAX_INDICES]; /* Staged lookup indices. */
  86     unsigned int trie_plen[CLS_MAX_TRIES];  /* Trie prefix length in 'mask'. */
  87     int ports_mask_len;
  88     struct trie_node *ports_trie; /* NULL if none. */
  89     struct minimask mask;       /* Wildcards for fields. */
  90     /* 'mask' must be the last field. */
  91 };
  92
  93 /* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata
  94  * field) with tags for the "cls_subtable"s that contain rules that match that
  95  * metadata value.  */
  96 struct cls_partition {
  97     struct hmap_node hmap_node; /* In struct cls_classifier's 'partitions'
  98                                  * hmap. */
  99     ovs_be64 metadata;          /* metadata value for this partition. */
 100     tag_type tags;              /* OR of each flow's cls_subtable tag. */
 101     struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
 102 };
 103
 104 /* Internal representation of a rule in a "struct cls_subtable". */
 105 struct cls_match {
 106     struct cls_rule *cls_rule;
 107     struct hindex_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
 108                                                       * 'indices'. */
 109     struct hmap_node hmap_node; /* Within struct cls_subtable 'rules'. */
 110     unsigned int priority;      /* Larger numbers are higher priorities. */
 111     struct cls_partition *partition;
 112     struct list list;           /* List of identical, lower-priority rules. */
 113     struct miniflow flow;       /* Matching rule. Mask is in the subtable. */
 114     /* 'flow' must be the last field. */
 115 };
 116
 117 static struct cls_match *
 118 cls_match_alloc(struct cls_rule *rule)
 119 {
 120     int count = count_1bits(rule->match.flow.map);
 121
 122     struct cls_match *cls_match
 123         = xmalloc(sizeof *cls_match - sizeof cls_match->flow.inline_values
 124                   + MINIFLOW_VALUES_SIZE(count));
 125
 126     cls_match->cls_rule = rule;
 127     miniflow_clone_inline(&cls_match->flow, &rule->match.flow, count);
 128     cls_match->priority = rule->priority;
 129     rule->cls_match = cls_match;
 130
 131     return cls_match;
 132 }
 133
 134 static struct cls_subtable *find_subtable(const struct cls_classifier *,
 135                                           const struct minimask *);
 136 static struct cls_subtable *insert_subtable(struct cls_classifier *,
 137                                             const struct minimask *);
 138
 139 static void destroy_subtable(struct cls_classifier *, struct cls_subtable *);
 140
 141 static void update_subtables_after_insertion(struct cls_classifier *,
 142                                              struct cls_subtable *,
 143                                              unsigned int new_priority);
 144 static void update_subtables_after_removal(struct cls_classifier *,
 145                                            struct cls_subtable *,
 146                                            unsigned int del_priority);
 147
 148 static struct cls_match *find_match_wc(const struct cls_subtable *,
 149                                        const struct flow *, struct trie_ctx *,
 150                                        unsigned int n_tries,
 151                                        struct flow_wildcards *);
 152 static struct cls_match *find_equal(struct cls_subtable *,
 153                                     const struct miniflow *, uint32_t hash);
 154 static struct cls_match *insert_rule(struct cls_classifier *,
 155                                      struct cls_subtable *, struct cls_rule *);
 156
 157 /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
 158 #define FOR_EACH_RULE_IN_LIST(RULE, HEAD)                               \
 159     for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE))
 160 #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD)                    \
 161     for ((RULE) = (HEAD);                                               \
 162          (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true);    \
 163          (RULE) = (NEXT))
 164
 165 static struct cls_match *next_rule_in_list__(struct cls_match *);
 166 static struct cls_match *next_rule_in_list(struct cls_match *);
 167
 168 static unsigned int minimask_get_prefix_len(const struct minimask *,
 169                                             const struct mf_field *);
 170 static void trie_init(struct cls_classifier *, int trie_idx,
 171                       const struct mf_field *);
 172 static unsigned int trie_lookup(const struct cls_trie *, const struct flow *,
 173                                 unsigned int *checkbits);
 174 static unsigned int trie_lookup_value(const struct trie_node *,
 175                                       const ovs_be32 value[],
 176                                       unsigned int *checkbits);
 177 static void trie_destroy(struct trie_node *);
 178 static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen);
 179 static void trie_insert_prefix(struct trie_node **, const ovs_be32 *prefix,
 180                                int mlen);
 181 static void trie_remove(struct cls_trie *, const struct cls_rule *, int mlen);
 182 static void trie_remove_prefix(struct trie_node **, const ovs_be32 *prefix,
 183                                int mlen);
 184 static void mask_set_prefix_bits(struct flow_wildcards *, uint8_t be32ofs,
 185                                  unsigned int nbits);
 186 static bool mask_prefix_bits_set(const struct flow_wildcards *,
 187                                  uint8_t be32ofs, unsigned int nbits);
 188
 189 static void
 190 cls_subtable_cache_init(struct cls_subtable_cache *array)
 191 {
 192     memset(array, 0, sizeof *array);
 193 }
 194
 195 static void
 196 cls_subtable_cache_destroy(struct cls_subtable_cache *array)
 197 {
 198     free(array->subtables);
 199     memset(array, 0, sizeof *array);
 200 }
 201
 202 /* Array insertion. */
 203 static void
 204 cls_subtable_cache_push_back(struct cls_subtable_cache *array,
 205                              struct cls_subtable_entry a)
 206 {
 207     if (array->size == array->alloc_size) {
 208         array->subtables = x2nrealloc(array->subtables, &array->alloc_size,
 209                                       sizeof a);
 210     }
 211
 212     array->subtables[array->size++] = a;
 213 }
 214
 215 /* Only for rearranging entries in the same cache. */
 216 static inline void
 217 cls_subtable_cache_splice(struct cls_subtable_entry *to,
 218                           struct cls_subtable_entry *start,
 219                           struct cls_subtable_entry *end)
 220 {
 221     if (to > end) {
 222         /* Same as splicing entries to (start) from [end, to). */
 223         struct cls_subtable_entry *temp = to;
 224         to = start; start = end; end = temp;
 225     }
 226     if (to < start) {
 227         while (start != end) {
 228             struct cls_subtable_entry temp = *start;
 229
 230             memmove(to + 1, to, (start - to) * sizeof *to);
 231             *to = temp;
 232             start++;
 233         }
 234     } /* Else nothing to be done. */
 235 }
 236
 237 /* Array removal. */
 238 static inline void
 239 cls_subtable_cache_remove(struct cls_subtable_cache *array,
 240                           struct cls_subtable_entry *elem)
 241 {
 242     ssize_t size = (&array->subtables[array->size]
 243                     - (elem + 1)) * sizeof *elem;
 244     if (size > 0) {
 245         memmove(elem, elem + 1, size);
 246     }
 247     array->size--;
 248 }
 249
 250 #define CLS_SUBTABLE_CACHE_FOR_EACH(SUBTABLE, ITER, ARRAY)      \
 251     for (ITER = (ARRAY)->subtables;                             \
 252          ITER < &(ARRAY)->subtables[(ARRAY)->size]              \
 253              && OVS_LIKELY(SUBTABLE = ITER->subtable);          \
 254          ++ITER)
 255 #define CLS_SUBTABLE_CACHE_FOR_EACH_CONTINUE(SUBTABLE, ITER, ARRAY) \
 256     for (++ITER;                                                    \
 257          ITER < &(ARRAY)->subtables[(ARRAY)->size]                  \
 258              && OVS_LIKELY(SUBTABLE = ITER->subtable);              \
 259          ++ITER)
 260 #define CLS_SUBTABLE_CACHE_FOR_EACH_REVERSE(SUBTABLE, ITER, ARRAY)  \
 261     for (ITER = &(ARRAY)->subtables[(ARRAY)->size];                 \
 262          ITER > (ARRAY)->subtables                                  \
 263              && OVS_LIKELY(SUBTABLE = (--ITER)->subtable);)
 264
 265 static void
 266 cls_subtable_cache_verify(struct cls_subtable_cache *array)
 267 {
 268     struct cls_subtable *table;
 269     struct cls_subtable_entry *iter;
 270     unsigned int priority = 0;
 271
 272     CLS_SUBTABLE_CACHE_FOR_EACH_REVERSE (table, iter, array) {
 273         if (iter->max_priority != table->max_priority) {
 274             VLOG_WARN("Subtable %p has mismatching priority in cache (%u != %u)",
 275                       table, iter->max_priority, table->max_priority);
 276         }
 277         if (iter->max_priority < priority) {
 278             VLOG_WARN("Subtable cache is out of order (%u < %u)",
 279                       iter->max_priority, priority);
 280         }
 281         priority = iter->max_priority;
 282     }
 283 }
 284
 285 static void
 286 cls_subtable_cache_reset(struct cls_classifier *cls)
 287 {
 288     struct cls_subtable_cache old = cls->subtables_priority;
 289     struct cls_subtable *subtable;
 290
 291     VLOG_WARN("Resetting subtable cache.");
 292
 293     cls_subtable_cache_verify(&cls->subtables_priority);
 294
 295     cls_subtable_cache_init(&cls->subtables_priority);
 296
 297     HMAP_FOR_EACH (subtable, hmap_node, &cls->subtables) {
 298         struct cls_match *head;
 299         struct cls_subtable_entry elem;
 300         struct cls_subtable *table;
 301         struct cls_subtable_entry *iter, *subtable_iter = NULL;
 302         unsigned int new_max = 0;
 303         unsigned int max_count = 0;
 304         bool found;
 305
 306         /* Verify max_priority. */
 307         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
 308             if (head->priority > new_max) {
 309                 new_max = head->priority;
 310                 max_count = 1;
 311             } else if (head->priority == new_max) {
 312                 max_count++;
 313             }
 314         }
 315         if (new_max != subtable->max_priority ||
 316             max_count != subtable->max_count) {
 317             VLOG_WARN("subtable %p (%u rules) has mismatching max_priority "
 318                       "(%u) or max_count (%u). Highest priority found was %u, "
 319                       "count: %u",
 320                       subtable, subtable->n_rules, subtable->max_priority,
 321                       subtable->max_count, new_max, max_count);
 322             subtable->max_priority = new_max;
 323             subtable->max_count = max_count;
 324         }
 325
 326         /* Locate the subtable from the old cache. */
 327         found = false;
 328         CLS_SUBTABLE_CACHE_FOR_EACH (table, iter, &old) {
 329             if (table == subtable) {
 330                 if (iter->max_priority != new_max) {
 331                     VLOG_WARN("Subtable %p has wrong max priority (%u != %u) "
 332                               "in the old cache.",
 333                               subtable, iter->max_priority, new_max);
 334                 }
 335                 if (found) {
 336                     VLOG_WARN("Subtable %p duplicated in the old cache.",
 337                               subtable);
 338                 }
 339                 found = true;
 340             }
 341         }
 342         if (!found) {
 343             VLOG_WARN("Subtable %p not found from the old cache.", subtable);
 344         }
 345
 346         elem.subtable = subtable;
 347         elem.tag = subtable->tag;
 348         elem.max_priority = subtable->max_priority;
 349         cls_subtable_cache_push_back(&cls->subtables_priority, elem);
 350
 351         /* Possibly move 'subtable' earlier in the priority list.  If we break
 352          * out of the loop, then 'subtable_iter' should be moved just before
 353          * 'iter'.  If the loop terminates normally, then 'iter' will be the
 354          * first list element and we'll move subtable just before that
 355          * (e.g. to the front of the list). */
 356         CLS_SUBTABLE_CACHE_FOR_EACH_REVERSE (table, iter,
 357                                              &cls->subtables_priority) {
 358             if (table == subtable) {
 359                 subtable_iter = iter; /* Locate the subtable as we go. */
 360             } else if (table->max_priority >= new_max) {
 361                 ovs_assert(subtable_iter != NULL);
 362                 iter++;
 363                 break;
 364             }
 365         }
 366
 367         /* Move 'subtable' just before 'iter' (unless it's already there). */
 368         if (iter != subtable_iter) {
 369             cls_subtable_cache_splice(iter, subtable_iter, subtable_iter + 1);
 370         }
 371     }
 372
 373     /* Verify that the old and the new have the same size. */
 374     if (old.size != cls->subtables_priority.size) {
 375         VLOG_WARN("subtables cache sizes differ: old (%"PRIuSIZE
 376                   ") != new (%"PRIuSIZE").",
 377                   old.size, cls->subtables_priority.size);
 378     }
 379
 380     cls_subtable_cache_destroy(&old);
 381
 382     cls_subtable_cache_verify(&cls->subtables_priority);
 383 }
 384
 385 \f
 386 /* flow/miniflow/minimask/minimatch utilities.
 387  * These are only used by the classifier, so place them here to allow
 388  * for better optimization. */
 389
 390 static inline uint64_t
 391 miniflow_get_map_in_range(const struct miniflow *miniflow,
 392                           uint8_t start, uint8_t end, unsigned int *offset)
 393 {
 394     uint64_t map = miniflow->map;
 395     *offset = 0;
 396
 397     if (start > 0) {
 398         uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */
 399         *offset = count_1bits(map & msk);
 400         map &= ~msk;
 401     }
 402     if (end < FLOW_U32S) {
 403         uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */
 404         map &= msk;
 405     }
 406     return map;
 407 }
 408
 409 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 410  * 'mask', given 'basis'.
 411  *
 412  * The hash values returned by this function are the same as those returned by
 413  * miniflow_hash_in_minimask(), only the form of the arguments differ. */
 414 static inline uint32_t
 415 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
 416                       uint32_t basis)
 417 {
 418     const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks);
 419     const uint32_t *flow_u32 = (const uint32_t *)flow;
 420     const uint32_t *p = mask_values;
 421     uint32_t hash;
 422     uint64_t map;
 423
 424     hash = basis;
 425     for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) {
 426         hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
 427     }
 428
 429     return mhash_finish(hash, (p - mask_values) * 4);
 430 }
 431
 432 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
 433  * 'mask', given 'basis'.
 434  *
 435  * The hash values returned by this function are the same as those returned by
 436  * flow_hash_in_minimask(), only the form of the arguments differ. */
 437 static inline uint32_t
 438 miniflow_hash_in_minimask(const struct miniflow *flow,
 439                           const struct minimask *mask, uint32_t basis)
 440 {
 441     const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks);
 442     const uint32_t *p = mask_values;
 443     uint32_t hash = basis;
 444     uint32_t flow_u32;
 445
 446     MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) {
 447         hash = mhash_add(hash, flow_u32 & *p++);
 448     }
 449
 450     return mhash_finish(hash, (p - mask_values) * 4);
 451 }
 452
 453 /* Returns a hash value for the bits of range [start, end) in 'flow',
 454  * where there are 1-bits in 'mask', given 'hash'.
 455  *
 456  * The hash values returned by this function are the same as those returned by
 457  * minimatch_hash_range(), only the form of the arguments differ. */
 458 static inline uint32_t
 459 flow_hash_in_minimask_range(const struct flow *flow,
 460                             const struct minimask *mask,
 461                             uint8_t start, uint8_t end, uint32_t *basis)
 462 {
 463     const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks);
 464     const uint32_t *flow_u32 = (const uint32_t *)flow;
 465     unsigned int offset;
 466     uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
 467                                              &offset);
 468     const uint32_t *p = mask_values + offset;
 469     uint32_t hash = *basis;
 470
 471     for (; map; map = zero_rightmost_1bit(map)) {
 472         hash = mhash_add(hash, flow_u32[raw_ctz(map)] & *p++);
 473     }
 474
 475     *basis = hash; /* Allow continuation from the unfinished value. */
 476     return mhash_finish(hash, (p - mask_values) * 4);
 477 }
 478
 479 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
 480 static inline void
 481 flow_wildcards_fold_minimask(struct flow_wildcards *wc,
 482                              const struct minimask *mask)
 483 {
 484     flow_union_with_miniflow(&wc->masks, &mask->masks);
 485 }
 486
 487 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
 488  * in range [start, end). */
 489 static inline void
 490 flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
 491                                    const struct minimask *mask,
 492                                    uint8_t start, uint8_t end)
 493 {
 494     uint32_t *dst_u32 = (uint32_t *)&wc->masks;
 495     unsigned int offset;
 496     uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end,
 497                                              &offset);
 498     const uint32_t *p = miniflow_get_u32_values(&mask->masks) + offset;
 499
 500     for (; map; map = zero_rightmost_1bit(map)) {
 501         dst_u32[raw_ctz(map)] |= *p++;
 502     }
 503 }
 504
 505 /* Returns a hash value for 'flow', given 'basis'. */
 506 static inline uint32_t
 507 miniflow_hash(const struct miniflow *flow, uint32_t basis)
 508 {
 509     const uint32_t *values = miniflow_get_u32_values(flow);
 510     const uint32_t *p = values;
 511     uint32_t hash = basis;
 512     uint64_t hash_map = 0;
 513     uint64_t map;
 514
 515     for (map = flow->map; map; map = zero_rightmost_1bit(map)) {
 516         if (*p) {
 517             hash = mhash_add(hash, *p);
 518             hash_map |= rightmost_1bit(map);
 519         }
 520         p++;
 521     }
 522     hash = mhash_add(hash, hash_map);
 523     hash = mhash_add(hash, hash_map >> 32);
 524
 525     return mhash_finish(hash, p - values);
 526 }
 527
 528 /* Returns a hash value for 'mask', given 'basis'. */
 529 static inline uint32_t
 530 minimask_hash(const struct minimask *mask, uint32_t basis)
 531 {
 532     return miniflow_hash(&mask->masks, basis);
 533 }
 534
 535 /* Returns a hash value for 'match', given 'basis'. */
 536 static inline uint32_t
 537 minimatch_hash(const struct minimatch *match, uint32_t basis)
 538 {
 539     return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis));
 540 }
 541
 542 /* Returns a hash value for the bits of range [start, end) in 'minimatch',
 543  * given 'basis'.
 544  *
 545  * The hash values returned by this function are the same as those returned by
 546  * flow_hash_in_minimask_range(), only the form of the arguments differ. */
 547 static inline uint32_t
 548 minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
 549                      uint32_t *basis)
 550 {
 551     unsigned int offset;
 552     const uint32_t *p, *q;
 553     uint32_t hash = *basis;
 554     int n, i;
 555
 556     n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end,
 557                                               &offset));
 558     q = miniflow_get_u32_values(&match->mask.masks) + offset;
 559     p = miniflow_get_u32_values(&match->flow) + offset;
 560
 561     for (i = 0; i < n; i++) {
 562         hash = mhash_add(hash, p[i] & q[i]);
 563     }
 564     *basis = hash; /* Allow continuation from the unfinished value. */
 565     return mhash_finish(hash, (offset + n) * 4);
 566 }
 567
 568 \f
 569 /* cls_rule. */
 570
 571 /* Initializes 'rule' to match packets specified by 'match' at the given
 572  * 'priority'.  'match' must satisfy the invariant described in the comment at
 573  * the definition of struct match.
 574  *
 575  * The caller must eventually destroy 'rule' with cls_rule_destroy().
 576  *
 577  * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but
 578  * internally Open vSwitch supports a wider range.) */
 579 void
 580 cls_rule_init(struct cls_rule *rule,
 581               const struct match *match, unsigned int priority)
 582 {
 583     minimatch_init(&rule->match, match);
 584     rule->priority = priority;
 585     rule->cls_match = NULL;
 586 }
 587
 588 /* Same as cls_rule_init() for initialization from a "struct minimatch". */
 589 void
 590 cls_rule_init_from_minimatch(struct cls_rule *rule,
 591                              const struct minimatch *match,
 592                              unsigned int priority)
 593 {
 594     minimatch_clone(&rule->match, match);
 595     rule->priority = priority;
 596     rule->cls_match = NULL;
 597 }
 598
 599 /* Initializes 'dst' as a copy of 'src'.
 600  *
 601  * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
 602 void
 603 cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
 604 {
 605     minimatch_clone(&dst->match, &src->match);
 606     dst->priority = src->priority;
 607     dst->cls_match = NULL;
 608 }
 609
 610 /* Initializes 'dst' with the data in 'src', destroying 'src'.
 611  *
 612  * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
 613 void
 614 cls_rule_move(struct cls_rule *dst, struct cls_rule *src)
 615 {
 616     minimatch_move(&dst->match, &src->match);
 617     dst->priority = src->priority;
 618     dst->cls_match = NULL;
 619 }
 620
 621 /* Frees memory referenced by 'rule'.  Doesn't free 'rule' itself (it's
 622  * normally embedded into a larger structure).
 623  *
 624  * ('rule' must not currently be in a classifier.) */
 625 void
 626 cls_rule_destroy(struct cls_rule *rule)
 627 {
 628     ovs_assert(!rule->cls_match);
 629     minimatch_destroy(&rule->match);
 630 }
 631
 632 /* Returns true if 'a' and 'b' match the same packets at the same priority,
 633  * false if they differ in some way. */
 634 bool
 635 cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
 636 {
 637     return a->priority == b->priority && minimatch_equal(&a->match, &b->match);
 638 }
 639
 640 /* Returns a hash value for 'rule', folding in 'basis'. */
 641 uint32_t
 642 cls_rule_hash(const struct cls_rule *rule, uint32_t basis)
 643 {
 644     return minimatch_hash(&rule->match, hash_int(rule->priority, basis));
 645 }
 646
 647 /* Appends a string describing 'rule' to 's'. */
 648 void
 649 cls_rule_format(const struct cls_rule *rule, struct ds *s)
 650 {
 651     minimatch_format(&rule->match, s, rule->priority);
 652 }
 653
 654 /* Returns true if 'rule' matches every packet, false otherwise. */
 655 bool
 656 cls_rule_is_catchall(const struct cls_rule *rule)
 657 {
 658     return minimask_is_catchall(&rule->match.mask);
 659 }
 660 \f
 661 /* Initializes 'cls' as a classifier that initially contains no classification
 662  * rules. */
 663 void
 664 classifier_init(struct classifier *cls_, const uint8_t *flow_segments)
 665 {
 666     struct cls_classifier *cls = xmalloc(sizeof *cls);
 667
 668     fat_rwlock_init(&cls_->rwlock);
 669
 670     cls_->cls = cls;
 671
 672     cls->n_rules = 0;
 673     hmap_init(&cls->subtables);
 674     cls_subtable_cache_init(&cls->subtables_priority);
 675     hmap_init(&cls->partitions);
 676     cls->n_flow_segments = 0;
 677     if (flow_segments) {
 678         while (cls->n_flow_segments < CLS_MAX_INDICES
 679                && *flow_segments < FLOW_U32S) {
 680             cls->flow_segments[cls->n_flow_segments++] = *flow_segments++;
 681         }
 682     }
 683     cls->n_tries = 0;
 684 }
 685
 686 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
 687  * caller's responsibility. */
 688 void
 689 classifier_destroy(struct classifier *cls_)
 690 {
 691     if (cls_) {
 692         struct cls_classifier *cls = cls_->cls;
 693         struct cls_subtable *partition, *next_partition;
 694         struct cls_subtable *subtable, *next_subtable;
 695         int i;
 696
 697         fat_rwlock_destroy(&cls_->rwlock);
 698         if (!cls) {
 699             return;
 700         }
 701
 702         for (i = 0; i < cls->n_tries; i++) {
 703             trie_destroy(cls->tries[i].root);
 704         }
 705
 706         HMAP_FOR_EACH_SAFE (subtable, next_subtable, hmap_node,
 707                             &cls->subtables) {
 708             destroy_subtable(cls, subtable);
 709         }
 710         hmap_destroy(&cls->subtables);
 711
 712         HMAP_FOR_EACH_SAFE (partition, next_partition, hmap_node,
 713                             &cls->partitions) {
 714             hmap_remove(&cls->partitions, &partition->hmap_node);
 715             free(partition);
 716         }
 717         hmap_destroy(&cls->partitions);
 718
 719         cls_subtable_cache_destroy(&cls->subtables_priority);
 720         free(cls);
 721     }
 722 }
 723
 724 /* We use uint64_t as a set for the fields below. */
 725 BUILD_ASSERT_DECL(MFF_N_IDS <= 64);
 726
 727 /* Set the fields for which prefix lookup should be performed. */
 728 void
 729 classifier_set_prefix_fields(struct classifier *cls_,
 730                              const enum mf_field_id *trie_fields,
 731                              unsigned int n_fields)
 732 {
 733     struct cls_classifier *cls = cls_->cls;
 734     uint64_t fields = 0;
 735     int i, trie;
 736
 737     for (i = 0, trie = 0; i < n_fields && trie < CLS_MAX_TRIES; i++) {
 738         const struct mf_field *field = mf_from_id(trie_fields[i]);
 739         if (field->flow_be32ofs < 0 || field->n_bits % 32) {
 740             /* Incompatible field.  This is the only place where we
 741              * enforce these requirements, but the rest of the trie code
 742              * depends on the flow_be32ofs to be non-negative and the
 743              * field length to be a multiple of 32 bits. */
 744             continue;
 745         }
 746
 747         if (fields & (UINT64_C(1) << trie_fields[i])) {
 748             /* Duplicate field, there is no need to build more than
 749              * one index for any one field. */
 750             continue;
 751         }
 752         fields |= UINT64_C(1) << trie_fields[i];
 753
 754         if (trie >= cls->n_tries || field != cls->tries[trie].field) {
 755             trie_init(cls, trie, field);
 756         }
 757         trie++;
 758     }
 759
 760     /* Destroy the rest. */
 761     for (i = trie; i < cls->n_tries; i++) {
 762         trie_init(cls, i, NULL);
 763     }
 764     cls->n_tries = trie;
 765 }
 766
 767 static void
 768 trie_init(struct cls_classifier *cls, int trie_idx,
 769           const struct mf_field *field)
 770 {
 771     struct cls_trie *trie = &cls->tries[trie_idx];
 772     struct cls_subtable *subtable;
 773     struct cls_subtable_entry *iter;
 774
 775     if (trie_idx < cls->n_tries) {
 776         trie_destroy(trie->root);
 777     }
 778     trie->root = NULL;
 779     trie->field = field;
 780
 781     /* Add existing rules to the trie. */
 782     CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) {
 783         unsigned int plen;
 784
 785         plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0;
 786         /* Initialize subtable's prefix length on this field. */
 787         subtable->trie_plen[trie_idx] = plen;
 788
 789         if (plen) {
 790             struct cls_match *head;
 791
 792             HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
 793                 struct cls_match *match;
 794
 795                 FOR_EACH_RULE_IN_LIST (match, head) {
 796                     trie_insert(trie, match->cls_rule, plen);
 797                 }
 798             }
 799         }
 800     }
 801 }
 802
 803 /* Returns true if 'cls' contains no classification rules, false otherwise. */
 804 bool
 805 classifier_is_empty(const struct classifier *cls)
 806 {
 807     return cls->cls->n_rules == 0;
 808 }
 809
 810 /* Returns the number of rules in 'cls'. */
 811 int
 812 classifier_count(const struct classifier *cls)
 813 {
 814     return cls->cls->n_rules;
 815 }
 816
 817 static uint32_t
 818 hash_metadata(ovs_be64 metadata_)
 819 {
 820     uint64_t metadata = (OVS_FORCE uint64_t) metadata_;
 821     return hash_uint64(metadata);
 822 }
 823
 824 static struct cls_partition *
 825 find_partition(const struct cls_classifier *cls, ovs_be64 metadata,
 826                uint32_t hash)
 827 {
 828     struct cls_partition *partition;
 829
 830     HMAP_FOR_EACH_IN_BUCKET (partition, hmap_node, hash, &cls->partitions) {
 831         if (partition->metadata == metadata) {
 832             return partition;
 833         }
 834     }
 835
 836     return NULL;
 837 }
 838
 839 static struct cls_partition *
 840 create_partition(struct cls_classifier *cls, struct cls_subtable *subtable,
 841                  ovs_be64 metadata)
 842 {
 843     uint32_t hash = hash_metadata(metadata);
 844     struct cls_partition *partition = find_partition(cls, metadata, hash);
 845     if (!partition) {
 846         partition = xmalloc(sizeof *partition);
 847         partition->metadata = metadata;
 848         partition->tags = 0;
 849         tag_tracker_init(&partition->tracker);
 850         hmap_insert(&cls->partitions, &partition->hmap_node, hash);
 851     }
 852     tag_tracker_add(&partition->tracker, &partition->tags, subtable->tag);
 853     return partition;
 854 }
 855
 856 static inline ovs_be32 minimatch_get_ports(const struct minimatch *match)
 857 {
 858     /* Could optimize to use the same map if needed for fast path. */
 859     return MINIFLOW_GET_BE32(&match->flow, tp_src)
 860         & MINIFLOW_GET_BE32(&match->mask.masks, tp_src);
 861 }
 862
 863 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 864  * must not modify or free it.
 865  *
 866  * If 'cls' already contains an identical rule (including wildcards, values of
 867  * fixed fields, and priority), replaces the old rule by 'rule' and returns the
 868  * rule that was replaced.  The caller takes ownership of the returned rule and
 869  * is thus responsible for destroying it with cls_rule_destroy(), freeing the
 870  * memory block in which it resides, etc., as necessary.
 871  *
 872  * Returns NULL if 'cls' does not contain a rule with an identical key, after
 873  * inserting the new rule.  In this case, no rules are displaced by the new
 874  * rule, even rules that cannot have any effect because the new rule matches a
 875  * superset of their flows and has higher priority. */
 876 struct cls_rule *
 877 classifier_replace(struct classifier *cls_, struct cls_rule *rule)
 878 {
 879     struct cls_classifier *cls = cls_->cls;
 880     struct cls_match *old_rule;
 881     struct cls_subtable *subtable;
 882
 883     subtable = find_subtable(cls, &rule->match.mask);
 884     if (!subtable) {
 885         subtable = insert_subtable(cls, &rule->match.mask);
 886     }
 887
 888     old_rule = insert_rule(cls, subtable, rule);
 889     if (!old_rule) {
 890         int i;
 891
 892         rule->cls_match->partition = NULL;
 893         if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
 894             ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
 895             rule->cls_match->partition = create_partition(cls, subtable,
 896                                                           metadata);
 897         }
 898
 899         subtable->n_rules++;
 900         cls->n_rules++;
 901
 902         for (i = 0; i < cls->n_tries; i++) {
 903             if (subtable->trie_plen[i]) {
 904                 trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
 905             }
 906         }
 907
 908         /* Ports trie. */
 909         if (subtable->ports_mask_len) {
 910             /* We mask the value to be inserted to always have the wildcarded
 911              * bits in known (zero) state, so we can include them in comparison
 912              * and they will always match (== their original value does not
 913              * matter). */
 914             ovs_be32 masked_ports = minimatch_get_ports(&rule->match);
 915
 916             trie_insert_prefix(&subtable->ports_trie, &masked_ports,
 917                                subtable->ports_mask_len);
 918         }
 919
 920         return NULL;
 921     } else {
 922         struct cls_rule *old_cls_rule = old_rule->cls_rule;
 923
 924         rule->cls_match->partition = old_rule->partition;
 925         old_cls_rule->cls_match = NULL;
 926         free(old_rule);
 927         return old_cls_rule;
 928     }
 929 }
 930
 931 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 932  * must not modify or free it.
 933  *
 934  * 'cls' must not contain an identical rule (including wildcards, values of
 935  * fixed fields, and priority).  Use classifier_find_rule_exactly() to find
 936  * such a rule. */
 937 void
 938 classifier_insert(struct classifier *cls, struct cls_rule *rule)
 939 {
 940     struct cls_rule *displaced_rule = classifier_replace(cls, rule);
 941     ovs_assert(!displaced_rule);
 942 }
 943
 944 /* Removes 'rule' from 'cls'.  It is the caller's responsibility to destroy
 945  * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule'
 946  * resides, etc., as necessary. */
 947 void
 948 classifier_remove(struct classifier *cls_, struct cls_rule *rule)
 949 {
 950     struct cls_classifier *cls = cls_->cls;
 951     struct cls_partition *partition;
 952     struct cls_match *cls_match = rule->cls_match;
 953     struct cls_match *head;
 954     struct cls_subtable *subtable;
 955     int i;
 956
 957     ovs_assert(cls_match);
 958
 959     subtable = find_subtable(cls, &rule->match.mask);
 960     ovs_assert(subtable);
 961
 962     if (subtable->ports_mask_len) {
 963         ovs_be32 masked_ports = minimatch_get_ports(&rule->match);
 964
 965         trie_remove_prefix(&subtable->ports_trie,
 966                            &masked_ports, subtable->ports_mask_len);
 967     }
 968     for (i = 0; i < cls->n_tries; i++) {
 969         if (subtable->trie_plen[i]) {
 970             trie_remove(&cls->tries[i], rule, subtable->trie_plen[i]);
 971         }
 972     }
 973
 974     /* Remove rule node from indices. */
 975     for (i = 0; i < subtable->n_indices; i++) {
 976         hindex_remove(&subtable->indices[i], &cls_match->index_nodes[i]);
 977     }
 978
 979     head = find_equal(subtable, &rule->match.flow, cls_match->hmap_node.hash);
 980     if (head != cls_match) {
 981         list_remove(&cls_match->list);
 982     } else if (list_is_empty(&cls_match->list)) {
 983         hmap_remove(&subtable->rules, &cls_match->hmap_node);
 984     } else {
 985         struct cls_match *next = CONTAINER_OF(cls_match->list.next,
 986                                               struct cls_match, list);
 987
 988         list_remove(&cls_match->list);
 989         hmap_replace(&subtable->rules, &cls_match->hmap_node,
 990                      &next->hmap_node);
 991     }
 992
 993     partition = cls_match->partition;
 994     if (partition) {
 995         tag_tracker_subtract(&partition->tracker, &partition->tags,
 996                              subtable->tag);
 997         if (!partition->tags) {
 998             hmap_remove(&cls->partitions, &partition->hmap_node);
 999             free(partition);
1000         }
1001     }
1002
1003     if (--subtable->n_rules == 0) {
1004         destroy_subtable(cls, subtable);
1005     } else {
1006         update_subtables_after_removal(cls, subtable, cls_match->priority);
1007     }
1008
1009     cls->n_rules--;
1010
1011     rule->cls_match = NULL;
1012     free(cls_match);
1013 }
1014
1015 /* Prefix tree context.  Valid when 'lookup_done' is true.  Can skip all
1016  * subtables which have more than 'match_plen' bits in their corresponding
1017  * field at offset 'be32ofs'.  If skipped, 'maskbits' prefix bits should be
1018  * unwildcarded to quarantee datapath flow matches only packets it should. */
1019 struct trie_ctx {
1020     const struct cls_trie *trie;
1021     bool lookup_done;        /* Status of the lookup. */
1022     uint8_t be32ofs;         /* U32 offset of the field in question. */
1023     unsigned int match_plen; /* Longest prefix than could possibly match. */
1024     unsigned int maskbits;   /* Prefix length needed to avoid false matches. */
1025 };
1026
1027 static void
1028 trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
1029 {
1030     ctx->trie = trie;
1031     ctx->be32ofs = trie->field->flow_be32ofs;
1032     ctx->lookup_done = false;
1033 }
1034
1035 static inline void
1036 lookahead_subtable(const struct cls_subtable_entry *subtables)
1037 {
1038     ovs_prefetch_range(subtables->subtable, sizeof *subtables->subtable);
1039 }
1040
1041 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
1042  * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
1043  * of equal priority match 'flow', returns one arbitrarily.
1044  *
1045  * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
1046  * set of bits that were significant in the lookup.  At some point
1047  * earlier, 'wc' should have been initialized (e.g., by
1048  * flow_wildcards_init_catchall()). */
1049 struct cls_rule *
1050 classifier_lookup(const struct classifier *cls_, const struct flow *flow,
1051                   struct flow_wildcards *wc)
1052 {
1053     struct cls_classifier *cls = cls_->cls;
1054     const struct cls_partition *partition;
1055     tag_type tags;
1056     struct cls_match *best;
1057     struct trie_ctx trie_ctx[CLS_MAX_TRIES];
1058     int i;
1059     struct cls_subtable_entry *subtables = cls->subtables_priority.subtables;
1060     int n_subtables = cls->subtables_priority.size;
1061     int64_t best_priority = -1;
1062
1063     /* Prefetch the subtables array. */
1064     ovs_prefetch_range(subtables, n_subtables * sizeof *subtables);
1065
1066     /* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them,
1067      * then 'flow' cannot possibly match in 'subtable':
1068      *
1069      *     - If flow->metadata maps to a given 'partition', then we can use
1070      *       'tags' for 'partition->tags'.
1071      *
1072      *     - If flow->metadata has no partition, then no rule in 'cls' has an
1073      *       exact-match for flow->metadata.  That means that we don't need to
1074      *       search any subtable that includes flow->metadata in its mask.
1075      *
1076      * In either case, we always need to search any cls_subtables that do not
1077      * include flow->metadata in its mask.  One way to do that would be to
1078      * check the "cls_subtable"s explicitly for that, but that would require an
1079      * extra branch per subtable.  Instead, we mark such a cls_subtable's
1080      * 'tags' as TAG_ALL and make sure that 'tags' is never empty.  This means
1081      * that 'tags' always intersects such a cls_subtable's 'tags', so we don't
1082      * need a special case.
1083      */
1084     partition = (hmap_is_empty(&cls->partitions)
1085                  ? NULL
1086                  : find_partition(cls, flow->metadata,
1087                                   hash_metadata(flow->metadata)));
1088     tags = partition ? partition->tags : TAG_ARBITRARY;
1089
1090     /* Initialize trie contexts for match_find_wc(). */
1091     for (i = 0; i < cls->n_tries; i++) {
1092         trie_ctx_init(&trie_ctx[i], &cls->tries[i]);
1093     }
1094
1095     /* Prefetch the first subtables. */
1096     if (n_subtables > 1) {
1097       lookahead_subtable(subtables);
1098       lookahead_subtable(subtables + 1);
1099     }
1100
1101     best = NULL;
1102     for (i = 0; OVS_LIKELY(i < n_subtables); i++) {
1103         struct cls_match *rule;
1104
1105         if ((int64_t)subtables[i].max_priority <= best_priority) {
1106             /* Subtables are in descending priority order,
1107              * can not find anything better. */
1108             break;
1109         }
1110
1111         /* Prefetch a forthcoming subtable. */
1112         if (i + 2 < n_subtables) {
1113             lookahead_subtable(&subtables[i + 2]);
1114         }
1115
1116         if (!tag_intersects(tags, subtables[i].tag)) {
1117             continue;
1118         }
1119
1120         rule = find_match_wc(subtables[i].subtable, flow, trie_ctx,
1121                              cls->n_tries, wc);
1122         if (rule && (int64_t)rule->priority > best_priority) {
1123             best_priority = (int64_t)rule->priority;
1124             best = rule;
1125         }
1126     }
1127
1128     return best ? best->cls_rule : NULL;
1129 }
1130
1131 /* Returns true if 'target' satisifies 'match', that is, if each bit for which
1132  * 'match' specifies a particular value has the correct value in 'target'.
1133  *
1134  * 'flow' and 'mask' have the same mask! */
1135 static bool
1136 miniflow_and_mask_matches_miniflow(const struct miniflow *flow,
1137                                    const struct minimask *mask,
1138                                    const struct miniflow *target)
1139 {
1140     const uint32_t *flowp = miniflow_get_u32_values(flow);
1141     const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
1142     uint32_t target_u32;
1143
1144     MINIFLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) {
1145         if ((*flowp++ ^ target_u32) & *maskp++) {
1146             return false;
1147         }
1148     }
1149
1150     return true;
1151 }
1152
1153 static inline struct cls_match *
1154 find_match_miniflow(const struct cls_subtable *subtable,
1155                     const struct miniflow *flow,
1156                     uint32_t hash)
1157 {
1158     struct cls_match *rule;
1159
1160     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
1161         if (miniflow_and_mask_matches_miniflow(&rule->flow, &subtable->mask,
1162                                                flow)) {
1163             return rule;
1164         }
1165     }
1166
1167     return NULL;
1168 }
1169
1170 /* Finds and returns the highest-priority rule in 'cls' that matches
1171  * 'miniflow'.  Returns a null pointer if no rules in 'cls' match 'flow'.
1172  * If multiple rules of equal priority match 'flow', returns one arbitrarily.
1173  *
1174  * This function is optimized for the userspace datapath, which only ever has
1175  * one priority value for it's flows!
1176  */
1177 struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls_,
1178                                                   const struct miniflow *flow)
1179 {
1180     struct cls_classifier *cls = cls_->cls;
1181     struct cls_subtable *subtable;
1182     struct cls_subtable_entry *iter;
1183
1184     CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) {
1185         struct cls_match *rule;
1186
1187         rule = find_match_miniflow(subtable, flow,
1188                                    miniflow_hash_in_minimask(flow,
1189                                                              &subtable->mask,
1190                                                              0));
1191         if (rule) {
1192             return rule->cls_rule;
1193         }
1194     }
1195
1196     return NULL;
1197 }
1198
1199 /* Finds and returns a rule in 'cls' with exactly the same priority and
1200  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
1201  * contain an exact match. */
1202 struct cls_rule *
1203 classifier_find_rule_exactly(const struct classifier *cls_,
1204                              const struct cls_rule *target)
1205 {
1206     struct cls_classifier *cls = cls_->cls;
1207     struct cls_match *head, *rule;
1208     struct cls_subtable *subtable;
1209
1210     subtable = find_subtable(cls, &target->match.mask);
1211     if (!subtable) {
1212         return NULL;
1213     }
1214
1215     /* Skip if there is no hope. */
1216     if (target->priority > subtable->max_priority) {
1217         return NULL;
1218     }
1219
1220     head = find_equal(subtable, &target->match.flow,
1221                       miniflow_hash_in_minimask(&target->match.flow,
1222                                                 &target->match.mask, 0));
1223     FOR_EACH_RULE_IN_LIST (rule, head) {
1224         if (target->priority >= rule->priority) {
1225             return target->priority == rule->priority ? rule->cls_rule : NULL;
1226         }
1227     }
1228     return NULL;
1229 }
1230
1231 /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
1232  * same matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
1233  * contain an exact match. */
1234 struct cls_rule *
1235 classifier_find_match_exactly(const struct classifier *cls,
1236                               const struct match *target,
1237                               unsigned int priority)
1238 {
1239     struct cls_rule *retval;
1240     struct cls_rule cr;
1241
1242     cls_rule_init(&cr, target, priority);
1243     retval = classifier_find_rule_exactly(cls, &cr);
1244     cls_rule_destroy(&cr);
1245
1246     return retval;
1247 }
1248
1249 /* Checks if 'target' would overlap any other rule in 'cls'.  Two rules are
1250  * considered to overlap if both rules have the same priority and a packet
1251  * could match both. */
1252 bool
1253 classifier_rule_overlaps(const struct classifier *cls_,
1254                          const struct cls_rule *target)
1255 {
1256     struct cls_classifier *cls = cls_->cls;
1257     struct cls_subtable *subtable;
1258     struct cls_subtable_entry *iter;
1259
1260     /* Iterate subtables in the descending max priority order. */
1261     CLS_SUBTABLE_CACHE_FOR_EACH (subtable, iter, &cls->subtables_priority) {
1262         uint32_t storage[FLOW_U32S];
1263         struct minimask mask;
1264         struct cls_match *head;
1265
1266         if (target->priority > iter->max_priority) {
1267             break; /* Can skip this and the rest of the subtables. */
1268         }
1269
1270         minimask_combine(&mask, &target->match.mask, &subtable->mask, storage);
1271         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
1272             struct cls_match *rule;
1273
1274             FOR_EACH_RULE_IN_LIST (rule, head) {
1275                 if (rule->priority < target->priority) {
1276                     break; /* Rules in descending priority order. */
1277                 }
1278                 if (rule->priority == target->priority
1279                     && miniflow_equal_in_minimask(&target->match.flow,
1280                                                   &rule->flow, &mask)) {
1281                     return true;
1282                 }
1283             }
1284         }
1285     }
1286
1287     return false;
1288 }
1289
1290 /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
1291  * specific than 'criteria'.  That is, 'rule' matches 'criteria' and this
1292  * function returns true if, for every field:
1293  *
1294  *   - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
1295  *     field, or
1296  *
1297  *   - 'criteria' wildcards the field,
1298  *
1299  * Conversely, 'rule' does not match 'criteria' and this function returns false
1300  * if, for at least one field:
1301  *
1302  *   - 'criteria' and 'rule' specify different values for the field, or
1303  *
1304  *   - 'criteria' specifies a value for the field but 'rule' wildcards it.
1305  *
1306  * Equivalently, the truth table for whether a field matches is:
1307  *
1308  *                                     rule
1309  *
1310  *                   c         wildcard    exact
1311  *                   r        +---------+---------+
1312  *                   i   wild |   yes   |   yes   |
1313  *                   t   card |         |         |
1314  *                   e        +---------+---------+
1315  *                   r  exact |    no   |if values|
1316  *                   i        |         |are equal|
1317  *                   a        +---------+---------+
1318  *
1319  * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
1320  * commands and by OpenFlow 1.0 aggregate and flow stats.
1321  *
1322  * Ignores rule->priority. */
1323 bool
1324 cls_rule_is_loose_match(const struct cls_rule *rule,
1325                         const struct minimatch *criteria)
1326 {
1327     return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
1328             && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
1329                                           &criteria->mask));
1330 }
1331 \f
1332 /* Iteration. */
1333
1334 static bool
1335 rule_matches(const struct cls_match *rule, const struct cls_rule *target)
1336 {
1337     return (!target
1338             || miniflow_equal_in_minimask(&rule->flow,
1339                                           &target->match.flow,
1340                                           &target->match.mask));
1341 }
1342
1343 static struct cls_match *
1344 search_subtable(const struct cls_subtable *subtable,
1345                 const struct cls_rule *target)
1346 {
1347     if (!target || !minimask_has_extra(&subtable->mask, &target->match.mask)) {
1348         struct cls_match *rule;
1349
1350         HMAP_FOR_EACH (rule, hmap_node, &subtable->rules) {
1351             if (rule_matches(rule, target)) {
1352                 return rule;
1353             }
1354         }
1355     }
1356     return NULL;
1357 }
1358
1359 /* Initializes 'cursor' for iterating through rules in 'cls':
1360  *
1361  *     - If 'target' is null, the cursor will visit every rule in 'cls'.
1362  *
1363  *     - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
1364  *       such that cls_rule_is_loose_match(rule, target) returns true.
1365  *
1366  * Ignores target->priority. */
1367 void
1368 cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
1369                 const struct cls_rule *target)
1370 {
1371     cursor->cls = cls->cls;
1372     cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL;
1373 }
1374
1375 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
1376  * pointer if there are no matches. */
1377 struct cls_rule *
1378 cls_cursor_first(struct cls_cursor *cursor)
1379 {
1380     struct cls_subtable *subtable;
1381
1382     HMAP_FOR_EACH (subtable, hmap_node, &cursor->cls->subtables) {
1383         struct cls_match *rule = search_subtable(subtable, cursor->target);
1384         if (rule) {
1385             cursor->subtable = subtable;
1386             return rule->cls_rule;
1387         }
1388     }
1389
1390     return NULL;
1391 }
1392
1393 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
1394  * pointer if there are no more matches. */
1395 struct cls_rule *
1396 cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_)
1397 {
1398     struct cls_match *rule = CONST_CAST(struct cls_match *, rule_->cls_match);
1399     const struct cls_subtable *subtable;
1400     struct cls_match *next;
1401
1402     next = next_rule_in_list__(rule);
1403     if (next->priority < rule->priority) {
1404         return next->cls_rule;
1405     }
1406
1407     /* 'next' is the head of the list, that is, the rule that is included in
1408      * the subtable's hmap.  (This is important when the classifier contains
1409      * rules that differ only in priority.) */
1410     rule = next;
1411     HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->subtable->rules) {
1412         if (rule_matches(rule, cursor->target)) {
1413             return rule->cls_rule;
1414         }
1415     }
1416
1417     subtable = cursor->subtable;
1418     HMAP_FOR_EACH_CONTINUE (subtable, hmap_node, &cursor->cls->subtables) {
1419         rule = search_subtable(subtable, cursor->target);
1420         if (rule) {
1421             cursor->subtable = subtable;
1422             return rule->cls_rule;
1423         }
1424     }
1425
1426     return NULL;
1427 }
1428 \f
1429 static struct cls_subtable *
1430 find_subtable(const struct cls_classifier *cls, const struct minimask *mask)
1431 {
1432     struct cls_subtable *subtable;
1433
1434     HMAP_FOR_EACH_IN_BUCKET (subtable, hmap_node, minimask_hash(mask, 0),
1435                              &cls->subtables) {
1436         if (minimask_equal(mask, &subtable->mask)) {
1437             return subtable;
1438         }
1439     }
1440     return NULL;
1441 }
1442
1443 static struct cls_subtable *
1444 insert_subtable(struct cls_classifier *cls, const struct minimask *mask)
1445 {
1446     uint32_t hash = minimask_hash(mask, 0);
1447     struct cls_subtable *subtable;
1448     int i, index = 0;
1449     struct flow_wildcards old, new;
1450     uint8_t prev;
1451     struct cls_subtable_entry elem;
1452     int count = count_1bits(mask->masks.map);
1453
1454     subtable = xzalloc(sizeof *subtable - sizeof mask->masks.inline_values
1455                        + MINIFLOW_VALUES_SIZE(count));
1456     hmap_init(&subtable->rules);
1457     miniflow_clone_inline(&subtable->mask.masks, &mask->masks, count);
1458
1459     /* Init indices for segmented lookup, if any. */
1460     flow_wildcards_init_catchall(&new);
1461     old = new;
1462     prev = 0;
1463     for (i = 0; i < cls->n_flow_segments; i++) {
1464         flow_wildcards_fold_minimask_range(&new, mask, prev,
1465                                            cls->flow_segments[i]);
1466         /* Add an index if it adds mask bits. */
1467         if (!flow_wildcards_equal(&new, &old)) {
1468             hindex_init(&subtable->indices[index]);
1469             subtable->index_ofs[index] = cls->flow_segments[i];
1470             index++;
1471             old = new;
1472         }
1473         prev = cls->flow_segments[i];
1474     }
1475     /* Check if the rest of the subtable's mask adds any bits,
1476      * and remove the last index if it doesn't. */
1477     if (index > 0) {
1478         flow_wildcards_fold_minimask_range(&new, mask, prev, FLOW_U32S);
1479         if (flow_wildcards_equal(&new, &old)) {
1480             --index;
1481             subtable->index_ofs[index] = 0;
1482             hindex_destroy(&subtable->indices[index]);
1483         }
1484     }
1485     subtable->n_indices = index;
1486
1487     subtable->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX
1488                      ? tag_create_deterministic(hash)
1489                      : TAG_ALL);
1490
1491     for (i = 0; i < cls->n_tries; i++) {
1492         subtable->trie_plen[i] = minimask_get_prefix_len(mask,
1493                                                          cls->tries[i].field);
1494     }
1495
1496     /* Ports trie. */
1497     subtable->ports_trie = NULL;
1498     subtable->ports_mask_len
1499         = 32 - ctz32(ntohl(MINIFLOW_GET_BE32(&mask->masks, tp_src)));
1500
1501     hmap_insert(&cls->subtables, &subtable->hmap_node, hash);
1502     elem.subtable = subtable;
1503     elem.tag = subtable->tag;
1504     elem.max_priority = subtable->max_priority;
1505     cls_subtable_cache_push_back(&cls->subtables_priority, elem);
1506
1507     return subtable;
1508 }
1509
1510 static void
1511 destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
1512 {
1513     int i;
1514     struct cls_subtable *table = NULL;
1515     struct cls_subtable_entry *iter;
1516
1517     CLS_SUBTABLE_CACHE_FOR_EACH (table, iter, &cls->subtables_priority) {
1518         if (table == subtable) {
1519             cls_subtable_cache_remove(&cls->subtables_priority, iter);
1520             break;
1521         }
1522     }
1523
1524     trie_destroy(subtable->ports_trie);
1525
1526     for (i = 0; i < subtable->n_indices; i++) {
1527         hindex_destroy(&subtable->indices[i]);
1528     }
1529     minimask_destroy(&subtable->mask);
1530     hmap_remove(&cls->subtables, &subtable->hmap_node);
1531     hmap_destroy(&subtable->rules);
1532     free(subtable);
1533 }
1534
1535 /* This function performs the following updates for 'subtable' in 'cls'
1536  * following the addition of a new rule with priority 'new_priority' to
1537  * 'subtable':
1538  *
1539  *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
1540  *
1541  *    - Update 'subtable''s position in 'cls->subtables_priority' if necessary.
1542  *
1543  * This function should only be called after adding a new rule, not after
1544  * replacing a rule by an identical one or modifying a rule in-place. */
1545 static void
1546 update_subtables_after_insertion(struct cls_classifier *cls,
1547                                  struct cls_subtable *subtable,
1548                                  unsigned int new_priority)
1549 {
1550     if (new_priority == subtable->max_priority) {
1551         ++subtable->max_count;
1552     } else if (new_priority > subtable->max_priority) {
1553         struct cls_subtable *table;
1554         struct cls_subtable_entry *iter, *subtable_iter = NULL;
1555
1556         subtable->max_priority = new_priority;
1557         subtable->max_count = 1;
1558
1559         /* Possibly move 'subtable' earlier in the priority list.  If we break
1560          * out of the loop, then 'subtable_iter' should be moved just before
1561          * 'iter'.  If the loop terminates normally, then 'iter' will be the
1562          * first list element and we'll move subtable just before that
1563          * (e.g. to the front of the list). */
1564         CLS_SUBTABLE_CACHE_FOR_EACH_REVERSE (table, iter, &cls->subtables_priority) {
1565             if (table == subtable) {
1566                 subtable_iter = iter; /* Locate the subtable as we go. */
1567                 iter->max_priority = new_priority;
1568             } else if (table->max_priority >= new_priority) {
1569                 if (subtable_iter == NULL) {
1570                     /* Corrupted cache? */
1571                     cls_subtable_cache_reset(cls);
1572                     VLOG_ABORT("update_subtables_after_insertion(): Subtable priority list corrupted.");
1573                     OVS_NOT_REACHED();
1574                 }
1575                 iter++;
1576                 break;
1577             }
1578         }
1579
1580         /* Move 'subtable' just before 'iter' (unless it's already there). */
1581         if (iter != subtable_iter) {
1582             cls_subtable_cache_splice(iter, subtable_iter, subtable_iter + 1);
1583         }
1584     }
1585 }
1586
1587 /* This function performs the following updates for 'subtable' in 'cls'
1588  * following the deletion of a rule with priority 'del_priority' from
1589  * 'subtable':
1590  *
1591  *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
1592  *
1593  *    - Update 'subtable''s position in 'cls->subtables_priority' if necessary.
1594  *
1595  * This function should only be called after removing a rule, not after
1596  * replacing a rule by an identical one or modifying a rule in-place. */
1597 static void
1598 update_subtables_after_removal(struct cls_classifier *cls,
1599                                struct cls_subtable *subtable,
1600                                unsigned int del_priority)
1601 {
1602     if (del_priority == subtable->max_priority && --subtable->max_count == 0) {
1603         struct cls_match *head;
1604         struct cls_subtable *table;
1605         struct cls_subtable_entry *iter, *subtable_iter = NULL;
1606
1607         subtable->max_priority = 0;
1608         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
1609             if (head->priority > subtable->max_priority) {
1610                 subtable->max_priority = head->priority;
1611                 subtable->max_count = 1;
1612             } else if (head->priority == subtable->max_priority) {
1613                 ++subtable->max_count;
1614             }
1615         }
1616
1617         /* Possibly move 'subtable' later in the priority list.  If we break
1618          * out of the loop, then 'subtable' should be moved just before that
1619          * 'iter'.  If the loop terminates normally, then 'iter' will be the
1620          * list head and we'll move subtable just before that (e.g. to the back
1621          * of the list). */
1622         CLS_SUBTABLE_CACHE_FOR_EACH (table, iter, &cls->subtables_priority) {
1623             if (table == subtable) {
1624                 subtable_iter = iter; /* Locate the subtable as we go. */
1625                 iter->max_priority = subtable->max_priority;
1626             } else if (table->max_priority <= subtable->max_priority) {
1627                 if (subtable_iter == NULL) {
1628                     /* Corrupted cache? */
1629                     cls_subtable_cache_reset(cls);
1630                     VLOG_ABORT("update_subtables_after_removal(): Subtable priority list corrupted.");
1631                     OVS_NOT_REACHED();
1632                 }
1633                 break;
1634             }
1635         }
1636
1637         /* Move 'subtable' just before 'iter' (unless it's already there). */
1638         if (iter != subtable_iter) {
1639             cls_subtable_cache_splice(iter, subtable_iter, subtable_iter + 1);
1640         }
1641     }
1642 }
1643
1644 struct range {
1645     uint8_t start;
1646     uint8_t end;
1647 };
1648
1649 /* Return 'true' if can skip rest of the subtable based on the prefix trie
1650  * lookup results. */
1651 static inline bool
1652 check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
1653             const unsigned int field_plen[CLS_MAX_TRIES],
1654             const struct range ofs, const struct flow *flow,
1655             struct flow_wildcards *wc)
1656 {
1657     int j;
1658
1659     /* Check if we could avoid fully unwildcarding the next level of
1660      * fields using the prefix tries.  The trie checks are done only as
1661      * needed to avoid folding in additional bits to the wildcards mask. */
1662     for (j = 0; j < n_tries; j++) {
1663         /* Is the trie field relevant for this subtable? */
1664         if (field_plen[j]) {
1665             struct trie_ctx *ctx = &trie_ctx[j];
1666             uint8_t be32ofs = ctx->be32ofs;
1667
1668             /* Is the trie field within the current range of fields? */
1669             if (be32ofs >= ofs.start && be32ofs < ofs.end) {
1670                 /* On-demand trie lookup. */
1671                 if (!ctx->lookup_done) {
1672                     ctx->match_plen = trie_lookup(ctx->trie, flow,
1673                                                   &ctx->maskbits);
1674                     ctx->lookup_done = true;
1675                 }
1676                 /* Possible to skip the rest of the subtable if subtable's
1677                  * prefix on the field is longer than what is known to match
1678                  * based on the trie lookup. */
1679                 if (field_plen[j] > ctx->match_plen) {
1680                     /* RFC: We want the trie lookup to never result in
1681                      * unwildcarding any bits that would not be unwildcarded
1682                      * otherwise.  Since the trie is shared by the whole
1683                      * classifier, it is possible that the 'maskbits' contain
1684                      * bits that are irrelevant for the partition of the
1685                      * classifier relevant for the current flow. */
1686
1687                     /* Can skip if the field is already unwildcarded. */
1688                     if (mask_prefix_bits_set(wc, be32ofs, ctx->maskbits)) {
1689                         return true;
1690                     }
1691                     /* Check that the trie result will not unwildcard more bits
1692                      * than this stage will. */
1693                     if (ctx->maskbits <= field_plen[j]) {
1694                         /* Unwildcard the bits and skip the rest. */
1695                         mask_set_prefix_bits(wc, be32ofs, ctx->maskbits);
1696                         /* Note: Prerequisite already unwildcarded, as the only
1697                          * prerequisite of the supported trie lookup fields is
1698                          * the ethertype, which is currently always
1699                          * unwildcarded.
1700                          */
1701                         return true;
1702                     }
1703                 }
1704             }
1705         }
1706     }
1707     return false;
1708 }
1709
1710 /* Returns true if 'target' satisifies 'flow'/'mask', that is, if each bit
1711  * for which 'flow', for which 'mask' has a bit set, specifies a particular
1712  * value has the correct value in 'target'.
1713  *
1714  * This function is equivalent to miniflow_equal_flow_in_minimask(flow,
1715  * target, mask) but it is faster because of the invariant that
1716  * flow->map and mask->masks.map are the same. */
1717 static inline bool
1718 miniflow_and_mask_matches_flow(const struct miniflow *flow,
1719                                const struct minimask *mask,
1720                                const struct flow *target)
1721 {
1722     const uint32_t *flowp = miniflow_get_u32_values(flow);
1723     const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
1724     uint32_t target_u32;
1725
1726     FLOW_FOR_EACH_IN_MAP(target_u32, target, mask->masks.map) {
1727         if ((*flowp++ ^ target_u32) & *maskp++) {
1728             return false;
1729         }
1730     }
1731
1732     return true;
1733 }
1734
1735 static inline struct cls_match *
1736 find_match(const struct cls_subtable *subtable, const struct flow *flow,
1737            uint32_t hash)
1738 {
1739     struct cls_match *rule;
1740
1741     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
1742         if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask,
1743                                            flow)) {
1744             return rule;
1745         }
1746     }
1747
1748     return NULL;
1749 }
1750
1751 static struct cls_match *
1752 find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
1753               struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
1754               struct flow_wildcards *wc)
1755 {
1756     uint32_t basis = 0, hash;
1757     struct cls_match *rule = NULL;
1758     int i;
1759     struct range ofs;
1760
1761     if (OVS_UNLIKELY(!wc)) {
1762         return find_match(subtable, flow,
1763                           flow_hash_in_minimask(flow, &subtable->mask, 0));
1764     }
1765
1766     ofs.start = 0;
1767     /* Try to finish early by checking fields in segments. */
1768     for (i = 0; i < subtable->n_indices; i++) {
1769         struct hindex_node *inode;
1770         ofs.end = subtable->index_ofs[i];
1771
1772         if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow,
1773                         wc)) {
1774             goto range_out;
1775         }
1776         hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
1777                                            ofs.end, &basis);
1778         ofs.start = ofs.end;
1779         inode = hindex_node_with_hash(&subtable->indices[i], hash);
1780         if (!inode) {
1781             /* No match, can stop immediately, but must fold in the mask
1782              * covered so far. */
1783             goto range_out;
1784         }
1785
1786         /* If we have narrowed down to a single rule already, check whether
1787          * that rule matches.  If it does match, then we're done.  If it does
1788          * not match, then we know that we will never get a match, but we do
1789          * not yet know how many wildcards we need to fold into 'wc' so we
1790          * continue iterating through indices to find that out.  (We won't
1791          * waste time calling miniflow_and_mask_matches_flow() again because
1792          * we've set 'rule' nonnull.)
1793          *
1794          * This check shows a measurable benefit with non-trivial flow tables.
1795          *
1796          * (Rare) hash collisions may cause us to miss the opportunity for this
1797          * optimization. */
1798         if (!inode->s && !rule) {
1799             ASSIGN_CONTAINER(rule, inode - i, index_nodes);
1800             if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask,
1801                                                flow)) {
1802                 goto out;
1803             }
1804         }
1805     }
1806     ofs.end = FLOW_U32S;
1807     /* Trie check for the final range. */
1808     if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow, wc)) {
1809         goto range_out;
1810     }
1811     if (!rule) {
1812         /* Multiple potential matches exist, look for one. */
1813         hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
1814                                            ofs.end, &basis);
1815         rule = find_match(subtable, flow, hash);
1816     } else {
1817         /* We already narrowed the matching candidates down to just 'rule',
1818          * but it didn't match. */
1819         rule = NULL;
1820     }
1821     if (!rule && subtable->ports_mask_len) {
1822         /* Ports are always part of the final range, if any.
1823          * No match was found for the ports.  Use the ports trie to figure out
1824          * which ports bits to unwildcard. */
1825         unsigned int mbits;
1826         ovs_be32 value, mask;
1827
1828         mask = MINIFLOW_GET_BE32(&subtable->mask.masks, tp_src);
1829         value = ((OVS_FORCE ovs_be32 *)flow)[TP_PORTS_OFS32] & mask;
1830         trie_lookup_value(subtable->ports_trie, &value, &mbits);
1831
1832         ((OVS_FORCE ovs_be32 *)&wc->masks)[TP_PORTS_OFS32] |=
1833             mask & htonl(~0 << (32 - mbits));
1834
1835         ofs.start = TP_PORTS_OFS32;
1836         goto range_out;
1837     }
1838  out:
1839     /* Must unwildcard all the fields, as they were looked at. */
1840     flow_wildcards_fold_minimask(wc, &subtable->mask);
1841     return rule;
1842
1843  range_out:
1844     /* Must unwildcard the fields looked up so far, if any. */
1845     if (ofs.start) {
1846         flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0, ofs.start);
1847     }
1848     return NULL;
1849 }
1850
1851 static struct cls_match *
1852 find_equal(struct cls_subtable *subtable, const struct miniflow *flow,
1853            uint32_t hash)
1854 {
1855     struct cls_match *head;
1856
1857     HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &subtable->rules) {
1858         if (miniflow_equal(&head->flow, flow)) {
1859             return head;
1860         }
1861     }
1862     return NULL;
1863 }
1864
1865 static struct cls_match *
1866 insert_rule(struct cls_classifier *cls, struct cls_subtable *subtable,
1867             struct cls_rule *new)
1868 {
1869     struct cls_match *cls_match = cls_match_alloc(new);
1870     struct cls_match *head;
1871     struct cls_match *old = NULL;
1872     int i;
1873     uint32_t basis = 0, hash;
1874     uint8_t prev_be32ofs = 0;
1875
1876     /* Add new node to segment indices. */
1877     for (i = 0; i < subtable->n_indices; i++) {
1878         hash = minimatch_hash_range(&new->match, prev_be32ofs,
1879                                     subtable->index_ofs[i], &basis);
1880         hindex_insert(&subtable->indices[i], &cls_match->index_nodes[i], hash);
1881         prev_be32ofs = subtable->index_ofs[i];
1882     }
1883     hash = minimatch_hash_range(&new->match, prev_be32ofs, FLOW_U32S, &basis);
1884     head = find_equal(subtable, &new->match.flow, hash);
1885     if (!head) {
1886         hmap_insert(&subtable->rules, &cls_match->hmap_node, hash);
1887         list_init(&cls_match->list);
1888         goto out;
1889     } else {
1890         /* Scan the list for the insertion point that will keep the list in
1891          * order of decreasing priority. */
1892         struct cls_match *rule;
1893
1894         cls_match->hmap_node.hash = hash; /* Otherwise done by hmap_insert. */
1895
1896         FOR_EACH_RULE_IN_LIST (rule, head) {
1897             if (cls_match->priority >= rule->priority) {
1898                 if (rule == head) {
1899                     /* 'new' is the new highest-priority flow in the list. */
1900                     hmap_replace(&subtable->rules,
1901                                  &rule->hmap_node, &cls_match->hmap_node);
1902                 }
1903
1904                 if (cls_match->priority == rule->priority) {
1905                     list_replace(&cls_match->list, &rule->list);
1906                     old = rule;
1907                     goto out;
1908                 } else {
1909                     list_insert(&rule->list, &cls_match->list);
1910                     goto out;
1911                 }
1912             }
1913         }
1914
1915         /* Insert 'new' at the end of the list. */
1916         list_push_back(&head->list, &cls_match->list);
1917     }
1918
1919  out:
1920     if (!old) {
1921         update_subtables_after_insertion(cls, subtable, cls_match->priority);
1922     } else {
1923         /* Remove old node from indices. */
1924         for (i = 0; i < subtable->n_indices; i++) {
1925             hindex_remove(&subtable->indices[i], &old->index_nodes[i]);
1926         }
1927     }
1928     return old;
1929 }
1930
1931 static struct cls_match *
1932 next_rule_in_list__(struct cls_match *rule)
1933 {
1934     struct cls_match *next = OBJECT_CONTAINING(rule->list.next, next, list);
1935     return next;
1936 }
1937
1938 static struct cls_match *
1939 next_rule_in_list(struct cls_match *rule)
1940 {
1941     struct cls_match *next = next_rule_in_list__(rule);
1942     return next->priority < rule->priority ? next : NULL;
1943 }
1944 \f
1945 /* A longest-prefix match tree. */
1946 struct trie_node {
1947     uint32_t prefix;           /* Prefix bits for this node, MSB first. */
1948     uint8_t  nbits;            /* Never zero, except for the root node. */
1949     unsigned int n_rules;      /* Number of rules that have this prefix. */
1950     struct trie_node *edges[2]; /* Both NULL if leaf. */
1951 };
1952
1953 /* Max bits per node.  Must fit in struct trie_node's 'prefix'.
1954  * Also tested with 16, 8, and 5 to stress the implementation. */
1955 #define TRIE_PREFIX_BITS 32
1956
1957 /* Return at least 'plen' bits of the 'prefix', starting at bit offset 'ofs'.
1958  * Prefixes are in the network byte order, and the offset 0 corresponds to
1959  * the most significant bit of the first byte.  The offset can be read as
1960  * "how many bits to skip from the start of the prefix starting at 'pr'". */
1961 static uint32_t
1962 raw_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
1963 {
1964     uint32_t prefix;
1965
1966     pr += ofs / 32; /* Where to start. */
1967     ofs %= 32;      /* How many bits to skip at 'pr'. */
1968
1969     prefix = ntohl(*pr) << ofs; /* Get the first 32 - ofs bits. */
1970     if (plen > 32 - ofs) {      /* Need more than we have already? */
1971         prefix |= ntohl(*++pr) >> (32 - ofs);
1972     }
1973     /* Return with possible unwanted bits at the end. */
1974     return prefix;
1975 }
1976
1977 /* Return min(TRIE_PREFIX_BITS, plen) bits of the 'prefix', starting at bit
1978  * offset 'ofs'.  Prefixes are in the network byte order, and the offset 0
1979  * corresponds to the most significant bit of the first byte.  The offset can
1980  * be read as "how many bits to skip from the start of the prefix starting at
1981  * 'pr'". */
1982 static uint32_t
1983 trie_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
1984 {
1985     if (!plen) {
1986         return 0;
1987     }
1988     if (plen > TRIE_PREFIX_BITS) {
1989         plen = TRIE_PREFIX_BITS; /* Get at most TRIE_PREFIX_BITS. */
1990     }
1991     /* Return with unwanted bits cleared. */
1992     return raw_get_prefix(pr, ofs, plen) & ~0u << (32 - plen);
1993 }
1994
1995 /* Return the number of equal bits in 'nbits' of 'prefix's MSBs and a 'value'
1996  * starting at "MSB 0"-based offset 'ofs'. */
1997 static unsigned int
1998 prefix_equal_bits(uint32_t prefix, unsigned int nbits, const ovs_be32 value[],
1999                   unsigned int ofs)
2000 {
2001     uint64_t diff = prefix ^ raw_get_prefix(value, ofs, nbits);
2002     /* Set the bit after the relevant bits to limit the result. */
2003     return raw_clz64(diff << 32 | UINT64_C(1) << (63 - nbits));
2004 }
2005
2006 /* Return the number of equal bits in 'node' prefix and a 'prefix' of length
2007  * 'plen', starting at "MSB 0"-based offset 'ofs'. */
2008 static unsigned int
2009 trie_prefix_equal_bits(const struct trie_node *node, const ovs_be32 prefix[],
2010                        unsigned int ofs, unsigned int plen)
2011 {
2012     return prefix_equal_bits(node->prefix, MIN(node->nbits, plen - ofs),
2013                              prefix, ofs);
2014 }
2015
2016 /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int.  'ofs' can
2017  * be greater than 31. */
2018 static unsigned int
2019 be_get_bit_at(const ovs_be32 value[], unsigned int ofs)
2020 {
2021     return (((const uint8_t *)value)[ofs / 8] >> (7 - ofs % 8)) & 1u;
2022 }
2023
2024 /* Return the bit at ("MSB 0"-based) offset 'ofs' as an int.  'ofs' must
2025  * be between 0 and 31, inclusive. */
2026 static unsigned int
2027 get_bit_at(const uint32_t prefix, unsigned int ofs)
2028 {
2029     return (prefix >> (31 - ofs)) & 1u;
2030 }
2031
2032 /* Create new branch. */
2033 static struct trie_node *
2034 trie_branch_create(const ovs_be32 *prefix, unsigned int ofs, unsigned int plen,
2035                    unsigned int n_rules)
2036 {
2037     struct trie_node *node = xmalloc(sizeof *node);
2038
2039     node->prefix = trie_get_prefix(prefix, ofs, plen);
2040
2041     if (plen <= TRIE_PREFIX_BITS) {
2042         node->nbits = plen;
2043         node->edges[0] = NULL;
2044         node->edges[1] = NULL;
2045         node->n_rules = n_rules;
2046     } else { /* Need intermediate nodes. */
2047         struct trie_node *subnode = trie_branch_create(prefix,
2048                                                        ofs + TRIE_PREFIX_BITS,
2049                                                        plen - TRIE_PREFIX_BITS,
2050                                                        n_rules);
2051         int bit = get_bit_at(subnode->prefix, 0);
2052         node->nbits = TRIE_PREFIX_BITS;
2053         node->edges[bit] = subnode;
2054         node->edges[!bit] = NULL;
2055         node->n_rules = 0;
2056     }
2057     return node;
2058 }
2059
2060 static void
2061 trie_node_destroy(struct trie_node *node)
2062 {
2063     free(node);
2064 }
2065
2066 static void
2067 trie_destroy(struct trie_node *node)
2068 {
2069     if (node) {
2070         trie_destroy(node->edges[0]);
2071         trie_destroy(node->edges[1]);
2072         free(node);
2073     }
2074 }
2075
2076 static bool
2077 trie_is_leaf(const struct trie_node *trie)
2078 {
2079     return !trie->edges[0] && !trie->edges[1]; /* No children. */
2080 }
2081
2082 static void
2083 mask_set_prefix_bits(struct flow_wildcards *wc, uint8_t be32ofs,
2084                      unsigned int nbits)
2085 {
2086     ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs];
2087     unsigned int i;
2088
2089     for (i = 0; i < nbits / 32; i++) {
2090         mask[i] = OVS_BE32_MAX;
2091     }
2092     if (nbits % 32) {
2093         mask[i] |= htonl(~0u << (32 - nbits % 32));
2094     }
2095 }
2096
2097 static bool
2098 mask_prefix_bits_set(const struct flow_wildcards *wc, uint8_t be32ofs,
2099                      unsigned int nbits)
2100 {
2101     ovs_be32 *mask = &((ovs_be32 *)&wc->masks)[be32ofs];
2102     unsigned int i;
2103     ovs_be32 zeroes = 0;
2104
2105     for (i = 0; i < nbits / 32; i++) {
2106         zeroes |= ~mask[i];
2107     }
2108     if (nbits % 32) {
2109         zeroes |= ~mask[i] & htonl(~0u << (32 - nbits % 32));
2110     }
2111
2112     return !zeroes; /* All 'nbits' bits set. */
2113 }
2114
2115 static struct trie_node **
2116 trie_next_edge(struct trie_node *node, const ovs_be32 value[],
2117                unsigned int ofs)
2118 {
2119     return node->edges + be_get_bit_at(value, ofs);
2120 }
2121
2122 static const struct trie_node *
2123 trie_next_node(const struct trie_node *node, const ovs_be32 value[],
2124                unsigned int ofs)
2125 {
2126     return node->edges[be_get_bit_at(value, ofs)];
2127 }
2128
2129 /* Return the prefix mask length necessary to find the longest-prefix match for
2130  * the '*value' in the prefix tree 'node'.
2131  * '*checkbits' is set to the number of bits in the prefix mask necessary to
2132  * determine a mismatch, in case there are longer prefixes in the tree below
2133  * the one that matched.
2134  */
2135 static unsigned int
2136 trie_lookup_value(const struct trie_node *node, const ovs_be32 value[],
2137                   unsigned int *checkbits)
2138 {
2139     unsigned int plen = 0, match_len = 0;
2140     const struct trie_node *prev = NULL;
2141
2142     for (; node; prev = node, node = trie_next_node(node, value, plen)) {
2143         unsigned int eqbits;
2144         /* Check if this edge can be followed. */
2145         eqbits = prefix_equal_bits(node->prefix, node->nbits, value, plen);
2146         plen += eqbits;
2147         if (eqbits < node->nbits) { /* Mismatch, nothing more to be found. */
2148             /* Bit at offset 'plen' differed. */
2149             *checkbits = plen + 1; /* Includes the first mismatching bit. */
2150             return match_len;
2151         }
2152         /* Full match, check if rules exist at this prefix length. */
2153         if (node->n_rules > 0) {
2154             match_len = plen;
2155         }
2156     }
2157     /* Dead end, exclude the other branch if it exists. */
2158     *checkbits = !prev || trie_is_leaf(prev) ? plen : plen + 1;
2159     return match_len;
2160 }
2161
2162 static unsigned int
2163 trie_lookup(const struct cls_trie *trie, const struct flow *flow,
2164             unsigned int *checkbits)
2165 {
2166     const struct mf_field *mf = trie->field;
2167
2168     /* Check that current flow matches the prerequisites for the trie
2169      * field.  Some match fields are used for multiple purposes, so we
2170      * must check that the trie is relevant for this flow. */
2171     if (mf_are_prereqs_ok(mf, flow)) {
2172         return trie_lookup_value(trie->root,
2173                                  &((ovs_be32 *)flow)[mf->flow_be32ofs],
2174                                  checkbits);
2175     }
2176     *checkbits = 0; /* Value not used in this case. */
2177     return UINT_MAX;
2178 }
2179
2180 /* Returns the length of a prefix match mask for the field 'mf' in 'minimask'.
2181  * Returns the u32 offset to the miniflow data in '*miniflow_index', if
2182  * 'miniflow_index' is not NULL. */
2183 static unsigned int
2184 minimask_get_prefix_len(const struct minimask *minimask,
2185                         const struct mf_field *mf)
2186 {
2187     unsigned int nbits = 0, mask_tz = 0; /* Non-zero when end of mask seen. */
2188     uint8_t u32_ofs = mf->flow_be32ofs;
2189     uint8_t u32_end = u32_ofs + mf->n_bytes / 4;
2190
2191     for (; u32_ofs < u32_end; ++u32_ofs) {
2192         uint32_t mask;
2193         mask = ntohl((OVS_FORCE ovs_be32)minimask_get(minimask, u32_ofs));
2194
2195         /* Validate mask, count the mask length. */
2196         if (mask_tz) {
2197             if (mask) {
2198                 return 0; /* No bits allowed after mask ended. */
2199             }
2200         } else {
2201             if (~mask & (~mask + 1)) {
2202                 return 0; /* Mask not contiguous. */
2203             }
2204             mask_tz = ctz32(mask);
2205             nbits += 32 - mask_tz;
2206         }
2207     }
2208
2209     return nbits;
2210 }
2211
2212 /*
2213  * This is called only when mask prefix is known to be CIDR and non-zero.
2214  * Relies on the fact that the flow and mask have the same map, and since
2215  * the mask is CIDR, the storage for the flow field exists even if it
2216  * happened to be zeros.
2217  */
2218 static const ovs_be32 *
2219 minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf)
2220 {
2221     return miniflow_get_be32_values(&match->flow) +
2222         count_1bits(match->flow.map & ((UINT64_C(1) << mf->flow_be32ofs) - 1));
2223 }
2224
2225 /* Insert rule in to the prefix tree.
2226  * 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
2227  * in 'rule'. */
2228 static void
2229 trie_insert(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
2230 {
2231     trie_insert_prefix(&trie->root,
2232                        minimatch_get_prefix(&rule->match, trie->field), mlen);
2233 }
2234
2235 static void
2236 trie_insert_prefix(struct trie_node **edge, const ovs_be32 *prefix, int mlen)
2237 {
2238     struct trie_node *node;
2239     int ofs = 0;
2240
2241     /* Walk the tree. */
2242     for (; (node = *edge) != NULL;
2243          edge = trie_next_edge(node, prefix, ofs)) {
2244         unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
2245         ofs += eqbits;
2246         if (eqbits < node->nbits) {
2247             /* Mismatch, new node needs to be inserted above. */
2248             int old_branch = get_bit_at(node->prefix, eqbits);
2249
2250             /* New parent node. */
2251             *edge = trie_branch_create(prefix, ofs - eqbits, eqbits,
2252                                        ofs == mlen ? 1 : 0);
2253
2254             /* Adjust old node for its new position in the tree. */
2255             node->prefix <<= eqbits;
2256             node->nbits -= eqbits;
2257             (*edge)->edges[old_branch] = node;
2258
2259             /* Check if need a new branch for the new rule. */
2260             if (ofs < mlen) {
2261                 (*edge)->edges[!old_branch]
2262                     = trie_branch_create(prefix, ofs, mlen - ofs, 1);
2263             }
2264             return;
2265         }
2266         /* Full match so far. */
2267
2268         if (ofs == mlen) {
2269             /* Full match at the current node, rule needs to be added here. */
2270             node->n_rules++;
2271             return;
2272         }
2273     }
2274     /* Must insert a new tree branch for the new rule. */
2275     *edge = trie_branch_create(prefix, ofs, mlen - ofs, 1);
2276 }
2277
2278 /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
2279  * in 'rule'. */
2280 static void
2281 trie_remove(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
2282 {
2283     trie_remove_prefix(&trie->root,
2284                        minimatch_get_prefix(&rule->match, trie->field), mlen);
2285 }
2286
2287 /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
2288  * in 'rule'. */
2289 static void
2290 trie_remove_prefix(struct trie_node **root, const ovs_be32 *prefix, int mlen)
2291 {
2292     struct trie_node *node;
2293     struct trie_node **edges[sizeof(union mf_value) * 8];
2294     int depth = 0, ofs = 0;
2295
2296     /* Walk the tree. */
2297     for (edges[0] = root;
2298          (node = *edges[depth]) != NULL;
2299          edges[++depth] = trie_next_edge(node, prefix, ofs)) {
2300         unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
2301
2302         if (eqbits < node->nbits) {
2303             /* Mismatch, nothing to be removed.  This should never happen, as
2304              * only rules in the classifier are ever removed. */
2305             break; /* Log a warning. */
2306         }
2307         /* Full match so far. */
2308         ofs += eqbits;
2309
2310         if (ofs == mlen) {
2311             /* Full prefix match at the current node, remove rule here. */
2312             if (!node->n_rules) {
2313                 break; /* Log a warning. */
2314             }
2315             node->n_rules--;
2316
2317             /* Check if can prune the tree. */
2318             while (!node->n_rules && !(node->edges[0] && node->edges[1])) {
2319                 /* No rules and at most one child node, remove this node. */
2320                 struct trie_node *next;
2321                 next = node->edges[0] ? node->edges[0] : node->edges[1];
2322
2323                 if (next) {
2324                     if (node->nbits + next->nbits > TRIE_PREFIX_BITS) {
2325                         break;   /* Cannot combine. */
2326                     }
2327                     /* Combine node with next. */
2328                     next->prefix = node->prefix | next->prefix >> node->nbits;
2329                     next->nbits += node->nbits;
2330                 }
2331                 trie_node_destroy(node);
2332                 /* Update the parent's edge. */
2333                 *edges[depth] = next;
2334                 if (next || !depth) {
2335                     /* Branch not pruned or at root, nothing more to do. */
2336                     break;
2337                 }
2338                 node = *edges[--depth];
2339             }
2340             return;
2341         }
2342     }
2343     /* Cannot go deeper. This should never happen, since only rules
2344      * that actually exist in the classifier are ever removed. */
2345     VLOG_WARN("Trying to remove non-existing rule from a prefix trie.");
2346 }