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  *
 257  * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
 258  * set of bits that were significant in the lookup.  At some point
 259  * earlier, 'wc' should have been initialized (e.g., by
 260  * flow_wildcards_init_catchall()). */
 261 struct cls_rule *
 262 classifier_lookup(const struct classifier *cls, const struct flow *flow,
 263                   struct flow_wildcards *wc)
 264 {
 265     struct cls_table *table;
 266     struct cls_rule *best;
 267
 268     best = NULL;
 269     LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
 270         struct cls_rule *rule = find_match(table, flow);
 271
 272         if (wc) {
 273             flow_wildcards_fold_minimask(wc, &table->mask);
 274         }
 275         if (rule) {
 276             best = rule;
 277             LIST_FOR_EACH_CONTINUE (table, list_node, &cls->tables_priority) {
 278                 if (table->max_priority <= best->priority) {
 279                     /* Tables in descending priority order,
 280                      * can not find anything better. */
 281                     return best;
 282                 }
 283                 rule = find_match(table, flow);
 284                 if (wc) {
 285                     flow_wildcards_fold_minimask(wc, &table->mask);
 286                 }
 287                 if (rule && rule->priority > best->priority) {
 288                     best = rule;
 289                 }
 290             }
 291             break;
 292         }
 293     }
 294     return best;
 295 }
 296
 297 /* Finds and returns a rule in 'cls' with exactly the same priority and
 298  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 299  * contain an exact match. */
 300 struct cls_rule *
 301 classifier_find_rule_exactly(const struct classifier *cls,
 302                              const struct cls_rule *target)
 303 {
 304     struct cls_rule *head, *rule;
 305     struct cls_table *table;
 306
 307     table = find_table(cls, &target->match.mask);
 308     if (!table) {
 309         return NULL;
 310     }
 311
 312     /* Skip if there is no hope. */
 313     if (target->priority > table->max_priority) {
 314         return NULL;
 315     }
 316
 317     head = find_equal(table, &target->match.flow,
 318                       miniflow_hash_in_minimask(&target->match.flow,
 319                                                 &target->match.mask, 0));
 320     FOR_EACH_RULE_IN_LIST (rule, head) {
 321         if (target->priority >= rule->priority) {
 322             return target->priority == rule->priority ? rule : NULL;
 323         }
 324     }
 325     return NULL;
 326 }
 327
 328 /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
 329  * same matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 330  * contain an exact match. */
 331 struct cls_rule *
 332 classifier_find_match_exactly(const struct classifier *cls,
 333                               const struct match *target,
 334                               unsigned int priority)
 335 {
 336     struct cls_rule *retval;
 337     struct cls_rule cr;
 338
 339     cls_rule_init(&cr, target, priority);
 340     retval = classifier_find_rule_exactly(cls, &cr);
 341     cls_rule_destroy(&cr);
 342
 343     return retval;
 344 }
 345
 346 /* Checks if 'target' would overlap any other rule in 'cls'.  Two rules are
 347  * considered to overlap if both rules have the same priority and a packet
 348  * could match both. */
 349 bool
 350 classifier_rule_overlaps(const struct classifier *cls,
 351                          const struct cls_rule *target)
 352 {
 353     struct cls_table *table;
 354
 355     /* Iterate tables in the descending max priority order. */
 356     LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
 357         uint32_t storage[FLOW_U32S];
 358         struct minimask mask;
 359         struct cls_rule *head;
 360
 361         if (target->priority > table->max_priority) {
 362             break; /* Can skip this and the rest of the tables. */
 363         }
 364
 365         minimask_combine(&mask, &target->match.mask, &table->mask, storage);
 366         HMAP_FOR_EACH (head, hmap_node, &table->rules) {
 367             struct cls_rule *rule;
 368
 369             FOR_EACH_RULE_IN_LIST (rule, head) {
 370                 if (rule->priority < target->priority) {
 371                     break; /* Rules in descending priority order. */
 372                 }
 373                 if (rule->priority == target->priority
 374                     && miniflow_equal_in_minimask(&target->match.flow,
 375                                                   &rule->match.flow, &mask)) {
 376                     return true;
 377                 }
 378             }
 379         }
 380     }
 381
 382     return false;
 383 }
 384
 385 /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
 386  * specific than 'criteria'.  That is, 'rule' matches 'criteria' and this
 387  * function returns true if, for every field:
 388  *
 389  *   - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
 390  *     field, or
 391  *
 392  *   - 'criteria' wildcards the field,
 393  *
 394  * Conversely, 'rule' does not match 'criteria' and this function returns false
 395  * if, for at least one field:
 396  *
 397  *   - 'criteria' and 'rule' specify different values for the field, or
 398  *
 399  *   - 'criteria' specifies a value for the field but 'rule' wildcards it.
 400  *
 401  * Equivalently, the truth table for whether a field matches is:
 402  *
 403  *                                     rule
 404  *
 405  *                   c         wildcard    exact
 406  *                   r        +---------+---------+
 407  *                   i   wild |   yes   |   yes   |
 408  *                   t   card |         |         |
 409  *                   e        +---------+---------+
 410  *                   r  exact |    no   |if values|
 411  *                   i        |         |are equal|
 412  *                   a        +---------+---------+
 413  *
 414  * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
 415  * commands and by OpenFlow 1.0 aggregate and flow stats.
 416  *
 417  * Ignores rule->priority. */
 418 bool
 419 cls_rule_is_loose_match(const struct cls_rule *rule,
 420                         const struct minimatch *criteria)
 421 {
 422     return (!minimask_has_extra(&rule->match.mask, &criteria->mask)
 423             && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow,
 424                                           &criteria->mask));
 425 }
 426 \f
 427 /* Iteration. */
 428
 429 static bool
 430 rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
 431 {
 432     return (!target
 433             || miniflow_equal_in_minimask(&rule->match.flow,
 434                                           &target->match.flow,
 435                                           &target->match.mask));
 436 }
 437
 438 static struct cls_rule *
 439 search_table(const struct cls_table *table, const struct cls_rule *target)
 440 {
 441     if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) {
 442         struct cls_rule *rule;
 443
 444         HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
 445             if (rule_matches(rule, target)) {
 446                 return rule;
 447             }
 448         }
 449     }
 450     return NULL;
 451 }
 452
 453 /* Initializes 'cursor' for iterating through rules in 'cls':
 454  *
 455  *     - If 'target' is null, the cursor will visit every rule in 'cls'.
 456  *
 457  *     - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
 458  *       such that cls_rule_is_loose_match(rule, target) returns true.
 459  *
 460  * Ignores target->priority. */
 461 void
 462 cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
 463                 const struct cls_rule *target)
 464 {
 465     cursor->cls = cls;
 466     cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL;
 467 }
 468
 469 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
 470  * pointer if there are no matches. */
 471 struct cls_rule *
 472 cls_cursor_first(struct cls_cursor *cursor)
 473 {
 474     struct cls_table *table;
 475
 476     HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) {
 477         struct cls_rule *rule = search_table(table, cursor->target);
 478         if (rule) {
 479             cursor->table = table;
 480             return rule;
 481         }
 482     }
 483
 484     return NULL;
 485 }
 486
 487 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
 488  * pointer if there are no more matches. */
 489 struct cls_rule *
 490 cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule)
 491 {
 492     const struct cls_table *table;
 493     struct cls_rule *next;
 494
 495     next = next_rule_in_list__(rule);
 496     if (next->priority < rule->priority) {
 497         return next;
 498     }
 499
 500     /* 'next' is the head of the list, that is, the rule that is included in
 501      * the table's hmap.  (This is important when the classifier contains rules
 502      * that differ only in priority.) */
 503     rule = next;
 504     HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) {
 505         if (rule_matches(rule, cursor->target)) {
 506             return rule;
 507         }
 508     }
 509
 510     table = cursor->table;
 511     HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) {
 512         rule = search_table(table, cursor->target);
 513         if (rule) {
 514             cursor->table = table;
 515             return rule;
 516         }
 517     }
 518
 519     return NULL;
 520 }
 521 \f
 522 static struct cls_table *
 523 find_table(const struct classifier *cls, const struct minimask *mask)
 524 {
 525     struct cls_table *table;
 526
 527     HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0),
 528                              &cls->tables) {
 529         if (minimask_equal(mask, &table->mask)) {
 530             return table;
 531         }
 532     }
 533     return NULL;
 534 }
 535
 536 static struct cls_table *
 537 insert_table(struct classifier *cls, const struct minimask *mask)
 538 {
 539     struct cls_table *table;
 540
 541     table = xzalloc(sizeof *table);
 542     hmap_init(&table->rules);
 543     minimask_clone(&table->mask, mask);
 544     hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0));
 545     list_push_back(&cls->tables_priority, &table->list_node);
 546
 547     return table;
 548 }
 549
 550 static void
 551 destroy_table(struct classifier *cls, struct cls_table *table)
 552 {
 553     minimask_destroy(&table->mask);
 554     hmap_remove(&cls->tables, &table->hmap_node);
 555     hmap_destroy(&table->rules);
 556     list_remove(&table->list_node);
 557     free(table);
 558 }
 559
 560 /* This function performs the following updates for 'table' in 'cls' following
 561  * the addition of a new rule with priority 'new_priority' to 'table':
 562  *
 563  *    - Update 'table->max_priority' and 'table->max_count' if necessary.
 564  *
 565  *    - Update 'table''s position in 'cls->tables_priority' if necessary.
 566  *
 567  * This function should only be called after adding a new rule, not after
 568  * replacing a rule by an identical one or modifying a rule in-place. */
 569 static void
 570 update_tables_after_insertion(struct classifier *cls, struct cls_table *table,
 571                               unsigned int new_priority)
 572 {
 573     if (new_priority == table->max_priority) {
 574         ++table->max_count;
 575     } else if (new_priority > table->max_priority) {
 576         struct cls_table *iter;
 577
 578         table->max_priority = new_priority;
 579         table->max_count = 1;
 580
 581         /* Possibly move 'table' earlier in the priority list.  If we break out
 582          * of the loop, then 'table' should be moved just after that 'iter'.
 583          * If the loop terminates normally, then 'iter' will be the list head
 584          * and we'll move table just after that (e.g. to the front of the
 585          * list). */
 586         iter = table;
 587         LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node,
 588                                         &cls->tables_priority) {
 589             if (iter->max_priority >= table->max_priority) {
 590                 break;
 591             }
 592         }
 593
 594         /* Move 'table' just after 'iter' (unless it's already there). */
 595         if (iter->list_node.next != &table->list_node) {
 596             list_splice(iter->list_node.next,
 597                         &table->list_node, table->list_node.next);
 598         }
 599     }
 600 }
 601
 602 /* This function performs the following updates for 'table' in 'cls' following
 603  * the deletion of a rule with priority 'del_priority' from 'table':
 604  *
 605  *    - Update 'table->max_priority' and 'table->max_count' if necessary.
 606  *
 607  *    - Update 'table''s position in 'cls->tables_priority' if necessary.
 608  *
 609  * This function should only be called after removing a rule, not after
 610  * replacing a rule by an identical one or modifying a rule in-place. */
 611 static void
 612 update_tables_after_removal(struct classifier *cls, struct cls_table *table,
 613                             unsigned int del_priority)
 614 {
 615     struct cls_table *iter;
 616
 617     if (del_priority == table->max_priority && --table->max_count == 0) {
 618         struct cls_rule *head;
 619
 620         table->max_priority = 0;
 621         HMAP_FOR_EACH (head, hmap_node, &table->rules) {
 622             if (head->priority > table->max_priority) {
 623                 table->max_priority = head->priority;
 624                 table->max_count = 1;
 625             } else if (head->priority == table->max_priority) {
 626                 ++table->max_count;
 627             }
 628         }
 629
 630         /* Possibly move 'table' later in the priority list.  If we break out
 631          * of the loop, then 'table' should be moved just before that 'iter'.
 632          * If the loop terminates normally, then 'iter' will be the list head
 633          * and we'll move table just before that (e.g. to the back of the
 634          * list). */
 635         iter = table;
 636         LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) {
 637             if (iter->max_priority <= table->max_priority) {
 638                 break;
 639             }
 640         }
 641
 642         /* Move 'table' just before 'iter' (unless it's already there). */
 643         if (iter->list_node.prev != &table->list_node) {
 644             list_splice(&iter->list_node,
 645                         &table->list_node, table->list_node.next);
 646         }
 647     }
 648 }
 649
 650 static struct cls_rule *
 651 find_match(const struct cls_table *table, const struct flow *flow)
 652 {
 653     uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0);
 654     struct cls_rule *rule;
 655
 656     HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) {
 657         if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow,
 658                                             &table->mask)) {
 659             return rule;
 660         }
 661     }
 662
 663     return NULL;
 664 }
 665
 666 static struct cls_rule *
 667 find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash)
 668 {
 669     struct cls_rule *head;
 670
 671     HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) {
 672         if (miniflow_equal(&head->match.flow, flow)) {
 673             return head;
 674         }
 675     }
 676     return NULL;
 677 }
 678
 679 static struct cls_rule *
 680 insert_rule(struct classifier *cls,
 681             struct cls_table *table, struct cls_rule *new)
 682 {
 683     struct cls_rule *head;
 684     struct cls_rule *old = NULL;
 685
 686     new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow,
 687                                                     &new->match.mask, 0);
 688
 689     head = find_equal(table, &new->match.flow, new->hmap_node.hash);
 690     if (!head) {
 691         hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash);
 692         list_init(&new->list);
 693         goto out;
 694     } else {
 695         /* Scan the list for the insertion point that will keep the list in
 696          * order of decreasing priority. */
 697         struct cls_rule *rule;
 698         FOR_EACH_RULE_IN_LIST (rule, head) {
 699             if (new->priority >= rule->priority) {
 700                 if (rule == head) {
 701                     /* 'new' is the new highest-priority flow in the list. */
 702                     hmap_replace(&table->rules,
 703                                  &rule->hmap_node, &new->hmap_node);
 704                 }
 705
 706                 if (new->priority == rule->priority) {
 707                     list_replace(&new->list, &rule->list);
 708                     old = rule;
 709                     goto out;
 710                 } else {
 711                     list_insert(&rule->list, &new->list);
 712                     goto out;
 713                 }
 714             }
 715         }
 716
 717         /* Insert 'new' at the end of the list. */
 718         list_push_back(&head->list, &new->list);
 719     }
 720
 721  out:
 722     if (!old) {
 723         update_tables_after_insertion(cls, table, new->priority);
 724     }
 725     return old;
 726 }
 727
 728 static struct cls_rule *
 729 next_rule_in_list__(struct cls_rule *rule)
 730 {
 731     struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list);
 732     return next;
 733 }
 734
 735 static struct cls_rule *
 736 next_rule_in_list(struct cls_rule *rule)
 737 {
 738     struct cls_rule *next = next_rule_in_list__(rule);
 739     return next->priority < rule->priority ? next : NULL;
 740 }