blob: 9858249cd7d6e57b7520b51b0b7bacc26c99ef24 [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>
Willy Tarreau45cb4fb2009-10-26 21:10:04 +010016#include <eb32tree.h>
Willy Tarreauf89c1872009-10-01 11:19:37 +020017
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;
Willy Tarreauf89c1872009-10-01 11:19:37 +020082 default:
83 tot = px->lbprm.tot_weight;
84 break;
85 }
86
87 /* here we *know* that we have some servers */
88 if (px->srv_act)
89 flag = SRV_RUNNING;
90 else
91 flag = SRV_RUNNING | SRV_BACKUP;
92
93 /* this algorithm gives priority to the first server, which means that
94 * it will respect the declaration order for equivalent weights, and
95 * that whatever the weights, the first server called will always be
96 * the first declared. This is an important asumption for the backup
97 * case, where we want the first server only.
98 */
99 for (cur = px->srv; cur; cur = cur->next)
100 cur->wscore = 0;
101
102 for (o = 0; o < tot; o++) {
103 int max = 0;
104 best = NULL;
105 for (cur = px->srv; cur; cur = cur->next) {
106 if (cur->eweight &&
107 flag == (cur->state &
108 (SRV_RUNNING | SRV_GOINGDOWN | SRV_BACKUP))) {
109 int v;
110
111 /* If we are forced to return only one server, we don't want to
112 * go further, because we would return the wrong one due to
113 * divide overflow.
114 */
115 if (tot == 1) {
116 best = cur;
117 /* note that best->wscore will be wrong but we don't care */
118 break;
119 }
120
121 cur->wscore += cur->eweight;
122 v = (cur->wscore + tot) / tot; /* result between 0 and 3 */
123 if (best == NULL || v > max) {
124 max = v;
125 best = cur;
126 }
127 }
128 }
129 px->lbprm.map.srv[o] = best;
130 best->wscore -= tot;
131 }
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200132 px->lbprm.map.state &= ~LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200133}
134
135/* This function is responsible of building the server MAP for map-based LB
136 * algorithms, allocating the map, and setting p->lbprm.wmult to the GCD of the
137 * weights if applicable. It should be called only once per proxy, at config
138 * time.
139 */
140void init_server_map(struct proxy *p)
141{
142 struct server *srv;
143 int pgcd;
144 int act, bck;
145
146 p->lbprm.set_server_status_up = map_set_server_status_up;
147 p->lbprm.set_server_status_down = map_set_server_status_down;
148 p->lbprm.update_server_eweight = NULL;
149
150 if (!p->srv)
151 return;
152
153 /* We will factor the weights to reduce the table,
154 * using Euclide's largest common divisor algorithm.
155 * Since we may have zero weights, we have to first
156 * find a non-zero weight server.
157 */
158 pgcd = 1;
159 srv = p->srv;
160 while (srv && !srv->uweight)
161 srv = srv->next;
162
163 if (srv) {
164 pgcd = srv->uweight; /* note: cannot be zero */
165 while (pgcd > 1 && (srv = srv->next)) {
166 int w = srv->uweight;
167 while (w) {
168 int t = pgcd % w;
169 pgcd = w;
170 w = t;
171 }
172 }
173 }
174
175 /* It is sometimes useful to know what factor to apply
176 * to the backend's effective weight to know its real
177 * weight.
178 */
179 p->lbprm.wmult = pgcd;
180
181 act = bck = 0;
182 for (srv = p->srv; srv; srv = srv->next) {
183 srv->eweight = srv->uweight / pgcd;
184 srv->prev_eweight = srv->eweight;
185 srv->prev_state = srv->state;
186 if (srv->state & SRV_BACKUP)
187 bck += srv->eweight;
188 else
189 act += srv->eweight;
190 }
191
192 /* this is the largest map we will ever need for this servers list */
193 if (act < bck)
194 act = bck;
195
196 if (!act)
197 act = 1;
198
199 p->lbprm.map.srv = (struct server **)calloc(act, sizeof(struct server *));
200 /* recounts servers and their weights */
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200201 p->lbprm.map.state = LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200202 recount_servers(p);
203 update_backend_weight(p);
204 recalc_server_map(p);
205}
206
207/*
208 * This function tries to find a running server with free connection slots for
209 * the proxy <px> following the round-robin method.
210 * If any server is found, it will be returned and px->lbprm.map.rr_idx will be updated
211 * to point to the next server. If no valid server is found, NULL is returned.
212 */
213struct server *map_get_server_rr(struct proxy *px, struct server *srvtoavoid)
214{
215 int newidx, avoididx;
216 struct server *srv, *avoided;
217
218 if (px->lbprm.tot_weight == 0)
219 return NULL;
220
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200221 if (px->lbprm.map.state & LB_MAP_RECALC)
Willy Tarreauf89c1872009-10-01 11:19:37 +0200222 recalc_server_map(px);
223
224 if (px->lbprm.map.rr_idx < 0 || px->lbprm.map.rr_idx >= px->lbprm.tot_weight)
225 px->lbprm.map.rr_idx = 0;
226 newidx = px->lbprm.map.rr_idx;
227
228 avoided = NULL;
229 avoididx = 0; /* shut a gcc warning */
230 do {
231 srv = px->lbprm.map.srv[newidx++];
Godbach8f9fd2f2013-08-07 09:48:23 +0800232 if (!srv->maxconn || (!srv->nbpend && srv->served < srv_dynamic_maxconn(srv))) {
Willy Tarreauf89c1872009-10-01 11:19:37 +0200233 /* make sure it is not the server we are try to exclude... */
234 if (srv != srvtoavoid) {
235 px->lbprm.map.rr_idx = newidx;
236 return srv;
237 }
238
239 avoided = srv; /* ...but remember that is was selected yet avoided */
240 avoididx = newidx;
241 }
242 if (newidx == px->lbprm.tot_weight)
243 newidx = 0;
244 } while (newidx != px->lbprm.map.rr_idx);
245
246 if (avoided)
247 px->lbprm.map.rr_idx = avoididx;
248
249 /* return NULL or srvtoavoid if found */
250 return avoided;
251}
252
Willy Tarreau39c9ba72009-10-01 21:11:15 +0200253/*
254 * This function returns the running server from the map at the location
255 * pointed to by the result of a modulo operation on <hash>. The server map may
256 * be recomputed if required before being looked up. If any server is found, it
257 * will be returned. If no valid server is found, NULL is returned.
258 */
259struct server *map_get_server_hash(struct proxy *px, unsigned int hash)
260{
261 if (px->lbprm.tot_weight == 0)
262 return NULL;
263
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200264 if (px->lbprm.map.state & LB_MAP_RECALC)
Willy Tarreau39c9ba72009-10-01 21:11:15 +0200265 recalc_server_map(px);
266
267 return px->lbprm.map.srv[hash % px->lbprm.tot_weight];
268}
269
Willy Tarreauf89c1872009-10-01 11:19:37 +0200270
271/*
272 * Local variables:
273 * c-indent-level: 8
274 * c-basic-offset: 8
275 * End:
276 */