lib/multipath.c

   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 \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 flow *flow)
  39 {
  40     return mf_check_dst(&mp->dst, flow);
  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 {
 172         return xasprintf("%s: unknown fields `%s'", s_, fields);
 173     }
 174     mp->basis = atoi(basis);
 175     if (!strcasecmp(algorithm, "modulo_n")) {
 176         mp->algorithm = NX_MP_ALG_MODULO_N;
 177     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 178         mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
 179     } else if (!strcasecmp(algorithm, "hrw")) {
 180         mp->algorithm = NX_MP_ALG_HRW;
 181     } else if (!strcasecmp(algorithm, "iter_hash")) {
 182         mp->algorithm = NX_MP_ALG_ITER_HASH;
 183     } else {
 184         return xasprintf("%s: unknown algorithm `%s'", s_, algorithm);
 185     }
 186     n_links = atoi(n_links_str);
 187     if (n_links < 1 || n_links > 65536) {
 188         return xasprintf("%s: n_links %d is not in valid range 1 to 65536",
 189                          s_, n_links);
 190     }
 191     mp->max_link = n_links - 1;
 192     mp->arg = atoi(arg);
 193
 194     error = mf_parse_subfield(&mp->dst, dst);
 195     if (error) {
 196         return error;
 197     }
 198     if (!mf_nxm_header(mp->dst.field->id)) {
 199         return xasprintf("%s: experimenter OXM field '%s' not supported",
 200                          s, dst);
 201     }
 202     if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
 203         return xasprintf("%s: %d-bit destination field has %u possible "
 204                          "values, less than specified n_links %d",
 205                          s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
 206     }
 207
 208     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 multipath_parse(struct ofpact_multipath *mp, const char *s_)
 218 {
 219     char *s = xstrdup(s_);
 220     char *error = multipath_parse__(mp, s_, s);
 221     free(s);
 222     return error;
 223 }
 224
 225 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
 226  * describes. */
 227 void
 228 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
 229 {
 230     const char *fields, *algorithm;
 231
 232     fields = flow_hash_fields_to_str(mp->fields);
 233
 234     switch (mp->algorithm) {
 235     case NX_MP_ALG_MODULO_N:
 236         algorithm = "modulo_n";
 237         break;
 238     case NX_MP_ALG_HASH_THRESHOLD:
 239         algorithm = "hash_threshold";
 240         break;
 241     case NX_MP_ALG_HRW:
 242         algorithm = "hrw";
 243         break;
 244     case NX_MP_ALG_ITER_HASH:
 245         algorithm = "iter_hash";
 246         break;
 247     default:
 248         algorithm = "<unknown>";
 249     }
 250
 251     ds_put_format(s, "%smultipath(%s%s,%"PRIu16",%s,%d,%"PRIu16",",
 252                   colors.paren, colors.end, fields, mp->basis, algorithm,
 253                   mp->max_link + 1, mp->arg);
 254     mf_format_subfield(&mp->dst, s);
 255     ds_put_format(s, "%s)%s", colors.paren, colors.end);
 256 }