]>
Commit | Line | Data |
---|---|---|
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 | ||
33 | VLOG_DEFINE_THIS_MODULE(multipath); | |
34 | ||
35 | static 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 | 39 | enum ofperr |
f25d0cf3 BP |
40 | multipath_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_*. */ | |
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); | |
53ddd40a BP |
97 | } |
98 | \f | |
99 | /* multipath_execute(). */ | |
100 | ||
53ddd40a BP |
101 | static 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 | 107 | void |
bcd2633a JP |
108 | multipath_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 |
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: | |
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 | 200 | void |
f25d0cf3 | 201 | multipath_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 | 258 | void |
f25d0cf3 | 259 | multipath_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 | } |