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