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/net.h>
  27 #include <linux/gcd.h>
  28
  29 #include <net/ip_vs.h>
  30
  31 /*
  32  * current destination pointer for weighted round-robin scheduling
  33  */
  34 struct ip_vs_wrr_mark {
  35         struct list_head *cl;   /* current list head */
  36         int cw;                 /* current weight */
  37         int mw;                 /* maximum weight */
  38         int di;                 /* decreasing interval */
  39 };
  40
  41
  42 static int ip_vs_wrr_gcd_weight(struct ip_vs_service *svc)
  43 {
  44         struct ip_vs_dest *dest;
  45         int weight;
  46         int g = 0;
  47
  48         list_for_each_entry(dest, &svc->destinations, n_list) {
  49                 weight = atomic_read(&dest->weight);
  50                 if (weight > 0) {
  51                         if (g > 0)
  52                                 g = gcd(weight, g);
  53                         else
  54                                 g = weight;
  55                 }
  56         }
  57         return g ? g : 1;
  58 }
  59
  60
  61 /*
  62  *    Get the maximum weight of the service destinations.
  63  */
  64 static int ip_vs_wrr_max_weight(struct ip_vs_service *svc)
  65 {
  66         struct ip_vs_dest *dest;
  67         int new_weight, weight = 0;
  68
  69         list_for_each_entry(dest, &svc->destinations, n_list) {
  70                 new_weight = atomic_read(&dest->weight);
  71                 if (new_weight > weight)
  72                         weight = new_weight;
  73         }
  74
  75         return weight;
  76 }
  77
  78
  79 static int ip_vs_wrr_init_svc(struct ip_vs_service *svc)
  80 {
  81         struct ip_vs_wrr_mark *mark;
  82
  83         /*
  84          *    Allocate the mark variable for WRR scheduling
  85          */
  86         mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_ATOMIC);
  87         if (mark == NULL) {
  88                 pr_err("%s(): no memory\n", __func__);
  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_ERR_RL("WRR: no destination available: "
 150                                              "no destinations present\n");
 151                                 dest = NULL;
 152                                 goto out;
 153                         }
 154
 155                         mark->cl = svc->destinations.next;
 156                         mark->cw -= mark->di;
 157                         if (mark->cw <= 0) {
 158                                 mark->cw = mark->mw;
 159                                 /*
 160                                  * Still zero, which means no available servers.
 161                                  */
 162                                 if (mark->cw == 0) {
 163                                         mark->cl = &svc->destinations;
 164                                         IP_VS_ERR_RL("WRR: no destination "
 165                                                      "available\n");
 166                                         dest = NULL;
 167                                         goto out;
 168                                 }
 169                         }
 170                 } else
 171                         mark->cl = mark->cl->next;
 172
 173                 if (mark->cl != &svc->destinations) {
 174                         /* not at the head of the list */
 175                         dest = list_entry(mark->cl, struct ip_vs_dest, n_list);
 176                         if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) &&
 177                             atomic_read(&dest->weight) >= mark->cw) {
 178                                 /* got it */
 179                                 break;
 180                         }
 181                 }
 182
 183                 if (mark->cl == p && mark->cw == mark->di) {
 184                         /* back to the start, and no dest is found.
 185                            It is only possible when all dests are OVERLOADED */
 186                         dest = NULL;
 187                         IP_VS_ERR_RL("WRR: no destination available: "
 188                                      "all destinations are overloaded\n");
 189                         goto out;
 190                 }
 191         }
 192
 193         IP_VS_DBG_BUF(6, "WRR: server %s:%u "
 194                       "activeconns %d refcnt %d weight %d\n",
 195                       IP_VS_DBG_ADDR(svc->af, &dest->addr), ntohs(dest->port),
 196                       atomic_read(&dest->activeconns),
 197                       atomic_read(&dest->refcnt),
 198                       atomic_read(&dest->weight));
 199
 200   out:
 201         write_unlock(&svc->sched_lock);
 202         return dest;
 203 }
 204
 205
 206 static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
 207         .name =                 "wrr",
 208         .refcnt =               ATOMIC_INIT(0),
 209         .module =               THIS_MODULE,
 210         .n_list =               LIST_HEAD_INIT(ip_vs_wrr_scheduler.n_list),
 211         .init_service =         ip_vs_wrr_init_svc,
 212         .done_service =         ip_vs_wrr_done_svc,
 213         .update_service =       ip_vs_wrr_update_svc,
 214         .schedule =             ip_vs_wrr_schedule,
 215 };
 216
 217 static int __init ip_vs_wrr_init(void)
 218 {
 219         return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
 220 }
 221
 222 static void __exit ip_vs_wrr_cleanup(void)
 223 {
 224         unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
 225 }
 226
 227 module_init(ip_vs_wrr_init);
 228 module_exit(ip_vs_wrr_cleanup);
 229 MODULE_LICENSE("GPL");