New action NXAST_RESUBMIT_TABLE.
[openvswitch] / lib / multipath.c
1 /*
2  * Copyright (c) 2010, 2011 Nicira Networks.
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 "dynamic-string.h"
25 #include "nx-match.h"
26 #include "ofp-util.h"
27 #include "openflow/nicira-ext.h"
28 #include "packets.h"
29 #include "vlog.h"
30
31 VLOG_DEFINE_THIS_MODULE(multipath);
32
33 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
34 \f
35 /* multipath_check(). */
36 int
37 multipath_check(const struct nx_action_multipath *mp, const struct flow *flow)
38 {
39     uint32_t n_links = ntohs(mp->max_link) + 1;
40     size_t min_n_bits = log_2_floor(n_links) + 1;
41     int error;
42
43     error = nxm_dst_check(mp->dst, mp->ofs_nbits, min_n_bits, flow);
44     if (error) {
45         return error;
46     }
47
48     if (!flow_hash_fields_valid(ntohs(mp->fields))) {
49         VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, ntohs(mp->fields));
50     } else if (mp->algorithm != htons(NX_MP_ALG_MODULO_N)
51                && mp->algorithm != htons(NX_MP_ALG_HASH_THRESHOLD)
52                && mp->algorithm != htons(NX_MP_ALG_HRW)
53                && mp->algorithm != htons(NX_MP_ALG_ITER_HASH)) {
54         VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16,
55                      ntohs(mp->algorithm));
56     } else {
57         return 0;
58     }
59
60     return ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT);
61 }
62 \f
63 /* multipath_execute(). */
64
65 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
66                                     unsigned int n_links, unsigned int arg);
67
68 void
69 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
70 {
71     /* Calculate value to store. */
72     uint32_t hash = flow_hash_fields(flow, ntohs(mp->fields),
73                                      ntohs(mp->basis));
74     uint16_t link = multipath_algorithm(hash, ntohs(mp->algorithm),
75                                         ntohs(mp->max_link) + 1,
76                                         ntohl(mp->arg));
77
78     nxm_reg_load(mp->dst, mp->ofs_nbits, link, flow);
79 }
80
81 static uint16_t
82 algorithm_hrw(uint32_t hash, unsigned int n_links)
83 {
84     uint32_t best_weight;
85     uint16_t best_link;
86     unsigned int link;
87
88     best_link = 0;
89     best_weight = hash_2words(hash, 0);
90     for (link = 1; link < n_links; link++) {
91         uint32_t weight = hash_2words(hash, link);
92         if (weight > best_weight) {
93             best_link = link;
94             best_weight = weight;
95         }
96     }
97     return best_link;
98 }
99
100 /* Works for 'x' in the range [1,65536], which is all we need.  */
101 static unsigned int
102 round_up_pow2(unsigned int x)
103 {
104     x--;
105     x |= x >> 1;
106     x |= x >> 2;
107     x |= x >> 4;
108     x |= x >> 8;
109     return x + 1;
110 }
111
112 static uint16_t
113 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
114 {
115     uint16_t link;
116     int i;
117
118     if (modulo < n_links || modulo / 2 > n_links) {
119         modulo = round_up_pow2(n_links);
120     }
121
122     i = 0;
123     do {
124         link = hash_2words(hash, i++) % modulo;
125     } while (link >= n_links);
126
127     return link;
128 }
129
130 static uint16_t
131 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
132                     unsigned int n_links, unsigned int arg)
133 {
134     switch (algorithm) {
135     case NX_MP_ALG_MODULO_N:
136         return hash % n_links;
137
138     case NX_MP_ALG_HASH_THRESHOLD:
139         if (n_links == 1) {
140             return 0;
141         }
142         return hash / (UINT32_MAX / n_links + 1);
143
144     case NX_MP_ALG_HRW:
145         return (n_links <= 64
146                 ? algorithm_hrw(hash, n_links)
147                 : algorithm_iter_hash(hash, n_links, 0));
148
149     case NX_MP_ALG_ITER_HASH:
150         return algorithm_iter_hash(hash, n_links, arg);
151     }
152
153     NOT_REACHED();
154 }
155 \f
156 /* multipath_parse(). */
157
158 void
159 multipath_parse(struct nx_action_multipath *mp, const char *s_)
160 {
161     char *s = xstrdup(s_);
162     char *save_ptr = NULL;
163     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
164     uint32_t header;
165     int ofs, n_bits;
166     int n_links;
167
168     fields = strtok_r(s, ", ", &save_ptr);
169     basis = strtok_r(NULL, ", ", &save_ptr);
170     algorithm = strtok_r(NULL, ", ", &save_ptr);
171     n_links_str = strtok_r(NULL, ", ", &save_ptr);
172     arg = strtok_r(NULL, ", ", &save_ptr);
173     dst = strtok_r(NULL, ", ", &save_ptr);
174     if (!dst) {
175         ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
176     }
177
178     memset(mp, 0, sizeof *mp);
179     mp->type = htons(OFPAT_VENDOR);
180     mp->len = htons(sizeof *mp);
181     mp->vendor = htonl(NX_VENDOR_ID);
182     mp->subtype = htons(NXAST_MULTIPATH);
183     if (!strcasecmp(fields, "eth_src")) {
184         mp->fields = htons(NX_HASH_FIELDS_ETH_SRC);
185     } else if (!strcasecmp(fields, "symmetric_l4")) {
186         mp->fields = htons(NX_HASH_FIELDS_SYMMETRIC_L4);
187     } else {
188         ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
189     }
190     mp->basis = htons(atoi(basis));
191     if (!strcasecmp(algorithm, "modulo_n")) {
192         mp->algorithm = htons(NX_MP_ALG_MODULO_N);
193     } else if (!strcasecmp(algorithm, "hash_threshold")) {
194         mp->algorithm = htons(NX_MP_ALG_HASH_THRESHOLD);
195     } else if (!strcasecmp(algorithm, "hrw")) {
196         mp->algorithm = htons(NX_MP_ALG_HRW);
197     } else if (!strcasecmp(algorithm, "iter_hash")) {
198         mp->algorithm = htons(NX_MP_ALG_ITER_HASH);
199     } else {
200         ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
201     }
202     n_links = atoi(n_links_str);
203     if (n_links < 1 || n_links > 65536) {
204         ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
205                   s_, n_links);
206     }
207     mp->max_link = htons(n_links - 1);
208     mp->arg = htonl(atoi(arg));
209
210     nxm_parse_field_bits(dst, &header, &ofs, &n_bits);
211     if (n_bits < 16 && n_links > (1u << n_bits)) {
212         ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
213                   "less than specified n_links %d",
214                   s_, n_bits, 1u << n_bits, n_links);
215     }
216     mp->ofs_nbits = nxm_encode_ofs_nbits(ofs, n_bits);
217     mp->dst = htonl(header);
218
219     free(s);
220 }
221
222 void
223 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
224 {
225     const char *fields, *algorithm;
226
227     uint16_t mp_fields    = ntohs(mp->fields);
228     uint16_t mp_algorithm = ntohs(mp->algorithm);
229
230     fields = flow_hash_fields_to_str(mp_fields);
231
232     switch ((enum nx_mp_algorithm) mp_algorithm) {
233     case NX_MP_ALG_MODULO_N:
234         algorithm = "modulo_n";
235         break;
236     case NX_MP_ALG_HASH_THRESHOLD:
237         algorithm = "hash_threshold";
238         break;
239     case NX_MP_ALG_HRW:
240         algorithm = "hrw";
241         break;
242     case NX_MP_ALG_ITER_HASH:
243         algorithm = "iter_hash";
244         break;
245     default:
246         algorithm = "<unknown>";
247     }
248
249     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
250                   fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
251                   ntohl(mp->arg));
252     nxm_format_field_bits(s, ntohl(mp->dst), nxm_decode_ofs(mp->ofs_nbits),
253                           nxm_decode_n_bits(mp->ofs_nbits));
254     ds_put_char(s, ')');
255 }