ofproto: Factor building of flow_removed messages out into ofp-util.
[sliver-openvswitch.git] / lib / multipath.c
1 /*
2  * Copyright (c) 2010, 2011 Nicira Networks.
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-util.h"
27 #include "openflow/nicira-ext.h"
28 #include "packets.h"
29 #include "vlog.h"
30
31 VLOG_DEFINE_THIS_MODULE(multipath);
32
33 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
34 \f
35 /* multipath_check(). */
36 int
37 multipath_check(const struct nx_action_multipath *mp)
38 {
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);
42
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");
58     } else {
59         return 0;
60     }
61
62     return ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT);
63 }
64 \f
65 /* multipath_execute(). */
66
67 static uint32_t multipath_hash(const struct flow *, enum nx_mp_fields,
68                                uint16_t basis);
69 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
70                                     unsigned int n_links, unsigned int arg);
71
72 void
73 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
74 {
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,
79                                         ntohl(mp->arg));
80
81     /* Store it. */
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);
87 }
88
89 static uint32_t
90 multipath_hash(const struct flow *flow, enum nx_mp_fields fields,
91                uint16_t basis)
92 {
93     switch (fields) {
94     case NX_MP_FIELDS_ETH_SRC:
95         return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
96
97     case NX_MP_FIELDS_SYMMETRIC_L4:
98         return flow_hash_symmetric_l4(flow, basis);
99     }
100
101     NOT_REACHED();
102 }
103
104 static uint16_t
105 algorithm_hrw(uint32_t hash, unsigned int n_links)
106 {
107     uint32_t best_weight;
108     uint16_t best_link;
109     unsigned int link;
110
111     best_link = 0;
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) {
116             best_link = link;
117             best_weight = weight;
118         }
119     }
120     return best_link;
121 }
122
123 /* Works for 'x' in the range [1,65536], which is all we need.  */
124 static unsigned int
125 round_up_pow2(unsigned int x)
126 {
127     x--;
128     x |= x >> 1;
129     x |= x >> 2;
130     x |= x >> 4;
131     x |= x >> 8;
132     return x + 1;
133 }
134
135 static uint16_t
136 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
137 {
138     uint16_t link;
139     int i;
140
141     if (modulo < n_links || modulo / 2 > n_links) {
142         modulo = round_up_pow2(n_links);
143     }
144
145     i = 0;
146     do {
147         link = hash_2words(hash, i++) % modulo;
148     } while (link >= n_links);
149
150     return link;
151 }
152
153 static uint16_t
154 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
155                     unsigned int n_links, unsigned int arg)
156 {
157     switch (algorithm) {
158     case NX_MP_ALG_MODULO_N:
159         return hash % n_links;
160
161     case NX_MP_ALG_HASH_THRESHOLD:
162         if (n_links == 1) {
163             return 0;
164         }
165         return hash / (UINT32_MAX / n_links + 1);
166
167     case NX_MP_ALG_HRW:
168         return (n_links <= 64
169                 ? algorithm_hrw(hash, n_links)
170                 : algorithm_iter_hash(hash, n_links, 0));
171
172     case NX_MP_ALG_ITER_HASH:
173         return algorithm_iter_hash(hash, n_links, arg);
174     }
175
176     NOT_REACHED();
177 }
178 \f
179 /* multipath_parse(). */
180
181 void
182 multipath_parse(struct nx_action_multipath *mp, const char *s_)
183 {
184     char *s = xstrdup(s_);
185     char *save_ptr = NULL;
186     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
187     uint32_t header;
188     int ofs, n_bits;
189     int n_links;
190
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);
197     if (!dst) {
198         ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
199     }
200
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);
210     } else {
211         ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
212     }
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);
222     } else {
223         ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
224     }
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",
228                   s_, n_links);
229     }
230     mp->max_link = htons(n_links - 1);
231     mp->arg = htonl(atoi(arg));
232
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_);
236     }
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);
241     }
242     mp->ofs_nbits = nxm_encode_ofs_nbits(ofs, n_bits);
243     mp->dst = htonl(header);
244
245     free(s);
246 }
247
248 void
249 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
250 {
251     const char *fields, *algorithm;
252
253     uint16_t mp_fields    = ntohs(mp->fields);
254     uint16_t mp_algorithm = ntohs(mp->algorithm);
255
256     switch ((enum nx_mp_fields) mp_fields) {
257     case NX_MP_FIELDS_ETH_SRC:
258         fields = "eth_src";
259         break;
260     case NX_MP_FIELDS_SYMMETRIC_L4:
261         fields = "symmetric_l4";
262         break;
263     default:
264         fields = "<unknown>";
265     }
266
267     switch ((enum nx_mp_algorithm) mp_algorithm) {
268     case NX_MP_ALG_MODULO_N:
269         algorithm = "modulo_n";
270         break;
271     case NX_MP_ALG_HASH_THRESHOLD:
272         algorithm = "hash_threshold";
273         break;
274     case NX_MP_ALG_HRW:
275         algorithm = "hrw";
276         break;
277     case NX_MP_ALG_ITER_HASH:
278         algorithm = "iter_hash";
279         break;
280     default:
281         algorithm = "<unknown>";
282     }
283
284     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
285                   fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
286                   ntohl(mp->arg));
287     nxm_format_field_bits(s, ntohl(mp->dst), nxm_decode_ofs(mp->ofs_nbits),
288                           nxm_decode_n_bits(mp->ofs_nbits));
289     ds_put_char(s, ')');
290 }