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