[GitHub/mt8127/android_kernel_alcatel_ttab.git] / net / ipv4 / multipath_wrandom.c

/*
 *              Weighted random policy for multipath.
 *
 *
 * Version:	$Id: multipath_wrandom.c,v 1.1.2.3 2004/09/22 07:51:40 elueck Exp $
 *
 * Authors:	Einar Lueck <elueck@de.ibm.com><lkml@einar-lueck.de>
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
 */

#include <asm/system.h>
#include <asm/uaccess.h>
#include <linux/types.h>
#include <linux/sched.h>
#include <linux/errno.h>
#include <linux/timer.h>
#include <linux/mm.h>
#include <linux/kernel.h>
#include <linux/fcntl.h>
#include <linux/stat.h>
#include <linux/socket.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/inetdevice.h>
#include <linux/igmp.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/module.h>
#include <linux/mroute.h>
#include <linux/init.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <linux/skbuff.h>
#include <net/sock.h>
#include <net/icmp.h>
#include <net/udp.h>
#include <net/raw.h>
#include <linux/notifier.h>
#include <linux/if_arp.h>
#include <linux/netfilter_ipv4.h>
#include <net/ipip.h>
#include <net/checksum.h>
#include <net/ip_fib.h>
#include <net/ip_mp_alg.h>

#define MULTIPATH_STATE_SIZE 15

struct multipath_candidate {
	struct multipath_candidate	*next;
	int				power;
	struct rtable			*rt;
};

struct multipath_dest {
	struct list_head	list;

	const struct fib_nh	*nh_info;
	__be32			netmask;
	__be32			network;
	unsigned char		prefixlen;

	struct rcu_head		rcu;
};

struct multipath_bucket {
	struct list_head	head;
	spinlock_t		lock;
};

struct multipath_route {
	struct list_head	list;

	int			oif;
	__be32			gw;
	struct list_head	dests;

	struct rcu_head		rcu;
};

/* state: primarily weight per route information */
static struct multipath_bucket state[MULTIPATH_STATE_SIZE];

/* interface to random number generation */
static unsigned int RANDOM_SEED = 93186752;

static inline unsigned int random(unsigned int ubound)
{
	static unsigned int a = 1588635695,
		q = 2,
		r = 1117695901;
	RANDOM_SEED = a*(RANDOM_SEED % q) - r*(RANDOM_SEED / q);
	return RANDOM_SEED % ubound;
}

static unsigned char __multipath_lookup_weight(const struct flowi *fl,
					       const struct rtable *rt)
{
	const int state_idx = rt->idev->dev->ifindex % MULTIPATH_STATE_SIZE;
	struct multipath_route *r;
	struct multipath_route *target_route = NULL;
	struct multipath_dest *d;
	int weight = 1;

	/* lookup the weight information for a certain route */
	rcu_read_lock();

	/* find state entry for gateway or add one if necessary */
	list_for_each_entry_rcu(r, &state[state_idx].head, list) {
		if (r->gw == rt->rt_gateway &&
		    r->oif == rt->idev->dev->ifindex) {
			target_route = r;
			break;
		}
	}

	if (!target_route) {
		/* this should not happen... but we are prepared */
		printk( KERN_CRIT"%s: missing state for gateway: %u and " \
			"device %d\n", __FUNCTION__, rt->rt_gateway,
			rt->idev->dev->ifindex);
		goto out;
	}

	/* find state entry for destination */
	list_for_each_entry_rcu(d, &target_route->dests, list) {
		__be32 targetnetwork = fl->fl4_dst &
			inet_make_mask(d->prefixlen);

		if ((targetnetwork & d->netmask) == d->network) {
			weight = d->nh_info->nh_weight;
			goto out;
		}
	}

out:
	rcu_read_unlock();
	return weight;
}

static void wrandom_init_state(void)
{
	int i;

	for (i = 0; i < MULTIPATH_STATE_SIZE; ++i) {
		INIT_LIST_HEAD(&state[i].head);
		spin_lock_init(&state[i].lock);
	}
}

static void wrandom_select_route(const struct flowi *flp,
				 struct rtable *first,
				 struct rtable **rp)
{
	struct rtable *rt;
	struct rtable *decision;
	struct multipath_candidate *first_mpc = NULL;
	struct multipath_candidate *mpc, *last_mpc = NULL;
	int power = 0;
	int last_power;
	int selector;
	const size_t size_mpc = sizeof(struct multipath_candidate);

