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