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