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
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.