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