[mirror_ovs.git] / lib / multipath.c

/*
 * Copyright (c) 2010, 2011, 2012 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <config.h>

#include "multipath.h"
#include <arpa/inet.h>
#include <inttypes.h>
#include <sys/types.h>
#include <netinet/in.h>
#include "dynamic-string.h"
#include "nx-match.h"
#include "ofp-actions.h"
#include "ofp-errors.h"
#include "ofp-util.h"
#include "openflow/nicira-ext.h"
#include "packets.h"
#include "vlog.h"

VLOG_DEFINE_THIS_MODULE(multipath);

static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
\f
/* Converts 'nam' into 'mp'.  Returns 0 if successful, otherwise an
 * OFPERR_*. */
enum ofperr
multipath_from_openflow(const struct nx_action_multipath *nam,
                        struct ofpact_multipath *mp)
{
    uint32_t n_links = ntohs(nam->max_link) + 1;
    size_t min_n_bits = log_2_ceil(n_links);

    ofpact_init_MULTIPATH(mp);
    mp->fields = ntohs(nam->fields);
    mp->basis = ntohs(nam->basis);
    mp->algorithm = ntohs(nam->algorithm);
    mp->max_link = ntohs(nam->max_link);
    mp->arg = ntohl(nam->arg);
    mp->dst.field = mf_from_nxm_header(ntohl(nam->dst));
    mp->dst.ofs = nxm_decode_ofs(nam->ofs_nbits);
    mp->dst.n_bits = nxm_decode_n_bits(nam->ofs_nbits);

    if (!flow_hash_fields_valid(mp->fields)) {
        VLOG_WARN_RL(&rl, "unsupported fields %d", (int) mp->fields);
        return OFPERR_OFPBAC_BAD_ARGUMENT;
    } else if (mp->algorithm != NX_MP_ALG_MODULO_N
               && mp->algorithm != NX_MP_ALG_HASH_THRESHOLD
               && mp->algorithm != NX_MP_ALG_HRW
               && mp->algorithm != NX_MP_ALG_ITER_HASH) {
        VLOG_WARN_RL(&rl, "unsupported algorithm %d", (int) mp->algorithm);
        return OFPERR_OFPBAC_BAD_ARGUMENT;
    } else if (mp->dst.n_bits < min_n_bits) {
        VLOG_WARN_RL(&rl, "multipath action requires at least %zu bits for "
                     "%"PRIu32" links", min_n_bits, n_links);
        return OFPERR_OFPBAC_BAD_ARGUMENT;
    }

    return multipath_check(mp, NULL);
}

/* Checks that 'mp' is valid on flow.  Returns 0 if it is valid, otherwise an
 * OFPERR_*. */
enum ofperr
multipath_check(const struct ofpact_multipath *mp,
                const struct flow *flow)
{
    return mf_check_dst(&mp->dst, flow);
}

/* Converts 'mp' into an OpenFlow NXAST_MULTIPATH action, which it appends to
 * 'openflow'. */
void
multipath_to_nxast(const struct ofpact_multipath *mp, struct ofpbuf *openflow)
{
    struct nx_action_multipath *nam = ofputil_put_NXAST_MULTIPATH(openflow);

    nam->fields = htons(mp->fields);
    nam->basis = htons(mp->basis);
    nam->algorithm = htons(mp->algorithm);
    nam->max_link = htons(mp->max_link);
    nam->arg = htonl(mp->arg);
    nam->ofs_nbits = nxm_encode_ofs_nbits(mp->dst.ofs, mp->dst.n_bits);
    nam->dst = htonl(mp->dst.field->nxm_header);
}
\f
/* multipath_execute(). */

static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
                                    unsigned int n_links, unsigned int arg);

/* Executes 'mp' based on the current contents of 'flow', writing the results
 * back into 'flow'.  Sets fields in 'wc' that were used to calculate
 * the result. */
