lib/multipath.c

   1 /*
   2  * Copyright (c) 2010, 2011, 2012 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 %zu 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'. */
 106 void
 107 multipath_execute(const struct ofpact_multipath *mp, struct flow *flow)
 108 {
 109     /* Calculate value to store. */
 110     uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
 111     uint16_t link = multipath_algorithm(hash, mp->algorithm,
 112                                         mp->max_link + 1, mp->arg);
 113
 114     nxm_reg_load(&mp->dst, link, flow);
 115 }
 116
 117 static uint16_t
 118 algorithm_hrw(uint32_t hash, unsigned int n_links)
 119 {
 120     uint32_t best_weight;
 121     uint16_t best_link;
 122     unsigned int link;
 123
 124     best_link = 0;
 125     best_weight = hash_2words(hash, 0);
 126     for (link = 1; link < n_links; link++) {
 127         uint32_t weight = hash_2words(hash, link);
 128         if (weight > best_weight) {
 129             best_link = link;
 130             best_weight = weight;
 131         }
 132     }
 133     return best_link;
 134 }
 135
 136 /* Works for 'x' in the range [1,65536], which is all we need.  */
 137 static unsigned int
 138 round_up_pow2(unsigned int x)
 139 {
 140     x--;
 141     x |= x >> 1;
 142     x |= x >> 2;
 143     x |= x >> 4;
 144     x |= x >> 8;
 145     return x + 1;
 146 }
 147
 148 static uint16_t
 149 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
 150 {
 151     uint16_t link;
 152     int i;
 153
 154     if (modulo < n_links || modulo / 2 > n_links) {
 155         modulo = round_up_pow2(n_links);
 156     }
 157
 158     i = 0;
 159     do {
 160         link = hash_2words(hash, i++) % modulo;
 161     } while (link >= n_links);
 162
 163     return link;
 164 }
 165
 166 static uint16_t
 167 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
 168                     unsigned int n_links, unsigned int arg)
 169 {
 170     switch (algorithm) {
 171     case NX_MP_ALG_MODULO_N:
 172         return hash % n_links;
 173
 174     case NX_MP_ALG_HASH_THRESHOLD:
 175         if (n_links == 1) {
 176             return 0;
 177         }
 178         return hash / (UINT32_MAX / n_links + 1);
 179
 180     case NX_MP_ALG_HRW:
 181         return (n_links <= 64
 182                 ? algorithm_hrw(hash, n_links)
 183                 : algorithm_iter_hash(hash, n_links, 0));
 184
 185     case NX_MP_ALG_ITER_HASH:
 186         return algorithm_iter_hash(hash, n_links, arg);
 187     }
 188
 189     NOT_REACHED();
 190 }
 191 \f
 192 /* Parses 's_' as a set of arguments to the "multipath" action and initializes
 193  * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
 194  *
 195  * Prints an error on stderr and aborts the program if 's_' syntax is
 196  * invalid. */
 197 void
 198 multipath_parse(struct ofpact_multipath *mp, const char *s_)
 199 {
 200     char *s = xstrdup(s_);
 201     char *save_ptr = NULL;
 202     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
 203     int n_links;
 204
 205     fields = strtok_r(s, ", ", &save_ptr);
 206     basis = strtok_r(NULL, ", ", &save_ptr);
 207     algorithm = strtok_r(NULL, ", ", &save_ptr);
 208     n_links_str = strtok_r(NULL, ", ", &save_ptr);
 209     arg = strtok_r(NULL, ", ", &save_ptr);
 210     dst = strtok_r(NULL, ", ", &save_ptr);
 211     if (!dst) {
 212         ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
 213     }
 214
 215     ofpact_init_MULTIPATH(mp);
 216     if (!strcasecmp(fields, "eth_src")) {
 217         mp->fields = NX_HASH_FIELDS_ETH_SRC;
 218     } else if (!strcasecmp(fields, "symmetric_l4")) {
 219         mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
 220     } else {
 221         ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
 222     }
 223     mp->basis = atoi(basis);
 224     if (!strcasecmp(algorithm, "modulo_n")) {
 225         mp->algorithm = NX_MP_ALG_MODULO_N;
 226     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 227         mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
 228     } else if (!strcasecmp(algorithm, "hrw")) {
 229         mp->algorithm = NX_MP_ALG_HRW;
 230     } else if (!strcasecmp(algorithm, "iter_hash")) {
 231         mp->algorithm = NX_MP_ALG_ITER_HASH;
 232     } else {
 233         ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
 234     }
 235     n_links = atoi(n_links_str);
 236     if (n_links < 1 || n_links > 65536) {
 237         ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
 238                   s_, n_links);
 239     }
 240     mp->max_link = n_links - 1;
 241     mp->arg = atoi(arg);
 242
 243     mf_parse_subfield(&mp->dst, dst);
 244     if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
 245         ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
 246                   "less than specified n_links %d",
 247                   s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
 248     }
 249
 250     free(s);
 251 }
 252
 253 /* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
 254  * describes. */
 255 void
 256 multipath_format(const struct ofpact_multipath *mp, struct ds *s)
 257 {
 258     const char *fields, *algorithm;
 259
 260     fields = flow_hash_fields_to_str(mp->fields);
 261
 262     switch (mp->algorithm) {
 263     case NX_MP_ALG_MODULO_N:
 264         algorithm = "modulo_n";
 265         break;
 266     case NX_MP_ALG_HASH_THRESHOLD:
 267         algorithm = "hash_threshold";
 268         break;
 269     case NX_MP_ALG_HRW:
 270         algorithm = "hrw";
 271         break;
 272     case NX_MP_ALG_ITER_HASH:
 273         algorithm = "iter_hash";
 274         break;
 275     default:
 276         algorithm = "<unknown>";
 277     }
 278
 279     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
 280                   fields, mp->basis, algorithm, mp->max_link + 1,
 281                   mp->arg);
 282     mf_format_subfield(&mp->dst, s);
 283     ds_put_char(s, ')');
 284 }