2 * Copyright (c) 2010, 2011 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"
20 #include <arpa/inet.h>
22 #include <sys/types.h>
23 #include <netinet/in.h>
24 #include "dynamic-string.h"
27 #include "openflow/nicira-ext.h"
31 VLOG_DEFINE_THIS_MODULE(multipath
);
33 static struct vlog_rate_limit rl
= VLOG_RATE_LIMIT_INIT(1, 5);
35 /* multipath_check(). */
37 multipath_check(const struct nx_action_multipath
*mp
)
39 uint32_t dst
= ntohl(mp
->dst
);
40 int ofs
= nxm_decode_ofs(mp
->ofs_nbits
);
41 int n_bits
= nxm_decode_n_bits(mp
->ofs_nbits
);
43 if (mp
->fields
!= htons(NX_MP_FIELDS_ETH_SRC
)
44 && mp
->fields
!= htons(NX_MP_FIELDS_SYMMETRIC_L4
)) {
45 VLOG_WARN_RL(&rl
, "unsupported fields %"PRIu16
, ntohs(mp
->fields
));
46 } else if (mp
->algorithm
!= htons(NX_MP_ALG_MODULO_N
)
47 && mp
->algorithm
!= htons(NX_MP_ALG_HASH_THRESHOLD
)
48 && mp
->algorithm
!= htons(NX_MP_ALG_HRW
)
49 && mp
->algorithm
!= htons(NX_MP_ALG_ITER_HASH
)) {
50 VLOG_WARN_RL(&rl
, "unsupported algorithm %"PRIu16
,
51 ntohs(mp
->algorithm
));
52 } else if (!NXM_IS_NX_REG(dst
) || NXM_NX_REG_IDX(dst
) >= FLOW_N_REGS
) {
53 VLOG_WARN_RL(&rl
, "unsupported destination field %#"PRIx32
, dst
);
54 } else if (ofs
+ n_bits
> nxm_field_bits(dst
)) {
55 VLOG_WARN_RL(&rl
, "destination overflows output field");
56 } else if (n_bits
< 16 && ntohs(mp
->max_link
) > (1u << n_bits
)) {
57 VLOG_WARN_RL(&rl
, "max_link overflows output field");
62 return ofp_mkerr(OFPET_BAD_ACTION
, OFPBAC_BAD_ARGUMENT
);
65 /* multipath_execute(). */
67 static uint32_t multipath_hash(const struct flow
*, enum nx_mp_fields
,
69 static uint16_t multipath_algorithm(uint32_t hash
, enum nx_mp_algorithm
,
70 unsigned int n_links
, unsigned int arg
);
73 multipath_execute(const struct nx_action_multipath
*mp
, struct flow
*flow
)
75 /* Calculate value to store. */
76 uint32_t hash
= multipath_hash(flow
, ntohs(mp
->fields
), ntohs(mp
->basis
));
77 uint16_t link
= multipath_algorithm(hash
, ntohs(mp
->algorithm
),
78 ntohs(mp
->max_link
) + 1,
82 uint32_t *reg
= &flow
->regs
[NXM_NX_REG_IDX(ntohl(mp
->dst
))];
83 int ofs
= nxm_decode_ofs(mp
->ofs_nbits
);
84 int n_bits
= nxm_decode_n_bits(mp
->ofs_nbits
);
85 uint32_t mask
= n_bits
== 32 ? UINT32_MAX
: (UINT32_C(1) << n_bits
) - 1;
86 *reg
= (*reg
& ~(mask
<< ofs
)) | (link
<< ofs
);
90 multipath_hash(const struct flow
*flow
, enum nx_mp_fields fields
,
94 case NX_MP_FIELDS_ETH_SRC
:
95 return hash_bytes(flow
->dl_src
, sizeof flow
->dl_src
, basis
);
97 case NX_MP_FIELDS_SYMMETRIC_L4
:
98 return flow_hash_symmetric_l4(flow
, basis
);
105 algorithm_hrw(uint32_t hash
, unsigned int n_links
)
107 uint32_t best_weight
;
112 best_weight
= hash_2words(hash
, 0);
113 for (link
= 1; link
< n_links
; link
++) {
114 uint32_t weight
= hash_2words(hash
, link
);
115 if (weight
> best_weight
) {
117 best_weight
= weight
;
123 /* Works for 'x' in the range [1,65536], which is all we need. */
125 round_up_pow2(unsigned int x
)
136 algorithm_iter_hash(uint32_t hash
, unsigned int n_links
, unsigned int modulo
)
141 if (modulo
< n_links
|| modulo
/ 2 > n_links
) {
142 modulo
= round_up_pow2(n_links
);
147 link
= hash_2words(hash
, i
++) % modulo
;
148 } while (link
>= n_links
);
154 multipath_algorithm(uint32_t hash
, enum nx_mp_algorithm algorithm
,
155 unsigned int n_links
, unsigned int arg
)
158 case NX_MP_ALG_MODULO_N
:
159 return hash
% n_links
;
161 case NX_MP_ALG_HASH_THRESHOLD
:
165 return hash
/ (UINT32_MAX
/ n_links
+ 1);
168 return (n_links
<= 64
169 ? algorithm_hrw(hash
, n_links
)
170 : algorithm_iter_hash(hash
, n_links
, 0));
172 case NX_MP_ALG_ITER_HASH
:
173 return algorithm_iter_hash(hash
, n_links
, arg
);
179 /* multipath_parse(). */
182 multipath_parse(struct nx_action_multipath
*mp
, const char *s_
)
184 char *s
= xstrdup(s_
);
185 char *save_ptr
= NULL
;
186 char *fields
, *basis
, *algorithm
, *n_links_str
, *arg
, *dst
;
191 fields
= strtok_r(s
, ", ", &save_ptr
);
192 basis
= strtok_r(NULL
, ", ", &save_ptr
);
193 algorithm
= strtok_r(NULL
, ", ", &save_ptr
);
194 n_links_str
= strtok_r(NULL
, ", ", &save_ptr
);
195 arg
= strtok_r(NULL
, ", ", &save_ptr
);
196 dst
= strtok_r(NULL
, ", ", &save_ptr
);
198 ovs_fatal(0, "%s: not enough arguments to multipath action", s_
);
201 memset(mp
, 0, sizeof *mp
);
202 mp
->type
= htons(OFPAT_VENDOR
);
203 mp
->len
= htons(sizeof *mp
);
204 mp
->vendor
= htonl(NX_VENDOR_ID
);
205 mp
->subtype
= htons(NXAST_MULTIPATH
);
206 if (!strcasecmp(fields
, "eth_src")) {
207 mp
->fields
= htons(NX_MP_FIELDS_ETH_SRC
);
208 } else if (!strcasecmp(fields
, "symmetric_l4")) {
209 mp
->fields
= htons(NX_MP_FIELDS_SYMMETRIC_L4
);
211 ovs_fatal(0, "%s: unknown fields `%s'", s_
, fields
);
213 mp
->basis
= htons(atoi(basis
));
214 if (!strcasecmp(algorithm
, "modulo_n")) {
215 mp
->algorithm
= htons(NX_MP_ALG_MODULO_N
);
216 } else if (!strcasecmp(algorithm
, "hash_threshold")) {
217 mp
->algorithm
= htons(NX_MP_ALG_HASH_THRESHOLD
);
218 } else if (!strcasecmp(algorithm
, "hrw")) {
219 mp
->algorithm
= htons(NX_MP_ALG_HRW
);
220 } else if (!strcasecmp(algorithm
, "iter_hash")) {
221 mp
->algorithm
= htons(NX_MP_ALG_ITER_HASH
);
223 ovs_fatal(0, "%s: unknown algorithm `%s'", s_
, algorithm
);
225 n_links
= atoi(n_links_str
);
226 if (n_links
< 1 || n_links
> 65536) {
227 ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
230 mp
->max_link
= htons(n_links
- 1);
231 mp
->arg
= htonl(atoi(arg
));
233 nxm_parse_field_bits(dst
, &header
, &ofs
, &n_bits
);
234 if (!NXM_IS_NX_REG(header
) || NXM_NX_REG_IDX(header
) >= FLOW_N_REGS
) {
235 ovs_fatal(0, "%s: destination field must be register", s_
);
237 if (n_bits
< 16 && n_links
> (1u << n_bits
)) {
238 ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
239 "less than specified n_links %d",
240 s_
, n_bits
, 1u << n_bits
, n_links
);
242 mp
->ofs_nbits
= nxm_encode_ofs_nbits(ofs
, n_bits
);
243 mp
->dst
= htonl(header
);
249 multipath_format(const struct nx_action_multipath
*mp
, struct ds
*s
)
251 const char *fields
, *algorithm
;
253 uint16_t mp_fields
= ntohs(mp
->fields
);
254 uint16_t mp_algorithm
= ntohs(mp
->algorithm
);
256 switch ((enum nx_mp_fields
) mp_fields
) {
257 case NX_MP_FIELDS_ETH_SRC
:
260 case NX_MP_FIELDS_SYMMETRIC_L4
:
261 fields
= "symmetric_l4";
264 fields
= "<unknown>";
267 switch ((enum nx_mp_algorithm
) mp_algorithm
) {
268 case NX_MP_ALG_MODULO_N
:
269 algorithm
= "modulo_n";
271 case NX_MP_ALG_HASH_THRESHOLD
:
272 algorithm
= "hash_threshold";
277 case NX_MP_ALG_ITER_HASH
:
278 algorithm
= "iter_hash";
281 algorithm
= "<unknown>";
284 ds_put_format(s
, "multipath(%s,%"PRIu16
",%s,%d,%"PRIu16
",",
285 fields
, ntohs(mp
->basis
), algorithm
, ntohs(mp
->max_link
) + 1,
287 nxm_format_field_bits(s
, ntohl(mp
->dst
), nxm_decode_ofs(mp
->ofs_nbits
),
288 nxm_decode_n_bits(mp
->ofs_nbits
));