ip_vs_sed.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * IPVS:        Shortest Expected Delay scheduling module
  4 *
  5 * Authors:     Wensong Zhang <wensong@linuxvirtualserver.org>
  6 *
  7 * Changes:
  8 */
  9
 10/*
 11 * The SED algorithm attempts to minimize each job's expected delay until
 12 * completion. The expected delay that the job will experience is
 13 * (Ci + 1) / Ui if sent to the ith server, in which Ci is the number of
 14 * jobs on the ith server and Ui is the fixed service rate (weight) of
 15 * the ith server. The SED algorithm adopts a greedy policy that each does
 16 * what is in its own best interest, i.e. to join the queue which would
 17 * minimize its expected delay of completion.
 18 *
 19 * See the following paper for more information:
 20 * A. Weinrib and S. Shenker, Greed is not enough: Adaptive load sharing
 21 * in large heterogeneous systems. In Proceedings IEEE INFOCOM'88,
 22 * pages 986-994, 1988.
 23 *
 24 * Thanks must go to Marko Buuri <marko@buuri.name> for talking SED to me.
 25 *
 26 * The difference between SED and WLC is that SED includes the incoming
 27 * job in the cost function (the increment of 1). SED may outperform
 28 * WLC, while scheduling big jobs under larger heterogeneous systems
 29 * (the server weight varies a lot).
 30 *
 31 */
 32
 33#define pr_fmt(fmt) "IPVS: " fmt
 34
 35#include <linux/module.h>
 36#include <linux/kernel.h>
 37
 38#include <net/ip_vs.h>
 39
 40
 41static inline int
 42ip_vs_sed_dest_overhead(struct ip_vs_dest *dest)
 43{
 44	/*
 45	 * We only use the active connection number in the cost
 46	 * calculation here.
 47	 */
 48	return atomic_read(&dest->activeconns) + 1;
 49}
 50
 51
 52/*
 53 *	Weighted Least Connection scheduling
 54 */
 55static struct ip_vs_dest *
 56ip_vs_sed_schedule(struct ip_vs_service *svc, const struct sk_buff *skb,
 57		   struct ip_vs_iphdr *iph)
 58{
 59	struct ip_vs_dest *dest, *least;
 60	int loh, doh;
 61
 62	IP_VS_DBG(6, "%s(): Scheduling...\n", __func__);
 63
 64	/*
 65	 * We calculate the load of each dest server as follows:
 66	 *	(server expected overhead) / dest->weight
 67	 *
 68	 * Remember -- no floats in kernel mode!!!
 69	 * The comparison of h1*w2 > h2*w1 is equivalent to that of
 70	 *		  h1/w1 > h2/w2
 71	 * if every weight is larger than zero.
 72	 *
 73	 * The server with weight=0 is quiesced and will not receive any
 74	 * new connections.
 75	 */
 76
 77	list_for_each_entry_rcu(dest, &svc->destinations, n_list) {
 78		if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) &&
 79		    atomic_read(&dest->weight) > 0) {
 80			least = dest;
 81			loh = ip_vs_sed_dest_overhead(least);
 82			goto nextstage;
 83		}
 84	}
 85	ip_vs_scheduler_err(svc, "no destination available");
 86	return NULL;
 87
 88	/*
 89	 *    Find the destination with the least load.
 90	 */
 91  nextstage:
 92	list_for_each_entry_continue_rcu(dest, &svc->destinations, n_list) {
 93		if (dest->flags & IP_VS_DEST_F_OVERLOAD)
 94			continue;
 95		doh = ip_vs_sed_dest_overhead(dest);
 96		if ((__s64)loh * atomic_read(&dest->weight) >
 97		    (__s64)doh * atomic_read(&least->weight)) {
 98			least = dest;
 99			loh = doh;
100		}
101	}
102
103	IP_VS_DBG_BUF(6, "SED: server %s:%u "
104		      "activeconns %d refcnt %d weight %d overhead %d\n",
105		      IP_VS_DBG_ADDR(least->af, &least->addr),
106		      ntohs(least->port),
107		      atomic_read(&least->activeconns),
108		      refcount_read(&least->refcnt),
109		      atomic_read(&least->weight), loh);
110
111	return least;
112}
113
114
115static struct ip_vs_scheduler ip_vs_sed_scheduler =
116{
117	.name =			"sed",
118	.refcnt =		ATOMIC_INIT(0),
119	.module =		THIS_MODULE,
120	.n_list =		LIST_HEAD_INIT(ip_vs_sed_scheduler.n_list),
121	.schedule =		ip_vs_sed_schedule,
122};
123
124
125static int __init ip_vs_sed_init(void)
126{
127	return register_ip_vs_scheduler(&ip_vs_sed_scheduler);
128}
129
130static void __exit ip_vs_sed_cleanup(void)
131{
132	unregister_ip_vs_scheduler(&ip_vs_sed_scheduler);
133	synchronize_rcu();
134}
135
136module_init(ip_vs_sed_init);
137module_exit(ip_vs_sed_cleanup);
138MODULE_LICENSE("GPL");
139MODULE_DESCRIPTION("ipvs shortest expected delay scheduler");