python: Serial JSON via Python's json lib.
[cascardo/ovs.git] / lib / flow.h
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 static inline uint64_t
110 flow_get_xreg(const struct flow *flow, int idx)
111 {
112     return ((uint64_t) flow->regs[idx * 2] << 32) | flow->regs[idx * 2 + 1];
113 }
114
115 static inline void
116 flow_set_xreg(struct flow *flow, int idx, uint64_t value)
117 {
118     flow->regs[idx * 2] = value >> 32;
119     flow->regs[idx * 2 + 1] = value;
120 }
121
122 static inline ovs_u128
123 flow_get_xxreg(const struct flow *flow, int idx)
124 {
125     ovs_u128 value;
126
127     value.u64.hi = (uint64_t) flow->regs[idx * 4] << 32;
128     value.u64.hi |= flow->regs[idx * 4 + 1];
129     value.u64.lo = (uint64_t) flow->regs[idx * 4 + 2] << 32;
130     value.u64.lo |= flow->regs[idx * 4 + 3];
131
132     return value;
133 }
134
135 static inline void
136 flow_set_xxreg(struct flow *flow, int idx, ovs_u128 value)
137 {
138     flow->regs[idx * 4] = value.u64.hi >> 32;
139     flow->regs[idx * 4 + 1] = value.u64.hi;
140     flow->regs[idx * 4 + 2] = value.u64.lo >> 32;
141     flow->regs[idx * 4 + 3] = value.u64.lo;
142 }
143
144 static inline int
145 flow_compare_3way(const struct flow *a, const struct flow *b)
146 {
147     return memcmp(a, b, sizeof *a);
148 }
149
150 static inline bool
151 flow_equal(const struct flow *a, const struct flow *b)
152 {
153     return !flow_compare_3way(a, b);
154 }
155
156 static inline size_t
157 flow_hash(const struct flow *flow, uint32_t basis)
158 {
159     return hash_bytes64((const uint64_t *)flow, sizeof *flow, basis);
160 }
161
162 static inline uint16_t
163 ofp_to_u16(ofp_port_t ofp_port)
164 {
165     return (OVS_FORCE uint16_t) ofp_port;
166 }
167
168 static inline uint32_t
169 odp_to_u32(odp_port_t odp_port)
170 {
171     return (OVS_FORCE uint32_t) odp_port;
172 }
173
174 static inline uint32_t
175 ofp11_to_u32(ofp11_port_t ofp11_port)
176 {
177     return (OVS_FORCE uint32_t) ofp11_port;
178 }
179
180 static inline ofp_port_t
181 u16_to_ofp(uint16_t port)
182 {
183     return OFP_PORT_C(port);
184 }
185
186 static inline odp_port_t
187 u32_to_odp(uint32_t port)
188 {
189     return ODP_PORT_C(port);
190 }
191
192 static inline ofp11_port_t
193 u32_to_ofp11(uint32_t port)
194 {
195     return OFP11_PORT_C(port);
196 }
197
198 static inline uint32_t
199 hash_ofp_port(ofp_port_t ofp_port)
200 {
201     return hash_int(ofp_to_u16(ofp_port), 0);
202 }
203
204 static inline uint32_t
205 hash_odp_port(odp_port_t odp_port)
206 {
207     return hash_int(odp_to_u32(odp_port), 0);
208 }
209 \f
210 uint32_t flow_hash_5tuple(const struct flow *flow, uint32_t basis);
211 uint32_t flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis);
212 uint32_t flow_hash_symmetric_l3l4(const struct flow *flow, uint32_t basis,
213                          bool inc_udp_ports );
214
215 /* Initialize a flow with random fields that matter for nx_hash_fields. */
216 void flow_random_hash_fields(struct flow *);
217 void flow_mask_hash_fields(const struct flow *, struct flow_wildcards *,
218                            enum nx_hash_fields);
219 uint32_t flow_hash_fields(const struct flow *, enum nx_hash_fields,
220                           uint16_t basis);
221 const char *flow_hash_fields_to_str(enum nx_hash_fields);
222 bool flow_hash_fields_valid(enum nx_hash_fields);
223
224 uint32_t flow_hash_in_wildcards(const struct flow *,
225                                 const struct flow_wildcards *,
226                                 uint32_t basis);
227
228 bool flow_equal_except(const struct flow *a, const struct flow *b,
229                        const struct flow_wildcards *);
230 \f
231 /* Bitmap for flow values.  For each 1-bit the corresponding flow value is
232  * explicitly specified, other values are zeroes.
233  *
234  * map_t must be wide enough to hold any member of struct flow. */
235 typedef unsigned long long map_t;
236 #define MAP_T_BITS (sizeof(map_t) * CHAR_BIT)
237 #define MAP_1 (map_t)1
238 #define MAP_MAX TYPE_MAXIMUM(map_t)
239
240 #define MAP_IS_SET(MAP, IDX) ((MAP) & (MAP_1 << (IDX)))
241
242 /* Iterate through the indices of all 1-bits in 'MAP'. */
243 #define MAP_FOR_EACH_INDEX(IDX, MAP)            \
244     ULLONG_FOR_EACH_1(IDX, MAP)
245
246 #define FLOWMAP_UNITS DIV_ROUND_UP(FLOW_U64S, MAP_T_BITS)
247
248 struct flowmap {
249     map_t bits[FLOWMAP_UNITS];
250 };
251
252 #define FLOWMAP_EMPTY_INITIALIZER { { 0 } }
253
254 static inline void flowmap_init(struct flowmap *);
255 static inline bool flowmap_equal(struct flowmap, struct flowmap);
256 static inline bool flowmap_is_set(const struct flowmap *, size_t idx);
257 static inline bool flowmap_are_set(const struct flowmap *, size_t idx,
258                                    unsigned int n_bits);
259 static inline void flowmap_set(struct flowmap *, size_t idx,
260                                unsigned int n_bits);
261 static inline void flowmap_clear(struct flowmap *, size_t idx,
262                                  unsigned int n_bits);
263 static inline struct flowmap flowmap_or(struct flowmap, struct flowmap);
264 static inline struct flowmap flowmap_and(struct flowmap, struct flowmap);
265 static inline bool flowmap_is_empty(struct flowmap);
266 static inline unsigned int flowmap_n_1bits(struct flowmap);
267
268 #define FLOWMAP_HAS_FIELD(FM, FIELD)                                    \
269     flowmap_are_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
270
271 #define FLOWMAP_SET(FM, FIELD)                                      \
272     flowmap_set(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
273
274 #define FLOWMAP_SET__(FM, FIELD, SIZE)                  \
275     flowmap_set(FM, FLOW_U64_OFFSET(FIELD),             \
276                 DIV_ROUND_UP(SIZE, sizeof(uint64_t)))
277
278 /* XXX: Only works for full 64-bit units. */
279 #define FLOWMAP_CLEAR(FM, FIELD)                                        \
280     BUILD_ASSERT_DECL(FLOW_U64_OFFREM(FIELD) == 0);                     \
281     BUILD_ASSERT_DECL(sizeof(((struct flow *)0)->FIELD) % sizeof(uint64_t) == 0); \
282     flowmap_clear(FM, FLOW_U64_OFFSET(FIELD), FLOW_U64_SIZE(FIELD))
283
284 /* Iterate through all units in 'FMAP'. */
285 #define FLOWMAP_FOR_EACH_UNIT(UNIT)                     \
286     for ((UNIT) = 0; (UNIT) < FLOWMAP_UNITS; (UNIT)++)
287
288 /* Iterate through all map units in 'FMAP'. */
289 #define FLOWMAP_FOR_EACH_MAP(MAP, FLOWMAP)                              \
290     for (size_t unit__ = 0;                                       \
291          unit__ < FLOWMAP_UNITS && ((MAP) = (FLOWMAP).bits[unit__], true); \
292          unit__++)
293
294 struct flowmap_aux;
295 static inline bool flowmap_next_index(struct flowmap_aux *, size_t *idx);
296
297 #define FLOWMAP_AUX_INITIALIZER(FLOWMAP) { .unit = 0, .map = (FLOWMAP) }
298
299 /* Iterate through all struct flow u64 indices specified by 'MAP'.  This is a
300  * slower but easier version of the FLOWMAP_FOR_EACH_MAP() &
301  * MAP_FOR_EACH_INDEX() combination. */
302 #define FLOWMAP_FOR_EACH_INDEX(IDX, MAP)                            \
303     for (struct flowmap_aux aux__ = FLOWMAP_AUX_INITIALIZER(MAP);   \
304          flowmap_next_index(&aux__, &(IDX));)
305
306 /* Flowmap inline implementations. */
307 static inline void
308 flowmap_init(struct flowmap *fm)
309 {
310     memset(fm, 0, sizeof *fm);
311 }
312
313 static inline bool
314 flowmap_equal(struct flowmap a, struct flowmap b)
315 {
316     return !memcmp(&a, &b, sizeof a);
317 }
318
319 static inline bool
320 flowmap_is_set(const struct flowmap *fm, size_t idx)
321 {
322     return (fm->bits[idx / MAP_T_BITS] & (MAP_1 << (idx % MAP_T_BITS))) != 0;
323 }
324
325 /* Returns 'true' if any of the 'n_bits' bits starting at 'idx' are set in
326  * 'fm'.  'n_bits' can be at most MAP_T_BITS. */
327 static inline bool
328 flowmap_are_set(const struct flowmap *fm, size_t idx, unsigned int n_bits)
329 {
330     map_t n_bits_mask = (MAP_1 << n_bits) - 1;
331     size_t unit = idx / MAP_T_BITS;
332
333     idx %= MAP_T_BITS;
334
335     if (fm->bits[unit] & (n_bits_mask << idx)) {
336         return true;
337     }
338     /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
339      * false-positive array out of bounds error by GCC 4.9. */
340     if (unit + 1 < FLOWMAP_UNITS && idx + n_bits > MAP_T_BITS) {
341         /* Check the remaining bits from the next unit. */
342         return fm->bits[unit + 1] & (n_bits_mask >> (MAP_T_BITS - idx));
343     }
344     return false;
345 }
346
347 /* Set the 'n_bits' consecutive bits in 'fm', starting at bit 'idx'.
348  * 'n_bits' can be at most MAP_T_BITS. */
349 static inline void
350 flowmap_set(struct flowmap *fm, size_t idx, unsigned int n_bits)
351 {
352     map_t n_bits_mask = (MAP_1 << n_bits) - 1;
353     size_t unit = idx / MAP_T_BITS;
354
355     idx %= MAP_T_BITS;
356
357     fm->bits[unit] |= n_bits_mask << idx;
358     /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
359      * false-positive array out of bounds error by GCC 4.9. */
360     if (unit + 1 < FLOWMAP_UNITS && idx + n_bits > MAP_T_BITS) {
361         /* 'MAP_T_BITS - idx' bits were set on 'unit', set the remaining
362          * bits from the next unit. */
363         fm->bits[unit + 1] |= n_bits_mask >> (MAP_T_BITS - idx);
364     }
365 }
366
367 /* Clears the 'n_bits' consecutive bits in 'fm', starting at bit 'idx'.
368  * 'n_bits' can be at most MAP_T_BITS. */
369 static inline void
370 flowmap_clear(struct flowmap *fm, size_t idx, unsigned int n_bits)
371 {
372     map_t n_bits_mask = (MAP_1 << n_bits) - 1;
373     size_t unit = idx / MAP_T_BITS;
374
375     idx %= MAP_T_BITS;
376
377     fm->bits[unit] &= ~(n_bits_mask << idx);
378     /* The seemingly unnecessary bounds check on 'unit' is a workaround for a
379      * false-positive array out of bounds error by GCC 4.9. */
380     if (unit + 1 < FLOWMAP_UNITS && idx + n_bits > MAP_T_BITS) {
381         /* 'MAP_T_BITS - idx' bits were cleared on 'unit', clear the
382          * remaining bits from the next unit. */
383         fm->bits[unit + 1] &= ~(n_bits_mask >> (MAP_T_BITS - idx));
384     }
385 }
386
387 /* OR the bits in the flowmaps. */
388 static inline struct flowmap
389 flowmap_or(struct flowmap a, struct flowmap b)
390 {
391     struct flowmap map;
392     size_t unit;
393
394     FLOWMAP_FOR_EACH_UNIT (unit) {
395         map.bits[unit] = a.bits[unit] | b.bits[unit];
396     }
397     return map;
398 }
399
400 /* AND the bits in the flowmaps. */
401 static inline struct flowmap
402 flowmap_and(struct flowmap a, struct flowmap b)
403 {
404     struct flowmap map;
405     size_t unit;
406
407     FLOWMAP_FOR_EACH_UNIT (unit) {
408         map.bits[unit] = a.bits[unit] & b.bits[unit];
409     }
410     return map;
411 }
412
413 static inline bool
414 flowmap_is_empty(struct flowmap fm)
415 {
416     map_t map;
417
418     FLOWMAP_FOR_EACH_MAP (map, fm) {
419         if (map) {
420             return false;
421         }
422     }
423     return true;
424 }
425
426 static inline unsigned int
427 flowmap_n_1bits(struct flowmap fm)
428 {
429     unsigned int n_1bits = 0;
430     size_t unit;
431
432     FLOWMAP_FOR_EACH_UNIT (unit) {
433         n_1bits += count_1bits(fm.bits[unit]);
434     }
435     return n_1bits;
436 }
437
438 struct flowmap_aux {
439     size_t unit;
440     struct flowmap map;
441 };
442
443 static inline bool
444 flowmap_next_index(struct flowmap_aux *aux, size_t *idx)
445 {
446     for (;;) {
447         map_t *map = &aux->map.bits[aux->unit];
448         if (*map) {
449             *idx = aux->unit * MAP_T_BITS + raw_ctz(*map);
450             *map = zero_rightmost_1bit(*map);
451             return true;
452         }
453         if (++aux->unit >= FLOWMAP_UNITS) {
454             return false;
455         }
456     }
457 }
458
459 \f
460 /* Compressed flow. */
461
462 /* A sparse representation of a "struct flow".
463  *
464  * A "struct flow" is fairly large and tends to be mostly zeros.  Sparse
465  * representation has two advantages.  First, it saves memory and, more
466  * importantly, minimizes the number of accessed cache lines.  Second, it saves
467  * time when the goal is to iterate over only the nonzero parts of the struct.
468  *
469  * The map member hold one bit for each uint64_t in a "struct flow".  Each
470  * 0-bit indicates that the corresponding uint64_t is zero, each 1-bit that it
471  * *may* be nonzero (see below how this applies to minimasks).
472  *
473  * The values indicated by 'map' always follow the miniflow in memory.  The
474  * user of the miniflow is responsible for always having enough storage after
475  * the struct miniflow corresponding to the number of 1-bits in maps.
476  *
477  * Elements in values array are allowed to be zero.  This is useful for "struct
478  * minimatch", for which ensuring that the miniflow and minimask members have
479  * same maps allows optimization.  This allowance applies only to a miniflow
480  * that is not a mask.  That is, a minimask may NOT have zero elements in its
481  * values.
482  *
483  * A miniflow is always dynamically allocated so that the maps are followed by
484  * at least as many elements as there are 1-bits in maps. */
485 struct miniflow {
486     struct flowmap map;
487     /* Followed by:
488      *     uint64_t values[n];
489      * where 'n' is miniflow_n_values(miniflow). */
490 };
491 BUILD_ASSERT_DECL(sizeof(struct miniflow) % sizeof(uint64_t) == 0);
492
493 #define MINIFLOW_VALUES_SIZE(COUNT) ((COUNT) * sizeof(uint64_t))
494
495 static inline uint64_t *miniflow_values(struct miniflow *mf)
496 {
497     return (uint64_t *)(mf + 1);
498 }
499
500 static inline const uint64_t *miniflow_get_values(const struct miniflow *mf)
501 {
502     return (const uint64_t *)(mf + 1);
503 }
504
505 struct pkt_metadata;
506
507 /* The 'dst' must follow with buffer space for FLOW_U64S 64-bit units.
508  * 'dst->map' is ignored on input and set on output to indicate which fields
509  * were extracted. */
510 void miniflow_extract(struct dp_packet *packet, struct miniflow *dst);
511 void miniflow_map_init(struct miniflow *, const struct flow *);
512 void flow_wc_map(const struct flow *, struct flowmap *);
513 size_t miniflow_alloc(struct miniflow *dsts[], size_t n,
514                       const struct miniflow *src);
515 void miniflow_init(struct miniflow *, const struct flow *);
516 void miniflow_clone(struct miniflow *, const struct miniflow *,
517                     size_t n_values);
518 struct miniflow * miniflow_create(const struct flow *);
519
520 void miniflow_expand(const struct miniflow *, struct flow *);
521
522 static inline uint64_t flow_u64_value(const struct flow *flow, size_t index)
523 {
524     return ((uint64_t *)flow)[index];
525 }
526
527 static inline uint64_t *flow_u64_lvalue(struct flow *flow, size_t index)
528 {
529     return &((uint64_t *)flow)[index];
530 }
531
532 static inline size_t
533 miniflow_n_values(const struct miniflow *flow)
534 {
535     return flowmap_n_1bits(flow->map);
536 }
537
538 struct flow_for_each_in_maps_aux {
539     const struct flow *flow;
540     struct flowmap_aux map_aux;
541 };
542
543 static inline bool
544 flow_values_get_next_in_maps(struct flow_for_each_in_maps_aux *aux,
545                              uint64_t *value)
546 {
547     size_t idx;
548
549     if (flowmap_next_index(&aux->map_aux, &idx)) {
550         *value = flow_u64_value(aux->flow, idx);
551         return true;
552     }
553     return false;
554 }
555
556 /* Iterate through all flow u64 values specified by 'MAPS'. */
557 #define FLOW_FOR_EACH_IN_MAPS(VALUE, FLOW, MAPS)            \
558     for (struct flow_for_each_in_maps_aux aux__             \
559              = { (FLOW), FLOWMAP_AUX_INITIALIZER(MAPS) };   \
560          flow_values_get_next_in_maps(&aux__, &(VALUE));)
561
562 struct mf_for_each_in_map_aux {
563     size_t unit;
564     struct flowmap fmap;
565     struct flowmap map;
566     const uint64_t *values;
567 };
568
569 static inline bool
570 mf_get_next_in_map(struct mf_for_each_in_map_aux *aux,
571                    uint64_t *value)
572 {
573     map_t *map, *fmap;
574     map_t rm1bit;
575
576     while (OVS_UNLIKELY(!*(map = &aux->map.bits[aux->unit]))) {
577         /* Skip remaining data in the previous unit. */
578         aux->values += count_1bits(aux->fmap.bits[aux->unit]);
579         if (++aux->unit == FLOWMAP_UNITS) {
580             return false;
581         }
582     }
583
584     rm1bit = rightmost_1bit(*map);
585     *map -= rm1bit;
586     fmap = &aux->fmap.bits[aux->unit];
587
588     if (OVS_LIKELY(*fmap & rm1bit)) {
589         map_t trash = *fmap & (rm1bit - 1);
590
591         *fmap -= trash;
592         /* count_1bits() is fast for systems where speed matters (e.g.,
593          * DPDK), so we don't try avoid using it.
594          * Advance 'aux->values' to point to the value for 'rm1bit'. */
595         aux->values += count_1bits(trash);
596
597         *value = *aux->values;
598     } else {
599         *value = 0;
600     }
601     return true;
602 }
603
604 /* Iterate through miniflow u64 values specified by 'FLOWMAP'. */
605 #define MINIFLOW_FOR_EACH_IN_FLOWMAP(VALUE, FLOW, FLOWMAP)          \
606     for (struct mf_for_each_in_map_aux aux__ =                      \
607         { 0, (FLOW)->map, (FLOWMAP), miniflow_get_values(FLOW) };   \
608          mf_get_next_in_map(&aux__, &(VALUE));)
609
610 /* This can be used when it is known that 'idx' is set in 'map'. */
611 static inline const uint64_t *
612 miniflow_values_get__(const uint64_t *values, map_t map, size_t idx)
613 {
614     return values + count_1bits(map & ((MAP_1 << idx) - 1));
615 }
616
617 /* This can be used when it is known that 'u64_idx' is set in
618  * the map of 'mf'. */
619 static inline const uint64_t *
620 miniflow_get__(const struct miniflow *mf, size_t idx)
621 {
622     const uint64_t *values = miniflow_get_values(mf);
623     const map_t *map = mf->map.bits;
624
625     while (idx >= MAP_T_BITS) {
626         idx -= MAP_T_BITS;
627         values += count_1bits(*map++);
628     }
629     return miniflow_values_get__(values, *map, idx);
630 }
631
632 #define MINIFLOW_IN_MAP(MF, IDX) flowmap_is_set(&(MF)->map, IDX)
633
634 /* Get the value of the struct flow 'FIELD' as up to 8 byte wide integer type
635  * 'TYPE' from miniflow 'MF'. */
636 #define MINIFLOW_GET_TYPE(MF, TYPE, FIELD)                              \
637     (MINIFLOW_IN_MAP(MF, FLOW_U64_OFFSET(FIELD))                        \
638      ? ((OVS_FORCE const TYPE *)miniflow_get__(MF, FLOW_U64_OFFSET(FIELD))) \
639      [FLOW_U64_OFFREM(FIELD) / sizeof(TYPE)]                            \
640      : 0)
641
642 #define MINIFLOW_GET_U128(FLOW, FIELD)                                  \
643     (ovs_u128) { .u64 = {                                               \
644             (MINIFLOW_IN_MAP(FLOW, FLOW_U64_OFFSET(FIELD)) ?            \
645              *miniflow_get__(FLOW, FLOW_U64_OFFSET(FIELD)) : 0),        \
646             (MINIFLOW_IN_MAP(FLOW, FLOW_U64_OFFSET(FIELD) + 1) ?        \
647              *miniflow_get__(FLOW, FLOW_U64_OFFSET(FIELD) + 1) : 0) } }
648
649 #define MINIFLOW_GET_U8(FLOW, FIELD)            \
650     MINIFLOW_GET_TYPE(FLOW, uint8_t, FIELD)
651 #define MINIFLOW_GET_U16(FLOW, FIELD)           \
652     MINIFLOW_GET_TYPE(FLOW, uint16_t, FIELD)
653 #define MINIFLOW_GET_BE16(FLOW, FIELD)          \
654     MINIFLOW_GET_TYPE(FLOW, ovs_be16, FIELD)
655 #define MINIFLOW_GET_U32(FLOW, FIELD)           \
656     MINIFLOW_GET_TYPE(FLOW, uint32_t, FIELD)
657 #define MINIFLOW_GET_BE32(FLOW, FIELD)          \
658     MINIFLOW_GET_TYPE(FLOW, ovs_be32, FIELD)
659 #define MINIFLOW_GET_U64(FLOW, FIELD)           \
660     MINIFLOW_GET_TYPE(FLOW, uint64_t, FIELD)
661 #define MINIFLOW_GET_BE64(FLOW, FIELD)          \
662     MINIFLOW_GET_TYPE(FLOW, ovs_be64, FIELD)
663
664 static inline uint64_t miniflow_get(const struct miniflow *,
665                                     unsigned int u64_ofs);
666 static inline uint32_t miniflow_get_u32(const struct miniflow *,
667                                         unsigned int u32_ofs);
668 static inline ovs_be32 miniflow_get_be32(const struct miniflow *,
669                                          unsigned int be32_ofs);
670 static inline uint16_t miniflow_get_vid(const struct miniflow *);
671 static inline uint16_t miniflow_get_tcp_flags(const struct miniflow *);
672 static inline ovs_be64 miniflow_get_metadata(const struct miniflow *);
673
674 bool miniflow_equal(const struct miniflow *a, const struct miniflow *b);
675 bool miniflow_equal_in_minimask(const struct miniflow *a,
676                                 const struct miniflow *b,
677                                 const struct minimask *);
678 bool miniflow_equal_flow_in_minimask(const struct miniflow *a,
679                                      const struct flow *b,
680                                      const struct minimask *);
681 uint32_t miniflow_hash_5tuple(const struct miniflow *flow, uint32_t basis);
682
683 \f
684 /* Compressed flow wildcards. */
685
686 /* A sparse representation of a "struct flow_wildcards".
687  *
688  * See the large comment on struct miniflow for details.
689  *
690  * Note: While miniflow can have zero data for a 1-bit in the map,
691  * a minimask may not!  We rely on this in the implementation. */
692 struct minimask {
693     struct miniflow masks;
694 };
695
696 void minimask_init(struct minimask *, const struct flow_wildcards *);
697 struct minimask * minimask_create(const struct flow_wildcards *);
698 void minimask_combine(struct minimask *dst,
699                       const struct minimask *a, const struct minimask *b,
700                       uint64_t storage[FLOW_U64S]);
701
702 void minimask_expand(const struct minimask *, struct flow_wildcards *);
703
704 static inline uint32_t minimask_get_u32(const struct minimask *,
705                                         unsigned int u32_ofs);
706 static inline ovs_be32 minimask_get_be32(const struct minimask *,
707                                          unsigned int be32_ofs);
708 static inline uint16_t minimask_get_vid_mask(const struct minimask *);
709 static inline ovs_be64 minimask_get_metadata_mask(const struct minimask *);
710
711 bool minimask_equal(const struct minimask *a, const struct minimask *b);
712 bool minimask_has_extra(const struct minimask *, const struct minimask *);
713
714 \f
715 /* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
716  * or fields. */
717 static inline bool
718 minimask_is_catchall(const struct minimask *mask)
719 {
720     /* For every 1-bit in mask's map, the corresponding value is non-zero,
721      * so the only way the mask can not fix any bits or fields is for the
722      * map the be zero. */
723     return flowmap_is_empty(mask->masks.map);
724 }
725
726 /* Returns the uint64_t that would be at byte offset '8 * u64_ofs' if 'flow'
727  * were expanded into a "struct flow". */
728 static inline uint64_t miniflow_get(const struct miniflow *flow,
729                                     unsigned int u64_ofs)
730 {
731     return MINIFLOW_IN_MAP(flow, u64_ofs) ? *miniflow_get__(flow, u64_ofs) : 0;
732 }
733
734 static inline uint32_t miniflow_get_u32(const struct miniflow *flow,
735                                         unsigned int u32_ofs)
736 {
737     uint64_t value = miniflow_get(flow, u32_ofs / 2);
738
739 #if WORDS_BIGENDIAN
740     return (u32_ofs & 1) ? value : value >> 32;
741 #else
742     return (u32_ofs & 1) ? value >> 32 : value;
743 #endif
744 }
745
746 static inline ovs_be32 miniflow_get_be32(const struct miniflow *flow,
747                                          unsigned int be32_ofs)
748 {
749     return (OVS_FORCE ovs_be32)miniflow_get_u32(flow, be32_ofs);
750 }
751
752 /* Returns the VID within the vlan_tci member of the "struct flow" represented
753  * by 'flow'. */
754 static inline uint16_t
755 miniflow_get_vid(const struct miniflow *flow)
756 {
757     ovs_be16 tci = MINIFLOW_GET_BE16(flow, vlan_tci);
758     return vlan_tci_to_vid(tci);
759 }
760
761 /* Returns the uint32_t that would be at byte offset '4 * u32_ofs' if 'mask'
762  * were expanded into a "struct flow_wildcards". */
763 static inline uint32_t
764 minimask_get_u32(const struct minimask *mask, unsigned int u32_ofs)
765 {
766     return miniflow_get_u32(&mask->masks, u32_ofs);
767 }
768
769 static inline ovs_be32
770 minimask_get_be32(const struct minimask *mask, unsigned int be32_ofs)
771 {
772     return (OVS_FORCE ovs_be32)minimask_get_u32(mask, be32_ofs);
773 }
774
775 /* Returns the VID mask within the vlan_tci member of the "struct
776  * flow_wildcards" represented by 'mask'. */
777 static inline uint16_t
778 minimask_get_vid_mask(const struct minimask *mask)
779 {
780     return miniflow_get_vid(&mask->masks);
781 }
782
783 /* Returns the value of the "tcp_flags" field in 'flow'. */
784 static inline uint16_t
785 miniflow_get_tcp_flags(const struct miniflow *flow)
786 {
787     return ntohs(MINIFLOW_GET_BE16(flow, tcp_flags));
788 }
789
790 /* Returns the value of the OpenFlow 1.1+ "metadata" field in 'flow'. */
791 static inline ovs_be64
792 miniflow_get_metadata(const struct miniflow *flow)
793 {
794     return MINIFLOW_GET_BE64(flow, metadata);
795 }
796
797 /* Returns the mask for the OpenFlow 1.1+ "metadata" field in 'mask'.
798  *
799  * The return value is all-1-bits if 'mask' matches on the whole value of the
800  * metadata field, all-0-bits if 'mask' entirely wildcards the metadata field,
801  * or some other value if the metadata field is partially matched, partially
802  * wildcarded. */
803 static inline ovs_be64
804 minimask_get_metadata_mask(const struct minimask *mask)
805 {
806     return MINIFLOW_GET_BE64(&mask->masks, metadata);
807 }
808
809 /* Perform a bitwise OR of miniflow 'src' flow data specified in 'subset' with
810  * the equivalent fields in 'dst', storing the result in 'dst'.  'subset' must
811  * be a subset of 'src's map. */
812 static inline void
813 flow_union_with_miniflow_subset(struct flow *dst, const struct miniflow *src,
814                                 struct flowmap subset)
815 {
816     uint64_t *dst_u64 = (uint64_t *) dst;
817     const uint64_t *p = miniflow_get_values(src);
818     map_t map;
819
820     FLOWMAP_FOR_EACH_MAP (map, subset) {
821         size_t idx;
822
823         MAP_FOR_EACH_INDEX(idx, map) {
824             dst_u64[idx] |= *p++;
825         }
826         dst_u64 += MAP_T_BITS;
827     }
828 }
829
830 /* Perform a bitwise OR of miniflow 'src' flow data with the equivalent
831  * fields in 'dst', storing the result in 'dst'. */
832 static inline void
833 flow_union_with_miniflow(struct flow *dst, const struct miniflow *src)
834 {
835     flow_union_with_miniflow_subset(dst, src, src->map);
836 }
837
838 static inline void
839 pkt_metadata_from_flow(struct pkt_metadata *md, const struct flow *flow)
840 {
841     md->recirc_id = flow->recirc_id;
842     md->dp_hash = flow->dp_hash;
843     flow_tnl_copy__(&md->tunnel, &flow->tunnel);
844     md->skb_priority = flow->skb_priority;
845     md->pkt_mark = flow->pkt_mark;
846     md->in_port = flow->in_port;
847     md->ct_state = flow->ct_state;
848     md->ct_zone = flow->ct_zone;
849     md->ct_mark = flow->ct_mark;
850     md->ct_label = flow->ct_label;
851 }
852
853 static inline bool is_ip_any(const struct flow *flow)
854 {
855     return dl_type_is_ip_any(flow->dl_type);
856 }
857
858 static inline bool is_icmpv4(const struct flow *flow,
859                              struct flow_wildcards *wc)
860 {
861     if (flow->dl_type == htons(ETH_TYPE_IP)) {
862         if (wc) {
863             memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
864         }
865         return flow->nw_proto == IPPROTO_ICMP;
866     }
867     return false;
868 }
869
870 static inline bool is_icmpv6(const struct flow *flow,
871                              struct flow_wildcards *wc)
872 {
873     if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
874         if (wc) {
875             memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
876         }
877         return flow->nw_proto == IPPROTO_ICMPV6;
878     }
879     return false;
880 }
881
882 static inline bool is_nd(const struct flow *flow,
883                          struct flow_wildcards *wc)
884 {
885     if (is_icmpv6(flow, wc)) {
886         if (wc) {
887             memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
888         }
889         if (flow->tp_dst != htons(0)) {
890             return false;
891         }
892
893         if (wc) {
894             memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
895         }
896         return (flow->tp_src == htons(ND_NEIGHBOR_SOLICIT) ||
897                 flow->tp_src == htons(ND_NEIGHBOR_ADVERT));
898     }
899     return false;
900 }
901
902 static inline bool is_igmp(const struct flow *flow, struct flow_wildcards *wc)
903 {
904     if (flow->dl_type == htons(ETH_TYPE_IP)) {
905         if (wc) {
906             memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
907         }
908         return flow->nw_proto == IPPROTO_IGMP;
909     }
910     return false;
911 }
912
913 static inline bool is_mld(const struct flow *flow,
914                           struct flow_wildcards *wc)
915 {
916     if (is_icmpv6(flow, wc)) {
917         if (wc) {
918             memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
919         }
920         return (flow->tp_src == htons(MLD_QUERY)
921                 || flow->tp_src == htons(MLD_REPORT)
922                 || flow->tp_src == htons(MLD_DONE)
923                 || flow->tp_src == htons(MLD2_REPORT));
924     }
925     return false;
926 }
927
928 static inline bool is_mld_query(const struct flow *flow,
929                                 struct flow_wildcards *wc)
930 {
931     if (is_icmpv6(flow, wc)) {
932         if (wc) {
933             memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
934         }
935         return flow->tp_src == htons(MLD_QUERY);
936     }
937     return false;
938 }
939
940 static inline bool is_mld_report(const struct flow *flow,
941                                  struct flow_wildcards *wc)
942 {
943     return is_mld(flow, wc) && !is_mld_query(flow, wc);
944 }
945
946 static inline bool is_stp(const struct flow *flow)
947 {
948     return (eth_addr_equals(flow->dl_dst, eth_addr_stp)
949             && flow->dl_type == htons(FLOW_DL_TYPE_NONE));
950 }
951
952 #endif /* flow.h */