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.12 2002/09/15 08:14:08 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         struct ip_vs_dest *dest;
  56         int weight;
  57         int g = 0;
  58
  59         list_for_each_entry(dest, &svc->destinations, n_list) {
  60                 weight = atomic_read(&dest->weight);
  61                 if (weight > 0) {
  62                         if (g > 0)
  63                                 g = gcd(weight, g);
  64                         else
  65                                 g = weight;
  66                 }
  67         }
  68         return g ? g : 1;
  69 }
  70
  71
  72 /*
  73  *    Get the maximum weight of the service destinations.
  74  */
  75 static int ip_vs_wrr_max_weight(struct ip_vs_service *svc)
  76 {
  77         struct ip_vs_dest *dest;
  78         int weight = 0;
  79
  80         list_for_each_entry(dest, &svc->destinations, n_list) {
  81                 if (atomic_read(&dest->weight) > weight)
  82                         weight = atomic_read(&dest->weight);
  83         }
  84
  85         return weight;
  86 }
  87
  88
  89 static int ip_vs_wrr_init_svc(struct ip_vs_service *svc)
  90 {
  91         struct ip_vs_wrr_mark *mark;
  92
  93         /*
  94          *    Allocate the mark variable for WRR scheduling
  95          */
  96         mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_ATOMIC);
  97         if (mark == NULL) {
  98                 IP_VS_ERR("ip_vs_wrr_init_svc(): no memory\n");
  99                 return -ENOMEM;
 100         }
 101         mark->cl = &svc->destinations;
 102         mark->cw = 0;
 103         mark->mw = ip_vs_wrr_max_weight(svc);
 104         mark->di = ip_vs_wrr_gcd_weight(svc);
 105         svc->sched_data = mark;
 106
 107         return 0;
 108 }
 109
 110
 111 static int ip_vs_wrr_done_svc(struct ip_vs_service *svc)
 112 {
 113         /*
 114          *    Release the mark variable
 115          */
 116         kfree(svc->sched_data);
 117
 118         return 0;
 119 }
 120
 121
 122 static int ip_vs_wrr_update_svc(struct ip_vs_service *svc)
 123 {
 124         struct ip_vs_wrr_mark *mark = svc->sched_data;
 125
 126         mark->cl = &svc->destinations;
 127         mark->mw = ip_vs_wrr_max_weight(svc);
 128         mark->di = ip_vs_wrr_gcd_weight(svc);
 129         return 0;
 130 }
 131
 132
 133 /*
 134  *    Weighted Round-Robin Scheduling
 135  */
 136 static struct ip_vs_dest *
 137 ip_vs_wrr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
 138 {
 139         struct ip_vs_dest *dest;
 140         struct ip_vs_wrr_mark *mark = svc->sched_data;
 141         struct list_head *p;
 142
 143         IP_VS_DBG(6, "ip_vs_wrr_schedule(): Scheduling...\n");
 144
 145         /*
 146          * This loop will always terminate, because mark->cw in (0, max_weight]
 147          * and at least one server has its weight equal to max_weight.
 148          */
 149         write_lock(&svc->sched_lock);
 150         p = mark->cl;
 151         while (1) {
 152                 if (mark->cl == &svc->destinations) {
 153                         /* it is at the head of the destination list */
 154
 155                         if (mark->cl == mark->cl->next) {
 156                                 /* no dest entry */
 157                                 dest = NULL;
 158                                 goto out;
 159                         }
 160
 161                         mark->cl = svc->destinations.next;
 162                         mark->cw -= mark->di;
 163                         if (mark->cw <= 0) {
 164                                 mark->cw = mark->mw;
 165                                 /*
 166                                  * Still zero, which means no availabe servers.
 167                                  */
 168                                 if (mark->cw == 0) {
 169                                         mark->cl = &svc->destinations;
 170                                         IP_VS_INFO("ip_vs_wrr_schedule(): "
 171                                                    "no available servers\n");
 172                                         dest = NULL;
 173                                         goto out;
 174                                 }
 175                         }
 176                 } else
 177                         mark->cl = mark->cl->next;
 178
 179                 if (mark->cl != &svc->destinations) {
 180                         /* not at the head of the list */
 181                         dest = list_entry(mark->cl, struct ip_vs_dest, n_list);
 182                         if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) &&
 183                             atomic_read(&dest->weight) >= mark->cw) {
 184                                 /* got it */
 185                                 break;
 186                         }
 187                 }
 188
 189                 if (mark->cl == p) {
 190                         /* back to the start, and no dest is found.
 191                            It is only possible when all dests are OVERLOADED */
 192                         dest = NULL;
 193                         goto out;
 194                 }
 195         }
 196
 197         IP_VS_DBG(6, "WRR: server %u.%u.%u.%u:%u "
 198                   "activeconns %d refcnt %d weight %d\n",
 199                   NIPQUAD(dest->addr), ntohs(dest->port),
 200                   atomic_read(&dest->activeconns),
 201                   atomic_read(&dest->refcnt),
 202                   atomic_read(&dest->weight));
 203
 204   out:
 205         write_unlock(&svc->sched_lock);
 206         return dest;
 207 }
 208
 209
 210 static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
 211         .name =                 "wrr",
 212         .refcnt =               ATOMIC_INIT(0),
 213         .module =               THIS_MODULE,
 214         .init_service =         ip_vs_wrr_init_svc,
 215         .done_service =         ip_vs_wrr_done_svc,
 216         .update_service =       ip_vs_wrr_update_svc,
 217         .schedule =             ip_vs_wrr_schedule,
 218 };
 219
 220 static int __init ip_vs_wrr_init(void)
 221 {
 222         INIT_LIST_HEAD(&ip_vs_wrr_scheduler.n_list);
 223         return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
 224 }
 225
 226 static void __exit ip_vs_wrr_cleanup(void)
 227 {
 228         unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
 229 }
 230
 231 module_init(ip_vs_wrr_init);
 232 module_exit(ip_vs_wrr_cleanup);
 233 MODULE_LICENSE("GPL");