2 * Copyright (c) 2010, 2011, 2012, 2013 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>
24 #include "dynamic-string.h"
26 #include "ofp-actions.h"
27 #include "ofp-errors.h"
29 #include "openflow/nicira-ext.h"
33 VLOG_DEFINE_THIS_MODULE(multipath);
35 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
37 /* Converts 'nam' into 'mp'. Returns 0 if successful, otherwise an
40 multipath_from_openflow(const struct nx_action_multipath *nam,
41 struct ofpact_multipath *mp)
43 uint32_t n_links = ntohs(nam->max_link) + 1;
44 size_t min_n_bits = log_2_ceil(n_links);
46 ofpact_init_MULTIPATH(mp);
47 mp->fields = ntohs(nam->fields);
48 mp->basis = ntohs(nam->basis);
49 mp->algorithm = ntohs(nam->algorithm);
50 mp->max_link = ntohs(nam->max_link);
51 mp->arg = ntohl(nam->arg);
52 mp->dst.field = mf_from_nxm_header(ntohl(nam->dst));
53 mp->dst.ofs = nxm_decode_ofs(nam->ofs_nbits);
54 mp->dst.n_bits = nxm_decode_n_bits(nam->ofs_nbits);
56 if (!flow_hash_fields_valid(mp->fields)) {
57 VLOG_WARN_RL(&rl, "unsupported fields %d", (int) mp->fields);
58 return OFPERR_OFPBAC_BAD_ARGUMENT;
59 } else if (mp->algorithm != NX_MP_ALG_MODULO_N
60 && mp->algorithm != NX_MP_ALG_HASH_THRESHOLD
61 && mp->algorithm != NX_MP_ALG_HRW
62 && mp->algorithm != NX_MP_ALG_ITER_HASH) {
63 VLOG_WARN_RL(&rl, "unsupported algorithm %d", (int) mp->algorithm);
64 return OFPERR_OFPBAC_BAD_ARGUMENT;
65 } else if (mp->dst.n_bits < min_n_bits) {
66 VLOG_WARN_RL(&rl, "multipath action requires at least %"PRIuSIZE" bits for "
67 "%"PRIu32" links", min_n_bits, n_links);
68 return OFPERR_OFPBAC_BAD_ARGUMENT;
71 return multipath_check(mp, NULL);
74 /* Checks that 'mp' is valid on flow. Returns 0 if it is valid, otherwise an
77 multipath_check(const struct ofpact_multipath *mp,
78 const struct flow *flow)
80 return mf_check_dst(&mp->dst, flow);
83 /* Converts 'mp' into an OpenFlow NXAST_MULTIPATH action, which it appends to
86 multipath_to_nxast(const struct ofpact_multipath *mp, struct ofpbuf *openflow)
88 struct nx_action_multipath *nam = ofputil_put_NXAST_MULTIPATH(openflow);
90 nam->fields = htons(mp->fields);
91 nam->basis = htons(mp->basis);
92 nam->algorithm = htons(mp->algorithm);
93 nam->max_link = htons(mp->max_link);
94 nam->arg = htonl(mp->arg);
95 nam->ofs_nbits = nxm_encode_ofs_nbits(mp->dst.ofs, mp->dst.n_bits);
96 nam->dst = htonl(mp->dst.field->nxm_header);
99 /* multipath_execute(). */
101 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
102 unsigned int n_links, unsigned int arg);
104 /* Executes 'mp' based on the current contents of 'flow', writing the results
105 * back into 'flow'. Sets fields in 'wc' that were used to calculate
108 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
109 struct flow_wildcards *wc)
111 /* Calculate value to store. */
112 uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
113 uint16_t link = multipath_algorithm(hash, mp->algorithm,
114 mp->max_link + 1, mp->arg);
116 flow_mask_hash_fields(flow, wc, mp->fields);
117 nxm_reg_load(&mp->dst, link, flow, wc);
121 algorithm_hrw(uint32_t hash, unsigned int n_links)
123 uint32_t best_weight;
128 best_weight = hash_2words(hash, 0);
129 for (link = 1; link < n_links; link++) {
130 uint32_t weight = hash_2words(hash, link);
131 if (weight > best_weight) {
133 best_weight = weight;
139 /* Works for 'x' in the range [1,65536], which is all we need. */
141 round_up_pow2(unsigned int x)
152 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
157 if (modulo < n_links || modulo / 2 > n_links) {
158 modulo = round_up_pow2(n_links);
163 link = hash_2words(hash, i++) % modulo;
164 } while (link >= n_links);
170 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
171 unsigned int n_links, unsigned int arg)
174 case NX_MP_ALG_MODULO_N:
175 return hash % n_links;
177 case NX_MP_ALG_HASH_THRESHOLD:
181 return hash / (UINT32_MAX / n_links + 1);
184 return (n_links <= 64
185 ? algorithm_hrw(hash, n_links)
186 : algorithm_iter_hash(hash, n_links, 0));
188 case NX_MP_ALG_ITER_HASH:
189 return algorithm_iter_hash(hash, n_links, arg);
195 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
196 * 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
198 * Returns NULL if successful, otherwise a malloc()'d string describing the
199 * error. The caller is responsible for freeing the returned string.*/
200 static char * WARN_UNUSED_RESULT
201 multipath_parse__(struct ofpact_multipath *mp, const char *s_, char *s)
203 char *save_ptr = NULL;
204 char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
208 fields = strtok_r(s, ", ", &save_ptr);
209 basis = strtok_r(NULL, ", ", &save_ptr);
210 algorithm = strtok_r(NULL, ", ", &save_ptr);
211 n_links_str = strtok_r(NULL, ", ", &save_ptr);
212 arg = strtok_r(NULL, ", ", &save_ptr);
213 dst = strtok_r(NULL, ", ", &save_ptr);
215 return xasprintf("%s: not enough arguments to multipath action", s_);
218 ofpact_init_MULTIPATH(mp);
219 if (!strcasecmp(fields, "eth_src")) {
220 mp->fields = NX_HASH_FIELDS_ETH_SRC;
221 } else if (!strcasecmp(fields, "symmetric_l4")) {
222 mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
224 return xasprintf("%s: unknown fields `%s'", s_, fields);
226 mp->basis = atoi(basis);
227 if (!strcasecmp(algorithm, "modulo_n")) {
228 mp->algorithm = NX_MP_ALG_MODULO_N;
229 } else if (!strcasecmp(algorithm, "hash_threshold")) {
230 mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
231 } else if (!strcasecmp(algorithm, "hrw")) {
232 mp->algorithm = NX_MP_ALG_HRW;
233 } else if (!strcasecmp(algorithm, "iter_hash")) {
234 mp->algorithm = NX_MP_ALG_ITER_HASH;
236 return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
238 n_links = atoi(n_links_str);
239 if (n_links < 1 || n_links > 65536) {
240 return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
243 mp->max_link = n_links - 1;
246 error = mf_parse_subfield(&mp->dst, dst);
250 if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
251 return xasprintf("%s: %d-bit destination field has %u possible "
252 "values, less than specified n_links %d",
253 s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
259 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
260 * 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
262 * Returns NULL if successful, otherwise a malloc()'d string describing the
263 * error. The caller is responsible for freeing the returned string. */
264 char * WARN_UNUSED_RESULT
265 multipath_parse(struct ofpact_multipath *mp, const char *s_)
267 char *s = xstrdup(s_);
268 char *error = multipath_parse__(mp, s_, s);
273 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
276 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
278 const char *fields, *algorithm;
280 fields = flow_hash_fields_to_str(mp->fields);
282 switch (mp->algorithm) {
283 case NX_MP_ALG_MODULO_N:
284 algorithm = "modulo_n";
286 case NX_MP_ALG_HASH_THRESHOLD:
287 algorithm = "hash_threshold";
292 case NX_MP_ALG_ITER_HASH:
293 algorithm = "iter_hash";
296 algorithm = "<unknown>";
299 ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
300 fields, mp->basis, algorithm, mp->max_link + 1,
302 mf_format_subfield(&mp->dst, s);