lib/classifier.c

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