2 * Copyright (c) 2010 Nicira Networks.
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"
21 #include <sys/types.h>
22 #include <netinet/in.h>
23 #include "dynamic-string.h"
26 #include "openflow/nicira-ext.h"
30 VLOG_DEFINE_THIS_MODULE(multipath);
32 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
34 /* multipath_check(). */
36 multipath_check(const struct nx_action_multipath *mp)
38 uint32_t dst = ntohl(mp->dst);
39 int ofs = nxm_decode_ofs(mp->ofs_nbits);
40 int n_bits = nxm_decode_n_bits(mp->ofs_nbits);
42 if (mp->fields != htons(NX_MP_FIELDS_ETH_SRC)
43 && mp->fields != htons(NX_MP_FIELDS_SYMMETRIC_L4)) {
44 VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, ntohs(mp->fields));
45 } else if (mp->algorithm != htons(NX_MP_ALG_MODULO_N)
46 && mp->algorithm != htons(NX_MP_ALG_HASH_THRESHOLD)
47 && mp->algorithm != htons(NX_MP_ALG_HRW)
48 && mp->algorithm != htons(NX_MP_ALG_ITER_HASH)) {
49 VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16,
50 ntohs(mp->algorithm));
51 } else if (!NXM_IS_NX_REG(dst) || NXM_NX_REG_IDX(dst) >= FLOW_N_REGS) {
52 VLOG_WARN_RL(&rl, "unsupported destination field %#"PRIx32, dst);
53 } else if (ofs + n_bits > nxm_field_bits(dst)) {
54 VLOG_WARN_RL(&rl, "destination overflows output field");
55 } else if (n_bits < 16 && ntohs(mp->max_link) > (1u << n_bits)) {
56 VLOG_WARN_RL(&rl, "max_link overflows output field");
61 return ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT);
64 /* multipath_execute(). */
66 static uint32_t multipath_hash(const struct flow *, enum nx_mp_fields,
68 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
69 unsigned int n_links, unsigned int arg);
72 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
74 /* Calculate value to store. */
75 uint32_t hash = multipath_hash(flow, ntohs(mp->fields), ntohs(mp->basis));
76 uint16_t link = multipath_algorithm(hash, ntohs(mp->algorithm),
77 ntohs(mp->max_link) + 1,
81 uint32_t *reg = &flow->regs[NXM_NX_REG_IDX(ntohl(mp->dst))];
82 int ofs = nxm_decode_ofs(mp->ofs_nbits);
83 int n_bits = nxm_decode_n_bits(mp->ofs_nbits);
84 uint32_t mask = n_bits == 32 ? UINT32_MAX : (UINT32_C(1) << n_bits) - 1;
85 *reg = (*reg & ~(mask << ofs)) | (link << ofs);
89 hash_symmetric_l4(const struct flow *flow, uint16_t basis)
96 uint8_t eth_addr[ETH_ADDR_LEN];
102 memset(&fields, 0, sizeof fields);
103 for (i = 0; i < ETH_ADDR_LEN; i++) {
104 fields.eth_addr[i] = flow->dl_src[i] ^ flow->dl_dst[i];
106 fields.vlan_tci = flow->vlan_tci & htons(VLAN_VID_MASK);
107 fields.eth_type = flow->dl_type;
108 if (fields.eth_type == htons(ETH_TYPE_IP)) {
109 fields.ip_addr = flow->nw_src ^ flow->nw_dst;
110 fields.ip_proto = flow->nw_proto;
111 if (fields.ip_proto == IP_TYPE_TCP || fields.ip_proto == IP_TYPE_UDP) {
112 fields.tp_addr = flow->tp_src ^ flow->tp_dst;
114 fields.tp_addr = htons(0);
117 fields.ip_addr = htonl(0);
119 fields.tp_addr = htons(0);
121 return hash_bytes(&fields, sizeof fields, basis);
125 multipath_hash(const struct flow *flow, enum nx_mp_fields fields,
129 case NX_MP_FIELDS_ETH_SRC:
130 return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
132 case NX_MP_FIELDS_SYMMETRIC_L4:
133 return hash_symmetric_l4(flow, basis);
140 algorithm_hrw(uint32_t hash, unsigned int n_links)
142 uint32_t best_weight;
147 best_weight = hash_2words(hash, 0);
148 for (link = 1; link < n_links; link++) {
149 uint32_t weight = hash_2words(hash, link);
150 if (weight > best_weight) {
152 best_weight = weight;
158 /* Works for 'x' in the range [1,65536], which is all we need. */
160 round_up_pow2(unsigned int x)
171 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
176 if (modulo < n_links || modulo / 2 > n_links) {
177 modulo = round_up_pow2(n_links);
182 link = hash_2words(hash, i++) % modulo;
183 } while (link >= n_links);
189 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
190 unsigned int n_links, unsigned int arg)
193 case NX_MP_ALG_MODULO_N:
194 return hash % n_links;
196 case NX_MP_ALG_HASH_THRESHOLD:
197 return hash / (UINT32_MAX / n_links);
200 return (n_links <= 64
201 ? algorithm_hrw(hash, n_links)
202 : algorithm_iter_hash(hash, n_links, 0));
204 case NX_MP_ALG_ITER_HASH:
205 return algorithm_iter_hash(hash, n_links, arg);
211 /* multipath_parse(). */
214 multipath_parse(struct nx_action_multipath *mp, const char *s_)
216 char *s = xstrdup(s_);
217 char *save_ptr = NULL;
218 char *fields, *basis, *algorithm, *n_links, *arg, *dst;
222 fields = strtok_r(s, ", ", &save_ptr);
223 basis = strtok_r(NULL, ", ", &save_ptr);
224 algorithm = strtok_r(NULL, ", ", &save_ptr);
225 n_links = strtok_r(NULL, ", ", &save_ptr);
226 arg = strtok_r(NULL, ", ", &save_ptr);
227 dst = strtok_r(NULL, ", ", &save_ptr);
229 ovs_fatal(0, "%s: not enough arguments to multipath action", s);
232 memset(mp, 0, sizeof *mp);
233 mp->type = htons(OFPAT_VENDOR);
234 mp->len = htons(sizeof *mp);
235 mp->vendor = htonl(NX_VENDOR_ID);
236 mp->subtype = htons(NXAST_MULTIPATH);
237 if (!strcasecmp(fields, "eth_src")) {
238 mp->fields = htons(NX_MP_FIELDS_ETH_SRC);
239 } else if (!strcasecmp(fields, "symmetric_l4")) {
240 mp->fields = htons(NX_MP_FIELDS_SYMMETRIC_L4);
242 ovs_fatal(0, "%s: unknown fields `%s'", s, fields);
244 mp->basis = htons(atoi(basis));
245 if (!strcasecmp(algorithm, "modulo_n")) {
246 mp->algorithm = htons(NX_MP_ALG_MODULO_N);
247 } else if (!strcasecmp(algorithm, "hash_threshold")) {
248 mp->algorithm = htons(NX_MP_ALG_HASH_THRESHOLD);
249 } else if (!strcasecmp(algorithm, "hrw")) {
250 mp->algorithm = htons(NX_MP_ALG_HRW);
251 } else if (!strcasecmp(algorithm, "iter_hash")) {
252 mp->algorithm = htons(NX_MP_ALG_ITER_HASH);
254 ovs_fatal(0, "%s: unknown algorithm `%s'", s, algorithm);
256 mp->max_link = htons(atoi(n_links) - 1);
257 mp->arg = htonl(atoi(arg));
259 nxm_parse_field_bits(dst, &header, &ofs, &n_bits);
260 mp->ofs_nbits = nxm_encode_ofs_nbits(ofs, n_bits);
261 mp->dst = htonl(header);
267 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
269 const char *fields, *algorithm;
271 switch ((enum nx_mp_fields) ntohs(mp->fields)) {
272 case NX_MP_FIELDS_ETH_SRC:
275 case NX_MP_FIELDS_SYMMETRIC_L4:
276 fields = "symmetric_l4";
279 fields = "<unknown>";
282 switch ((enum nx_mp_algorithm) ntohs(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, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
302 nxm_format_field_bits(s, ntohl(mp->dst), nxm_decode_ofs(mp->ofs_nbits),
303 nxm_decode_n_bits(mp->ofs_nbits));