Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * IPVS: Source Hashing scheduling module | |
3 | * | |
1da177e4 LT |
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 | * | |
76ad94fc MM |
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 | * | |
1da177e4 LT |
38 | */ |
39 | ||
9aada7ac HE |
40 | #define KMSG_COMPONENT "IPVS" |
41 | #define pr_fmt(fmt) KMSG_COMPONENT ": " fmt | |
42 | ||
14c85021 | 43 | #include <linux/ip.h> |
5a0e3ad6 | 44 | #include <linux/slab.h> |
1da177e4 LT |
45 | #include <linux/module.h> |
46 | #include <linux/kernel.h> | |
14c85021 | 47 | #include <linux/skbuff.h> |
1da177e4 LT |
48 | |
49 | #include <net/ip_vs.h> | |
50 | ||
eba3b5a7 AF |
51 | #include <net/tcp.h> |
52 | #include <linux/udp.h> | |
53 | #include <linux/sctp.h> | |
54 | ||
1da177e4 LT |
55 | |
56 | /* | |
57 | * IPVS SH bucket | |
58 | */ | |
59 | struct ip_vs_sh_bucket { | |
1acb7f67 | 60 | struct ip_vs_dest __rcu *dest; /* real server (cache) */ |
1da177e4 LT |
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 | ||
1acb7f67 | 73 | struct ip_vs_sh_state { |
1acb7f67 | 74 | struct rcu_head rcu_head; |
a70b9641 | 75 | struct ip_vs_sh_bucket buckets[IP_VS_SH_TAB_SIZE]; |
1acb7f67 | 76 | }; |
1da177e4 | 77 | |
eba3b5a7 AF |
78 | /* Helper function to determine if server is unavailable */ |
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 | ||
1da177e4 LT |
85 | /* |
86 | * Returns hash value for IPVS SH entry | |
87 | */ | |
eba3b5a7 AF |
88 | static inline unsigned int |
89 | ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr, | |
90 | __be16 port, unsigned int offset) | |
1da177e4 | 91 | { |
20971a0a JV |
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 | |
eba3b5a7 AF |
99 | return (offset + (ntohs(port) + ntohl(addr_fold))*2654435761UL) & |
100 | IP_VS_SH_TAB_MASK; | |
1da177e4 LT |
101 | } |
102 | ||
103 | ||
104 | /* | |
105 | * Get ip_vs_dest associated with supplied parameters. | |
106 | */ | |
107 | static inline struct ip_vs_dest * | |
eba3b5a7 AF |
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) | |
1da177e4 | 110 | { |
eba3b5a7 AF |
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; | |
1da177e4 LT |
115 | } |
116 | ||
117 | ||
1255ce5f AF |
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 | */ | |
eba3b5a7 AF |
124 | static inline struct ip_vs_dest * |
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 | { | |
1255ce5f AF |
128 | unsigned int offset, roffset; |
129 | unsigned int hash, ihash; | |
eba3b5a7 AF |
130 | struct ip_vs_dest *dest; |
131 | ||
1255ce5f AF |
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", | |
4d316f3f | 141 | IP_VS_DBG_ADDR(dest->af, &dest->addr), ntohs(dest->port)); |
1255ce5f AF |
142 | |
143 | /* if the original dest is unavailable, loop around the table | |
144 | * starting from ihash to find a new dest | |
145 | */ | |
eba3b5a7 | 146 | for (offset = 0; offset < IP_VS_SH_TAB_SIZE; offset++) { |
1255ce5f AF |
147 | roffset = (offset + ihash) % IP_VS_SH_TAB_SIZE; |
148 | hash = ip_vs_sh_hashkey(svc->af, addr, port, roffset); | |
eba3b5a7 AF |
149 | dest = rcu_dereference(s->buckets[hash].dest); |
150 | if (!dest) | |
151 | break; | |
1255ce5f | 152 | if (!is_unavailable(dest)) |
eba3b5a7 | 153 | return dest; |
1255ce5f AF |
154 | IP_VS_DBG_BUF(6, "SH: selected unavailable " |
155 | "server %s:%d (offset %d), reselecting", | |
4d316f3f | 156 | IP_VS_DBG_ADDR(dest->af, &dest->addr), |
1255ce5f | 157 | ntohs(dest->port), roffset); |
eba3b5a7 AF |
158 | } |
159 | ||
160 | return NULL; | |
161 | } | |
162 | ||
1da177e4 LT |
163 | /* |
164 | * Assign all the hash buckets of the specified table with the service. | |
165 | */ | |
166 | static int | |
1acb7f67 | 167 | ip_vs_sh_reassign(struct ip_vs_sh_state *s, struct ip_vs_service *svc) |
1da177e4 LT |
168 | { |
169 | int i; | |
170 | struct ip_vs_sh_bucket *b; | |
171 | struct list_head *p; | |
172 | struct ip_vs_dest *dest; | |
76ad94fc | 173 | int d_count; |
1acb7f67 | 174 | bool empty; |
1da177e4 | 175 | |
1acb7f67 | 176 | b = &s->buckets[0]; |
1da177e4 | 177 | p = &svc->destinations; |
1acb7f67 | 178 | empty = list_empty(p); |
76ad94fc | 179 | d_count = 0; |
1da177e4 | 180 | for (i=0; i<IP_VS_SH_TAB_SIZE; i++) { |
1acb7f67 JA |
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 { | |
1da177e4 LT |
187 | if (p == &svc->destinations) |
188 | p = p->next; | |
189 | ||
190 | dest = list_entry(p, struct ip_vs_dest, n_list); | |
1acb7f67 JA |
191 | ip_vs_dest_hold(dest); |
192 | RCU_INIT_POINTER(b->dest, dest); | |
1da177e4 | 193 | |
76ad94fc | 194 | IP_VS_DBG_BUF(6, "assigned i: %d dest: %s weight: %d\n", |
4d316f3f | 195 | i, IP_VS_DBG_ADDR(dest->af, &dest->addr), |
76ad94fc MM |
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 | ||
1da177e4 LT |
204 | } |
205 | b++; | |
206 | } | |
207 | return 0; | |
208 | } | |
209 | ||
210 | ||
211 | /* | |
212 | * Flush all the hash buckets of the specified table. | |
213 | */ | |
1acb7f67 | 214 | static void ip_vs_sh_flush(struct ip_vs_sh_state *s) |
1da177e4 LT |
215 | { |
216 | int i; | |
217 | struct ip_vs_sh_bucket *b; | |
1acb7f67 | 218 | struct ip_vs_dest *dest; |
1da177e4 | 219 | |
1acb7f67 | 220 | b = &s->buckets[0]; |
1da177e4 | 221 | for (i=0; i<IP_VS_SH_TAB_SIZE; i++) { |
1acb7f67 JA |
222 | dest = rcu_dereference_protected(b->dest, 1); |
223 | if (dest) { | |
224 | ip_vs_dest_put(dest); | |
225 | RCU_INIT_POINTER(b->dest, NULL); | |
1da177e4 LT |
226 | } |
227 | b++; | |
228 | } | |
229 | } | |
230 | ||
231 | ||
232 | static int ip_vs_sh_init_svc(struct ip_vs_service *svc) | |
233 | { | |
1acb7f67 | 234 | struct ip_vs_sh_state *s; |
1da177e4 LT |
235 | |
236 | /* allocate the SH table for this service */ | |
1acb7f67 JA |
237 | s = kzalloc(sizeof(struct ip_vs_sh_state), GFP_KERNEL); |
238 | if (s == NULL) | |
1da177e4 | 239 | return -ENOMEM; |
0a9ee813 | 240 | |
1acb7f67 | 241 | svc->sched_data = s; |
1da177e4 LT |
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 | ||
1acb7f67 JA |
246 | /* assign the hash buckets with current dests */ |
247 | ip_vs_sh_reassign(s, svc); | |
1da177e4 LT |
248 | |
249 | return 0; | |
250 | } | |
251 | ||
252 | ||
ed3ffc4e | 253 | static void ip_vs_sh_done_svc(struct ip_vs_service *svc) |
1da177e4 | 254 | { |
1acb7f67 | 255 | struct ip_vs_sh_state *s = svc->sched_data; |
1da177e4 LT |
256 | |
257 | /* got to clean up hash buckets here */ | |
1acb7f67 | 258 | ip_vs_sh_flush(s); |
1da177e4 LT |
259 | |
260 | /* release the table itself */ | |
1acb7f67 | 261 | kfree_rcu(s, rcu_head); |
1da177e4 LT |
262 | IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) released\n", |
263 | sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE); | |
1da177e4 LT |
264 | } |
265 | ||
266 | ||
1acb7f67 JA |
267 | static int ip_vs_sh_dest_changed(struct ip_vs_service *svc, |
268 | struct ip_vs_dest *dest) | |
1da177e4 | 269 | { |
1acb7f67 | 270 | struct ip_vs_sh_state *s = svc->sched_data; |
1da177e4 LT |
271 | |
272 | /* assign the hash buckets with the updated service */ | |
1acb7f67 | 273 | ip_vs_sh_reassign(s, svc); |
1da177e4 LT |
274 | |
275 | return 0; | |
276 | } | |
277 | ||
278 | ||
eba3b5a7 AF |
279 | /* Helper function to get port number */ |
280 | static inline __be16 | |
281 | ip_vs_sh_get_port(const struct sk_buff *skb, struct ip_vs_iphdr *iph) | |
1da177e4 | 282 | { |
1471f35e | 283 | __be16 _ports[2], *ports; |
eba3b5a7 | 284 | |
1471f35e AG |
285 | /* At this point we know that we have a valid packet of some kind. |
286 | * Because ICMP packets are only guaranteed to have the first 8 | |
287 | * bytes, let's just grab the ports. Fortunately they're in the | |
288 | * same position for all three of the protocols we care about. | |
289 | */ | |
eba3b5a7 AF |
290 | switch (iph->protocol) { |
291 | case IPPROTO_TCP: | |
eba3b5a7 | 292 | case IPPROTO_UDP: |
eba3b5a7 | 293 | case IPPROTO_SCTP: |
1471f35e AG |
294 | ports = skb_header_pointer(skb, iph->len, sizeof(_ports), |
295 | &_ports); | |
296 | if (unlikely(!ports)) | |
54e35cc5 | 297 | return 0; |
1471f35e AG |
298 | |
299 | if (likely(!ip_vs_iph_inverse(iph))) | |
300 | return ports[0]; | |
301 | else | |
302 | return ports[1]; | |
eba3b5a7 | 303 | default: |
1471f35e | 304 | return 0; |
eba3b5a7 | 305 | } |
1da177e4 LT |
306 | } |
307 | ||
308 | ||
309 | /* | |
310 | * Source Hashing scheduling | |
311 | */ | |
312 | static struct ip_vs_dest * | |
bba54de5 JA |
313 | ip_vs_sh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb, |
314 | struct ip_vs_iphdr *iph) | |
1da177e4 LT |
315 | { |
316 | struct ip_vs_dest *dest; | |
1acb7f67 | 317 | struct ip_vs_sh_state *s; |
eba3b5a7 | 318 | __be16 port = 0; |
1471f35e AG |
319 | const union nf_inet_addr *hash_addr; |
320 | ||
321 | hash_addr = ip_vs_iph_inverse(iph) ? &iph->daddr : &iph->saddr; | |
1da177e4 LT |
322 | |
323 | IP_VS_DBG(6, "ip_vs_sh_schedule(): Scheduling...\n"); | |
324 | ||
eba3b5a7 AF |
325 | if (svc->flags & IP_VS_SVC_F_SCHED_SH_PORT) |
326 | port = ip_vs_sh_get_port(skb, iph); | |
327 | ||
1acb7f67 | 328 | s = (struct ip_vs_sh_state *) svc->sched_data; |
eba3b5a7 AF |
329 | |
330 | if (svc->flags & IP_VS_SVC_F_SCHED_SH_FALLBACK) | |
1471f35e | 331 | dest = ip_vs_sh_get_fallback(svc, s, hash_addr, port); |
eba3b5a7 | 332 | else |
1471f35e | 333 | dest = ip_vs_sh_get(svc, s, hash_addr, port); |
eba3b5a7 AF |
334 | |
335 | if (!dest) { | |
41ac51ee | 336 | ip_vs_scheduler_err(svc, "no destination available"); |
1da177e4 LT |
337 | return NULL; |
338 | } | |
339 | ||
20971a0a | 340 | IP_VS_DBG_BUF(6, "SH: source IP address %s --> server %s:%d\n", |
1471f35e | 341 | IP_VS_DBG_ADDR(svc->af, hash_addr), |
4d316f3f | 342 | IP_VS_DBG_ADDR(dest->af, &dest->addr), |
20971a0a | 343 | ntohs(dest->port)); |
1da177e4 LT |
344 | |
345 | return dest; | |
346 | } | |
347 | ||
348 | ||
349 | /* | |
350 | * IPVS SH Scheduler structure | |
351 | */ | |
352 | static struct ip_vs_scheduler ip_vs_sh_scheduler = | |
353 | { | |
354 | .name = "sh", | |
355 | .refcnt = ATOMIC_INIT(0), | |
356 | .module = THIS_MODULE, | |
d149ccc9 | 357 | .n_list = LIST_HEAD_INIT(ip_vs_sh_scheduler.n_list), |
1da177e4 LT |
358 | .init_service = ip_vs_sh_init_svc, |
359 | .done_service = ip_vs_sh_done_svc, | |
1acb7f67 JA |
360 | .add_dest = ip_vs_sh_dest_changed, |
361 | .del_dest = ip_vs_sh_dest_changed, | |
362 | .upd_dest = ip_vs_sh_dest_changed, | |
1da177e4 LT |
363 | .schedule = ip_vs_sh_schedule, |
364 | }; | |
365 | ||
366 | ||
367 | static int __init ip_vs_sh_init(void) | |
368 | { | |
1da177e4 LT |
369 | return register_ip_vs_scheduler(&ip_vs_sh_scheduler); |
370 | } | |
371 | ||
372 | ||
373 | static void __exit ip_vs_sh_cleanup(void) | |
374 | { | |
375 | unregister_ip_vs_scheduler(&ip_vs_sh_scheduler); | |
ceec4c38 | 376 | synchronize_rcu(); |
1da177e4 LT |
377 | } |
378 | ||
379 | ||
380 | module_init(ip_vs_sh_init); | |
381 | module_exit(ip_vs_sh_cleanup); | |
382 | MODULE_LICENSE("GPL"); |