2 * Copyright (c) 2010, 2011, 2012, 2013, 2014, 2016, 2017, 2019 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 "multipath.h"
20 #include <sys/types.h>
21 #include <netinet/in.h>
22 #include <arpa/inet.h>
26 #include "openflow/nicira-ext.h"
27 #include "openvswitch/dynamic-string.h"
28 #include "openvswitch/ofp-actions.h"
29 #include "openvswitch/ofp-errors.h"
33 /* Checks that 'mp' is valid on flow. Returns 0 if it is valid, otherwise an
36 multipath_check(const struct ofpact_multipath
*mp
,
37 const struct match
*match
)
39 return mf_check_dst(&mp
->dst
, match
);
42 /* multipath_execute(). */
44 static uint16_t multipath_algorithm(uint32_t hash
, enum nx_mp_algorithm
,
45 unsigned int n_links
, unsigned int arg
);
47 /* Executes 'mp' based on the current contents of 'flow', writing the results
48 * back into 'flow'. Sets fields in 'wc' that were used to calculate
51 multipath_execute(const struct ofpact_multipath
*mp
, struct flow
*flow
,
52 struct flow_wildcards
*wc
)
54 /* Calculate value to store. */
55 uint32_t hash
= flow_hash_fields(flow
, mp
->fields
, mp
->basis
);
56 uint16_t link
= multipath_algorithm(hash
, mp
->algorithm
,
57 mp
->max_link
+ 1, mp
->arg
);
59 flow_mask_hash_fields(flow
, wc
, mp
->fields
);
60 nxm_reg_load(&mp
->dst
, link
, flow
, wc
);
64 algorithm_hrw(uint32_t hash
, unsigned int n_links
)
71 best_weight
= hash_2words(hash
, 0);
72 for (link
= 1; link
< n_links
; link
++) {
73 uint32_t weight
= hash_2words(hash
, link
);
74 if (weight
> best_weight
) {
82 /* Works for 'x' in the range [1,65536], which is all we need. */
84 round_up_pow2(unsigned int x
)
95 algorithm_iter_hash(uint32_t hash
, unsigned int n_links
, unsigned int modulo
)
100 if (modulo
< n_links
|| modulo
/ 2 > n_links
) {
101 modulo
= round_up_pow2(n_links
);
106 link
= hash_2words(hash
, i
++) % modulo
;
107 } while (link
>= n_links
);
113 multipath_algorithm(uint32_t hash
, enum nx_mp_algorithm algorithm
,
114 unsigned int n_links
, unsigned int arg
)
117 case NX_MP_ALG_MODULO_N
:
118 return hash
% n_links
;
120 case NX_MP_ALG_HASH_THRESHOLD
:
124 return hash
/ (UINT32_MAX
/ n_links
+ 1);
127 return (n_links
<= 64
128 ? algorithm_hrw(hash
, n_links
)
129 : algorithm_iter_hash(hash
, n_links
, 0));
131 case NX_MP_ALG_ITER_HASH
:
132 return algorithm_iter_hash(hash
, n_links
, arg
);
138 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
139 * 'mp' accordingly. ovs-actions(7) describes the format parsed.
141 * Returns NULL if successful, otherwise a malloc()'d string describing the
142 * error. The caller is responsible for freeing the returned string.*/
143 static char * OVS_WARN_UNUSED_RESULT
144 multipath_parse__(struct ofpact_multipath
*mp
, const char *s_
, char *s
)
146 char *save_ptr
= NULL
;
147 char *fields
, *basis
, *algorithm
, *n_links_str
, *arg
, *dst
;
151 fields
= strtok_r(s
, ", ", &save_ptr
);
152 basis
= strtok_r(NULL
, ", ", &save_ptr
);
153 algorithm
= strtok_r(NULL
, ", ", &save_ptr
);
154 n_links_str
= strtok_r(NULL
, ", ", &save_ptr
);
155 arg
= strtok_r(NULL
, ", ", &save_ptr
);
156 dst
= strtok_r(NULL
, ", ", &save_ptr
);
158 return xasprintf("%s: not enough arguments to multipath action", s_
);
161 ofpact_init_MULTIPATH(mp
);
162 if (!strcasecmp(fields
, "eth_src")) {
163 mp
->fields
= NX_HASH_FIELDS_ETH_SRC
;
164 } else if (!strcasecmp(fields
, "symmetric_l4")) {
165 mp
->fields
= NX_HASH_FIELDS_SYMMETRIC_L4
;
166 } else if (!strcasecmp(fields
, "symmetric_l3l4")) {
167 mp
->fields
= NX_HASH_FIELDS_SYMMETRIC_L3L4
;
168 } else if (!strcasecmp(fields
, "symmetric_l3l4+udp")) {
169 mp
->fields
= NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP
;
170 } else if (!strcasecmp(fields
, "nw_src")) {
171 mp
->fields
= NX_HASH_FIELDS_NW_SRC
;
172 } else if (!strcasecmp(fields
, "nw_dst")) {
173 mp
->fields
= NX_HASH_FIELDS_NW_DST
;
174 } else if (!strcasecmp(fields
, "symmetric_l3")) {
175 mp
->fields
= NX_HASH_FIELDS_SYMMETRIC_L3
;
177 return xasprintf("%s: unknown fields `%s'", s_
, fields
);
179 mp
->basis
= atoi(basis
);
180 if (!strcasecmp(algorithm
, "modulo_n")) {
181 mp
->algorithm
= NX_MP_ALG_MODULO_N
;
182 } else if (!strcasecmp(algorithm
, "hash_threshold")) {
183 mp
->algorithm
= NX_MP_ALG_HASH_THRESHOLD
;
184 } else if (!strcasecmp(algorithm
, "hrw")) {
185 mp
->algorithm
= NX_MP_ALG_HRW
;
186 } else if (!strcasecmp(algorithm
, "iter_hash")) {
187 mp
->algorithm
= NX_MP_ALG_ITER_HASH
;
189 return xasprintf("%s: unknown algorithm `%s'", s_
, algorithm
);
191 n_links
= atoi(n_links_str
);
192 if (n_links
< 1 || n_links
> 65536) {
193 return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
196 mp
->max_link
= n_links
- 1;
199 error
= mf_parse_subfield(&mp
->dst
, dst
);
203 if (!mf_nxm_header(mp
->dst
.field
->id
)) {
204 return xasprintf("%s: experimenter OXM field '%s' not supported",
207 if (mp
->dst
.n_bits
< 16 && n_links
> (1u << mp
->dst
.n_bits
)) {
208 return xasprintf("%s: %d-bit destination field has %u possible "
209 "values, less than specified n_links %d",
210 s_
, mp
->dst
.n_bits
, 1u << mp
->dst
.n_bits
, n_links
);
216 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
217 * 'mp' accordingly. ovs-actions(7) describes the format parsed.
219 * Returns NULL if successful, otherwise a malloc()'d string describing the
220 * error. The caller is responsible for freeing the returned string. */
221 char * OVS_WARN_UNUSED_RESULT
222 multipath_parse(struct ofpact_multipath
*mp
, const char *s_
)
224 char *s
= xstrdup(s_
);
225 char *error
= multipath_parse__(mp
, s_
, s
);
230 /* Appends a description of 'mp' to 's', in the format that ovs-actions(7)
233 multipath_format(const struct ofpact_multipath
*mp
, struct ds
*s
)
235 const char *fields
, *algorithm
;
237 fields
= flow_hash_fields_to_str(mp
->fields
);
239 switch (mp
->algorithm
) {
240 case NX_MP_ALG_MODULO_N
:
241 algorithm
= "modulo_n";
243 case NX_MP_ALG_HASH_THRESHOLD
:
244 algorithm
= "hash_threshold";
249 case NX_MP_ALG_ITER_HASH
:
250 algorithm
= "iter_hash";
253 algorithm
= "<unknown>";
256 ds_put_format(s
, "%smultipath(%s%s,%"PRIu16
",%s,%d,%"PRIu32
",",
257 colors
.paren
, colors
.end
, fields
, mp
->basis
, algorithm
,
258 mp
->max_link
+ 1, mp
->arg
);
259 mf_format_subfield(&mp
->dst
, s
);
260 ds_put_format(s
, "%s)%s", colors
.paren
, colors
.end
);