net/ipv4/multipath_wrandom.c - fp2-dev/kernel/msm - Gitiles

 /*
  *              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 <linux/config.h>
 #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;
 	__u32			netmask;
 	__u32			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;
 	__u32			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) {
 		__u32 targetnetwork = fl->fl4_dst &
 			(0xFFFFFFFF >> (32 - 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(__u32 network,
 			       __u32 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");
	/*
	* 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 <linux/config.h>
	#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;
	__u32 netmask;
	__u32 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;
	__u32 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) {
	__u32 targetnetwork = fl->fl4_dst &
	(0xFFFFFFFF >> (32 - 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(__u32 network,
	__u32 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");