]> git.proxmox.com Git - mirror_ovs.git/blame - lib/multipath.c
ofproto-dpif: Store relevant fields for wildcarding in facet.
[mirror_ovs.git] / lib / multipath.c
CommitLineData
53ddd40a 1/*
e0edde6f 2 * Copyright (c) 2010, 2011, 2012 Nicira, Inc.
53ddd40a
BP
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"
19f62195 20#include <arpa/inet.h>
53ddd40a
BP
21#include <inttypes.h>
22#include <sys/types.h>
23#include <netinet/in.h>
24#include "dynamic-string.h"
25#include "nx-match.h"
f25d0cf3 26#include "ofp-actions.h"
90bf1e07 27#include "ofp-errors.h"
53ddd40a
BP
28#include "ofp-util.h"
29#include "openflow/nicira-ext.h"
30#include "packets.h"
31#include "vlog.h"
32
33VLOG_DEFINE_THIS_MODULE(multipath);
34
35static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
36\f
f25d0cf3
BP
37/* Converts 'nam' into 'mp'. Returns 0 if successful, otherwise an
38 * OFPERR_*. */
90bf1e07 39enum ofperr
f25d0cf3
BP
40multipath_from_openflow(const struct nx_action_multipath *nam,
41 struct ofpact_multipath *mp)
53ddd40a 42{
f25d0cf3 43 uint32_t n_links = ntohs(nam->max_link) + 1;
300c6946 44 size_t min_n_bits = log_2_ceil(n_links);
43edca57 45
f25d0cf3
BP
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) {
ce523f65
EJ
66 VLOG_WARN_RL(&rl, "multipath action requires at least %zu bits for "
67 "%"PRIu32" links", min_n_bits, n_links);
f25d0cf3 68 return OFPERR_OFPBAC_BAD_ARGUMENT;
53ddd40a
BP
69 }
70
f25d0cf3
BP
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_*. */
76enum ofperr
77multipath_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'. */
85void
86multipath_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);
53ddd40a
BP
97}
98\f
99/* multipath_execute(). */
100
53ddd40a
BP
101static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
102 unsigned int n_links, unsigned int arg);
103
f25d0cf3 104/* Executes 'mp' based on the current contents of 'flow', writing the results
bcd2633a
JP
105 * back into 'flow'. Sets fields in 'wc' that were used to calculate
106 * the result. */
53ddd40a 107void
bcd2633a
JP
108multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
109 struct flow_wildcards *wc)
53ddd40a
BP
110{
111 /* Calculate value to store. */
f25d0cf3
BP
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
bcd2633a 116 flow_mask_hash_fields(wc, mp->fields);
f25d0cf3 117 nxm_reg_load(&mp->dst, link, flow);
53ddd40a
BP
118}
119
53ddd40a
BP
120static uint16_t
121algorithm_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. */
140static unsigned int
141round_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
151static uint16_t
152algorithm_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
169static uint16_t
170multipath_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:
d7bf2b00
BP
178 if (n_links == 1) {
179 return 0;
180 }
181 return hash / (UINT32_MAX / n_links + 1);
53ddd40a
BP
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 NOT_REACHED();
193}
194\f
f25d0cf3
BP
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 * Prints an error on stderr and aborts the program if 's_' syntax is
199 * invalid. */
53ddd40a 200void
f25d0cf3 201multipath_parse(struct ofpact_multipath *mp, const char *s_)
53ddd40a
BP
202{
203 char *s = xstrdup(s_);
204 char *save_ptr = NULL;
f25d0cf3 205 char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
770f1f66 206 int n_links;
53ddd40a
BP
207
208 fields = strtok_r(s, ", ", &save_ptr);
209 basis = strtok_r(NULL, ", ", &save_ptr);
210 algorithm = strtok_r(NULL, ", ", &save_ptr);
770f1f66 211 n_links_str = strtok_r(NULL, ", ", &save_ptr);
53ddd40a 212 arg = strtok_r(NULL, ", ", &save_ptr);
f25d0cf3
BP
213 dst = strtok_r(NULL, ", ", &save_ptr);
214 if (!dst) {
770f1f66 215 ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
53ddd40a
BP
216 }
217
f25d0cf3 218 ofpact_init_MULTIPATH(mp);
53ddd40a 219 if (!strcasecmp(fields, "eth_src")) {
f25d0cf3 220 mp->fields = NX_HASH_FIELDS_ETH_SRC;
53ddd40a 221 } else if (!strcasecmp(fields, "symmetric_l4")) {
f25d0cf3 222 mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
53ddd40a 223 } else {
770f1f66 224 ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
53ddd40a 225 }
f25d0cf3 226 mp->basis = atoi(basis);
53ddd40a 227 if (!strcasecmp(algorithm, "modulo_n")) {
f25d0cf3 228 mp->algorithm = NX_MP_ALG_MODULO_N;
53ddd40a 229 } else if (!strcasecmp(algorithm, "hash_threshold")) {
f25d0cf3 230 mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
53ddd40a 231 } else if (!strcasecmp(algorithm, "hrw")) {
f25d0cf3 232 mp->algorithm = NX_MP_ALG_HRW;
53ddd40a 233 } else if (!strcasecmp(algorithm, "iter_hash")) {
f25d0cf3 234 mp->algorithm = NX_MP_ALG_ITER_HASH;
53ddd40a 235 } else {
770f1f66 236 ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
53ddd40a 237 }
770f1f66
BP
238 n_links = atoi(n_links_str);
239 if (n_links < 1 || n_links > 65536) {
240 ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
241 s_, n_links);
242 }
f25d0cf3
BP
243 mp->max_link = n_links - 1;
244 mp->arg = atoi(arg);
53ddd40a 245
f25d0cf3
BP
246 mf_parse_subfield(&mp->dst, dst);
247 if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
770f1f66
BP
248 ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
249 "less than specified n_links %d",
f25d0cf3 250 s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
770f1f66 251 }
53ddd40a
BP
252
253 free(s);
254}
255
f25d0cf3
BP
256/* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
257 * describes. */
53ddd40a 258void
f25d0cf3 259multipath_format(const struct ofpact_multipath *mp, struct ds *s)
53ddd40a
BP
260{
261 const char *fields, *algorithm;
262
f25d0cf3 263 fields = flow_hash_fields_to_str(mp->fields);
53ddd40a 264
f25d0cf3 265 switch (mp->algorithm) {
53ddd40a
BP
266 case NX_MP_ALG_MODULO_N:
267 algorithm = "modulo_n";
268 break;
269 case NX_MP_ALG_HASH_THRESHOLD:
270 algorithm = "hash_threshold";
271 break;
272 case NX_MP_ALG_HRW:
273 algorithm = "hrw";
274 break;
275 case NX_MP_ALG_ITER_HASH:
276 algorithm = "iter_hash";
277 break;
278 default:
279 algorithm = "<unknown>";
280 }
281
282 ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
f25d0cf3
BP
283 fields, mp->basis, algorithm, mp->max_link + 1,
284 mp->arg);
285 mf_format_subfield(&mp->dst, s);
53ddd40a
BP
286 ds_put_char(s, ')');
287}