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                 pr_err("%s(): no memory\n", __func__);
  90                 return -ENOMEM;
  91         }
  92         mark->cl = &svc->destinations;
  93         mark->cw = 0;
  94         mark->mw = ip_vs_wrr_max_weight(svc);
  95         mark->di = ip_vs_wrr_gcd_weight(svc);
  96         svc->sched_data = mark;
  97
  98         return 0;
  99 }
 100
 101
 102 static int ip_vs_wrr_done_svc(struct ip_vs_service *svc)
 103 {
 104         /*
 105          *    Release the mark variable
 106          */
 107         kfree(svc->sched_data);
 108
 109         return 0;
 110 }
 111
 112
 113 static int ip_vs_wrr_update_svc(struct ip_vs_service *svc)
 114 {
 115         struct ip_vs_wrr_mark *mark = svc->sched_data;
 116
 117         mark->cl = &svc->destinations;
 118         mark->mw = ip_vs_wrr_max_weight(svc);
 119         mark->di = ip_vs_wrr_gcd_weight(svc);
 120         if (mark->cw > mark->mw)
 121                 mark->cw = 0;
 122         return 0;
 123 }
 124
 125
 126 /*
 127  *    Weighted Round-Robin Scheduling
 128  */
 129 static struct ip_vs_dest *
 130 ip_vs_wrr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
 131 {
 132         struct ip_vs_dest *dest;
 133         struct ip_vs_wrr_mark *mark = svc->sched_data;
 134         struct list_head *p;
 135
 136         IP_VS_DBG(6, "%s(): Scheduling...\n", __func__);
 137
 138         /*
 139          * This loop will always terminate, because mark->cw in (0, max_weight]
 140          * and at least one server has its weight equal to max_weight.
 141          */
 142         write_lock(&svc->sched_lock);
 143         p = mark->cl;
 144         while (1) {
 145                 if (mark->cl == &svc->destinations) {
 146                         /* it is at the head of the destination list */
 147
 148                         if (mark->cl == mark->cl->next) {
 149                                 /* no dest entry */
 150                                 IP_VS_ERR_RL("WRR: no destination available: "
 151                                              "no destinations present\n");
 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_ERR_RL("WRR: no destination "
 166                                                      "available\n");
 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_ERR_RL("WRR: no destination available: "
 189                                      "all destinations are overloaded\n");
 190                         goto out;
 191                 }
 192         }
 193
 194         IP_VS_DBG_BUF(6, "WRR: server %s:%u "
 195                       "activeconns %d refcnt %d weight %d\n",
 196                       IP_VS_DBG_ADDR(svc->af, &dest->addr), ntohs(dest->port),
 197                       atomic_read(&dest->activeconns),
 198                       atomic_read(&dest->refcnt),
 199                       atomic_read(&dest->weight));
 200
 201   out:
 202         write_unlock(&svc->sched_lock);
 203         return dest;
 204 }
 205
 206
 207 static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
 208         .name =                 "wrr",
 209         .refcnt =               ATOMIC_INIT(0),
 210         .module =               THIS_MODULE,
 211         .n_list =               LIST_HEAD_INIT(ip_vs_wrr_scheduler.n_list),
 212         .init_service =         ip_vs_wrr_init_svc,
 213         .done_service =         ip_vs_wrr_done_svc,
 214         .update_service =       ip_vs_wrr_update_svc,
 215         .schedule =             ip_vs_wrr_schedule,
 216 };
 217
 218 static int __init ip_vs_wrr_init(void)
 219 {
 220         return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
 221 }
 222
 223 static void __exit ip_vs_wrr_cleanup(void)
 224 {
 225         unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
 226 }
 227
 228 module_init(ip_vs_wrr_init);
 229 module_exit(ip_vs_wrr_cleanup);
 230 MODULE_LICENSE("GPL");