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