1 /*
2 * Fast Weighted Least Connection load balancing algorithm.
3 *
4 * Copyright 2000-2009 Willy Tarreau <w@1wt.eu>
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 */
12
13 #include <common/compat.h>
14 #include <common/config.h>
15 #include <common/debug.h>
16 #include <eb32tree.h>
17
18 #include <types/global.h>
19 #include <types/server.h>
20
21 #include <proto/backend.h>
22 #include <proto/queue.h>
23
24
25 /* Remove a server from a tree. It must have previously been dequeued. This
26 * function is meant to be called when a server is going down or has its
27 * weight disabled.
28 */
fwlc_remove_from_tree(struct server * s)29 static inline void fwlc_remove_from_tree(struct server *s)
30 {
31 s->lb_tree = NULL;
32 }
33
34 /* simply removes a server from a tree */
fwlc_dequeue_srv(struct server * s)35 static inline void fwlc_dequeue_srv(struct server *s)
36 {
37 eb32_delete(&s->lb_node);
38 }
39
40 /* Queue a server in its associated tree, assuming the weight is >0.
41 * Servers are sorted by #conns/weight. To ensure maximum accuracy,
42 * we use #conns*SRV_EWGHT_MAX/eweight as the sorting key.
43 */
fwlc_queue_srv(struct server * s)44 static inline void fwlc_queue_srv(struct server *s)
45 {
46 s->lb_node.key = s->served * SRV_EWGHT_MAX / s->eweight;
47 eb32_insert(s->lb_tree, &s->lb_node);
48 }
49
50 /* Re-position the server in the FWLC tree after it has been assigned one
51 * connection or after it has released one. Note that it is possible that
52 * the server has been moved out of the tree due to failed health-checks.
53 */
fwlc_srv_reposition(struct server * s)54 static void fwlc_srv_reposition(struct server *s)
55 {
56 if (!s->lb_tree)
57 return;
58 fwlc_dequeue_srv(s);
59 fwlc_queue_srv(s);
60 }
61
62 /* This function updates the server trees according to server <srv>'s new
63 * state. It should be called when server <srv>'s status changes to down.
64 * It is not important whether the server was already down or not. It is not
65 * important either that the new state is completely down (the caller may not
66 * know all the variables of a server's state).
67 */
fwlc_set_server_status_down(struct server * srv)68 static void fwlc_set_server_status_down(struct server *srv)
69 {
70 struct proxy *p = srv->proxy;
71
72 if (!srv_lb_status_changed(srv))
73 return;
74
75 if (srv_is_usable(srv))
76 goto out_update_state;
77
78 if (!srv_was_usable(srv))
79 /* server was already down */
80 goto out_update_backend;
81
82 if (srv->flags & SRV_F_BACKUP) {
83 p->lbprm.tot_wbck -= srv->prev_eweight;
84 p->srv_bck--;
85
86 if (srv == p->lbprm.fbck) {
87 /* we lost the first backup server in a single-backup
88 * configuration, we must search another one.
89 */
90 struct server *srv2 = p->lbprm.fbck;
91 do {
92 srv2 = srv2->next;
93 } while (srv2 &&
94 !((srv2->flags & SRV_F_BACKUP) &&
95 srv_is_usable(srv2)));
96 p->lbprm.fbck = srv2;
97 }
98 } else {
99 p->lbprm.tot_wact -= srv->prev_eweight;
100 p->srv_act--;
101 }
102
103 fwlc_dequeue_srv(srv);
104 fwlc_remove_from_tree(srv);
105
106 out_update_backend:
107 /* check/update tot_used, tot_weight */
108 update_backend_weight(p);
109 out_update_state:
110 srv_lb_commit_status(srv);
111 }
112
113 /* This function updates the server trees according to server <srv>'s new
114 * state. It should be called when server <srv>'s status changes to up.
115 * It is not important whether the server was already down or not. It is not
116 * important either that the new state is completely UP (the caller may not
117 * know all the variables of a server's state). This function will not change
118 * the weight of a server which was already up.
119 */
fwlc_set_server_status_up(struct server * srv)120 static void fwlc_set_server_status_up(struct server *srv)
121 {
122 struct proxy *p = srv->proxy;
123
124 if (!srv_lb_status_changed(srv))
125 return;
126
127 if (!srv_is_usable(srv))
128 goto out_update_state;
129
130 if (srv_was_usable(srv))
131 /* server was already up */
132 goto out_update_backend;
133
134 if (srv->flags & SRV_F_BACKUP) {
135 srv->lb_tree = &p->lbprm.fwlc.bck;
136 p->lbprm.tot_wbck += srv->eweight;
137 p->srv_bck++;
138
139 if (!(p->options & PR_O_USE_ALL_BK)) {
140 if (!p->lbprm.fbck) {
141 /* there was no backup server anymore */
142 p->lbprm.fbck = srv;
143 } else {
144 /* we may have restored a backup server prior to fbck,
145 * in which case it should replace it.
146 */
147 struct server *srv2 = srv;
148 do {
149 srv2 = srv2->next;
150 } while (srv2 && (srv2 != p->lbprm.fbck));
151 if (srv2)
152 p->lbprm.fbck = srv;
153 }
154 }
155 } else {
156 srv->lb_tree = &p->lbprm.fwlc.act;
157 p->lbprm.tot_wact += srv->eweight;
158 p->srv_act++;
159 }
160
161 /* note that eweight cannot be 0 here */
162 fwlc_queue_srv(srv);
163
164 out_update_backend:
165 /* check/update tot_used, tot_weight */
166 update_backend_weight(p);
167 out_update_state:
168 srv_lb_commit_status(srv);
169 }
170
171 /* This function must be called after an update to server <srv>'s effective
172 * weight. It may be called after a state change too.
173 */
fwlc_update_server_weight(struct server * srv)174 static void fwlc_update_server_weight(struct server *srv)
175 {
176 int old_state, new_state;
177 struct proxy *p = srv->proxy;
178
179 if (!srv_lb_status_changed(srv))
180 return;
181
182 /* If changing the server's weight changes its state, we simply apply
183 * the procedures we already have for status change. If the state
184 * remains down, the server is not in any tree, so it's as easy as
185 * updating its values. If the state remains up with different weights,
186 * there are some computations to perform to find a new place and
187 * possibly a new tree for this server.
188 */
189
190 old_state = srv_was_usable(srv);
191 new_state = srv_is_usable(srv);
192
193 if (!old_state && !new_state) {
194 srv_lb_commit_status(srv);
195 return;
196 }
197 else if (!old_state && new_state) {
198 fwlc_set_server_status_up(srv);
199 return;
200 }
201 else if (old_state && !new_state) {
202 fwlc_set_server_status_down(srv);
203 return;
204 }
205
206 if (srv->lb_tree)
207 fwlc_dequeue_srv(srv);
208
209 if (srv->flags & SRV_F_BACKUP) {
210 p->lbprm.tot_wbck += srv->eweight - srv->prev_eweight;
211 srv->lb_tree = &p->lbprm.fwlc.bck;
212 } else {
213 p->lbprm.tot_wact += srv->eweight - srv->prev_eweight;
214 srv->lb_tree = &p->lbprm.fwlc.act;
215 }
216
217 fwlc_queue_srv(srv);
218
219 update_backend_weight(p);
220 srv_lb_commit_status(srv);
221 }
222
223 /* This function is responsible for building the trees in case of fast
224 * weighted least-conns. It also sets p->lbprm.wdiv to the eweight to
225 * uweight ratio. Both active and backup groups are initialized.
226 */
fwlc_init_server_tree(struct proxy * p)227 void fwlc_init_server_tree(struct proxy *p)
228 {
229 struct server *srv;
230 struct eb_root init_head = EB_ROOT;
231
232 p->lbprm.set_server_status_up = fwlc_set_server_status_up;
233 p->lbprm.set_server_status_down = fwlc_set_server_status_down;
234 p->lbprm.update_server_eweight = fwlc_update_server_weight;
235 p->lbprm.server_take_conn = fwlc_srv_reposition;
236 p->lbprm.server_drop_conn = fwlc_srv_reposition;
237
238 p->lbprm.wdiv = BE_WEIGHT_SCALE;
239 for (srv = p->srv; srv; srv = srv->next) {
240 srv->eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult;
241 srv_lb_commit_status(srv);
242 }
243
244 recount_servers(p);
245 update_backend_weight(p);
246
247 p->lbprm.fwlc.act = init_head;
248 p->lbprm.fwlc.bck = init_head;
249
250 /* queue active and backup servers in two distinct groups */
251 for (srv = p->srv; srv; srv = srv->next) {
252 if (!srv_is_usable(srv))
253 continue;
254 srv->lb_tree = (srv->flags & SRV_F_BACKUP) ? &p->lbprm.fwlc.bck : &p->lbprm.fwlc.act;
255 fwlc_queue_srv(srv);
256 }
257 }
258
259 /* Return next server from the FWLC tree in backend <p>. If the tree is empty,
260 * return NULL. Saturated servers are skipped.
261 */
fwlc_get_next_server(struct proxy * p,struct server * srvtoavoid)262 struct server *fwlc_get_next_server(struct proxy *p, struct server *srvtoavoid)
263 {
264 struct server *srv, *avoided;
265 struct eb32_node *node;
266
267 srv = avoided = NULL;
268
269 if (p->srv_act)
270 node = eb32_first(&p->lbprm.fwlc.act);
271 else if (p->lbprm.fbck)
272 return p->lbprm.fbck;
273 else if (p->srv_bck)
274 node = eb32_first(&p->lbprm.fwlc.bck);
275 else
276 return NULL;
277
278 while (node) {
279 /* OK, we have a server. However, it may be saturated, in which
280 * case we don't want to reconsider it for now, so we'll simply
281 * skip it. Same if it's the server we try to avoid, in which
282 * case we simply remember it for later use if needed.
283 */
284 struct server *s;
285
286 s = eb32_entry(node, struct server, lb_node);
287 if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) {
288 if (s != srvtoavoid) {
289 srv = s;
290 break;
291 }
292 avoided = s;
293 }
294 node = eb32_next(node);
295 }
296
297 if (!srv)
298 srv = avoided;
299
300 return srv;
301 }
302
303
304 /*
305 * Local variables:
306 * c-indent-level: 8
307 * c-basic-offset: 8
308 * End:
309 */
310