ip_vs_wrr.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * IPVS:        Weighted Round-Robin Scheduling module
  4 *
  5 * Authors:     Wensong Zhang <wensong@linuxvirtualserver.org>
  6 *
  7 * Changes:
  8 *     Wensong Zhang            :     changed the ip_vs_wrr_schedule to return dest
  9 *     Wensong Zhang            :     changed some comestics things for debugging
 10 *     Wensong Zhang            :     changed for the d-linked destination list
 11 *     Wensong Zhang            :     added the ip_vs_wrr_update_svc
 12 *     Julian Anastasov         :     fixed the bug of returning destination
 13 *                                    with weight 0 when all weights are zero
 14 */
 15
 16#define pr_fmt(fmt) "IPVS: " fmt
 17
 18#include <linux/module.h>
 19#include <linux/kernel.h>
 20#include <linux/slab.h>
 21#include <linux/net.h>
 22#include <linux/gcd.h>
 23
 24#include <net/ip_vs.h>
 25
 26/* The WRR algorithm depends on some caclulations:
 27 * - mw: maximum weight
 28 * - di: weight step, greatest common divisor from all weights
 29 * - cw: current required weight
 30 * As result, all weights are in the [di..mw] range with a step=di.
 31 *
 32 * First, we start with cw = mw and select dests with weight >= cw.
 33 * Then cw is reduced with di and all dests are checked again.
 34 * Last pass should be with cw = di. We have mw/di passes in total:
 35 *
 36 * pass 1: cw = max weight
 37 * pass 2: cw = max weight - di
 38 * pass 3: cw = max weight - 2 * di
 39 * ...
 40 * last pass: cw = di
 41 *
 42 * Weights are supposed to be >= di but we run in parallel with
 43 * weight changes, it is possible some dest weight to be reduced
 44 * below di, bad if it is the only available dest.
 45 *
 46 * So, we modify how mw is calculated, now it is reduced with (di - 1),
 47 * so that last cw is 1 to catch such dests with weight below di:
 48 * pass 1: cw = max weight - (di - 1)
 49 * pass 2: cw = max weight - di - (di - 1)
 50 * pass 3: cw = max weight - 2 * di - (di - 1)
 51 * ...
 52 * last pass: cw = 1
 53 *
 54 */
 55
 56/*
 57 * current destination pointer for weighted round-robin scheduling
 58 */
 59struct ip_vs_wrr_mark {
 60	struct ip_vs_dest *cl;	/* current dest or head */
 61	int cw;			/* current weight */
 62	int mw;			/* maximum weight */
 63	int di;			/* decreasing interval */
 64	struct rcu_head		rcu_head;
 65};
 66
 67
 68static int ip_vs_wrr_gcd_weight(struct ip_vs_service *svc)
 69{
 70	struct ip_vs_dest *dest;
 71	int weight;
 72	int g = 0;
 73
 74	list_for_each_entry(dest, &svc->destinations, n_list) {
 75		weight = atomic_read(&dest->weight);
 76		if (weight > 0) {
 77			if (g > 0)
 78				g = gcd(weight, g);
 79			else
 80				g = weight;
 81		}
 82	}
 83	return g ? g : 1;
 84}
 85
 86
 87/*
 88 *    Get the maximum weight of the service destinations.
 89 */
 90static int ip_vs_wrr_max_weight(struct ip_vs_service *svc)
 91{
 92	struct ip_vs_dest *dest;
 93	int new_weight, weight = 0;
 94
 95	list_for_each_entry(dest, &svc->destinations, n_list) {
 96		new_weight = atomic_read(&dest->weight);
 97		if (new_weight > weight)
 98			weight = new_weight;
 99	}
100
101	return weight;
102}
103
104
105static int ip_vs_wrr_init_svc(struct ip_vs_service *svc)
106{
107	struct ip_vs_wrr_mark *mark;
108
109	/*
110	 *    Allocate the mark variable for WRR scheduling
111	 */
112	mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_KERNEL);
113	if (mark == NULL)
114		return -ENOMEM;
115
116	mark->cl = list_entry(&svc->destinations, struct ip_vs_dest, n_list);
117	mark->di = ip_vs_wrr_gcd_weight(svc);
118	mark->mw = ip_vs_wrr_max_weight(svc) - (mark->di - 1);
119	mark->cw = mark->mw;
120	svc->sched_data = mark;
121
122	return 0;
123}
124
125
126static void ip_vs_wrr_done_svc(struct ip_vs_service *svc)
127{
128	struct ip_vs_wrr_mark *mark = svc->sched_data;
129
130	/*
131	 *    Release the mark variable
132	 */
133	kfree_rcu(mark, rcu_head);
134}
135
136
137static int ip_vs_wrr_dest_changed(struct ip_vs_service *svc,
138				  struct ip_vs_dest *dest)
139{
140	struct ip_vs_wrr_mark *mark = svc->sched_data;
141
142	spin_lock_bh(&svc->sched_lock);
143	mark->cl = list_entry(&svc->destinations, struct ip_vs_dest, n_list);
144	mark->di = ip_vs_wrr_gcd_weight(svc);
145	mark->mw = ip_vs_wrr_max_weight(svc) - (mark->di - 1);
146	if (mark->cw > mark->mw || !mark->cw)
147		mark->cw = mark->mw;
148	else if (mark->di > 1)
149		mark->cw = (mark->cw / mark->di) * mark->di + 1;
150	spin_unlock_bh(&svc->sched_lock);
151	return 0;
152}
153
154
155/*
156 *    Weighted Round-Robin Scheduling
157 */
158static struct ip_vs_dest *
159ip_vs_wrr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb,
160		   struct ip_vs_iphdr *iph)
161{
162	struct ip_vs_dest *dest, *last, *stop = NULL;
163	struct ip_vs_wrr_mark *mark = svc->sched_data;
164	bool last_pass = false, restarted = false;
165
166	IP_VS_DBG(6, "%s(): Scheduling...\n", __func__);
167
168	spin_lock_bh(&svc->sched_lock);
169	dest = mark->cl;
170	/* No available dests? */
171	if (mark->mw == 0)
172		goto err_noavail;
173	last = dest;
174	/* Stop only after all dests were checked for weight >= 1 (last pass) */
175	while (1) {
176		list_for_each_entry_continue_rcu(dest,
177						 &svc->destinations,
178						 n_list) {
179			if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) &&
180			    atomic_read(&dest->weight) >= mark->cw)
181				goto found;
182			if (dest == stop)
183				goto err_over;
184		}
185		mark->cw -= mark->di;
186		if (mark->cw <= 0) {
187			mark->cw = mark->mw;
188			/* Stop if we tried last pass from first dest:
189			 * 1. last_pass: we started checks when cw > di but
190			 *	then all dests were checked for w >= 1
191			 * 2. last was head: the first and only traversal
192			 *	was for weight >= 1, for all dests.
193			 */
194			if (last_pass ||
195			    &last->n_list == &svc->destinations)
196				goto err_over;
197			restarted = true;
198		}
199		last_pass = mark->cw <= mark->di;
200		if (last_pass && restarted &&
201		    &last->n_list != &svc->destinations) {
202			/* First traversal was for w >= 1 but only
203			 * for dests after 'last', now do the same
204			 * for all dests up to 'last'.
205			 */
206			stop = last;
207		}
208	}
209
210found:
211	IP_VS_DBG_BUF(6, "WRR: server %s:%u "
212		      "activeconns %d refcnt %d weight %d\n",
213		      IP_VS_DBG_ADDR(dest->af, &dest->addr), ntohs(dest->port),
214		      atomic_read(&dest->activeconns),
215		      refcount_read(&dest->refcnt),
216		      atomic_read(&dest->weight));
217	mark->cl = dest;
218
219  out:
220	spin_unlock_bh(&svc->sched_lock);
221	return dest;
222
223err_noavail:
224	mark->cl = dest;
225	dest = NULL;
226	ip_vs_scheduler_err(svc, "no destination available");
227	goto out;
228
229err_over:
230	mark->cl = dest;
231	dest = NULL;
232	ip_vs_scheduler_err(svc, "no destination available: "
233			    "all destinations are overloaded");
234	goto out;
235}
236
237
238static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
239	.name =			"wrr",
240	.refcnt =		ATOMIC_INIT(0),
241	.module =		THIS_MODULE,
242	.n_list =		LIST_HEAD_INIT(ip_vs_wrr_scheduler.n_list),
243	.init_service =		ip_vs_wrr_init_svc,
244	.done_service =		ip_vs_wrr_done_svc,
245	.add_dest =		ip_vs_wrr_dest_changed,
246	.del_dest =		ip_vs_wrr_dest_changed,
247	.upd_dest =		ip_vs_wrr_dest_changed,
248	.schedule =		ip_vs_wrr_schedule,
249};
250
251static int __init ip_vs_wrr_init(void)
252{
253	return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
254}
255
256static void __exit ip_vs_wrr_cleanup(void)
257{
258	unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler);
259	synchronize_rcu();
260}
261
262module_init(ip_vs_wrr_init);
263module_exit(ip_vs_wrr_cleanup);
264MODULE_LICENSE("GPL");
265MODULE_DESCRIPTION("ipvs weighted round-robin scheduler");