[linux-block.git] / net / netfilter / ipvs / ip_vs_sh.c

/*
 * IPVS:        Source Hashing scheduling module
 *
 * Authors:     Wensong Zhang <wensong@gnuchina.org>
 *
 *              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.
 *
 * Changes:
 *
 */

/*
 * The sh algorithm is to select server by the hash key of source IP
 * address. The pseudo code is as follows:
 *
 *       n <- servernode[src_ip];
 *       if (n is dead) OR
 *          (n is overloaded) or (n.weight <= 0) then
 *                 return NULL;
 *
 *       return n;
 *
 * Notes that servernode is a 256-bucket hash table that maps the hash
 * index derived from packet source IP address to the current server
 * array. If the sh scheduler is used in cache cluster, it is good to
 * combine it with cache_bypass feature. When the statically assigned
 * server is dead or overloaded, the load balancer can bypass the cache
 * server and send requests to the original server directly.
 *
 */

#define KMSG_COMPONENT "IPVS"
#define pr_fmt(fmt) KMSG_COMPONENT ": " fmt

#include <linux/ip.h>
#include <linux/slab.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>

#include <net/ip_vs.h>


/*
 *      IPVS SH bucket
 */
struct ip_vs_sh_bucket {
	struct ip_vs_dest       *dest;          /* real server (cache) */
};

/*
 *     for IPVS SH entry hash table
 */
#ifndef CONFIG_IP_VS_SH_TAB_BITS
#define CONFIG_IP_VS_SH_TAB_BITS        8
#endif
#define IP_VS_SH_TAB_BITS               CONFIG_IP_VS_SH_TAB_BITS
#define IP_VS_SH_TAB_SIZE               (1 << IP_VS_SH_TAB_BITS)
#define IP_VS_SH_TAB_MASK               (IP_VS_SH_TAB_SIZE - 1)


/*
 *	Returns hash value for IPVS SH entry
 */
static inline unsigned ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr)
{
	__be32 addr_fold = addr->ip;

#ifdef CONFIG_IP_VS_IPV6
	if (af == AF_INET6)
		addr_fold = addr->ip6[0]^addr->ip6[1]^
			    addr->ip6[2]^addr->ip6[3];
#endif
	return (ntohl(addr_fold)*2654435761UL) & IP_VS_SH_TAB_MASK;
}


/*
 *      Get ip_vs_dest associated with supplied parameters.
 */
static inline struct ip_vs_dest *
ip_vs_sh_get(int af, struct ip_vs_sh_bucket *tbl,
	     const union nf_inet_addr *addr)
{
	return (tbl[ip_vs_sh_hashkey(af, addr)]).dest;
}


/*
 *      Assign all the hash buckets of the specified table with the service.
 */
static int
ip_vs_sh_assign(struct ip_vs_sh_bucket *tbl, struct ip_vs_service *svc)
{
	int i;
	struct ip_vs_sh_bucket *b;
	struct list_head *p;
	struct ip_vs_dest *dest;

	b = tbl;
	p = &svc->destinations;
	for (i=0; i<IP_VS_SH_TAB_SIZE; i++) {
		if (list_empty(p)) {
			b->dest = NULL;
		} else {
			if (p == &svc->destinations)
				p = p->next;

			dest = list_entry(p, struct ip_vs_dest, n_list);
			atomic_inc(&dest->refcnt);
			b->dest = dest;

			p = p->next;
		}
		b++;
	}
	return 0;
}


/*
 *      Flush all the hash buckets of the specified table.
 */
static void ip_vs_sh_flush(struct ip_vs_sh_bucket *tbl)
{
	int i;
	struct ip_vs_sh_bucket *b;

	b = tbl;
	for (i=0; i<IP_VS_SH_TAB_SIZE; i++) {
		if (b->dest) {
			atomic_dec(&b->dest->refcnt);
			b->dest = NULL;
		}
		b++;
	}
}


static int ip_vs_sh_init_svc(struct ip_vs_service *svc)
{
	struct ip_vs_sh_bucket *tbl;

	/* allocate the SH table for this service */
	tbl = kmalloc(sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE,
		      GFP_ATOMIC);
	if (tbl == NULL) {
		pr_err("%s(): no memory\n", __func__);
		return -ENOMEM;
	}
	svc->sched_data = tbl;
	IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) allocated for "
		  "current service\n",
		  sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE);

	/* assign the hash buckets with the updated service */
	ip_vs_sh_assign(tbl, svc);

	return 0;
}


