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 "packets.h"
  28 #include "ovs-thread.h"
  29
  30 static struct cls_subtable *find_subtable(const struct classifier *,
  31                                           const struct minimask *);
  32 static struct cls_subtable *insert_subtable(struct classifier *,
  33                                             const struct minimask *);
  34
  35 static void destroy_subtable(struct classifier *, struct cls_subtable *);
  36
  37 static void update_subtables_after_insertion(struct classifier *,
  38                                              struct cls_subtable *,
  39                                              unsigned int new_priority);
  40 static void update_subtables_after_removal(struct classifier *,
  41                                            struct cls_subtable *,
  42                                            unsigned int del_priority);
  43
  44 static struct cls_rule *find_match_wc(const struct cls_subtable *,
  45                                       const struct flow *,
  46                                       struct flow_wildcards *);
  47 static struct cls_rule *find_equal(struct cls_subtable *,
  48                                    const struct miniflow *, uint32_t hash);
  49 static struct cls_rule *insert_rule(struct classifier *,
  50                                     struct cls_subtable *, struct cls_rule *);
  51
  52 /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
  53 #define FOR_EACH_RULE_IN_LIST(RULE, HEAD)                               \
  54     for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE))
  55 #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD)                    \
  56     for ((RULE) = (HEAD);                                               \
  57          (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true);    \
  58          (RULE) = (NEXT))
  59
  60 static struct cls_rule *next_rule_in_list__(struct cls_rule *);
  61 static struct cls_rule *next_rule_in_list(struct cls_rule *);
  62 \f
  63 /* cls_rule. */
  64
  65 /* Initializes 'rule' to match packets specified by 'match' at the given
  66  * 'priority'.  'match' must satisfy the invariant described in the comment at
  67  * the definition of struct match.
  68  *
  69  * The caller must eventually destroy 'rule' with cls_rule_destroy().
  70  *
  71  * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but
  72  * internally Open vSwitch supports a wider range.) */
  73 void
  74 cls_rule_init(struct cls_rule *rule,
  75               const struct match *match, unsigned int priority)
  76 {
  77     minimatch_init(&rule->match, match);
  78     rule->priority = priority;
  79 }
  80
  81 /* Same as cls_rule_init() for initialization from a "struct minimatch". */
  82 void
  83 cls_rule_init_from_minimatch(struct cls_rule *rule,
  84                              const struct minimatch *match,
  85                              unsigned int priority)
  86 {
  87     minimatch_clone(&rule->match, match);
  88     rule->priority = priority;
  89 }
  90
  91 /* Initializes 'dst' as a copy of 'src'.
  92  *
  93  * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
  94 void
  95 cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
  96 {
  97     minimatch_clone(&dst->match, &src->match);
  98     dst->priority = src->priority;
  99 }
 100
 101 /* Initializes 'dst' with the data in 'src', destroying 'src'.
 102  *
 103  * The caller must eventually destroy 'dst' with cls_rule_destroy(). */
 104 void
 105 cls_rule_move(struct cls_rule *dst, struct cls_rule *src)
 106 {
 107     minimatch_move(&dst->match, &src->match);
 108     dst->priority = src->priority;
 109 }
 110
 111 /* Frees memory referenced by 'rule'.  Doesn't free 'rule' itself (it's
 112  * normally embedded into a larger structure).
 113  *
 114  * ('rule' must not currently be in a classifier.) */
 115 void
 116 cls_rule_destroy(struct cls_rule *rule)
 117 {
 118     minimatch_destroy(&rule->match);
 119 }
 120
 121 /* Returns true if 'a' and 'b' match the same packets at the same priority,
 122  * false if they differ in some way. */
 123 bool
 124 cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
 125 {
 126     return a->priority == b->priority && minimatch_equal(&a->match, &b->match);
 127 }
 128
 129 /* Returns a hash value for 'rule', folding in 'basis'. */
 130 uint32_t
 131 cls_rule_hash(const struct cls_rule *rule, uint32_t basis)
 132 {
 133     return minimatch_hash(&rule->match, hash_int(rule->priority, basis));
 134 }
 135
 136 /* Appends a string describing 'rule' to 's'. */
 137 void
 138 cls_rule_format(const struct cls_rule *rule, struct ds *s)
 139 {
 140     minimatch_format(&rule->match, s, rule->priority);
 141 }
 142
 143 /* Returns true if 'rule' matches every packet, false otherwise. */
 144 bool
 145 cls_rule_is_catchall(const struct cls_rule *rule)
 146 {
 147     return minimask_is_catchall(&rule->match.mask);
 148 }
 149 \f
 150 /* Initializes 'cls' as a classifier that initially contains no classification
 151  * rules. */
 152 void
 153 classifier_init(struct classifier *cls, const uint8_t *flow_segments)
 154 {
 155     cls->n_rules = 0;
 156     hmap_init(&cls->subtables);
 157     list_init(&cls->subtables_priority);
 158     hmap_init(&cls->partitions);
 159     ovs_rwlock_init(&cls->rwlock);
 160     cls->n_flow_segments = 0;
 161     if (flow_segments) {
 162         while (cls->n_flow_segments < CLS_MAX_INDICES
 163                && *flow_segments < FLOW_U32S) {
 164             cls->flow_segments[cls->n_flow_segments++] = *flow_segments++;
 165         }
 166     }
 167 }
 168
 169 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
 170  * caller's responsibility. */
 171 void
 172 classifier_destroy(struct classifier *cls)
 173 {
 174     if (cls) {
 175         struct cls_subtable *partition, *next_partition;
 176         struct cls_subtable *subtable, *next_subtable;
 177
 178         HMAP_FOR_EACH_SAFE (subtable, next_subtable, hmap_node,
 179                             &cls->subtables) {
 180             destroy_subtable(cls, subtable);
 181         }
 182         hmap_destroy(&cls->subtables);
 183
 184         HMAP_FOR_EACH_SAFE (partition, next_partition, hmap_node,
 185                             &cls->partitions) {
 186             hmap_remove(&cls->partitions, &partition->hmap_node);
 187             free(partition);
 188         }
 189         hmap_destroy(&cls->partitions);
 190         ovs_rwlock_destroy(&cls->rwlock);
 191     }
 192 }
 193
 194 /* Returns true if 'cls' contains no classification rules, false otherwise. */
 195 bool
 196 classifier_is_empty(const struct classifier *cls)
 197 {
 198     return cls->n_rules == 0;
 199 }
 200
 201 /* Returns the number of rules in 'cls'. */
 202 int
 203 classifier_count(const struct classifier *cls)
 204 {
 205     return cls->n_rules;
 206 }
 207
 208 static uint32_t
 209 hash_metadata(ovs_be64 metadata_)
 210 {
 211     uint64_t metadata = (OVS_FORCE uint64_t) metadata_;
 212     return hash_2words(metadata, metadata >> 32);
 213 }
 214
 215 static struct cls_partition *
 216 find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash)
 217 {
 218     struct cls_partition *partition;
 219
 220     HMAP_FOR_EACH_IN_BUCKET (partition, hmap_node, hash, &cls->partitions) {
 221         if (partition->metadata == metadata) {
 222             return partition;
 223         }
 224     }
 225
 226     return NULL;
 227 }
 228
 229 static struct cls_partition *
 230 create_partition(struct classifier *cls, struct cls_subtable *subtable,
 231                  ovs_be64 metadata)
 232 {
 233     uint32_t hash = hash_metadata(metadata);
 234     struct cls_partition *partition = find_partition(cls, metadata, hash);
 235     if (!partition) {
 236         partition = xmalloc(sizeof *partition);
 237         partition->metadata = metadata;
 238         partition->tags = 0;
 239         tag_tracker_init(&partition->tracker);
 240         hmap_insert(&cls->partitions, &partition->hmap_node, hash);
 241     }
 242     tag_tracker_add(&partition->tracker, &partition->tags, subtable->tag);
 243     return partition;
 244 }
 245
 246 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 247  * must not modify or free it.
 248  *
 249  * If 'cls' already contains an identical rule (including wildcards, values of
 250  * fixed fields, and priority), replaces the old rule by 'rule' and returns the
 251  * rule that was replaced.  The caller takes ownership of the returned rule and
 252  * is thus responsible for destroying it with cls_rule_destroy(), freeing the
 253  * memory block in which it resides, etc., as necessary.
 254  *
 255  * Returns NULL if 'cls' does not contain a rule with an identical key, after
 256  * inserting the new rule.  In this case, no rules are displaced by the new
 257  * rule, even rules that cannot have any effect because the new rule matches a
 258  * superset of their flows and has higher priority. */
 259 struct cls_rule *
 260 classifier_replace(struct classifier *cls, struct cls_rule *rule)
 261 {
 262     struct cls_rule *old_rule;
 263     struct cls_subtable *subtable;
 264
 265     subtable = find_subtable(cls, &rule->match.mask);
 266     if (!subtable) {
 267         subtable = insert_subtable(cls, &rule->match.mask);
 268     }
 269
 270     old_rule = insert_rule(cls, subtable, rule);
 271     if (!old_rule) {
 272         if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
 273             ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
 274             rule->partition = create_partition(cls, subtable, metadata);
 275         } else {
 276             rule->partition = NULL;
 277         }
 278
 279         subtable->n_rules++;
 280         cls->n_rules++;
 281     } else {
 282         rule->partition = old_rule->partition;
 283     }
 284     return old_rule;
 285 }
 286
 287 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 288  * must not modify or free it.
 289  *
 290  * 'cls' must not contain an identical rule (including wildcards, values of
 291  * fixed fields, and priority).  Use classifier_find_rule_exactly() to find
 292  * such a rule. */
 293 void
 294 classifier_insert(struct classifier *cls, struct cls_rule *rule)
 295 {
 296     struct cls_rule *displaced_rule = classifier_replace(cls, rule);
 297     ovs_assert(!displaced_rule);
 298 }
 299
 300 /* Removes 'rule' from 'cls'.  It is the caller's responsibility to destroy
 301  * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule'
 302  * resides, etc., as necessary. */
 303 void
 304 classifier_remove(struct classifier *cls, struct cls_rule *rule)
 305 {
 306     struct cls_partition *partition;
 307     struct cls_rule *head;
 308     struct cls_subtable *subtable;
 309     int i;
 310
 311     subtable = find_subtable(cls, &rule->match.mask);
 312
 313     /* Remove rule node from indices. */
 314     for (i = 0; i < subtable->n_indices; i++) {
 315         hindex_remove(&subtable->indices[i], &rule->index_nodes[i]);
 316     }
 317
 318     head = find_equal(subtable, &rule->match.flow, rule->hmap_node.hash);
 319     if (head != rule) {
 320         list_remove(&rule->list);
 321     } else if (list_is_empty(&rule->list)) {
 322         hmap_remove(&subtable->rules, &rule->hmap_node);
 323     } else {
 324         struct cls_rule *next = CONTAINER_OF(rule->list.next,
 325                                              struct cls_rule, list);
 326
 327         list_remove(&rule->list);
 328         hmap_replace(&subtable->rules, &rule->hmap_node, &next->hmap_node);
 329     }
 330
 331     partition = rule->partition;
 332     if (partition) {
 333         tag_tracker_subtract(&partition->tracker, &partition->tags,
 334                              subtable->tag);
 335         if (!partition->tags) {
 336             hmap_remove(&cls->partitions, &partition->hmap_node);
 337             free(partition);
 338         }
 339     }
 340
 341     if (--subtable->n_rules == 0) {
 342         destroy_subtable(cls, subtable);
 343     } else {
 344         update_subtables_after_removal(cls, subtable, rule->priority);
 345     }
 346     cls->n_rules--;
 347 }
 348
 349 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
 350  * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
 351  * of equal priority match 'flow', returns one arbitrarily.
 352  *
 353  * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
 354  * set of bits that were significant in the lookup.  At some point
 355  * earlier, 'wc' should have been initialized (e.g., by
 356  * flow_wildcards_init_catchall()). */
 357 struct cls_rule *
 358 classifier_lookup(const struct classifier *cls, const struct flow *flow,
 359                   struct flow_wildcards *wc)
 360 {
 361     const struct cls_partition *partition;
 362     struct cls_subtable *subtable;
 363     struct cls_rule *best;
 364     tag_type tags;
 365
 366     /* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them,
 367      * then 'flow' cannot possibly match in 'subtable':
 368      *
 369      *     - If flow->metadata maps to a given 'partition', then we can use
 370      *       'tags' for 'partition->tags'.
 371      *
 372      *     - If flow->metadata has no partition, then no rule in 'cls' has an
 373      *       exact-match for flow->metadata.  That means that we don't need to
 374      *       search any subtable that includes flow->metadata in its mask.
 375      *
 376      * In either case, we always need to search any cls_subtables that do not
 377      * include flow->metadata in its mask.  One way to do that would be to
 378      * check the "cls_subtable"s explicitly for that, but that would require an
 379      * extra branch per subtable.  Instead, we mark such a cls_subtable's
 380      * 'tags' as TAG_ALL and make sure that 'tags' is never empty.  This means
 381      * that 'tags' always intersects such a cls_subtable's 'tags', so we don't
 382      * need a special case.
 383      */
 384     partition = (hmap_is_empty(&cls->partitions)
 385                  ? NULL
 386                  : find_partition(cls, flow->metadata,
 387                                   hash_metadata(flow->metadata)));
 388     tags = partition ? partition->tags : TAG_ARBITRARY;
 389
 390     best = NULL;
 391     LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
 392         struct cls_rule *rule;
 393
 394         if (!tag_intersects(tags, subtable->tag)) {
 395             continue;
 396         }
 397
 398         rule = find_match_wc(subtable, flow, wc);
 399         if (rule) {
 400             best = rule;
 401             LIST_FOR_EACH_CONTINUE (subtable, list_node,
 402                                     &cls->subtables_priority) {
 403                 if (subtable->max_priority <= best->priority) {
 404                     /* Subtables are in descending priority order,
 405                      * can not find anything better. */
 406                     return best;
 407                 }
 408                 if (!tag_intersects(tags, subtable->tag)) {
 409                     continue;
 410                 }
 411
 412                 rule = find_match_wc(subtable, flow, wc);
 413                 if (rule && rule->priority > best->priority) {
 414                     best = rule;
 415                 }
 416             }
 417             break;
 418         }
 419     }
 420     return best;
 421 }
 422
 423 /* Finds and returns a rule in 'cls' with exactly the same priority and
 424  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 425  * contain an exact match. */
 426 struct cls_rule *
 427 classifier_find_rule_exactly(const struct classifier *cls,
 428                              const struct cls_rule *target)
 429 {
 430     struct cls_rule *head, *rule;
 431     struct cls_subtable *subtable;
 432
 433     subtable = find_subtable(cls, &target->match.mask);
 434     if (!subtable) {
 435         return NULL;
 436     }
 437
 438     /* Skip if there is no hope. */
 439     if (target->priority > subtable->max_priority) {
 440         return NULL;
 441     }
 442
 443     head = find_equal(subtable, &target->match.flow,
 444                       miniflow_hash_in_minimask(&target->match.flow,
 445                                                 &target->match.mask, 0));
 446     FOR_EACH_RULE_IN_LIST (rule, head) {
 447         if (target->priority >= rule->priority) {
 448             return target->priority == rule->priority ? rule : NULL;
 449         }
 450     }
 451     return NULL;
 452 }
 453
 454 /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
 455  * same matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 456  * contain an exact match. */
 457 struct cls_rule *
 458 classifier_find_match_exactly(const struct classifier *cls,
 459                               const struct match *target,
 460                               unsigned int priority)
 461 {
 462     struct cls_rule *retval;
 463     struct cls_rule cr;
 464
 465     cls_rule_init(&cr, target, priority);
 466     retval = classifier_find_rule_exactly(cls, &cr);
 467     cls_rule_destroy(&cr);
 468
 469     return retval;
 470 }
 471
 472 /* Checks if 'target' would overlap any other rule in 'cls'.  Two rules are
 473  * considered to overlap if both rules have the same priority and a packet
 474  * could match both. */
 475 bool
 476 classifier_rule_overlaps(const struct classifier *cls,
 477                          const struct cls_rule *target)
 478 {
 479     struct cls_subtable *subtable;
 480
 481     /* Iterate subtables in the descending max priority order. */
 482     LIST_FOR_EACH (subtable, list_node, &cls->subtables_priority) {
 483         uint32_t storage[FLOW_U32S];
 484         struct minimask mask;
 485         struct cls_rule *head;
 486
 487         if (target->priority > subtable->max_priority) {
 488             break; /* Can skip this and the rest of the subtables. */
 489         }
 490
 491         minimask_combine(&mask, &target->match.mask, &subtable->mask, storage);
 492         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
 493             struct cls_rule *rule;
 494
 495             FOR_EACH_RULE_IN_LIST (rule, head) {
 496                 if (rule->priority < target->priority) {
 497                     break; /* Rules in descending priority order. */
 498                 }
 499                 if (rule->priority == target->priority
 500                     && miniflow_equal_in_minimask(&target->match.flow,
 501                                                   &rule->match.flow, &mask)) {
 502                     return true;
 503                 }
 504             }
 505         }
 506     }
 507
 508     return false;
 509 }
 510
 511 /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
 512  * specific than 'criteria'.  That is, 'rule' matches 'criteria' and this
 513  * function returns true if, for every field:
 514  *
 515  *   - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
 516  *     field, or
 517  *
 518  *   - 'criteria' wildcards the field,
 519  *
 520  * Conversely, 'rule' does not match 'criteria' and this function returns false
 521  * if, for at least one field:
 522  *
 523  *   - 'criteria' and 'rule' specify different values for the field, or
 524  *
 525  *   - 'criteria' specifies a value for the field but 'rule' wildcards it.
 526  *
 527  * Equivalently, the truth table for whether a field matches is:
 528  *
 529  *                                     rule
 530  *
 531  *                   c         wildcard    exact
 532  *                   r        +---------+---------+
 533  *                   i   wild |   yes   |   yes   |
 534  *                   t   card |         |         |
 535  *                   e        +---------+---------+
 536  *                   r  exact |    no   |if values|
 537  *                   i        |         |are equal|
 538  *                   a        +---------+---------+
 539  *
 540  * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
 541  * commands and by OpenFlow 1.0 aggregate and flow stats.
 542  *
 543  * Ignores rule->priority. */
 544 bool
 545 cls_rule_is_loose_match(const struct cls_rule *rule,
 546                         const struct minimatch *criteria)
 547 {
 548     return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
 549             && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
 550                                           &criteria->mask));
 551 }
 552 \f
 553 /* Iteration. */
 554
 555 static bool
 556 rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
 557 {
 558     return (!target
 559             || miniflow_equal_in_minimask(&rule->match.flow,
 560                                           &target->match.flow,
 561                                           &target->match.mask));
 562 }
 563
 564 static struct cls_rule *
 565 search_subtable(const struct cls_subtable *subtable,
 566                 const struct cls_rule *target)
 567 {
 568     if (!target || !minimask_has_extra(&subtable->mask, &target->match.mask)) {
 569         struct cls_rule *rule;
 570
 571         HMAP_FOR_EACH (rule, hmap_node, &subtable->rules) {
 572             if (rule_matches(rule, target)) {
 573                 return rule;
 574             }
 575         }
 576     }
 577     return NULL;
 578 }
 579
 580 /* Initializes 'cursor' for iterating through rules in 'cls':
 581  *
 582  *     - If 'target' is null, the cursor will visit every rule in 'cls'.
 583  *
 584  *     - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
 585  *       such that cls_rule_is_loose_match(rule, target) returns true.
 586  *
 587  * Ignores target->priority. */
 588 void
 589 cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
 590                 const struct cls_rule *target)
 591 {
 592     cursor->cls = cls;
 593     cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL;
 594 }
 595
 596 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
 597  * pointer if there are no matches. */
 598 struct cls_rule *
 599 cls_cursor_first(struct cls_cursor *cursor)
 600 {
 601     struct cls_subtable *subtable;
 602
 603     HMAP_FOR_EACH (subtable, hmap_node, &cursor->cls->subtables) {
 604         struct cls_rule *rule = search_subtable(subtable, cursor->target);
 605         if (rule) {
 606             cursor->subtable = subtable;
 607             return rule;
 608         }
 609     }
 610
 611     return NULL;
 612 }
 613
 614 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
 615  * pointer if there are no more matches. */
 616 struct cls_rule *
 617 cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_)
 618 {
 619     struct cls_rule *rule = CONST_CAST(struct cls_rule *, rule_);
 620     const struct cls_subtable *subtable;
 621     struct cls_rule *next;
 622
 623     next = next_rule_in_list__(rule);
 624     if (next->priority < rule->priority) {
 625         return next;
 626     }
 627
 628     /* 'next' is the head of the list, that is, the rule that is included in
 629      * the subtable's hmap.  (This is important when the classifier contains
 630      * rules that differ only in priority.) */
 631     rule = next;
 632     HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->subtable->rules) {
 633         if (rule_matches(rule, cursor->target)) {
 634             return rule;
 635         }
 636     }
 637
 638     subtable = cursor->subtable;
 639     HMAP_FOR_EACH_CONTINUE (subtable, hmap_node, &cursor->cls->subtables) {
 640         rule = search_subtable(subtable, cursor->target);
 641         if (rule) {
 642             cursor->subtable = subtable;
 643             return rule;
 644         }
 645     }
 646
 647     return NULL;
 648 }
 649 \f
 650 static struct cls_subtable *
 651 find_subtable(const struct classifier *cls, const struct minimask *mask)
 652 {
 653     struct cls_subtable *subtable;
 654
 655     HMAP_FOR_EACH_IN_BUCKET (subtable, hmap_node, minimask_hash(mask, 0),
 656                              &cls->subtables) {
 657         if (minimask_equal(mask, &subtable->mask)) {
 658             return subtable;
 659         }
 660     }
 661     return NULL;
 662 }
 663
 664 static struct cls_subtable *
 665 insert_subtable(struct classifier *cls, const struct minimask *mask)
 666 {
 667     uint32_t hash = minimask_hash(mask, 0);
 668     struct cls_subtable *subtable;
 669     int i, index = 0;
 670     struct flow_wildcards old, new;
 671     uint8_t prev;
 672
 673     subtable = xzalloc(sizeof *subtable);
 674     hmap_init(&subtable->rules);
 675     minimask_clone(&subtable->mask, mask);
 676
 677     /* Init indices for segmented lookup, if any. */
 678     flow_wildcards_init_catchall(&new);
 679     old = new;
 680     prev = 0;
 681     for (i = 0; i < cls->n_flow_segments; i++) {
 682         flow_wildcards_fold_minimask_range(&new, mask, prev,
 683                                            cls->flow_segments[i]);
 684         /* Add an index if it adds mask bits. */
 685         if (!flow_wildcards_equal(&new, &old)) {
 686             hindex_init(&subtable->indices[index]);
 687             subtable->index_ofs[index] = cls->flow_segments[i];
 688             index++;
 689             old = new;
 690         }
 691         prev = cls->flow_segments[i];
 692     }
 693     /* Check if the rest of the subtable's mask adds any bits,
 694      * and remove the last index if it doesn't. */
 695     if (index > 0) {
 696         flow_wildcards_fold_minimask_range(&new, mask, prev, FLOW_U32S);
 697         if (flow_wildcards_equal(&new, &old)) {
 698             --index;
 699             subtable->index_ofs[index] = 0;
 700             hindex_destroy(&subtable->indices[index]);
 701         }
 702     }
 703     subtable->n_indices = index;
 704
 705     hmap_insert(&cls->subtables, &subtable->hmap_node, hash);
 706     list_push_back(&cls->subtables_priority, &subtable->list_node);
 707     subtable->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX
 708                      ? tag_create_deterministic(hash)
 709                      : TAG_ALL);
 710
 711     return subtable;
 712 }
 713
 714 static void
 715 destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
 716 {
 717     int i;
 718
 719     for (i = 0; i < subtable->n_indices; i++) {
 720         hindex_destroy(&subtable->indices[i]);
 721     }
 722     minimask_destroy(&subtable->mask);
 723     hmap_remove(&cls->subtables, &subtable->hmap_node);
 724     hmap_destroy(&subtable->rules);
 725     list_remove(&subtable->list_node);
 726     free(subtable);
 727 }
 728
 729 /* This function performs the following updates for 'subtable' in 'cls'
 730  * following the addition of a new rule with priority 'new_priority' to
 731  * 'subtable':
 732  *
 733  *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
 734  *
 735  *    - Update 'subtable''s position in 'cls->subtables_priority' if necessary.
 736  *
 737  * This function should only be called after adding a new rule, not after
 738  * replacing a rule by an identical one or modifying a rule in-place. */
 739 static void
 740 update_subtables_after_insertion(struct classifier *cls,
 741                                  struct cls_subtable *subtable,
 742                                  unsigned int new_priority)
 743 {
 744     if (new_priority == subtable->max_priority) {
 745         ++subtable->max_count;
 746     } else if (new_priority > subtable->max_priority) {
 747         struct cls_subtable *iter;
 748
 749         subtable->max_priority = new_priority;
 750         subtable->max_count = 1;
 751
 752         /* Possibly move 'subtable' earlier in the priority list.  If we break
 753          * out of the loop, then 'subtable' should be moved just after that
 754          * 'iter'.  If the loop terminates normally, then 'iter' will be the
 755          * list head and we'll move subtable just after that (e.g. to the front
 756          * of the list). */
 757         iter = subtable;
 758         LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node,
 759                                         &cls->subtables_priority) {
 760             if (iter->max_priority >= subtable->max_priority) {
 761                 break;
 762             }
 763         }
 764
 765         /* Move 'subtable' just after 'iter' (unless it's already there). */
 766         if (iter->list_node.next != &subtable->list_node) {
 767             list_splice(iter->list_node.next,
 768                         &subtable->list_node, subtable->list_node.next);
 769         }
 770     }
 771 }
 772
 773 /* This function performs the following updates for 'subtable' in 'cls'
 774  * following the deletion of a rule with priority 'del_priority' from
 775  * 'subtable':
 776  *
 777  *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
 778  *
 779  *    - Update 'subtable''s position in 'cls->subtables_priority' if necessary.
 780  *
 781  * This function should only be called after removing a rule, not after
 782  * replacing a rule by an identical one or modifying a rule in-place. */
 783 static void
 784 update_subtables_after_removal(struct classifier *cls,
 785                                struct cls_subtable *subtable,
 786                                unsigned int del_priority)
 787 {
 788     struct cls_subtable *iter;
 789
 790     if (del_priority == subtable->max_priority && --subtable->max_count == 0) {
 791         struct cls_rule *head;
 792
 793         subtable->max_priority = 0;
 794         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
 795             if (head->priority > subtable->max_priority) {
 796                 subtable->max_priority = head->priority;
 797                 subtable->max_count = 1;
 798             } else if (head->priority == subtable->max_priority) {
 799                 ++subtable->max_count;
 800             }
 801         }
 802
 803         /* Possibly move 'subtable' later in the priority list.  If we break
 804          * out of the loop, then 'subtable' should be moved just before that
 805          * 'iter'.  If the loop terminates normally, then 'iter' will be the
 806          * list head and we'll move subtable just before that (e.g. to the back
 807          * of the list). */
 808         iter = subtable;
 809         LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->subtables_priority) {
 810             if (iter->max_priority <= subtable->max_priority) {
 811                 break;
 812             }
 813         }
 814
 815         /* Move 'subtable' just before 'iter' (unless it's already there). */
 816         if (iter->list_node.prev != &subtable->list_node) {
 817             list_splice(&iter->list_node,
 818                         &subtable->list_node, subtable->list_node.next);
 819         }
 820     }
 821 }
 822
 823 static inline struct cls_rule *
 824 find_match(const struct cls_subtable *subtable, const struct flow *flow,
 825            uint32_t hash)
 826 {
 827     struct cls_rule *rule;
 828
 829     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
 830         if (minimatch_matches_flow(&rule->match, flow)) {
 831             return rule;
 832         }
 833     }
 834
 835     return NULL;
 836 }
 837
 838 static struct cls_rule *
 839 find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
 840               struct flow_wildcards * wc)
 841 {
 842     uint32_t basis = 0, hash;
 843     struct cls_rule *rule = NULL;
 844     uint8_t prev_u32ofs = 0;
 845     int i;
 846
 847     if (!wc) {
 848         return find_match(subtable, flow,
 849                           flow_hash_in_minimask(flow, &subtable->mask, 0));
 850     }
 851
 852     /* Try to finish early by checking fields in segments. */
 853     for (i = 0; i < subtable->n_indices; i++) {
 854         struct hindex_node *inode;
 855
 856         hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
 857                                            subtable->index_ofs[i], &basis);
 858         prev_u32ofs = subtable->index_ofs[i];
 859         inode = hindex_node_with_hash(&subtable->indices[i], hash);
 860         if (!inode) {
 861             /* No match, can stop immediately, but must fold in the mask
 862              * covered so far. */
 863             flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0,
 864                                                prev_u32ofs);
 865             return NULL;
 866         }
 867
 868         /* If we have narrowed down to a single rule already, check whether
 869          * that rule matches.  If it does match, then we're done.  If it does
 870          * not match, then we know that we will never get a match, but we do
 871          * not yet know how many wildcards we need to fold into 'wc' so we
 872          * continue iterating through indices to find that out.  (We won't
 873          * waste time calling minimatch_matches_flow() again because we've set
 874          * 'rule' nonnull.)
 875          *
 876          * This check shows a measurable benefit with non-trivial flow tables.
 877          *
 878          * (Rare) hash collisions may cause us to miss the opportunity for this
 879          * optimization. */
 880         if (!inode->s && !rule) {
 881             ASSIGN_CONTAINER(rule, inode - i, index_nodes);
 882             if (minimatch_matches_flow(&rule->match, flow)) {
 883                 goto out;
 884             }
 885         }
 886     }
 887
 888     if (!rule) {
 889         /* Multiple potential matches exist, look for one. */
 890         hash = flow_hash_in_minimask_range(flow, &subtable->mask, prev_u32ofs,
 891                                            FLOW_U32S, &basis);
 892         rule = find_match(subtable, flow, hash);
 893     } else {
 894         /* We already narrowed the matching candidates down to just 'rule',
 895          * but it didn't match. */
 896         rule = NULL;
 897     }
 898  out:
 899     flow_wildcards_fold_minimask(wc, &subtable->mask);
 900     return rule;
 901 }
 902
 903 static struct cls_rule *
 904 find_equal(struct cls_subtable *subtable, const struct miniflow *flow,
 905            uint32_t hash)
 906 {
 907     struct cls_rule *head;
 908
 909     HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &subtable->rules) {
 910         if (miniflow_equal(&head->match.flow, flow)) {
 911             return head;
 912         }
 913     }
 914     return NULL;
 915 }
 916
 917 static struct cls_rule *
 918 insert_rule(struct classifier *cls, struct cls_subtable *subtable,
 919             struct cls_rule *new)
 920 {
 921     struct cls_rule *head;
 922     struct cls_rule *old = NULL;
 923     int i;
 924     uint32_t basis = 0, hash;
 925     uint8_t prev_u32ofs = 0;
 926
 927     /* Add new node to segment indices. */
 928     for (i = 0; i < subtable->n_indices; i++) {
 929         hash = minimatch_hash_range(&new->match, prev_u32ofs,
 930                                     subtable->index_ofs[i], &basis);
 931         hindex_insert(&subtable->indices[i], &new->index_nodes[i], hash);
 932         prev_u32ofs = subtable->index_ofs[i];
 933     }
 934     hash = minimatch_hash_range(&new->match, prev_u32ofs, FLOW_U32S, &basis);
 935     head = find_equal(subtable, &new->match.flow, hash);
 936     if (!head) {
 937         hmap_insert(&subtable->rules, &new->hmap_node, hash);
 938         list_init(&new->list);
 939         goto out;
 940     } else {
 941         /* Scan the list for the insertion point that will keep the list in
 942          * order of decreasing priority. */
 943         struct cls_rule *rule;
 944
 945         new->hmap_node.hash = hash; /* Otherwise done by hmap_insert. */
 946
 947         FOR_EACH_RULE_IN_LIST (rule, head) {
 948             if (new->priority >= rule->priority) {
 949                 if (rule == head) {
 950                     /* 'new' is the new highest-priority flow in the list. */
 951                     hmap_replace(&subtable->rules,
 952                                  &rule->hmap_node, &new->hmap_node);
 953                 }
 954
 955                 if (new->priority == rule->priority) {
 956                     list_replace(&new->list, &rule->list);
 957                     old = rule;
 958                     goto out;
 959                 } else {
 960                     list_insert(&rule->list, &new->list);
 961                     goto out;
 962                 }
 963             }
 964         }
 965
 966         /* Insert 'new' at the end of the list. */
 967         list_push_back(&head->list, &new->list);
 968     }
 969
 970  out:
 971     if (!old) {
 972         update_subtables_after_insertion(cls, subtable, new->priority);
 973     } else {
 974         /* Remove old node from indices. */
 975         for (i = 0; i < subtable->n_indices; i++) {
 976             hindex_remove(&subtable->indices[i], &old->index_nodes[i]);
 977         }
 978     }
 979     return old;
 980 }
 981
 982 static struct cls_rule *
 983 next_rule_in_list__(struct cls_rule *rule)
 984 {
 985     struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list);
 986     return next;
 987 }
 988
 989 static struct cls_rule *
 990 next_rule_in_list(struct cls_rule *rule)
 991 {
 992     struct cls_rule *next = next_rule_in_list__(rule);
 993     return next->priority < rule->priority ? next : NULL;
 994 }