	/* collect all candidates and identify their weights */
	for (rt = rcu_dereference(first); rt;
	     rt = rcu_dereference(rt->u.rt_next)) {
		if ((rt->u.dst.flags & DST_BALANCED) != 0 &&
		    multipath_comparekeys(&rt->fl, flp)) {
			struct multipath_candidate* mpc =
				(struct multipath_candidate*)
				kmalloc(size_mpc, GFP_ATOMIC);

			if (!mpc)
				return;

			power += __multipath_lookup_weight(flp, rt) * 10000;

			mpc->power = power;
			mpc->rt = rt;
			mpc->next = NULL;

			if (!first_mpc)
				first_mpc = mpc;
			else
				last_mpc->next = mpc;

			last_mpc = mpc;
		}
	}

	/* choose a weighted random candidate */
	decision = first;
	selector = random(power);
	last_power = 0;

	/* select candidate, adjust GC data and cleanup local state */
	decision = first;
	last_mpc = NULL;
	for (mpc = first_mpc; mpc; mpc = mpc->next) {
		mpc->rt->u.dst.lastuse = jiffies;
		if (last_power <= selector && selector < mpc->power)
			decision = mpc->rt;

		last_power = mpc->power;
		kfree(last_mpc);
		last_mpc = mpc;
	}

	/* concurrent __multipath_flush may lead to !last_mpc */
	kfree(last_mpc);

	decision->u.dst.__use++;
	*rp = decision;
}

static void wrandom_set_nhinfo(__be32 network,
			       __be32 netmask,
			       unsigned char prefixlen,
			       const struct fib_nh *nh)
{
	const int state_idx = nh->nh_oif % MULTIPATH_STATE_SIZE;
	struct multipath_route *r, *target_route = NULL;
	struct multipath_dest *d, *target_dest = NULL;

	/* store the weight information for a certain route */
	spin_lock_bh(&state[state_idx].lock);

	/* find state entry for gateway or add one if necessary */
	list_for_each_entry_rcu(r, &state[state_idx].head, list) {
		if (r->gw == nh->nh_gw && r->oif == nh->nh_oif) {
			target_route = r;
			break;
		}
	}

	if (!target_route) {
		const size_t size_rt = sizeof(struct multipath_route);
		target_route = (struct multipath_route *)
			kmalloc(size_rt, GFP_ATOMIC);

		target_route->gw = nh->nh_gw;
		target_route->oif = nh->nh_oif;
		memset(&target_route->rcu, 0, sizeof(struct rcu_head));
		INIT_LIST_HEAD(&target_route->dests);

		list_add_rcu(&target_route->list, &state[state_idx].head);
	}

	/* find state entry for destination or add one if necessary */
	list_for_each_entry_rcu(d, &target_route->dests, list) {
		if (d->nh_info == nh) {
			target_dest = d;
			break;
		}
	}

	if (!target_dest) {
		const size_t size_dst = sizeof(struct multipath_dest);
		target_dest = (struct multipath_dest*)
			kmalloc(size_dst, GFP_ATOMIC);

		target_dest->nh_info = nh;
		target_dest->network = network;
		target_dest->netmask = netmask;
		target_dest->prefixlen = prefixlen;
		memset(&target_dest->rcu, 0, sizeof(struct rcu_head));

		list_add_rcu(&target_dest->list, &target_route->dests);
	}
	/* else: we already stored this info for another destination =>
	 * we are finished
	 */

	spin_unlock_bh(&state[state_idx].lock);
}

static void __multipath_free(struct rcu_head *head)
{
	struct multipath_route *rt = container_of(head, struct multipath_route,
						  rcu);
	kfree(rt);
}

static void __multipath_free_dst(struct rcu_head *head)
{
	struct multipath_dest *dst = container_of(head,
						  struct multipath_dest,
						  rcu);
	kfree(dst);
}

static void wrandom_flush(void)
{
	int i;

	/* defere delete to all entries */
	for (i = 0; i < MULTIPATH_STATE_SIZE; ++i) {
		struct multipath_route *r;

		spin_lock_bh(&state[i].lock);
		list_for_each_entry_rcu(r, &state[i].head, list) {
			struct multipath_dest *d;
			list_for_each_entry_rcu(d, &r->dests, list) {
				list_del_rcu(&d->list);
				call_rcu(&d->rcu,
					 __multipath_free_dst);
			}
			list_del_rcu(&r->list);
			call_rcu(&r->rcu,
				 __multipath_free);
		}

		spin_unlock_bh(&state[i].lock);
	}
}

