ip_vs_nq.c

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