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