1 /*
2 * IPVS: Source Hashing scheduling module
3 *
4 * Authors: Wensong Zhang <wensong@gnuchina.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 sh algorithm is to select server by the hash key of source IP
17 * address. The pseudo code is as follows:
18 *
19 * n <- servernode[src_ip];
20 * if (n is dead) OR
21 * (n is overloaded) or (n.weight <= 0) then
22 * return NULL;
23 *
24 * return n;
25 *
26 * Notes that servernode is a 256-bucket hash table that maps the hash
27 * index derived from packet source IP address to the current server
28 * array. If the sh scheduler is used in cache cluster, it is good to
29 * combine it with cache_bypass feature. When the statically assigned
30 * server is dead or overloaded, the load balancer can bypass the cache
31 * server and send requests to the original server directly.
32 *
33 * The weight destination attribute can be used to control the
34 * distribution of connections to the destinations in servernode. The
35 * greater the weight, the more connections the destination
36 * will receive.
37 *
38 */
39
40 #define KMSG_COMPONENT "IPVS"
41 #define pr_fmt(fmt) KMSG_COMPONENT ": " fmt
42
43 #include <linux/ip.h>
44 #include <linux/slab.h>
45 #include <linux/module.h>
46 #include <linux/kernel.h>
47 #include <linux/skbuff.h>
48
49 #include <net/ip_vs.h>
50
51 #include <net/tcp.h>
52 #include <linux/udp.h>
53 #include <linux/sctp.h>
54
55
56 /*
57 * IPVS SH bucket
58 */
59 struct ip_vs_sh_bucket {
60 struct ip_vs_dest __rcu *dest; /* real server (cache) */
61 };
62
63 /*
64 * for IPVS SH entry hash table
65 */
66 #ifndef CONFIG_IP_VS_SH_TAB_BITS
67 #define CONFIG_IP_VS_SH_TAB_BITS 8
68 #endif
69 #define IP_VS_SH_TAB_BITS CONFIG_IP_VS_SH_TAB_BITS
70 #define IP_VS_SH_TAB_SIZE (1 << IP_VS_SH_TAB_BITS)
71 #define IP_VS_SH_TAB_MASK (IP_VS_SH_TAB_SIZE - 1)
72
73 struct ip_vs_sh_state {
74 struct rcu_head rcu_head;
75 struct ip_vs_sh_bucket buckets[IP_VS_SH_TAB_SIZE];
76 };
77
78 /* Helper function to determine if server is unavailable */
is_unavailable(struct ip_vs_dest * dest)79 static inline bool is_unavailable(struct ip_vs_dest *dest)
80 {
81 return atomic_read(&dest->weight) <= 0 ||
82 dest->flags & IP_VS_DEST_F_OVERLOAD;
83 }
84
85 /*
86 * Returns hash value for IPVS SH entry
87 */
88 static inline unsigned int
ip_vs_sh_hashkey(int af,const union nf_inet_addr * addr,__be16 port,unsigned int offset)89 ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr,
90 __be16 port, unsigned int offset)
91 {
92 __be32 addr_fold = addr->ip;
93
94 #ifdef CONFIG_IP_VS_IPV6
95 if (af == AF_INET6)
96 addr_fold = addr->ip6[0]^addr->ip6[1]^
97 addr->ip6[2]^addr->ip6[3];
98 #endif
99 return (offset + (ntohs(port) + ntohl(addr_fold))*2654435761UL) &
100 IP_VS_SH_TAB_MASK;
101 }
102
103
104 /*
105 * Get ip_vs_dest associated with supplied parameters.
106 */
107 static inline struct ip_vs_dest *
ip_vs_sh_get(struct ip_vs_service * svc,struct ip_vs_sh_state * s,const union nf_inet_addr * addr,__be16 port)108 ip_vs_sh_get(struct ip_vs_service *svc, struct ip_vs_sh_state *s,
109 const union nf_inet_addr *addr, __be16 port)
110 {
111 unsigned int hash = ip_vs_sh_hashkey(svc->af, addr, port, 0);
112 struct ip_vs_dest *dest = rcu_dereference(s->buckets[hash].dest);
113
114 return (!dest || is_unavailable(dest)) ? NULL : dest;
115 }
116
117
118 /* As ip_vs_sh_get, but with fallback if selected server is unavailable
119 *
120 * The fallback strategy loops around the table starting from a "random"
121 * point (in fact, it is chosen to be the original hash value to make the
122 * algorithm deterministic) to find a new server.
123 */
124 static inline struct ip_vs_dest *
ip_vs_sh_get_fallback(struct ip_vs_service * svc,struct ip_vs_sh_state * s,const union nf_inet_addr * addr,__be16 port)125 ip_vs_sh_get_fallback(struct ip_vs_service *svc, struct ip_vs_sh_state *s,
126 const union nf_inet_addr *addr, __be16 port)
127 {
128 unsigned int offset, roffset;
129 unsigned int hash, ihash;
130 struct ip_vs_dest *dest;
131
132 /* first try the dest it's supposed to go to */
133 ihash = ip_vs_sh_hashkey(svc->af, addr, port, 0);
134 dest = rcu_dereference(s->buckets[ihash].dest);
135 if (!dest)
136 return NULL;
137 if (!is_unavailable(dest))
138 return dest;
139
140 IP_VS_DBG_BUF(6, "SH: selected unavailable server %s:%d, reselecting",
141 IP_VS_DBG_ADDR(dest->af, &dest->addr), ntohs(dest->port));
142
143 /* if the original dest is unavailable, loop around the table
144 * starting from ihash to find a new dest
145 */
146 for (offset = 0; offset < IP_VS_SH_TAB_SIZE; offset++) {
147 roffset = (offset + ihash) % IP_VS_SH_TAB_SIZE;
148 hash = ip_vs_sh_hashkey(svc->af, addr, port, roffset);
149 dest = rcu_dereference(s->buckets[hash].dest);
150 if (!dest)
151 break;
152 if (!is_unavailable(dest))
153 return dest;
154 IP_VS_DBG_BUF(6, "SH: selected unavailable "
155 "server %s:%d (offset %d), reselecting",
156 IP_VS_DBG_ADDR(dest->af, &dest->addr),
157 ntohs(dest->port), roffset);
158 }
159
160 return NULL;
161 }
162
163 /*
164 * Assign all the hash buckets of the specified table with the service.
165 */
166 static int
ip_vs_sh_reassign(struct ip_vs_sh_state * s,struct ip_vs_service * svc)167 ip_vs_sh_reassign(struct ip_vs_sh_state *s, struct ip_vs_service *svc)
168 {
169 int i;
170 struct ip_vs_sh_bucket *b;
171 struct list_head *p;
172 struct ip_vs_dest *dest;
173 int d_count;
174 bool empty;
175
176 b = &s->buckets[0];
177 p = &svc->destinations;
178 empty = list_empty(p);
179 d_count = 0;
180 for (i=0; i<IP_VS_SH_TAB_SIZE; i++) {
181 dest = rcu_dereference_protected(b->dest, 1);
182 if (dest)
183 ip_vs_dest_put(dest);
184 if (empty)
185 RCU_INIT_POINTER(b->dest, NULL);
186 else {
187 if (p == &svc->destinations)
188 p = p->next;
189
190 dest = list_entry(p, struct ip_vs_dest, n_list);
191 ip_vs_dest_hold(dest);
192 RCU_INIT_POINTER(b->dest, dest);
193
194 IP_VS_DBG_BUF(6, "assigned i: %d dest: %s weight: %d\n",
195 i, IP_VS_DBG_ADDR(dest->af, &dest->addr),
196 atomic_read(&dest->weight));
197
198 /* Don't move to next dest until filling weight */
199 if (++d_count >= atomic_read(&dest->weight)) {
200 p = p->next;
201 d_count = 0;
202 }
203
204 }
205 b++;
206 }
207 return 0;
208 }
209
210
211 /*
212 * Flush all the hash buckets of the specified table.
213 */
ip_vs_sh_flush(struct ip_vs_sh_state * s)214 static void ip_vs_sh_flush(struct ip_vs_sh_state *s)
215 {
216 int i;
217 struct ip_vs_sh_bucket *b;
218 struct ip_vs_dest *dest;
219
220 b = &s->buckets[0];
221 for (i=0; i<IP_VS_SH_TAB_SIZE; i++) {
222 dest = rcu_dereference_protected(b->dest, 1);
223 if (dest) {
224 ip_vs_dest_put(dest);
225 RCU_INIT_POINTER(b->dest, NULL);
226 }
227 b++;
228 }
229 }
230
231
ip_vs_sh_init_svc(struct ip_vs_service * svc)232 static int ip_vs_sh_init_svc(struct ip_vs_service *svc)
233 {
234 struct ip_vs_sh_state *s;
235
236 /* allocate the SH table for this service */
237 s = kzalloc(sizeof(struct ip_vs_sh_state), GFP_KERNEL);
238 if (s == NULL)
239 return -ENOMEM;
240
241 svc->sched_data = s;
242 IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) allocated for "
243 "current service\n",
244 sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE);
245
246 /* assign the hash buckets with current dests */
247 ip_vs_sh_reassign(s, svc);
248
249 return 0;
250 }
251
252
ip_vs_sh_done_svc(struct ip_vs_service * svc)253 static void ip_vs_sh_done_svc(struct ip_vs_service *svc)
254 {
255 struct ip_vs_sh_state *s = svc->sched_data;
256
257 /* got to clean up hash buckets here */
258 ip_vs_sh_flush(s);
259
260 /* release the table itself */
261 kfree_rcu(s, rcu_head);
262 IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) released\n",
263 sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE);
264 }
265
266
ip_vs_sh_dest_changed(struct ip_vs_service * svc,struct ip_vs_dest * dest)267 static int ip_vs_sh_dest_changed(struct ip_vs_service *svc,
268 struct ip_vs_dest *dest)
269 {
270 struct ip_vs_sh_state *s = svc->sched_data;
271
272 /* assign the hash buckets with the updated service */
273 ip_vs_sh_reassign(s, svc);
274
275 return 0;
276 }
277
278
279 /* Helper function to get port number */
280 static inline __be16
ip_vs_sh_get_port(const struct sk_buff * skb,struct ip_vs_iphdr * iph)281 ip_vs_sh_get_port(const struct sk_buff *skb, struct ip_vs_iphdr *iph)
282 {
283 __be16 port;
284 struct tcphdr _tcph, *th;
285 struct udphdr _udph, *uh;
286 sctp_sctphdr_t _sctph, *sh;
287
288 switch (iph->protocol) {
289 case IPPROTO_TCP:
290 th = skb_header_pointer(skb, iph->len, sizeof(_tcph), &_tcph);
291 if (unlikely(th == NULL))
292 return 0;
293 port = th->source;
294 break;
295 case IPPROTO_UDP:
296 uh = skb_header_pointer(skb, iph->len, sizeof(_udph), &_udph);
297 if (unlikely(uh == NULL))
298 return 0;
299 port = uh->source;
300 break;
301 case IPPROTO_SCTP:
302 sh = skb_header_pointer(skb, iph->len, sizeof(_sctph), &_sctph);
303 if (unlikely(sh == NULL))
304 return 0;
305 port = sh->source;
306 break;
307 default:
308 port = 0;
309 }
310
311 return port;
312 }
313
314
315 /*
316 * Source Hashing scheduling
317 */
318 static struct ip_vs_dest *
ip_vs_sh_schedule(struct ip_vs_service * svc,const struct sk_buff * skb,struct ip_vs_iphdr * iph)319 ip_vs_sh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb,
320 struct ip_vs_iphdr *iph)
321 {
322 struct ip_vs_dest *dest;
323 struct ip_vs_sh_state *s;
324 __be16 port = 0;
325
326 IP_VS_DBG(6, "ip_vs_sh_schedule(): Scheduling...\n");
327
328 if (svc->flags & IP_VS_SVC_F_SCHED_SH_PORT)
329 port = ip_vs_sh_get_port(skb, iph);
330
331 s = (struct ip_vs_sh_state *) svc->sched_data;
332
333 if (svc->flags & IP_VS_SVC_F_SCHED_SH_FALLBACK)
334 dest = ip_vs_sh_get_fallback(svc, s, &iph->saddr, port);
335 else
336 dest = ip_vs_sh_get(svc, s, &iph->saddr, port);
337
338 if (!dest) {
339 ip_vs_scheduler_err(svc, "no destination available");
340 return NULL;
341 }
342
343 IP_VS_DBG_BUF(6, "SH: source IP address %s --> server %s:%d\n",
344 IP_VS_DBG_ADDR(svc->af, &iph->saddr),
345 IP_VS_DBG_ADDR(dest->af, &dest->addr),
346 ntohs(dest->port));
347
348 return dest;
349 }
350
351
352 /*
353 * IPVS SH Scheduler structure
354 */
355 static struct ip_vs_scheduler ip_vs_sh_scheduler =
356 {
357 .name = "sh",
358 .refcnt = ATOMIC_INIT(0),
359 .module = THIS_MODULE,
360 .n_list = LIST_HEAD_INIT(ip_vs_sh_scheduler.n_list),
361 .init_service = ip_vs_sh_init_svc,
362 .done_service = ip_vs_sh_done_svc,
363 .add_dest = ip_vs_sh_dest_changed,
364 .del_dest = ip_vs_sh_dest_changed,
365 .upd_dest = ip_vs_sh_dest_changed,
366 .schedule = ip_vs_sh_schedule,
367 };
368
369
ip_vs_sh_init(void)370 static int __init ip_vs_sh_init(void)
371 {
372 return register_ip_vs_scheduler(&ip_vs_sh_scheduler);
373 }
374
375
ip_vs_sh_cleanup(void)376 static void __exit ip_vs_sh_cleanup(void)
377 {
378 unregister_ip_vs_scheduler(&ip_vs_sh_scheduler);
379 synchronize_rcu();
380 }
381
382
383 module_init(ip_vs_sh_init);
384 module_exit(ip_vs_sh_cleanup);
385 MODULE_LICENSE("GPL");
386