Revert DSCP update changes.
[openvswitch] / lib / multipath.c
1 /*
2  * Copyright (c) 2010, 2011, 2012 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 "meta-flow.h"
26 #include "nx-match.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 /* multipath_check(). */
38 enum ofperr
39 multipath_check(const struct nx_action_multipath *mp, const struct flow *flow)
40 {
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;
44     enum ofperr error;
45
46     nxm_decode(&dst, mp->dst, mp->ofs_nbits);
47     error = mf_check_dst(&dst, flow);
48     if (error) {
49         return error;
50     }
51
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);
63     } else {
64         return 0;
65     }
66
67     return OFPERR_OFPBAC_BAD_ARGUMENT;
68 }
69 \f
70 /* multipath_execute(). */
71
72 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
73                                     unsigned int n_links, unsigned int arg);
74
75 void
76 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
77 {
78     /* Calculate value to store. */
79     uint32_t hash = flow_hash_fields(flow, ntohs(mp->fields),
80                                      ntohs(mp->basis));
81     uint16_t link = multipath_algorithm(hash, ntohs(mp->algorithm),
82                                         ntohs(mp->max_link) + 1,
83                                         ntohl(mp->arg));
84     struct mf_subfield dst;
85
86     nxm_decode(&dst, mp->dst, mp->ofs_nbits);
87     mf_set_subfield_value(&dst, link, flow);
88 }
89
90 static uint16_t
91 algorithm_hrw(uint32_t hash, unsigned int n_links)
92 {
93     uint32_t best_weight;
94     uint16_t best_link;
95     unsigned int link;
96
97     best_link = 0;
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) {
102             best_link = link;
103             best_weight = weight;
104         }
105     }
106     return best_link;
107 }
108
109 /* Works for 'x' in the range [1,65536], which is all we need.  */
110 static unsigned int
111 round_up_pow2(unsigned int x)
112 {
113     x--;
114     x |= x >> 1;
115     x |= x >> 2;
116     x |= x >> 4;
117     x |= x >> 8;
118     return x + 1;
119 }
120
121 static uint16_t
122 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
123 {
124     uint16_t link;
125     int i;
126
127     if (modulo < n_links || modulo / 2 > n_links) {
128         modulo = round_up_pow2(n_links);
129     }
130
131     i = 0;
132     do {
133         link = hash_2words(hash, i++) % modulo;
134     } while (link >= n_links);
135
136     return link;
137 }
138
139 static uint16_t
140 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
141                     unsigned int n_links, unsigned int arg)
142 {
143     switch (algorithm) {
144     case NX_MP_ALG_MODULO_N:
145         return hash % n_links;
146
147     case NX_MP_ALG_HASH_THRESHOLD:
148         if (n_links == 1) {
149             return 0;
150         }
151         return hash / (UINT32_MAX / n_links + 1);
152
153     case NX_MP_ALG_HRW:
154         return (n_links <= 64
155                 ? algorithm_hrw(hash, n_links)
156                 : algorithm_iter_hash(hash, n_links, 0));
157
158     case NX_MP_ALG_ITER_HASH:
159         return algorithm_iter_hash(hash, n_links, arg);
160     }
161
162     NOT_REACHED();
163 }
164 \f
165 /* multipath_parse(). */
166
167 void
168 multipath_parse(struct nx_action_multipath *mp, const char *s_)
169 {
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;
174     int n_links;
175
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);
182     if (!dst_s) {
183         ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
184     }
185
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);
191     } else {
192         ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
193     }
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);
203     } else {
204         ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
205     }
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",
209                   s_, n_links);
210     }
211     mp->max_link = htons(n_links - 1);
212     mp->arg = htonl(atoi(arg));
213
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);
219     }
220     mp->ofs_nbits = nxm_encode_ofs_nbits(dst.ofs, dst.n_bits);
221     mp->dst = htonl(dst.field->nxm_header);
222
223     free(s);
224 }
225
226 void
227 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
228 {
229     const char *fields, *algorithm;
230
231     uint16_t mp_fields    = ntohs(mp->fields);
232     uint16_t mp_algorithm = ntohs(mp->algorithm);
233
234     struct mf_subfield dst;
235
236     fields = flow_hash_fields_to_str(mp_fields);
237
238     switch ((enum nx_mp_algorithm) mp_algorithm) {
239     case NX_MP_ALG_MODULO_N:
240         algorithm = "modulo_n";
241         break;
242     case NX_MP_ALG_HASH_THRESHOLD:
243         algorithm = "hash_threshold";
244         break;
245     case NX_MP_ALG_HRW:
246         algorithm = "hrw";
247         break;
248     case NX_MP_ALG_ITER_HASH:
249         algorithm = "iter_hash";
250         break;
251     default:
252         algorithm = "<unknown>";
253     }
254
255     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
256                   fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
257                   ntohl(mp->arg));
258     nxm_decode(&dst, mp->dst, mp->ofs_nbits);
259     mf_format_subfield(&dst, s);
260     ds_put_char(s, ')');
261 }