Merge branch 'linus' into cpus4096-for-linus
[linux-2.6] / net / ipv4 / ipvs / ip_vs_nq.c
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 #include <linux/module.h>
35 #include <linux/kernel.h>
36
37 #include <net/ip_vs.h>
38
39
40 static int
41 ip_vs_nq_init_svc(struct ip_vs_service *svc)
42 {
43         return 0;
44 }
45
46
47 static int
48 ip_vs_nq_done_svc(struct ip_vs_service *svc)
49 {
50         return 0;
51 }
52
53
54 static int
55 ip_vs_nq_update_svc(struct ip_vs_service *svc)
56 {
57         return 0;
58 }
59
60
61 static inline unsigned int
62 ip_vs_nq_dest_overhead(struct ip_vs_dest *dest)
63 {
64         /*
65          * We only use the active connection number in the cost
66          * calculation here.
67          */
68         return atomic_read(&dest->activeconns) + 1;
69 }
70
71
72 /*
73  *      Weighted Least Connection scheduling
74  */
75 static struct ip_vs_dest *
76 ip_vs_nq_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
77 {
78         struct ip_vs_dest *dest, *least = NULL;
79         unsigned int loh = 0, doh;
80
81         IP_VS_DBG(6, "ip_vs_nq_schedule(): Scheduling...\n");
82
83         /*
84          * We calculate the load of each dest server as follows:
85          *      (server expected overhead) / dest->weight
86          *
87          * Remember -- no floats in kernel mode!!!
88          * The comparison of h1*w2 > h2*w1 is equivalent to that of
89          *                h1/w1 > h2/w2
90          * if every weight is larger than zero.
91          *
92          * The server with weight=0 is quiesced and will not receive any
93          * new connections.
94          */
95
96         list_for_each_entry(dest, &svc->destinations, n_list) {
97
98                 if (dest->flags & IP_VS_DEST_F_OVERLOAD ||
99                     !atomic_read(&dest->weight))
100                         continue;
101
102                 doh = ip_vs_nq_dest_overhead(dest);
103
104                 /* return the server directly if it is idle */
105                 if (atomic_read(&dest->activeconns) == 0) {
106                         least = dest;
107                         loh = doh;
108                         goto out;
109                 }
110
111                 if (!least ||
112                     (loh * atomic_read(&dest->weight) >
113                      doh * atomic_read(&least->weight))) {
114                         least = dest;
115                         loh = doh;
116                 }
117         }
118
119         if (!least)
120                 return NULL;
121
122   out:
123         IP_VS_DBG(6, "NQ: server %u.%u.%u.%u:%u "
124                   "activeconns %d refcnt %d weight %d overhead %d\n",
125                   NIPQUAD(least->addr), ntohs(least->port),
126                   atomic_read(&least->activeconns),
127                   atomic_read(&least->refcnt),
128                   atomic_read(&least->weight), loh);
129
130         return least;
131 }
132
133
134 static struct ip_vs_scheduler ip_vs_nq_scheduler =
135 {
136         .name =                 "nq",
137         .refcnt =               ATOMIC_INIT(0),
138         .module =               THIS_MODULE,
139         .init_service =         ip_vs_nq_init_svc,
140         .done_service =         ip_vs_nq_done_svc,
141         .update_service =       ip_vs_nq_update_svc,
142         .schedule =             ip_vs_nq_schedule,
143 };
144
145
146 static int __init ip_vs_nq_init(void)
147 {
148         INIT_LIST_HEAD(&ip_vs_nq_scheduler.n_list);
149         return register_ip_vs_scheduler(&ip_vs_nq_scheduler);
150 }
151
152 static void __exit ip_vs_nq_cleanup(void)
153 {
154         unregister_ip_vs_scheduler(&ip_vs_nq_scheduler);
155 }
156
157 module_init(ip_vs_nq_init);
158 module_exit(ip_vs_nq_cleanup);
159 MODULE_LICENSE("GPL");