classifier: New function cls_rule_to_string().
[openvswitch] / 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 }