~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/ipv4/ipvs/ip_vs_wrr.c

Version: ~ [ linux-5.15-rc1 ] ~ [ linux-5.14.5 ] ~ [ linux-5.13.18 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.66 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.147 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.206 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.246 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.282 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.283 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * IPVS:        Weighted Round-Robin Scheduling module
  3  *
  4  * Version:     $Id: ip_vs_wrr.c,v 1.12 2002/09/15 08:14:08 wensong Exp $
  5  *
  6  * Authors:     Wensong Zhang <wensong@linuxvirtualserver.org>
  7  *
  8  *              This program is free software; you can redistribute it and/or
  9  *              modify it under the terms of the GNU General Public License
 10  *              as published by the Free Software Foundation; either version
 11  *              2 of the License, or (at your option) any later version.
 12  *
 13  * Changes:
 14  *     Wensong Zhang            :     changed the ip_vs_wrr_schedule to return dest
 15  *     Wensong Zhang            :     changed some comestics things for debugging
 16  *     Wensong Zhang            :     changed for the d-linked destination list
 17  *     Wensong Zhang            :     added the ip_vs_wrr_update_svc
 18  *     Julian Anastasov         :     fixed the bug of returning destination
 19  *                                    with weight 0 when all weights are zero
 20  *
 21  */
 22 
 23 #include <linux/config.h>
 24 #include <linux/module.h>
 25 #include <linux/init.h>
 26 #include <linux/types.h>
 27 #include <linux/kernel.h>
 28 #include <linux/errno.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 /*
 44  *    Get the gcd of server weights
 45  */
 46 static int gcd(int a, int b)
 47 {
 48         int c;
 49 
 50         while ((c = a % b)) {
 51                 a = b;
 52                 b = c;
 53         }
 54         return b;
 55 }
 56 
 57 static int ip_vs_wrr_gcd_weight(struct ip_vs_service *svc)
 58 {
 59         struct ip_vs_dest *dest;
 60         int weight;
 61         int g = 0;
 62 
 63         list_for_each_entry(dest, &svc->destinations, n_list) {
 64                 weight = atomic_read(&dest->weight);
 65                 if (weight > 0) {
 66                         if (g > 0)
 67                                 g = gcd(weight, g);
 68                         else
 69                                 g = weight;
 70                 }
 71         }
 72         return g ? g : 1;
 73 }
 74 
 75 
 76 /*
 77  *    Get the maximum weight of the service destinations.
 78  */
 79 static int ip_vs_wrr_max_weight(struct ip_vs_service *svc)
 80 {
 81         struct ip_vs_dest *dest;
 82         int weight = 0;
 83 
 84         list_for_each_entry(dest, &svc->destinations, n_list) {
 85                 if (atomic_read(&dest->weight) > weight)
 86                         weight = atomic_read(&dest->weight);
 87         }
 88 
 89         return weight;
 90 }
 91 
 92 
 93 static int ip_vs_wrr_init_svc(struct ip_vs_service *svc)
 94 {
 95         struct ip_vs_wrr_mark *mark;
 96 
 97         /*
 98          *    Allocate the mark variable for WRR scheduling
 99          */
100         mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_ATOMIC);
101         if (mark == NULL) {
102                 IP_VS_ERR("ip_vs_wrr_init_svc(): no memory\n");
103                 return -ENOMEM;
104         }
105         mark->cl = &svc->destinations;
106         mark->cw = 0;
107         mark->mw = ip_vs_wrr_max_weight(svc);
108         mark->di = ip_vs_wrr_gcd_weight(svc);
109         svc->sched_data = mark;
110 
111         return 0;
112 }
113 
114 
115 static int ip_vs_wrr_done_svc(struct ip_vs_service *svc)
116 {
117         /*
118          *    Release the mark variable
119          */
120         kfree(svc->sched_data);
121 
122         return 0;
123 }
124 
125 
126 static int ip_vs_wrr_update_svc(struct ip_vs_service *svc)
127 {
128         struct ip_vs_wrr_mark *mark = svc->sched_data;
129 
130         mark->cl = &svc->destinations;
131         mark->mw = ip_vs_wrr_max_weight(svc);
132         mark->di = ip_vs_wrr_gcd_weight(svc);
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                                 dest = NULL;
162                                 goto out;
163                         }
164 
165                         mark->cl = svc->destinations.next;
166                         mark->cw -= mark->di;
167                         if (mark->cw <= 0) {
168                                 mark->cw = mark->mw;
169                                 /*
170                                  * Still zero, which means no availabe servers.
171                                  */
172                                 if (mark->cw == 0) {
173                                         mark->cl = &svc->destinations;
174                                         IP_VS_INFO("ip_vs_wrr_schedule(): "
175                                                    "no available servers\n");
176                                         dest = NULL;
177                                         goto out;
178                                 }
179                         }
180                 } else
181                         mark->cl = mark->cl->next;
182 
183                 if (mark->cl != &svc->destinations) {
184                         /* not at the head of the list */
185                         dest = list_entry(mark->cl, struct ip_vs_dest, n_list);
186                         if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) &&
187                             atomic_read(&dest->weight) >= mark->cw) {
188                                 /* got it */
189                                 break;
190                         }
191                 }
192 
193                 if (mark->cl == p) {
194                         /* back to the start, and no dest is found.
195                            It is only possible when all dests are OVERLOADED */
196                         dest = NULL;
197                         goto out;
198                 }
199         }
200 
201         IP_VS_DBG(6, "WRR: server %u.%u.%u.%u:%u "
202                   "activeconns %d refcnt %d weight %d\n",
203                   NIPQUAD(dest->addr), ntohs(dest->port),
204                   atomic_read(&dest->activeconns),
205                   atomic_read(&dest->refcnt),
206                   atomic_read(&dest->weight));
207 
208   out:
209         write_unlock(&svc->sched_lock);
210         return dest;
211 }
212 
213 
214 static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
215         .name =                 "wrr",
216         .refcnt =               ATOMIC_INIT(0),
217         .module =               THIS_MODULE,
218         .init_service =         ip_vs_wrr_init_svc,
219         .done_service =         ip_vs_wrr_done_svc,
220         .update_service =       ip_vs_wrr_update_svc,
221         .schedule =             ip_vs_wrr_schedule,
222 };
223 
224 static int __init ip_vs_wrr_init(void)
225 {
226         INIT_LIST_HEAD(&ip_vs_wrr_scheduler.n_list);
227         return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
228 }
229 
230 static void __exit ip_vs_wrr_cleanup(void)
231 {
232         unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
233 }
234 
235 module_init(ip_vs_wrr_init);
236 module_exit(ip_vs_wrr_cleanup);
237 MODULE_LICENSE("GPL");
238 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp