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 */ 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 125 static int __init ip_vs_twos_init(void) 126 { 127 return register_ip_vs_scheduler(&ip_vs_twos_scheduler); 128 } 129 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