void
multipath_execute(const struct ofpact_multipath *mp, struct flow *flow,
                  struct flow_wildcards *wc)
{
    /* Calculate value to store. */
    uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
    uint16_t link = multipath_algorithm(hash, mp->algorithm,
                                        mp->max_link + 1, mp->arg);

    flow_mask_hash_fields(wc, mp->fields);
    nxm_reg_load(&mp->dst, link, flow);
}

static uint16_t
algorithm_hrw(uint32_t hash, unsigned int n_links)
{
    uint32_t best_weight;
    uint16_t best_link;
    unsigned int link;

    best_link = 0;
    best_weight = hash_2words(hash, 0);
    for (link = 1; link < n_links; link++) {
        uint32_t weight = hash_2words(hash, link);
        if (weight > best_weight) {
            best_link = link;
            best_weight = weight;
        }
    }
    return best_link;
}

/* Works for 'x' in the range [1,65536], which is all we need.  */
static unsigned int
round_up_pow2(unsigned int x)
{
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    return x + 1;
}

static uint16_t
algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
{
    uint16_t link;
    int i;

    if (modulo < n_links || modulo / 2 > n_links) {
        modulo = round_up_pow2(n_links);
    }

    i = 0;
    do {
        link = hash_2words(hash, i++) % modulo;
    } while (link >= n_links);

    return link;
}

static uint16_t
multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
                    unsigned int n_links, unsigned int arg)
{
    switch (algorithm) {
    case NX_MP_ALG_MODULO_N:
        return hash % n_links;

    case NX_MP_ALG_HASH_THRESHOLD:
        if (n_links == 1) {
            return 0;
        }
        return hash / (UINT32_MAX / n_links + 1);

    case NX_MP_ALG_HRW:
        return (n_links <= 64
                ? algorithm_hrw(hash, n_links)
                : algorithm_iter_hash(hash, n_links, 0));

    case NX_MP_ALG_ITER_HASH:
        return algorithm_iter_hash(hash, n_links, arg);
    }

    NOT_REACHED();
}
\f
/* Parses 's_' as a set of arguments to the "multipath" action and initializes
 * 'mp' accordingly.  ovs-ofctl(8) describes the format parsed.
 *
 * Prints an error on stderr and aborts the program if 's_' syntax is
 * invalid. */
void
multipath_parse(struct ofpact_multipath *mp, const char *s_)
{
    char *s = xstrdup(s_);
    char *save_ptr = NULL;
    char *fields, *basis, *algorithm, *n_links_str, *arg, *dst;
    int n_links;

    fields = strtok_r(s, ", ", &save_ptr);
    basis = strtok_r(NULL, ", ", &save_ptr);
    algorithm = strtok_r(NULL, ", ", &save_ptr);
    n_links_str = strtok_r(NULL, ", ", &save_ptr);
    arg = strtok_r(NULL, ", ", &save_ptr);
    dst = strtok_r(NULL, ", ", &save_ptr);
    if (!dst) {
        ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
    }

    ofpact_init_MULTIPATH(mp);
    if (!strcasecmp(fields, "eth_src")) {
        mp->fields = NX_HASH_FIELDS_ETH_SRC;
    } else if (!strcasecmp(fields, "symmetric_l4")) {
        mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
    } else {
        ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
    }
    mp->basis = atoi(basis);
    if (!strcasecmp(algorithm, "modulo_n")) {
        mp->algorithm = NX_MP_ALG_MODULO_N;
    } else if (!strcasecmp(algorithm, "hash_threshold")) {
        mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
    } else if (!strcasecmp(algorithm, "hrw")) {
        mp->algorithm = NX_MP_ALG_HRW;
    } else if (!strcasecmp(algorithm, "iter_hash")) {
        mp->algorithm = NX_MP_ALG_ITER_HASH;
    } else {
        ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
    }
    n_links = atoi(n_links_str);
    if (n_links < 1 || n_links > 65536) {
        ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
                  s_, n_links);
    }
    mp->max_link = n_links - 1;
    mp->arg = atoi(arg);

    mf_parse_subfield(&mp->dst, dst);
    if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
        ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
                  "less than specified n_links %d",
                  s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
    }

    free(s);
}

/* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
 * describes. */
void
multipath_format(const struct ofpact_multipath *mp, struct ds *s)
{
    const char *fields, *algorithm;

    fields = flow_hash_fields_to_str(mp->fields);

    switch (mp->algorithm) {
    case NX_MP_ALG_MODULO_N:
        algorithm = "modulo_n";
        break;
    case NX_MP_ALG_HASH_THRESHOLD:
        algorithm = "hash_threshold";
        break;
    case NX_MP_ALG_HRW:
        algorithm = "hrw";
        break;
    case NX_MP_ALG_ITER_HASH:
        algorithm = "iter_hash";
        break;
    default:
        algorithm = "<unknown>";
    }

    ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
                  fields, mp->basis, algorithm, mp->max_link + 1,
                  mp->arg);
    mf_format_subfield(&mp->dst, s);
    ds_put_char(s, ')');
}
Commit	Line	Data
53ddd40a	1	/*
e0edde6f	2	* Copyright (c) 2010, 2011, 2012 Nicira, Inc.
53ddd40a BP	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"
19f62195	20	#include <arpa/inet.h>
53ddd40a BP	21	#include <inttypes.h>
	22	#include <sys/types.h>
	23	#include <netinet/in.h>
	24	#include "dynamic-string.h"
	25	#include "nx-match.h"
f25d0cf3	26	#include "ofp-actions.h"
90bf1e07	27	#include "ofp-errors.h"
53ddd40a BP	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
f25d0cf3 BP	37	/* Converts 'nam' into 'mp'. Returns 0 if successful, otherwise an
f25d0cf3 BP	38	* OFPERR_. /
90bf1e07	39	enum ofperr
f25d0cf3 BP	40	multipath_from_openflow(const struct nx_action_multipath *nam,
f25d0cf3 BP	41	struct ofpact_multipath *mp)
53ddd40a	42	{
f25d0cf3	43	uint32_t n_links = ntohs(nam->max_link) + 1;
300c6946	44	size_t min_n_bits = log_2_ceil(n_links);
43edca57	45
f25d0cf3 BP	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) {
ce523f65 EJ	66	VLOG_WARN_RL(&rl, "multipath action requires at least %zu bits for "
ce523f65 EJ	67	"%"PRIu32" links", min_n_bits, n_links);
f25d0cf3	68	return OFPERR_OFPBAC_BAD_ARGUMENT;
53ddd40a BP	69	}
53ddd40a BP	70
f25d0cf3 BP	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);
53ddd40a BP	97	}
	98	\f
	99	/* multipath_execute(). */
	100
53ddd40a BP	101	static uint16_t multipath_algorithm(uint32_t hash, enum nx_mp_algorithm,
	102	unsigned int n_links, unsigned int arg);
	103
