ip_vs_dh.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * IPVS:        Destination Hashing scheduling module
  4 *
  5 * Authors:     Wensong Zhang <wensong@gnuchina.org>
  6 *
  7 *              Inspired by the consistent hashing scheduler patch from
  8 *              Thomas Proell <proellt@gmx.de>
  9 *
 10 * Changes:
 11 */
 12
 13/*
 14 * The dh algorithm is to select server by the hash key of destination IP
 15 * address. The pseudo code is as follows:
 16 *
 17 *       n <- servernode[dest_ip];
 18 *       if (n is dead) OR
 19 *          (n is overloaded) OR (n.weight <= 0) then
 20 *                 return NULL;
 21 *
 22 *       return n;
 23 *
 24 * Notes that servernode is a 256-bucket hash table that maps the hash
 25 * index derived from packet destination IP address to the current server
 26 * array. If the dh scheduler is used in cache cluster, it is good to
 27 * combine it with cache_bypass feature. When the statically assigned
 28 * server is dead or overloaded, the load balancer can bypass the cache
 29 * server and send requests to the original server directly.
 30 *
 31 */
 32
 33#define pr_fmt(fmt) "IPVS: " fmt
 34
 35#include <linux/ip.h>
 36#include <linux/slab.h>
 37#include <linux/module.h>
 38#include <linux/kernel.h>
 39#include <linux/skbuff.h>
 40#include <linux/hash.h>
 41
 42#include <net/ip_vs.h>
 43
 44
 45/*
 46 *      IPVS DH bucket
 47 */
 48struct ip_vs_dh_bucket {
 49	struct ip_vs_dest __rcu	*dest;	/* real server (cache) */
 50};
 51
 52/*
 53 *     for IPVS DH entry hash table
 54 */
 55#ifndef CONFIG_IP_VS_DH_TAB_BITS
 56#define CONFIG_IP_VS_DH_TAB_BITS        8
 57#endif
 58#define IP_VS_DH_TAB_BITS               CONFIG_IP_VS_DH_TAB_BITS
 59#define IP_VS_DH_TAB_SIZE               (1 << IP_VS_DH_TAB_BITS)
 60#define IP_VS_DH_TAB_MASK               (IP_VS_DH_TAB_SIZE - 1)
 61
 62struct ip_vs_dh_state {
 63	struct ip_vs_dh_bucket		buckets[IP_VS_DH_TAB_SIZE];
 64	struct rcu_head			rcu_head;
 65};
 66
 67/*
 68 *	Returns hash value for IPVS DH entry
 69 */
 70static inline unsigned int ip_vs_dh_hashkey(int af, const union nf_inet_addr *addr)
 71{
 72	__be32 addr_fold = addr->ip;
 73
 74#ifdef CONFIG_IP_VS_IPV6
 75	if (af == AF_INET6)
 76		addr_fold = addr->ip6[0]^addr->ip6[1]^
 77			    addr->ip6[2]^addr->ip6[3];
 78#endif
 79	return hash_32(ntohl(addr_fold), IP_VS_DH_TAB_BITS);
 80}
 81
 82
 83/*
 84 *      Get ip_vs_dest associated with supplied parameters.
 85 */
 86static inline struct ip_vs_dest *
 87ip_vs_dh_get(int af, struct ip_vs_dh_state *s, const union nf_inet_addr *addr)
 88{
 89	return rcu_dereference(s->buckets[ip_vs_dh_hashkey(af, addr)].dest);
 90}
 91
 92
 93/*
 94 *      Assign all the hash buckets of the specified table with the service.
 95 */
 96static int
 97ip_vs_dh_reassign(struct ip_vs_dh_state *s, struct ip_vs_service *svc)
 98{
 99	int i;
100	struct ip_vs_dh_bucket *b;
101	struct list_head *p;
102	struct ip_vs_dest *dest;
103	bool empty;
104
105	b = &s->buckets[0];
106	p = &svc->destinations;
107	empty = list_empty(p);
108	for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
109		dest = rcu_dereference_protected(b->dest, 1);
110		if (dest)
111			ip_vs_dest_put(dest);
112		if (empty)
113			RCU_INIT_POINTER(b->dest, NULL);
114		else {
115			if (p == &svc->destinations)
116				p = p->next;
117
118			dest = list_entry(p, struct ip_vs_dest, n_list);
119			ip_vs_dest_hold(dest);
120			RCU_INIT_POINTER(b->dest, dest);
121
122			p = p->next;
123		}
124		b++;
125	}
126	return 0;
127}
128
129
130/*
131 *      Flush all the hash buckets of the specified table.
132 */
133static void ip_vs_dh_flush(struct ip_vs_dh_state *s)
134{
135	int i;
136	struct ip_vs_dh_bucket *b;
137	struct ip_vs_dest *dest;
138
139	b = &s->buckets[0];
140	for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
141		dest = rcu_dereference_protected(b->dest, 1);
142		if (dest) {
143			ip_vs_dest_put(dest);
144			RCU_INIT_POINTER(b->dest, NULL);
145		}
146		b++;
147	}
148}
149
150
151static int ip_vs_dh_init_svc(struct ip_vs_service *svc)
152{
153	struct ip_vs_dh_state *s;
154
155	/* allocate the DH table for this service */
156	s = kzalloc(sizeof(struct ip_vs_dh_state), GFP_KERNEL);
157	if (s == NULL)
158		return -ENOMEM;
159
160	svc->sched_data = s;
161	IP_VS_DBG(6, "DH hash table (memory=%zdbytes) allocated for "
162		  "current service\n",
163		  sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
164
165	/* assign the hash buckets with current dests */
166	ip_vs_dh_reassign(s, svc);
167
168	return 0;
169}
170
171
172static void ip_vs_dh_done_svc(struct ip_vs_service *svc)
173{
174	struct ip_vs_dh_state *s = svc->sched_data;
175
176	/* got to clean up hash buckets here */
177	ip_vs_dh_flush(s);
178
179	/* release the table itself */
180	kfree_rcu(s, rcu_head);
181	IP_VS_DBG(6, "DH hash table (memory=%zdbytes) released\n",
182		  sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
183}
184
185
186static int ip_vs_dh_dest_changed(struct ip_vs_service *svc,
187				 struct ip_vs_dest *dest)
188{
189	struct ip_vs_dh_state *s = svc->sched_data;
190
191	/* assign the hash buckets with the updated service */
192	ip_vs_dh_reassign(s, svc);
193
194	return 0;
195}
196
197
198/*
199 *      If the dest flags is set with IP_VS_DEST_F_OVERLOAD,
200 *      consider that the server is overloaded here.
201 */
202static inline int is_overloaded(struct ip_vs_dest *dest)
203{
204	return dest->flags & IP_VS_DEST_F_OVERLOAD;
205}
206
207
208/*
209 *      Destination hashing scheduling
210 */
211static struct ip_vs_dest *
212ip_vs_dh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb,
213		  struct ip_vs_iphdr *iph)
214{
215	struct ip_vs_dest *dest;
216	struct ip_vs_dh_state *s;
217
218	IP_VS_DBG(6, "%s(): Scheduling...\n", __func__);
219
220	s = (struct ip_vs_dh_state *) svc->sched_data;
221	dest = ip_vs_dh_get(svc->af, s, &iph->daddr);
222	if (!dest
223	    || !(dest->flags & IP_VS_DEST_F_AVAILABLE)
224	    || atomic_read(&dest->weight) <= 0
225	    || is_overloaded(dest)) {
226		ip_vs_scheduler_err(svc, "no destination available");
227		return NULL;
228	}
229
230	IP_VS_DBG_BUF(6, "DH: destination IP address %s --> server %s:%d\n",
231		      IP_VS_DBG_ADDR(svc->af, &iph->daddr),
232		      IP_VS_DBG_ADDR(dest->af, &dest->addr),
233		      ntohs(dest->port));
234
235	return dest;
236}
237
238
239/*
240 *      IPVS DH Scheduler structure
241 */
242static struct ip_vs_scheduler ip_vs_dh_scheduler =
243{
244	.name =			"dh",
245	.refcnt =		ATOMIC_INIT(0),
246	.module =		THIS_MODULE,
247	.n_list =		LIST_HEAD_INIT(ip_vs_dh_scheduler.n_list),
248	.init_service =		ip_vs_dh_init_svc,
249	.done_service =		ip_vs_dh_done_svc,
250	.add_dest =		ip_vs_dh_dest_changed,
251	.del_dest =		ip_vs_dh_dest_changed,
252	.schedule =		ip_vs_dh_schedule,
253};
254
255
256static int __init ip_vs_dh_init(void)
257{
258	return register_ip_vs_scheduler(&ip_vs_dh_scheduler);
259}
260
261
262static void __exit ip_vs_dh_cleanup(void)
263{
264	unregister_ip_vs_scheduler(&ip_vs_dh_scheduler);
265	synchronize_rcu();
266}
267
268
269module_init(ip_vs_dh_init);
270module_exit(ip_vs_dh_cleanup);
271MODULE_LICENSE("GPL");
272MODULE_DESCRIPTION("ipvs destination hashing scheduler");