Merge branch 'davem-next' of master.kernel.org:/pub/scm/linux/kernel/git/jgarzik...
[linux-2.6] / net / ipv4 / ipvs / ip_vs_wrr.c
1 /*
2  * IPVS:        Weighted Round-Robin Scheduling module
3  *
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>
23 #include <linux/net.h>
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;
171                                         IP_VS_ERR_RL("ip_vs_wrr_schedule(): "
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");