lib/classifier.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2012 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 <assert.h>
  20 #include <errno.h>
  21 #include <netinet/in.h>
  22 #include "byte-order.h"
  23 #include "dynamic-string.h"
  24 #include "flow.h"
  25 #include "hash.h"
  26 #include "odp-util.h"
  27 #include "ofp-util.h"
  28 #include "packets.h"
  29
  30 static struct cls_table *find_table(const struct classifier *,
  31                                     const struct flow_wildcards *);
  32 static struct cls_table *insert_table(struct classifier *,
  33                                       const struct flow_wildcards *);
  34
  35 static void destroy_table(struct classifier *, struct cls_table *);
  36
  37 static struct cls_rule *find_match(const struct cls_table *,
  38                                    const struct flow *);
  39 static struct cls_rule *find_equal(struct cls_table *, const struct flow *,
  40                                    uint32_t hash);
  41 static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *);
  42
  43 /* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
  44 #define FOR_EACH_RULE_IN_LIST(RULE, HEAD)                               \
  45     for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE))
  46 #define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD)                    \
  47     for ((RULE) = (HEAD);                                               \
  48          (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true);    \
  49          (RULE) = (NEXT))
  50
  51 static struct cls_rule *next_rule_in_list__(struct cls_rule *);
  52 static struct cls_rule *next_rule_in_list(struct cls_rule *);
  53 \f
  54 /* cls_rule. */
  55
  56 /* Initializes 'rule' to match packets specified by 'match' at the given
  57  * 'priority'.
  58  *
  59  * 'match' must satisfy the invariant described in the comment at the
  60  * definition of struct match.
  61  *
  62  * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but
  63  * internally Open vSwitch supports a wider range.) */
  64 void
  65 cls_rule_init(struct cls_rule *rule,
  66               const struct match *match, unsigned int priority)
  67 {
  68     rule->match = *match;
  69     rule->priority = priority;
  70 }
  71
  72 /* Returns true if 'a' and 'b' match the same packets at the same priority,
  73  * false if they differ in some way. */
  74 bool
  75 cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b)
  76 {
  77     return a->priority == b->priority && match_equal(&a->match, &b->match);
  78 }
  79
  80 /* Returns a hash value for 'rule', folding in 'basis'. */
  81 uint32_t
  82 cls_rule_hash(const struct cls_rule *rule, uint32_t basis)
  83 {
  84     return match_hash(&rule->match, hash_int(rule->priority, basis));
  85 }
  86
  87 /* Appends a string describing 'rule' to 's'. */
  88 void
  89 cls_rule_format(const struct cls_rule *rule, struct ds *s)
  90 {
  91     match_format(&rule->match, s, rule->priority);
  92 }
  93 \f
  94 /* Initializes 'cls' as a classifier that initially contains no classification
  95  * rules. */
  96 void
  97 classifier_init(struct classifier *cls)
  98 {
  99     cls->n_rules = 0;
 100     hmap_init(&cls->tables);
 101 }
 102
 103 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
 104  * caller's responsibility. */
 105 void
 106 classifier_destroy(struct classifier *cls)
 107 {
 108     if (cls) {
 109         struct cls_table *table, *next_table;
 110
 111         HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) {
 112             hmap_destroy(&table->rules);
 113             hmap_remove(&cls->tables, &table->hmap_node);
 114             free(table);
 115         }
 116         hmap_destroy(&cls->tables);
 117     }
 118 }
 119
 120 /* Returns true if 'cls' contains no classification rules, false otherwise. */
 121 bool
 122 classifier_is_empty(const struct classifier *cls)
 123 {
 124     return cls->n_rules == 0;
 125 }
 126
 127 /* Returns the number of rules in 'cls'. */
 128 int
 129 classifier_count(const struct classifier *cls)
 130 {
 131     return cls->n_rules;
 132 }
 133
 134 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 135  * must not modify or free it.
 136  *
 137  * If 'cls' already contains an identical rule (including wildcards, values of
 138  * fixed fields, and priority), replaces the old rule by 'rule' and returns the
 139  * rule that was replaced.  The caller takes ownership of the returned rule and
 140  * is thus responsible for freeing it, etc., as necessary.
 141  *
 142  * Returns NULL if 'cls' does not contain a rule with an identical key, after
 143  * inserting the new rule.  In this case, no rules are displaced by the new
 144  * rule, even rules that cannot have any effect because the new rule matches a
 145  * superset of their flows and has higher priority. */
 146 struct cls_rule *
 147 classifier_replace(struct classifier *cls, struct cls_rule *rule)
 148 {
 149     struct cls_rule *old_rule;
 150     struct cls_table *table;
 151
 152     table = find_table(cls, &rule->match.wc);
 153     if (!table) {
 154         table = insert_table(cls, &rule->match.wc);
 155     }
 156
 157     old_rule = insert_rule(table, rule);
 158     if (!old_rule) {
 159         table->n_table_rules++;
 160         cls->n_rules++;
 161     }
 162     return old_rule;
 163 }
 164
 165 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
 166  * must not modify or free it.
 167  *
 168  * 'cls' must not contain an identical rule (including wildcards, values of
 169  * fixed fields, and priority).  Use classifier_find_rule_exactly() to find
 170  * such a rule. */
 171 void
 172 classifier_insert(struct classifier *cls, struct cls_rule *rule)
 173 {
 174     struct cls_rule *displaced_rule = classifier_replace(cls, rule);
 175     assert(!displaced_rule);
 176 }
 177
 178 /* Removes 'rule' from 'cls'.  It is the caller's responsibility to free
 179  * 'rule', if this is desirable. */
 180 void
 181 classifier_remove(struct classifier *cls, struct cls_rule *rule)
 182 {
 183     struct cls_rule *head;
 184     struct cls_table *table;
 185
 186     table = find_table(cls, &rule->match.wc);
 187     head = find_equal(table, &rule->match.flow, rule->hmap_node.hash);
 188     if (head != rule) {
 189         list_remove(&rule->list);
 190     } else if (list_is_empty(&rule->list)) {
 191         hmap_remove(&table->rules, &rule->hmap_node);
 192     } else {
 193         struct cls_rule *next = CONTAINER_OF(rule->list.next,
 194                                              struct cls_rule, list);
 195
 196         list_remove(&rule->list);
 197         hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node);
 198     }
 199
 200     if (--table->n_table_rules == 0) {
 201         destroy_table(cls, table);
 202     }
 203
 204     cls->n_rules--;
 205 }
 206
 207 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
 208  * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
 209  * of equal priority match 'flow', returns one arbitrarily. */
 210 struct cls_rule *
 211 classifier_lookup(const struct classifier *cls, const struct flow *flow)
 212 {
 213     struct cls_table *table;
 214     struct cls_rule *best;
 215
 216     best = NULL;
 217     HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
 218         struct cls_rule *rule = find_match(table, flow);
 219         if (rule && (!best || rule->priority > best->priority)) {
 220             best = rule;
 221         }
 222     }
 223     return best;
 224 }
 225
 226 /* Finds and returns a rule in 'cls' with exactly the same priority and
 227  * matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 228  * contain an exact match. */
 229 struct cls_rule *
 230 classifier_find_rule_exactly(const struct classifier *cls,
 231                              const struct cls_rule *target)
 232 {
 233     struct cls_rule *head, *rule;
 234     struct cls_table *table;
 235
 236     table = find_table(cls, &target->match.wc);
 237     if (!table) {
 238         return NULL;
 239     }
 240
 241     head = find_equal(table, &target->match.flow,
 242                       flow_hash(&target->match.flow, 0));
 243     FOR_EACH_RULE_IN_LIST (rule, head) {
 244         if (target->priority >= rule->priority) {
 245             return target->priority == rule->priority ? rule : NULL;
 246         }
 247     }
 248     return NULL;
 249 }
 250
 251 /* Finds and returns a rule in 'cls' with priority 'priority' and exactly the
 252  * same matching criteria as 'target'.  Returns a null pointer if 'cls' doesn't
 253  * contain an exact match. */
 254 struct cls_rule *
 255 classifier_find_match_exactly(const struct classifier *cls,
 256                               const struct match *target,
 257                               unsigned int priority)
 258 {
 259     struct cls_rule *retval;
 260     struct cls_rule cr;
 261
 262     cls_rule_init(&cr, target, priority);
 263     retval = classifier_find_rule_exactly(cls, &cr);
 264
 265     return retval;
 266 }
 267
 268 /* Checks if 'target' would overlap any other rule in 'cls'.  Two rules are
 269  * considered to overlap if both rules have the same priority and a packet
 270  * could match both. */
 271 bool
 272 classifier_rule_overlaps(const struct classifier *cls,
 273                          const struct cls_rule *target)
 274 {
 275     struct cls_table *table;
 276
 277     HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
 278         struct flow_wildcards wc;
 279         struct cls_rule *head;
 280
 281         flow_wildcards_combine(&wc, &target->match.wc, &table->wc);
 282         HMAP_FOR_EACH (head, hmap_node, &table->rules) {
 283             struct cls_rule *rule;
 284
 285             FOR_EACH_RULE_IN_LIST (rule, head) {
 286                 if (rule->priority == target->priority
 287                     && flow_equal_except(&target->match.flow,
 288                                          &rule->match.flow, &wc)) {
 289                     return true;
 290                 }
 291             }
 292         }
 293     }
 294
 295     return false;
 296 }
 297
 298 /* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more
 299  * specific than 'criteria'.  That is, 'rule' matches 'criteria' and this
 300  * function returns true if, for every field:
 301  *
 302  *   - 'criteria' and 'rule' specify the same (non-wildcarded) value for the
 303  *     field, or
 304  *
 305  *   - 'criteria' wildcards the field,
 306  *
 307  * Conversely, 'rule' does not match 'criteria' and this function returns false
 308  * if, for at least one field:
 309  *
 310  *   - 'criteria' and 'rule' specify different values for the field, or
 311  *
 312  *   - 'criteria' specifies a value for the field but 'rule' wildcards it.
 313  *
 314  * Equivalently, the truth table for whether a field matches is:
 315  *
 316  *                                     rule
 317  *
 318  *                   c         wildcard    exact
 319  *                   r        +---------+---------+
 320  *                   i   wild |   yes   |   yes   |
 321  *                   t   card |         |         |
 322  *                   e        +---------+---------+
 323  *                   r  exact |    no   |if values|
 324  *                   i        |         |are equal|
 325  *                   a        +---------+---------+
 326  *
 327  * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD
 328  * commands and by OpenFlow 1.0 aggregate and flow stats.
 329  *
 330  * Ignores rule->priority. */
 331 bool
 332 cls_rule_is_loose_match(const struct cls_rule *rule,
 333                         const struct match *criteria)
 334 {
 335     return (!flow_wildcards_has_extra(&rule->match.wc, &criteria->wc)
 336             && flow_equal_except(&rule->match.flow, &criteria->flow,
 337                                  &criteria->wc));
 338 }
 339 \f
 340 /* Iteration. */
 341
 342 static bool
 343 rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
 344 {
 345     return (!target
 346             || flow_equal_except(&rule->match.flow, &target->match.flow,
 347                                  &target->match.wc));
 348 }
 349
 350 static struct cls_rule *
 351 search_table(const struct cls_table *table, const struct cls_rule *target)
 352 {
 353     if (!target || !flow_wildcards_has_extra(&table->wc, &target->match.wc)) {
 354         struct cls_rule *rule;
 355
 356         HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
 357             if (rule_matches(rule, target)) {
 358                 return rule;
 359             }
 360         }
 361     }
 362     return NULL;
 363 }
 364
 365 /* Initializes 'cursor' for iterating through rules in 'cls':
 366  *
 367  *     - If 'target' is null, the cursor will visit every rule in 'cls'.
 368  *
 369  *     - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls'
 370  *       such that cls_rule_is_loose_match(rule, target) returns true.
 371  *
 372  * Ignores target->priority. */
 373 void
 374 cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls,
 375                 const struct cls_rule *target)
 376 {
 377     cursor->cls = cls;
 378     cursor->target = target;
 379 }
 380
 381 /* Returns the first matching cls_rule in 'cursor''s iteration, or a null
 382  * pointer if there are no matches. */
 383 struct cls_rule *
 384 cls_cursor_first(struct cls_cursor *cursor)
 385 {
 386     struct cls_table *table;
 387
 388     HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) {
 389         struct cls_rule *rule = search_table(table, cursor->target);
 390         if (rule) {
 391             cursor->table = table;
 392             return rule;
 393         }
 394     }
 395
 396     return NULL;
 397 }
 398
 399 /* Returns the next matching cls_rule in 'cursor''s iteration, or a null
 400  * pointer if there are no more matches. */
 401 struct cls_rule *
 402 cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule)
 403 {
 404     const struct cls_table *table;
 405     struct cls_rule *next;
 406
 407     next = next_rule_in_list__(rule);
 408     if (next->priority < rule->priority) {
 409         return next;
 410     }
 411
 412     /* 'next' is the head of the list, that is, the rule that is included in
 413      * the table's hmap.  (This is important when the classifier contains rules
 414      * that differ only in priority.) */
 415     rule = next;
 416     HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) {
 417         if (rule_matches(rule, cursor->target)) {
 418             return rule;
 419         }
 420     }
 421
 422     table = cursor->table;
 423     HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) {
 424         rule = search_table(table, cursor->target);
 425         if (rule) {
 426             cursor->table = table;
 427             return rule;
 428         }
 429     }
 430
 431     return NULL;
 432 }
 433 \f
 434 static struct cls_table *
 435 find_table(const struct classifier *cls, const struct flow_wildcards *wc)
 436 {
 437     struct cls_table *table;
 438
 439     HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc, 0),
 440                              &cls->tables) {
 441         if (flow_wildcards_equal(wc, &table->wc)) {
 442             return table;
 443         }
 444     }
 445     return NULL;
 446 }
 447
 448 static struct cls_table *
 449 insert_table(struct classifier *cls, const struct flow_wildcards *wc)
 450 {
 451     struct cls_table *table;
 452
 453     table = xzalloc(sizeof *table);
 454     hmap_init(&table->rules);
 455     table->wc = *wc;
 456     table->is_catchall = flow_wildcards_is_catchall(&table->wc);
 457     hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc, 0));
 458
 459     return table;
 460 }
 461
 462 static void
 463 destroy_table(struct classifier *cls, struct cls_table *table)
 464 {
 465     hmap_remove(&cls->tables, &table->hmap_node);
 466     hmap_destroy(&table->rules);
 467     free(table);
 468 }
 469
 470 static struct cls_rule *
 471 find_match(const struct cls_table *table, const struct flow *flow)
 472 {
 473     struct cls_rule *rule;
 474
 475     if (table->is_catchall) {
 476         HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
 477             return rule;
 478         }
 479     } else {
 480         struct flow f;
 481
 482         f = *flow;
 483         flow_zero_wildcards(&f, &table->wc);
 484         HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0),
 485                                  &table->rules) {
 486             if (flow_equal(&f, &rule->match.flow)) {
 487                 return rule;
 488             }
 489         }
 490     }
 491
 492     return NULL;
 493 }
 494
 495 static struct cls_rule *
 496 find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash)
 497 {
 498     struct cls_rule *head;
 499
 500     HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) {
 501         if (flow_equal(&head->match.flow, flow)) {
 502             return head;
 503         }
 504     }
 505     return NULL;
 506 }
 507
 508 static struct cls_rule *
 509 insert_rule(struct cls_table *table, struct cls_rule *new)
 510 {
 511     struct cls_rule *head;
 512
 513     new->hmap_node.hash = flow_hash(&new->match.flow, 0);
 514
 515     head = find_equal(table, &new->match.flow, new->hmap_node.hash);
 516     if (!head) {
 517         hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash);
 518         list_init(&new->list);
 519         return NULL;
 520     } else {
 521         /* Scan the list for the insertion point that will keep the list in
 522          * order of decreasing priority. */
 523         struct cls_rule *rule;
 524         FOR_EACH_RULE_IN_LIST (rule, head) {
 525             if (new->priority >= rule->priority) {
 526                 if (rule == head) {
 527                     /* 'new' is the new highest-priority flow in the list. */
 528                     hmap_replace(&table->rules,
 529                                  &rule->hmap_node, &new->hmap_node);
 530                 }
 531
 532                 if (new->priority == rule->priority) {
 533                     list_replace(&new->list, &rule->list);
 534                     return rule;
 535                 } else {
 536                     list_insert(&rule->list, &new->list);
 537                     return NULL;
 538                 }
 539             }
 540         }
 541
 542         /* Insert 'new' at the end of the list. */
 543         list_push_back(&head->list, &new->list);
 544         return NULL;
 545     }
 546 }
 547
 548 static struct cls_rule *
 549 next_rule_in_list__(struct cls_rule *rule)
 550 {
 551     struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list);
 552     return next;
 553 }
 554
 555 static struct cls_rule *
 556 next_rule_in_list(struct cls_rule *rule)
 557 {
 558     struct cls_rule *next = next_rule_in_list__(rule);
 559     return next->priority < rule->priority ? next : NULL;
 560 }