net/netfilter/ipvs/ip_vs_sh.c

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