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