2 * IPVS: Destination Hashing scheduling module
4 * Authors: Wensong Zhang <wensong@gnuchina.org>
6 * Inspired by the consistent hashing scheduler patch from
7 * Thomas Proell <proellt@gmx.de>
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version
12 * 2 of the License, or (at your option) any later version.
19 * The dh algorithm is to select server by the hash key of destination IP
20 * address. The pseudo code is as follows:
22 * n <- servernode[dest_ip];
24 * (n is overloaded) OR (n.weight <= 0) then
29 * Notes that servernode is a 256-bucket hash table that maps the hash
30 * index derived from packet destination IP address to the current server
31 * array. If the dh scheduler is used in cache cluster, it is good to
32 * combine it with cache_bypass feature. When the statically assigned
33 * server is dead or overloaded, the load balancer can bypass the cache
34 * server and send requests to the original server directly.
38 #define KMSG_COMPONENT "IPVS"
39 #define pr_fmt(fmt) KMSG_COMPONENT ": " fmt
42 #include <linux/slab.h>
43 #include <linux/module.h>
44 #include <linux/kernel.h>
45 #include <linux/skbuff.h>
46 #include <linux/hash.h>
48 #include <net/ip_vs.h>
54 struct ip_vs_dh_bucket {
55 struct ip_vs_dest __rcu *dest; /* real server (cache) */
59 * for IPVS DH entry hash table
61 #ifndef CONFIG_IP_VS_DH_TAB_BITS
62 #define CONFIG_IP_VS_DH_TAB_BITS 8
64 #define IP_VS_DH_TAB_BITS CONFIG_IP_VS_DH_TAB_BITS
65 #define IP_VS_DH_TAB_SIZE (1 << IP_VS_DH_TAB_BITS)
66 #define IP_VS_DH_TAB_MASK (IP_VS_DH_TAB_SIZE - 1)
68 struct ip_vs_dh_state {
69 struct ip_vs_dh_bucket buckets[IP_VS_DH_TAB_SIZE];
70 struct rcu_head rcu_head;
74 * Returns hash value for IPVS DH entry
76 static inline unsigned int ip_vs_dh_hashkey(int af, const union nf_inet_addr *addr)
78 __be32 addr_fold = addr->ip;
80 #ifdef CONFIG_IP_VS_IPV6
82 addr_fold = addr->ip6[0]^addr->ip6[1]^
83 addr->ip6[2]^addr->ip6[3];
85 return hash_32(ntohl(addr_fold), IP_VS_DH_TAB_BITS);
90 * Get ip_vs_dest associated with supplied parameters.
92 static inline struct ip_vs_dest *
93 ip_vs_dh_get(int af, struct ip_vs_dh_state *s, const union nf_inet_addr *addr)
95 return rcu_dereference(s->buckets[ip_vs_dh_hashkey(af, addr)].dest);
100 * Assign all the hash buckets of the specified table with the service.
103 ip_vs_dh_reassign(struct ip_vs_dh_state *s, struct ip_vs_service *svc)
106 struct ip_vs_dh_bucket *b;
108 struct ip_vs_dest *dest;
112 p = &svc->destinations;
113 empty = list_empty(p);
114 for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
115 dest = rcu_dereference_protected(b->dest, 1);
117 ip_vs_dest_put(dest);
119 RCU_INIT_POINTER(b->dest, NULL);
121 if (p == &svc->destinations)
124 dest = list_entry(p, struct ip_vs_dest, n_list);
125 ip_vs_dest_hold(dest);
126 RCU_INIT_POINTER(b->dest, dest);
137 * Flush all the hash buckets of the specified table.
139 static void ip_vs_dh_flush(struct ip_vs_dh_state *s)
142 struct ip_vs_dh_bucket *b;
143 struct ip_vs_dest *dest;
146 for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
147 dest = rcu_dereference_protected(b->dest, 1);
149 ip_vs_dest_put(dest);
150 RCU_INIT_POINTER(b->dest, NULL);
157 static int ip_vs_dh_init_svc(struct ip_vs_service *svc)
159 struct ip_vs_dh_state *s;
161 /* allocate the DH table for this service */
162 s = kzalloc(sizeof(struct ip_vs_dh_state), GFP_KERNEL);
167 IP_VS_DBG(6, "DH hash table (memory=%zdbytes) allocated for "
169 sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
171 /* assign the hash buckets with current dests */
172 ip_vs_dh_reassign(s, svc);
178 static void ip_vs_dh_done_svc(struct ip_vs_service *svc)
180 struct ip_vs_dh_state *s = svc->sched_data;
182 /* got to clean up hash buckets here */
185 /* release the table itself */
186 kfree_rcu(s, rcu_head);
187 IP_VS_DBG(6, "DH hash table (memory=%zdbytes) released\n",
188 sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
192 static int ip_vs_dh_dest_changed(struct ip_vs_service *svc,
193 struct ip_vs_dest *dest)
195 struct ip_vs_dh_state *s = svc->sched_data;
197 /* assign the hash buckets with the updated service */
198 ip_vs_dh_reassign(s, svc);
205 * If the dest flags is set with IP_VS_DEST_F_OVERLOAD,
206 * consider that the server is overloaded here.
208 static inline int is_overloaded(struct ip_vs_dest *dest)
210 return dest->flags & IP_VS_DEST_F_OVERLOAD;
215 * Destination hashing scheduling
217 static struct ip_vs_dest *
218 ip_vs_dh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb,
219 struct ip_vs_iphdr *iph)
221 struct ip_vs_dest *dest;
222 struct ip_vs_dh_state *s;
224 IP_VS_DBG(6, "%s(): Scheduling...\n", __func__);
226 s = (struct ip_vs_dh_state *) svc->sched_data;
227 dest = ip_vs_dh_get(svc->af, s, &iph->daddr);
229 || !(dest->flags & IP_VS_DEST_F_AVAILABLE)
230 || atomic_read(&dest->weight) <= 0
231 || is_overloaded(dest)) {
232 ip_vs_scheduler_err(svc, "no destination available");
236 IP_VS_DBG_BUF(6, "DH: destination IP address %s --> server %s:%d\n",
237 IP_VS_DBG_ADDR(svc->af, &iph->daddr),
238 IP_VS_DBG_ADDR(dest->af, &dest->addr),
246 * IPVS DH Scheduler structure
248 static struct ip_vs_scheduler ip_vs_dh_scheduler =
251 .refcnt = ATOMIC_INIT(0),
252 .module = THIS_MODULE,
253 .n_list = LIST_HEAD_INIT(ip_vs_dh_scheduler.n_list),
254 .init_service = ip_vs_dh_init_svc,
255 .done_service = ip_vs_dh_done_svc,
256 .add_dest = ip_vs_dh_dest_changed,
257 .del_dest = ip_vs_dh_dest_changed,
258 .schedule = ip_vs_dh_schedule,
262 static int __init ip_vs_dh_init(void)
264 return register_ip_vs_scheduler(&ip_vs_dh_scheduler);
268 static void __exit ip_vs_dh_cleanup(void)
270 unregister_ip_vs_scheduler(&ip_vs_dh_scheduler);
275 module_init(ip_vs_dh_init);
276 module_exit(ip_vs_dh_cleanup);
277 MODULE_LICENSE("GPL");