f25d0cf3	104	/* Executes 'mp' based on the current contents of 'flow', writing the results
bcd2633a JP	105	* back into 'flow'. Sets fields in 'wc' that were used to calculate
bcd2633a JP	106	* the result. */
53ddd40a	107	void
bcd2633a JP	108	multipath_execute(const struct ofpact_multipath mp, struct flow flow,
bcd2633a JP	109	struct flow_wildcards *wc)
53ddd40a BP	110	{
53ddd40a BP	111	/* Calculate value to store. */
f25d0cf3 BP	112	uint32_t hash = flow_hash_fields(flow, mp->fields, mp->basis);
	113	uint16_t link = multipath_algorithm(hash, mp->algorithm,
	114	mp->max_link + 1, mp->arg);
	115
bcd2633a	116	flow_mask_hash_fields(wc, mp->fields);
f25d0cf3	117	nxm_reg_load(&mp->dst, link, flow);
53ddd40a BP	118	}
53ddd40a BP	119
53ddd40a BP	120	static uint16_t
	121	algorithm_hrw(uint32_t hash, unsigned int n_links)
	122	{
	123	uint32_t best_weight;
	124	uint16_t best_link;
	125	unsigned int link;
	126
	127	best_link = 0;
	128	best_weight = hash_2words(hash, 0);
	129	for (link = 1; link < n_links; link++) {
	130	uint32_t weight = hash_2words(hash, link);
	131	if (weight > best_weight) {
	132	best_link = link;
	133	best_weight = weight;
	134	}
	135	}
	136	return best_link;
	137	}
	138
	139	/* Works for 'x' in the range [1,65536], which is all we need. */
	140	static unsigned int
	141	round_up_pow2(unsigned int x)
	142	{
	143	x--;
	144	x \|= x >> 1;
	145	x \|= x >> 2;
	146	x \|= x >> 4;
	147	x \|= x >> 8;
	148	return x + 1;
	149	}
	150
	151	static uint16_t
	152	algorithm_iter_hash(uint32_t hash, unsigned int n_links, unsigned int modulo)
	153	{
	154	uint16_t link;
	155	int i;
	156
	157	if (modulo < n_links \|\| modulo / 2 > n_links) {
	158	modulo = round_up_pow2(n_links);
	159	}
	160
	161	i = 0;
	162	do {
	163	link = hash_2words(hash, i++) % modulo;
	164	} while (link >= n_links);
	165
	166	return link;
	167	}
	168
	169	static uint16_t
	170	multipath_algorithm(uint32_t hash, enum nx_mp_algorithm algorithm,
	171	unsigned int n_links, unsigned int arg)
	172	{
	173	switch (algorithm) {
	174	case NX_MP_ALG_MODULO_N:
	175	return hash % n_links;
	176
	177	case NX_MP_ALG_HASH_THRESHOLD:
d7bf2b00 BP	178	if (n_links == 1) {
	179	return 0;
	180	}
	181	return hash / (UINT32_MAX / n_links + 1);
53ddd40a BP	182
	183	case NX_MP_ALG_HRW:
	184	return (n_links <= 64
	185	? algorithm_hrw(hash, n_links)
	186	: algorithm_iter_hash(hash, n_links, 0));
	187
	188	case NX_MP_ALG_ITER_HASH:
	189	return algorithm_iter_hash(hash, n_links, arg);
	190	}
	191
	192	NOT_REACHED();
	193	}
	194	\f
f25d0cf3 BP	195	/* Parses 's_' as a set of arguments to the "multipath" action and initializes
	196	* 'mp' accordingly. ovs-ofctl(8) describes the format parsed.
	197	*
	198	* Prints an error on stderr and aborts the program if 's_' syntax is
	199	* invalid. */