static struct ip_mp_alg_ops wrandom_ops = {
	.mp_alg_select_route	=	wrandom_select_route,
	.mp_alg_flush		=	wrandom_flush,
	.mp_alg_set_nhinfo	=	wrandom_set_nhinfo,
};

static int __init wrandom_init(void)
{
	wrandom_init_state();

	return multipath_alg_register(&wrandom_ops, IP_MP_ALG_WRANDOM);
}

static void __exit wrandom_exit(void)
{
	multipath_alg_unregister(&wrandom_ops, IP_MP_ALG_WRANDOM);
}

module_init(wrandom_init);
module_exit(wrandom_exit);
MODULE_LICENSE("GPL");
Commit	Line	Data
1da177e4 LT	1	/*
	2	* Weighted random policy for multipath.
	3	*
	4	*
	5	* Version: $Id: multipath_wrandom.c,v 1.1.2.3 2004/09/22 07:51:40 elueck Exp $
	6	*
	7	* Authors: Einar Lueck <elueck@de.ibm.com><lkml@einar-lueck.de>
	8	*
	9	* This program is free software; you can redistribute it and/or
	10	* modify it under the terms of the GNU General Public License
	11	* as published by the Free Software Foundation; either version
	12	* 2 of the License, or (at your option) any later version.
	13	*/
	14
1da177e4 LT	15	#include <asm/system.h>
	16	#include <asm/uaccess.h>
	17	#include <linux/types.h>
	18	#include <linux/sched.h>
	19	#include <linux/errno.h>
	20	#include <linux/timer.h>
	21	#include <linux/mm.h>
	22	#include <linux/kernel.h>
	23	#include <linux/fcntl.h>
	24	#include <linux/stat.h>
	25	#include <linux/socket.h>
	26	#include <linux/in.h>
	27	#include <linux/inet.h>
	28	#include <linux/netdevice.h>
	29	#include <linux/inetdevice.h>
	30	#include <linux/igmp.h>
	31	#include <linux/proc_fs.h>
	32	#include <linux/seq_file.h>
6efd8455	33	#include <linux/module.h>
1da177e4 LT	34	#include <linux/mroute.h>
	35	#include <linux/init.h>
	36	#include <net/ip.h>
	37	#include <net/protocol.h>
	38	#include <linux/skbuff.h>
	39	#include <net/sock.h>
	40	#include <net/icmp.h>
	41	#include <net/udp.h>
	42	#include <net/raw.h>
	43	#include <linux/notifier.h>
	44	#include <linux/if_arp.h>
	45	#include <linux/netfilter_ipv4.h>
	46	#include <net/ipip.h>
	47	#include <net/checksum.h>
	48	#include <net/ip_fib.h>
	49	#include <net/ip_mp_alg.h>
	50
	51	#define MULTIPATH_STATE_SIZE 15
	52
	53	struct multipath_candidate {
	54	struct multipath_candidate *next;
	55	int power;
	56	struct rtable *rt;
	57	};
	58
	59	struct multipath_dest {
	60	struct list_head list;
	61
	62	const struct fib_nh *nh_info;
f20f4a60 AV	63	__be32 netmask;
f20f4a60 AV	64	__be32 network;
1da177e4 LT	65	unsigned char prefixlen;
	66
	67	struct rcu_head rcu;
	68	};
	69
	70	struct multipath_bucket {
	71	struct list_head head;
	72	spinlock_t lock;
	73	};
	74
	75	struct multipath_route {
	76	struct list_head list;
	77
	78	int oif;
f20f4a60	79	__be32 gw;
1da177e4 LT	80	struct list_head dests;
	81
	82	struct rcu_head rcu;
	83	};
	84
	85	/* state: primarily weight per route information */
	86	static struct multipath_bucket state[MULTIPATH_STATE_SIZE];
	87
	88	/* interface to random number generation */
	89	static unsigned int RANDOM_SEED = 93186752;
	90
	91	static inline unsigned int random(unsigned int ubound)
	92	{
	93	static unsigned int a = 1588635695,
	94	q = 2,
	95	r = 1117695901;
	96	RANDOM_SEED = a(RANDOM_SEED % q) - r(RANDOM_SEED / q);
	97	return RANDOM_SEED % ubound;
	98	}
	99
	100	static unsigned char __multipath_lookup_weight(const struct flowi *fl,
	101	const struct rtable *rt)
	102	{
	103	const int state_idx = rt->idev->dev->ifindex % MULTIPATH_STATE_SIZE;
	104	struct multipath_route *r;
	105	struct multipath_route *target_route = NULL;
	106	struct multipath_dest *d;
	107	int weight = 1;
	108
	109	/* lookup the weight information for a certain route */
	110	rcu_read_lock();
	111
	112	/* find state entry for gateway or add one if necessary */
	113	list_for_each_entry_rcu(r, &state[state_idx].head, list) {
	114	if (r->gw == rt->rt_gateway &&
	115	r->oif == rt->idev->dev->ifindex) {
	116	target_route = r;
	117	break;
	118	}
	119	}
	120
	121	if (!target_route) {
	122	/* this should not happen... but we are prepared */
	123	printk( KERN_CRIT"%s: missing state for gateway: %u and " \
	124	"device %d\n", __FUNCTION__, rt->rt_gateway,
	125	rt->idev->dev->ifindex);
	126	goto out;
	127	}
	128
	129	/* find state entry for destination */
	130	list_for_each_entry_rcu(d, &target_route->dests, list) {
e8192f36 AV	131	__be32 targetnetwork = fl->fl4_dst &
e8192f36 AV	132	inet_make_mask(d->prefixlen);
1da177e4 LT	133
	134	if ((targetnetwork & d->netmask) == d->network) {
	135	weight = d->nh_info->nh_weight;
	136	goto out;
	137	}
	138	}
	139
	140	out:
	141	rcu_read_unlock();
	142	return weight;
	143	}
	144
