2 * Copyright (c) 2009, 2010 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #define CLASSIFIER_H 1
22 * This flow classifier assumes that we can arrange the fields in a flow in an
23 * order such that the set of wildcarded fields in a rule tend to fall toward
24 * the end of the ordering. That is, if field F is wildcarded, then all the
25 * fields after F tend to be wildcarded as well. If this assumption is
26 * violated, then the classifier will still classify flows correctly, but its
27 * performance will suffer.
29 * The classifier uses a collection of CLS_N_FIELDS hash tables for wildcarded
30 * flows. Each of these tables contains the flows that wildcard a given field
31 * and do not wildcard any of the fields that precede F in the ordering. The
32 * key for each hash table is the value of the fields preceding F that are not
33 * wildcarded. All the flows that fall within a table and have the same key
34 * are kept as a linked list ordered from highest to lowest priority.
36 * The classifier also maintains a separate hash table of exact-match flows.
38 * To search the classifier we first search the table of exact-match flows,
39 * since exact-match flows always have highest priority. If there is a match,
40 * we're done. Otherwise, we search each of the CLS_N_FIELDS hash tables in
41 * turn, looking for the highest-priority match, and return it (if any).
47 #include "openflow/nicira-ext.h"
48 #include "openflow/openflow.h"
50 /* Number of bytes of fields in a rule. */
51 #define CLS_N_BYTES 37
55 * This definition sets the ordering of fields, which is important for
56 * performance (see above). To adjust the ordering, change the order of the
59 /* struct flow all-caps */ \
60 /* wildcard bit(s) member name name */ \
61 /* ----------------- ----------- -------- */ \
62 CLS_FIELD(OFPFW_IN_PORT, in_port, IN_PORT) \
63 CLS_FIELD(NXFW_TUN_ID, tun_id, TUN_ID) \
64 CLS_FIELD(OFPFW_DL_VLAN, dl_vlan, DL_VLAN) \
65 CLS_FIELD(OFPFW_DL_VLAN_PCP, dl_vlan_pcp, DL_VLAN_PCP) \
66 CLS_FIELD(OFPFW_DL_SRC, dl_src, DL_SRC) \
67 CLS_FIELD(OFPFW_DL_DST, dl_dst, DL_DST) \
68 CLS_FIELD(OFPFW_DL_TYPE, dl_type, DL_TYPE) \
69 CLS_FIELD(OFPFW_NW_SRC_MASK, nw_src, NW_SRC) \
70 CLS_FIELD(OFPFW_NW_DST_MASK, nw_dst, NW_DST) \
71 CLS_FIELD(OFPFW_NW_PROTO, nw_proto, NW_PROTO) \
72 CLS_FIELD(OFPFW_NW_TOS, nw_tos, NW_TOS) \
73 CLS_FIELD(OFPFW_TP_SRC, tp_src, TP_SRC) \
74 CLS_FIELD(OFPFW_TP_DST, tp_dst, TP_DST)
78 * (These are also indexed into struct classifier's 'tables' array.) */
80 #define CLS_FIELD(WILDCARDS, MEMBER, NAME) CLS_F_IDX_##NAME,
83 CLS_F_IDX_EXACT, /* Exact-match table. */
84 CLS_N_FIELDS = CLS_F_IDX_EXACT
87 /* Field information. */
89 int ofs; /* Offset in struct flow. */
90 int len; /* Length in bytes. */
91 uint32_t wildcards; /* OFPFW_* bit or bits for this field. */
92 const char *name; /* Name (for debugging). */
94 extern const struct cls_field cls_fields[CLS_N_FIELDS + 1];
96 /* A flow classifier. */
98 int n_rules; /* Sum of hmap_count() over tables[]. */
99 struct hmap tables[CLS_N_FIELDS]; /* Contain cls_bucket elements. */
100 struct hmap exact_table; /* Contain cls_rule elements. */
103 /* A group of rules with the same fixed values for initial fields. */
105 struct hmap_node hmap_node; /* Within struct classifier 'tables'. */
106 struct list rules; /* In order from highest to lowest priority. */
107 struct flow fixed; /* Values for fixed fields. */
110 /* A flow classification rule.
112 * Use cls_rule_from_flow() or cls_rule_from_match() to initialize a cls_rule
113 * or you will almost certainly not initialize 'table_idx' correctly, with
114 * disastrous results! */
117 struct list list; /* Within struct cls_bucket 'rules'. */
118 struct hmap_node hmap; /* Within struct classifier 'exact_table'. */
120 struct flow flow; /* All field values. */
121 struct flow_wildcards wc; /* Wildcards for fields. */
122 unsigned int priority; /* Larger numbers are higher priorities. */
123 unsigned int table_idx; /* Index into struct classifier 'tables'. */
126 void cls_rule_from_flow(const struct flow *, uint32_t wildcards,
127 unsigned int priority, struct cls_rule *);
128 void cls_rule_from_match(const struct ofp_match *, unsigned int priority,
129 bool tun_id_from_cookie, uint64_t cookie,
131 char *cls_rule_to_string(const struct cls_rule *);
132 void cls_rule_print(const struct cls_rule *);
133 void cls_rule_moved(struct classifier *,
134 struct cls_rule *old, struct cls_rule *new);
135 void cls_rule_replace(struct classifier *, const struct cls_rule *old,
136 struct cls_rule *new);
138 void classifier_init(struct classifier *);
139 void classifier_destroy(struct classifier *);
140 bool classifier_is_empty(const struct classifier *);
141 int classifier_count(const struct classifier *);
142 int classifier_count_exact(const struct classifier *);
143 struct cls_rule *classifier_insert(struct classifier *, struct cls_rule *);
144 void classifier_insert_exact(struct classifier *, struct cls_rule *);
145 void classifier_remove(struct classifier *, struct cls_rule *);
146 struct cls_rule *classifier_lookup(const struct classifier *,
147 const struct flow *);
148 struct cls_rule *classifier_lookup_wild(const struct classifier *,
149 const struct flow *);
150 struct cls_rule *classifier_lookup_exact(const struct classifier *,
151 const struct flow *);
152 bool classifier_rule_overlaps(const struct classifier *, const struct flow *,
153 uint32_t wildcards, unsigned int priority);
155 typedef void cls_cb_func(struct cls_rule *, void *aux);
158 CLS_INC_EXACT = 1 << 0, /* Include exact-match flows? */
159 CLS_INC_WILD = 1 << 1, /* Include flows with wildcards? */
160 CLS_INC_ALL = CLS_INC_EXACT | CLS_INC_WILD
162 void classifier_for_each(const struct classifier *, int include,
163 cls_cb_func *, void *aux);
164 void classifier_for_each_match(const struct classifier *,
165 const struct cls_rule *,
166 int include, cls_cb_func *, void *aux);
167 struct cls_rule *classifier_find_rule_exactly(const struct classifier *,
168 const struct flow *target,
170 unsigned int priority);
172 #define CLASSIFIER_FOR_EACH_EXACT_RULE(RULE, MEMBER, CLS) \
173 HMAP_FOR_EACH (RULE, MEMBER.node.hmap, &(CLS)->exact_table)
175 #define CLASSIFIER_FOR_EACH_EXACT_RULE_SAFE(RULE, NEXT, MEMBER, CLS) \
176 HMAP_FOR_EACH_SAFE (RULE, NEXT, MEMBER.node.hmap, &(CLS)->exact_table)
178 #endif /* classifier.h */