]>
Commit | Line | Data |
---|---|---|
53ddd40a | 1 | /* |
c2d936a4 | 2 | * Copyright (c) 2010, 2011, 2012, 2013, 2014 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" | |
53ddd40a | 31 | \f |
f25d0cf3 BP |
32 | /* Checks that 'mp' is valid on flow. Returns 0 if it is valid, otherwise an |
33 | * OFPERR_*. */ | |
34 | enum ofperr | |
35 | multipath_check(const struct ofpact_multipath *mp, | |
36 | const struct flow *flow) | |
37 | { | |
38 | return mf_check_dst(&mp->dst, flow); | |
39 | } | |
53ddd40a BP |
40 | \f |
41 | /* multipath_execute(). */ | |
42 | ||
53ddd40a BP |
43 | static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm, |
44 | unsigned int n_links, unsigned int arg); | |
45 | ||
f25d0cf3 | 46 | /* Executes 'mp' based on the current contents of 'flow', writing the results |
bcd2633a JP |
47 | * back into 'flow'. Sets fields in 'wc' that were used to calculate |
48 | * the result. */ | |
53ddd40a | 49 | void |
bcd2633a JP |
50 | multipath_execute(const struct ofpact_multipath *mp, struct flow *flow, |
51 | struct flow_wildcards *wc) | |
53ddd40a BP |
52 | { |
53 | /* Calculate value to store. */ | |
f25d0cf3 BP |
54 | uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis); |
55 | uint16_t link = multipath_algorithm(hash, mp->algorithm, | |
56 | mp->max_link + 1, mp->arg); | |
57 | ||
6cdd5145 | 58 | flow_mask_hash_fields(flow, wc, mp->fields); |
f74e7df7 | 59 | nxm_reg_load(&mp->dst, link, flow, wc); |
53ddd40a BP |
60 | } |
61 | ||
53ddd40a BP |
62 | static uint16_t |
63 | algorithm_hrw(uint32_t hash, unsigned int n_links) | |
64 | { | |
65 | uint32_t best_weight; | |
66 | uint16_t best_link; | |
67 | unsigned int link; | |
68 | ||
69 | best_link = 0; | |
70 | best_weight = hash_2words(hash, 0); | |
71 | for (link = 1; link < n_links; link++) { | |
72 | uint32_t weight = hash_2words(hash, link); | |
73 | if (weight > best_weight) { | |
74 | best_link = link; | |
75 | best_weight = weight; | |
76 | } | |
77 | } | |
78 | return best_link; | |
79 | } | |
80 | ||
81 | /* Works for 'x' in the range [1,65536], which is all we need. */ | |
82 | static unsigned int | |
83 | round_up_pow2(unsigned int x) | |
84 | { | |
85 | x--; | |
86 | x |= x >> 1; | |
87 | x |= x >> 2; | |
88 | x |= x >> 4; | |
89 | x |= x >> 8; | |
90 | return x + 1; | |
91 | } | |
92 | ||
93 | static uint16_t | |
94 | algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo) | |
95 | { | |
96 | uint16_t link; | |
97 | int i; | |
98 | ||
99 | if (modulo < n_links || modulo / 2 > n_links) { | |
100 | modulo = round_up_pow2(n_links); | |
101 | } | |
102 | ||
103 | i = 0; | |
104 | do { | |
105 | link = hash_2words(hash, i++) % modulo; | |
106 | } while (link >= n_links); | |
107 | ||
108 | return link; | |
109 | } | |
110 | ||
111 | static uint16_t | |
112 | multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm, | |
113 | unsigned int n_links, unsigned int arg) | |
114 | { | |
115 | switch (algorithm) { | |
116 | case NX_MP_ALG_MODULO_N: | |
117 | return hash % n_links; | |
118 | ||
119 | case NX_MP_ALG_HASH_THRESHOLD: | |
d7bf2b00 BP |
120 | if (n_links == 1) { |
121 | return 0; | |
122 | } | |
123 | return hash / (UINT32_MAX / n_links + 1); | |
53ddd40a BP |
124 | |
125 | case NX_MP_ALG_HRW: | |
126 | return (n_links <= 64 | |
127 | ? algorithm_hrw(hash, n_links) | |
128 | : algorithm_iter_hash(hash, n_links, 0)); | |
129 | ||
130 | case NX_MP_ALG_ITER_HASH: | |
131 | return algorithm_iter_hash(hash, n_links, arg); | |
132 | } | |
133 | ||
428b2edd | 134 | OVS_NOT_REACHED(); |
53ddd40a BP |
135 | } |
136 | \f | |
f25d0cf3 BP |
137 | /* Parses 's_' as a set of arguments to the "multipath" action and initializes |
138 | * 'mp' accordingly. ovs-ofctl(8) describes the format parsed. | |
139 | * | |
bdda5aca BP |
140 | * Returns NULL if successful, otherwise a malloc()'d string describing the |
141 | * error. The caller is responsible for freeing the returned string.*/ | |
cab50449 | 142 | static char * OVS_WARN_UNUSED_RESULT |
bdda5aca | 143 | multipath_parse__(struct ofpact_multipath *mp, const char *s_, char *s) |
53ddd40a | 144 | { |
53ddd40a | 145 | char *save_ptr = NULL; |
f25d0cf3 | 146 | char *fields, *basis, *algorithm, *n_links_str, *arg, *dst; |
bdda5aca | 147 | char *error; |
770f1f66 | 148 | int n_links; |
53ddd40a BP |
149 | |
150 | fields = strtok_r(s, ", ", &save_ptr); | |
151 | basis = strtok_r(NULL, ", ", &save_ptr); | |
152 | algorithm = strtok_r(NULL, ", ", &save_ptr); | |
770f1f66 | 153 | n_links_str = strtok_r(NULL, ", ", &save_ptr); |
53ddd40a | 154 | arg = strtok_r(NULL, ", ", &save_ptr); |
f25d0cf3 BP |
155 | dst = strtok_r(NULL, ", ", &save_ptr); |
156 | if (!dst) { | |
bdda5aca | 157 | return xasprintf("%s: not enough arguments to multipath action", s_); |
53ddd40a BP |
158 | } |
159 | ||
f25d0cf3 | 160 | ofpact_init_MULTIPATH(mp); |
53ddd40a | 161 | if (!strcasecmp(fields, "eth_src")) { |
f25d0cf3 | 162 | mp->fields = NX_HASH_FIELDS_ETH_SRC; |
53ddd40a | 163 | } else if (!strcasecmp(fields, "symmetric_l4")) { |
f25d0cf3 | 164 | mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4; |
53ddd40a | 165 | } else { |
bdda5aca | 166 | return xasprintf("%s: unknown fields `%s'", s_, fields); |
53ddd40a | 167 | } |
f25d0cf3 | 168 | mp->basis = atoi(basis); |
53ddd40a | 169 | if (!strcasecmp(algorithm, "modulo_n")) { |
f25d0cf3 | 170 | mp->algorithm = NX_MP_ALG_MODULO_N; |
53ddd40a | 171 | } else if (!strcasecmp(algorithm, "hash_threshold")) { |
f25d0cf3 | 172 | mp->algorithm = NX_MP_ALG_HASH_THRESHOLD; |
53ddd40a | 173 | } else if (!strcasecmp(algorithm, "hrw")) { |
f25d0cf3 | 174 | mp->algorithm = NX_MP_ALG_HRW; |
53ddd40a | 175 | } else if (!strcasecmp(algorithm, "iter_hash")) { |
f25d0cf3 | 176 | mp->algorithm = NX_MP_ALG_ITER_HASH; |
53ddd40a | 177 | } else { |
bdda5aca | 178 | return xasprintf("%s: unknown algorithm `%s'", s_, algorithm); |
53ddd40a | 179 | } |
770f1f66 BP |
180 | n_links = atoi(n_links_str); |
181 | if (n_links < 1 || n_links > 65536) { | |
bdda5aca BP |
182 | return xasprintf("%s: n_links %d is not in valid range 1 to 65536", |
183 | s_, n_links); | |
770f1f66 | 184 | } |
f25d0cf3 BP |
185 | mp->max_link = n_links - 1; |
186 | mp->arg = atoi(arg); | |
53ddd40a | 187 | |
bdda5aca BP |
188 | error = mf_parse_subfield(&mp->dst, dst); |
189 | if (error) { | |
190 | return error; | |
191 | } | |
bad8a439 BP |
192 | if (!mf_nxm_header(mp->dst.field->id)) { |
193 | return xasprintf("%s: experimenter OXM field '%s' not supported", | |
194 | s, dst); | |
195 | } | |
f25d0cf3 | 196 | if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) { |
bdda5aca BP |
197 | return xasprintf("%s: %d-bit destination field has %u possible " |
198 | "values, less than specified n_links %d", | |
199 | s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links); | |
770f1f66 | 200 | } |
53ddd40a | 201 | |
bdda5aca BP |
202 | return NULL; |
203 | } | |
204 | ||
205 | /* Parses 's_' as a set of arguments to the "multipath" action and initializes | |
206 | * 'mp' accordingly. ovs-ofctl(8) describes the format parsed. | |
207 | * | |
208 | * Returns NULL if successful, otherwise a malloc()'d string describing the | |
209 | * error. The caller is responsible for freeing the returned string. */ | |
cab50449 | 210 | char * OVS_WARN_UNUSED_RESULT |
bdda5aca BP |
211 | multipath_parse(struct ofpact_multipath *mp, const char *s_) |
212 | { | |
213 | char *s = xstrdup(s_); | |
214 | char *error = multipath_parse__(mp, s_, s); | |
53ddd40a | 215 | free(s); |
bdda5aca | 216 | return error; |
53ddd40a BP |
217 | } |
218 | ||
f25d0cf3 BP |
219 | /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8) |
220 | * describes. */ | |
53ddd40a | 221 | void |
f25d0cf3 | 222 | multipath_format(const struct ofpact_multipath *mp, struct ds *s) |
53ddd40a BP |
223 | { |
224 | const char *fields, *algorithm; | |
225 | ||
f25d0cf3 | 226 | fields = flow_hash_fields_to_str(mp->fields); |
53ddd40a | 227 | |
f25d0cf3 | 228 | switch (mp->algorithm) { |
53ddd40a BP |
229 | case NX_MP_ALG_MODULO_N: |
230 | algorithm = "modulo_n"; | |
231 | break; | |
232 | case NX_MP_ALG_HASH_THRESHOLD: | |
233 | algorithm = "hash_threshold"; | |
234 | break; | |
235 | case NX_MP_ALG_HRW: | |
236 | algorithm = "hrw"; | |
237 | break; | |
238 | case NX_MP_ALG_ITER_HASH: | |
239 | algorithm = "iter_hash"; | |
240 | break; | |
241 | default: | |
242 | algorithm = "<unknown>"; | |
243 | } | |
244 | ||
245 | ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",", | |
f25d0cf3 BP |
246 | fields, mp->basis, algorithm, mp->max_link + 1, |
247 | mp->arg); | |
248 | mf_format_subfield(&mp->dst, s); | |
53ddd40a BP |
249 | ds_put_char(s, ')'); |
250 | } |