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