Merge branches 'release', 'acpi_pm_device_sleep_state' and 'battery' into release
[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 #include <linux/net.h>
26
27 #include <net/ip_vs.h>
28
29 /*
30  * current destination pointer for weighted round-robin scheduling
31  */
32 struct 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  */
43 static 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
54 static 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  */
76 static 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
90 static 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
112 static 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
123 static 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  */
139 static struct ip_vs_dest *
140 ip_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
213 static 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
223 static 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
229 static void __exit ip_vs_wrr_cleanup(void)
230 {
231         unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
232 }
233
234 module_init(ip_vs_wrr_init);
235 module_exit(ip_vs_wrr_cleanup);
236 MODULE_LICENSE("GPL");