net/ipv4/ipvs/ip_vs_wrr.c

   1 /*
   2  * IPVS:        Weighted Round-Robin Scheduling module
   3  *
   4  * Version:     $Id: ip_vs_wrr.c,v 1.11 2002/03/25 12:44:35 wensong Exp $
   5  *
   6  * Authors:     Wensong Zhang <wensong@linuxvirtualserver.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  *     Wensong Zhang            :     changed the ip_vs_wrr_schedule to return dest
  15  *     Wensong Zhang            :     changed some comestics things for debugging
  16  *     Wensong Zhang            :     changed for the d-linked destination list
  17  *     Wensong Zhang            :     added the ip_vs_wrr_update_svc
  18  *     Julian Anastasov         :     fixed the bug of returning destination
  19  *                                    with weight 0 when all weights are zero
  20  *
  21  */
  22
  23 #include <linux/module.h>
  24 #include <linux/kernel.h>
  25
  26 #include <net/ip_vs.h>
  27
  28 /*
  29  * current destination pointer for weighted round-robin scheduling
  30  */
  31 struct ip_vs_wrr_mark {
  32         struct list_head *cl;   /* current list head */
  33         int cw;                 /* current weight */
  34         int mw;                 /* maximum weight */
  35         int di;                 /* decreasing interval */
  36 };
  37
  38
  39 /*
  40  *    Get the gcd of server weights
  41  */
  42 static int gcd(int a, int b)
  43 {
  44         int c;
  45
  46         while ((c = a % b)) {
  47                 a = b;
  48                 b = c;
  49         }
  50         return b;
  51 }
  52
  53 static int ip_vs_wrr_gcd_weight(struct ip_vs_service *svc)
  54 {
  55         register struct list_head *l, *e;
  56         struct ip_vs_dest *dest;
  57         int weight;
  58         int g = 1;
  59
  60         l = &svc->destinations;
  61         for (e=l->next; e!=l; e=e->next) {
  62                 dest = list_entry(e, struct ip_vs_dest, n_list);
  63                 weight = atomic_read(&dest->weight);
  64                 if (weight > 0) {
  65                         g = weight;
  66                         break;
  67                 }
  68         }
  69         if (e == l)
  70                 return g;
  71
  72         for (e=e->next; e!=l; e=e->next) {
  73                 dest = list_entry(e, struct ip_vs_dest, n_list);
  74                 weight = atomic_read(&dest->weight);
  75                 if (weight > 0)
  76                         g = gcd(weight, g);
  77         }
  78
  79         return g;
  80 }
  81
  82
  83 /*
  84  *    Get the maximum weight of the service destinations.
  85  */
  86 static int ip_vs_wrr_max_weight(struct ip_vs_service *svc)
  87 {
  88         register struct list_head *l, *e;
  89         struct ip_vs_dest *dest;
  90         int weight = 0;
  91
  92         l = &svc->destinations;
  93         for (e=l->next; e!=l; e=e->next) {
  94                 dest = list_entry(e, struct ip_vs_dest, n_list);
  95                 if (atomic_read(&dest->weight) > weight)
  96                         weight = atomic_read(&dest->weight);
  97         }
  98
  99         return weight;
 100 }
 101
 102
 103 static int ip_vs_wrr_init_svc(struct ip_vs_service *svc)
 104 {
 105         struct ip_vs_wrr_mark *mark;
 106
 107         /*
 108          *    Allocate the mark variable for WRR scheduling
 109          */
 110         mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_ATOMIC);
 111         if (mark == NULL) {
 112                 IP_VS_ERR("ip_vs_wrr_init_svc(): no memory\n");
 113                 return -ENOMEM;
 114         }
 115         mark->cl = &svc->destinations;
 116         mark->cw = 0;
 117         mark->mw = ip_vs_wrr_max_weight(svc);
 118         mark->di = ip_vs_wrr_gcd_weight(svc);
 119         svc->sched_data = mark;
 120
 121         return 0;
 122 }
 123
 124
 125 static int ip_vs_wrr_done_svc(struct ip_vs_service *svc)
 126 {
 127         /*
 128          *    Release the mark variable
 129          */
 130         kfree(svc->sched_data);
 131
 132         return 0;
 133 }
 134
 135
 136 static int ip_vs_wrr_update_svc(struct ip_vs_service *svc)
 137 {
 138         struct ip_vs_wrr_mark *mark = svc->sched_data;
 139
 140         mark->cl = &svc->destinations;
 141         mark->mw = ip_vs_wrr_max_weight(svc);
 142         mark->di = ip_vs_wrr_gcd_weight(svc);
 143         if (mark->cw > mark->mw)
 144                 mark->cw = 0;
 145         return 0;
 146 }
 147
 148
 149 /*
 150  *    Weighted Round-Robin Scheduling
 151  */
 152 static struct ip_vs_dest *
 153 ip_vs_wrr_schedule(struct ip_vs_service *svc, struct iphdr *iph)
 154 {
 155         struct ip_vs_dest *dest;
 156         struct ip_vs_wrr_mark *mark = svc->sched_data;
 157
 158         IP_VS_DBG(6, "ip_vs_wrr_schedule(): Scheduling...\n");
 159
 160         /*
 161          * This loop will always terminate, because 0<mark->cw<max_weight,
 162          * and at least one server has its weight equal to max_weight.
 163          */
 164         write_lock(&svc->sched_lock);
 165         while (1) {
 166                 if (mark->cl == &svc->destinations) {
 167                         /* it is at the head of the destination list */
 168
 169                         if (mark->cl == mark->cl->next) {
 170                                 /* no dest entry */
 171                                 write_unlock(&svc->sched_lock);
 172                                 return NULL;
 173                         }
 174
 175                         mark->cl = svc->destinations.next;
 176                         mark->cw -= mark->di;
 177                         if (mark->cw <= 0) {
 178                                 mark->cw = mark->mw;
 179                                 /*
 180                                  * Still zero, which means no available servers.
 181                                  */
 182                                 if (mark->cw == 0) {
 183                                         mark->cl = &svc->destinations;
 184                                         write_unlock(&svc->sched_lock);
 185                                         IP_VS_INFO("ip_vs_wrr_schedule(): "
 186                                                    "no available servers\n");
 187                                         return NULL;
 188                                 }
 189                         }
 190                 }
 191                 else mark->cl = mark->cl->next;
 192
 193                 if (mark->cl != &svc->destinations) {
 194                         /* not at the head of the list */
 195                         dest = list_entry(mark->cl, struct ip_vs_dest, n_list);
 196                         if (atomic_read(&dest->weight) >= mark->cw) {
 197                                 write_unlock(&svc->sched_lock);
 198                                 break;
 199                         }
 200                 }
 201         }
 202
 203         IP_VS_DBG(6, "WRR: server %u.%u.%u.%u:%u "
 204                   "activeconns %d refcnt %d weight %d\n",
 205                   NIPQUAD(dest->addr), ntohs(dest->port),
 206                   atomic_read(&dest->activeconns),
 207                   atomic_read(&dest->refcnt),
 208                   atomic_read(&dest->weight));
 209
 210         return  dest;
 211 }
 212
 213
 214 static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
 215         {0},                    /* n_list */
 216         "wrr",                  /* name */
 217         ATOMIC_INIT(0),         /* refcnt */
 218         THIS_MODULE,            /* this module */
 219         ip_vs_wrr_init_svc,     /* service initializer */
 220         ip_vs_wrr_done_svc,     /* service done */
 221         ip_vs_wrr_update_svc,   /* service updater */
 222         ip_vs_wrr_schedule,     /* select a server from the destination list */
 223 };
 224
 225 static int __init ip_vs_wrr_init(void)
 226 {
 227         INIT_LIST_HEAD(&ip_vs_wrr_scheduler.n_list);
 228         return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
 229 }
 230
 231 static void __exit ip_vs_wrr_cleanup(void)
 232 {
 233         unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
 234 }
 235
 236 module_init(ip_vs_wrr_init);
 237 module_exit(ip_vs_wrr_cleanup);
 238 MODULE_LICENSE("GPL");