lib/multipath.c

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