lib/multipath.c

   1 /*
   2  * Copyright (c) 2010, 2011 Nicira Networks.
   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-util.h"
  27 #include "openflow/nicira-ext.h"
  28 #include "packets.h"
  29 #include "vlog.h"
  30
  31 VLOG_DEFINE_THIS_MODULE(multipath);
  32
  33 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
  34 \f
  35 /* multipath_check(). */
  36 int
  37 multipath_check(const struct nx_action_multipath *mp, const struct flow *flow)
  38 {
  39     uint32_t n_links = ntohs(mp->max_link) + 1;
  40     size_t min_n_bits = log_2_floor(n_links) + 1;
  41     int ofs = nxm_decode_ofs(mp->ofs_nbits);
  42     int n_bits = nxm_decode_n_bits(mp->ofs_nbits);
  43     int error;
  44
  45     error = nxm_dst_check(mp->dst, ofs, n_bits, flow);
  46     if (error) {
  47         return error;
  48     }
  49
  50     if (!flow_hash_fields_valid(ntohs(mp->fields))) {
  51         VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, ntohs(mp->fields));
  52     } else if (mp->algorithm != htons(NX_MP_ALG_MODULO_N)
  53                && mp->algorithm != htons(NX_MP_ALG_HASH_THRESHOLD)
  54                && mp->algorithm != htons(NX_MP_ALG_HRW)
  55                && mp->algorithm != htons(NX_MP_ALG_ITER_HASH)) {
  56         VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16,
  57                      ntohs(mp->algorithm));
  58     } else if (n_bits < min_n_bits) {
  59         VLOG_WARN_RL(&rl, "multipath action requires at least %zu bits for "
  60                      "%"PRIu32" links", min_n_bits, n_links);
  61     } else {
  62         return 0;
  63     }
  64
  65     return ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT);
  66 }
  67 \f
  68 /* multipath_execute(). */
  69
  70 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
  71                                     unsigned int n_links, unsigned int arg);
  72
  73 void
  74 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
  75 {
  76     /* Calculate value to store. */
  77     uint32_t hash = flow_hash_fields(flow, ntohs(mp->fields),
  78                                      ntohs(mp->basis));
  79     uint16_t link = multipath_algorithm(hash, ntohs(mp->algorithm),
  80                                         ntohs(mp->max_link) + 1,
  81                                         ntohl(mp->arg));
  82
  83     nxm_reg_load(mp->dst, mp->ofs_nbits, link, flow);
  84 }
  85
  86 static uint16_t
  87 algorithm_hrw(uint32_t hash, unsigned int n_links)
  88 {
  89     uint32_t best_weight;
  90     uint16_t best_link;
  91     unsigned int link;
  92
  93     best_link = 0;
  94     best_weight = hash_2words(hash, 0);
  95     for (link = 1; link < n_links; link++) {
  96         uint32_t weight = hash_2words(hash, link);
  97         if (weight > best_weight) {
  98             best_link = link;
  99             best_weight = weight;
 100         }
 101     }
 102     return best_link;
 103 }
 104
 105 /* Works for 'x' in the range [1,65536], which is all we need.  */
 106 static unsigned int
 107 round_up_pow2(unsigned int x)
 108 {
 109     x--;
 110     x |= x >> 1;
 111     x |= x >> 2;
 112     x |= x >> 4;
 113     x |= x >> 8;
 114     return x + 1;
 115 }
 116
 117 static uint16_t
 118 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
 119 {
 120     uint16_t link;
 121     int i;
 122
 123     if (modulo < n_links || modulo / 2 > n_links) {
 124         modulo = round_up_pow2(n_links);
 125     }
 126
 127     i = 0;
 128     do {
 129         link = hash_2words(hash, i++) % modulo;
 130     } while (link >= n_links);
 131
 132     return link;
 133 }
 134
 135 static uint16_t
 136 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
 137                     unsigned int n_links, unsigned int arg)
 138 {
 139     switch (algorithm) {
 140     case NX_MP_ALG_MODULO_N:
 141         return hash % n_links;
 142
 143     case NX_MP_ALG_HASH_THRESHOLD:
 144         if (n_links == 1) {
 145             return 0;
 146         }
 147         return hash / (UINT32_MAX / n_links + 1);
 148
 149     case NX_MP_ALG_HRW:
 150         return (n_links <= 64
 151                 ? algorithm_hrw(hash, n_links)
 152                 : algorithm_iter_hash(hash, n_links, 0));
 153
 154     case NX_MP_ALG_ITER_HASH:
 155         return algorithm_iter_hash(hash, n_links, arg);
 156     }
 157
 158     NOT_REACHED();
 159 }
 160 \f
 161 /* multipath_parse(). */
 162
 163 void
 164 multipath_parse(struct nx_action_multipath *mp, const char *s_)
 165 {
 166     char *s = xstrdup(s_);
 167     char *save_ptr = NULL;
 168     char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
 169     uint32_t header;
 170     int ofs, n_bits;
 171     int n_links;
 172
 173     fields = strtok_r(s, ", ", &save_ptr);
 174     basis = strtok_r(NULL, ", ", &save_ptr);
 175     algorithm = strtok_r(NULL, ", ", &save_ptr);
 176     n_links_str = strtok_r(NULL, ", ", &save_ptr);
 177     arg = strtok_r(NULL, ", ", &save_ptr);
 178     dst = strtok_r(NULL, ", ", &save_ptr);
 179     if (!dst) {
 180         ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
 181     }
 182
 183     memset(mp, 0, sizeof *mp);
 184     mp->type = htons(OFPAT_VENDOR);
 185     mp->len = htons(sizeof *mp);
 186     mp->vendor = htonl(NX_VENDOR_ID);
 187     mp->subtype = htons(NXAST_MULTIPATH);
 188     if (!strcasecmp(fields, "eth_src")) {
 189         mp->fields = htons(NX_HASH_FIELDS_ETH_SRC);
 190     } else if (!strcasecmp(fields, "symmetric_l4")) {
 191         mp->fields = htons(NX_HASH_FIELDS_SYMMETRIC_L4);
 192     } else {
 193         ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
 194     }
 195     mp->basis = htons(atoi(basis));
 196     if (!strcasecmp(algorithm, "modulo_n")) {
 197         mp->algorithm = htons(NX_MP_ALG_MODULO_N);
 198     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 199         mp->algorithm = htons(NX_MP_ALG_HASH_THRESHOLD);
 200     } else if (!strcasecmp(algorithm, "hrw")) {
 201         mp->algorithm = htons(NX_MP_ALG_HRW);
 202     } else if (!strcasecmp(algorithm, "iter_hash")) {
 203         mp->algorithm = htons(NX_MP_ALG_ITER_HASH);
 204     } else {
 205         ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
 206     }
 207     n_links = atoi(n_links_str);
 208     if (n_links < 1 || n_links > 65536) {
 209         ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
 210                   s_, n_links);
 211     }
 212     mp->max_link = htons(n_links - 1);
 213     mp->arg = htonl(atoi(arg));
 214
 215     nxm_parse_field_bits(dst, &header, &ofs, &n_bits);
 216     if (n_bits < 16 && n_links > (1u << n_bits)) {
 217         ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
 218                   "less than specified n_links %d",
 219                   s_, n_bits, 1u << n_bits, n_links);
 220     }
 221     mp->ofs_nbits = nxm_encode_ofs_nbits(ofs, n_bits);
 222     mp->dst = htonl(header);
 223
 224     free(s);
 225 }
 226
 227 void
 228 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
 229 {
 230     const char *fields, *algorithm;
 231
 232     uint16_t mp_fields    = ntohs(mp->fields);
 233     uint16_t mp_algorithm = ntohs(mp->algorithm);
 234
 235     fields = flow_hash_fields_to_str(mp_fields);
 236
 237     switch ((enum nx_mp_algorithm) mp_algorithm) {
 238     case NX_MP_ALG_MODULO_N:
 239         algorithm = "modulo_n";
 240         break;
 241     case NX_MP_ALG_HASH_THRESHOLD:
 242         algorithm = "hash_threshold";
 243         break;
 244     case NX_MP_ALG_HRW:
 245         algorithm = "hrw";
 246         break;
 247     case NX_MP_ALG_ITER_HASH:
 248         algorithm = "iter_hash";
 249         break;
 250     default:
 251         algorithm = "<unknown>";
 252     }
 253
 254     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
 255                   fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
 256                   ntohl(mp->arg));
 257     nxm_format_field_bits(s, ntohl(mp->dst), nxm_decode_ofs(mp->ofs_nbits),
 258                           nxm_decode_n_bits(mp->ofs_nbits));
 259     ds_put_char(s, ')');
 260 }