2 * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Nicira, Inc.
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.
19 #include <sys/types.h>
20 #include <netinet/in.h>
21 #include <netinet/icmp6.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"
35 struct dpif_flow_stats
;
37 struct flow_wildcards
;
40 struct ofputil_port_map
;
44 /* Some flow fields are mutually exclusive or only appear within the flow
45 * pipeline. IPv6 headers are bigger than IPv4 and MPLS, and IPv6 ND packets
46 * are bigger than TCP,UDP and IGMP packets. */
47 #define FLOW_MAX_PACKET_U64S (FLOW_U64S \
48 /* Unused in datapath */ - FLOW_U64_SIZE(regs) \
49 - FLOW_U64_SIZE(metadata) \
50 /* L2.5/3 */ - FLOW_U64_SIZE(nw_src) /* incl. nw_dst */ \
51 - FLOW_U64_SIZE(mpls_lse) \
52 /* L4 */ - FLOW_U64_SIZE(tp_src) \
55 extern const uint8_t flow_segment_u64s
[];
57 /* Configured maximum VLAN headers. */
58 extern int flow_vlan_limit
;
60 #define FLOW_U64_OFFSET(FIELD) \
61 (offsetof(struct flow, FIELD) / sizeof(uint64_t))
62 #define FLOW_U64_OFFREM(FIELD) \
63 (offsetof(struct flow, FIELD) % sizeof(uint64_t))
65 /* Number of 64-bit units spanned by a 'FIELD'. */
66 #define FLOW_U64_SIZE(FIELD) \
67 DIV_ROUND_UP(FLOW_U64_OFFREM(FIELD) + MEMBER_SIZEOF(struct flow, FIELD), \
70 void flow_extract(struct dp_packet
*, struct flow
*);
72 void flow_zero_wildcards(struct flow
*, const struct flow_wildcards
*);
73 void flow_unwildcard_tp_ports(const struct flow
*, struct flow_wildcards
*);
74 void flow_get_metadata(const struct flow
*, struct match
*flow_metadata
);
76 const char *ct_state_to_string(uint32_t state
);
77 uint32_t ct_state_from_string(const char *);
78 bool parse_ct_state(const char *state_str
, uint32_t default_state
,
79 uint32_t *ct_state
, struct ds
*);
80 bool validate_ct_state(uint32_t state
, struct ds
*);
81 void flow_clear_conntrack(struct flow
*);
83 char *flow_to_string(const struct flow
*, const struct ofputil_port_map
*);
84 void format_flags(struct ds
*ds
, const char *(*bit_to_string
)(uint32_t),
85 uint32_t flags
, char del
);
86 void format_flags_masked(struct ds
*ds
, const char *name
,
87 const char *(*bit_to_string
)(uint32_t),
88 uint32_t flags
, uint32_t mask
, uint32_t max_mask
);
89 void format_packet_type_masked(struct ds
*, ovs_be32 value
, ovs_be32 mask
);
90 int parse_flags(const char *s
, const char *(*bit_to_string
)(uint32_t),
91 char end
, const char *field_name
, char **res_string
,
92 uint32_t *res_flags
, uint32_t allowed
, uint32_t *res_mask
);
94 void flow_format(struct ds
*, const struct flow
*,
95 const struct ofputil_port_map
*);
96 void flow_print(FILE *, const struct flow
*, const struct ofputil_port_map
*);
97 static inline int flow_compare_3way(const struct flow
*, const struct flow
*);
98 static inline bool flow_equal(const struct flow
*, const struct flow
*);
99 static inline size_t flow_hash(const struct flow
*, uint32_t basis
);
101 void flow_set_dl_vlan(struct flow
*, ovs_be16 vid
);
102 void flow_fix_vlan_tpid(struct flow
*);
103 void flow_set_vlan_vid(struct flow
*, ovs_be16 vid
);
104 void flow_set_vlan_pcp(struct flow
*, uint8_t pcp
);
106 void flow_limit_vlans(int vlan_limit
);
107 int flow_count_vlan_headers(const struct flow
*);
108 void flow_skip_common_vlan_headers(const struct flow
*a
, int *p_an
,
109 const struct flow
*b
, int *p_bn
);
110 void flow_pop_vlan(struct flow
*, struct flow_wildcards
*);
111 void flow_push_vlan_uninit(struct flow
*, struct flow_wildcards
*);
113 int flow_count_mpls_labels(const struct flow
*, struct flow_wildcards
*);
114 int flow_count_common_mpls_labels(const struct flow
*a
, int an
,
115 const struct flow
*b
, int bn
,
116 struct flow_wildcards
*wc
);
117 void flow_push_mpls(struct flow
*, int n
, ovs_be16 mpls_eth_type
,
118 struct flow_wildcards
*, bool clear_flow_L3
);
119 bool flow_pop_mpls(struct flow
*, int n
, ovs_be16 eth_type
,
120 struct flow_wildcards
*);
121 void flow_set_mpls_label(struct flow
*, int idx
, ovs_be32 label
);
122 void flow_set_mpls_ttl(struct flow
*, int idx
, uint8_t ttl
);
123 void flow_set_mpls_tc(struct flow
*, int idx
, uint8_t tc
);
124 void flow_set_mpls_bos(struct flow
*, int idx
, uint8_t stack
);
125 void flow_set_mpls_lse(struct flow
*, int idx
, ovs_be32 lse
);
127 void flow_compose(struct dp_packet
*, const struct flow
*);
129 bool parse_ipv6_ext_hdrs(const void **datap
, size_t *sizep
, uint8_t *nw_proto
,
131 ovs_be16
parse_dl_type(const struct eth_header
*data_
, size_t size
);
133 static inline uint64_t
134 flow_get_xreg(const struct flow
*flow
, int idx
)
136 return ((uint64_t) flow
->regs
[idx
* 2] << 32) | flow
->regs
[idx
* 2 + 1];
140 flow_set_xreg(struct flow
*flow
, int idx
, uint64_t value
)
142 flow
->regs
[idx
* 2] = value
>> 32;
143 flow
->regs
[idx
* 2 + 1] = value
;
146 static inline ovs_u128
147 flow_get_xxreg(const struct flow
*flow
, int idx
)
151 value
.u64
.hi
= (uint64_t) flow
->regs
[idx
* 4] << 32;
152 value
.u64
.hi
|= flow
->regs
[idx
* 4 + 1];
153 value
.u64
.lo
= (uint64_t) flow
->regs
[idx
* 4 + 2] << 32;
154 value
.u64
.lo
|= flow
->regs
[idx
* 4 + 3];
160 flow_set_xxreg(struct flow
*flow
, int idx
, ovs_u128 value
)
162 flow
->regs
[idx
* 4] = value
.u64
.hi
>> 32;
163 flow
->regs
[idx
* 4 + 1] = value
.u64
.hi
;
164 flow
->regs
[idx
* 4 + 2] = value
.u64
.lo
>> 32;
165 flow
->regs
[idx
* 4 + 3] = value
.u64
.lo
;
169 flow_compare_3way(const struct flow
*a
, const struct flow
*b
)
171 return memcmp(a
, b
, sizeof *a
);
175 flow_equal(const struct flow
*a
, const struct flow
*b
)
177 return !flow_compare_3way(a
, b
);
181 flow_hash(const struct flow
*flow
, uint32_t basis
)
183 return hash_bytes64((const uint64_t *)flow
, sizeof *flow
, basis
);
186 static inline uint16_t
187 ofp_to_u16(ofp_port_t ofp_port
)
189 return (OVS_FORCE
uint16_t) ofp_port
;
192 static inline uint32_t
193 odp_to_u32(odp_port_t odp_port
)
195 return (OVS_FORCE
uint32_t) odp_port
;
198 static inline uint32_t
199 ofp11_to_u32(ofp11_port_t ofp11_port
)
201 return (OVS_FORCE
uint32_t) ofp11_port
;
204 static inline ofp_port_t
205 u16_to_ofp(uint16_t port
)
207 return OFP_PORT_C(port
);
210 static inline odp_port_t
211 u32_to_odp(uint32_t port
)
213 return ODP_PORT_C(port
);
216 static inline ofp11_port_t
217 u32_to_ofp11(uint32_t port
)
219 return OFP11_PORT_C(port
);
222 static inline uint32_t
223 hash_ofp_port(ofp_port_t ofp_port
)
225 return hash_int(ofp_to_u16(ofp_port
), 0);
228 static inline uint32_t
229 hash_odp_port(odp_port_t odp_port
)
231 return hash_int(odp_to_u32(odp_port
), 0);
234 uint32_t flow_hash_5tuple(const struct flow
*flow
, uint32_t basis
);
235 uint32_t flow_hash_symmetric_l4(const struct flow
*flow
, uint32_t basis
);
236 uint32_t flow_hash_symmetric_l3l4(const struct flow
*flow
, uint32_t basis
,
237 bool inc_udp_ports
);
239 /* Initialize a flow with random fields that matter for nx_hash_fields. */
240 void flow_random_hash_fields(struct flow
*);
241 void flow_mask_hash_fields(const struct flow
*, struct flow_wildcards
*,
242 enum nx_hash_fields
);
243 uint32_t flow_hash_fields(const struct flow
*, enum nx_hash_fields
,
245 const char *flow_hash_fields_to_str(enum nx_hash_fields
);
246 bool flow_hash_fields_valid(enum nx_hash_fields
);
248 uint32_t flow_hash_in_wildcards(const struct flow
*,
249 const struct flow_wildcards
*,
252 bool flow_equal_except(const struct flow
*a
, const struct flow
*b
,
253 const struct flow_wildcards
*);
255 /* Bitmap for flow values. For each 1-bit the corresponding flow value is
256 * explicitly specified, other values are zeroes.
258 * map_t must be wide enough to hold any member of struct flow. */
259 typedef unsigned long long map_t
;
260 #define MAP_T_BITS (sizeof(map_t) * CHAR_BIT)
261 #define MAP_1 (map_t)1
262 #define MAP_MAX TYPE_MAXIMUM(map_t)
264 #define MAP_IS_SET(MAP, IDX) ((MAP) & (MAP_1 << (IDX)))
266 /* Iterate through the indices of all 1-bits in 'MAP'. */
267 #define MAP_FOR_EACH_INDEX(IDX, MAP) \
268 ULLONG_FOR_EACH_1(IDX, MAP)
270 #define FLOWMAP_UNITS DIV_ROUND_UP(FLOW_U64S, MAP_T_BITS)
273 map_t bits
[FLOWMAP_UNITS
];
276 #define FLOWMAP_EMPTY_INITIALIZER { { 0 } }
278 static inline void flowmap_init(struct flowmap
*);
279 static inline bool flowmap_equal(struct flowmap
, struct flowmap
);
280 static inline bool flowmap_is_set(const struct flowmap
*, size_t idx
);
281 static inline bool flowmap_are_set(const struct flowmap
*, size_t idx
,
282 unsigned int n_bits
);
283 static inline void flowmap_set(struct flowmap
*, size_t idx
,
284 unsigned int n_bits
);
285 static inline void flowmap_clear(struct flowmap
*, size_t idx
,
286 unsigned int n_bits
);
287 static inline struct flowmap
flowmap_or(struct flowmap
, struct flowmap
);
288 static inline struct flowmap
flowmap_and(struct flowmap
, struct flowmap
);
289 static inline bool flowmap_is_empty(struct flowmap
);
290 static inline unsigned int flowmap_n_1bits(struct flowmap
);
292 #define FLOWMAP_HAS_FIELD(FM, FIELD) \
293 flowmap_are_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
295 #define FLOWMAP_SET(FM, FIELD) \
296 flowmap_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
298 #define FLOWMAP_SET__(FM, FIELD, SIZE) \
299 flowmap_set(FM, FLOW_U64_OFFSET(FIELD), \
300 DIV_ROUND_UP(SIZE, sizeof(uint64_t)))
302 /* XXX: Only works for full 64-bit units. */
303 #define FLOWMAP_CLEAR(FM, FIELD) \
304 BUILD_ASSERT_DECL(FLOW_U64_OFFREM(FIELD) == 0); \
305 BUILD_ASSERT_DECL(sizeof(((struct flow *)0)->FIELD) % sizeof(uint64_t) == 0); \
306 flowmap_clear(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
308 /* Iterate through all units in 'FMAP'. */
309 #define FLOWMAP_FOR_EACH_UNIT(UNIT) \
310 for ((UNIT) = 0; (UNIT) < FLOWMAP_UNITS; (UNIT)++)
312 /* Iterate through all map units in 'FMAP'. */
313 #define FLOWMAP_FOR_EACH_MAP(MAP, FLOWMAP) \
314 for (size_t unit__ = 0; \
315 unit__ < FLOWMAP_UNITS && ((MAP) = (FLOWMAP).bits[unit__], true); \
319 static inline bool flowmap_next_index(struct flowmap_aux
*, size_t *idx
);
321 #define FLOWMAP_AUX_INITIALIZER(FLOWMAP) { .unit = 0, .map = (FLOWMAP) }
323 /* Iterate through all struct flow u64 indices specified by 'MAP'. This is a
324 * slower but easier version of the FLOWMAP_FOR_EACH_MAP() &
325 * MAP_FOR_EACH_INDEX() combination. */
326 #define FLOWMAP_FOR_EACH_INDEX(IDX, MAP) \
327 for (struct flowmap_aux aux__ = FLOWMAP_AUX_INITIALIZER(MAP); \
328 flowmap_next_index(&aux__, &(IDX));)
330 /* Flowmap inline implementations. */
332 flowmap_init(struct flowmap
*fm
)
334 memset(fm
, 0, sizeof *fm
);
338 flowmap_equal(struct flowmap a
, struct flowmap b
)
340 return !memcmp(&a
, &b
, sizeof a
);
344 flowmap_is_set(const struct flowmap
*fm
, size_t idx
)
346 return (fm
->bits
[idx
/ MAP_T_BITS
] & (MAP_1
<< (idx
% MAP_T_BITS
))) != 0;
349 /* Returns 'true' if any of the 'n_bits' bits starting at 'idx' are set in
350 * 'fm'. 'n_bits' can be at most MAP_T_BITS. */
352 flowmap_are_set(const struct flowmap
*fm
, size_t idx
, unsigned int n_bits
)
354 map_t n_bits_mask
= (MAP_1
<< n_bits
) - 1;
355 size_t unit
= idx
/ MAP_T_BITS
;
359 if (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 if (unit
+ 1 < FLOWMAP_UNITS
&& idx
+ n_bits
> MAP_T_BITS
) {
365 /* Check the remaining bits from the next unit. */
366 return fm
->bits
[unit
+ 1] & (n_bits_mask
>> (MAP_T_BITS
- idx
));
371 /* Set the 'n_bits' consecutive bits in 'fm', starting at bit 'idx'.
372 * 'n_bits' can be at most MAP_T_BITS. */
374 flowmap_set(struct flowmap
*fm
, size_t idx
, unsigned int n_bits
)
376 map_t n_bits_mask
= (MAP_1
<< n_bits
) - 1;
377 size_t unit
= idx
/ MAP_T_BITS
;
381 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 if (unit
+ 1 < FLOWMAP_UNITS
&& idx
+ n_bits
> MAP_T_BITS
) {
385 /* 'MAP_T_BITS - idx' bits were set on 'unit', set the remaining
386 * bits from the next unit. */
387 fm
->bits
[unit
+ 1] |= n_bits_mask
>> (MAP_T_BITS
- idx
);
391 /* Clears the 'n_bits' consecutive bits in 'fm', starting at bit 'idx'.
392 * 'n_bits' can be at most MAP_T_BITS. */
394 flowmap_clear(struct flowmap
*fm
, size_t idx
, unsigned int n_bits
)
396 map_t n_bits_mask
= (MAP_1
<< n_bits
) - 1;
397 size_t unit
= idx
/ MAP_T_BITS
;
401 fm
->bits
[unit
] &= ~(n_bits_mask
<< idx
);
402 /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
403 * false-positive array out of bounds error by GCC 4.9. */
404 if (unit
+ 1 < FLOWMAP_UNITS
&& idx
+ n_bits
> MAP_T_BITS
) {
405 /* 'MAP_T_BITS - idx' bits were cleared on 'unit', clear the
406 * remaining bits from the next unit. */
407 fm
->bits
[unit
+ 1] &= ~(n_bits_mask
>> (MAP_T_BITS
- idx
));
411 /* OR the bits in the flowmaps. */
412 static inline struct flowmap
413 flowmap_or(struct flowmap a
, struct flowmap b
)
418 FLOWMAP_FOR_EACH_UNIT (unit
) {
419 map
.bits
[unit
] = a
.bits
[unit
] | b
.bits
[unit
];
424 /* AND the bits in the flowmaps. */
425 static inline struct flowmap
426 flowmap_and(struct flowmap a
, struct flowmap b
)
431 FLOWMAP_FOR_EACH_UNIT (unit
) {
432 map
.bits
[unit
] = a
.bits
[unit
] & b
.bits
[unit
];
438 flowmap_is_empty(struct flowmap fm
)
442 FLOWMAP_FOR_EACH_MAP (map
, fm
) {
450 static inline unsigned int
451 flowmap_n_1bits(struct flowmap fm
)
453 unsigned int n_1bits
= 0;
456 FLOWMAP_FOR_EACH_UNIT (unit
) {
457 n_1bits
+= count_1bits(fm
.bits
[unit
]);
468 flowmap_next_index(struct flowmap_aux
*aux
, size_t *idx
)
471 map_t
*map
= &aux
->map
.bits
[aux
->unit
];
473 *idx
= aux
->unit
* MAP_T_BITS
+ raw_ctz(*map
);
474 *map
= zero_rightmost_1bit(*map
);
477 if (++aux
->unit
>= FLOWMAP_UNITS
) {
484 /* Compressed flow. */
486 /* A sparse representation of a "struct flow".
488 * A "struct flow" is fairly large and tends to be mostly zeros. Sparse
489 * representation has two advantages. First, it saves memory and, more
490 * importantly, minimizes the number of accessed cache lines. Second, it saves
491 * time when the goal is to iterate over only the nonzero parts of the struct.
493 * The map member hold one bit for each uint64_t in a "struct flow". Each
494 * 0-bit indicates that the corresponding uint64_t is zero, each 1-bit that it
495 * *may* be nonzero (see below how this applies to minimasks).
497 * The values indicated by 'map' always follow the miniflow in memory. The
498 * user of the miniflow is responsible for always having enough storage after
499 * the struct miniflow corresponding to the number of 1-bits in maps.
501 * Elements in values array are allowed to be zero. This is useful for "struct
502 * minimatch", for which ensuring that the miniflow and minimask members have
503 * same maps allows optimization. This allowance applies only to a miniflow
504 * that is not a mask. That is, a minimask may NOT have zero elements in its
507 * A miniflow is always dynamically allocated so that the maps are followed by
508 * at least as many elements as there are 1-bits in maps. */
512 * uint64_t values[n];
513 * where 'n' is miniflow_n_values(miniflow). */
515 BUILD_ASSERT_DECL(sizeof(struct miniflow
) % sizeof(uint64_t) == 0);
517 #define MINIFLOW_VALUES_SIZE(COUNT) ((COUNT) * sizeof(uint64_t))
519 static inline uint64_t *miniflow_values(struct miniflow
*mf
)
521 return (uint64_t *)(mf
+ 1);
524 static inline const uint64_t *miniflow_get_values(const struct miniflow
*mf
)
526 return (const uint64_t *)(mf
+ 1);
531 /* The 'dst' must follow with buffer space for FLOW_U64S 64-bit units.
532 * 'dst->map' is ignored on input and set on output to indicate which fields
534 void miniflow_extract(struct dp_packet
*packet
, struct miniflow
*dst
);
535 void miniflow_map_init(struct miniflow
*, const struct flow
*);
536 void flow_wc_map(const struct flow
*, struct flowmap
*);
537 size_t miniflow_alloc(struct miniflow
*dsts
[], size_t n
,
538 const struct miniflow
*src
);
539 void miniflow_init(struct miniflow
*, const struct flow
*);
540 void miniflow_clone(struct miniflow
*, const struct miniflow
*,
542 struct miniflow
* miniflow_create(const struct flow
*);
544 void miniflow_expand(const struct miniflow
*, struct flow
*);
546 static inline uint64_t flow_u64_value(const struct flow
*flow
, size_t index
)
548 return ((uint64_t *)flow
)[index
];
551 static inline uint64_t *flow_u64_lvalue(struct flow
*flow
, size_t index
)
553 return &((uint64_t *)flow
)[index
];
557 miniflow_n_values(const struct miniflow
*flow
)
559 return flowmap_n_1bits(flow
->map
);
562 struct flow_for_each_in_maps_aux
{
563 const struct flow
*flow
;
564 struct flowmap_aux map_aux
;
568 flow_values_get_next_in_maps(struct flow_for_each_in_maps_aux
*aux
,
573 if (flowmap_next_index(&aux
->map_aux
, &idx
)) {
574 *value
= flow_u64_value(aux
->flow
, idx
);
580 /* Iterate through all flow u64 values specified by 'MAPS'. */
581 #define FLOW_FOR_EACH_IN_MAPS(VALUE, FLOW, MAPS) \
582 for (struct flow_for_each_in_maps_aux aux__ \
583 = { (FLOW), FLOWMAP_AUX_INITIALIZER(MAPS) }; \
584 flow_values_get_next_in_maps(&aux__, &(VALUE));)
586 struct mf_for_each_in_map_aux
{
587 size_t unit
; /* Current 64-bit unit of the flowmaps
589 struct flowmap fmap
; /* Remaining 1-bits corresponding to the
590 64-bit words in ‘values’ */
591 struct flowmap map
; /* Remaining 1-bits corresponding to the
592 64-bit words of interest. */
593 const uint64_t *values
; /* 64-bit words corresponding to the
594 1-bits in ‘fmap’. */
597 /* Get the data from ‘aux->values’ corresponding to the next lowest 1-bit
598 * in ‘aux->map’, given that ‘aux->values’ points to an array of 64-bit
599 * words corresponding to the 1-bits in ‘aux->fmap’, starting from the
602 * Returns ’true’ if the traversal is incomplete, ‘false’ otherwise.
603 * ‘aux’ is prepared for the next iteration after each call.
605 * This is used to traverse through, for example, the values in a miniflow
606 * representation of a flow key selected by non-zero 64-bit words in a
607 * corresponding subtable mask. */
609 mf_get_next_in_map(struct mf_for_each_in_map_aux
*aux
,
615 /* Skip empty map units. */
616 while (OVS_UNLIKELY(!*(map
= &aux
->map
.bits
[aux
->unit
]))) {
617 /* Skip remaining data in the current unit before advancing
619 aux
->values
+= count_1bits(aux
->fmap
.bits
[aux
->unit
]);
620 if (++aux
->unit
== FLOWMAP_UNITS
) {
625 rm1bit
= rightmost_1bit(*map
);
627 fmap
= &aux
->fmap
.bits
[aux
->unit
];
629 /* If the rightmost 1-bit found from the current unit in ‘aux->map’
630 * (‘rm1bit’) is also present in ‘aux->fmap’, store the corresponding
631 * value from ‘aux->values’ to ‘*value', otherwise store 0. */
632 if (OVS_LIKELY(*fmap
& rm1bit
)) {
633 /* Skip all 64-bit words in ‘values’ preceding the one corresponding
634 * to ‘rm1bit’. */
635 map_t trash
= *fmap
& (rm1bit
- 1);
637 /* Avoid resetting 'fmap' and calling count_1bits() when trash is
641 aux
->values
+= count_1bits(trash
);
644 *value
= *aux
->values
;
651 /* Iterate through miniflow u64 values specified by 'FLOWMAP'. */
652 #define MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, FLOW, FLOWMAP) \
653 for (struct mf_for_each_in_map_aux aux__ = \
654 { 0, (FLOW)->map, (FLOWMAP), miniflow_get_values(FLOW) }; \
655 mf_get_next_in_map(&aux__, &(VALUE));)
657 /* This can be used when it is known that 'idx' is set in 'map'. */
658 static inline const uint64_t *
659 miniflow_values_get__(const uint64_t *values
, map_t map
, size_t idx
)
661 return values
+ count_1bits(map
& ((MAP_1
<< idx
) - 1));
664 /* This can be used when it is known that 'u64_idx' is set in
665 * the map of 'mf'. */
666 static inline const uint64_t *
667 miniflow_get__(const struct miniflow
*mf
, size_t idx
)
669 const uint64_t *values
= miniflow_get_values(mf
);
670 const map_t
*map
= mf
->map
.bits
;
672 while (idx
>= MAP_T_BITS
) {
674 values
+= count_1bits(*map
++);
676 return miniflow_values_get__(values
, *map
, idx
);
679 #define MINIFLOW_IN_MAP(MF, IDX) flowmap_is_set(&(MF)->map, IDX)
681 /* Get the value of the struct flow 'FIELD' as up to 8 byte wide integer type
682 * 'TYPE' from miniflow 'MF'. */
683 #define MINIFLOW_GET_TYPE(MF, TYPE, FIELD) \
684 (MINIFLOW_IN_MAP(MF, FLOW_U64_OFFSET(FIELD)) \
685 ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, FLOW_U64_OFFSET(FIELD))) \
686 [FLOW_U64_OFFREM(FIELD) / sizeof(TYPE)] \
689 #define MINIFLOW_GET_U128(FLOW, FIELD) \
690 (ovs_u128) { .u64 = { \
691 (MINIFLOW_IN_MAP(FLOW, FLOW_U64_OFFSET(FIELD)) ? \
692 *miniflow_get__(FLOW, FLOW_U64_OFFSET(FIELD)) : 0), \
693 (MINIFLOW_IN_MAP(FLOW, FLOW_U64_OFFSET(FIELD) + 1) ? \
694 *miniflow_get__(FLOW, FLOW_U64_OFFSET(FIELD) + 1) : 0) } }
696 #define MINIFLOW_GET_U8(FLOW, FIELD) \
697 MINIFLOW_GET_TYPE(FLOW, uint8_t, FIELD)
698 #define MINIFLOW_GET_U16(FLOW, FIELD) \
699 MINIFLOW_GET_TYPE(FLOW, uint16_t, FIELD)
700 #define MINIFLOW_GET_BE16(FLOW, FIELD) \
701 MINIFLOW_GET_TYPE(FLOW, ovs_be16, FIELD)
702 #define MINIFLOW_GET_U32(FLOW, FIELD) \
703 MINIFLOW_GET_TYPE(FLOW, uint32_t, FIELD)
704 #define MINIFLOW_GET_BE32(FLOW, FIELD) \
705 MINIFLOW_GET_TYPE(FLOW, ovs_be32, FIELD)
706 #define MINIFLOW_GET_U64(FLOW, FIELD) \
707 MINIFLOW_GET_TYPE(FLOW, uint64_t, FIELD)
708 #define MINIFLOW_GET_BE64(FLOW, FIELD) \
709 MINIFLOW_GET_TYPE(FLOW, ovs_be64, FIELD)
711 static inline uint64_t miniflow_get(const struct miniflow
*,
712 unsigned int u64_ofs
);
713 static inline uint32_t miniflow_get_u32(const struct miniflow
*,
714 unsigned int u32_ofs
);
715 static inline ovs_be32
miniflow_get_be32(const struct miniflow
*,
716 unsigned int be32_ofs
);
717 static inline uint16_t miniflow_get_vid(const struct miniflow
*, size_t);
718 static inline uint16_t miniflow_get_tcp_flags(const struct miniflow
*);
719 static inline ovs_be64
miniflow_get_metadata(const struct miniflow
*);
721 bool miniflow_equal(const struct miniflow
*a
, const struct miniflow
*b
);
722 bool miniflow_equal_in_minimask(const struct miniflow
*a
,
723 const struct miniflow
*b
,
724 const struct minimask
*);
725 bool miniflow_equal_flow_in_minimask(const struct miniflow
*a
,
726 const struct flow
*b
,
727 const struct minimask
*);
728 uint32_t miniflow_hash_5tuple(const struct miniflow
*flow
, uint32_t basis
);
731 /* Compressed flow wildcards. */
733 /* A sparse representation of a "struct flow_wildcards".
735 * See the large comment on struct miniflow for details.
737 * Note: While miniflow can have zero data for a 1-bit in the map,
738 * a minimask may not! We rely on this in the implementation. */
740 struct miniflow masks
;
743 void minimask_init(struct minimask
*, const struct flow_wildcards
*);
744 struct minimask
* minimask_create(const struct flow_wildcards
*);
745 void minimask_combine(struct minimask
*dst
,
746 const struct minimask
*a
, const struct minimask
*b
,
747 uint64_t storage
[FLOW_U64S
]);
749 void minimask_expand(const struct minimask
*, struct flow_wildcards
*);
751 static inline uint32_t minimask_get_u32(const struct minimask
*,
752 unsigned int u32_ofs
);
753 static inline ovs_be32
minimask_get_be32(const struct minimask
*,
754 unsigned int be32_ofs
);
755 static inline uint16_t minimask_get_vid_mask(const struct minimask
*, size_t);
756 static inline ovs_be64
minimask_get_metadata_mask(const struct minimask
*);
758 bool minimask_equal(const struct minimask
*a
, const struct minimask
*b
);
759 bool minimask_has_extra(const struct minimask
*, const struct minimask
*);
762 /* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
765 minimask_is_catchall(const struct minimask
*mask
)
767 /* For every 1-bit in mask's map, the corresponding value is non-zero,
768 * so the only way the mask can not fix any bits or fields is for the
769 * map the be zero. */
770 return flowmap_is_empty(mask
->masks
.map
);
773 /* Returns the uint64_t that would be at byte offset '8 * u64_ofs' if 'flow'
774 * were expanded into a "struct flow". */
775 static inline uint64_t miniflow_get(const struct miniflow
*flow
,
776 unsigned int u64_ofs
)
778 return MINIFLOW_IN_MAP(flow
, u64_ofs
) ? *miniflow_get__(flow
, u64_ofs
) : 0;
781 static inline uint32_t miniflow_get_u32(const struct miniflow
*flow
,
782 unsigned int u32_ofs
)
784 uint64_t value
= miniflow_get(flow
, u32_ofs
/ 2);
787 return (u32_ofs
& 1) ? value
: value
>> 32;
789 return (u32_ofs
& 1) ? value
>> 32 : value
;
793 static inline ovs_be32
miniflow_get_be32(const struct miniflow
*flow
,
794 unsigned int be32_ofs
)
796 return (OVS_FORCE ovs_be32
)miniflow_get_u32(flow
, be32_ofs
);
799 /* Returns the VID within the vlan_tci member of the "struct flow" represented
801 static inline uint16_t
802 miniflow_get_vid(const struct miniflow
*flow
, size_t n
)
804 if (n
< FLOW_MAX_VLAN_HEADERS
) {
805 union flow_vlan_hdr hdr
= {
806 .qtag
= MINIFLOW_GET_BE32(flow
, vlans
[n
])
808 return vlan_tci_to_vid(hdr
.tci
);
813 /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'mask'
814 * were expanded into a "struct flow_wildcards". */
815 static inline uint32_t
816 minimask_get_u32(const struct minimask
*mask
, unsigned int u32_ofs
)
818 return miniflow_get_u32(&mask
->masks
, u32_ofs
);
821 static inline ovs_be32
822 minimask_get_be32(const struct minimask
*mask
, unsigned int be32_ofs
)
824 return (OVS_FORCE ovs_be32
)minimask_get_u32(mask
, be32_ofs
);
827 /* Returns the VID mask within the vlan_tci member of the "struct
828 * flow_wildcards" represented by 'mask'. */
829 static inline uint16_t
830 minimask_get_vid_mask(const struct minimask
*mask
, size_t n
)
832 return miniflow_get_vid(&mask
->masks
, n
);
835 /* Returns the value of the "tcp_flags" field in 'flow'. */
836 static inline uint16_t
837 miniflow_get_tcp_flags(const struct miniflow
*flow
)
839 return ntohs(MINIFLOW_GET_BE16(flow
, tcp_flags
));
842 /* Returns the value of the OpenFlow 1.1+ "metadata" field in 'flow'. */
843 static inline ovs_be64
844 miniflow_get_metadata(const struct miniflow
*flow
)
846 return MINIFLOW_GET_BE64(flow
, metadata
);
849 /* Returns the mask for the OpenFlow 1.1+ "metadata" field in 'mask'.
851 * The return value is all-1-bits if 'mask' matches on the whole value of the
852 * metadata field, all-0-bits if 'mask' entirely wildcards the metadata field,
853 * or some other value if the metadata field is partially matched, partially
855 static inline ovs_be64
856 minimask_get_metadata_mask(const struct minimask
*mask
)
858 return MINIFLOW_GET_BE64(&mask
->masks
, metadata
);
861 /* Perform a bitwise OR of miniflow 'src' flow data specified in 'subset' with
862 * the equivalent fields in 'dst', storing the result in 'dst'. 'subset' must
863 * be a subset of 'src's map. */
865 flow_union_with_miniflow_subset(struct flow
*dst
, const struct miniflow
*src
,
866 struct flowmap subset
)
868 uint64_t *dst_u64
= (uint64_t *) dst
;
869 const uint64_t *p
= miniflow_get_values(src
);
872 FLOWMAP_FOR_EACH_MAP (map
, subset
) {
875 MAP_FOR_EACH_INDEX(idx
, map
) {
876 dst_u64
[idx
] |= *p
++;
878 dst_u64
+= MAP_T_BITS
;
882 /* Perform a bitwise OR of miniflow 'src' flow data with the equivalent
883 * fields in 'dst', storing the result in 'dst'. */
885 flow_union_with_miniflow(struct flow
*dst
, const struct miniflow
*src
)
887 flow_union_with_miniflow_subset(dst
, src
, src
->map
);
890 static inline bool is_ct_valid(const struct flow
*flow
,
891 const struct flow_wildcards
*mask
,
892 struct flow_wildcards
*wc
)
894 /* Matches are checked with 'mask' and without 'wc'. */
896 /* Must match at least one of the bits that implies a valid
897 * conntrack entry, or an explicit not-invalid. */
898 return flow
->ct_state
& (CS_NEW
| CS_ESTABLISHED
| CS_RELATED
899 | CS_REPLY_DIR
| CS_SRC_NAT
| CS_DST_NAT
)
900 || (flow
->ct_state
& CS_TRACKED
901 && mask
->masks
.ct_state
& CS_INVALID
902 && !(flow
->ct_state
& CS_INVALID
));
904 /* Else we are checking a fully extracted flow, where valid CT state always
905 * has either 'new', 'established', or 'reply_dir' bit set. */
906 #define CS_VALID_MASK (CS_NEW | CS_ESTABLISHED | CS_REPLY_DIR)
908 wc
->masks
.ct_state
|= CS_VALID_MASK
;
910 return flow
->ct_state
& CS_VALID_MASK
;
914 pkt_metadata_from_flow(struct pkt_metadata
*md
, const struct flow
*flow
)
916 /* Update this function whenever struct flow changes. */
917 BUILD_ASSERT_DECL(FLOW_WC_SEQ
== 39);
919 md
->recirc_id
= flow
->recirc_id
;
920 md
->dp_hash
= flow
->dp_hash
;
921 flow_tnl_copy__(&md
->tunnel
, &flow
->tunnel
);
922 md
->skb_priority
= flow
->skb_priority
;
923 md
->pkt_mark
= flow
->pkt_mark
;
924 md
->in_port
= flow
->in_port
;
925 md
->ct_state
= flow
->ct_state
;
926 md
->ct_zone
= flow
->ct_zone
;
927 md
->ct_mark
= flow
->ct_mark
;
928 md
->ct_label
= flow
->ct_label
;
930 md
->ct_orig_tuple_ipv6
= false;
931 if (is_ct_valid(flow
, NULL
, NULL
)) {
932 if (flow
->dl_type
== htons(ETH_TYPE_IP
)) {
933 md
->ct_orig_tuple
.ipv4
= (struct ovs_key_ct_tuple_ipv4
) {
940 } else if (flow
->dl_type
== htons(ETH_TYPE_IPV6
)) {
941 md
->ct_orig_tuple_ipv6
= true;
942 md
->ct_orig_tuple
.ipv6
= (struct ovs_key_ct_tuple_ipv6
) {
951 memset(&md
->ct_orig_tuple
, 0, sizeof md
->ct_orig_tuple
);
955 /* Often, during translation we need to read a value from a flow('FLOW') and
956 * unwildcard the corresponding bits in the wildcards('WC'). This macro makes
957 * it easier to do that. */
959 #define FLOW_WC_GET_AND_MASK_WC(FLOW, WC, FIELD) \
960 (((WC) ? WC_MASK_FIELD(WC, FIELD) : NULL), ((FLOW)->FIELD))
962 static inline bool is_ethernet(const struct flow
*flow
,
963 struct flow_wildcards
*wc
)
966 WC_MASK_FIELD(wc
, packet_type
);
968 return flow
->packet_type
== htonl(PT_ETH
);
971 static inline ovs_be16
get_dl_type(const struct flow
*flow
)
973 if (flow
->packet_type
== htonl(PT_ETH
)) {
974 return flow
->dl_type
;
975 } else if (pt_ns(flow
->packet_type
) == OFPHTN_ETHERTYPE
) {
976 return pt_ns_type_be(flow
->packet_type
);
978 return htons(FLOW_DL_TYPE_NONE
);
982 static inline bool is_vlan(const struct flow
*flow
,
983 struct flow_wildcards
*wc
)
985 if (!is_ethernet(flow
, wc
)) {
989 WC_MASK_FIELD_MASK(wc
, vlans
[0].tci
, htons(VLAN_CFI
));
991 return (flow
->vlans
[0].tci
& htons(VLAN_CFI
)) != 0;
994 static inline bool is_ip_any(const struct flow
*flow
)
996 return dl_type_is_ip_any(get_dl_type(flow
));
999 static inline bool is_ip_proto(const struct flow
*flow
, uint8_t ip_proto
,
1000 struct flow_wildcards
*wc
)
1002 if (is_ip_any(flow
)) {
1004 WC_MASK_FIELD(wc
, nw_proto
);
1006 return flow
->nw_proto
== ip_proto
;
1011 static inline bool is_tcp(const struct flow
*flow
,
1012 struct flow_wildcards
*wc
)
1014 return is_ip_proto(flow
, IPPROTO_TCP
, wc
);
1017 static inline bool is_udp(const struct flow
*flow
,
1018 struct flow_wildcards
*wc
)
1020 return is_ip_proto(flow
, IPPROTO_UDP
, wc
);
1023 static inline bool is_sctp(const struct flow
*flow
,
1024 struct flow_wildcards
*wc
)
1026 return is_ip_proto(flow
, IPPROTO_SCTP
, wc
);
1029 static inline bool is_icmpv4(const struct flow
*flow
,
1030 struct flow_wildcards
*wc
)
1032 if (get_dl_type(flow
) == htons(ETH_TYPE_IP
)) {
1034 memset(&wc
->masks
.nw_proto
, 0xff, sizeof wc
->masks
.nw_proto
);
1036 return flow
->nw_proto
== IPPROTO_ICMP
;
1041 static inline bool is_icmpv6(const struct flow
*flow
,
1042 struct flow_wildcards
*wc
)
1044 if (get_dl_type(flow
) == htons(ETH_TYPE_IPV6
)) {
1046 memset(&wc
->masks
.nw_proto
, 0xff, sizeof wc
->masks
.nw_proto
);
1048 return flow
->nw_proto
== IPPROTO_ICMPV6
;
1053 static inline bool is_nd(const struct flow
*flow
,
1054 struct flow_wildcards
*wc
)
1056 if (is_icmpv6(flow
, wc
)) {
1058 memset(&wc
->masks
.tp_dst
, 0xff, sizeof wc
->masks
.tp_dst
);
1060 if (flow
->tp_dst
!= htons(0)) {
1065 memset(&wc
->masks
.tp_src
, 0xff, sizeof wc
->masks
.tp_src
);
1067 return (flow
->tp_src
== htons(ND_NEIGHBOR_SOLICIT
) ||
1068 flow
->tp_src
== htons(ND_NEIGHBOR_ADVERT
));
1073 static inline bool is_igmp(const struct flow
*flow
, struct flow_wildcards
*wc
)
1075 if (get_dl_type(flow
) == htons(ETH_TYPE_IP
)) {
1077 memset(&wc
->masks
.nw_proto
, 0xff, sizeof wc
->masks
.nw_proto
);
1079 return flow
->nw_proto
== IPPROTO_IGMP
;
1084 static inline bool is_mld(const struct flow
*flow
,
1085 struct flow_wildcards
*wc
)
1087 if (is_icmpv6(flow
, wc
)) {
1089 memset(&wc
->masks
.tp_src
, 0xff, sizeof wc
->masks
.tp_src
);
1091 return (flow
->tp_src
== htons(MLD_QUERY
)
1092 || flow
->tp_src
== htons(MLD_REPORT
)
1093 || flow
->tp_src
== htons(MLD_DONE
)
1094 || flow
->tp_src
== htons(MLD2_REPORT
));
1099 static inline bool is_mld_query(const struct flow
*flow
,
1100 struct flow_wildcards
*wc
)
1102 if (is_icmpv6(flow
, wc
)) {
1104 memset(&wc
->masks
.tp_src
, 0xff, sizeof wc
->masks
.tp_src
);
1106 return flow
->tp_src
== htons(MLD_QUERY
);
1111 static inline bool is_mld_report(const struct flow
*flow
,
1112 struct flow_wildcards
*wc
)
1114 return is_mld(flow
, wc
) && !is_mld_query(flow
, wc
);
1117 static inline bool is_stp(const struct flow
*flow
)
1119 return (flow
->dl_type
== htons(FLOW_DL_TYPE_NONE
)
1120 && eth_addr_equals(flow
->dl_dst
, eth_addr_stp
));