e905a9ed	145	static void wrandom_init_state(void)
1da177e4 LT	146	{
	147	int i;
	148
	149	for (i = 0; i < MULTIPATH_STATE_SIZE; ++i) {
	150	INIT_LIST_HEAD(&state[i].head);
	151	spin_lock_init(&state[i].lock);
	152	}
	153	}
	154
	155	static void wrandom_select_route(const struct flowi *flp,
	156	struct rtable *first,
	157	struct rtable **rp)
	158	{
	159	struct rtable *rt;
	160	struct rtable *decision;
	161	struct multipath_candidate *first_mpc = NULL;
	162	struct multipath_candidate mpc, last_mpc = NULL;
	163	int power = 0;
	164	int last_power;
	165	int selector;
	166	const size_t size_mpc = sizeof(struct multipath_candidate);
	167
	168	/* collect all candidates and identify their weights */
	169	for (rt = rcu_dereference(first); rt;
	170	rt = rcu_dereference(rt->u.rt_next)) {
	171	if ((rt->u.dst.flags & DST_BALANCED) != 0 &&
	172	multipath_comparekeys(&rt->fl, flp)) {
	173	struct multipath_candidate* mpc =
	174	(struct multipath_candidate*)
60d53065	175	kmalloc(size_mpc, GFP_ATOMIC);
1da177e4 LT	176
	177	if (!mpc)
	178	return;
	179
	180	power += __multipath_lookup_weight(flp, rt) * 10000;
	181
	182	mpc->power = power;
	183	mpc->rt = rt;
	184	mpc->next = NULL;
	185
	186	if (!first_mpc)
	187	first_mpc = mpc;
	188	else
	189	last_mpc->next = mpc;
	190
	191	last_mpc = mpc;
	192	}
	193	}
	194
	195	/* choose a weighted random candidate */
	196	decision = first;
	197	selector = random(power);
	198	last_power = 0;
	199
	200	/* select candidate, adjust GC data and cleanup local state */
	201	decision = first;
	202	last_mpc = NULL;
	203	for (mpc = first_mpc; mpc; mpc = mpc->next) {
	204	mpc->rt->u.dst.lastuse = jiffies;
	205	if (last_power <= selector && selector < mpc->power)
	206	decision = mpc->rt;
	207
	208	last_power = mpc->power;
a51482bd	209	kfree(last_mpc);
1da177e4 LT	210	last_mpc = mpc;
	211	}
	212
a51482bd JJ	213	/* concurrent __multipath_flush may lead to !last_mpc */
a51482bd JJ	214	kfree(last_mpc);
1da177e4 LT	215
	216	decision->u.dst.__use++;
	217	*rp = decision;
	218	}
	219
