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