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

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

Version: ~ [ linux-5.18 ] ~ [ linux-5.17.9 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.41 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.117 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.195 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.244 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.280 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.315 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ 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.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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");
243 

~ [ 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