1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* IPVS: Power of Twos Choice Scheduling module
3 *
4 * Authors: Darby Payne <darby.payne@applovin.com>
5 */
6
7 #define pr_fmt(fmt) "IPVS: " fmt
8
9 #include <linux/kernel.h>
10 #include <linux/module.h>
11 #include <linux/random.h>
12
13 #include <net/ip_vs.h>
14
15 /* Power of Twos Choice scheduling, algorithm originally described by
16 * Michael Mitzenmacher.
17 *
18 * Randomly picks two destinations and picks the one with the least
19 * amount of connections
20 *
21 * The algorithm calculates a few variables
22 * - total_weight = sum of all weights
23 * - rweight1 = random number between [0,total_weight]
24 * - rweight2 = random number between [0,total_weight]
25 *
26 * For each destination
27 * decrement rweight1 and rweight2 by the destination weight
28 * pick choice1 when rweight1 is <= 0
29 * pick choice2 when rweight2 is <= 0
30 *
31 * Return choice2 if choice2 has less connections than choice 1 normalized
32 * by weight
33 *
34 * References
35 * ----------
36 *
37 * [Mitzenmacher 2016]
38 * The Power of Two Random Choices: A Survey of Techniques and Results
39 * Michael Mitzenmacher, Andrea W. Richa y, Ramesh Sitaraman
40 * http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/twosurvey.pdf
41 *
42 */
ip_vs_twos_schedule(struct ip_vs_service * svc,const struct sk_buff * skb,struct ip_vs_iphdr * iph)43 static struct ip_vs_dest *ip_vs_twos_schedule(struct ip_vs_service *svc,
44 const struct sk_buff *skb,
45 struct ip_vs_iphdr *iph)
46 {
47 struct ip_vs_dest *dest, *choice1 = NULL, *choice2 = NULL;
48 int rweight1, rweight2, weight1 = -1, weight2 = -1, overhead1 = 0;
49 int overhead2, total_weight = 0, weight;
50
51 IP_VS_DBG(6, "%s(): Scheduling...\n", __func__);
52
53 /* Generate a random weight between [0,sum of all weights) */
54 list_for_each_entry_rcu(dest, &svc->destinations, n_list) {
55 if (!(dest->flags & IP_VS_DEST_F_OVERLOAD)) {
56 weight = atomic_read(&dest->weight);
57 if (weight > 0) {
58 total_weight += weight;
59 choice1 = dest;
60 }
61 }
62 }
63
64 if (!choice1) {
65 ip_vs_scheduler_err(svc, "no destination available");
66 return NULL;
67 }
68
69 /* Add 1 to total_weight so that the random weights are inclusive
70 * from 0 to total_weight
71 */
72 total_weight += 1;
73 rweight1 = get_random_u32_below(total_weight);
74 rweight2 = get_random_u32_below(total_weight);
75
76 /* Pick two weighted servers */
77 list_for_each_entry_rcu(dest, &svc->destinations, n_list) {
78 if (dest->flags & IP_VS_DEST_F_OVERLOAD)
79 continue;
80
81 weight = atomic_read(&dest->weight);
82 if (weight <= 0)
83 continue;
84
85 rweight1 -= weight;
86 rweight2 -= weight;
87
88 if (rweight1 <= 0 && weight1 == -1) {
89 choice1 = dest;
90 weight1 = weight;
91 overhead1 = ip_vs_dest_conn_overhead(dest);
92 }
93
94 if (rweight2 <= 0 && weight2 == -1) {
95 choice2 = dest;
96 weight2 = weight;
97 overhead2 = ip_vs_dest_conn_overhead(dest);
98 }
99
100 if (weight1 != -1 && weight2 != -1)
101 goto nextstage;
102 }
103
104 nextstage:
105 if (choice2 && (weight2 * overhead1) > (weight1 * overhead2))
106 choice1 = choice2;
107
108 IP_VS_DBG_BUF(6, "twos: server %s:%u conns %d refcnt %d weight %d\n",
109 IP_VS_DBG_ADDR(choice1->af, &choice1->addr),
110 ntohs(choice1->port), atomic_read(&choice1->activeconns),
111 refcount_read(&choice1->refcnt),
112 atomic_read(&choice1->weight));
113
114 return choice1;
115 }
116
117 static struct ip_vs_scheduler ip_vs_twos_scheduler = {
118 .name = "twos",
119 .refcnt = ATOMIC_INIT(0),
120 .module = THIS_MODULE,
121 .n_list = LIST_HEAD_INIT(ip_vs_twos_scheduler.n_list),
122 .schedule = ip_vs_twos_schedule,
123 };
124
ip_vs_twos_init(void)125 static int __init ip_vs_twos_init(void)
126 {
127 return register_ip_vs_scheduler(&ip_vs_twos_scheduler);
128 }
129
ip_vs_twos_cleanup(void)130 static void __exit ip_vs_twos_cleanup(void)
131 {
132 unregister_ip_vs_scheduler(&ip_vs_twos_scheduler);
133 synchronize_rcu();
134 }
135
136 module_init(ip_vs_twos_init);
137 module_exit(ip_vs_twos_cleanup);
138 MODULE_LICENSE("GPL");
139 MODULE_DESCRIPTION("ipvs power of twos choice scheduler");
140