blob: fef16ac2ececbc430ecc99b48139d33717cd749f [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
Willy Tarreauc5150da2014-05-13 19:27:31 +020031 if (!srv_lb_status_changed(srv))
Willy Tarreauf89c1872009-10-01 11:19:37 +020032 return;
33
Emeric Brun52a91d32017-08-31 14:41:55 +020034 if (srv_willbe_usable(srv))
Willy Tarreauf89c1872009-10-01 11:19:37 +020035 goto out_update_state;
36
37 /* FIXME: could be optimized since we know what changed */
38 recount_servers(p);
39 update_backend_weight(p);
Willy Tarreau5b4c2b52009-10-03 11:21:53 +020040 p->lbprm.map.state |= LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +020041 out_update_state:
Willy Tarreauc5150da2014-05-13 19:27:31 +020042 srv_lb_commit_status(srv);
Willy Tarreauf89c1872009-10-01 11:19:37 +020043}
44
45/* This function updates the map according to server <srv>'s new state */
46static void map_set_server_status_up(struct server *srv)
47{
48 struct proxy *p = srv->proxy;
49
Willy Tarreauc5150da2014-05-13 19:27:31 +020050 if (!srv_lb_status_changed(srv))
Willy Tarreauf89c1872009-10-01 11:19:37 +020051 return;
52
Emeric Brun52a91d32017-08-31 14:41:55 +020053 if (!srv_willbe_usable(srv))
Willy Tarreauf89c1872009-10-01 11:19:37 +020054 goto out_update_state;
55
56 /* FIXME: could be optimized since we know what changed */
57 recount_servers(p);
58 update_backend_weight(p);
Willy Tarreau5b4c2b52009-10-03 11:21:53 +020059 p->lbprm.map.state |= LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +020060 out_update_state:
Willy Tarreauc5150da2014-05-13 19:27:31 +020061 srv_lb_commit_status(srv);
Willy Tarreauf89c1872009-10-01 11:19:37 +020062}
63
64/* This function recomputes the server map for proxy px. It relies on
65 * px->lbprm.tot_wact, tot_wbck, tot_used, tot_weight, so it must be
66 * called after recount_servers(). It also expects px->lbprm.map.srv
67 * to be allocated with the largest size needed. It updates tot_weight.
68 */
69void recalc_server_map(struct proxy *px)
70{
71 int o, tot, flag;
72 struct server *cur, *best;
73
74 switch (px->lbprm.tot_used) {
75 case 0: /* no server */
Willy Tarreau5b4c2b52009-10-03 11:21:53 +020076 px->lbprm.map.state &= ~LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +020077 return;
Willy Tarreauf89c1872009-10-01 11:19:37 +020078 default:
79 tot = px->lbprm.tot_weight;
80 break;
81 }
82
83 /* here we *know* that we have some servers */
84 if (px->srv_act)
Willy Tarreauc93cd162014-05-13 15:54:22 +020085 flag = 0;
Willy Tarreauf89c1872009-10-01 11:19:37 +020086 else
Willy Tarreauc93cd162014-05-13 15:54:22 +020087 flag = SRV_F_BACKUP;
Willy Tarreauf89c1872009-10-01 11:19:37 +020088
89 /* this algorithm gives priority to the first server, which means that
90 * it will respect the declaration order for equivalent weights, and
91 * that whatever the weights, the first server called will always be
92 * the first declared. This is an important asumption for the backup
93 * case, where we want the first server only.
94 */
95 for (cur = px->srv; cur; cur = cur->next)
96 cur->wscore = 0;
97
98 for (o = 0; o < tot; o++) {
99 int max = 0;
100 best = NULL;
101 for (cur = px->srv; cur; cur = cur->next) {
Willy Tarreau9943d312014-05-22 16:20:59 +0200102 if ((cur->flags & SRV_F_BACKUP) == flag &&
Emeric Brun52a91d32017-08-31 14:41:55 +0200103 srv_willbe_usable(cur)) {
Willy Tarreauf89c1872009-10-01 11:19:37 +0200104 int v;
105
106 /* If we are forced to return only one server, we don't want to
107 * go further, because we would return the wrong one due to
108 * divide overflow.
109 */
110 if (tot == 1) {
111 best = cur;
112 /* note that best->wscore will be wrong but we don't care */
113 break;
114 }
115
Emeric Brun52a91d32017-08-31 14:41:55 +0200116 cur->wscore += cur->next_eweight;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200117 v = (cur->wscore + tot) / tot; /* result between 0 and 3 */
118 if (best == NULL || v > max) {
119 max = v;
120 best = cur;
121 }
122 }
123 }
124 px->lbprm.map.srv[o] = best;
125 best->wscore -= tot;
126 }
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200127 px->lbprm.map.state &= ~LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200128}
129
130/* This function is responsible of building the server MAP for map-based LB
131 * algorithms, allocating the map, and setting p->lbprm.wmult to the GCD of the
132 * weights if applicable. It should be called only once per proxy, at config
133 * time.
134 */
135void init_server_map(struct proxy *p)
136{
137 struct server *srv;
138 int pgcd;
139 int act, bck;
140
141 p->lbprm.set_server_status_up = map_set_server_status_up;
142 p->lbprm.set_server_status_down = map_set_server_status_down;
143 p->lbprm.update_server_eweight = NULL;
144
145 if (!p->srv)
146 return;
147
148 /* We will factor the weights to reduce the table,
149 * using Euclide's largest common divisor algorithm.
150 * Since we may have zero weights, we have to first
151 * find a non-zero weight server.
152 */
153 pgcd = 1;
154 srv = p->srv;
155 while (srv && !srv->uweight)
156 srv = srv->next;
157
158 if (srv) {
159 pgcd = srv->uweight; /* note: cannot be zero */
160 while (pgcd > 1 && (srv = srv->next)) {
161 int w = srv->uweight;
162 while (w) {
163 int t = pgcd % w;
164 pgcd = w;
165 w = t;
166 }
167 }
168 }
169
170 /* It is sometimes useful to know what factor to apply
171 * to the backend's effective weight to know its real
172 * weight.
173 */
174 p->lbprm.wmult = pgcd;
175
176 act = bck = 0;
177 for (srv = p->srv; srv; srv = srv->next) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200178 srv->next_eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult;
Willy Tarreauc5150da2014-05-13 19:27:31 +0200179
Willy Tarreauc93cd162014-05-13 15:54:22 +0200180 if (srv->flags & SRV_F_BACKUP)
Emeric Brun52a91d32017-08-31 14:41:55 +0200181 bck += srv->next_eweight;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200182 else
Emeric Brun52a91d32017-08-31 14:41:55 +0200183 act += srv->next_eweight;
184 srv_lb_commit_status(srv);
Willy Tarreauf89c1872009-10-01 11:19:37 +0200185 }
186
187 /* this is the largest map we will ever need for this servers list */
188 if (act < bck)
189 act = bck;
190
191 if (!act)
192 act = 1;
193
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200194 p->lbprm.map.srv = calloc(act, sizeof(struct server *));
Willy Tarreauf89c1872009-10-01 11:19:37 +0200195 /* recounts servers and their weights */
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200196 p->lbprm.map.state = LB_MAP_RECALC;
Willy Tarreauf89c1872009-10-01 11:19:37 +0200197 recount_servers(p);
198 update_backend_weight(p);
199 recalc_server_map(p);
200}
201
202/*
203 * This function tries to find a running server with free connection slots for
204 * the proxy <px> following the round-robin method.
205 * If any server is found, it will be returned and px->lbprm.map.rr_idx will be updated
206 * to point to the next server. If no valid server is found, NULL is returned.
207 */
208struct server *map_get_server_rr(struct proxy *px, struct server *srvtoavoid)
209{
210 int newidx, avoididx;
211 struct server *srv, *avoided;
212
213 if (px->lbprm.tot_weight == 0)
214 return NULL;
215
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200216 if (px->lbprm.map.state & LB_MAP_RECALC)
Willy Tarreauf89c1872009-10-01 11:19:37 +0200217 recalc_server_map(px);
218
219 if (px->lbprm.map.rr_idx < 0 || px->lbprm.map.rr_idx >= px->lbprm.tot_weight)
220 px->lbprm.map.rr_idx = 0;
221 newidx = px->lbprm.map.rr_idx;
222
223 avoided = NULL;
224 avoididx = 0; /* shut a gcc warning */
225 do {
226 srv = px->lbprm.map.srv[newidx++];
Godbach8f9fd2f2013-08-07 09:48:23 +0800227 if (!srv->maxconn || (!srv->nbpend && srv->served < srv_dynamic_maxconn(srv))) {
Willy Tarreauf89c1872009-10-01 11:19:37 +0200228 /* make sure it is not the server we are try to exclude... */
229 if (srv != srvtoavoid) {
230 px->lbprm.map.rr_idx = newidx;
231 return srv;
232 }
233
234 avoided = srv; /* ...but remember that is was selected yet avoided */
235 avoididx = newidx;
236 }
237 if (newidx == px->lbprm.tot_weight)
238 newidx = 0;
239 } while (newidx != px->lbprm.map.rr_idx);
240
241 if (avoided)
242 px->lbprm.map.rr_idx = avoididx;
243
244 /* return NULL or srvtoavoid if found */
245 return avoided;
246}
247
Willy Tarreau39c9ba72009-10-01 21:11:15 +0200248/*
249 * This function returns the running server from the map at the location
250 * pointed to by the result of a modulo operation on <hash>. The server map may
251 * be recomputed if required before being looked up. If any server is found, it
252 * will be returned. If no valid server is found, NULL is returned.
253 */
254struct server *map_get_server_hash(struct proxy *px, unsigned int hash)
255{
256 if (px->lbprm.tot_weight == 0)
257 return NULL;
258
Willy Tarreau5b4c2b52009-10-03 11:21:53 +0200259 if (px->lbprm.map.state & LB_MAP_RECALC)
Willy Tarreau39c9ba72009-10-01 21:11:15 +0200260 recalc_server_map(px);
261
262 return px->lbprm.map.srv[hash % px->lbprm.tot_weight];
263}
264
Willy Tarreauf89c1872009-10-01 11:19:37 +0200265
266/*
267 * Local variables:
268 * c-indent-level: 8
269 * c-basic-offset: 8
270 * End:
271 */