static int ip_vs_sh_done_svc(struct ip_vs_service *svc)
{
	struct ip_vs_sh_bucket *tbl = svc->sched_data;

	/* got to clean up hash buckets here */
	ip_vs_sh_flush(tbl);

	/* release the table itself */
	kfree(svc->sched_data);
	IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) released\n",
		  sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE);

	return 0;
}


static int ip_vs_sh_update_svc(struct ip_vs_service *svc)
{
	struct ip_vs_sh_bucket *tbl = svc->sched_data;

	/* got to clean up hash buckets here */
	ip_vs_sh_flush(tbl);

	/* assign the hash buckets with the updated service */
	ip_vs_sh_assign(tbl, svc);

	return 0;
}


/*
 *      If the dest flags is set with IP_VS_DEST_F_OVERLOAD,
 *      consider that the server is overloaded here.
 */
static inline int is_overloaded(struct ip_vs_dest *dest)
{
	return dest->flags & IP_VS_DEST_F_OVERLOAD;
}


/*
 *      Source Hashing scheduling
 */
static struct ip_vs_dest *
ip_vs_sh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
{
	struct ip_vs_dest *dest;
	struct ip_vs_sh_bucket *tbl;
	struct ip_vs_iphdr iph;

	ip_vs_fill_iphdr(svc->af, skb_network_header(skb), &iph);

	IP_VS_DBG(6, "ip_vs_sh_schedule(): Scheduling...\n");

	tbl = (struct ip_vs_sh_bucket *)svc->sched_data;
	dest = ip_vs_sh_get(svc->af, tbl, &iph.saddr);
	if (!dest
	    || !(dest->flags & IP_VS_DEST_F_AVAILABLE)
	    || atomic_read(&dest->weight) <= 0
	    || is_overloaded(dest)) {
		IP_VS_ERR_RL("SH: no destination available\n");
		return NULL;
	}

	IP_VS_DBG_BUF(6, "SH: source IP address %s --> server %s:%d\n",
		      IP_VS_DBG_ADDR(svc->af, &iph.saddr),
		      IP_VS_DBG_ADDR(svc->af, &dest->addr),
		      ntohs(dest->port));

	return dest;
}


/*
 *      IPVS SH Scheduler structure
 */
static struct ip_vs_scheduler ip_vs_sh_scheduler =
{
	.name =			"sh",
	.refcnt =		ATOMIC_INIT(0),
	.module =		THIS_MODULE,
	.n_list	 =		LIST_HEAD_INIT(ip_vs_sh_scheduler.n_list),
	.init_service =		ip_vs_sh_init_svc,
	.done_service =		ip_vs_sh_done_svc,
	.update_service =	ip_vs_sh_update_svc,
	.schedule =		ip_vs_sh_schedule,
};


static int __init ip_vs_sh_init(void)
{
	return register_ip_vs_scheduler(&ip_vs_sh_scheduler);
}


static void __exit ip_vs_sh_cleanup(void)
{
	unregister_ip_vs_scheduler(&ip_vs_sh_scheduler);
}


module_init(ip_vs_sh_init);
module_exit(ip_vs_sh_cleanup);
MODULE_LICENSE("GPL");
Commit	Line	Data
1da177e4 LT	1	/*
	2	* IPVS: Source Hashing scheduling module
	3	*
1da177e4 LT	4	* Authors: Wensong Zhang <wensong@gnuchina.org>
	5	*
	6	* This program is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU General Public License
	8	* as published by the Free Software Foundation; either version
	9	* 2 of the License, or (at your option) any later version.
	10	*
	11	* Changes:
	12	*
	13	*/
	14
	15	/*
	16	* The sh algorithm is to select server by the hash key of source IP
	17	* address. The pseudo code is as follows:
	18	*
	19	* n <- servernode[src_ip];
	20	* if (n is dead) OR
	21	* (n is overloaded) or (n.weight <= 0) then
	22	* return NULL;
	23	*
	24	* return n;
	25	*
	26	* Notes that servernode is a 256-bucket hash table that maps the hash
	27	* index derived from packet source IP address to the current server
	28	* array. If the sh scheduler is used in cache cluster, it is good to
	29	* combine it with cache_bypass feature. When the statically assigned
	30	* server is dead or overloaded, the load balancer can bypass the cache
	31	* server and send requests to the original server directly.
	32	*
	33	*/
	34
