1/*
2 * IPVS:        Weighted Round-Robin Scheduling module
3 *
4 * Version:     $Id: ip_vs_wrr.c,v 1.1.1.1 2007/08/03 18:53:52 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 */
31struct 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 */
42static 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
53static 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 */
75static 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
89static 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
111static 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
122static 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 */
138static struct ip_vs_dest *
139ip_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
212static 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
222static 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
228static void __exit ip_vs_wrr_cleanup(void)
229{
230	unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
231}
232
233module_init(ip_vs_wrr_init);
234module_exit(ip_vs_wrr_cleanup);
235MODULE_LICENSE("GPL");
236