Based on Google's Maglev algorithm [1][2], this scheduler builds a lookup table in a way disruption is minimized when a change occurs. This helps in case of active/active setup without synchronization. Like for classic source hashing, this lookup table is used to assign connections to a real server. Both source address and port are used to compute the hash (unlike sh where this is optional). Weights are correctly handled. Unlike sh, servers with a weight of 0 are considered as absent. Also, unlike sh, when a server becomes unavailable due to a threshold, no fallback is possible: doing so would seriously impair the the usefulness of using a consistent hash. There is a small hack to detect when all real servers have a weight of 0. It relies on the fact it is not possible for the weight of a real server to change during the execution of the assignment. I believe this is the case as modifications through netlink are subject to a mutex, but the use of atomic_read() is unsettling. The value of 65537 for the hash table size is currently not modifiable at compile-time. This is the value suggested in the Maglev paper. Another possible value is 257 (for small tests) and 655373 (for very large setups). [1]: https://research.google.com/pubs/pub44824.html [2]: https://blog.acolyer.org/2016/03/21/maglev-a-fast-and-reliable-software-network-load-balancer/ Signed-off-by: Vincent Bernat <vincent@xxxxxxxxx> --- include/net/ip_vs.h | 27 ++++ net/netfilter/ipvs/Kconfig | 13 ++ net/netfilter/ipvs/Makefile | 1 + net/netfilter/ipvs/ip_vs_csh.c | 339 +++++++++++++++++++++++++++++++++++++++++ net/netfilter/ipvs/ip_vs_sh.c | 32 +--- 5 files changed, 381 insertions(+), 31 deletions(-) create mode 100644 net/netfilter/ipvs/ip_vs_csh.c diff --git a/include/net/ip_vs.h b/include/net/ip_vs.h index eb0bec043c96..2184b43b7320 100644 --- a/include/net/ip_vs.h +++ b/include/net/ip_vs.h @@ -195,6 +195,33 @@ static inline int ip_vs_addr_equal(int af, const union nf_inet_addr *a, return a->ip == b->ip; } +static inline __be16 ip_vs_get_port(const struct sk_buff *skb, struct ip_vs_iphdr *iph) +{ + __be16 _ports[2], *ports; + + /* At this point we know that we have a valid packet of some kind. + * Because ICMP packets are only guaranteed to have the first 8 + * bytes, let's just grab the ports. Fortunately they're in the + * same position for all three of the protocols we care about. + */ + switch (iph->protocol) { + case IPPROTO_TCP: + case IPPROTO_UDP: + case IPPROTO_SCTP: + ports = skb_header_pointer(skb, iph->len, sizeof(_ports), + &_ports); + if (unlikely(!ports)) + return 0; + + if (likely(!ip_vs_iph_inverse(iph))) + return ports[0]; + else + return ports[1]; + default: + return 0; + } +} + #ifdef CONFIG_IP_VS_DEBUG #include <linux/net.h> diff --git a/net/netfilter/ipvs/Kconfig b/net/netfilter/ipvs/Kconfig index b32fb0dbe237..bfd091e020af 100644 --- a/net/netfilter/ipvs/Kconfig +++ b/net/netfilter/ipvs/Kconfig @@ -225,6 +225,19 @@ config IP_VS_SH If you want to compile it in kernel, say Y. To compile it as a module, choose M here. If unsure, say N. +config IP_VS_CSH + tristate "consistent source hashing scheduling" + ---help--- + The consistent source hashing scheduling algorithm assigns + network connections to the servers through looking up a + statically assigned hash table by their source IP addresses + and ports. The hash table is built to minimize disruption + when a server becomes unavailable. It relies on the Maglev + algorithm. + + If you want to compile it in kernel, say Y. To compile it as a + module, choose M here. If unsure, say N. + config IP_VS_SED tristate "shortest expected delay scheduling" ---help--- diff --git a/net/netfilter/ipvs/Makefile b/net/netfilter/ipvs/Makefile index c552993fa4b9..7d0badf86dfe 100644 --- a/net/netfilter/ipvs/Makefile +++ b/net/netfilter/ipvs/Makefile @@ -33,6 +33,7 @@ obj-$(CONFIG_IP_VS_LBLC) += ip_vs_lblc.o obj-$(CONFIG_IP_VS_LBLCR) += ip_vs_lblcr.o obj-$(CONFIG_IP_VS_DH) += ip_vs_dh.o obj-$(CONFIG_IP_VS_SH) += ip_vs_sh.o +obj-$(CONFIG_IP_VS_CSH) += ip_vs_csh.o obj-$(CONFIG_IP_VS_SED) += ip_vs_sed.o obj-$(CONFIG_IP_VS_NQ) += ip_vs_nq.o diff --git a/net/netfilter/ipvs/ip_vs_csh.c b/net/netfilter/ipvs/ip_vs_csh.c new file mode 100644 index 000000000000..c70db61ba934 --- /dev/null +++ b/net/netfilter/ipvs/ip_vs_csh.c @@ -0,0 +1,339 @@ +/* + * IPVS: Consistent Hashing scheduling module using Google's Maglev + * + * Authors: Vincent Bernat <vincent@xxxxxxxxx> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. + * + * Changes: + * + */ + +/* + * The Maglev algorithm is a consistent hashing algorithm described in + * section 3.4 of "Maglev: A Fast and Reliable Software Network Load + * Balancer" (https://research.google.com/pubs/pub44824.html). + * + * The following pseudo-code from listing in page 6 is implemented + * using M = 65537. Weight is implemented by allowing servers to push + * their candidates several times at each turn. Currently, thresholds + * are ignored. + * + * Both source address and port are used for the hash. IPVS runs after + * fragment reassembly, so source port is always available. + * + */ + +#define KMSG_COMPONENT "IPVS" +#define pr_fmt(fmt) KMSG_COMPONENT ": " fmt + +#include <linux/ip.h> +#include <linux/slab.h> +#include <linux/module.h> +#include <linux/kernel.h> +#include <linux/skbuff.h> + +#include <net/ip_vs.h> + +#include <net/tcp.h> +#include <linux/udp.h> +#include <linux/sctp.h> + +#define IP_VS_CSH_TAB_SIZE 65537 + +/* + * IPVS CSH bucket + */ +struct ip_vs_csh_bucket { + struct ip_vs_dest __rcu *dest; /* real server (cache) */ + bool assigned; +}; + + +struct ip_vs_csh_state { + struct rcu_head rcu_head; + struct ip_vs_csh_bucket buckets[IP_VS_CSH_TAB_SIZE]; +}; + + +/* Helper function to determine if server is unavailable */ +static inline bool is_unavailable(struct ip_vs_dest *dest) +{ + return dest->flags & IP_VS_DEST_F_OVERLOAD; +} + + +/* + * Returns hash value for IPVS CSH entry + */ +static inline unsigned int +ip_vs_csh_hashkey(int af, const union nf_inet_addr *addr, + __be16 port) +{ + __be32 addr_fold = addr->ip; + +#ifdef CONFIG_IP_VS_IPV6 + if (af == AF_INET6) + addr_fold = addr->ip6[0]^addr->ip6[1]^ + addr->ip6[2]^addr->ip6[3]; +#endif + return hash_32(ntohs(port) + ntohl(addr_fold), 32) % IP_VS_CSH_TAB_SIZE; +} + + +/* + * Get ip_vs_dest associated with supplied parameters. + */ +static inline struct ip_vs_dest * +ip_vs_csh_get(struct ip_vs_service *svc, struct ip_vs_csh_state *s, + const union nf_inet_addr *addr, __be16 port) +{ + unsigned int hash = ip_vs_csh_hashkey(svc->af, addr, port); + struct ip_vs_dest *dest = rcu_dereference(s->buckets[hash].dest); + + return (!dest || is_unavailable(dest)) ? NULL : dest; +} + +/* + * For provided destination, return the "j"th element of its permutation. + */ +static inline u32 +ip_vs_csh_permutation(struct ip_vs_dest *d, int j) +{ + u32 offset, skip; + __be32 addr_fold = d->addr.ip; + +#ifdef CONFIG_IP_VS_IPV6 + if (d->af == AF_INET6) + addr_fold = d->addr.ip6[0]^d->addr.ip6[1]^ + d->addr.ip6[2]^d->addr.ip6[3]; +#endif + addr_fold = ntohl(addr_fold) + ntohs(d->port); + offset = hash_32(addr_fold, 32) % IP_VS_CSH_TAB_SIZE; + skip = (hash_32(addr_fold + 1, 32) % (IP_VS_CSH_TAB_SIZE - 1)) + 1; + return (offset + j * skip) % IP_VS_CSH_TAB_SIZE; +} + + +/* + * Flush all the hash buckets of the specified table. + */ +static void ip_vs_csh_flush(struct ip_vs_csh_state *s) +{ + int i; + struct ip_vs_csh_bucket *b; + struct ip_vs_dest *dest; + + b = &s->buckets[0]; + for (i=0; i<IP_VS_CSH_TAB_SIZE; i++) { + dest = rcu_dereference_protected(b->dest, 1); + if (dest) { + ip_vs_dest_put(dest); + RCU_INIT_POINTER(b->dest, NULL); + } + b++; + } +} + + +/* + * Assign all the hash buckets of the specified table with the service. + */ +static int +ip_vs_csh_reassign(struct ip_vs_csh_state *s, struct ip_vs_service *svc) +{ + int n, c, i, j; + struct ip_vs_csh_bucket *b; + struct list_head *p = &svc->destinations; + struct ip_vs_dest *dest, *olddest; + int num_dests = svc->num_dests; + int d_count, weight; + int *next = NULL; + + /* Special case: no real servers */ + if (list_empty(p)) { + ip_vs_csh_flush(s); + return 0; + } + + /* For each destination, reset the position in the permutation + * list. */ + next = kzalloc(sizeof(int) * num_dests, GFP_KERNEL); + if (next == NULL) + return -ENOMEM; + + /* For each bucket, flip the assigned bit: the destination has + * not been set. */ + for (n=0, b = &s->buckets[0]; + n<IP_VS_CSH_TAB_SIZE; + n++, b++) { + b->assigned = false; + } + + d_count = 0; + i = 0; + j = 0; + n = 0; + while (true) { + if (p == &svc->destinations) + p = p->next; + dest = list_entry(p, struct ip_vs_dest, n_list); + weight = atomic_read(&dest->weight); + + if (weight > 0) { + /* Find the next preferred bucket for the destination. */ + ip_vs_dest_hold(dest); + do { + c = ip_vs_csh_permutation(dest, next[i]); + b = &s->buckets[c]; + next[i]++; + } while (b->assigned); + + /* Assign the bucket. */ + b->assigned = 1; + olddest = rcu_dereference_protected(b->dest, 1); + if (olddest) + ip_vs_dest_put(olddest); + RCU_INIT_POINTER(b->dest, dest); + + IP_VS_DBG_BUF(6, "CSH: assigned c: %d dest: %s:%d weight: %d\n", + c, IP_VS_DBG_ADDR(dest->af, &dest->addr), ntohs(dest->port), + atomic_read(&dest->weight)); + if (++n == IP_VS_CSH_TAB_SIZE) break; + } + + if (++j == num_dests && n == 0) { + IP_VS_DBG(6, "CSH: all servers have 0 weight\n"); + ip_vs_csh_flush(s); + break; + } + + /* Don't move to next dest until filling weight */ + if (++d_count >= weight) { + p = p->next; + i = (i + 1) % num_dests; + d_count = 0; + } + } + + kfree(next); + return 0; +} + + +static int ip_vs_csh_init_svc(struct ip_vs_service *svc) +{ + struct ip_vs_csh_state *s; + + /* allocate the SH table for this service */ + s = kzalloc(sizeof(struct ip_vs_csh_state), GFP_KERNEL); + if (s == NULL) + return -ENOMEM; + + svc->sched_data = s; + IP_VS_DBG(6, "CSH: hash table (memory=%zdbytes) allocated for " + "current service\n", + sizeof(struct ip_vs_csh_bucket)*IP_VS_CSH_TAB_SIZE); + + /* assign the hash buckets with current dests */ + ip_vs_csh_reassign(s, svc); + + return 0; +} + + +static void ip_vs_csh_done_svc(struct ip_vs_service *svc) +{ + struct ip_vs_csh_state *s = svc->sched_data; + + /* got to clean up hash buckets here */ + ip_vs_csh_flush(s); + + /* release the table itself */ + kfree_rcu(s, rcu_head); + IP_VS_DBG(6, "CSH: hash table (memory=%zdbytes) released\n", + sizeof(struct ip_vs_csh_bucket)*IP_VS_CSH_TAB_SIZE); +} + + +static int ip_vs_csh_dest_changed(struct ip_vs_service *svc, + struct ip_vs_dest *dest) +{ + struct ip_vs_csh_state *s = svc->sched_data; + + /* assign the hash buckets with the updated service */ + ip_vs_csh_reassign(s, svc); + + return 0; +} + +/* + * Consistent Source Hashing scheduling with Maglev + */ +static struct ip_vs_dest * +ip_vs_csh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb, + struct ip_vs_iphdr *iph) +{ + struct ip_vs_dest *dest; + struct ip_vs_csh_state *s; + __be16 port = 0; + const union nf_inet_addr *hash_addr; + + hash_addr = ip_vs_iph_inverse(iph) ? &iph->daddr : &iph->saddr; + port = ip_vs_get_port(skb, iph); + + s = (struct ip_vs_csh_state *) svc->sched_data; + dest = ip_vs_csh_get(svc, s, hash_addr, port); + + if (!dest) { + ip_vs_scheduler_err(svc, "no destination available"); + return NULL; + } + + IP_VS_DBG_BUF(6, "CSH: source IP address %s:%d --> server %s:%d\n", + IP_VS_DBG_ADDR(svc->af, hash_addr), + ntohs(port), + IP_VS_DBG_ADDR(dest->af, &dest->addr), + ntohs(dest->port)); + + return dest; +} + + +/* + * IPVS CSH Scheduler structure + */ +static struct ip_vs_scheduler ip_vs_csh_scheduler = +{ + .name = "csh", + .refcnt = ATOMIC_INIT(0), + .module = THIS_MODULE, + .n_list = LIST_HEAD_INIT(ip_vs_csh_scheduler.n_list), + .init_service = ip_vs_csh_init_svc, + .done_service = ip_vs_csh_done_svc, + .add_dest = ip_vs_csh_dest_changed, + .del_dest = ip_vs_csh_dest_changed, + .upd_dest = ip_vs_csh_dest_changed, + .schedule = ip_vs_csh_schedule, +}; + + +static int __init ip_vs_csh_init(void) +{ + return register_ip_vs_scheduler(&ip_vs_csh_scheduler); +} + + +static void __exit ip_vs_csh_cleanup(void) +{ + unregister_ip_vs_scheduler(&ip_vs_csh_scheduler); + synchronize_rcu(); +} + + +module_init(ip_vs_csh_init); +module_exit(ip_vs_csh_cleanup); +MODULE_LICENSE("GPL"); diff --git a/net/netfilter/ipvs/ip_vs_sh.c b/net/netfilter/ipvs/ip_vs_sh.c index 16aaac6eedc9..b67565d12b6a 100644 --- a/net/netfilter/ipvs/ip_vs_sh.c +++ b/net/netfilter/ipvs/ip_vs_sh.c @@ -276,36 +276,6 @@ static int ip_vs_sh_dest_changed(struct ip_vs_service *svc, } -/* Helper function to get port number */ -static inline __be16 -ip_vs_sh_get_port(const struct sk_buff *skb, struct ip_vs_iphdr *iph) -{ - __be16 _ports[2], *ports; - - /* At this point we know that we have a valid packet of some kind. - * Because ICMP packets are only guaranteed to have the first 8 - * bytes, let's just grab the ports. Fortunately they're in the - * same position for all three of the protocols we care about. - */ - switch (iph->protocol) { - case IPPROTO_TCP: - case IPPROTO_UDP: - case IPPROTO_SCTP: - ports = skb_header_pointer(skb, iph->len, sizeof(_ports), - &_ports); - if (unlikely(!ports)) - return 0; - - if (likely(!ip_vs_iph_inverse(iph))) - return ports[0]; - else - return ports[1]; - default: - return 0; - } -} - - /* * Source Hashing scheduling */ @@ -323,7 +293,7 @@ ip_vs_sh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb, IP_VS_DBG(6, "ip_vs_sh_schedule(): Scheduling...\n"); if (svc->flags & IP_VS_SVC_F_SCHED_SH_PORT) - port = ip_vs_sh_get_port(skb, iph); + port = ip_vs_get_port(skb, iph); s = (struct ip_vs_sh_state *) svc->sched_data; -- 2.16.3 -- To unsubscribe from this list: send the line "unsubscribe lvs-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
