lib/classifier.c

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