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 | ||
51 | ||
52 | /* | |
53 | * IPVS SH bucket | |
54 | */ | |
55 | struct ip_vs_sh_bucket { | |
56 | struct ip_vs_dest *dest; /* real server (cache) */ | |
57 | }; | |
58 | ||
59 | /* | |
60 | * for IPVS SH entry hash table | |
61 | */ | |
62 | #ifndef CONFIG_IP_VS_SH_TAB_BITS | |
63 | #define CONFIG_IP_VS_SH_TAB_BITS 8 | |
64 | #endif | |
65 | #define IP_VS_SH_TAB_BITS CONFIG_IP_VS_SH_TAB_BITS | |
66 | #define IP_VS_SH_TAB_SIZE (1 << IP_VS_SH_TAB_BITS) | |
67 | #define IP_VS_SH_TAB_MASK (IP_VS_SH_TAB_SIZE - 1) | |
68 | ||
69 | ||
70 | /* | |
71 | * Returns hash value for IPVS SH entry | |
72 | */ | |
95c96174 | 73 | static inline unsigned int ip_vs_sh_hashkey(int af, const union nf_inet_addr *addr) |
1da177e4 | 74 | { |
20971a0a JV |
75 | __be32 addr_fold = addr->ip; |
76 | ||
77 | #ifdef CONFIG_IP_VS_IPV6 | |
78 | if (af == AF_INET6) | |
79 | addr_fold = addr->ip6[0]^addr->ip6[1]^ | |
80 | addr->ip6[2]^addr->ip6[3]; | |
81 | #endif | |
82 | return (ntohl(addr_fold)*2654435761UL) & IP_VS_SH_TAB_MASK; | |
1da177e4 LT |
83 | } |
84 | ||
85 | ||
86 | /* | |
87 | * Get ip_vs_dest associated with supplied parameters. | |
88 | */ | |
89 | static inline struct ip_vs_dest * | |
20971a0a JV |
90 | ip_vs_sh_get(int af, struct ip_vs_sh_bucket *tbl, |
91 | const union nf_inet_addr *addr) | |
1da177e4 | 92 | { |
20971a0a | 93 | return (tbl[ip_vs_sh_hashkey(af, addr)]).dest; |
1da177e4 LT |
94 | } |
95 | ||
96 | ||
97 | /* | |
98 | * Assign all the hash buckets of the specified table with the service. | |
99 | */ | |
100 | static int | |
101 | ip_vs_sh_assign(struct ip_vs_sh_bucket *tbl, struct ip_vs_service *svc) | |
102 | { | |
103 | int i; | |
104 | struct ip_vs_sh_bucket *b; | |
105 | struct list_head *p; | |
106 | struct ip_vs_dest *dest; | |
76ad94fc | 107 | int d_count; |
1da177e4 LT |
108 | |
109 | b = tbl; | |
110 | p = &svc->destinations; | |
76ad94fc | 111 | d_count = 0; |
1da177e4 LT |
112 | for (i=0; i<IP_VS_SH_TAB_SIZE; i++) { |
113 | if (list_empty(p)) { | |
114 | b->dest = NULL; | |
115 | } else { | |
116 | if (p == &svc->destinations) | |
117 | p = p->next; | |
118 | ||
119 | dest = list_entry(p, struct ip_vs_dest, n_list); | |
120 | atomic_inc(&dest->refcnt); | |
121 | b->dest = dest; | |
122 | ||
76ad94fc MM |
123 | IP_VS_DBG_BUF(6, "assigned i: %d dest: %s weight: %d\n", |
124 | i, IP_VS_DBG_ADDR(svc->af, &dest->addr), | |
125 | atomic_read(&dest->weight)); | |
126 | ||
127 | /* Don't move to next dest until filling weight */ | |
128 | if (++d_count >= atomic_read(&dest->weight)) { | |
129 | p = p->next; | |
130 | d_count = 0; | |
131 | } | |
132 | ||
1da177e4 LT |
133 | } |
134 | b++; | |
135 | } | |
136 | return 0; | |
137 | } | |
138 | ||
139 | ||
140 | /* | |
141 | * Flush all the hash buckets of the specified table. | |
142 | */ | |
143 | static void ip_vs_sh_flush(struct ip_vs_sh_bucket *tbl) | |
144 | { | |
145 | int i; | |
146 | struct ip_vs_sh_bucket *b; | |
147 | ||
148 | b = tbl; | |
149 | for (i=0; i<IP_VS_SH_TAB_SIZE; i++) { | |
150 | if (b->dest) { | |
151 | atomic_dec(&b->dest->refcnt); | |
152 | b->dest = NULL; | |
153 | } | |
154 | b++; | |
155 | } | |
156 | } | |
157 | ||
158 | ||
159 | static int ip_vs_sh_init_svc(struct ip_vs_service *svc) | |
160 | { | |
161 | struct ip_vs_sh_bucket *tbl; | |
162 | ||
163 | /* allocate the SH table for this service */ | |
164 | tbl = kmalloc(sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE, | |
165 | GFP_ATOMIC); | |
0a9ee813 | 166 | if (tbl == NULL) |
1da177e4 | 167 | return -ENOMEM; |
0a9ee813 | 168 | |
1da177e4 LT |
169 | svc->sched_data = tbl; |
170 | IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) allocated for " | |
171 | "current service\n", | |
172 | sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE); | |
173 | ||
174 | /* assign the hash buckets with the updated service */ | |
175 | ip_vs_sh_assign(tbl, svc); | |
176 | ||
177 | return 0; | |
178 | } | |
179 | ||
180 | ||
181 | static int ip_vs_sh_done_svc(struct ip_vs_service *svc) | |
182 | { | |
183 | struct ip_vs_sh_bucket *tbl = svc->sched_data; | |
184 | ||
185 | /* got to clean up hash buckets here */ | |
186 | ip_vs_sh_flush(tbl); | |
187 | ||
188 | /* release the table itself */ | |
189 | kfree(svc->sched_data); | |
190 | IP_VS_DBG(6, "SH hash table (memory=%Zdbytes) released\n", | |
191 | sizeof(struct ip_vs_sh_bucket)*IP_VS_SH_TAB_SIZE); | |
192 | ||
193 | return 0; | |
194 | } | |
195 | ||
196 | ||
197 | static int ip_vs_sh_update_svc(struct ip_vs_service *svc) | |
198 | { | |
199 | struct ip_vs_sh_bucket *tbl = svc->sched_data; | |
200 | ||
201 | /* got to clean up hash buckets here */ | |
202 | ip_vs_sh_flush(tbl); | |
203 | ||
204 | /* assign the hash buckets with the updated service */ | |
205 | ip_vs_sh_assign(tbl, svc); | |
206 | ||
207 | return 0; | |
208 | } | |
209 | ||
210 | ||
211 | /* | |
212 | * If the dest flags is set with IP_VS_DEST_F_OVERLOAD, | |
213 | * consider that the server is overloaded here. | |
214 | */ | |
215 | static inline int is_overloaded(struct ip_vs_dest *dest) | |
216 | { | |
217 | return dest->flags & IP_VS_DEST_F_OVERLOAD; | |
218 | } | |
219 | ||
220 | ||
221 | /* | |
222 | * Source Hashing scheduling | |
223 | */ | |
224 | static struct ip_vs_dest * | |
225 | ip_vs_sh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb) | |
226 | { | |
227 | struct ip_vs_dest *dest; | |
228 | struct ip_vs_sh_bucket *tbl; | |
20971a0a JV |
229 | struct ip_vs_iphdr iph; |
230 | ||
231 | ip_vs_fill_iphdr(svc->af, skb_network_header(skb), &iph); | |
1da177e4 LT |
232 | |
233 | IP_VS_DBG(6, "ip_vs_sh_schedule(): Scheduling...\n"); | |
234 | ||
235 | tbl = (struct ip_vs_sh_bucket *)svc->sched_data; | |
20971a0a | 236 | dest = ip_vs_sh_get(svc->af, tbl, &iph.saddr); |
1da177e4 LT |
237 | if (!dest |
238 | || !(dest->flags & IP_VS_DEST_F_AVAILABLE) | |
239 | || atomic_read(&dest->weight) <= 0 | |
240 | || is_overloaded(dest)) { | |
41ac51ee | 241 | ip_vs_scheduler_err(svc, "no destination available"); |
1da177e4 LT |
242 | return NULL; |
243 | } | |
244 | ||
20971a0a JV |
245 | IP_VS_DBG_BUF(6, "SH: source IP address %s --> server %s:%d\n", |
246 | IP_VS_DBG_ADDR(svc->af, &iph.saddr), | |
247 | IP_VS_DBG_ADDR(svc->af, &dest->addr), | |
248 | ntohs(dest->port)); | |
1da177e4 LT |
249 | |
250 | return dest; | |
251 | } | |
252 | ||
253 | ||
254 | /* | |
255 | * IPVS SH Scheduler structure | |
256 | */ | |
257 | static struct ip_vs_scheduler ip_vs_sh_scheduler = | |
258 | { | |
259 | .name = "sh", | |
260 | .refcnt = ATOMIC_INIT(0), | |
261 | .module = THIS_MODULE, | |
d149ccc9 | 262 | .n_list = LIST_HEAD_INIT(ip_vs_sh_scheduler.n_list), |
1da177e4 LT |
263 | .init_service = ip_vs_sh_init_svc, |
264 | .done_service = ip_vs_sh_done_svc, | |
265 | .update_service = ip_vs_sh_update_svc, | |
266 | .schedule = ip_vs_sh_schedule, | |
267 | }; | |
268 | ||
269 | ||
270 | static int __init ip_vs_sh_init(void) | |
271 | { | |
1da177e4 LT |
272 | return register_ip_vs_scheduler(&ip_vs_sh_scheduler); |
273 | } | |
274 | ||
275 | ||
276 | static void __exit ip_vs_sh_cleanup(void) | |
277 | { | |
278 | unregister_ip_vs_scheduler(&ip_vs_sh_scheduler); | |
279 | } | |
280 | ||
281 | ||
282 | module_init(ip_vs_sh_init); | |
283 | module_exit(ip_vs_sh_cleanup); | |
284 | MODULE_LICENSE("GPL"); |