Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 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 : : #ifndef FLOW_H
17 : : #define FLOW_H 1
18 : :
19 : : #include <sys/types.h>
20 : : #include <netinet/in.h>
21 : : #include <netinet/icmp6.h>
22 : : #include <stdbool.h>
23 : : #include <stdint.h>
24 : : #include <string.h>
25 : : #include "bitmap.h"
26 : : #include "byte-order.h"
27 : : #include "openvswitch/compiler.h"
28 : : #include "openflow/nicira-ext.h"
29 : : #include "openflow/openflow.h"
30 : : #include "openvswitch/flow.h"
31 : : #include "packets.h"
32 : : #include "hash.h"
33 : : #include "util.h"
34 : :
35 : : struct dpif_flow_stats;
36 : : struct ds;
37 : : struct flow_wildcards;
38 : : struct minimask;
39 : : struct dp_packet;
40 : : struct pkt_metadata;
41 : : struct match;
42 : :
43 : : /* Some flow fields are mutually exclusive or only appear within the flow
44 : : * pipeline. IPv6 headers are bigger than IPv4 and MPLS, and IPv6 ND packets
45 : : * are bigger than TCP,UDP and IGMP packets. */
46 : : #define FLOW_MAX_PACKET_U64S (FLOW_U64S \
47 : : /* Unused in datapath */ - FLOW_U64_SIZE(regs) \
48 : : - FLOW_U64_SIZE(metadata) \
49 : : /* L2.5/3 */ - FLOW_U64_SIZE(nw_src) /* incl. nw_dst */ \
50 : : - FLOW_U64_SIZE(mpls_lse) \
51 : : /* L4 */ - FLOW_U64_SIZE(tp_src) \
52 : : )
53 : :
54 : : extern const uint8_t flow_segment_u64s[];
55 : :
56 : : #define FLOW_U64_OFFSET(FIELD) \
57 : : (offsetof(struct flow, FIELD) / sizeof(uint64_t))
58 : : #define FLOW_U64_OFFREM(FIELD) \
59 : : (offsetof(struct flow, FIELD) % sizeof(uint64_t))
60 : :
61 : : /* Number of 64-bit units spanned by a 'FIELD'. */
62 : : #define FLOW_U64_SIZE(FIELD) \
63 : : DIV_ROUND_UP(FLOW_U64_OFFREM(FIELD) + MEMBER_SIZEOF(struct flow, FIELD), \
64 : : sizeof(uint64_t))
65 : :
66 : : void flow_extract(struct dp_packet *, struct flow *);
67 : :
68 : : void flow_zero_wildcards(struct flow *, const struct flow_wildcards *);
69 : : void flow_unwildcard_tp_ports(const struct flow *, struct flow_wildcards *);
70 : : void flow_get_metadata(const struct flow *, struct match *flow_metadata);
71 : :
72 : : const char *ct_state_to_string(uint32_t state);
73 : : char *flow_to_string(const struct flow *);
74 : : void format_flags(struct ds *ds, const char *(*bit_to_string)(uint32_t),
75 : : uint32_t flags, char del);
76 : : void format_flags_masked(struct ds *ds, const char *name,
77 : : const char *(*bit_to_string)(uint32_t),
78 : : uint32_t flags, uint32_t mask, uint32_t max_mask);
79 : : int parse_flags(const char *s, const char *(*bit_to_string)(uint32_t),
80 : : char end, const char *field_name, char **res_string,
81 : : uint32_t *res_flags, uint32_t allowed, uint32_t *res_mask);
82 : :
83 : : void flow_format(struct ds *, const struct flow *);
84 : : void flow_print(FILE *, const struct flow *);
85 : : static inline int flow_compare_3way(const struct flow *, const struct flow *);
86 : : static inline bool flow_equal(const struct flow *, const struct flow *);
87 : : static inline size_t flow_hash(const struct flow *, uint32_t basis);
88 : :
89 : : void flow_set_dl_vlan(struct flow *, ovs_be16 vid);
90 : : void flow_set_vlan_vid(struct flow *, ovs_be16 vid);
91 : : void flow_set_vlan_pcp(struct flow *, uint8_t pcp);
92 : :
93 : : int flow_count_mpls_labels(const struct flow *, struct flow_wildcards *);
94 : : int flow_count_common_mpls_labels(const struct flow *a, int an,
95 : : const struct flow *b, int bn,
96 : : struct flow_wildcards *wc);
97 : : void flow_push_mpls(struct flow *, int n, ovs_be16 mpls_eth_type,
98 : : struct flow_wildcards *);
99 : : bool flow_pop_mpls(struct flow *, int n, ovs_be16 eth_type,
100 : : struct flow_wildcards *);
101 : : void flow_set_mpls_label(struct flow *, int idx, ovs_be32 label);
102 : : void flow_set_mpls_ttl(struct flow *, int idx, uint8_t ttl);
103 : : void flow_set_mpls_tc(struct flow *, int idx, uint8_t tc);
104 : : void flow_set_mpls_bos(struct flow *, int idx, uint8_t stack);
105 : : void flow_set_mpls_lse(struct flow *, int idx, ovs_be32 lse);
106 : :
107 : : void flow_compose(struct dp_packet *, const struct flow *);
108 : :
109 : : bool parse_ipv6_ext_hdrs(const void **datap, size_t *sizep, uint8_t *nw_proto,
110 : : uint8_t *nw_frag);
111 : : ovs_be16 parse_dl_type(const struct eth_header *data_, size_t size);
112 : :
113 : : static inline uint64_t
114 : 1638 : flow_get_xreg(const struct flow *flow, int idx)
115 : : {
116 : 1638 : return ((uint64_t) flow->regs[idx * 2] << 32) | flow->regs[idx * 2 + 1];
117 : : }
118 : :
119 : : static inline void
120 : 296 : flow_set_xreg(struct flow *flow, int idx, uint64_t value)
121 : : {
122 : 296 : flow->regs[idx * 2] = value >> 32;
123 : 296 : flow->regs[idx * 2 + 1] = value;
124 : 296 : }
125 : :
126 : : static inline ovs_u128
127 : 315104 : flow_get_xxreg(const struct flow *flow, int idx)
128 : : {
129 : : ovs_u128 value;
130 : :
131 : 315104 : value.u64.hi = (uint64_t) flow->regs[idx * 4] << 32;
132 : 315104 : value.u64.hi |= flow->regs[idx * 4 + 1];
133 : 315104 : value.u64.lo = (uint64_t) flow->regs[idx * 4 + 2] << 32;
134 : 315104 : value.u64.lo |= flow->regs[idx * 4 + 3];
135 : :
136 : 315104 : return value;
137 : : }
138 : :
139 : : static inline void
140 : 311788 : flow_set_xxreg(struct flow *flow, int idx, ovs_u128 value)
141 : : {
142 : 311788 : flow->regs[idx * 4] = value.u64.hi >> 32;
143 : 311788 : flow->regs[idx * 4 + 1] = value.u64.hi;
144 : 311788 : flow->regs[idx * 4 + 2] = value.u64.lo >> 32;
145 : 311788 : flow->regs[idx * 4 + 3] = value.u64.lo;
146 : 311788 : }
147 : :
148 : : static inline int
149 : 2114000 : flow_compare_3way(const struct flow *a, const struct flow *b)
150 : : {
151 : 2114000 : return memcmp(a, b, sizeof *a);
152 : : }
153 : :
154 : : static inline bool
155 : 2113879 : flow_equal(const struct flow *a, const struct flow *b)
156 : : {
157 : 2113879 : return !flow_compare_3way(a, b);
158 : : }
159 : :
160 : : static inline size_t
161 : 4371414 : flow_hash(const struct flow *flow, uint32_t basis)
162 : : {
163 : 4371414 : return hash_bytes64((const uint64_t *)flow, sizeof *flow, basis);
164 : : }
165 : :
166 : : static inline uint16_t
167 : 6766958 : ofp_to_u16(ofp_port_t ofp_port)
168 : : {
169 : 6766958 : return (OVS_FORCE uint16_t) ofp_port;
170 : : }
171 : :
172 : : static inline uint32_t
173 : 361724 : odp_to_u32(odp_port_t odp_port)
174 : : {
175 : 361724 : return (OVS_FORCE uint32_t) odp_port;
176 : : }
177 : :
178 : : static inline uint32_t
179 : 47934 : ofp11_to_u32(ofp11_port_t ofp11_port)
180 : : {
181 : 47934 : return (OVS_FORCE uint32_t) ofp11_port;
182 : : }
183 : :
184 : : static inline ofp_port_t
185 : 5521323 : u16_to_ofp(uint16_t port)
186 : : {
187 : 5521323 : return OFP_PORT_C(port);
188 : : }
189 : :
190 : : static inline odp_port_t
191 : 231263 : u32_to_odp(uint32_t port)
192 : : {
193 : 231263 : return ODP_PORT_C(port);
194 : : }
195 : :
196 : : static inline ofp11_port_t
197 : : u32_to_ofp11(uint32_t port)
198 : : {
199 : : return OFP11_PORT_C(port);
200 : : }
201 : :
202 : : static inline uint32_t
203 : 977954 : hash_ofp_port(ofp_port_t ofp_port)
204 : : {
205 : 977954 : return hash_int(ofp_to_u16(ofp_port), 0);
206 : : }
207 : :
208 : : static inline uint32_t
209 : 90414 : hash_odp_port(odp_port_t odp_port)
210 : : {
211 : 90414 : return hash_int(odp_to_u32(odp_port), 0);
212 : : }
213 : :
214 : : uint32_t flow_hash_5tuple(const struct flow *flow, uint32_t basis);
215 : : uint32_t flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis);
216 : : uint32_t flow_hash_symmetric_l3l4(const struct flow *flow, uint32_t basis,
217 : : bool inc_udp_ports );
218 : :
219 : : /* Initialize a flow with random fields that matter for nx_hash_fields. */
220 : : void flow_random_hash_fields(struct flow *);
221 : : void flow_mask_hash_fields(const struct flow *, struct flow_wildcards *,
222 : : enum nx_hash_fields);
223 : : uint32_t flow_hash_fields(const struct flow *, enum nx_hash_fields,
224 : : uint16_t basis);
225 : : const char *flow_hash_fields_to_str(enum nx_hash_fields);
226 : : bool flow_hash_fields_valid(enum nx_hash_fields);
227 : :
228 : : uint32_t flow_hash_in_wildcards(const struct flow *,
229 : : const struct flow_wildcards *,
230 : : uint32_t basis);
231 : :
232 : : bool flow_equal_except(const struct flow *a, const struct flow *b,
233 : : const struct flow_wildcards *);
234 : :
235 : : /* Bitmap for flow values. For each 1-bit the corresponding flow value is
236 : : * explicitly specified, other values are zeroes.
237 : : *
238 : : * map_t must be wide enough to hold any member of struct flow. */
239 : : typedef unsigned long long map_t;
240 : : #define MAP_T_BITS (sizeof(map_t) * CHAR_BIT)
241 : : #define MAP_1 (map_t)1
242 : : #define MAP_MAX TYPE_MAXIMUM(map_t)
243 : :
244 : : #define MAP_IS_SET(MAP, IDX) ((MAP) & (MAP_1 << (IDX)))
245 : :
246 : : /* Iterate through the indices of all 1-bits in 'MAP'. */
247 : : #define MAP_FOR_EACH_INDEX(IDX, MAP) \
248 : : ULLONG_FOR_EACH_1(IDX, MAP)
249 : :
250 : : #define FLOWMAP_UNITS DIV_ROUND_UP(FLOW_U64S, MAP_T_BITS)
251 : :
252 : : struct flowmap {
253 : : map_t bits[FLOWMAP_UNITS];
254 : : };
255 : :
256 : : #define FLOWMAP_EMPTY_INITIALIZER { { 0 } }
257 : :
258 : : static inline void flowmap_init(struct flowmap *);
259 : : static inline bool flowmap_equal(struct flowmap, struct flowmap);
260 : : static inline bool flowmap_is_set(const struct flowmap *, size_t idx);
261 : : static inline bool flowmap_are_set(const struct flowmap *, size_t idx,
262 : : unsigned int n_bits);
263 : : static inline void flowmap_set(struct flowmap *, size_t idx,
264 : : unsigned int n_bits);
265 : : static inline void flowmap_clear(struct flowmap *, size_t idx,
266 : : unsigned int n_bits);
267 : : static inline struct flowmap flowmap_or(struct flowmap, struct flowmap);
268 : : static inline struct flowmap flowmap_and(struct flowmap, struct flowmap);
269 : : static inline bool flowmap_is_empty(struct flowmap);
270 : : static inline unsigned int flowmap_n_1bits(struct flowmap);
271 : :
272 : : #define FLOWMAP_HAS_FIELD(FM, FIELD) \
273 : : flowmap_are_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
274 : :
275 : : #define FLOWMAP_SET(FM, FIELD) \
276 : : flowmap_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
277 : :
278 : : #define FLOWMAP_SET__(FM, FIELD, SIZE) \
279 : : flowmap_set(FM, FLOW_U64_OFFSET(FIELD), \
280 : : DIV_ROUND_UP(SIZE, sizeof(uint64_t)))
281 : :
282 : : /* XXX: Only works for full 64-bit units. */
283 : : #define FLOWMAP_CLEAR(FM, FIELD) \
284 : : BUILD_ASSERT_DECL(FLOW_U64_OFFREM(FIELD) == 0); \
285 : : BUILD_ASSERT_DECL(sizeof(((struct flow *)0)->FIELD) % sizeof(uint64_t) == 0); \
286 : : flowmap_clear(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
287 : :
288 : : /* Iterate through all units in 'FMAP'. */
289 : : #define FLOWMAP_FOR_EACH_UNIT(UNIT) \
290 : : for ((UNIT) = 0; (UNIT) < FLOWMAP_UNITS; (UNIT)++)
291 : :
292 : : /* Iterate through all map units in 'FMAP'. */
293 : : #define FLOWMAP_FOR_EACH_MAP(MAP, FLOWMAP) \
294 : : for (size_t unit__ = 0; \
295 : : unit__ < FLOWMAP_UNITS && ((MAP) = (FLOWMAP).bits[unit__], true); \
296 : : unit__++)
297 : :
298 : : struct flowmap_aux;
299 : : static inline bool flowmap_next_index(struct flowmap_aux *, size_t *idx);
300 : :
301 : : #define FLOWMAP_AUX_INITIALIZER(FLOWMAP) { .unit = 0, .map = (FLOWMAP) }
302 : :
303 : : /* Iterate through all struct flow u64 indices specified by 'MAP'. This is a
304 : : * slower but easier version of the FLOWMAP_FOR_EACH_MAP() &
305 : : * MAP_FOR_EACH_INDEX() combination. */
306 : : #define FLOWMAP_FOR_EACH_INDEX(IDX, MAP) \
307 : : for (struct flowmap_aux aux__ = FLOWMAP_AUX_INITIALIZER(MAP); \
308 : : flowmap_next_index(&aux__, &(IDX));)
309 : :
310 : : /* Flowmap inline implementations. */
311 : : static inline void
312 : 6292334 : flowmap_init(struct flowmap *fm)
313 : : {
314 : 6292334 : memset(fm, 0, sizeof *fm);
315 : 6292334 : }
316 : :
317 : : static inline bool
318 : 1236553 : flowmap_equal(struct flowmap a, struct flowmap b)
319 : : {
320 : 1236553 : return !memcmp(&a, &b, sizeof a);
321 : : }
322 : :
323 : : static inline bool
324 : 82358219 : flowmap_is_set(const struct flowmap *fm, size_t idx)
325 : : {
326 : 82358219 : return (fm->bits[idx / MAP_T_BITS] & (MAP_1 << (idx % MAP_T_BITS))) != 0;
327 : : }
328 : :
329 : : /* Returns 'true' if any of the 'n_bits' bits starting at 'idx' are set in
330 : : * 'fm'. 'n_bits' can be at most MAP_T_BITS. */
331 : : static inline bool
332 : 20662 : flowmap_are_set(const struct flowmap *fm, size_t idx, unsigned int n_bits)
333 : : {
334 : 20662 : map_t n_bits_mask = (MAP_1 << n_bits) - 1;
335 : 20662 : size_t unit = idx / MAP_T_BITS;
336 : :
337 : 20662 : idx %= MAP_T_BITS;
338 : :
339 [ - + ]: 20662 : if (fm->bits[unit] & (n_bits_mask << idx)) {
340 : 0 : return true;
341 : : }
342 : : /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
343 : : * false-positive array out of bounds error by GCC 4.9. */
344 [ + - ][ - + ]: 20662 : if (unit + 1 < FLOWMAP_UNITS && idx + n_bits > MAP_T_BITS) {
345 : : /* Check the remaining bits from the next unit. */
346 : 0 : return fm->bits[unit + 1] & (n_bits_mask >> (MAP_T_BITS - idx));
347 : : }
348 : 20662 : return false;
349 : : }
350 : :
351 : : /* Set the 'n_bits' consecutive bits in 'fm', starting at bit 'idx'.
352 : : * 'n_bits' can be at most MAP_T_BITS. */
353 : : static inline void
354 : 2366366 : flowmap_set(struct flowmap *fm, size_t idx, unsigned int n_bits)
355 : : {
356 : 2366366 : map_t n_bits_mask = (MAP_1 << n_bits) - 1;
357 : 2366366 : size_t unit = idx / MAP_T_BITS;
358 : :
359 : 2366366 : idx %= MAP_T_BITS;
360 : :
361 : 2366366 : fm->bits[unit] |= n_bits_mask << idx;
362 : : /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
363 : : * false-positive array out of bounds error by GCC 4.9. */
364 [ + + ][ + + ]: 2366366 : if (unit + 1 < FLOWMAP_UNITS && idx + n_bits > MAP_T_BITS) {
365 : : /* 'MAP_T_BITS - idx' bits were set on 'unit', set the remaining
366 : : * bits from the next unit. */
367 : 2500 : fm->bits[unit + 1] |= n_bits_mask >> (MAP_T_BITS - idx);
368 : : }
369 : 2366366 : }
370 : :
371 : : /* Clears the 'n_bits' consecutive bits in 'fm', starting at bit 'idx'.
372 : : * 'n_bits' can be at most MAP_T_BITS. */
373 : : static inline void
374 : 144246 : flowmap_clear(struct flowmap *fm, size_t idx, unsigned int n_bits)
375 : : {
376 : 144246 : map_t n_bits_mask = (MAP_1 << n_bits) - 1;
377 : 144246 : size_t unit = idx / MAP_T_BITS;
378 : :
379 : 144246 : idx %= MAP_T_BITS;
380 : :
381 : 144246 : fm->bits[unit] &= ~(n_bits_mask << idx);
382 : : /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
383 : : * false-positive array out of bounds error by GCC 4.9. */
384 [ + + ][ + + ]: 144246 : if (unit + 1 < FLOWMAP_UNITS && idx + n_bits > MAP_T_BITS) {
385 : : /* 'MAP_T_BITS - idx' bits were cleared on 'unit', clear the
386 : : * remaining bits from the next unit. */
387 : 48082 : fm->bits[unit + 1] &= ~(n_bits_mask >> (MAP_T_BITS - idx));
388 : : }
389 : 144246 : }
390 : :
391 : : /* OR the bits in the flowmaps. */
392 : : static inline struct flowmap
393 : 39909440 : flowmap_or(struct flowmap a, struct flowmap b)
394 : : {
395 : : struct flowmap map;
396 : : size_t unit;
397 : :
398 [ + + ]: 119728320 : FLOWMAP_FOR_EACH_UNIT (unit) {
399 : 79818880 : map.bits[unit] = a.bits[unit] | b.bits[unit];
400 : : }
401 : 39909440 : return map;
402 : : }
403 : :
404 : : /* AND the bits in the flowmaps. */
405 : : static inline struct flowmap
406 : 26612 : flowmap_and(struct flowmap a, struct flowmap b)
407 : : {
408 : : struct flowmap map;
409 : : size_t unit;
410 : :
411 [ + + ]: 79836 : FLOWMAP_FOR_EACH_UNIT (unit) {
412 : 53224 : map.bits[unit] = a.bits[unit] & b.bits[unit];
413 : : }
414 : 26612 : return map;
415 : : }
416 : :
417 : : static inline bool
418 : 419048 : flowmap_is_empty(struct flowmap fm)
419 : : {
420 : : map_t map;
421 : :
422 [ + + ]: 748789 : FLOWMAP_FOR_EACH_MAP (map, fm) {
423 [ + + ]: 593376 : if (map) {
424 : 263635 : return false;
425 : : }
426 : : }
427 : 155413 : return true;
428 : : }
429 : :
430 : : static inline unsigned int
431 : 7778374 : flowmap_n_1bits(struct flowmap fm)
432 : : {
433 : 7778374 : unsigned int n_1bits = 0;
434 : : size_t unit;
435 : :
436 [ + + ]: 23335122 : FLOWMAP_FOR_EACH_UNIT (unit) {
437 : 15556748 : n_1bits += count_1bits(fm.bits[unit]);
438 : : }
439 : 7778374 : return n_1bits;
440 : : }
441 : :
442 : : struct flowmap_aux {
443 : : size_t unit;
444 : : struct flowmap map;
445 : : };
446 : :
447 : : static inline bool
448 : 6682549 : flowmap_next_index(struct flowmap_aux *aux, size_t *idx)
449 : : {
450 : : for (;;) {
451 : 8105943 : map_t *map = &aux->map.bits[aux->unit];
452 [ + + ]: 8105943 : if (*map) {
453 : 5259870 : *idx = aux->unit * MAP_T_BITS + raw_ctz(*map);
454 : 5259870 : *map = zero_rightmost_1bit(*map);
455 : 5259870 : return true;
456 : : }
457 [ + + ]: 2846073 : if (++aux->unit >= FLOWMAP_UNITS) {
458 : 1422679 : return false;
459 : : }
460 : 1423394 : }
461 : : }
462 : :
463 : :
464 : : /* Compressed flow. */
465 : :
466 : : /* A sparse representation of a "struct flow".
467 : : *
468 : : * A "struct flow" is fairly large and tends to be mostly zeros. Sparse
469 : : * representation has two advantages. First, it saves memory and, more
470 : : * importantly, minimizes the number of accessed cache lines. Second, it saves
471 : : * time when the goal is to iterate over only the nonzero parts of the struct.
472 : : *
473 : : * The map member hold one bit for each uint64_t in a "struct flow". Each
474 : : * 0-bit indicates that the corresponding uint64_t is zero, each 1-bit that it
475 : : * *may* be nonzero (see below how this applies to minimasks).
476 : : *
477 : : * The values indicated by 'map' always follow the miniflow in memory. The
478 : : * user of the miniflow is responsible for always having enough storage after
479 : : * the struct miniflow corresponding to the number of 1-bits in maps.
480 : : *
481 : : * Elements in values array are allowed to be zero. This is useful for "struct
482 : : * minimatch", for which ensuring that the miniflow and minimask members have
483 : : * same maps allows optimization. This allowance applies only to a miniflow
484 : : * that is not a mask. That is, a minimask may NOT have zero elements in its
485 : : * values.
486 : : *
487 : : * A miniflow is always dynamically allocated so that the maps are followed by
488 : : * at least as many elements as there are 1-bits in maps. */
489 : : struct miniflow {
490 : : struct flowmap map;
491 : : /* Followed by:
492 : : * uint64_t values[n];
493 : : * where 'n' is miniflow_n_values(miniflow). */
494 : : };
495 : : BUILD_ASSERT_DECL(sizeof(struct miniflow) % sizeof(uint64_t) == 0);
496 : :
497 : : #define MINIFLOW_VALUES_SIZE(COUNT) ((COUNT) * sizeof(uint64_t))
498 : :
499 : 2135173 : static inline uint64_t *miniflow_values(struct miniflow *mf)
500 : : {
501 : 2135173 : return (uint64_t *)(mf + 1);
502 : : }
503 : :
504 : 605391295 : static inline const uint64_t *miniflow_get_values(const struct miniflow *mf)
505 : : {
506 : 605391295 : return (const uint64_t *)(mf + 1);
507 : : }
508 : :
509 : : struct pkt_metadata;
510 : :
511 : : /* The 'dst' must follow with buffer space for FLOW_U64S 64-bit units.
512 : : * 'dst->map' is ignored on input and set on output to indicate which fields
513 : : * were extracted. */
514 : : void miniflow_extract(struct dp_packet *packet, struct miniflow *dst);
515 : : void miniflow_map_init(struct miniflow *, const struct flow *);
516 : : void flow_wc_map(const struct flow *, struct flowmap *);
517 : : size_t miniflow_alloc(struct miniflow *dsts[], size_t n,
518 : : const struct miniflow *src);
519 : : void miniflow_init(struct miniflow *, const struct flow *);
520 : : void miniflow_clone(struct miniflow *, const struct miniflow *,
521 : : size_t n_values);
522 : : struct miniflow * miniflow_create(const struct flow *);
523 : :
524 : : void miniflow_expand(const struct miniflow *, struct flow *);
525 : :
526 : 45927667 : static inline uint64_t flow_u64_value(const struct flow *flow, size_t index)
527 : : {
528 : 45927667 : return ((uint64_t *)flow)[index];
529 : : }
530 : :
531 : : static inline uint64_t *flow_u64_lvalue(struct flow *flow, size_t index)
532 : : {
533 : : return &((uint64_t *)flow)[index];
534 : : }
535 : :
536 : : static inline size_t
537 : 6620137 : miniflow_n_values(const struct miniflow *flow)
538 : : {
539 : 6620137 : return flowmap_n_1bits(flow->map);
540 : : }
541 : :
542 : : struct flow_for_each_in_maps_aux {
543 : : const struct flow *flow;
544 : : struct flowmap_aux map_aux;
545 : : };
546 : :
547 : : static inline bool
548 : 91216 : flow_values_get_next_in_maps(struct flow_for_each_in_maps_aux *aux,
549 : : uint64_t *value)
550 : : {
551 : : size_t idx;
552 : :
553 [ + + ]: 91216 : if (flowmap_next_index(&aux->map_aux, &idx)) {
554 : 80885 : *value = flow_u64_value(aux->flow, idx);
555 : 80885 : return true;
556 : : }
557 : 91216 : return false;
558 : : }
559 : :
560 : : /* Iterate through all flow u64 values specified by 'MAPS'. */
561 : : #define FLOW_FOR_EACH_IN_MAPS(VALUE, FLOW, MAPS) \
562 : : for (struct flow_for_each_in_maps_aux aux__ \
563 : : = { (FLOW), FLOWMAP_AUX_INITIALIZER(MAPS) }; \
564 : : flow_values_get_next_in_maps(&aux__, &(VALUE));)
565 : :
566 : : struct mf_for_each_in_map_aux {
567 : : size_t unit;
568 : : struct flowmap fmap;
569 : : struct flowmap map;
570 : : const uint64_t *values;
571 : : };
572 : :
573 : : static inline bool
574 : 6654486 : mf_get_next_in_map(struct mf_for_each_in_map_aux *aux,
575 : : uint64_t *value)
576 : : {
577 : : map_t *map, *fmap;
578 : : map_t rm1bit;
579 : :
580 [ + + ]: 7432359 : while (OVS_UNLIKELY(!*(map = &aux->map.bits[aux->unit]))) {
581 : : /* Skip remaining data in the previous unit. */
582 : 1555746 : aux->values += count_1bits(aux->fmap.bits[aux->unit]);
583 [ + + ]: 1555746 : if (++aux->unit == FLOWMAP_UNITS) {
584 : 777873 : return false;
585 : : }
586 : : }
587 : :
588 : 5876613 : rm1bit = rightmost_1bit(*map);
589 : 5876613 : *map -= rm1bit;
590 : 5876613 : fmap = &aux->fmap.bits[aux->unit];
591 : :
592 [ + + ]: 5876613 : if (OVS_LIKELY(*fmap & rm1bit)) {
593 : 5795894 : map_t trash = *fmap & (rm1bit - 1);
594 : :
595 : 5795894 : *fmap -= trash;
596 : : /* count_1bits() is fast for systems where speed matters (e.g.,
597 : : * DPDK), so we don't try avoid using it.
598 : : * Advance 'aux->values' to point to the value for 'rm1bit'. */
599 : 5795894 : aux->values += count_1bits(trash);
600 : :
601 : 5795894 : *value = *aux->values;
602 : : } else {
603 : 80719 : *value = 0;
604 : : }
605 : 5876613 : return true;
606 : : }
607 : :
608 : : /* Iterate through miniflow u64 values specified by 'FLOWMAP'. */
609 : : #define MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, FLOW, FLOWMAP) \
610 : : for (struct mf_for_each_in_map_aux aux__ = \
611 : : { 0, (FLOW)->map, (FLOWMAP), miniflow_get_values(FLOW) }; \
612 : : mf_get_next_in_map(&aux__, &(VALUE));)
613 : :
614 : : /* This can be used when it is known that 'idx' is set in 'map'. */
615 : : static inline const uint64_t *
616 : 3636493 : miniflow_values_get__(const uint64_t *values, map_t map, size_t idx)
617 : : {
618 : 3636493 : return values + count_1bits(map & ((MAP_1 << idx) - 1));
619 : : }
620 : :
621 : : /* This can be used when it is known that 'u64_idx' is set in
622 : : * the map of 'mf'. */
623 : : static inline const uint64_t *
624 : 3636493 : miniflow_get__(const struct miniflow *mf, size_t idx)
625 : : {
626 : 3636493 : const uint64_t *values = miniflow_get_values(mf);
627 : 3636493 : const map_t *map = mf->map.bits;
628 : :
629 [ + + ]: 4313984 : while (idx >= MAP_T_BITS) {
630 : 677491 : idx -= MAP_T_BITS;
631 : 677491 : values += count_1bits(*map++);
632 : : }
633 : 3636493 : return miniflow_values_get__(values, *map, idx);
634 : : }
635 : :
636 : : #define MINIFLOW_IN_MAP(MF, IDX) flowmap_is_set(&(MF)->map, IDX)
637 : :
638 : : /* Get the value of the struct flow 'FIELD' as up to 8 byte wide integer type
639 : : * 'TYPE' from miniflow 'MF'. */
640 : : #define MINIFLOW_GET_TYPE(MF, TYPE, FIELD) \
641 : : (MINIFLOW_IN_MAP(MF, FLOW_U64_OFFSET(FIELD)) \
642 : : ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, FLOW_U64_OFFSET(FIELD))) \
643 : : [FLOW_U64_OFFREM(FIELD) / sizeof(TYPE)] \
644 : : : 0)
645 : :
646 : : #define MINIFLOW_GET_U128(FLOW, FIELD) \
647 : : (ovs_u128) { .u64 = { \
648 : : (MINIFLOW_IN_MAP(FLOW, FLOW_U64_OFFSET(FIELD)) ? \
649 : : *miniflow_get__(FLOW, FLOW_U64_OFFSET(FIELD)) : 0), \
650 : : (MINIFLOW_IN_MAP(FLOW, FLOW_U64_OFFSET(FIELD) + 1) ? \
651 : : *miniflow_get__(FLOW, FLOW_U64_OFFSET(FIELD) + 1) : 0) } }
652 : :
653 : : #define MINIFLOW_GET_U8(FLOW, FIELD) \
654 : : MINIFLOW_GET_TYPE(FLOW, uint8_t, FIELD)
655 : : #define MINIFLOW_GET_U16(FLOW, FIELD) \
656 : : MINIFLOW_GET_TYPE(FLOW, uint16_t, FIELD)
657 : : #define MINIFLOW_GET_BE16(FLOW, FIELD) \
658 : : MINIFLOW_GET_TYPE(FLOW, ovs_be16, FIELD)
659 : : #define MINIFLOW_GET_U32(FLOW, FIELD) \
660 : : MINIFLOW_GET_TYPE(FLOW, uint32_t, FIELD)
661 : : #define MINIFLOW_GET_BE32(FLOW, FIELD) \
662 : : MINIFLOW_GET_TYPE(FLOW, ovs_be32, FIELD)
663 : : #define MINIFLOW_GET_U64(FLOW, FIELD) \
664 : : MINIFLOW_GET_TYPE(FLOW, uint64_t, FIELD)
665 : : #define MINIFLOW_GET_BE64(FLOW, FIELD) \
666 : : MINIFLOW_GET_TYPE(FLOW, ovs_be64, FIELD)
667 : :
668 : : static inline uint64_t miniflow_get(const struct miniflow *,
669 : : unsigned int u64_ofs);
670 : : static inline uint32_t miniflow_get_u32(const struct miniflow *,
671 : : unsigned int u32_ofs);
672 : : static inline ovs_be32 miniflow_get_be32(const struct miniflow *,
673 : : unsigned int be32_ofs);
674 : : static inline uint16_t miniflow_get_vid(const struct miniflow *);
675 : : static inline uint16_t miniflow_get_tcp_flags(const struct miniflow *);
676 : : static inline ovs_be64 miniflow_get_metadata(const struct miniflow *);
677 : :
678 : : bool miniflow_equal(const struct miniflow *a, const struct miniflow *b);
679 : : bool miniflow_equal_in_minimask(const struct miniflow *a,
680 : : const struct miniflow *b,
681 : : const struct minimask *);
682 : : bool miniflow_equal_flow_in_minimask(const struct miniflow *a,
683 : : const struct flow *b,
684 : : const struct minimask *);
685 : : uint32_t miniflow_hash_5tuple(const struct miniflow *flow, uint32_t basis);
686 : :
687 : :
688 : : /* Compressed flow wildcards. */
689 : :
690 : : /* A sparse representation of a "struct flow_wildcards".
691 : : *
692 : : * See the large comment on struct miniflow for details.
693 : : *
694 : : * Note: While miniflow can have zero data for a 1-bit in the map,
695 : : * a minimask may not! We rely on this in the implementation. */
696 : : struct minimask {
697 : : struct miniflow masks;
698 : : };
699 : :
700 : : void minimask_init(struct minimask *, const struct flow_wildcards *);
701 : : struct minimask * minimask_create(const struct flow_wildcards *);
702 : : void minimask_combine(struct minimask *dst,
703 : : const struct minimask *a, const struct minimask *b,
704 : : uint64_t storage[FLOW_U64S]);
705 : :
706 : : void minimask_expand(const struct minimask *, struct flow_wildcards *);
707 : :
708 : : static inline uint32_t minimask_get_u32(const struct minimask *,
709 : : unsigned int u32_ofs);
710 : : static inline ovs_be32 minimask_get_be32(const struct minimask *,
711 : : unsigned int be32_ofs);
712 : : static inline uint16_t minimask_get_vid_mask(const struct minimask *);
713 : : static inline ovs_be64 minimask_get_metadata_mask(const struct minimask *);
714 : :
715 : : bool minimask_equal(const struct minimask *a, const struct minimask *b);
716 : : bool minimask_has_extra(const struct minimask *, const struct minimask *);
717 : :
718 : :
719 : : /* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
720 : : * or fields. */
721 : : static inline bool
722 : 323728 : minimask_is_catchall(const struct minimask *mask)
723 : : {
724 : : /* For every 1-bit in mask's map, the corresponding value is non-zero,
725 : : * so the only way the mask can not fix any bits or fields is for the
726 : : * map the be zero. */
727 : 323728 : return flowmap_is_empty(mask->masks.map);
728 : : }
729 : :
730 : : /* Returns the uint64_t that would be at byte offset '8 * u64_ofs' if 'flow'
731 : : * were expanded into a "struct flow". */
732 : 2542962 : static inline uint64_t miniflow_get(const struct miniflow *flow,
733 : : unsigned int u64_ofs)
734 : : {
735 [ + + ]: 2542962 : return MINIFLOW_IN_MAP(flow, u64_ofs) ? *miniflow_get__(flow, u64_ofs) : 0;
736 : : }
737 : :
738 : 47452 : static inline uint32_t miniflow_get_u32(const struct miniflow *flow,
739 : : unsigned int u32_ofs)
740 : : {
741 : 47452 : uint64_t value = miniflow_get(flow, u32_ofs / 2);
742 : :
743 : : #if WORDS_BIGENDIAN
744 : : return (u32_ofs & 1) ? value : value >> 32;
745 : : #else
746 [ + + ]: 47452 : return (u32_ofs & 1) ? value >> 32 : value;
747 : : #endif
748 : : }
749 : :
750 : : static inline ovs_be32 miniflow_get_be32(const struct miniflow *flow,
751 : : unsigned int be32_ofs)
752 : : {
753 : : return (OVS_FORCE ovs_be32)miniflow_get_u32(flow, be32_ofs);
754 : : }
755 : :
756 : : /* Returns the VID within the vlan_tci member of the "struct flow" represented
757 : : * by 'flow'. */
758 : : static inline uint16_t
759 : 13306 : miniflow_get_vid(const struct miniflow *flow)
760 : : {
761 [ + + ]: 13306 : ovs_be16 tci = MINIFLOW_GET_BE16(flow, vlan_tci);
762 : 13306 : return vlan_tci_to_vid(tci);
763 : : }
764 : :
765 : : /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'mask'
766 : : * were expanded into a "struct flow_wildcards". */
767 : : static inline uint32_t
768 : 47452 : minimask_get_u32(const struct minimask *mask, unsigned int u32_ofs)
769 : : {
770 : 47452 : return miniflow_get_u32(&mask->masks, u32_ofs);
771 : : }
772 : :
773 : : static inline ovs_be32
774 : 47452 : minimask_get_be32(const struct minimask *mask, unsigned int be32_ofs)
775 : : {
776 : 47452 : return (OVS_FORCE ovs_be32)minimask_get_u32(mask, be32_ofs);
777 : : }
778 : :
779 : : /* Returns the VID mask within the vlan_tci member of the "struct
780 : : * flow_wildcards" represented by 'mask'. */
781 : : static inline uint16_t
782 : : minimask_get_vid_mask(const struct minimask *mask)
783 : : {
784 : : return miniflow_get_vid(&mask->masks);
785 : : }
786 : :
787 : : /* Returns the value of the "tcp_flags" field in 'flow'. */
788 : : static inline uint16_t
789 : 9245 : miniflow_get_tcp_flags(const struct miniflow *flow)
790 : : {
791 [ + + ]: 9245 : return ntohs(MINIFLOW_GET_BE16(flow, tcp_flags));
792 : : }
793 : :
794 : : /* Returns the value of the OpenFlow 1.1+ "metadata" field in 'flow'. */
795 : : static inline ovs_be64
796 : : miniflow_get_metadata(const struct miniflow *flow)
797 : : {
798 : : return MINIFLOW_GET_BE64(flow, metadata);
799 : : }
800 : :
801 : : /* Returns the mask for the OpenFlow 1.1+ "metadata" field in 'mask'.
802 : : *
803 : : * The return value is all-1-bits if 'mask' matches on the whole value of the
804 : : * metadata field, all-0-bits if 'mask' entirely wildcards the metadata field,
805 : : * or some other value if the metadata field is partially matched, partially
806 : : * wildcarded. */
807 : : static inline ovs_be64
808 : : minimask_get_metadata_mask(const struct minimask *mask)
809 : : {
810 : : return MINIFLOW_GET_BE64(&mask->masks, metadata);
811 : : }
812 : :
813 : : /* Perform a bitwise OR of miniflow 'src' flow data specified in 'subset' with
814 : : * the equivalent fields in 'dst', storing the result in 'dst'. 'subset' must
815 : : * be a subset of 'src's map. */
816 : : static inline void
817 : 471437749 : flow_union_with_miniflow_subset(struct flow *dst, const struct miniflow *src,
818 : : struct flowmap subset)
819 : : {
820 : 471437749 : uint64_t *dst_u64 = (uint64_t *) dst;
821 : 471437749 : const uint64_t *p = miniflow_get_values(src);
822 : : map_t map;
823 : :
824 [ + + ]: 1414313240 : FLOWMAP_FOR_EACH_MAP (map, subset) {
825 : : size_t idx;
826 : :
827 [ + + ]: 4595391261 : MAP_FOR_EACH_INDEX(idx, map) {
828 : 3652515769 : dst_u64[idx] |= *p++;
829 : : }
830 : 942875493 : dst_u64 += MAP_T_BITS;
831 : : }
832 : 471437748 : }
833 : :
834 : : /* Perform a bitwise OR of miniflow 'src' flow data with the equivalent
835 : : * fields in 'dst', storing the result in 'dst'. */
836 : : static inline void
837 : 445269647 : flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
838 : : {
839 : 445269647 : flow_union_with_miniflow_subset(dst, src, src->map);
840 : 445269646 : }
841 : :
842 : : static inline void
843 : 14897 : pkt_metadata_from_flow(struct pkt_metadata *md, const struct flow *flow)
844 : : {
845 : 14897 : md->recirc_id = flow->recirc_id;
846 : 14897 : md->dp_hash = flow->dp_hash;
847 : 14897 : flow_tnl_copy__(&md->tunnel, &flow->tunnel);
848 : 14897 : md->skb_priority = flow->skb_priority;
849 : 14897 : md->pkt_mark = flow->pkt_mark;
850 : 14897 : md->in_port = flow->in_port;
851 : 14897 : md->ct_state = flow->ct_state;
852 : 14897 : md->ct_zone = flow->ct_zone;
853 : 14897 : md->ct_mark = flow->ct_mark;
854 : 14897 : md->ct_label = flow->ct_label;
855 : 14897 : }
856 : :
857 : 70 : static inline bool is_vlan(const struct flow *flow,
858 : : struct flow_wildcards *wc)
859 : : {
860 [ + + ]: 70 : if (wc) {
861 : 40 : WC_MASK_FIELD_MASK(wc, vlan_tci, htons(VLAN_CFI));
862 : : }
863 : 70 : return (flow->vlan_tci & htons(VLAN_CFI)) != 0;
864 : : }
865 : :
866 : 2067096 : static inline bool is_ip_any(const struct flow *flow)
867 : : {
868 : 2067096 : return dl_type_is_ip_any(flow->dl_type);
869 : : }
870 : :
871 : 1546 : static inline bool is_ip_proto(const struct flow *flow, uint8_t ip_proto,
872 : : struct flow_wildcards *wc)
873 : : {
874 [ + + ]: 1546 : if (is_ip_any(flow)) {
875 [ + + ]: 1497 : if (wc) {
876 : 29 : WC_MASK_FIELD(wc, nw_proto);
877 : : }
878 : 1497 : return flow->nw_proto == ip_proto;
879 : : }
880 : 49 : return false;
881 : : }
882 : :
883 : 1201 : static inline bool is_tcp(const struct flow *flow,
884 : : struct flow_wildcards *wc)
885 : : {
886 : 1201 : return is_ip_proto(flow, IPPROTO_TCP, wc);
887 : : }
888 : :
889 : 325 : static inline bool is_udp(const struct flow *flow,
890 : : struct flow_wildcards *wc)
891 : : {
892 : 325 : return is_ip_proto(flow, IPPROTO_UDP, wc);
893 : : }
894 : :
895 : 20 : static inline bool is_sctp(const struct flow *flow,
896 : : struct flow_wildcards *wc)
897 : : {
898 : 20 : return is_ip_proto(flow, IPPROTO_SCTP, wc);
899 : : }
900 : :
901 : 204462 : static inline bool is_icmpv4(const struct flow *flow,
902 : : struct flow_wildcards *wc)
903 : : {
904 [ + + ]: 204462 : if (flow->dl_type == htons(ETH_TYPE_IP)) {
905 [ + + ]: 94403 : if (wc) {
906 : 4 : memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
907 : : }
908 : 94403 : return flow->nw_proto == IPPROTO_ICMP;
909 : : }
910 : 110059 : return false;
911 : : }
912 : :
913 : 668090 : static inline bool is_icmpv6(const struct flow *flow,
914 : : struct flow_wildcards *wc)
915 : : {
916 [ + + ]: 668090 : if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
917 [ + + ]: 33149 : if (wc) {
918 : 9 : memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
919 : : }
920 : 33149 : return flow->nw_proto == IPPROTO_ICMPV6;
921 : : }
922 : 634941 : return false;
923 : : }
924 : :
925 : 521133 : static inline bool is_nd(const struct flow *flow,
926 : : struct flow_wildcards *wc)
927 : : {
928 [ + + ]: 521133 : if (is_icmpv6(flow, wc)) {
929 [ + + ]: 16881 : if (wc) {
930 : 9 : memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
931 : : }
932 [ + + ]: 16881 : if (flow->tp_dst != htons(0)) {
933 : 17 : return false;
934 : : }
935 : :
936 [ + + ]: 16864 : if (wc) {
937 : 9 : memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
938 : : }
939 [ + + + + ]: 28785 : return (flow->tp_src == htons(ND_NEIGHBOR_SOLICIT) ||
940 : 11921 : flow->tp_src == htons(ND_NEIGHBOR_ADVERT));
941 : : }
942 : 504252 : return false;
943 : : }
944 : :
945 : 0 : static inline bool is_igmp(const struct flow *flow, struct flow_wildcards *wc)
946 : : {
947 [ # # ]: 0 : if (flow->dl_type == htons(ETH_TYPE_IP)) {
948 [ # # ]: 0 : if (wc) {
949 : 0 : memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
950 : : }
951 : 0 : return flow->nw_proto == IPPROTO_IGMP;
952 : : }
953 : 0 : return false;
954 : : }
955 : :
956 : 0 : static inline bool is_mld(const struct flow *flow,
957 : : struct flow_wildcards *wc)
958 : : {
959 [ # # ]: 0 : if (is_icmpv6(flow, wc)) {
960 [ # # ]: 0 : if (wc) {
961 : 0 : memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
962 : : }
963 : 0 : return (flow->tp_src == htons(MLD_QUERY)
964 [ # # ]: 0 : || flow->tp_src == htons(MLD_REPORT)
965 [ # # ]: 0 : || flow->tp_src == htons(MLD_DONE)
966 [ # # ][ # # ]: 0 : || flow->tp_src == htons(MLD2_REPORT));
967 : : }
968 : 0 : return false;
969 : : }
970 : :
971 : 0 : static inline bool is_mld_query(const struct flow *flow,
972 : : struct flow_wildcards *wc)
973 : : {
974 [ # # ]: 0 : if (is_icmpv6(flow, wc)) {
975 [ # # ]: 0 : if (wc) {
976 : 0 : memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
977 : : }
978 : 0 : return flow->tp_src == htons(MLD_QUERY);
979 : : }
980 : 0 : return false;
981 : : }
982 : :
983 : 0 : static inline bool is_mld_report(const struct flow *flow,
984 : : struct flow_wildcards *wc)
985 : : {
986 [ # # ][ # # ]: 0 : return is_mld(flow, wc) && !is_mld_query(flow, wc);
987 : : }
988 : :
989 : 233868 : static inline bool is_stp(const struct flow *flow)
990 : : {
991 : 467736 : return (eth_addr_equals(flow->dl_dst, eth_addr_stp)
992 [ + + ][ + - ]: 233868 : && flow->dl_type == htons(FLOW_DL_TYPE_NONE));
993 : : }
994 : :
995 : : #endif /* flow.h */
|
