net/ipv4/ipvs/ip_vs_dh.c

   1 /*
   2  * IPVS:        Destination Hashing scheduling module
   3  *
   4  * Version:     $Id: ip_vs_dh.c,v 1.5 2002/09/15 08:14:08 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) OR (n.weight <= 0) 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=%Zdbytes) 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=%Zdbytes) 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 dest flags is set with IP_VS_DEST_F_OVERLOAD,
 189  *      consider that the server is overloaded here.
 190  */
 191 static inline int is_overloaded(struct ip_vs_dest *dest)
 192 {
 193         return dest->flags & IP_VS_DEST_F_OVERLOAD;
 194 }
 195
 196
 197 /*
 198  *      Destination hashing scheduling
 199  */
 200 static struct ip_vs_dest *
 201 ip_vs_dh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
 202 {
 203         struct ip_vs_dest *dest;
 204         struct ip_vs_dh_bucket *tbl;
 205         struct iphdr *iph = skb->nh.iph;
 206
 207         IP_VS_DBG(6, "ip_vs_dh_schedule(): Scheduling...\n");
 208
 209         tbl = (struct ip_vs_dh_bucket *)svc->sched_data;
 210         dest = ip_vs_dh_get(tbl, iph->daddr);
 211         if (!dest
 212             || !(dest->flags & IP_VS_DEST_F_AVAILABLE)
 213             || atomic_read(&dest->weight) <= 0
 214             || is_overloaded(dest)) {
 215                 return NULL;
 216         }
 217
 218         IP_VS_DBG(6, "DH: destination IP address %u.%u.%u.%u "
 219                   "--> server %u.%u.%u.%u:%d\n",
 220                   NIPQUAD(iph->daddr),
 221                   NIPQUAD(dest->addr),
 222                   ntohs(dest->port));
 223
 224         return dest;
 225 }
 226
 227
 228 /*
 229  *      IPVS DH Scheduler structure
 230  */
 231 static struct ip_vs_scheduler ip_vs_dh_scheduler =
 232 {
 233         .name =                 "dh",
 234         .refcnt =               ATOMIC_INIT(0),
 235         .module =               THIS_MODULE,
 236         .init_service =         ip_vs_dh_init_svc,
 237         .done_service =         ip_vs_dh_done_svc,
 238         .update_service =       ip_vs_dh_update_svc,
 239         .schedule =             ip_vs_dh_schedule,
 240 };
 241
 242
 243 static int __init ip_vs_dh_init(void)
 244 {
 245         INIT_LIST_HEAD(&ip_vs_dh_scheduler.n_list);
 246         return register_ip_vs_scheduler(&ip_vs_dh_scheduler);
 247 }
 248
 249
 250 static void __exit ip_vs_dh_cleanup(void)
 251 {
 252         unregister_ip_vs_scheduler(&ip_vs_dh_scheduler);
 253 }
 254
 255
 256 module_init(ip_vs_dh_init);
 257 module_exit(ip_vs_dh_cleanup);
 258 MODULE_LICENSE("GPL");