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