]>
Commit | Line | Data |
---|---|---|
38c449e0 JR |
1 | /* |
2 | * Copyright (c) 2014 Nicira, Inc. | |
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 | #ifndef CLASSIFIER_PRIVATE_H | |
18 | #define CLASSIFIER_PRIVATE_H 1 | |
19 | ||
c501b427 | 20 | #include "cmap.h" |
38c449e0 JR |
21 | #include "flow.h" |
22 | #include "hash.h" | |
c501b427 | 23 | #include "rculist.h" |
38c449e0 JR |
24 | #include "tag.h" |
25 | ||
26 | /* Classifier internal definitions, subject to change at any time. */ | |
27 | ||
28 | /* A set of rules that all have the same fields wildcarded. */ | |
29 | struct cls_subtable { | |
30 | /* The fields are only used by writers and iterators. */ | |
31 | struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */ | |
32 | ||
33 | /* The fields are only used by writers. */ | |
34 | int n_rules OVS_GUARDED; /* Number of rules, including | |
35 | * duplicates. */ | |
f80028fe | 36 | int max_priority OVS_GUARDED; /* Max priority of any rule in subtable. */ |
38c449e0 JR |
37 | unsigned int max_count OVS_GUARDED; /* Count of max_priority rules. */ |
38 | ||
39 | /* These fields are accessed by readers who care about wildcarding. */ | |
f80028fe JR |
40 | const tag_type tag; /* Tag generated from mask for partitioning. */ |
41 | const uint8_t n_indices; /* How many indices to use. */ | |
42 | const uint8_t index_ofs[CLS_MAX_INDICES]; /* u32 segment boundaries. */ | |
38c449e0 JR |
43 | unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask' |
44 | * (runtime configurable). */ | |
f80028fe | 45 | const int ports_mask_len; |
38c449e0 JR |
46 | struct cmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */ |
47 | rcu_trie_ptr ports_trie; /* NULL if none. */ | |
48 | ||
49 | /* These fields are accessed by all readers. */ | |
f80028fe JR |
50 | struct cmap rules; /* Contains 'cls_match'es. */ |
51 | const struct minimask mask; /* Wildcards for fields. */ | |
38c449e0 JR |
52 | /* 'mask' must be the last field. */ |
53 | }; | |
54 | ||
55 | /* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata | |
56 | * field) with tags for the "cls_subtable"s that contain rules that match that | |
57 | * metadata value. */ | |
58 | struct cls_partition { | |
59 | struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */ | |
60 | ovs_be64 metadata; /* metadata value for this partition. */ | |
61 | tag_type tags; /* OR of each flow's cls_subtable tag. */ | |
62 | struct tag_tracker tracker OVS_GUARDED; /* Tracks the bits in 'tags'. */ | |
63 | }; | |
64 | ||
65 | /* Internal representation of a rule in a "struct cls_subtable". */ | |
66 | struct cls_match { | |
f80028fe | 67 | /* Accessed by everybody. */ |
c501b427 | 68 | struct rculist list OVS_GUARDED; /* Identical, lower-priority rules. */ |
38c449e0 JR |
69 | |
70 | /* Accessed only by writers. */ | |
71 | struct cls_partition *partition OVS_GUARDED; | |
72 | ||
73 | /* Accessed by readers interested in wildcarding. */ | |
f80028fe | 74 | const int priority; /* Larger numbers are higher priorities. */ |
38c449e0 JR |
75 | struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's |
76 | * 'indices'. */ | |
77 | /* Accessed by all readers. */ | |
78 | struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */ | |
f80028fe JR |
79 | const struct cls_rule *cls_rule; |
80 | const struct miniflow flow; /* Matching rule. Mask is in the subtable. */ | |
38c449e0 JR |
81 | /* 'flow' must be the last field. */ |
82 | }; | |
83 | ||
84 | /* A longest-prefix match tree. */ | |
85 | struct trie_node { | |
86 | uint32_t prefix; /* Prefix bits for this node, MSB first. */ | |
87 | uint8_t n_bits; /* Never zero, except for the root node. */ | |
88 | unsigned int n_rules; /* Number of rules that have this prefix. */ | |
89 | rcu_trie_ptr edges[2]; /* Both NULL if leaf. */ | |
90 | }; | |
91 | ||
92 | /* Max bits per node. Must fit in struct trie_node's 'prefix'. | |
93 | * Also tested with 16, 8, and 5 to stress the implementation. */ | |
94 | #define TRIE_PREFIX_BITS 32 | |
95 | \f | |
96 | /* flow/miniflow/minimask/minimatch utilities. | |
97 | * These are only used by the classifier, so place them here to allow | |
98 | * for better optimization. */ | |
99 | ||
100 | static inline uint64_t | |
101 | miniflow_get_map_in_range(const struct miniflow *miniflow, | |
102 | uint8_t start, uint8_t end, unsigned int *offset) | |
103 | { | |
104 | uint64_t map = miniflow->map; | |
105 | *offset = 0; | |
106 | ||
107 | if (start > 0) { | |
108 | uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */ | |
109 | *offset = count_1bits(map & msk); | |
110 | map &= ~msk; | |
111 | } | |
112 | if (end < FLOW_U32S) { | |
113 | uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */ | |
114 | map &= msk; | |
115 | } | |
116 | return map; | |
117 | } | |
118 | ||
119 | /* Returns a hash value for the bits of 'flow' where there are 1-bits in | |
120 | * 'mask', given 'basis'. | |
121 | * | |
122 | * The hash values returned by this function are the same as those returned by | |
123 | * miniflow_hash_in_minimask(), only the form of the arguments differ. */ | |
124 | static inline uint32_t | |
125 | flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask, | |
126 | uint32_t basis) | |
127 | { | |
128 | const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); | |
129 | const uint32_t *flow_u32 = (const uint32_t *)flow; | |
130 | const uint32_t *p = mask_values; | |
131 | uint32_t hash; | |
132 | uint64_t map; | |
133 | ||
134 | hash = basis; | |
135 | for (map = mask->masks.map; map; map = zero_rightmost_1bit(map)) { | |
136 | hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++); | |
137 | } | |
138 | ||
139 | return hash_finish(hash, (p - mask_values) * 4); | |
140 | } | |
141 | ||
142 | /* Returns a hash value for the bits of 'flow' where there are 1-bits in | |
143 | * 'mask', given 'basis'. | |
144 | * | |
145 | * The hash values returned by this function are the same as those returned by | |
146 | * flow_hash_in_minimask(), only the form of the arguments differ. */ | |
147 | static inline uint32_t | |
148 | miniflow_hash_in_minimask(const struct miniflow *flow, | |
149 | const struct minimask *mask, uint32_t basis) | |
150 | { | |
151 | const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); | |
152 | const uint32_t *p = mask_values; | |
153 | uint32_t hash = basis; | |
154 | uint32_t flow_u32; | |
155 | ||
156 | MINIFLOW_FOR_EACH_IN_MAP(flow_u32, flow, mask->masks.map) { | |
157 | hash = hash_add(hash, flow_u32 & *p++); | |
158 | } | |
159 | ||
160 | return hash_finish(hash, (p - mask_values) * 4); | |
161 | } | |
162 | ||
163 | /* Returns a hash value for the bits of range [start, end) in 'flow', | |
164 | * where there are 1-bits in 'mask', given 'hash'. | |
165 | * | |
166 | * The hash values returned by this function are the same as those returned by | |
167 | * minimatch_hash_range(), only the form of the arguments differ. */ | |
168 | static inline uint32_t | |
169 | flow_hash_in_minimask_range(const struct flow *flow, | |
170 | const struct minimask *mask, | |
171 | uint8_t start, uint8_t end, uint32_t *basis) | |
172 | { | |
173 | const uint32_t *mask_values = miniflow_get_u32_values(&mask->masks); | |
174 | const uint32_t *flow_u32 = (const uint32_t *)flow; | |
175 | unsigned int offset; | |
176 | uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, | |
177 | &offset); | |
178 | const uint32_t *p = mask_values + offset; | |
179 | uint32_t hash = *basis; | |
180 | ||
181 | for (; map; map = zero_rightmost_1bit(map)) { | |
182 | hash = hash_add(hash, flow_u32[raw_ctz(map)] & *p++); | |
183 | } | |
184 | ||
185 | *basis = hash; /* Allow continuation from the unfinished value. */ | |
186 | return hash_finish(hash, (p - mask_values) * 4); | |
187 | } | |
188 | ||
189 | /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */ | |
190 | static inline void | |
191 | flow_wildcards_fold_minimask(struct flow_wildcards *wc, | |
192 | const struct minimask *mask) | |
193 | { | |
194 | flow_union_with_miniflow(&wc->masks, &mask->masks); | |
195 | } | |
196 | ||
197 | /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask | |
198 | * in range [start, end). */ | |
199 | static inline void | |
200 | flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, | |
201 | const struct minimask *mask, | |
202 | uint8_t start, uint8_t end) | |
203 | { | |
204 | uint32_t *dst_u32 = (uint32_t *)&wc->masks; | |
205 | unsigned int offset; | |
206 | uint64_t map = miniflow_get_map_in_range(&mask->masks, start, end, | |
207 | &offset); | |
208 | const uint32_t *p = miniflow_get_u32_values(&mask->masks) + offset; | |
209 | ||
210 | for (; map; map = zero_rightmost_1bit(map)) { | |
211 | dst_u32[raw_ctz(map)] |= *p++; | |
212 | } | |
213 | } | |
214 | ||
215 | /* Returns a hash value for 'flow', given 'basis'. */ | |
216 | static inline uint32_t | |
217 | miniflow_hash(const struct miniflow *flow, uint32_t basis) | |
218 | { | |
219 | const uint32_t *values = miniflow_get_u32_values(flow); | |
220 | const uint32_t *p = values; | |
221 | uint32_t hash = basis; | |
222 | uint64_t hash_map = 0; | |
223 | uint64_t map; | |
224 | ||
225 | for (map = flow->map; map; map = zero_rightmost_1bit(map)) { | |
226 | if (*p) { | |
227 | hash = hash_add(hash, *p); | |
228 | hash_map |= rightmost_1bit(map); | |
229 | } | |
230 | p++; | |
231 | } | |
232 | hash = hash_add(hash, hash_map); | |
233 | hash = hash_add(hash, hash_map >> 32); | |
234 | ||
235 | return hash_finish(hash, p - values); | |
236 | } | |
237 | ||
238 | /* Returns a hash value for 'mask', given 'basis'. */ | |
239 | static inline uint32_t | |
240 | minimask_hash(const struct minimask *mask, uint32_t basis) | |
241 | { | |
242 | return miniflow_hash(&mask->masks, basis); | |
243 | } | |
244 | ||
245 | /* Returns a hash value for 'match', given 'basis'. */ | |
246 | static inline uint32_t | |
247 | minimatch_hash(const struct minimatch *match, uint32_t basis) | |
248 | { | |
249 | return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis)); | |
250 | } | |
251 | ||
252 | /* Returns a hash value for the bits of range [start, end) in 'minimatch', | |
253 | * given 'basis'. | |
254 | * | |
255 | * The hash values returned by this function are the same as those returned by | |
256 | * flow_hash_in_minimask_range(), only the form of the arguments differ. */ | |
257 | static inline uint32_t | |
258 | minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end, | |
259 | uint32_t *basis) | |
260 | { | |
261 | unsigned int offset; | |
262 | const uint32_t *p, *q; | |
263 | uint32_t hash = *basis; | |
264 | int n, i; | |
265 | ||
266 | n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end, | |
267 | &offset)); | |
268 | q = miniflow_get_u32_values(&match->mask.masks) + offset; | |
269 | p = miniflow_get_u32_values(&match->flow) + offset; | |
270 | ||
271 | for (i = 0; i < n; i++) { | |
272 | hash = hash_add(hash, p[i] & q[i]); | |
273 | } | |
274 | *basis = hash; /* Allow continuation from the unfinished value. */ | |
275 | return hash_finish(hash, (offset + n) * 4); | |
276 | } | |
277 | ||
278 | #endif |