2 * Copyright (c) 2010, 2011, 2012 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"
25 #include "meta-flow.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 /* multipath_check(). */
39 multipath_check(const struct nx_action_multipath *mp, const struct flow *flow)
41 uint32_t n_links = ntohs(mp->max_link) + 1;
42 size_t min_n_bits = log_2_ceil(n_links);
43 struct mf_subfield dst;
46 nxm_decode(&dst, mp->dst, mp->ofs_nbits);
47 error = mf_check_dst(&dst, flow);
52 if (!flow_hash_fields_valid(ntohs(mp->fields))) {
53 VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, ntohs(mp->fields));
54 } else if (mp->algorithm != htons(NX_MP_ALG_MODULO_N)
55 && mp->algorithm != htons(NX_MP_ALG_HASH_THRESHOLD)
56 && mp->algorithm != htons(NX_MP_ALG_HRW)
57 && mp->algorithm != htons(NX_MP_ALG_ITER_HASH)) {
58 VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16,
59 ntohs(mp->algorithm));
60 } else if (dst.n_bits < min_n_bits) {
61 VLOG_WARN_RL(&rl, "multipath action requires at least %zu bits for "
62 "%"PRIu32" links", min_n_bits, n_links);
67 return OFPERR_OFPBAC_BAD_ARGUMENT;
70 /* multipath_execute(). */
72 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
73 unsigned int n_links, unsigned int arg);
76 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
78 /* Calculate value to store. */
79 uint32_t hash = flow_hash_fields(flow, ntohs(mp->fields),
81 uint16_t link = multipath_algorithm(hash, ntohs(mp->algorithm),
82 ntohs(mp->max_link) + 1,
84 struct mf_subfield dst;
86 nxm_decode(&dst, mp->dst, mp->ofs_nbits);
87 mf_set_subfield_value(&dst, link, flow);
91 algorithm_hrw(uint32_t hash, unsigned int n_links)
98 best_weight = hash_2words(hash, 0);
99 for (link = 1; link < n_links; link++) {
100 uint32_t weight = hash_2words(hash, link);
101 if (weight > best_weight) {
103 best_weight = weight;
109 /* Works for 'x' in the range [1,65536], which is all we need. */
111 round_up_pow2(unsigned int x)
122 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
127 if (modulo < n_links || modulo / 2 > n_links) {
128 modulo = round_up_pow2(n_links);
133 link = hash_2words(hash, i++) % modulo;
134 } while (link >= n_links);
140 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
141 unsigned int n_links, unsigned int arg)
144 case NX_MP_ALG_MODULO_N:
145 return hash % n_links;
147 case NX_MP_ALG_HASH_THRESHOLD:
151 return hash / (UINT32_MAX / n_links + 1);
154 return (n_links <= 64
155 ? algorithm_hrw(hash, n_links)
156 : algorithm_iter_hash(hash, n_links, 0));
158 case NX_MP_ALG_ITER_HASH:
159 return algorithm_iter_hash(hash, n_links, arg);
165 /* multipath_parse(). */
168 multipath_parse(struct nx_action_multipath *mp, const char *s_)
170 char *s = xstrdup(s_);
171 char *save_ptr = NULL;
172 char *fields, *basis, *algorithm, *n_links_str, *arg, *dst_s;
173 struct mf_subfield dst;
176 fields = strtok_r(s, ", ", &save_ptr);
177 basis = strtok_r(NULL, ", ", &save_ptr);
178 algorithm = strtok_r(NULL, ", ", &save_ptr);
179 n_links_str = strtok_r(NULL, ", ", &save_ptr);
180 arg = strtok_r(NULL, ", ", &save_ptr);
181 dst_s = strtok_r(NULL, ", ", &save_ptr);
183 ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
186 ofputil_init_NXAST_MULTIPATH(mp);
187 if (!strcasecmp(fields, "eth_src")) {
188 mp->fields = htons(NX_HASH_FIELDS_ETH_SRC);
189 } else if (!strcasecmp(fields, "symmetric_l4")) {
190 mp->fields = htons(NX_HASH_FIELDS_SYMMETRIC_L4);
192 ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
194 mp->basis = htons(atoi(basis));
195 if (!strcasecmp(algorithm, "modulo_n")) {
196 mp->algorithm = htons(NX_MP_ALG_MODULO_N);
197 } else if (!strcasecmp(algorithm, "hash_threshold")) {
198 mp->algorithm = htons(NX_MP_ALG_HASH_THRESHOLD);
199 } else if (!strcasecmp(algorithm, "hrw")) {
200 mp->algorithm = htons(NX_MP_ALG_HRW);
201 } else if (!strcasecmp(algorithm, "iter_hash")) {
202 mp->algorithm = htons(NX_MP_ALG_ITER_HASH);
204 ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
206 n_links = atoi(n_links_str);
207 if (n_links < 1 || n_links > 65536) {
208 ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
211 mp->max_link = htons(n_links - 1);
212 mp->arg = htonl(atoi(arg));
214 mf_parse_subfield(&dst, dst_s);
215 if (dst.n_bits < 16 && n_links > (1u << dst.n_bits)) {
216 ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
217 "less than specified n_links %d",
218 s_, dst.n_bits, 1u << dst.n_bits, n_links);
220 mp->ofs_nbits = nxm_encode_ofs_nbits(dst.ofs, dst.n_bits);
221 mp->dst = htonl(dst.field->nxm_header);
227 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
229 const char *fields, *algorithm;
231 uint16_t mp_fields = ntohs(mp->fields);
232 uint16_t mp_algorithm = ntohs(mp->algorithm);
234 struct mf_subfield dst;
236 fields = flow_hash_fields_to_str(mp_fields);
238 switch ((enum nx_mp_algorithm) mp_algorithm) {
239 case NX_MP_ALG_MODULO_N:
240 algorithm = "modulo_n";
242 case NX_MP_ALG_HASH_THRESHOLD:
243 algorithm = "hash_threshold";
248 case NX_MP_ALG_ITER_HASH:
249 algorithm = "iter_hash";
252 algorithm = "<unknown>";
255 ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
256 fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
258 nxm_decode(&dst, mp->dst, mp->ofs_nbits);
259 mf_format_subfield(&dst, s);