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