9aada7ac HE	35	#define KMSG_COMPONENT "IPVS"
	36	#define pr_fmt(fmt) KMSG_COMPONENT ": " fmt
	37
14c85021	38	#include <linux/ip.h>
5a0e3ad6	39	#include <linux/slab.h>
1da177e4 LT	40	#include <linux/module.h>
1da177e4 LT	41	#include <linux/kernel.h>
14c85021	42	#include <linux/skbuff.h>
1da177e4 LT	43
	44	#include <net/ip_vs.h>
	45
	46
	47	/*
	48	* IPVS SH bucket
	49	*/
	50	struct ip_vs_sh_bucket {
	51	struct ip_vs_dest dest; / real server (cache) */
	52	};
	53
	54	/*
	55	* for IPVS SH entry hash table
	56	*/
	57	#ifndef CONFIG_IP_VS_SH_TAB_BITS
	58	#define CONFIG_IP_VS_SH_TAB_BITS 8
	59	#endif
	60	#define IP_VS_SH_TAB_BITS CONFIG_IP_VS_SH_TAB_BITS
	61	#define IP_VS_SH_TAB_SIZE (1 << IP_VS_SH_TAB_BITS)
	62	#define IP_VS_SH_TAB_MASK (IP_VS_SH_TAB_SIZE - 1)
	63
	64
	65	/*
	66	* Returns hash value for IPVS SH entry
	67	*/
20971a0a	68	static inline unsigned ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr)
1da177e4	69	{
20971a0a JV	70	__be32 addr_fold = addr->ip;
	71
	72	#ifdef CONFIG_IP_VS_IPV6
	73	if (af == AF_INET6)
	74	addr_fold = addr->ip6[0]^addr->ip6[1]^
	75	addr->ip6[2]^addr->ip6[3];
	76	#endif
	77	return (ntohl(addr_fold)*2654435761UL) & IP_VS_SH_TAB_MASK;
1da177e4 LT	78	}
	79
	80
	81	/*
	82	* Get ip_vs_dest associated with supplied parameters.
	83	*/
	84	static inline struct ip_vs_dest *
