blob: 2918c26be753769915cb6af959553eb26675a4c7 [file] [log] [blame]
Willy Tarreauf89c1872009-10-01 11:19:37 +02001/*
2 * Map-based load-balancing (RR and HASH)
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 <common/eb32tree.h>
17
18#include <types/global.h>
19#include <types/server.h>
20
21#include <proto/backend.h>
22#include <proto/proto_http.h>
23#include <proto/proto_tcp.h>
24#include <proto/queue.h>
25
26/* this function updates the map according to server <srv>'s new state */
27static void map_set_server_status_down(struct server *srv)
28{
29 struct proxy *p = srv->proxy;
30
31 if (srv->state == srv->prev_state &&
32 srv->eweight == srv->prev_eweight)
33 return;
34
35 if (srv_is_usable(srv->state, srv->eweight))
36 goto out_update_state;
37
38 /* FIXME: could be optimized since we know what changed */
39 recount_servers(p);
40 update_backend_weight(p);
Willy Tarreau5b4c2b52009-10-03 11:21:53 +020041 p->lbprm.map.state |= LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +020042 out_update_state:
43 srv->prev_state = srv->state;
44 srv->prev_eweight = srv->eweight;
45}
46
47/* This function updates the map according to server <srv>'s new state */
48static void map_set_server_status_up(struct server *srv)
49{
50 struct proxy *p = srv->proxy;
51
52 if (srv->state == srv->prev_state &&
53 srv->eweight == srv->prev_eweight)
54 return;
55
56 if (!srv_is_usable(srv->state, srv->eweight))
57 goto out_update_state;
58
59 /* FIXME: could be optimized since we know what changed */
60 recount_servers(p);
61 update_backend_weight(p);
Willy Tarreau5b4c2b52009-10-03 11:21:53 +020062 p->lbprm.map.state |= LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +020063 out_update_state:
64 srv->prev_state = srv->state;
65 srv->prev_eweight = srv->eweight;
66}
67
68/* This function recomputes the server map for proxy px. It relies on
69 * px->lbprm.tot_wact, tot_wbck, tot_used, tot_weight, so it must be
70 * called after recount_servers(). It also expects px->lbprm.map.srv
71 * to be allocated with the largest size needed. It updates tot_weight.
72 */
73void recalc_server_map(struct proxy *px)
74{
75 int o, tot, flag;
76 struct server *cur, *best;
77
78 switch (px->lbprm.tot_used) {
79 case 0: /* no server */
Willy Tarreau5b4c2b52009-10-03 11:21:53 +020080 px->lbprm.map.state &= ~LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +020081 return;
82 case 1: /* only one server, just fill first entry */
83 tot = 1;
84 break;
85 default:
86 tot = px->lbprm.tot_weight;
87 break;
88 }
89
90 /* here we *know* that we have some servers */
91 if (px->srv_act)
92 flag = SRV_RUNNING;
93 else
94 flag = SRV_RUNNING | SRV_BACKUP;
95
96 /* this algorithm gives priority to the first server, which means that
97 * it will respect the declaration order for equivalent weights, and
98 * that whatever the weights, the first server called will always be
99 * the first declared. This is an important asumption for the backup
100 * case, where we want the first server only.
101 */
102 for (cur = px->srv; cur; cur = cur->next)
103 cur->wscore = 0;
104
105 for (o = 0; o < tot; o++) {
106 int max = 0;
107 best = NULL;
108 for (cur = px->srv; cur; cur = cur->next) {
109 if (cur->eweight &&
110 flag == (cur->state &
111 (SRV_RUNNING | SRV_GOINGDOWN | SRV_BACKUP))) {
112 int v;
113
114 /* If we are forced to return only one server, we don't want to
115 * go further, because we would return the wrong one due to
116 * divide overflow.
117 */
118 if (tot == 1) {
119 best = cur;
120 /* note that best->wscore will be wrong but we don't care */
121 break;
122 }
123
124 cur->wscore += cur->eweight;
125 v = (cur->wscore + tot) / tot; /* result between 0 and 3 */
126 if (best == NULL || v > max) {
127 max = v;
128 best = cur;
129 }
130 }
131 }
132 px->lbprm.map.srv[o] = best;
133 best->wscore -= tot;
134 }
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200135 px->lbprm.map.state &= ~LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200136}
137
138/* This function is responsible of building the server MAP for map-based LB
139 * algorithms, allocating the map, and setting p->lbprm.wmult to the GCD of the
140 * weights if applicable. It should be called only once per proxy, at config
141 * time.
142 */
143void init_server_map(struct proxy *p)
144{
145 struct server *srv;
146 int pgcd;
147 int act, bck;
148
149 p->lbprm.set_server_status_up = map_set_server_status_up;
150 p->lbprm.set_server_status_down = map_set_server_status_down;
151 p->lbprm.update_server_eweight = NULL;
152
153 if (!p->srv)
154 return;
155
156 /* We will factor the weights to reduce the table,
157 * using Euclide's largest common divisor algorithm.
158 * Since we may have zero weights, we have to first
159 * find a non-zero weight server.
160 */
161 pgcd = 1;
162 srv = p->srv;
163 while (srv && !srv->uweight)
164 srv = srv->next;
165
166 if (srv) {
167 pgcd = srv->uweight; /* note: cannot be zero */
168 while (pgcd > 1 && (srv = srv->next)) {
169 int w = srv->uweight;
170 while (w) {
171 int t = pgcd % w;
172 pgcd = w;
173 w = t;
174 }
175 }
176 }
177
178 /* It is sometimes useful to know what factor to apply
179 * to the backend's effective weight to know its real
180 * weight.
181 */
182 p->lbprm.wmult = pgcd;
183
184 act = bck = 0;
185 for (srv = p->srv; srv; srv = srv->next) {
186 srv->eweight = srv->uweight / pgcd;
187 srv->prev_eweight = srv->eweight;
188 srv->prev_state = srv->state;
189 if (srv->state & SRV_BACKUP)
190 bck += srv->eweight;
191 else
192 act += srv->eweight;
193 }
194
195 /* this is the largest map we will ever need for this servers list */
196 if (act < bck)
197 act = bck;
198
199 if (!act)
200 act = 1;
201
202 p->lbprm.map.srv = (struct server **)calloc(act, sizeof(struct server *));
203 /* recounts servers and their weights */
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200204 p->lbprm.map.state = LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200205 recount_servers(p);
206 update_backend_weight(p);
207 recalc_server_map(p);
208}
209
210/*
211 * This function tries to find a running server with free connection slots for
212 * the proxy <px> following the round-robin method.
213 * If any server is found, it will be returned and px->lbprm.map.rr_idx will be updated
214 * to point to the next server. If no valid server is found, NULL is returned.
215 */
216struct server *map_get_server_rr(struct proxy *px, struct server *srvtoavoid)
217{
218 int newidx, avoididx;
219 struct server *srv, *avoided;
220
221 if (px->lbprm.tot_weight == 0)
222 return NULL;
223
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200224 if (px->lbprm.map.state & LB_MAP_RECALC)
Willy Tarreauf89c1872009-10-01 11:19:37 +0200225 recalc_server_map(px);
226
227 if (px->lbprm.map.rr_idx < 0 || px->lbprm.map.rr_idx >= px->lbprm.tot_weight)
228 px->lbprm.map.rr_idx = 0;
229 newidx = px->lbprm.map.rr_idx;
230
231 avoided = NULL;
232 avoididx = 0; /* shut a gcc warning */
233 do {
234 srv = px->lbprm.map.srv[newidx++];
235 if (!srv->maxconn || srv->cur_sess < srv_dynamic_maxconn(srv)) {
236 /* make sure it is not the server we are try to exclude... */
237 if (srv != srvtoavoid) {
238 px->lbprm.map.rr_idx = newidx;
239 return srv;
240 }
241
242 avoided = srv; /* ...but remember that is was selected yet avoided */
243 avoididx = newidx;
244 }
245 if (newidx == px->lbprm.tot_weight)
246 newidx = 0;
247 } while (newidx != px->lbprm.map.rr_idx);
248
249 if (avoided)
250 px->lbprm.map.rr_idx = avoididx;
251
252 /* return NULL or srvtoavoid if found */
253 return avoided;
254}
255
Willy Tarreau39c9ba72009-10-01 21:11:15 +0200256/*
257 * This function returns the running server from the map at the location
258 * pointed to by the result of a modulo operation on <hash>. The server map may
259 * be recomputed if required before being looked up. If any server is found, it
260 * will be returned. If no valid server is found, NULL is returned.
261 */
262struct server *map_get_server_hash(struct proxy *px, unsigned int hash)
263{
264 if (px->lbprm.tot_weight == 0)
265 return NULL;
266
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200267 if (px->lbprm.map.state & LB_MAP_RECALC)
Willy Tarreau39c9ba72009-10-01 21:11:15 +0200268 recalc_server_map(px);
269
270 return px->lbprm.map.srv[hash % px->lbprm.tot_weight];
271}
272
Willy Tarreauf89c1872009-10-01 11:19:37 +0200273
274/*
275 * Local variables:
276 * c-indent-level: 8
277 * c-basic-offset: 8
278 * End:
279 */