lib/classifier.c

   1 /*
   2  * Copyright (c) 2009, 2010 Nicira Networks.
   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 "dynamic-string.h"
  23 #include "flow.h"
  24 #include "hash.h"
  25
  26 const struct cls_field cls_fields[CLS_N_FIELDS + 1] = {
  27 #define CLS_FIELD(WILDCARDS, MEMBER, NAME)      \
  28     { offsetof(flow_t, MEMBER),                 \
  29       sizeof ((flow_t *)0)->MEMBER,             \
  30       WILDCARDS,                                \
  31       #NAME },
  32     CLS_FIELDS
  33 #undef CLS_FIELD
  34     { sizeof(flow_t), 0, 0, "exact" },
  35 };
  36
  37 static uint32_t hash_fields(const flow_t *, int table_idx);
  38 static bool equal_fields(const flow_t *, const flow_t *, int table_idx);
  39
  40 static int table_idx_from_wildcards(uint32_t wildcards);
  41 static struct cls_rule *table_insert(struct hmap *, struct cls_rule *);
  42 static struct cls_rule *insert_exact_rule(struct classifier *,
  43                                           struct cls_rule *);
  44 static struct cls_bucket *find_bucket(struct hmap *, size_t hash,
  45                                       const struct cls_rule *);
  46 static struct cls_rule *search_table(const struct hmap *table, int field_idx,
  47                                      const struct cls_rule *);
  48 static struct cls_rule *search_exact_table(const struct classifier *,
  49                                            size_t hash, const flow_t *);
  50 static bool rules_match_1wild(const struct cls_rule *fixed,
  51                               const struct cls_rule *wild, int field_idx);
  52 static bool rules_match_2wild(const struct cls_rule *wild1,
  53                               const struct cls_rule *wild2, int field_idx);
  54
  55 /* Converts the flow in 'flow' into a cls_rule in 'rule', with the given
  56  * 'wildcards' and 'priority'.*/
  57 void
  58 cls_rule_from_flow(struct cls_rule *rule, const flow_t *flow,
  59                    uint32_t wildcards, unsigned int priority)
  60 {
  61     rule->flow = *flow;
  62     flow_wildcards_init(&rule->wc, wildcards);
  63     rule->priority = priority;
  64     rule->table_idx = table_idx_from_wildcards(rule->wc.wildcards);
  65 }
  66
  67 /* Converts the ofp_match in 'match' into a cls_rule in 'rule', with the given
  68  * 'priority'. */
  69 void
  70 cls_rule_from_match(struct cls_rule *rule, const struct ofp_match *match,
  71                     unsigned int priority)
  72 {
  73     uint32_t wildcards;
  74     flow_from_match(&rule->flow, &wildcards, match);
  75     flow_wildcards_init(&rule->wc, wildcards);
  76     rule->priority = rule->wc.wildcards ? priority : UINT16_MAX;
  77     rule->table_idx = table_idx_from_wildcards(rule->wc.wildcards);
  78 }
  79
  80 /* Converts 'rule' to a string and returns the string.  The caller must free
  81  * the string (with free()). */
  82 char *
  83 cls_rule_to_string(const struct cls_rule *rule)
  84 {
  85     struct ds s = DS_EMPTY_INITIALIZER;
  86     ds_put_format(&s, "wildcards=%x priority=%u ",
  87                   rule->wc.wildcards, rule->priority);
  88     flow_format(&s, &rule->flow);
  89     return ds_cstr(&s);
  90 }
  91
  92 /* Prints cls_rule 'rule', for debugging.
  93  *
  94  * (The output could be improved and expanded, but this was good enough to
  95  * debug the classifier.) */
  96 void
  97 cls_rule_print(const struct cls_rule *rule)
  98 {
  99     printf("wildcards=%x priority=%u ", rule->wc.wildcards, rule->priority);
 100     flow_print(stdout, &rule->flow);
 101     putc('\n', stdout);
 102 }
 103
 104 /* Adjusts pointers around 'old', which must be in classifier 'cls', to
 105  * compensate for it having been moved in memory to 'new' (e.g. due to
 106  * realloc()).
 107  *
 108  * This function cannot be realized in all possible flow classifier
 109  * implementations, so we will probably have to change the interface if we
 110  * change the implementation.  Shouldn't be a big deal though. */
 111 void
 112 cls_rule_moved(struct classifier *cls, struct cls_rule *old,
 113                struct cls_rule *new)
 114 {
 115     if (old != new) {
 116         if (new->wc.wildcards) {
 117             list_moved(&new->node.list);
 118         } else {
 119             hmap_node_moved(&cls->exact_table,
 120                             &old->node.hmap, &new->node.hmap);
 121         }
 122     }
 123 }
 124
 125 /* Replaces 'old', which must be in classifier 'cls', by 'new' (e.g. due to
 126  * realloc()); that is, after calling this function 'new' will be in 'cls' in
 127  * place of 'old'.
 128  *
 129  * 'new' and 'old' must be exactly the same: wildcard the same fields, have the
 130  * same fixed values for non-wildcarded fields, and have the same priority.
 131  *
 132  * The caller takes ownership of 'old' and is thus responsible for freeing it,
 133  * etc., as necessary.
 134  *
 135  * This function cannot be realized in all possible flow classifier
 136  * implementations, so we will probably have to change the interface if we
 137  * change the implementation.  Shouldn't be a big deal though. */
 138 void
 139 cls_rule_replace(struct classifier *cls, const struct cls_rule *old,
 140                  struct cls_rule *new)
 141 {
 142     assert(old != new);
 143     assert(old->wc.wildcards == new->wc.wildcards);
 144     assert(old->priority == new->priority);
 145
 146     if (new->wc.wildcards) {
 147         list_replace(&new->node.list, &old->node.list);
 148     } else {
 149         hmap_replace(&cls->exact_table, &old->node.hmap, &new->node.hmap);
 150     }
 151 }
 152 \f
 153 /* Initializes 'cls' as a classifier that initially contains no classification
 154  * rules. */
 155 void
 156 classifier_init(struct classifier *cls)
 157 {
 158     int i;
 159
 160     cls->n_rules = 0;
 161     for (i = 0; i < ARRAY_SIZE(cls->tables); i++) {
 162         hmap_init(&cls->tables[i]);
 163     }
 164     hmap_init(&cls->exact_table);
 165 }
 166
 167 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
 168  * caller's responsibility. */
 169 void
 170 classifier_destroy(struct classifier *cls)
 171 {
 172     if (cls) {
 173         struct cls_bucket *bucket, *next_bucket;
 174         struct hmap *tbl;
 175
 176         for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) {
 177             HMAP_FOR_EACH_SAFE (bucket, next_bucket,
 178                                 struct cls_bucket, hmap_node, tbl) {
 179                 free(bucket);
 180             }
 181             hmap_destroy(tbl);
 182         }
 183         hmap_destroy(&cls->exact_table);
 184     }
 185 }
 186
 187 /* Returns true if 'cls' does not contain any classification rules, false
 188  * otherwise. */
 189 bool
 190 classifier_is_empty(const struct classifier *cls)
 191 {
 192     return cls->n_rules == 0;
 193 }
 194
 195 /* Returns the number of rules in 'classifier'. */
 196 int
 197 classifier_count(const struct classifier *cls)
 198 {
 199     return cls->n_rules;
 200 }
 201
 202 /* Returns the number of rules in 'classifier' that have no wildcards. */
 203 int
 204 classifier_count_exact(const struct classifier *cls)
 205 {
 206     return hmap_count(&cls->exact_table);
 207 }
 208
 209 /* Inserts 'rule' into 'cls'.  Transfers ownership of 'rule' to 'cls'.
 210  *
 211  * If 'cls' already contains an identical rule (including wildcards, values of
 212  * fixed fields, and priority), replaces the old rule by 'rule' and returns the
 213  * rule that was replaced.  The caller takes ownership of the returned rule and
 214  * is thus responsible for freeing it, etc., as necessary.
 215  *
 216  * Returns NULL if 'cls' does not contain a rule with an identical key, after
 217  * inserting the new rule.  In this case, no rules are displaced by the new
 218  * rule, even rules that cannot have any effect because the new rule matches a
 219  * superset of their flows and has higher priority. */
 220 struct cls_rule *
 221 classifier_insert(struct classifier *cls, struct cls_rule *rule)
 222 {
 223     struct cls_rule *old;
 224     assert((rule->wc.wildcards == 0) == (rule->table_idx == CLS_F_IDX_EXACT));
 225     old = (rule->wc.wildcards
 226            ? table_insert(&cls->tables[rule->table_idx], rule)
 227            : insert_exact_rule(cls, rule));
 228     if (!old) {
 229         cls->n_rules++;
 230     }
 231     return old;
 232 }
 233
 234 /* Inserts 'rule' into 'cls'.  Transfers ownership of 'rule' to 'cls'.
 235  *
 236  * 'rule' must be an exact-match rule (rule->wc.wildcards must be 0) and 'cls'
 237  * must not contain any rule with an identical key. */
 238 void
 239 classifier_insert_exact(struct classifier *cls, struct cls_rule *rule)
 240 {
 241     hmap_insert(&cls->exact_table, &rule->node.hmap,
 242                 flow_hash(&rule->flow, 0));
 243     cls->n_rules++;
 244 }
 245
 246 /* Removes 'rule' from 'cls'.  It is caller's responsibility to free 'rule', if
 247  * this is desirable. */
 248 void
 249 classifier_remove(struct classifier *cls, struct cls_rule *rule)
 250 {
 251     if (rule->wc.wildcards) {
 252         /* Remove 'rule' from bucket.  If that empties the bucket, remove the
 253          * bucket from its table. */
 254         struct hmap *table = &cls->tables[rule->table_idx];
 255         struct list *rules = list_remove(&rule->node.list);
 256         if (list_is_empty(rules)) {
 257             /* This code is a little tricky.  list_remove() returns the list
 258              * element just after the one removed.  Since the list is now
 259              * empty, this will be the address of the 'rules' member of the
 260              * bucket that was just emptied, so pointer arithmetic (via
 261              * CONTAINER_OF) can find that bucket. */
 262             struct cls_bucket *bucket;
 263             bucket = CONTAINER_OF(rules, struct cls_bucket, rules);
 264             hmap_remove(table, &bucket->hmap_node);
 265             free(bucket);
 266         }
 267     } else {
 268         /* Remove 'rule' from cls->exact_table. */
 269         hmap_remove(&cls->exact_table, &rule->node.hmap);
 270     }
 271     cls->n_rules--;
 272 }
 273
 274 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
 275  * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
 276  * of equal priority match 'flow', returns one arbitrarily.
 277  *
 278  * (When multiple rules of equal priority happen to fall into the same bucket,
 279  * rules added more recently take priority over rules added less recently, but
 280  * this is subject to change and should not be depended upon.) */
 281 struct cls_rule *
 282 classifier_lookup(const struct classifier *cls, const flow_t *flow)
 283 {
 284     struct cls_rule *rule = classifier_lookup_exact(cls, flow);
 285     if (!rule) {
 286         rule = classifier_lookup_wild(cls, flow);
 287     }
 288     return rule;
 289 }
 290
 291 struct cls_rule *
 292 classifier_lookup_exact(const struct classifier *cls, const flow_t *flow)
 293 {
 294     return (!hmap_is_empty(&cls->exact_table)
 295             ? search_exact_table(cls, flow_hash(flow, 0), flow)
 296             : NULL);
 297 }
 298
 299 struct cls_rule *
 300 classifier_lookup_wild(const struct classifier *cls, const flow_t *flow)
 301 {
 302     struct cls_rule *best = NULL;
 303     if (cls->n_rules > hmap_count(&cls->exact_table)) {
 304         struct cls_rule target;
 305         int i;
 306
 307         cls_rule_from_flow(&target, flow, 0, 0);
 308         for (i = 0; i < CLS_N_FIELDS; i++) {
 309             struct cls_rule *rule = search_table(&cls->tables[i], i, &target);
 310             if (rule && (!best || rule->priority > best->priority)) {
 311                 best = rule;
 312             }
 313         }
 314     }
 315     return best;
 316 }
 317
 318 struct cls_rule *
 319 classifier_find_rule_exactly(const struct classifier *cls,
 320                              const flow_t *target, uint32_t wildcards,
 321                              unsigned int priority)
 322 {
 323     struct cls_bucket *bucket;
 324     int table_idx;
 325     uint32_t hash;
 326
 327     if (!wildcards) {
 328         /* Ignores 'priority'. */
 329         return search_exact_table(cls, flow_hash(target, 0), target);
 330     }
 331
 332     assert(wildcards == (wildcards & OFPFW_ALL));
 333     table_idx = table_idx_from_wildcards(wildcards);
 334     hash = hash_fields(target, table_idx);
 335     HMAP_FOR_EACH_WITH_HASH (bucket, struct cls_bucket, hmap_node, hash,
 336                              &cls->tables[table_idx]) {
 337         if (equal_fields(&bucket->fixed, target, table_idx)) {
 338             struct cls_rule *pos;
 339             LIST_FOR_EACH (pos, struct cls_rule, node.list, &bucket->rules) {
 340                 if (pos->priority < priority) {
 341                     return NULL;
 342                 } else if (pos->priority == priority &&
 343                            pos->wc.wildcards == wildcards &&
 344                            flow_equal(target, &pos->flow)) {
 345                     return pos;
 346                 }
 347             }
 348         }
 349     }
 350     return NULL;
 351 }
 352
 353 /* Checks if the flow defined by 'target' with 'wildcards' at 'priority'
 354  * overlaps with any other rule at the same priority in the classifier.
 355  * Two rules are considered overlapping if a packet could match both. */
 356 bool
 357 classifier_rule_overlaps(const struct classifier *cls,
 358                          const flow_t *target, uint32_t wildcards,
 359                          unsigned int priority)
 360 {
 361     struct cls_rule target_rule;
 362     const struct hmap *tbl;
 363
 364     if (!wildcards) {
 365         return search_exact_table(cls, flow_hash(target, 0), target) ?
 366             true : false;
 367     }
 368
 369     cls_rule_from_flow(&target_rule, target, wildcards, priority);
 370
 371     for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) {
 372         struct cls_bucket *bucket;
 373
 374         HMAP_FOR_EACH (bucket, struct cls_bucket, hmap_node, tbl) {
 375             struct cls_rule *rule;
 376
 377             LIST_FOR_EACH (rule, struct cls_rule, node.list,
 378                            &bucket->rules) {
 379                 if (rule->priority == priority
 380                         && rules_match_2wild(rule, &target_rule, 0)) {
 381                     return true;
 382                 }
 383             }
 384         }
 385     }
 386
 387     return false;
 388 }
 389
 390 /* Ignores target->priority.
 391  *
 392  * 'callback' is allowed to delete the rule that is passed as its argument, but
 393  * it must not delete (or move) any other rules in 'cls' that are in the same
 394  * table as the argument rule.  Two rules are in the same table if their
 395  * cls_rule structs have the same table_idx; as a special case, a rule with
 396  * wildcards and an exact-match rule will never be in the same table. */
 397 void
 398 classifier_for_each_match(const struct classifier *cls,
 399                           const struct cls_rule *target,
 400                           int include, cls_cb_func *callback, void *aux)
 401 {
 402     if (include & CLS_INC_WILD) {
 403         const struct hmap *table;
 404
 405         for (table = &cls->tables[0]; table < &cls->tables[CLS_N_FIELDS];
 406              table++) {
 407             struct cls_bucket *bucket, *next_bucket;
 408
 409             HMAP_FOR_EACH_SAFE (bucket, next_bucket,
 410                                 struct cls_bucket, hmap_node, table) {
 411                 /* XXX there is a bit of room for optimization here based on
 412                  * rejecting entire buckets on their fixed fields, but it will
 413                  * only be worthwhile for big buckets (which we hope we won't
 414                  * get anyway, but...) */
 415                 struct cls_rule *prev_rule, *rule;
 416
 417                 /* We can't just use LIST_FOR_EACH_SAFE here because, if the
 418                  * callback deletes the last rule in the bucket, then the
 419                  * bucket itself will be destroyed.  The bucket contains the
 420                  * list head so that's a use-after-free error. */
 421                 prev_rule = NULL;
 422                 LIST_FOR_EACH (rule, struct cls_rule, node.list,
 423                                &bucket->rules) {
 424                     if (rules_match_1wild(rule, target, 0)) {
 425                         if (prev_rule) {
 426                             callback(prev_rule, aux);
 427                         }
 428                         prev_rule = rule;
 429                     }
 430                 }
 431                 if (prev_rule) {
 432                     callback(prev_rule, aux);
 433                 }
 434             }
 435         }
 436     }
 437
 438     if (include & CLS_INC_EXACT) {
 439         if (target->wc.wildcards) {
 440             struct cls_rule *rule, *next_rule;
 441
 442             HMAP_FOR_EACH_SAFE (rule, next_rule, struct cls_rule, node.hmap,
 443                                 &cls->exact_table) {
 444                 if (rules_match_1wild(rule, target, 0)) {
 445                     callback(rule, aux);
 446                 }
 447             }
 448         } else {
 449             /* Optimization: there can be at most one match in the exact
 450              * table. */
 451             size_t hash = flow_hash(&target->flow, 0);
 452             struct cls_rule *rule = search_exact_table(cls, hash,
 453                                                        &target->flow);
 454             if (rule) {
 455                 callback(rule, aux);
 456             }
 457         }
 458     }
 459 }
 460
 461 /* 'callback' is allowed to delete the rule that is passed as its argument, but
 462  * it must not delete (or move) any other rules in 'cls' that are in the same
 463  * table as the argument rule.  Two rules are in the same table if their
 464  * cls_rule structs have the same table_idx; as a special case, a rule with
 465  * wildcards and an exact-match rule will never be in the same table. */
 466 void
 467 classifier_for_each(const struct classifier *cls, int include,
 468                     void (*callback)(struct cls_rule *, void *aux),
 469                     void *aux)
 470 {
 471     if (include & CLS_INC_WILD) {
 472         const struct hmap *tbl;
 473
 474         for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) {
 475             struct cls_bucket *bucket, *next_bucket;
 476
 477             HMAP_FOR_EACH_SAFE (bucket, next_bucket,
 478                                 struct cls_bucket, hmap_node, tbl) {
 479                 struct cls_rule *prev_rule, *rule;
 480
 481                 /* We can't just use LIST_FOR_EACH_SAFE here because, if the
 482                  * callback deletes the last rule in the bucket, then the
 483                  * bucket itself will be destroyed.  The bucket contains the
 484                  * list head so that's a use-after-free error. */
 485                 prev_rule = NULL;
 486                 LIST_FOR_EACH (rule, struct cls_rule, node.list,
 487                                &bucket->rules) {
 488                     if (prev_rule) {
 489                         callback(prev_rule, aux);
 490                     }
 491                     prev_rule = rule;
 492                 }
 493                 if (prev_rule) {
 494                     callback(prev_rule, aux);
 495                 }
 496             }
 497         }
 498     }
 499
 500     if (include & CLS_INC_EXACT) {
 501         struct cls_rule *rule, *next_rule;
 502
 503         HMAP_FOR_EACH_SAFE (rule, next_rule,
 504                             struct cls_rule, node.hmap, &cls->exact_table) {
 505             callback(rule, aux);
 506         }
 507     }
 508 }
 509 \f
 510 static struct cls_bucket *create_bucket(struct hmap *, size_t hash,
 511                                         const flow_t *fixed);
 512 static struct cls_rule *bucket_insert(struct cls_bucket *, struct cls_rule *);
 513
 514 static inline bool equal_bytes(const void *, const void *, size_t n);
 515
 516 /* Returns a hash computed across the fields in 'flow' whose field indexes
 517  * (CLS_F_IDX_*) are less than 'table_idx'.  (If 'table_idx' is
 518  * CLS_F_IDX_EXACT, hashes all the fields in 'flow'). */
 519 static uint32_t
 520 hash_fields(const flow_t *flow, int table_idx)
 521 {
 522     /* I just know I'm going to hell for writing code this way.
 523      *
 524      * GCC generates pretty good code here, with only a single taken
 525      * conditional jump per execution.  Now the question is, would we be better
 526      * off marking this function ALWAYS_INLINE and writing a wrapper that
 527      * switches on the value of 'table_idx' to get rid of all the conditional
 528      * jumps entirely (except for one in the wrapper)?  Honestly I really,
 529      * really hope that it doesn't matter in practice.
 530      *
 531      * We could do better by calculating hashes incrementally, instead of
 532      * starting over from the top each time.  But that would be even uglier. */
 533     uint32_t a, b, c;
 534     uint32_t tmp[3];
 535     size_t n;
 536
 537     a = b = c = 0xdeadbeef + table_idx;
 538     n = 0;
 539
 540 #define CLS_FIELD(WILDCARDS, MEMBER, NAME)                      \
 541     if (table_idx == CLS_F_IDX_##NAME) {                        \
 542         /* Done. */                                             \
 543         memset((uint8_t *) tmp + n, 0, sizeof tmp - n);         \
 544         goto finish;                                            \
 545     } else {                                                    \
 546         const size_t size = sizeof flow->MEMBER;                \
 547         const uint8_t *p1 = (const uint8_t *) &flow->MEMBER;    \
 548         const size_t p1_size = MIN(sizeof tmp - n, size);       \
 549         const uint8_t *p2 = p1 + p1_size;                       \
 550         const size_t p2_size = size - p1_size;                  \
 551                                                                 \
 552         /* Append to 'tmp' as much data as will fit. */         \
 553         memcpy((uint8_t *) tmp + n, p1, p1_size);               \
 554         n += p1_size;                                           \
 555                                                                 \
 556         /* If 'tmp' is full, mix. */                            \
 557         if (n == sizeof tmp) {                                  \
 558             a += tmp[0];                                        \
 559             b += tmp[1];                                        \
 560             c += tmp[2];                                        \
 561             HASH_MIX(a, b, c);                                  \
 562             n = 0;                                              \
 563         }                                                       \
 564                                                                 \
 565         /* Append to 'tmp' any data that didn't fit. */         \
 566         memcpy(tmp, p2, p2_size);                               \
 567         n += p2_size;                                           \
 568     }
 569     CLS_FIELDS
 570 #undef CLS_FIELD
 571
 572 finish:
 573     a += tmp[0];
 574     b += tmp[1];
 575     c += tmp[2];
 576     HASH_FINAL(a, b, c);
 577     return c;
 578 }
 579
 580 /* Compares the fields in 'a' and 'b' whose field indexes (CLS_F_IDX_*) are
 581  * less than 'table_idx'.  (If 'table_idx' is CLS_F_IDX_EXACT, compares all the
 582  * fields in 'a' and 'b').
 583  *
 584  * Returns true if all the compared fields are equal, false otherwise. */
 585 static bool
 586 equal_fields(const flow_t *a, const flow_t *b, int table_idx)
 587 {
 588     /* XXX The generated code could be better here. */
 589 #define CLS_FIELD(WILDCARDS, MEMBER, NAME)                              \
 590     if (table_idx == CLS_F_IDX_##NAME) {                                \
 591         return true;                                                    \
 592     } else if (!equal_bytes(&a->MEMBER, &b->MEMBER, sizeof a->MEMBER)) { \
 593         return false;                                                   \
 594     }
 595     CLS_FIELDS
 596 #undef CLS_FIELD
 597
 598     return true;
 599 }
 600
 601 static int
 602 table_idx_from_wildcards(uint32_t wildcards)
 603 {
 604     if (!wildcards) {
 605         return CLS_F_IDX_EXACT;
 606     }
 607 #define CLS_FIELD(WILDCARDS, MEMBER, NAME) \
 608     if (wildcards & WILDCARDS) {           \
 609         return CLS_F_IDX_##NAME;           \
 610     }
 611     CLS_FIELDS
 612 #undef CLS_FIELD
 613     NOT_REACHED();
 614 }
 615
 616 /* Inserts 'rule' into 'table'.  Returns the rule, if any, that was displaced
 617  * in favor of 'rule'. */
 618 static struct cls_rule *
 619 table_insert(struct hmap *table, struct cls_rule *rule)
 620 {
 621     struct cls_bucket *bucket;
 622     size_t hash;
 623
 624     hash = hash_fields(&rule->flow, rule->table_idx);
 625     bucket = find_bucket(table, hash, rule);
 626     if (!bucket) {
 627         bucket = create_bucket(table, hash, &rule->flow);
 628     }
 629
 630     return bucket_insert(bucket, rule);
 631 }
 632
 633 /* Inserts 'rule' into 'bucket', given that 'field' is the first wildcarded
 634  * field in 'rule'.
 635  *
 636  * Returns the rule, if any, that was displaced in favor of 'rule'. */
 637 static struct cls_rule *
 638 bucket_insert(struct cls_bucket *bucket, struct cls_rule *rule)
 639 {
 640     struct cls_rule *pos;
 641     LIST_FOR_EACH (pos, struct cls_rule, node.list, &bucket->rules) {
 642         if (pos->priority == rule->priority) {
 643             if (pos->wc.wildcards == rule->wc.wildcards
 644                 && rules_match_1wild(pos, rule, rule->table_idx))
 645             {
 646                 list_replace(&rule->node.list, &pos->node.list);
 647                 return pos;
 648             }
 649         } else if (pos->priority < rule->priority) {
 650             break;
 651         }
 652     }
 653     list_insert(&pos->node.list, &rule->node.list);
 654     return NULL;
 655 }
 656
 657 static struct cls_rule *
 658 insert_exact_rule(struct classifier *cls, struct cls_rule *rule)
 659 {
 660     struct cls_rule *old_rule;
 661     size_t hash;
 662
 663     hash = flow_hash(&rule->flow, 0);
 664     old_rule = search_exact_table(cls, hash, &rule->flow);
 665     if (old_rule) {
 666         hmap_remove(&cls->exact_table, &old_rule->node.hmap);
 667     }
 668     hmap_insert(&cls->exact_table, &rule->node.hmap, hash);
 669     return old_rule;
 670 }
 671
 672 /* Returns the bucket in 'table' that has the given 'hash' and the same fields
 673  * as 'rule->flow' (up to 'rule->table_idx'), or a null pointer if no bucket
 674  * matches. */
 675 static struct cls_bucket *
 676 find_bucket(struct hmap *table, size_t hash, const struct cls_rule *rule)
 677 {
 678     struct cls_bucket *bucket;
 679     HMAP_FOR_EACH_WITH_HASH (bucket, struct cls_bucket, hmap_node, hash,
 680                              table) {
 681         if (equal_fields(&bucket->fixed, &rule->flow, rule->table_idx)) {
 682             return bucket;
 683         }
 684     }
 685     return NULL;
 686 }
 687
 688 /* Creates a bucket and inserts it in 'table' with the given 'hash' and 'fixed'
 689  * values.  Returns the new bucket. */
 690 static struct cls_bucket *
 691 create_bucket(struct hmap *table, size_t hash, const flow_t *fixed)
 692 {
 693     struct cls_bucket *bucket = xmalloc(sizeof *bucket);
 694     list_init(&bucket->rules);
 695     bucket->fixed = *fixed;
 696     hmap_insert(table, &bucket->hmap_node, hash);
 697     return bucket;
 698 }
 699
 700 /* Returns true if the 'n' bytes in 'a' and 'b' are equal, false otherwise. */
 701 static inline bool ALWAYS_INLINE
 702 equal_bytes(const void *a, const void *b, size_t n)
 703 {
 704 #ifdef __i386__
 705     /* For some reason GCC generates stupid code for memcmp() of small
 706      * constant integer lengths.  Help it out.
 707      *
 708      * This function is always inlined, and it is always called with 'n' as a
 709      * compile-time constant, so the switch statement gets optimized out and
 710      * this whole function just expands to an instruction or two. */
 711     switch (n) {
 712     case 1:
 713         return *(uint8_t *) a == *(uint8_t *) b;
 714
 715     case 2:
 716         return *(uint16_t *) a == *(uint16_t *) b;
 717
 718     case 4:
 719         return *(uint32_t *) a == *(uint32_t *) b;
 720
 721     case 6:
 722         return (*(uint32_t *) a == *(uint32_t *) b
 723                 && ((uint16_t *) a)[2] == ((uint16_t *) b)[2]);
 724
 725     default:
 726         abort();
 727     }
 728 #else
 729     /* I hope GCC is smarter on your platform. */
 730     return !memcmp(a, b, n);
 731 #endif
 732 }
 733
 734 /* Returns the 32-bit unsigned integer at 'p'. */
 735 static inline uint32_t
 736 read_uint32(const void *p)
 737 {
 738     /* GCC optimizes this into a single machine instruction on x86. */
 739     uint32_t x;
 740     memcpy(&x, p, sizeof x);
 741     return x;
 742 }
 743
 744 /* Compares the specified field in 'a' and 'b'.  Returns true if the fields are
 745  * equal, or if the ofp_match wildcard bits in 'wildcards' are set such that
 746  * non-equal values may be ignored.  'nw_src_mask' and 'nw_dst_mask' must be
 747  * those that would be set for 'wildcards' by cls_rule_set_masks().
 748  *
 749  * The compared field is the one with wildcard bit or bits 'field_wc', offset
 750  * 'rule_ofs' within cls_rule's "fields" member, and length 'len', in bytes. */
 751 static inline bool ALWAYS_INLINE
 752 field_matches(const flow_t *a_, const flow_t *b_,
 753               uint32_t wildcards, uint32_t nw_src_mask, uint32_t nw_dst_mask,
 754               uint32_t field_wc, int ofs, int len)
 755 {
 756     /* This function is always inlined, and it is always called with 'field_wc'
 757      * as a compile-time constant, so the "if" conditionals here generate no
 758      * code. */
 759     const void *a = (const uint8_t *) a_ + ofs;
 760     const void *b = (const uint8_t *) b_ + ofs;
 761     if (!(field_wc & (field_wc - 1))) {
 762         /* Handle all the single-bit wildcard cases. */
 763         return wildcards & field_wc || equal_bytes(a, b, len);
 764     } else if (field_wc == OFPFW_NW_SRC_MASK ||
 765                field_wc == OFPFW_NW_DST_MASK) {
 766         uint32_t a_ip = read_uint32(a);
 767         uint32_t b_ip = read_uint32(b);
 768         uint32_t mask = (field_wc == OFPFW_NW_SRC_MASK
 769                          ? nw_src_mask : nw_dst_mask);
 770         return ((a_ip ^ b_ip) & mask) == 0;
 771     } else {
 772         abort();
 773     }
 774 }
 775
 776 /* Returns true if 'a' and 'b' match, ignoring fields for which the wildcards
 777  * in 'wildcards' are set.  'nw_src_mask' and 'nw_dst_mask' must be those that
 778  * would be set for 'wildcards' by cls_rule_set_masks().  'field_idx' is the
 779  * index of the first field to be compared; fields before 'field_idx' are
 780  * assumed to match.  (Always returns true if 'field_idx' is CLS_N_FIELDS.) */
 781 static bool
 782 rules_match(const struct cls_rule *a, const struct cls_rule *b,
 783             uint32_t wildcards, uint32_t nw_src_mask, uint32_t nw_dst_mask,
 784             int field_idx)
 785 {
 786     /* This is related to Duff's device (see
 787      * http://en.wikipedia.org/wiki/Duff's_device).  */
 788     switch (field_idx) {
 789 #define CLS_FIELD(WILDCARDS, MEMBER, NAME)                          \
 790         case CLS_F_IDX_##NAME:                                      \
 791             if (!field_matches(&a->flow, &b->flow,                  \
 792                                wildcards, nw_src_mask, nw_dst_mask, \
 793                                WILDCARDS, offsetof(flow_t, MEMBER), \
 794                                sizeof a->flow.MEMBER)) {            \
 795                 return false;                                       \
 796             }                                                       \
 797         /* Fall though */
 798         CLS_FIELDS
 799 #undef CLS_FIELD
 800     }
 801     return true;
 802 }
 803
 804 /* Returns true if 'fixed' and 'wild' match.  All fields in 'fixed' must have
 805  * fixed values; 'wild' may contain wildcards.
 806  *
 807  * 'field_idx' is the index of the first field to be compared; fields before
 808  * 'field_idx' are assumed to match.  Always returns true if 'field_idx' is
 809  * CLS_N_FIELDS. */
 810 static bool
 811 rules_match_1wild(const struct cls_rule *fixed, const struct cls_rule *wild,
 812                   int field_idx)
 813 {
 814     return rules_match(fixed, wild, wild->wc.wildcards, wild->wc.nw_src_mask,
 815                        wild->wc.nw_dst_mask, field_idx);
 816 }
 817
 818 /* Returns true if 'wild1' and 'wild2' match, that is, if their fields
 819  * are equal modulo wildcards in 'wild1' or 'wild2'.
 820  *
 821  * 'field_idx' is the index of the first field to be compared; fields before
 822  * 'field_idx' are assumed to match.  Always returns true if 'field_idx' is
 823  * CLS_N_FIELDS. */
 824 static bool
 825 rules_match_2wild(const struct cls_rule *wild1, const struct cls_rule *wild2,
 826                   int field_idx)
 827 {
 828     return rules_match(wild1, wild2,
 829                        wild1->wc.wildcards | wild2->wc.wildcards,
 830                        wild1->wc.nw_src_mask & wild2->wc.nw_src_mask,
 831                        wild1->wc.nw_dst_mask & wild2->wc.nw_dst_mask,
 832                        field_idx);
 833 }
 834
 835 /* Searches 'bucket' for a rule that matches 'target'.  Returns the
 836  * highest-priority match, if one is found, or a null pointer if there is no
 837  * match.
 838  *
 839  * 'field_idx' must be the index of the first wildcarded field in 'bucket'. */
 840 static struct cls_rule *
 841 search_bucket(struct cls_bucket *bucket, int field_idx,
 842               const struct cls_rule *target)
 843 {
 844     struct cls_rule *pos;
 845
 846     if (!equal_fields(&bucket->fixed, &target->flow, field_idx)) {
 847         return NULL;
 848     }
 849
 850     LIST_FOR_EACH (pos, struct cls_rule, node.list, &bucket->rules) {
 851         if (rules_match_1wild(target, pos, field_idx)) {
 852             return pos;
 853         }
 854     }
 855     return NULL;
 856 }
 857
 858 /* Searches 'table' for a rule that matches 'target'.  Returns the
 859  * highest-priority match, if one is found, or a null pointer if there is no
 860  * match.
 861  *
 862  * 'field_idx' must be the index of the first wildcarded field in 'table'. */
 863 static struct cls_rule *
 864 search_table(const struct hmap *table, int field_idx,
 865              const struct cls_rule *target)
 866 {
 867     struct cls_bucket *bucket;
 868
 869     switch (hmap_count(table)) {
 870         /* In these special cases there's no need to hash.  */
 871     case 0:
 872         return NULL;
 873     case 1:
 874         bucket = CONTAINER_OF(hmap_first(table), struct cls_bucket, hmap_node);
 875         return search_bucket(bucket, field_idx, target);
 876     }
 877
 878     HMAP_FOR_EACH_WITH_HASH (bucket, struct cls_bucket, hmap_node,
 879                              hash_fields(&target->flow, field_idx), table) {
 880         struct cls_rule *rule = search_bucket(bucket, field_idx, target);
 881         if (rule) {
 882             return rule;
 883         }
 884     }
 885     return NULL;
 886 }
 887
 888 static struct cls_rule *
 889 search_exact_table(const struct classifier *cls, size_t hash,
 890                    const flow_t *target)
 891 {
 892     struct cls_rule *rule;
 893
 894     HMAP_FOR_EACH_WITH_HASH (rule, struct cls_rule, node.hmap,
 895                              hash, &cls->exact_table) {
 896         if (flow_equal(&rule->flow, target)) {
 897             return rule;
 898         }
 899     }
 900     return NULL;
 901 }