20971a0a JV	85	ip_vs_sh_get(int af, struct ip_vs_sh_bucket *tbl,
20971a0a JV	86	const union nf_inet_addr *addr)
1da177e4	87	{
20971a0a	88	return (tbl[ip_vs_sh_hashkey(af, addr)]).dest;
1da177e4 LT	89	}
	90
	91
	92	/*
	93	* Assign all the hash buckets of the specified table with the service.
	94	*/
	95	static int
	96	ip_vs_sh_assign(struct ip_vs_sh_bucket tbl, struct ip_vs_service svc)
	97	{
	98	int i;
	99	struct ip_vs_sh_bucket *b;
	100	struct list_head *p;
	101	struct ip_vs_dest *dest;
	102
	103	b = tbl;
	104	p = &svc->destinations;
	105	for (i=0; i<IP_VS_SH_TAB_SIZE; i++) {
	106	if (list_empty(p)) {
	107	b->dest = NULL;
	108	} else {
	109	if (p == &svc->destinations)
	110	p = p->next;
	111
	112	dest = list_entry(p, struct ip_vs_dest, n_list);
	113	atomic_inc(&dest->refcnt);
	114	b->dest = dest;
	115
	116	p = p->next;
	117	}
	118	b++;
	119	}
	120	return 0;
	121	}
	122
	123
	124	/*
	125	* Flush all the hash buckets of the specified table.
	126	*/
	127	static void ip_vs_sh_flush(struct ip_vs_sh_bucket *tbl)
	128	{
	129	int i;
	130	struct ip_vs_sh_bucket *b;
	131
	132	b = tbl;
	133	for (i=0; i<IP_VS_SH_TAB_SIZE; i++) {
	134	if (b->dest) {
	135	atomic_dec(&b->dest->refcnt);
	136	b->dest = NULL;
	137	}
	138	b++;
	139	}
	140	}
	141
	142
	143	static int ip_vs_sh_init_svc(struct ip_vs_service *svc)
	144	{
	145	struct ip_vs_sh_bucket *tbl;
	146
	147	/* allocate the SH table for this service */
	148	tbl = kmalloc(sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE,
	149	GFP_ATOMIC);
	150	if (tbl == NULL) {
1e3e238e	151	pr_err("%s(): no memory\n", __func__);
1da177e4 LT	152	return -ENOMEM;
	153	}
	154	svc->sched_data = tbl;
	155	IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) allocated for "
	156	"current service\n",
	157	sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE);
	158
	159	/* assign the hash buckets with the updated service */
	160	ip_vs_sh_assign(tbl, svc);
	161
	162	return 0;
	163	}
	164
	165
	166	static int ip_vs_sh_done_svc(struct ip_vs_service *svc)
	167	{
	168	struct ip_vs_sh_bucket *tbl = svc->sched_data;
	169
	170	/* got to clean up hash buckets here */
	171	ip_vs_sh_flush(tbl);
	172
	173	/* release the table itself */
	174	kfree(svc->sched_data);
	175	IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) released\n",
	176	sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE);
	177
	178	return 0;
	179	}
	180
	181
	182	static int ip_vs_sh_update_svc(struct ip_vs_service *svc)
	183	{
	184	struct ip_vs_sh_bucket *tbl = svc->sched_data;
	185
	186	/* got to clean up hash buckets here */
	187	ip_vs_sh_flush(tbl);
	188
	189	/* assign the hash buckets with the updated service */
	190	ip_vs_sh_assign(tbl, svc);
	191
	192	return 0;
	193	}
	194
	195
	196	/*
	197	* If the dest flags is set with IP_VS_DEST_F_OVERLOAD,
	198	* consider that the server is overloaded here.
	199	*/
	200	static inline int is_overloaded(struct ip_vs_dest *dest)
	201	{
	202	return dest->flags & IP_VS_DEST_F_OVERLOAD;
	203	}
	204
	205
	206	/*
	207	* Source Hashing scheduling
	208	*/
	209	static struct ip_vs_dest *
	210	ip_vs_sh_schedule(struct ip_vs_service svc, const struct sk_buff skb)
	211	{
	212	struct ip_vs_dest *dest;
	213	struct ip_vs_sh_bucket *tbl;
20971a0a JV	214	struct ip_vs_iphdr iph;
	215
	216	ip_vs_fill_iphdr(svc->af, skb_network_header(skb), &iph);
1da177e4 LT	217
	218	IP_VS_DBG(6, "ip_vs_sh_schedule(): Scheduling...\n");
	219
	220	tbl = (struct ip_vs_sh_bucket *)svc->sched_data;
20971a0a	221	dest = ip_vs_sh_get(svc->af, tbl, &iph.saddr);
1da177e4 LT	222	if (!dest
	223	\|\| !(dest->flags & IP_VS_DEST_F_AVAILABLE)
	224	\|\| atomic_read(&dest->weight) <= 0
	225	\|\| is_overloaded(dest)) {
68888d10	226	IP_VS_ERR_RL("SH: no destination available\n");
1da177e4 LT	227	return NULL;
	228	}
	229
20971a0a JV	230	IP_VS_DBG_BUF(6, "SH: source IP address %s --> server %s:%d\n",
	231	IP_VS_DBG_ADDR(svc->af, &iph.saddr),
	232	IP_VS_DBG_ADDR(svc->af, &dest->addr),
	233	ntohs(dest->port));
1da177e4 LT	234
	235	return dest;
	236	}
	237
	238
	239	/*
	240	* IPVS SH Scheduler structure
	241	*/
	242	static struct ip_vs_scheduler ip_vs_sh_scheduler =
	243	{
	244	.name = "sh",
	245	.refcnt = ATOMIC_INIT(0),
	246	.module = THIS_MODULE,
d149ccc9	247	.n_list = LIST_HEAD_INIT(ip_vs_sh_scheduler.n_list),
1da177e4 LT	248	.init_service = ip_vs_sh_init_svc,
	249	.done_service = ip_vs_sh_done_svc,
	250	.update_service = ip_vs_sh_update_svc,
	251	.schedule = ip_vs_sh_schedule,
	252	};
	253
	254
	255	static int __init ip_vs_sh_init(void)
	256	{
1da177e4 LT	257	return register_ip_vs_scheduler(&ip_vs_sh_scheduler);
	258	}
	259
	260
	261	static void __exit ip_vs_sh_cleanup(void)
	262	{
	263	unregister_ip_vs_scheduler(&ip_vs_sh_scheduler);
	264	}
	265
	266
	267	module_init(ip_vs_sh_init);
	268	module_exit(ip_vs_sh_cleanup);
	269	MODULE_LICENSE("GPL");