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/ip.h>
  41 #include <linux/module.h>
  42 #include <linux/kernel.h>
  43 #include <linux/skbuff.h>
  44
  45 #include <net/ip_vs.h>
  46
  47
  48 /*
  49  *      IPVS DH bucket
  50  */
  51 struct ip_vs_dh_bucket {
  52         struct ip_vs_dest       *dest;          /* real server (cache) */
  53 };
  54
  55 /*
  56  *     for IPVS DH entry hash table
  57  */
  58 #ifndef CONFIG_IP_VS_DH_TAB_BITS
  59 #define CONFIG_IP_VS_DH_TAB_BITS        8
  60 #endif
  61 #define IP_VS_DH_TAB_BITS               CONFIG_IP_VS_DH_TAB_BITS
  62 #define IP_VS_DH_TAB_SIZE               (1 << IP_VS_DH_TAB_BITS)
  63 #define IP_VS_DH_TAB_MASK               (IP_VS_DH_TAB_SIZE - 1)
  64
  65
  66 /*
  67  *      Returns hash value for IPVS DH entry
  68  */
  69 static inline unsigned ip_vs_dh_hashkey(__u32 addr)
  70 {
  71         return (ntohl(addr)*2654435761UL) & IP_VS_DH_TAB_MASK;
  72 }
  73
  74
  75 /*
  76  *      Get ip_vs_dest associated with supplied parameters.
  77  */
  78 static inline struct ip_vs_dest *
  79 ip_vs_dh_get(struct ip_vs_dh_bucket *tbl, __u32 addr)
  80 {
  81         return (tbl[ip_vs_dh_hashkey(addr)]).dest;
  82 }
  83
  84
  85 /*
  86  *      Assign all the hash buckets of the specified table with the service.
  87  */
  88 static int
  89 ip_vs_dh_assign(struct ip_vs_dh_bucket *tbl, struct ip_vs_service *svc)
  90 {
  91         int i;
  92         struct ip_vs_dh_bucket *b;
  93         struct list_head *p;
  94         struct ip_vs_dest *dest;
  95
  96         b = tbl;
  97         p = &svc->destinations;
  98         for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
  99                 if (list_empty(p)) {
 100                         b->dest = NULL;
 101                 } else {
 102                         if (p == &svc->destinations)
 103                                 p = p->next;
 104
 105                         dest = list_entry(p, struct ip_vs_dest, n_list);
 106                         atomic_inc(&dest->refcnt);
 107                         b->dest = dest;
 108
 109                         p = p->next;
 110                 }
 111                 b++;
 112         }
 113         return 0;
 114 }
 115
 116
 117 /*
 118  *      Flush all the hash buckets of the specified table.
 119  */
 120 static void ip_vs_dh_flush(struct ip_vs_dh_bucket *tbl)
 121 {
 122         int i;
 123         struct ip_vs_dh_bucket *b;
 124
 125         b = tbl;
 126         for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
 127                 if (b->dest) {
 128                         atomic_dec(&b->dest->refcnt);
 129                         b->dest = NULL;
 130                 }
 131                 b++;
 132         }
 133 }
 134
 135
 136 static int ip_vs_dh_init_svc(struct ip_vs_service *svc)
 137 {
 138         struct ip_vs_dh_bucket *tbl;
 139
 140         /* allocate the DH table for this service */
 141         tbl = kmalloc(sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE,
 142                       GFP_ATOMIC);
 143         if (tbl == NULL) {
 144                 IP_VS_ERR("ip_vs_dh_init_svc(): no memory\n");
 145                 return -ENOMEM;
 146         }
 147         svc->sched_data = tbl;
 148         IP_VS_DBG(6, "DH hash table (memory=%Zdbytes) allocated for "
 149                   "current service\n",
 150                   sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
 151
 152         /* assign the hash buckets with the updated service */
 153         ip_vs_dh_assign(tbl, svc);
 154
 155         return 0;
 156 }
 157
 158
 159 static int ip_vs_dh_done_svc(struct ip_vs_service *svc)
 160 {
 161         struct ip_vs_dh_bucket *tbl = svc->sched_data;
 162
 163         /* got to clean up hash buckets here */
 164         ip_vs_dh_flush(tbl);
 165
 166         /* release the table itself */
 167         kfree(svc->sched_data);
 168         IP_VS_DBG(6, "DH hash table (memory=%Zdbytes) released\n",
 169                   sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
 170
 171         return 0;
 172 }
 173
 174
 175 static int ip_vs_dh_update_svc(struct ip_vs_service *svc)
 176 {
 177         struct ip_vs_dh_bucket *tbl = svc->sched_data;
 178
 179         /* got to clean up hash buckets here */
 180         ip_vs_dh_flush(tbl);
 181
 182         /* assign the hash buckets with the updated service */
 183         ip_vs_dh_assign(tbl, svc);
 184
 185         return 0;
 186 }
 187
 188
 189 /*
 190  *      If the dest flags is set with IP_VS_DEST_F_OVERLOAD,
 191  *      consider that the server is overloaded here.
 192  */
 193 static inline int is_overloaded(struct ip_vs_dest *dest)
 194 {
 195         return dest->flags & IP_VS_DEST_F_OVERLOAD;
 196 }
 197
 198
 199 /*
 200  *      Destination hashing scheduling
 201  */
 202 static struct ip_vs_dest *
 203 ip_vs_dh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
 204 {
 205         struct ip_vs_dest *dest;
 206         struct ip_vs_dh_bucket *tbl;
 207         struct iphdr *iph = skb->nh.iph;
 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         .name =                 "dh",
 236         .refcnt =               ATOMIC_INIT(0),
 237         .module =               THIS_MODULE,
 238         .init_service =         ip_vs_dh_init_svc,
 239         .done_service =         ip_vs_dh_done_svc,
 240         .update_service =       ip_vs_dh_update_svc,
 241         .schedule =             ip_vs_dh_schedule,
 242 };
 243
 244
 245 static int __init ip_vs_dh_init(void)
 246 {
 247         INIT_LIST_HEAD(&ip_vs_dh_scheduler.n_list);
 248         return register_ip_vs_scheduler(&ip_vs_dh_scheduler);
 249 }
 250
 251
 252 static void __exit ip_vs_dh_cleanup(void)
 253 {
 254         unregister_ip_vs_scheduler(&ip_vs_dh_scheduler);
 255 }
 256
 257
 258 module_init(ip_vs_dh_init);
 259 module_exit(ip_vs_dh_cleanup);
 260 MODULE_LICENSE("GPL");