tests: Add support for automatically running Ryu tests against OVS.
[sliver-openvswitch.git] / lib / multipath.c
1 /*
2  * Copyright (c) 2010, 2011, 2012, 2013 Nicira, Inc.
3  *
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:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <config.h>
18
19 #include "multipath.h"
20 #include <arpa/inet.h>
21 #include <inttypes.h>
22 #include <sys/types.h>
23 #include <netinet/in.h>
24 #include "dynamic-string.h"
25 #include "nx-match.h"
26 #include "ofp-actions.h"
27 #include "ofp-errors.h"
28 #include "ofp-util.h"
29 #include "openflow/nicira-ext.h"
30 #include "packets.h"
31 #include "vlog.h"
32
33 VLOG_DEFINE_THIS_MODULE(multipath);
34
35 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
36 \f
37 /* Converts 'nam' into 'mp'.  Returns 0 if successful, otherwise an
38  * OFPERR_*. */
39 enum ofperr
40 multipath_from_openflow(const struct nx_action_multipath *nam,
41                         struct ofpact_multipath *mp)
42 {
43     uint32_t n_links = ntohs(nam->max_link) + 1;
44     size_t min_n_bits = log_2_ceil(n_links);
45
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);
55
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;
69     }
70
71     return multipath_check(mp, NULL);
72 }
73
74 /* Checks that 'mp' is valid on flow.  Returns 0 if it is valid, otherwise an
75  * OFPERR_*. */
76 enum ofperr
77 multipath_check(const struct ofpact_multipath *mp,
78                 const struct flow *flow)
79 {
80     return mf_check_dst(&mp->dst, flow);
81 }
82
83 /* Converts 'mp' into an OpenFlow NXAST_MULTIPATH action, which it appends to
84  * 'openflow'. */
85 void
86 multipath_to_nxast(const struct ofpact_multipath *mp, struct ofpbuf *openflow)
87 {
88     struct nx_action_multipath *nam = ofputil_put_NXAST_MULTIPATH(openflow);
89
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);
97 }
98 \f
99 /* multipath_execute(). */
100
101 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
102                                     unsigned int n_links, unsigned int arg);
103
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
106  * the result. */
107 void
108 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
109                   struct flow_wildcards *wc)
110 {
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);
115
116     flow_mask_hash_fields(flow, wc, mp->fields);
117     nxm_reg_load(&mp->dst, link, flow, wc);
118 }
119
120 static uint16_t
121 algorithm_hrw(uint32_t hash, unsigned int n_links)
122 {
123     uint32_t best_weight;
124     uint16_t best_link;
125     unsigned int link;
126
127     best_link = 0;
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) {
132             best_link = link;
133             best_weight = weight;
134         }
135     }
136     return best_link;
137 }
138
139 /* Works for 'x' in the range [1,65536], which is all we need.  */
140 static unsigned int
141 round_up_pow2(unsigned int x)
142 {
143     x--;
144     x |= x >> 1;
145     x |= x >> 2;
146     x |= x >> 4;
147     x |= x >> 8;
148     return x + 1;
149 }
150
151 static uint16_t
152 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
153 {
154     uint16_t link;
155     int i;
156
157     if (modulo < n_links || modulo / 2 > n_links) {
158         modulo = round_up_pow2(n_links);
159     }
160
161     i = 0;
162     do {
163         link = hash_2words(hash, i++) % modulo;
164     } while (link >= n_links);
165
166     return link;
167 }
168
169 static uint16_t
170 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
171                     unsigned int n_links, unsigned int arg)
172 {
173     switch (algorithm) {
174     case NX_MP_ALG_MODULO_N:
175         return hash % n_links;
176
177     case NX_MP_ALG_HASH_THRESHOLD:
178         if (n_links == 1) {
179             return 0;
180         }
181         return hash / (UINT32_MAX / n_links + 1);
182
183     case NX_MP_ALG_HRW:
184         return (n_links <= 64
185                 ? algorithm_hrw(hash, n_links)
186                 : algorithm_iter_hash(hash, n_links, 0));
187
188     case NX_MP_ALG_ITER_HASH:
189         return algorithm_iter_hash(hash, n_links, arg);
190     }
191
192     OVS_NOT_REACHED();
193 }
194 \f
195 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
196  * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
197  *
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)
202 {
203     char *save_ptr = NULL;
204     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
205     char *error;
206     int n_links;
207
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);
214     if (!dst) {
215         return xasprintf("%s: not enough arguments to multipath action", s_);
216     }
217
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;
223     } else {
224         return xasprintf("%s: unknown fields `%s'", s_, fields);
225     }
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;
235     } else {
236         return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
237     }
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",
241                          s_, n_links);
242     }
243     mp->max_link = n_links - 1;
244     mp->arg = atoi(arg);
245
246     error = mf_parse_subfield(&mp->dst, dst);
247     if (error) {
248         return error;
249     }
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);
254     }
255
256     return NULL;
257 }
258
259 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
260  * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
261  *
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_)
266 {
267     char *s = xstrdup(s_);
268     char *error = multipath_parse__(mp, s_, s);
269     free(s);
270     return error;
271 }
272
273 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
274  * describes. */
275 void
276 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
277 {
278     const char *fields, *algorithm;
279
280     fields = flow_hash_fields_to_str(mp->fields);
281
282     switch (mp->algorithm) {
283     case NX_MP_ALG_MODULO_N:
284         algorithm = "modulo_n";
285         break;
286     case NX_MP_ALG_HASH_THRESHOLD:
287         algorithm = "hash_threshold";
288         break;
289     case NX_MP_ALG_HRW:
290         algorithm = "hrw";
291         break;
292     case NX_MP_ALG_ITER_HASH:
293         algorithm = "iter_hash";
294         break;
295     default:
296         algorithm = "<unknown>";
297     }
298
299     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
300                   fields, mp->basis, algorithm, mp->max_link + 1,
301                   mp->arg);
302     mf_format_subfield(&mp->dst, s);
303     ds_put_char(s, ')');
304 }