lib/classifier.c

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