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