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