d9cd66e0 AV	220	static void wrandom_set_nhinfo(__be32 network,
d9cd66e0 AV	221	__be32 netmask,
1da177e4 LT	222	unsigned char prefixlen,
	223	const struct fib_nh *nh)
	224	{
	225	const int state_idx = nh->nh_oif % MULTIPATH_STATE_SIZE;
	226	struct multipath_route r, target_route = NULL;
	227	struct multipath_dest d, target_dest = NULL;
	228
	229	/* store the weight information for a certain route */
f8addb32	230	spin_lock_bh(&state[state_idx].lock);
1da177e4 LT	231
	232	/* find state entry for gateway or add one if necessary */
	233	list_for_each_entry_rcu(r, &state[state_idx].head, list) {
	234	if (r->gw == nh->nh_gw && r->oif == nh->nh_oif) {
	235	target_route = r;
	236	break;
	237	}
	238	}
	239
	240	if (!target_route) {
	241	const size_t size_rt = sizeof(struct multipath_route);
	242	target_route = (struct multipath_route *)
60d53065	243	kmalloc(size_rt, GFP_ATOMIC);
1da177e4 LT	244
	245	target_route->gw = nh->nh_gw;
	246	target_route->oif = nh->nh_oif;
	247	memset(&target_route->rcu, 0, sizeof(struct rcu_head));
	248	INIT_LIST_HEAD(&target_route->dests);
	249
	250	list_add_rcu(&target_route->list, &state[state_idx].head);
	251	}
	252
	253	/* find state entry for destination or add one if necessary */
	254	list_for_each_entry_rcu(d, &target_route->dests, list) {
	255	if (d->nh_info == nh) {
	256	target_dest = d;
	257	break;
	258	}
	259	}
	260
	261	if (!target_dest) {
	262	const size_t size_dst = sizeof(struct multipath_dest);
	263	target_dest = (struct multipath_dest*)
60d53065	264	kmalloc(size_dst, GFP_ATOMIC);
1da177e4 LT	265
	266	target_dest->nh_info = nh;
	267	target_dest->network = network;
	268	target_dest->netmask = netmask;
	269	target_dest->prefixlen = prefixlen;
	270	memset(&target_dest->rcu, 0, sizeof(struct rcu_head));
	271
	272	list_add_rcu(&target_dest->list, &target_route->dests);
	273	}
	274	/* else: we already stored this info for another destination =>
	275	* we are finished
	276	*/
	277
f8addb32	278	spin_unlock_bh(&state[state_idx].lock);
1da177e4 LT	279	}
	280
	281	static void __multipath_free(struct rcu_head *head)
	282	{
	283	struct multipath_route *rt = container_of(head, struct multipath_route,
	284	rcu);
	285	kfree(rt);
	286	}
	287
	288	static void __multipath_free_dst(struct rcu_head *head)
	289	{
e905a9ed	290	struct multipath_dest *dst = container_of(head,
1da177e4 LT	291	struct multipath_dest,
	292	rcu);
	293	kfree(dst);
	294	}
	295
	296	static void wrandom_flush(void)
	297	{
	298	int i;
	299
	300	/* defere delete to all entries */
	301	for (i = 0; i < MULTIPATH_STATE_SIZE; ++i) {
	302	struct multipath_route *r;
	303
f8addb32	304	spin_lock_bh(&state[i].lock);
1da177e4 LT	305	list_for_each_entry_rcu(r, &state[i].head, list) {
	306	struct multipath_dest *d;
	307	list_for_each_entry_rcu(d, &r->dests, list) {
	308	list_del_rcu(&d->list);
	309	call_rcu(&d->rcu,
	310	__multipath_free_dst);
	311	}
	312	list_del_rcu(&r->list);
	313	call_rcu(&r->rcu,
	314	__multipath_free);
	315	}
	316
f8addb32	317	spin_unlock_bh(&state[i].lock);
1da177e4 LT	318	}
	319	}
	320
	321	static struct ip_mp_alg_ops wrandom_ops = {
	322	.mp_alg_select_route = wrandom_select_route,
	323	.mp_alg_flush = wrandom_flush,
	324	.mp_alg_set_nhinfo = wrandom_set_nhinfo,
	325	};
	326
	327	static int __init wrandom_init(void)
	328	{
	329	wrandom_init_state();
	330
	331	return multipath_alg_register(&wrandom_ops, IP_MP_ALG_WRANDOM);
	332	}
	333
	334	static void __exit wrandom_exit(void)
	335	{
	336	multipath_alg_unregister(&wrandom_ops, IP_MP_ALG_WRANDOM);
	337	}
	338
	339	module_init(wrandom_init);
	340	module_exit(wrandom_exit);
6efd8455	341	MODULE_LICENSE("GPL");