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