2 * Copyright (c) 2010, 2011, 2012, 2013, 2014, 2016 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 <arpa/inet.h>
22 #include <sys/types.h>
23 #include <netinet/in.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"
30 #include "openvswitch/ofp-util.h"
34 /* Checks that 'mp' is valid on flow. Returns 0 if it is valid, otherwise an
37 multipath_check(const struct ofpact_multipath *mp,
38 const struct flow *flow)
40 return mf_check_dst(&mp->dst, flow);
43 /* multipath_execute(). */
45 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
46 unsigned int n_links, unsigned int arg);
48 /* Executes 'mp' based on the current contents of 'flow', writing the results
49 * back into 'flow'. Sets fields in 'wc' that were used to calculate
52 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
53 struct flow_wildcards *wc)
55 /* Calculate value to store. */
56 uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
57 uint16_t link = multipath_algorithm(hash, mp->algorithm,
58 mp->max_link + 1, mp->arg);
60 flow_mask_hash_fields(flow, wc, mp->fields);
61 nxm_reg_load(&mp->dst, link, flow, wc);
65 algorithm_hrw(uint32_t hash, unsigned int n_links)
72 best_weight = hash_2words(hash, 0);
73 for (link = 1; link < n_links; link++) {
74 uint32_t weight = hash_2words(hash, link);
75 if (weight > best_weight) {
83 /* Works for 'x' in the range [1,65536], which is all we need. */
85 round_up_pow2(unsigned int x)
96 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
101 if (modulo < n_links || modulo / 2 > n_links) {
102 modulo = round_up_pow2(n_links);
107 link = hash_2words(hash, i++) % modulo;
108 } while (link >= n_links);
114 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
115 unsigned int n_links, unsigned int arg)
118 case NX_MP_ALG_MODULO_N:
119 return hash % n_links;
121 case NX_MP_ALG_HASH_THRESHOLD:
125 return hash / (UINT32_MAX / n_links + 1);
128 return (n_links <= 64
129 ? algorithm_hrw(hash, n_links)
130 : algorithm_iter_hash(hash, n_links, 0));
132 case NX_MP_ALG_ITER_HASH:
133 return algorithm_iter_hash(hash, n_links, arg);
139 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
140 * 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
142 * Returns NULL if successful, otherwise a malloc()'d string describing the
143 * error. The caller is responsible for freeing the returned string.*/
144 static char * OVS_WARN_UNUSED_RESULT
145 multipath_parse__(struct ofpact_multipath *mp, const char *s_, char *s)
147 char *save_ptr = NULL;
148 char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
152 fields = strtok_r(s, ", ", &save_ptr);
153 basis = strtok_r(NULL, ", ", &save_ptr);
154 algorithm = strtok_r(NULL, ", ", &save_ptr);
155 n_links_str = strtok_r(NULL, ", ", &save_ptr);
156 arg = strtok_r(NULL, ", ", &save_ptr);
157 dst = strtok_r(NULL, ", ", &save_ptr);
159 return xasprintf("%s: not enough arguments to multipath action", s_);
162 ofpact_init_MULTIPATH(mp);
163 if (!strcasecmp(fields, "eth_src")) {
164 mp->fields = NX_HASH_FIELDS_ETH_SRC;
165 } else if (!strcasecmp(fields, "symmetric_l4")) {
166 mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
167 } else if (!strcasecmp(fields, "symmetric_l3l4")) {
168 mp->fields = NX_HASH_FIELDS_SYMMETRIC_L3L4;
169 } else if (!strcasecmp(fields, "symmetric_l3l4+udp")) {
170 mp->fields = NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP;
172 return xasprintf("%s: unknown fields `%s'", s_, fields);
174 mp->basis = atoi(basis);
175 if (!strcasecmp(algorithm, "modulo_n")) {
176 mp->algorithm = NX_MP_ALG_MODULO_N;
177 } else if (!strcasecmp(algorithm, "hash_threshold")) {
178 mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
179 } else if (!strcasecmp(algorithm, "hrw")) {
180 mp->algorithm = NX_MP_ALG_HRW;
181 } else if (!strcasecmp(algorithm, "iter_hash")) {
182 mp->algorithm = NX_MP_ALG_ITER_HASH;
184 return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
186 n_links = atoi(n_links_str);
187 if (n_links < 1 || n_links > 65536) {
188 return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
191 mp->max_link = n_links - 1;
194 error = mf_parse_subfield(&mp->dst, dst);
198 if (!mf_nxm_header(mp->dst.field->id)) {
199 return xasprintf("%s: experimenter OXM field '%s' not supported",
202 if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
203 return xasprintf("%s: %d-bit destination field has %u possible "
204 "values, less than specified n_links %d",
205 s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
211 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
212 * 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
214 * Returns NULL if successful, otherwise a malloc()'d string describing the
215 * error. The caller is responsible for freeing the returned string. */
216 char * OVS_WARN_UNUSED_RESULT
217 multipath_parse(struct ofpact_multipath *mp, const char *s_)
219 char *s = xstrdup(s_);
220 char *error = multipath_parse__(mp, s_, s);
225 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
228 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
230 const char *fields, *algorithm;
232 fields = flow_hash_fields_to_str(mp->fields);
234 switch (mp->algorithm) {
235 case NX_MP_ALG_MODULO_N:
236 algorithm = "modulo_n";
238 case NX_MP_ALG_HASH_THRESHOLD:
239 algorithm = "hash_threshold";
244 case NX_MP_ALG_ITER_HASH:
245 algorithm = "iter_hash";
248 algorithm = "<unknown>";
251 ds_put_format(s, "%smultipath(%s%s,%"PRIu16",%s,%d,%"PRIu16",",
252 colors.paren, colors.end, fields, mp->basis, algorithm,
253 mp->max_link + 1, mp->arg);
254 mf_format_subfield(&mp->dst, s);
255 ds_put_format(s, "%s)%s", colors.paren, colors.end);