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