lib/multipath.c

   1 /*
   2  * Copyright (c) 2010, 2011, 2012, 2013, 2014 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 "dynamic-string.h"
  26 #include "nx-match.h"
  27 #include "ofp-actions.h"
  28 #include "ofp-util.h"
  29 #include "openvswitch/ofp-errors.h"
  30 #include "openflow/nicira-ext.h"
  31 #include "packets.h"
  32 \f
  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,
  37                 const struct flow *flow)
  38 {
  39     return mf_check_dst(&mp->dst, flow);
  40 }
  41 \f
  42 /* multipath_execute(). */
  43
  44 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
  45                                     unsigned int n_links, unsigned int arg);
  46
  47 /* Executes 'mp' based on the current contents of 'flow', writing the results
  48  * back into 'flow'.  Sets fields in 'wc' that were used to calculate
  49  * the result. */
  50 void
  51 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
  52                   struct flow_wildcards *wc)
  53 {
  54     /* Calculate value to store. */
  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
  59     flow_mask_hash_fields(flow, wc, mp->fields);
  60     nxm_reg_load(&mp->dst, link, flow, wc);
  61 }
  62
  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:
 121         if (n_links == 1) {
 122             return 0;
 123         }
 124         return hash / (UINT32_MAX / n_links + 1);
 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
 135     OVS_NOT_REACHED();
 136 }
 137 \f
 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  *
 141  * Returns NULL if successful, otherwise a malloc()'d string describing the
 142  * error.  The caller is responsible for freeing the returned string.*/
 143 static char * OVS_WARN_UNUSED_RESULT
 144 multipath_parse__(struct ofpact_multipath *mp, const char *s_, char *s)
 145 {
 146     char *save_ptr = NULL;
 147     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
 148     char *error;
 149     int n_links;
 150
 151     fields = strtok_r(s, ", ", &save_ptr);
 152     basis = strtok_r(NULL, ", ", &save_ptr);
 153     algorithm = strtok_r(NULL, ", ", &save_ptr);
 154     n_links_str = strtok_r(NULL, ", ", &save_ptr);
 155     arg = strtok_r(NULL, ", ", &save_ptr);
 156     dst = strtok_r(NULL, ", ", &save_ptr);
 157     if (!dst) {
 158         return xasprintf("%s: not enough arguments to multipath action", s_);
 159     }
 160
 161     ofpact_init_MULTIPATH(mp);
 162     if (!strcasecmp(fields, "eth_src")) {
 163         mp->fields = NX_HASH_FIELDS_ETH_SRC;
 164     } else if (!strcasecmp(fields, "symmetric_l4")) {
 165         mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
 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;
 170     } else {
 171         return xasprintf("%s: unknown fields `%s'", s_, fields);
 172     }
 173     mp->basis = atoi(basis);
 174     if (!strcasecmp(algorithm, "modulo_n")) {
 175         mp->algorithm = NX_MP_ALG_MODULO_N;
 176     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 177         mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
 178     } else if (!strcasecmp(algorithm, "hrw")) {
 179         mp->algorithm = NX_MP_ALG_HRW;
 180     } else if (!strcasecmp(algorithm, "iter_hash")) {
 181         mp->algorithm = NX_MP_ALG_ITER_HASH;
 182     } else {
 183         return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
 184     }
 185     n_links = atoi(n_links_str);
 186     if (n_links < 1 || n_links > 65536) {
 187         return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
 188                          s_, n_links);
 189     }
 190     mp->max_link = n_links - 1;
 191     mp->arg = atoi(arg);
 192
 193     error = mf_parse_subfield(&mp->dst, dst);
 194     if (error) {
 195         return error;
 196     }
 197     if (!mf_nxm_header(mp->dst.field->id)) {
 198         return xasprintf("%s: experimenter OXM field '%s' not supported",
 199                          s, dst);
 200     }
 201     if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
 202         return xasprintf("%s: %d-bit destination field has %u possible "
 203                          "values, less than specified n_links %d",
 204                          s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
 205     }
 206
 207     return NULL;
 208 }
 209
 210 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
 211  * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
 212  *
 213  * Returns NULL if successful, otherwise a malloc()'d string describing the
 214  * error.  The caller is responsible for freeing the returned string. */
 215 char * OVS_WARN_UNUSED_RESULT
 216 multipath_parse(struct ofpact_multipath *mp, const char *s_)
 217 {
 218     char *s = xstrdup(s_);
 219     char *error = multipath_parse__(mp, s_, s);
 220     free(s);
 221     return error;
 222 }
 223
 224 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
 225  * describes. */
 226 void
 227 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
 228 {
 229     const char *fields, *algorithm;
 230
 231     fields = flow_hash_fields_to_str(mp->fields);
 232
 233     switch (mp->algorithm) {
 234     case NX_MP_ALG_MODULO_N:
 235         algorithm = "modulo_n";
 236         break;
 237     case NX_MP_ALG_HASH_THRESHOLD:
 238         algorithm = "hash_threshold";
 239         break;
 240     case NX_MP_ALG_HRW:
 241         algorithm = "hrw";
 242         break;
 243     case NX_MP_ALG_ITER_HASH:
 244         algorithm = "iter_hash";
 245         break;
 246     default:
 247         algorithm = "<unknown>";
 248     }
 249
 250     ds_put_format(s, "%smultipath(%s%s,%"PRIu16",%s,%d,%"PRIu16",",
 251                   colors.paren, colors.end, fields, mp->basis, algorithm,
 252                   mp->max_link + 1, mp->arg);
 253     mf_format_subfield(&mp->dst, s);
 254     ds_put_format(s, "%s)%s", colors.paren, colors.end);
 255 }