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