2 * Copyright (c) 2010, 2011, 2012, 2013, 2014 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"
32 /* Checks that 'mp' is valid on flow. Returns 0 if it is valid, otherwise an
35 multipath_check(const struct ofpact_multipath *mp,
36 const struct flow *flow)
38 return mf_check_dst(&mp->dst, flow);
41 /* multipath_execute(). */
43 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
44 unsigned int n_links, unsigned int arg);
46 /* Executes 'mp' based on the current contents of 'flow', writing the results
47 * back into 'flow'. Sets fields in 'wc' that were used to calculate
50 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
51 struct flow_wildcards *wc)
53 /* Calculate value to store. */
54 uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
55 uint16_t link = multipath_algorithm(hash, mp->algorithm,
56 mp->max_link + 1, mp->arg);
58 flow_mask_hash_fields(flow, wc, mp->fields);
59 nxm_reg_load(&mp->dst, link, flow, wc);
63 algorithm_hrw(uint32_t hash, unsigned int n_links)
70 best_weight = hash_2words(hash, 0);
71 for (link = 1; link < n_links; link++) {
72 uint32_t weight = hash_2words(hash, link);
73 if (weight > best_weight) {
81 /* Works for 'x' in the range [1,65536], which is all we need. */
83 round_up_pow2(unsigned int x)
94 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
99 if (modulo < n_links || modulo / 2 > n_links) {
100 modulo = round_up_pow2(n_links);
105 link = hash_2words(hash, i++) % modulo;
106 } while (link >= n_links);
112 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
113 unsigned int n_links, unsigned int arg)
116 case NX_MP_ALG_MODULO_N:
117 return hash % n_links;
119 case NX_MP_ALG_HASH_THRESHOLD:
123 return hash / (UINT32_MAX / n_links + 1);
126 return (n_links <= 64
127 ? algorithm_hrw(hash, n_links)
128 : algorithm_iter_hash(hash, n_links, 0));
130 case NX_MP_ALG_ITER_HASH:
131 return algorithm_iter_hash(hash, n_links, arg);
137 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
138 * 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
140 * Returns NULL if successful, otherwise a malloc()'d string describing the
141 * error. The caller is responsible for freeing the returned string.*/
142 static char * OVS_WARN_UNUSED_RESULT
143 multipath_parse__(struct ofpact_multipath *mp, const char *s_, char *s)
145 char *save_ptr = NULL;
146 char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
150 fields = strtok_r(s, ", ", &save_ptr);
151 basis = strtok_r(NULL, ", ", &save_ptr);
152 algorithm = strtok_r(NULL, ", ", &save_ptr);
153 n_links_str = strtok_r(NULL, ", ", &save_ptr);
154 arg = strtok_r(NULL, ", ", &save_ptr);
155 dst = strtok_r(NULL, ", ", &save_ptr);
157 return xasprintf("%s: not enough arguments to multipath action", s_);
160 ofpact_init_MULTIPATH(mp);
161 if (!strcasecmp(fields, "eth_src")) {
162 mp->fields = NX_HASH_FIELDS_ETH_SRC;
163 } else if (!strcasecmp(fields, "symmetric_l4")) {
164 mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
166 return xasprintf("%s: unknown fields `%s'", s_, fields);
168 mp->basis = atoi(basis);
169 if (!strcasecmp(algorithm, "modulo_n")) {
170 mp->algorithm = NX_MP_ALG_MODULO_N;
171 } else if (!strcasecmp(algorithm, "hash_threshold")) {
172 mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
173 } else if (!strcasecmp(algorithm, "hrw")) {
174 mp->algorithm = NX_MP_ALG_HRW;
175 } else if (!strcasecmp(algorithm, "iter_hash")) {
176 mp->algorithm = NX_MP_ALG_ITER_HASH;
178 return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
180 n_links = atoi(n_links_str);
181 if (n_links < 1 || n_links > 65536) {
182 return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
185 mp->max_link = n_links - 1;
188 error = mf_parse_subfield(&mp->dst, dst);
192 if (!mf_nxm_header(mp->dst.field->id)) {
193 return xasprintf("%s: experimenter OXM field '%s' not supported",
196 if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
197 return xasprintf("%s: %d-bit destination field has %u possible "
198 "values, less than specified n_links %d",
199 s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
205 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
206 * 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
208 * Returns NULL if successful, otherwise a malloc()'d string describing the
209 * error. The caller is responsible for freeing the returned string. */
210 char * OVS_WARN_UNUSED_RESULT
211 multipath_parse(struct ofpact_multipath *mp, const char *s_)
213 char *s = xstrdup(s_);
214 char *error = multipath_parse__(mp, s_, s);
219 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
222 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
224 const char *fields, *algorithm;
226 fields = flow_hash_fields_to_str(mp->fields);
228 switch (mp->algorithm) {
229 case NX_MP_ALG_MODULO_N:
230 algorithm = "modulo_n";
232 case NX_MP_ALG_HASH_THRESHOLD:
233 algorithm = "hash_threshold";
238 case NX_MP_ALG_ITER_HASH:
239 algorithm = "iter_hash";
242 algorithm = "<unknown>";
245 ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
246 fields, mp->basis, algorithm, mp->max_link + 1,
248 mf_format_subfield(&mp->dst, s);