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