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)
  38 {
  39     uint32_t dst = ntohl(mp->dst);
  40     int ofs = nxm_decode_ofs(mp->ofs_nbits);
  41     int n_bits = nxm_decode_n_bits(mp->ofs_nbits);
  42
  43     if (mp->fields != htons(NX_MP_FIELDS_ETH_SRC)
  44         && mp->fields != htons(NX_MP_FIELDS_SYMMETRIC_L4)) {
  45         VLOG_WARN_RL(&rl, "unsupported fields %"PRIu16, ntohs(mp->fields));
  46     } else if (mp->algorithm != htons(NX_MP_ALG_MODULO_N)
  47                && mp->algorithm != htons(NX_MP_ALG_HASH_THRESHOLD)
  48                && mp->algorithm != htons(NX_MP_ALG_HRW)
  49                && mp->algorithm != htons(NX_MP_ALG_ITER_HASH)) {
  50         VLOG_WARN_RL(&rl, "unsupported algorithm %"PRIu16,
  51                      ntohs(mp->algorithm));
  52     } else if (!NXM_IS_NX_REG(dst) || NXM_NX_REG_IDX(dst) >= FLOW_N_REGS) {
  53         VLOG_WARN_RL(&rl, "unsupported destination field %#"PRIx32, dst);
  54     } else if (ofs + n_bits > nxm_field_bits(dst)) {
  55         VLOG_WARN_RL(&rl, "destination overflows output field");
  56     } else if (n_bits < 16 && ntohs(mp->max_link) > (1u << n_bits)) {
  57         VLOG_WARN_RL(&rl, "max_link overflows output field");
  58     } else {
  59         return 0;
  60     }
  61
  62     return ofp_mkerr(OFPET_BAD_ACTION, OFPBAC_BAD_ARGUMENT);
  63 }
  64 \f
  65 /* multipath_execute(). */
  66
  67 static uint32_t multipath_hash(const struct flow *, enum nx_mp_fields,
  68                                uint16_t basis);
  69 static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
  70                                     unsigned int n_links, unsigned int arg);
  71
  72 void
  73 multipath_execute(const struct nx_action_multipath *mp, struct flow *flow)
  74 {
  75     /* Calculate value to store. */
  76     uint32_t hash = multipath_hash(flow, ntohs(mp->fields), ntohs(mp->basis));
  77     uint16_t link = multipath_algorithm(hash, ntohs(mp->algorithm),
  78                                         ntohs(mp->max_link) + 1,
  79                                         ntohl(mp->arg));
  80
  81     /* Store it. */
  82     uint32_t *reg = &flow->regs[NXM_NX_REG_IDX(ntohl(mp->dst))];
  83     int ofs = nxm_decode_ofs(mp->ofs_nbits);
  84     int n_bits = nxm_decode_n_bits(mp->ofs_nbits);
  85     uint32_t mask = n_bits == 32 ? UINT32_MAX : (UINT32_C(1) << n_bits) - 1;
  86     *reg = (*reg & ~(mask << ofs)) | (link << ofs);
  87 }
  88
  89 static uint32_t
  90 hash_symmetric_l4(const struct flow *flow, uint16_t basis)
  91 {
  92     struct {
  93         ovs_be32 ip_addr;
  94         ovs_be16 eth_type;
  95         ovs_be16 vlan_tci;
  96         ovs_be16 tp_addr;
  97         uint8_t eth_addr[ETH_ADDR_LEN];
  98         uint8_t ip_proto;
  99     } fields;
 100
 101     int i;
 102
 103     memset(&fields, 0, sizeof fields);
 104     for (i = 0; i < ETH_ADDR_LEN; i++) {
 105         fields.eth_addr[i] = flow->dl_src[i] ^ flow->dl_dst[i];
 106     }
 107     fields.vlan_tci = flow->vlan_tci & htons(VLAN_VID_MASK);
 108     fields.eth_type = flow->dl_type;
 109     if (fields.eth_type == htons(ETH_TYPE_IP)) {
 110         fields.ip_addr = flow->nw_src ^ flow->nw_dst;
 111         fields.ip_proto = flow->nw_proto;
 112         if (fields.ip_proto == IP_TYPE_TCP || fields.ip_proto == IP_TYPE_UDP) {
 113             fields.tp_addr = flow->tp_src ^ flow->tp_dst;
 114         } else {
 115             fields.tp_addr = htons(0);
 116         }
 117     } else {
 118         fields.ip_addr = htonl(0);
 119         fields.ip_proto = 0;
 120         fields.tp_addr = htons(0);
 121     }
 122     return hash_bytes(&fields, sizeof fields, basis);
 123 }
 124
 125 static uint32_t
 126 multipath_hash(const struct flow *flow, enum nx_mp_fields fields,
 127                uint16_t basis)
 128 {
 129     switch (fields) {
 130     case NX_MP_FIELDS_ETH_SRC:
 131         return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
 132
 133     case NX_MP_FIELDS_SYMMETRIC_L4:
 134         return hash_symmetric_l4(flow, basis);
 135     }
 136
 137     NOT_REACHED();
 138 }
 139
 140 static uint16_t
 141 algorithm_hrw(uint32_t hash, unsigned int n_links)
 142 {
 143     uint32_t best_weight;
 144     uint16_t best_link;
 145     unsigned int link;
 146
 147     best_link = 0;
 148     best_weight = hash_2words(hash, 0);
 149     for (link = 1; link < n_links; link++) {
 150         uint32_t weight = hash_2words(hash, link);
 151         if (weight > best_weight) {
 152             best_link = link;
 153             best_weight = weight;
 154         }
 155     }
 156     return best_link;
 157 }
 158
 159 /* Works for 'x' in the range [1,65536], which is all we need.  */
 160 static unsigned int
 161 round_up_pow2(unsigned int x)
 162 {
 163     x--;
 164     x |= x >> 1;
 165     x |= x >> 2;
 166     x |= x >> 4;
 167     x |= x >> 8;
 168     return x + 1;
 169 }
 170
 171 static uint16_t
 172 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
 173 {
 174     uint16_t link;
 175     int i;
 176
 177     if (modulo < n_links || modulo / 2 > n_links) {
 178         modulo = round_up_pow2(n_links);
 179     }
 180
 181     i = 0;
 182     do {
 183         link = hash_2words(hash, i++) % modulo;
 184     } while (link >= n_links);
 185
 186     return link;
 187 }
 188
 189 static uint16_t
 190 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
 191                     unsigned int n_links, unsigned int arg)
 192 {
 193     switch (algorithm) {
 194     case NX_MP_ALG_MODULO_N:
 195         return hash % n_links;
 196
 197     case NX_MP_ALG_HASH_THRESHOLD:
 198         if (n_links == 1) {
 199             return 0;
 200         }
 201         return hash / (UINT32_MAX / n_links + 1);
 202
 203     case NX_MP_ALG_HRW:
 204         return (n_links <= 64
 205                 ? algorithm_hrw(hash, n_links)
 206                 : algorithm_iter_hash(hash, n_links, 0));
 207
 208     case NX_MP_ALG_ITER_HASH:
 209         return algorithm_iter_hash(hash, n_links, arg);
 210     }
 211
 212     NOT_REACHED();
 213 }
 214 \f
 215 /* multipath_parse(). */
 216
 217 void
 218 multipath_parse(struct nx_action_multipath *mp, const char *s_)
 219 {
 220     char *s = xstrdup(s_);
 221     char *save_ptr = NULL;
 222     char *fields, *basis, *algorithm, *n_links, *arg, *dst;
 223     uint32_t header;
 224     int ofs, n_bits;
 225
 226     fields = strtok_r(s, ", ", &save_ptr);
 227     basis = strtok_r(NULL, ", ", &save_ptr);
 228     algorithm = strtok_r(NULL, ", ", &save_ptr);
 229     n_links = strtok_r(NULL, ", ", &save_ptr);
 230     arg = strtok_r(NULL, ", ", &save_ptr);
 231     dst = strtok_r(NULL, ", ", &save_ptr);
 232     if (!dst) {
 233         ovs_fatal(0, "%s: not enough arguments to multipath action", s);
 234     }
 235
 236     memset(mp, 0, sizeof *mp);
 237     mp->type = htons(OFPAT_VENDOR);
 238     mp->len = htons(sizeof *mp);
 239     mp->vendor = htonl(NX_VENDOR_ID);
 240     mp->subtype = htons(NXAST_MULTIPATH);
 241     if (!strcasecmp(fields, "eth_src")) {
 242         mp->fields = htons(NX_MP_FIELDS_ETH_SRC);
 243     } else if (!strcasecmp(fields, "symmetric_l4")) {
 244         mp->fields = htons(NX_MP_FIELDS_SYMMETRIC_L4);
 245     } else {
 246         ovs_fatal(0, "%s: unknown fields `%s'", s, fields);
 247     }
 248     mp->basis = htons(atoi(basis));
 249     if (!strcasecmp(algorithm, "modulo_n")) {
 250         mp->algorithm = htons(NX_MP_ALG_MODULO_N);
 251     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 252         mp->algorithm = htons(NX_MP_ALG_HASH_THRESHOLD);
 253     } else if (!strcasecmp(algorithm, "hrw")) {
 254         mp->algorithm = htons(NX_MP_ALG_HRW);
 255     } else if (!strcasecmp(algorithm, "iter_hash")) {
 256         mp->algorithm = htons(NX_MP_ALG_ITER_HASH);
 257     } else {
 258         ovs_fatal(0, "%s: unknown algorithm `%s'", s, algorithm);
 259     }
 260     mp->max_link = htons(atoi(n_links) - 1);
 261     mp->arg = htonl(atoi(arg));
 262
 263     nxm_parse_field_bits(dst, &header, &ofs, &n_bits);
 264     mp->ofs_nbits = nxm_encode_ofs_nbits(ofs, n_bits);
 265     mp->dst = htonl(header);
 266
 267     free(s);
 268 }
 269
 270 void
 271 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
 272 {
 273     const char *fields, *algorithm;
 274
 275     uint16_t mp_fields    = ntohs(mp->fields);
 276     uint16_t mp_algorithm = ntohs(mp->algorithm);
 277
 278     switch ((enum nx_mp_fields) mp_fields) {
 279     case NX_MP_FIELDS_ETH_SRC:
 280         fields = "eth_src";
 281         break;
 282     case NX_MP_FIELDS_SYMMETRIC_L4:
 283         fields = "symmetric_l4";
 284         break;
 285     default:
 286         fields = "<unknown>";
 287     }
 288
 289     switch ((enum nx_mp_algorithm) mp_algorithm) {
 290     case NX_MP_ALG_MODULO_N:
 291         algorithm = "modulo_n";
 292         break;
 293     case NX_MP_ALG_HASH_THRESHOLD:
 294         algorithm = "hash_threshold";
 295         break;
 296     case NX_MP_ALG_HRW:
 297         algorithm = "hrw";
 298         break;
 299     case NX_MP_ALG_ITER_HASH:
 300         algorithm = "iter_hash";
 301         break;
 302     default:
 303         algorithm = "<unknown>";
 304     }
 305
 306     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
 307                   fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
 308                   ntohl(mp->arg));
 309     nxm_format_field_bits(s, ntohl(mp->dst), nxm_decode_ofs(mp->ofs_nbits),
 310                           nxm_decode_n_bits(mp->ofs_nbits));
 311     ds_put_char(s, ')');
 312 }