lib/multipath.c

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