net/ipv4/ipvs/ip_vs_dh.c

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