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