net/ipv4/ipvs/ip_vs_wrr.c

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