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