Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * IPVS: Weighted Round-Robin Scheduling module | |
3 | * | |
1da177e4 LT |
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> | |
9c1ca6e6 | 23 | #include <linux/net.h> |
1da177e4 LT |
24 | |
25 | #include <net/ip_vs.h> | |
26 | ||
27 | /* | |
28 | * current destination pointer for weighted round-robin scheduling | |
29 | */ | |
30 | struct 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 | */ | |
41 | static 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 | ||
52 | static 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 | */ | |
74 | static 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 | ||
88 | static 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 | ||
110 | static 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 | ||
121 | static 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 | */ | |
137 | static struct ip_vs_dest * | |
138 | ip_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; | |
9c1ca6e6 | 171 | IP_VS_ERR_RL("ip_vs_wrr_schedule(): " |
1da177e4 LT |
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 | ||
211 | static struct ip_vs_scheduler ip_vs_wrr_scheduler = { | |
212 | .name = "wrr", | |
213 | .refcnt = ATOMIC_INIT(0), | |
214 | .module = THIS_MODULE, | |
215 | .init_service = ip_vs_wrr_init_svc, | |
216 | .done_service = ip_vs_wrr_done_svc, | |
217 | .update_service = ip_vs_wrr_update_svc, | |
218 | .schedule = ip_vs_wrr_schedule, | |
219 | }; | |
220 | ||
221 | static int __init ip_vs_wrr_init(void) | |
222 | { | |
223 | INIT_LIST_HEAD(&ip_vs_wrr_scheduler.n_list); | |
224 | return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ; | |
225 | } | |
226 | ||
227 | static void __exit ip_vs_wrr_cleanup(void) | |
228 | { | |
229 | unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler); | |
230 | } | |
231 | ||
232 | module_init(ip_vs_wrr_init); | |
233 | module_exit(ip_vs_wrr_cleanup); | |
234 | MODULE_LICENSE("GPL"); |