/* * IPVS:        Locality-Based Least-Connection with Replication scheduler * * Version:     $Id: ip_vs_lblcr.c,v 1.11 2002/09/15 08:14:08 wensong Exp $ * * 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: *     Julian Anastasov        :    Added the missing (dest->weight>0) *                                  condition in the ip_vs_dest_set_max. * *//* * The lblc/r algorithm is as follows (pseudo code): * *       if serverSet[dest_ip] is null then *               n, serverSet[dest_ip] <- {weighted least-conn node}; *       else *               n <- {least-conn (alive) node in serverSet[dest_ip]}; *               if (n is null) OR *                  (n.conns>n.weight AND *                   there is a node m with m.conns<m.weight/2) then *                   n <- {weighted least-conn node}; *                   add n to serverSet[dest_ip]; *               if |serverSet[dest_ip]| > 1 AND *                   now - serverSet[dest_ip].lastMod > T then *                   m <- {most conn node in serverSet[dest_ip]}; *                   remove m from serverSet[dest_ip]; *       if serverSet[dest_ip] changed then *               serverSet[dest_ip].lastMod <- now; * *       return n; * */#include <linux/module.h>#include <linux/kernel.h>/* for sysctl */#include <linux/fs.h>#include <linux/sysctl.h>/* for proc_net_create/proc_net_remove */#include <linux/proc_fs.h>#include <net/ip_vs.h>/* *    It is for garbage collection of stale IPVS lblcr entries, *    when the table is full. */#define CHECK_EXPIRE_INTERVAL   (60*HZ)#define ENTRY_TIMEOUT           (6*60*HZ)/* *    It is for full expiration check. *    When there is no partial expiration check (garbage collection) *    in a half hour, do a full expiration check to collect stale *    entries that haven't been touched for a day. */#define COUNT_FOR_FULL_EXPIRATION   30static int sysctl_ip_vs_lblcr_expiration = 24*60*60*HZ;/* *     for IPVS lblcr entry hash table */#ifndef CONFIG_IP_VS_LBLCR_TAB_BITS#define CONFIG_IP_VS_LBLCR_TAB_BITS      10#endif#define IP_VS_LBLCR_TAB_BITS     CONFIG_IP_VS_LBLCR_TAB_BITS#define IP_VS_LBLCR_TAB_SIZE     (1 << IP_VS_LBLCR_TAB_BITS)#define IP_VS_LBLCR_TAB_MASK     (IP_VS_LBLCR_TAB_SIZE - 1)/* *      IPVS destination set structure and operations */struct ip_vs_dest_list {	struct ip_vs_dest_list  *next;          /* list link */	struct ip_vs_dest       *dest;          /* destination server */};struct ip_vs_dest_set {	atomic_t                size;           /* set size */	unsigned long           lastmod;        /* last modified time */	struct ip_vs_dest_list  *list;          /* destination list */	rwlock_t	        lock;           /* lock for this list */};static struct ip_vs_dest_list *ip_vs_dest_set_insert(struct ip_vs_dest_set *set, struct ip_vs_dest *dest){	struct ip_vs_dest_list *e;	for (e=set->list; e!=NULL; e=e->next) {		if (e->dest == dest)			/* already existed */			return NULL;	}	e = kmalloc(sizeof(struct ip_vs_dest_list), GFP_ATOMIC);	if (e == NULL) {		IP_VS_ERR("ip_vs_dest_set_insert(): no memory\n");		return NULL;	}	atomic_inc(&dest->refcnt);	e->dest = dest;	/* link it to the list */	write_lock(&set->lock);	e->next = set->list;	set->list = e;	atomic_inc(&set->size);	write_unlock(&set->lock);	set->lastmod = jiffies;	return e;}static voidip_vs_dest_set_erase(struct ip_vs_dest_set *set, struct ip_vs_dest *dest){	struct ip_vs_dest_list *e, **ep;	write_lock(&set->lock);	for (ep=&set->list, e=*ep; e!=NULL; e=*ep) {		if (e->dest == dest) {			/* HIT */			*ep = e->next;			atomic_dec(&set->size);			set->lastmod = jiffies;			atomic_dec(&e->dest->refcnt);			kfree(e);			break;		}		ep = &e->next;	}	write_unlock(&set->lock);}static void ip_vs_dest_set_eraseall(struct ip_vs_dest_set *set){	struct ip_vs_dest_list *e, **ep;	write_lock(&set->lock);	for (ep=&set->list, e=*ep; e!=NULL; e=*ep) {		*ep = e->next;		/*		 * We don't kfree dest because it is refered either		 * by its service or by the trash dest list.		 */		atomic_dec(&e->dest->refcnt);		kfree(e);	}	write_unlock(&set->lock);}/* get weighted least-connection node in the destination set */static inline struct ip_vs_dest *ip_vs_dest_set_min(struct ip_vs_dest_set *set){	register struct ip_vs_dest_list *e;	struct ip_vs_dest *dest, *least;	int loh, doh;	if (set == NULL)		return NULL;	read_lock(&set->lock);	/* select the first destination server, whose weight > 0 */	for (e=set->list; e!=NULL; e=e->next) {		least = e->dest;		if (least->flags & IP_VS_DEST_F_OVERLOAD)			continue;		if ((atomic_read(&least->weight) > 0)		    && (least->flags & IP_VS_DEST_F_AVAILABLE)) {			loh = atomic_read(&least->activeconns) * 50				+ atomic_read(&least->inactconns);			goto nextstage;		}	}	read_unlock(&set->lock);	return NULL;	/* find the destination with the weighted least load */  nextstage:	for (e=e->next; e!=NULL; e=e->next) {		dest = e->dest;		if (dest->flags & IP_VS_DEST_F_OVERLOAD)			continue;		doh = atomic_read(&dest->activeconns) * 50			+ atomic_read(&dest->inactconns);		if ((loh * atomic_read(&dest->weight) >		     doh * atomic_read(&least->weight))		    && (dest->flags & IP_VS_DEST_F_AVAILABLE)) {			least = dest;			loh = doh;		}	}	read_unlock(&set->lock);	IP_VS_DBG(6, "ip_vs_dest_set_min: server %d.%d.%d.%d:%d "		  "activeconns %d refcnt %d weight %d overhead %d\n",		  NIPQUAD(least->addr), ntohs(least->port),		  atomic_read(&least->activeconns),		  atomic_read(&least->refcnt),		  atomic_read(&least->weight), loh);	return least;}/* get weighted most-connection node in the destination set */static inline struct ip_vs_dest *ip_vs_dest_set_max(struct ip_vs_dest_set *set){	register struct ip_vs_dest_list *e;	struct ip_vs_dest *dest, *most;	int moh, doh;	if (set == NULL)		return NULL;	read_lock(&set->lock);	/* select the first destination server, whose weight > 0 */	for (e=set->list; e!=NULL; e=e->next) {		most = e->dest;		if (atomic_read(&most->weight) > 0) {			moh = atomic_read(&most->activeconns) * 50				+ atomic_read(&most->inactconns);			goto nextstage;		}	}	read_unlock(&set->lock);	return NULL;	/* find the destination with the weighted most load */  nextstage:	for (e=e->next; e!=NULL; e=e->next) {		dest = e->dest;		doh = atomic_read(&dest->activeconns) * 50			+ atomic_read(&dest->inactconns);		/* moh/mw < doh/dw ==> moh*dw < doh*mw, where mw,dw>0 */		if ((moh * atomic_read(&dest->weight) <		     doh * atomic_read(&most->weight))		    && (atomic_read(&dest->weight) > 0)) {			most = dest;			moh = doh;		}	}	read_unlock(&set->lock);	IP_VS_DBG(6, "ip_vs_dest_set_max: server %d.%d.%d.%d:%d "		  "activeconns %d refcnt %d weight %d overhead %d\n",		  NIPQUAD(most->addr), ntohs(most->port),		  atomic_read(&most->activeconns),		  atomic_read(&most->refcnt),		  atomic_read(&most->weight), moh);	return most;}/* *      IPVS lblcr entry represents an association between destination *      IP address and its destination server set */struct ip_vs_lblcr_entry {	struct list_head        list;	__u32                   addr;           /* destination IP address */	struct ip_vs_dest_set   set;            /* destination server set */	unsigned long           lastuse;        /* last used time */};/* *      IPVS lblcr hash table */struct ip_vs_lblcr_table {	rwlock_t	        lock;           /* lock for this table */	struct list_head        bucket[IP_VS_LBLCR_TAB_SIZE];  /* hash bucket */	atomic_t                entries;        /* number of entries */	int                     max_size;       /* maximum size of entries */	struct timer_list       periodic_timer; /* collect stale entries */	int                     rover;          /* rover for expire check */	int                     counter;        /* counter for no expire */};/* *      IPVS LBLCR sysctl table */static ctl_table vs_vars_table[] = {	{		.ctl_name	= NET_IPV4_VS_LBLCR_EXPIRE,		.procname	= "lblcr_expiration",		.data		= &sysctl_ip_vs_lblcr_expiration,		.maxlen		= sizeof(int),		.mode		= 0644, 		.proc_handler	= &proc_dointvec_jiffies,	},	{ .ctl_name = 0 }};static ctl_table vs_table[] = {	{		.ctl_name	= NET_IPV4_VS,		.procname	= "vs",		.mode		= 0555,		.child		= vs_vars_table	},	{ .ctl_name = 0 }};static ctl_table ipv4_table[] = {	{		.ctl_name	= NET_IPV4,		.procname	= "ipv4", 		.mode		= 0555,		.child		= vs_table	},	{ .ctl_name = 0 }};static ctl_table lblcr_root_table[] = {	{		.ctl_name	= CTL_NET,		.procname	= "net", 		.mode		= 0555, 		.child		= ipv4_table	},	{ .ctl_name = 0 }};static struct ctl_table_header * sysctl_header;/* *      new/free a ip_vs_lblcr_entry, which is a mapping of a destination *      IP address to a server. */static inline struct ip_vs_lblcr_entry *ip_vs_lblcr_new(__u32 daddr){	struct ip_vs_lblcr_entry *en;	en = kmalloc(sizeof(struct ip_vs_lblcr_entry), GFP_ATOMIC);	if (en == NULL) {		IP_VS_ERR("ip_vs_lblcr_new(): no memory\n");		return NULL;	}	INIT_LIST_HEAD(&en->list);	en->addr = daddr;	/* initilize its dest set */	atomic_set(&(en->set.size), 0);	en->set.list = NULL;	en->set.lock = RW_LOCK_UNLOCKED;	return en;}static inline void ip_vs_lblcr_free(struct ip_vs_lblcr_entry *en){	list_del(&en->list);	ip_vs_dest_set_eraseall(&en->set);	kfree(en);}/* *	Returns hash value for IPVS LBLCR entry */static inline unsigned ip_vs_lblcr_hashkey(__u32 addr){	return (ntohl(addr)*2654435761UL) & IP_VS_LBLCR_TAB_MASK;}/* *	Hash an entry in the ip_vs_lblcr_table. *	returns bool success. */static intip_vs_lblcr_hash(struct ip_vs_lblcr_table *tbl, struct ip_vs_lblcr_entry *en){	unsigned hash;	if (!list_empty(&en->list)) {		IP_VS_ERR("ip_vs_lblcr_hash(): request for already hashed, "			  "called from %p\n", __builtin_return_address(0));		return 0;	}	/*	 *	Hash by destination IP address	 */	hash = ip_vs_lblcr_hashkey(en->addr);	write_lock(&tbl->lock);	list_add(&en->list, &tbl->bucket[hash]);	atomic_inc(&tbl->entries);	write_unlock(&tbl->lock);	return 1;}#if 0000/* *	Unhash ip_vs_lblcr_entry from ip_vs_lblcr_table. *	returns bool success. */static int ip_vs_lblcr_unhash(struct ip_vs_lblcr_table *tbl,			     struct ip_vs_lblcr_entry *en){	if (list_empty(&en->list)) {		IP_VS_ERR("ip_vs_lblcr_unhash(): request for not hashed entry, "			  "called from %p\n", __builtin_return_address(0));		return 0;	}	/*	 * Remove it from the table	 */	write_lock(&tbl->lock);	list_del(&en->list);	INIT_LIST_HEAD(&en->list);	write_unlock(&tbl->lock);	return 1;}#endif/* *  Get ip_vs_lblcr_entry associated with supplied parameters.