net/ipv4/ipvs/ip_vs_sh.c

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