1/* 2 * IPVS: Weighted Round-Robin Scheduling module 3 * 4 * Version: $Id: ip_vs_wrr.c,v 1.1.1.1 2007/08/03 18:53:52 Exp $ 5 * 6 * Authors: Wensong Zhang <wensong@linuxvirtualserver.org> 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License 10 * as published by the Free Software Foundation; either version 11 * 2 of the License, or (at your option) any later version. 12 * 13 * Changes: 14 * Wensong Zhang : changed the ip_vs_wrr_schedule to return dest 15 * Wensong Zhang : changed some comestics things for debugging 16 * Wensong Zhang : changed for the d-linked destination list 17 * Wensong Zhang : added the ip_vs_wrr_update_svc 18 * Julian Anastasov : fixed the bug of returning destination 19 * with weight 0 when all weights are zero 20 * 21 */ 22 23#include <linux/module.h> 24#include <linux/kernel.h> 25 26#include <net/ip_vs.h> 27 28/* 29 * current destination pointer for weighted round-robin scheduling 30 */ 31struct ip_vs_wrr_mark { 32 struct list_head *cl; /* current list head */ 33 int cw; /* current weight */ 34 int mw; /* maximum weight */ 35 int di; /* decreasing interval */ 36}; 37 38 39/* 40 * Get the gcd of server weights 41 */ 42static int gcd(int a, int b) 43{ 44 int c; 45 46 while ((c = a % b)) { 47 a = b; 48 b = c; 49 } 50 return b; 51} 52 53static int ip_vs_wrr_gcd_weight(struct ip_vs_service *svc) 54{ 55 struct ip_vs_dest *dest; 56 int weight; 57 int g = 0; 58 59 list_for_each_entry(dest, &svc->destinations, n_list) { 60 weight = atomic_read(&dest->weight); 61 if (weight > 0) { 62 if (g > 0) 63 g = gcd(weight, g); 64 else 65 g = weight; 66 } 67 } 68 return g ? g : 1; 69} 70 71 72/* 73 * Get the maximum weight of the service destinations. 74 */ 75static int ip_vs_wrr_max_weight(struct ip_vs_service *svc) 76{ 77 struct ip_vs_dest *dest; 78 int weight = 0; 79 80 list_for_each_entry(dest, &svc->destinations, n_list) { 81 if (atomic_read(&dest->weight) > weight) 82 weight = atomic_read(&dest->weight); 83 } 84 85 return weight; 86} 87 88 89static int ip_vs_wrr_init_svc(struct ip_vs_service *svc) 90{ 91 struct ip_vs_wrr_mark *mark; 92 93 /* 94 * Allocate the mark variable for WRR scheduling 95 */ 96 mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_ATOMIC); 97 if (mark == NULL) { 98 IP_VS_ERR("ip_vs_wrr_init_svc(): no memory\n"); 99 return -ENOMEM; 100 } 101 mark->cl = &svc->destinations; 102 mark->cw = 0; 103 mark->mw = ip_vs_wrr_max_weight(svc); 104 mark->di = ip_vs_wrr_gcd_weight(svc); 105 svc->sched_data = mark; 106 107 return 0; 108} 109 110 111static int ip_vs_wrr_done_svc(struct ip_vs_service *svc) 112{ 113 /* 114 * Release the mark variable 115 */ 116 kfree(svc->sched_data); 117 118 return 0; 119} 120 121 122static int ip_vs_wrr_update_svc(struct ip_vs_service *svc) 123{ 124 struct ip_vs_wrr_mark *mark = svc->sched_data; 125 126 mark->cl = &svc->destinations; 127 mark->mw = ip_vs_wrr_max_weight(svc); 128 mark->di = ip_vs_wrr_gcd_weight(svc); 129 if (mark->cw > mark->mw) 130 mark->cw = 0; 131 return 0; 132} 133 134 135/* 136 * Weighted Round-Robin Scheduling 137 */ 138static struct ip_vs_dest * 139ip_vs_wrr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb) 140{ 141 struct ip_vs_dest *dest; 142 struct ip_vs_wrr_mark *mark = svc->sched_data; 143 struct list_head *p; 144 145 IP_VS_DBG(6, "ip_vs_wrr_schedule(): Scheduling...\n"); 146 147 /* 148 * This loop will always terminate, because mark->cw in (0, max_weight] 149 * and at least one server has its weight equal to max_weight. 150 */ 151 write_lock(&svc->sched_lock); 152 p = mark->cl; 153 while (1) { 154 if (mark->cl == &svc->destinations) { 155 /* it is at the head of the destination list */ 156 157 if (mark->cl == mark->cl->next) { 158 /* no dest entry */ 159 dest = NULL; 160 goto out; 161 } 162 163 mark->cl = svc->destinations.next; 164 mark->cw -= mark->di; 165 if (mark->cw <= 0) { 166 mark->cw = mark->mw; 167 /* 168 * Still zero, which means no available servers. 169 */ 170 if (mark->cw == 0) { 171 mark->cl = &svc->destinations; 172 IP_VS_INFO("ip_vs_wrr_schedule(): " 173 "no available servers\n"); 174 dest = NULL; 175 goto out; 176 } 177 } 178 } else 179 mark->cl = mark->cl->next; 180 181 if (mark->cl != &svc->destinations) { 182 /* not at the head of the list */ 183 dest = list_entry(mark->cl, struct ip_vs_dest, n_list); 184 if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) && 185 atomic_read(&dest->weight) >= mark->cw) { 186 /* got it */ 187 break; 188 } 189 } 190 191 if (mark->cl == p && mark->cw == mark->di) { 192 /* back to the start, and no dest is found. 193 It is only possible when all dests are OVERLOADED */ 194 dest = NULL; 195 goto out; 196 } 197 } 198 199 IP_VS_DBG(6, "WRR: server %u.%u.%u.%u:%u " 200 "activeconns %d refcnt %d weight %d\n", 201 NIPQUAD(dest->addr), ntohs(dest->port), 202 atomic_read(&dest->activeconns), 203 atomic_read(&dest->refcnt), 204 atomic_read(&dest->weight)); 205 206 out: 207 write_unlock(&svc->sched_lock); 208 return dest; 209} 210 211 212static struct ip_vs_scheduler ip_vs_wrr_scheduler = { 213 .name = "wrr", 214 .refcnt = ATOMIC_INIT(0), 215 .module = THIS_MODULE, 216 .init_service = ip_vs_wrr_init_svc, 217 .done_service = ip_vs_wrr_done_svc, 218 .update_service = ip_vs_wrr_update_svc, 219 .schedule = ip_vs_wrr_schedule, 220}; 221 222static int __init ip_vs_wrr_init(void) 223{ 224 INIT_LIST_HEAD(&ip_vs_wrr_scheduler.n_list); 225 return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ; 226} 227 228static void __exit ip_vs_wrr_cleanup(void) 229{ 230 unregister_ip_vs_scheduler(&ip_vs_wrr_scheduler); 231} 232 233module_init(ip_vs_wrr_init); 234module_exit(ip_vs_wrr_cleanup); 235MODULE_LICENSE("GPL"); 236