lib/classifier.c

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