LXR linux/net/netfilter/ipvs/ip_vs

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