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         tag_tracker_init(&partition->tracker);
 231         hmap_insert(&cls->partitions, &partition->hmap_node, hash);
 232     }
 233     tag_tracker_add(&partition->tracker, &partition->tags, table->tag);
 234     return partition;
 235 }
 236
 237 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 238  * must not modify or free it.
 239  *
 240  * If 'cls' already contains an identical rule (including wildcards, values of
 241  * fixed fields, and priority), replaces the old rule by 'rule' and returns the
 242  * rule that was replaced.  The caller takes ownership of the returned rule and
 243  * is thus responsible for destroying it with cls_rule_destroy(), freeing the
 244  * memory block in which it resides, etc., as necessary.
 245  *
 246  * Returns NULL if 'cls' does not contain a rule with an identical key, after
 247  * inserting the new rule.  In this case, no rules are displaced by the new
 248  * rule, even rules that cannot have any effect because the new rule matches a
 249  * superset of their flows and has higher priority. */
 250 struct cls_rule *
 251 classifier_replace(struct classifier *cls, struct cls_rule *rule)
 252 {
 253     struct cls_rule *old_rule;
 254     struct cls_table *table;
 255
 256     table = find_table(cls, &rule->match.mask);
 257     if (!table) {
 258         table = insert_table(cls, &rule->match.mask);
 259     }
 260
 261     old_rule = insert_rule(cls, table, rule);
 262     if (!old_rule) {
 263         if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
 264             ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
 265             rule->partition = create_partition(cls, table, metadata);
 266         } else {
 267             rule->partition = NULL;
 268         }
 269
 270         table->n_table_rules++;
 271         cls->n_rules++;
 272     } else {
 273         rule->partition = old_rule->partition;
 274     }
 275     return old_rule;
 276 }
 277
 278 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 279  * must not modify or free it.
 280  *
 281  * 'cls' must not contain an identical rule (including wildcards, values of
 282  * fixed fields, and priority).  Use classifier_find_rule_exactly() to find
 283  * such a rule. */
 284 void
 285 classifier_insert(struct classifier *cls, struct cls_rule *rule)
 286 {
 287     struct cls_rule *displaced_rule = classifier_replace(cls, rule);
 288     ovs_assert(!displaced_rule);
 289 }
 290
 291 /* Removes 'rule' from 'cls'.  It is the caller's responsibility to destroy
 292  * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule'
 293  * resides, etc., as necessary. */
 294 void
 295 classifier_remove(struct classifier *cls, struct cls_rule *rule)
 296 {
 297     struct cls_partition *partition;
 298     struct cls_rule *head;
 299     struct cls_table *table;
 300
 301     table = find_table(cls, &rule->match.mask);
 302     head = find_equal(table, &rule->match.flow, rule->hmap_node.hash);
 303     if (head != rule) {
 304         list_remove(&rule->list);
 305     } else if (list_is_empty(&rule->list)) {
 306         hmap_remove(&table->rules, &rule->hmap_node);
 307     } else {
 308         struct cls_rule *next = CONTAINER_OF(rule->list.next,
 309                                              struct cls_rule, list);
 310
 311         list_remove(&rule->list);
 312         hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node);
 313     }
 314
 315     partition = rule->partition;
 316     if (partition) {
 317         tag_tracker_subtract(&partition->tracker, &partition->tags,
 318                              table->tag);
 319         if (!partition->tags) {
 320             hmap_remove(&cls->partitions, &partition->hmap_node);
 321             free(partition);
 322         }
 323     }
 324
 325     if (--table->n_table_rules == 0) {
 326         destroy_table(cls, table);
 327     } else {
 328         update_tables_after_removal(cls, table, rule->priority);
 329     }
 330     cls->n_rules--;
 331 }
 332
 333 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
 334  * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
 335  * of equal priority match 'flow', returns one arbitrarily.
 336  *
 337  * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
 338  * set of bits that were significant in the lookup.  At some point
 339  * earlier, 'wc' should have been initialized (e.g., by
 340  * flow_wildcards_init_catchall()). */
 341 struct cls_rule *
 342 classifier_lookup(const struct classifier *cls, const struct flow *flow,
 343                   struct flow_wildcards *wc)
 344 {
 345     const struct cls_partition *partition;
 346     struct cls_table *table;
 347     struct cls_rule *best;
 348     tag_type tags;
 349
 350     /* Determine 'tags' such that, if 'table->tag' doesn't intersect them, then
 351      * 'flow' cannot possibly match in 'table':
 352      *
 353      *     - If flow->metadata maps to a given 'partition', then we can use
 354      *       'tags' for 'partition->tags'.
 355      *
 356      *     - If flow->metadata has no partition, then no rule in 'cls' has an
 357      *       exact-match for flow->metadata.  That means that we don't need to
 358      *       search any table that includes flow->metadata in its mask.
 359      *
 360      * In either case, we always need to search any cls_tables that do not
 361      * include flow->metadata in its mask.  One way to do that would be to
 362      * check the "cls_table"s explicitly for that, but that would require an
 363      * extra branch per table.  Instead, we mark such a cls_table's 'tags' as
 364      * TAG_ALL and make sure that 'tags' is never empty.  This means that
 365      * 'tags' always intersects such a cls_table's 'tags', so we don't need a
 366      * special case.
 367      */
 368     partition = (hmap_is_empty(&cls->partitions)
 369                  ? NULL
 370                  : find_partition(cls, flow->metadata,
 371                                   hash_metadata(flow->metadata)));
 372     tags = partition ? partition->tags : TAG_ARBITRARY;
 373
 374     best = NULL;
 375     LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
 376         struct cls_rule *rule;
 377
 378         if (!tag_intersects(tags, table->tag)) {
 379             continue;
 380         }
 381
 382         rule = find_match(table, flow);
 383         if (wc) {
 384             flow_wildcards_fold_minimask(wc, &table->mask);
 385         }
 386         if (rule) {
 387             best = rule;
 388             LIST_FOR_EACH_CONTINUE (table, list_node, &cls->tables_priority) {
 389                 if (table->max_priority <= best->priority) {
 390                     /* Tables in descending priority order,
 391                      * can not find anything better. */
 392                     return best;
 393                 }
 394                 if (!tag_intersects(tags, table->tag)) {
 395                     continue;
 396                 }
 397
 398                 rule = find_match(table, flow);
 399                 if (wc) {
 400                     flow_wildcards_fold_minimask(wc, &table->mask);
 401                 }
 402                 if (rule && rule->priority > best->priority) {
 403                     best = rule;
 404                 }
 405             }
 406             break;
 407         }
 408     }
 409     return best;
 410 }
 411
 412 /* Finds and returns a rule in 'cls' with exactly the same priority and
 413  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 414  * contain an exact match. */
 415 struct cls_rule *
 416 classifier_find_rule_exactly(const struct classifier *cls,
 417                              const struct cls_rule *target)
 418 {
 419     struct cls_rule *head, *rule;
 420     struct cls_table *table;
 421
 422     table = find_table(cls, &target->match.mask);
 423     if (!table) {
 424         return NULL;
 425     }
 426
 427     /* Skip if there is no hope. */
 428     if (target->priority > table->max_priority) {
 429         return NULL;
 430     }
 431
 432     head = find_equal(table, &target->match.flow,
 433                       miniflow_hash_in_minimask(&target->match.flow,
 434                                                 &target->match.mask, 0));
 435     FOR_EACH_RULE_IN_LIST (rule, head) {
 436         if (target->priority >= rule->priority) {
 437             return target->priority == rule->priority ? rule : NULL;
 438         }
 439     }
 440     return NULL;
 441 }
 442
 443 /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
 444  * same matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 445  * contain an exact match. */
 446 struct cls_rule *
 447 classifier_find_match_exactly(const struct classifier *cls,
 448                               const struct match *target,
 449                               unsigned int priority)
 450 {
 451     struct cls_rule *retval;
 452     struct cls_rule cr;
 453
 454     cls_rule_init(&cr, target, priority);
 455     retval = classifier_find_rule_exactly(cls, &cr);
 456     cls_rule_destroy(&cr);
 457
 458     return retval;
 459 }
 460
 461 /* Checks if 'target' would overlap any other rule in 'cls'.  Two rules are
 462  * considered to overlap if both rules have the same priority and a packet
 463  * could match both. */
 464 bool
 465 classifier_rule_overlaps(const struct classifier *cls,
 466                          const struct cls_rule *target)
 467 {
 468     struct cls_table *table;
 469
 470     /* Iterate tables in the descending max priority order. */
 471     LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
 472         uint32_t storage[FLOW_U32S];
 473         struct minimask mask;
 474         struct cls_rule *head;
 475
 476         if (target->priority > table->max_priority) {
 477             break; /* Can skip this and the rest of the tables. */
 478         }
 479
 480         minimask_combine(&mask, &target->match.mask, &table->mask, storage);
 481         HMAP_FOR_EACH (head, hmap_node, &table->rules) {
 482             struct cls_rule *rule;
 483
 484             FOR_EACH_RULE_IN_LIST (rule, head) {
 485                 if (rule->priority < target->priority) {
 486                     break; /* Rules in descending priority order. */
 487                 }
 488                 if (rule->priority == target->priority
 489                     && miniflow_equal_in_minimask(&target->match.flow,
 490                                                   &rule->match.flow, &mask)) {
 491                     return true;
 492                 }
 493             }
 494         }
 495     }
 496
 497     return false;
 498 }
 499
 500 /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
 501  * specific than 'criteria'.  That is, 'rule' matches 'criteria' and this
 502  * function returns true if, for every field:
 503  *
 504  *   - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
 505  *     field, or
 506  *
 507  *   - 'criteria' wildcards the field,
 508  *
 509  * Conversely, 'rule' does not match 'criteria' and this function returns false
 510  * if, for at least one field:
 511  *
 512  *   - 'criteria' and 'rule' specify different values for the field, or
 513  *
 514  *   - 'criteria' specifies a value for the field but 'rule' wildcards it.
 515  *
 516  * Equivalently, the truth table for whether a field matches is:
 517  *
 518  *                                     rule
 519  *
 520  *                   c         wildcard    exact
 521  *                   r        +---------+---------+
 522  *                   i   wild |   yes   |   yes   |
 523  *                   t   card |         |         |
 524  *                   e        +---------+---------+
 525  *                   r  exact |    no   |if values|
 526  *                   i        |         |are equal|
 527  *                   a        +---------+---------+
 528  *
 529  * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
 530  * commands and by OpenFlow 1.0 aggregate and flow stats.
 531  *
 532  * Ignores rule->priority. */
 533 bool
 534 cls_rule_is_loose_match(const struct cls_rule *rule,
 535                         const struct minimatch *criteria)
 536 {
 537     return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
 538             && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
 539                                           &criteria->mask));
 540 }
 541 \f
 542 /* Iteration. */
 543
 544 static bool
 545 rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
 546 {
 547     return (!target
 548             || miniflow_equal_in_minimask(&rule->match.flow,
 549                                           &target->match.flow,
 550                                           &target->match.mask));
 551 }
 552
 553 static struct cls_rule *
 554 search_table(const struct cls_table *table, const struct cls_rule *target)
 555 {
 556     if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) {
 557         struct cls_rule *rule;
 558
 559         HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
 560             if (rule_matches(rule, target)) {
 561                 return rule;
 562             }
 563         }
 564     }
 565     return NULL;
 566 }
 567
 568 /* Initializes 'cursor' for iterating through rules in 'cls':
 569  *
 570  *     - If 'target' is null, the cursor will visit every rule in 'cls'.
 571  *
 572  *     - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
 573  *       such that cls_rule_is_loose_match(rule, target) returns true.
 574  *
 575  * Ignores target->priority. */
 576 void
 577 cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
 578                 const struct cls_rule *target)
 579 {
 580     cursor->cls = cls;
 581     cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL;
 582 }
 583
 584 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
 585  * pointer if there are no matches. */
 586 struct cls_rule *
 587 cls_cursor_first(struct cls_cursor *cursor)
 588 {
 589     struct cls_table *table;
 590
 591     HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) {
 592         struct cls_rule *rule = search_table(table, cursor->target);
 593         if (rule) {
 594             cursor->table = table;
 595             return rule;
 596         }
 597     }
 598
 599     return NULL;
 600 }
 601
 602 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
 603  * pointer if there are no more matches. */
 604 struct cls_rule *
 605 cls_cursor_next(struct cls_cursor *cursor, const struct cls_rule *rule_)
 606 {
 607     struct cls_rule *rule = CONST_CAST(struct cls_rule *, rule_);
 608     const struct cls_table *table;
 609     struct cls_rule *next;
 610
 611     next = next_rule_in_list__(rule);
 612     if (next->priority < rule->priority) {
 613         return next;
 614     }
 615
 616     /* 'next' is the head of the list, that is, the rule that is included in
 617      * the table's hmap.  (This is important when the classifier contains rules
 618      * that differ only in priority.) */
 619     rule = next;
 620     HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) {
 621         if (rule_matches(rule, cursor->target)) {
 622             return rule;
 623         }
 624     }
 625
 626     table = cursor->table;
 627     HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) {
 628         rule = search_table(table, cursor->target);
 629         if (rule) {
 630             cursor->table = table;
 631             return rule;
 632         }
 633     }
 634
 635     return NULL;
 636 }
 637 \f
 638 static struct cls_table *
 639 find_table(const struct classifier *cls, const struct minimask *mask)
 640 {
 641     struct cls_table *table;
 642
 643     HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0),
 644                              &cls->tables) {
 645         if (minimask_equal(mask, &table->mask)) {
 646             return table;
 647         }
 648     }
 649     return NULL;
 650 }
 651
 652 static struct cls_table *
 653 insert_table(struct classifier *cls, const struct minimask *mask)
 654 {
 655     uint32_t hash = minimask_hash(mask, 0);
 656     struct cls_table *table;
 657
 658     table = xzalloc(sizeof *table);
 659     hmap_init(&table->rules);
 660     minimask_clone(&table->mask, mask);
 661     hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0));
 662     list_push_back(&cls->tables_priority, &table->list_node);
 663     table->tag = (minimask_get_metadata_mask(mask) == OVS_BE64_MAX
 664                   ? tag_create_deterministic(hash)
 665                   : TAG_ALL);
 666
 667     return table;
 668 }
 669
 670 static void
 671 destroy_table(struct classifier *cls, struct cls_table *table)
 672 {
 673     minimask_destroy(&table->mask);
 674     hmap_remove(&cls->tables, &table->hmap_node);
 675     hmap_destroy(&table->rules);
 676     list_remove(&table->list_node);
 677     free(table);
 678 }
 679
 680 /* This function performs the following updates for 'table' in 'cls' following
 681  * the addition of a new rule with priority 'new_priority' to 'table':
 682  *
 683  *    - Update 'table->max_priority' and 'table->max_count' if necessary.
 684  *
 685  *    - Update 'table''s position in 'cls->tables_priority' if necessary.
 686  *
 687  * This function should only be called after adding a new rule, not after
 688  * replacing a rule by an identical one or modifying a rule in-place. */
 689 static void
 690 update_tables_after_insertion(struct classifier *cls, struct cls_table *table,
 691                               unsigned int new_priority)
 692 {
 693     if (new_priority == table->max_priority) {
 694         ++table->max_count;
 695     } else if (new_priority > table->max_priority) {
 696         struct cls_table *iter;
 697
 698         table->max_priority = new_priority;
 699         table->max_count = 1;
 700
 701         /* Possibly move 'table' earlier in the priority list.  If we break out
 702          * of the loop, then 'table' should be moved just after that 'iter'.
 703          * If the loop terminates normally, then 'iter' will be the list head
 704          * and we'll move table just after that (e.g. to the front of the
 705          * list). */
 706         iter = table;
 707         LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node,
 708                                         &cls->tables_priority) {
 709             if (iter->max_priority >= table->max_priority) {
 710                 break;
 711             }
 712         }
 713
 714         /* Move 'table' just after 'iter' (unless it's already there). */
 715         if (iter->list_node.next != &table->list_node) {
 716             list_splice(iter->list_node.next,
 717                         &table->list_node, table->list_node.next);
 718         }
 719     }
 720 }
 721
 722 /* This function performs the following updates for 'table' in 'cls' following
 723  * the deletion of a rule with priority 'del_priority' from 'table':
 724  *
 725  *    - Update 'table->max_priority' and 'table->max_count' if necessary.
 726  *
 727  *    - Update 'table''s position in 'cls->tables_priority' if necessary.
 728  *
 729  * This function should only be called after removing a rule, not after
 730  * replacing a rule by an identical one or modifying a rule in-place. */
 731 static void
 732 update_tables_after_removal(struct classifier *cls, struct cls_table *table,
 733                             unsigned int del_priority)
 734 {
 735     struct cls_table *iter;
 736
 737     if (del_priority == table->max_priority && --table->max_count == 0) {
 738         struct cls_rule *head;
 739
 740         table->max_priority = 0;
 741         HMAP_FOR_EACH (head, hmap_node, &table->rules) {
 742             if (head->priority > table->max_priority) {
 743                 table->max_priority = head->priority;
 744                 table->max_count = 1;
 745             } else if (head->priority == table->max_priority) {
 746                 ++table->max_count;
 747             }
 748         }
 749
 750         /* Possibly move 'table' later in the priority list.  If we break out
 751          * of the loop, then 'table' should be moved just before that 'iter'.
 752          * If the loop terminates normally, then 'iter' will be the list head
 753          * and we'll move table just before that (e.g. to the back of the
 754          * list). */
 755         iter = table;
 756         LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) {
 757             if (iter->max_priority <= table->max_priority) {
 758                 break;
 759             }
 760         }
 761
 762         /* Move 'table' just before 'iter' (unless it's already there). */
 763         if (iter->list_node.prev != &table->list_node) {
 764             list_splice(&iter->list_node,
 765                         &table->list_node, table->list_node.next);
 766         }
 767     }
 768 }
 769
 770 static struct cls_rule *
 771 find_match(const struct cls_table *table, const struct flow *flow)
 772 {
 773     uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0);
 774     struct cls_rule *rule;
 775
 776     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) {
 777         if (minimatch_matches_flow(&rule->match, flow)) {
 778             return rule;
 779         }
 780     }
 781
 782     return NULL;
 783 }
 784
 785 static struct cls_rule *
 786 find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash)
 787 {
 788     struct cls_rule *head;
 789
 790     HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) {
 791         if (miniflow_equal(&head->match.flow, flow)) {
 792             return head;
 793         }
 794     }
 795     return NULL;
 796 }
 797
 798 static struct cls_rule *
 799 insert_rule(struct classifier *cls,
 800             struct cls_table *table, struct cls_rule *new)
 801 {
 802     struct cls_rule *head;
 803     struct cls_rule *old = NULL;
 804
 805     new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow,
 806                                                     &new->match.mask, 0);
 807
 808     head = find_equal(table, &new->match.flow, new->hmap_node.hash);
 809     if (!head) {
 810         hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash);
 811         list_init(&new->list);
 812         goto out;
 813     } else {
 814         /* Scan the list for the insertion point that will keep the list in
 815          * order of decreasing priority. */
 816         struct cls_rule *rule;
 817         FOR_EACH_RULE_IN_LIST (rule, head) {
 818             if (new->priority >= rule->priority) {
 819                 if (rule == head) {
 820                     /* 'new' is the new highest-priority flow in the list. */
 821                     hmap_replace(&table->rules,
 822                                  &rule->hmap_node, &new->hmap_node);
 823                 }
 824
 825                 if (new->priority == rule->priority) {
 826                     list_replace(&new->list, &rule->list);
 827                     old = rule;
 828                     goto out;
 829                 } else {
 830                     list_insert(&rule->list, &new->list);
 831                     goto out;
 832                 }
 833             }
 834         }
 835
 836         /* Insert 'new' at the end of the list. */
 837         list_push_back(&head->list, &new->list);
 838     }
 839
 840  out:
 841     if (!old) {
 842         update_tables_after_insertion(cls, table, new->priority);
 843     }
 844     return old;
 845 }
 846
 847 static struct cls_rule *
 848 next_rule_in_list__(struct cls_rule *rule)
 849 {
 850     struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list);
 851     return next;
 852 }
 853
 854 static struct cls_rule *
 855 next_rule_in_list(struct cls_rule *rule)
 856 {
 857     struct cls_rule *next = next_rule_in_list__(rule);
 858     return next->priority < rule->priority ? next : NULL;
 859 }