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     memset(&fields, 0, sizeof fields);
 103     for (i = 0; i < ETH_ADDR_LEN; i++) {
 104         fields.eth_addr[i] = flow->dl_src[i] ^ flow->dl_dst[i];
 105     }
 106     fields.vlan_tci = flow->vlan_tci & htons(VLAN_VID_MASK);
 107     fields.eth_type = flow->dl_type;
 108     if (fields.eth_type == htons(ETH_TYPE_IP)) {
 109         fields.ip_addr = flow->nw_src ^ flow->nw_dst;
 110         fields.ip_proto = flow->nw_proto;
 111         if (fields.ip_proto == IP_TYPE_TCP || fields.ip_proto == IP_TYPE_UDP) {
 112             fields.tp_addr = flow->tp_src ^ flow->tp_dst;
 113         } else {
 114             fields.tp_addr = htons(0);
 115         }
 116     } else {
 117         fields.ip_addr = htonl(0);
 118         fields.ip_proto = 0;
 119         fields.tp_addr = htons(0);
 120     }
 121     return hash_bytes(&fields, sizeof fields, basis);
 122 }
 123
 124 static uint32_t
 125 multipath_hash(const struct flow *flow, enum nx_mp_fields fields,
 126                uint16_t basis)
 127 {
 128     switch (fields) {
 129     case NX_MP_FIELDS_ETH_SRC:
 130         return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
 131
 132     case NX_MP_FIELDS_SYMMETRIC_L4:
 133         return hash_symmetric_l4(flow, basis);
 134     }
 135
 136     NOT_REACHED();
 137 }
 138
 139 static uint16_t
 140 algorithm_hrw(uint32_t hash, unsigned int n_links)
 141 {
 142     uint32_t best_weight;
 143     uint16_t best_link;
 144     unsigned int link;
 145
 146     best_link = 0;
 147     best_weight = hash_2words(hash, 0);
 148     for (link = 1; link < n_links; link++) {
 149         uint32_t weight = hash_2words(hash, link);
 150         if (weight > best_weight) {
 151             best_link = link;
 152             best_weight = weight;
 153         }
 154     }
 155     return best_link;
 156 }
 157
 158 /* Works for 'x' in the range [1,65536], which is all we need.  */
 159 static unsigned int
 160 round_up_pow2(unsigned int x)
 161 {
 162     x--;
 163     x |= x >> 1;
 164     x |= x >> 2;
 165     x |= x >> 4;
 166     x |= x >> 8;
 167     return x + 1;
 168 }
 169
 170 static uint16_t
 171 algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
 172 {
 173     uint16_t link;
 174     int i;
 175
 176     if (modulo < n_links || modulo / 2 > n_links) {
 177         modulo = round_up_pow2(n_links);
 178     }
 179
 180     i = 0;
 181     do {
 182         link = hash_2words(hash, i++) % modulo;
 183     } while (link >= n_links);
 184
 185     return link;
 186 }
 187
 188 static uint16_t
 189 multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
 190                     unsigned int n_links, unsigned int arg)
 191 {
 192     switch (algorithm) {
 193     case NX_MP_ALG_MODULO_N:
 194         return hash % n_links;
 195
 196     case NX_MP_ALG_HASH_THRESHOLD:
 197         return hash / (UINT32_MAX / n_links);
 198
 199     case NX_MP_ALG_HRW:
 200         return (n_links <= 64
 201                 ? algorithm_hrw(hash, n_links)
 202                 : algorithm_iter_hash(hash, n_links, 0));
 203
 204     case NX_MP_ALG_ITER_HASH:
 205         return algorithm_iter_hash(hash, n_links, arg);
 206     }
 207
 208     NOT_REACHED();
 209 }
 210 \f
 211 /* multipath_parse(). */
 212
 213 void
 214 multipath_parse(struct nx_action_multipath *mp, const char *s_)
 215 {
 216     char *s = xstrdup(s_);
 217     char *save_ptr = NULL;
 218     char *fields, *basis, *algorithm, *n_links, *arg, *dst;
 219     uint32_t header;
 220     int ofs, n_bits;
 221
 222     fields = strtok_r(s, ", ", &save_ptr);
 223     basis = strtok_r(NULL, ", ", &save_ptr);
 224     algorithm = strtok_r(NULL, ", ", &save_ptr);
 225     n_links = strtok_r(NULL, ", ", &save_ptr);
 226     arg = strtok_r(NULL, ", ", &save_ptr);
 227     dst = strtok_r(NULL, ", ", &save_ptr);
 228     if (!dst) {
 229         ovs_fatal(0, "%s: not enough arguments to multipath action", s);
 230     }
 231
 232     memset(mp, 0, sizeof *mp);
 233     mp->type = htons(OFPAT_VENDOR);
 234     mp->len = htons(sizeof *mp);
 235     mp->vendor = htonl(NX_VENDOR_ID);
 236     mp->subtype = htons(NXAST_MULTIPATH);
 237     if (!strcasecmp(fields, "eth_src")) {
 238         mp->fields = htons(NX_MP_FIELDS_ETH_SRC);
 239     } else if (!strcasecmp(fields, "symmetric_l4")) {
 240         mp->fields = htons(NX_MP_FIELDS_SYMMETRIC_L4);
 241     } else {
 242         ovs_fatal(0, "%s: unknown fields `%s'", s, fields);
 243     }
 244     mp->basis = htons(atoi(basis));
 245     if (!strcasecmp(algorithm, "modulo_n")) {
 246         mp->algorithm = htons(NX_MP_ALG_MODULO_N);
 247     } else if (!strcasecmp(algorithm, "hash_threshold")) {
 248         mp->algorithm = htons(NX_MP_ALG_HASH_THRESHOLD);
 249     } else if (!strcasecmp(algorithm, "hrw")) {
 250         mp->algorithm = htons(NX_MP_ALG_HRW);
 251     } else if (!strcasecmp(algorithm, "iter_hash")) {
 252         mp->algorithm = htons(NX_MP_ALG_ITER_HASH);
 253     } else {
 254         ovs_fatal(0, "%s: unknown algorithm `%s'", s, algorithm);
 255     }
 256     mp->max_link = htons(atoi(n_links) - 1);
 257     mp->arg = htonl(atoi(arg));
 258
 259     nxm_parse_field_bits(dst, &header, &ofs, &n_bits);
 260     mp->ofs_nbits = nxm_encode_ofs_nbits(ofs, n_bits);
 261     mp->dst = htonl(header);
 262
 263     free(s);
 264 }
 265
 266 void
 267 multipath_format(const struct nx_action_multipath *mp, struct ds *s)
 268 {
 269     const char *fields, *algorithm;
 270
 271     switch ((enum nx_mp_fields) ntohs(mp->fields)) {
 272     case NX_MP_FIELDS_ETH_SRC:
 273         fields = "eth_src";
 274         break;
 275     case NX_MP_FIELDS_SYMMETRIC_L4:
 276         fields = "symmetric_l4";
 277         break;
 278     default:
 279         fields = "<unknown>";
 280     }
 281
 282     switch ((enum nx_mp_algorithm) ntohs(mp->algorithm)) {
 283     case NX_MP_ALG_MODULO_N:
 284         algorithm = "modulo_n";
 285         break;
 286     case NX_MP_ALG_HASH_THRESHOLD:
 287         algorithm = "hash_threshold";
 288         break;
 289     case NX_MP_ALG_HRW:
 290         algorithm = "hrw";
 291         break;
 292     case NX_MP_ALG_ITER_HASH:
 293         algorithm = "iter_hash";
 294         break;
 295     default:
 296         algorithm = "<unknown>";
 297     }
 298
 299     ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
 300                   fields, ntohs(mp->basis), algorithm, ntohs(mp->max_link) + 1,
 301                   ntohl(mp->arg));
 302     nxm_format_field_bits(s, ntohl(mp->dst), nxm_decode_ofs(mp->ofs_nbits),
 303                           nxm_decode_n_bits(mp->ofs_nbits));
 304     ds_put_char(s, ')');
 305 }