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