53ddd40a	200	void
f25d0cf3	201	multipath_parse(struct ofpact_multipath mp, const char s_)
53ddd40a BP	202	{
	203	char *s = xstrdup(s_);
	204	char *save_ptr = NULL;
f25d0cf3	205	char fields, basis, algorithm, n_links_str, arg, dst;
770f1f66	206	int n_links;
53ddd40a BP	207
	208	fields = strtok_r(s, ", ", &save_ptr);
	209	basis = strtok_r(NULL, ", ", &save_ptr);
	210	algorithm = strtok_r(NULL, ", ", &save_ptr);
770f1f66	211	n_links_str = strtok_r(NULL, ", ", &save_ptr);
53ddd40a	212	arg = strtok_r(NULL, ", ", &save_ptr);
f25d0cf3 BP	213	dst = strtok_r(NULL, ", ", &save_ptr);
f25d0cf3 BP	214	if (!dst) {
770f1f66	215	ovs_fatal(0, "%s: not enough arguments to multipath action", s_);
53ddd40a BP	216	}
53ddd40a BP	217
f25d0cf3	218	ofpact_init_MULTIPATH(mp);
53ddd40a	219	if (!strcasecmp(fields, "eth_src")) {
f25d0cf3	220	mp->fields = NX_HASH_FIELDS_ETH_SRC;
53ddd40a	221	} else if (!strcasecmp(fields, "symmetric_l4")) {
f25d0cf3	222	mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
53ddd40a	223	} else {
770f1f66	224	ovs_fatal(0, "%s: unknown fields `%s'", s_, fields);
53ddd40a	225	}
f25d0cf3	226	mp->basis = atoi(basis);
53ddd40a	227	if (!strcasecmp(algorithm, "modulo_n")) {
f25d0cf3	228	mp->algorithm = NX_MP_ALG_MODULO_N;
53ddd40a	229	} else if (!strcasecmp(algorithm, "hash_threshold")) {
f25d0cf3	230	mp->algorithm = NX_MP_ALG_HASH_THRESHOLD;
53ddd40a	231	} else if (!strcasecmp(algorithm, "hrw")) {
f25d0cf3	232	mp->algorithm = NX_MP_ALG_HRW;
53ddd40a	233	} else if (!strcasecmp(algorithm, "iter_hash")) {
f25d0cf3	234	mp->algorithm = NX_MP_ALG_ITER_HASH;
53ddd40a	235	} else {
770f1f66	236	ovs_fatal(0, "%s: unknown algorithm `%s'", s_, algorithm);
53ddd40a	237	}
770f1f66 BP	238	n_links = atoi(n_links_str);
	239	if (n_links < 1 \|\| n_links > 65536) {
	240	ovs_fatal(0, "%s: n_links %d is not in valid range 1 to 65536",
	241	s_, n_links);
	242	}
f25d0cf3 BP	243	mp->max_link = n_links - 1;
f25d0cf3 BP	244	mp->arg = atoi(arg);
53ddd40a	245
f25d0cf3 BP	246	mf_parse_subfield(&mp->dst, dst);
f25d0cf3 BP	247	if (mp->dst.n_bits < 16 && n_links > (1u << mp->dst.n_bits)) {
770f1f66 BP	248	ovs_fatal(0, "%s: %d-bit destination field has %u possible values, "
770f1f66 BP	249	"less than specified n_links %d",
f25d0cf3	250	s_, mp->dst.n_bits, 1u << mp->dst.n_bits, n_links);
770f1f66	251	}
53ddd40a BP	252
	253	free(s);
	254	}
	255
f25d0cf3 BP	256	/* Appends a description of 'mp' to 's', in the format that ovs-ofctl(8)
f25d0cf3 BP	257	* describes. */
53ddd40a	258	void
f25d0cf3	259	multipath_format(const struct ofpact_multipath mp, struct ds s)
53ddd40a BP	260	{
	261	const char fields, algorithm;
	262
f25d0cf3	263	fields = flow_hash_fields_to_str(mp->fields);
53ddd40a	264
f25d0cf3	265	switch (mp->algorithm) {
53ddd40a BP	266	case NX_MP_ALG_MODULO_N:
	267	algorithm = "modulo_n";
	268	break;
	269	case NX_MP_ALG_HASH_THRESHOLD:
	270	algorithm = "hash_threshold";
	271	break;
	272	case NX_MP_ALG_HRW:
	273	algorithm = "hrw";
	274	break;
	275	case NX_MP_ALG_ITER_HASH:
	276	algorithm = "iter_hash";
	277	break;
	278	default:
	279	algorithm = "<unknown>";
	280	}
	281
	282	ds_put_format(s, "multipath(%s,%"PRIu16",%s,%d,%"PRIu16",",
f25d0cf3 BP	283	fields, mp->basis, algorithm, mp->max_link + 1,
	284	mp->arg);
	285	mf_format_subfield(&mp->dst, s);
53ddd40a BP	286	ds_put_char(s, ')');
53ddd40a BP	287	}