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