lib/multipath.c

   1 /*
   2  * Copyright (c) 2010, 2011, 2012, 2013 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 "dynamic-string.h"
  25 #include "nx-match.h"
  26 #include "ofp-actions.h"
  27 #include "ofp-errors.h"
  28 #include "ofp-util.h"
  29 #include "openflow/nicira-ext.h"
  30 #include "packets.h"
  31 #include "vlog.h"
  32
  33 VLOG_DEFINE_THIS_MODULE(multipath);
  34
  35 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
  36 \f
  37 /* Converts 'nam' into 'mp'.  Returns 0 if successful, otherwise an
  38  * OFPERR_*. */
  39 enum ofperr
  40 multipath_from_openflow(const struct nx_action_multipath *nam,
  41                         struct ofpact_multipath *mp)
  42 {
  43     uint32_t n_links = ntohs(nam->max_link) + 1;
  44     size_t min_n_bits = log_2_ceil(n_links);
  45
  46     ofpact_init_MULTIPATH(mp);
  47     mp->fields = ntohs(nam->fields);
  48     mp->basis = ntohs(nam->basis);
  49     mp->algorithm = ntohs(nam->algorithm);
  50     mp->max_link = ntohs(nam->max_link);
  51     mp->arg = ntohl(nam->arg);
  52     mp->dst.field = mf_from_nxm_header(ntohl(nam->dst));
  53     mp->dst.ofs = nxm_decode_ofs(nam->ofs_nbits);
  54     mp->dst.n_bits = nxm_decode_n_bits(nam->ofs_nbits);
  55
  56     if (!flow_hash_fields_valid(mp->fields)) {
  57         VLOG_WARN_RL(&rl, "unsupported fields %d", (int) mp->fields);
  58         return OFPERR_OFPBAC_BAD_ARGUMENT;
  59     } else if (mp->algorithm != NX_MP_ALG_MODULO_N
  60                && mp->algorithm != NX_MP_ALG_HASH_THRESHOLD
  61                && mp->algorithm != NX_MP_ALG_HRW
  62                && mp->algorithm != NX_MP_ALG_ITER_HASH) {
  63         VLOG_WARN_RL(&rl, "unsupported algorithm %d", (int) mp->algorithm);
  64         return OFPERR_OFPBAC_BAD_ARGUMENT;
  65     } else if (mp->dst.n_bits < min_n_bits) {
  66         VLOG_WARN_RL(&rl, "multipath action requires at least %"PRIuSIZE" bits for "
  67                      "%"PRIu32" links", min_n_bits, n_links);
  68         return OFPERR_OFPBAC_BAD_ARGUMENT;
  69     }
  70
  71     return multipath_check(mp, NULL);
  72 }
  73
  74 /* Checks that 'mp' is valid on flow.  Returns 0 if it is valid, otherwise an
  75  * OFPERR_*. */
  76 enum ofperr
  77 multipath_check(const struct ofpact_multipath *mp,
  78                 const struct flow *flow)
  79 {
  80     return mf_check_dst(&mp->dst, flow);
  81 }
  82
  83 /* Converts 'mp' into an OpenFlow NXAST_MULTIPATH action, which it appends to
  84  * 'openflow'. */
  85 void
  86 multipath_to_nxast(const struct ofpact_multipath *mp, struct ofpbuf *openflow)
  87 {
  88     struct nx_action_multipath *nam = ofputil_put_NXAST_MULTIPATH(openflow);
  89
  90     nam->fields = htons(mp->fields);
  91     nam->basis = htons(mp->basis);
  92     nam->algorithm = htons(mp->algorithm);
  93     nam->max_link = htons(mp->max_link);
  94     nam->arg = htonl(mp->arg);
  95     nam->ofs_nbits = nxm_encode_ofs_nbits(mp->dst.ofs, mp->dst.n_bits);
  96     nam->dst = htonl(mp->dst.field->nxm_header);
  97 }
  98 \f
  99 /* multipath_execute(). */
 100
 101 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
 102                                     unsigned int n_links, unsigned int arg);
 103
 104 /* Executes 'mp' based on the current contents of 'flow', writing the results
 105  * back into 'flow'.  Sets fields in 'wc' that were used to calculate
 106  * the result. */
 107 void
 108 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
 109                   struct flow_wildcards *wc)
 110 {
 111     /* Calculate value to store. */
 112     uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
 113     uint16_t link = multipath_algorithm(hash, mp->algorithm,
 114                                         mp->max_link + 1, mp->arg);
 115
 116     flow_mask_hash_fields(flow, wc, mp->fields);
 117     nxm_reg_load(&mp->dst, link, flow, wc);
 118 }
 119
 120 static uint16_t
 121 algorithm_hrw(uint32_t hash, unsigned int n_links)
 122 {
 123     uint32_t best_weight;
 124     uint16_t best_link;
 125     unsigned int link;
 126
 127     best_link = 0;
 128     best_weight = hash_2words(hash, 0);
 129     for (link = 1; link < n_links; link++) {
 130         uint32_t weight = hash_2words(hash, link);
 131         if (weight > best_weight) {
 132             best_link = link;
 133             best_weight = weight;
 134         }
 135     }
 136     return best_link;
 137 }
 138
 139 /* Works for 'x' in the range [1,65536], which is all we need.  */
 140 static unsigned int
 141 round_up_pow2(unsigned int x)
 142 {
 143     x--;
 144     x |= x >> 1;
 145     x |= x >> 2;
 146     x |= x >> 4;
 147     x |= x >> 8;
 148     return x + 1;
 149 }
 150
 151 static uint16_t
 152 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
 153 {
 154     uint16_t link;
 155     int i;
 156
 157     if (modulo < n_links || modulo / 2 > n_links) {
 158         modulo = round_up_pow2(n_links);
 159     }
 160
 161     i = 0;
 162     do {
 163         link = hash_2words(hash, i++) % modulo;
 164     } while (link >= n_links);
 165
 166     return link;
 167 }
 168
 169 static uint16_t
 170 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
 171                     unsigned int n_links, unsigned int arg)
 172 {
 173     switch (algorithm) {
 174     case NX_MP_ALG_MODULO_N:
 175         return hash % n_links;
 176
 177     case NX_MP_ALG_HASH_THRESHOLD:
 178         if (n_links == 1) {
 179             return 0;
 180         }
 181         return hash / (UINT32_MAX / n_links + 1);
 182
 183     case NX_MP_ALG_HRW:
 184         return (n_links <= 64
 185                 ? algorithm_hrw(hash, n_links)
 186                 : algorithm_iter_hash(hash, n_links, 0));
 187
 188     case NX_MP_ALG_ITER_HASH:
 189         return algorithm_iter_hash(hash, n_links, arg);
 190     }
 191
 192     OVS_NOT_REACHED();
 193 }
 194 \f
 195 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
 196  * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
 197  *
 198  * Returns NULL if successful, otherwise a malloc()'d string describing the
 199  * error.  The caller is responsible for freeing the returned string.*/
 200 static char * WARN_UNUSED_RESULT
 201 multipath_parse__(struct ofpact_multipath *mp, const char *s_, char *s)
 202 {
 203     char *save_ptr = NULL;
 204     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
 205     char *error;
 206     int n_links;
 207
 208     fields = strtok_r(s, ", ", &save_ptr);
 209     basis = strtok_r(NULL, ", ", &save_ptr);
 210     algorithm = strtok_r(NULL, ", ", &save_ptr);
 211     n_links_str = strtok_r(NULL, ", ", &save_ptr);
 212     arg = strtok_r(NULL, ", ", &save_ptr);
 213     dst = strtok_r(NULL, ", ", &save_ptr);
 214     if (!dst) {
 215         return xasprintf("%s: not enough arguments to multipath action", s_);
 216     }
 217
 218     ofpact_init_MULTIPATH(mp);
 219     if (!strcasecmp(fields, "eth_src")) {
 220         mp->fields = NX_HASH_FIELDS_ETH_SRC;
 221     } else if (!strcasecmp(fields, "symmetric_l4")) {
 222         mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
 223     } else {
 224         return xasprintf("%s: unknown fields `%s'", s_, fields);
 225     }
 226     mp->basis = atoi(basis);
 227     if (!strcasecmp(algorithm, "modulo_n")) {
 228         mp->algorithm = NX_MP_ALG_MODULO_N;
 229     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 230         mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
 231     } else if (!strcasecmp(algorithm, "hrw")) {
 232         mp->algorithm = NX_MP_ALG_HRW;
 233     } else if (!strcasecmp(algorithm, "iter_hash")) {
 234         mp->algorithm = NX_MP_ALG_ITER_HASH;
 235     } else {
 236         return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
 237     }
 238     n_links = atoi(n_links_str);
 239     if (n_links < 1 || n_links > 65536) {
 240         return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
 241                          s_, n_links);
 242     }
 243     mp->max_link = n_links - 1;
 244     mp->arg = atoi(arg);
 245
 246     error = mf_parse_subfield(&mp->dst, dst);
 247     if (error) {
 248         return error;
 249     }
 250     if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
 251         return xasprintf("%s: %d-bit destination field has %u possible "
 252                          "values, less than specified n_links %d",
 253                          s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
 254     }
 255
 256     return NULL;
 257 }
 258
 259 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
 260  * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
 261  *
 262  * Returns NULL if successful, otherwise a malloc()'d string describing the
 263  * error.  The caller is responsible for freeing the returned string. */
 264 char * WARN_UNUSED_RESULT
 265 multipath_parse(struct ofpact_multipath *mp, const char *s_)
 266 {
 267     char *s = xstrdup(s_);
 268     char *error = multipath_parse__(mp, s_, s);
 269     free(s);
 270     return error;
 271 }
 272
 273 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
 274  * describes. */
 275 void
 276 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
 277 {
 278     const char *fields, *algorithm;
 279
 280     fields = flow_hash_fields_to_str(mp->fields);
 281
 282     switch (mp->algorithm) {
 283     case NX_MP_ALG_MODULO_N:
 284         algorithm = "modulo_n";
 285         break;
 286     case NX_MP_ALG_HASH_THRESHOLD:
 287         algorithm = "hash_threshold";
 288         break;
 289     case NX_MP_ALG_HRW:
 290         algorithm = "hrw";
 291         break;
 292     case NX_MP_ALG_ITER_HASH:
 293         algorithm = "iter_hash";
 294         break;
 295     default:
 296         algorithm = "<unknown>";
 297     }
 298
 299     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
 300                   fields, mp->basis, algorithm, mp->max_link + 1,
 301                   mp->arg);
 302     mf_format_subfield(&mp->dst, s);
 303     ds_put_char(s, ')');
 304 }