blob: 0bf4e81a2c9a45c6ae0f8f146e674b0c08bec8ac [file] [log] [blame]
Willy Tarreau6b2e11b2009-10-01 07:52:15 +02001/*
2 * Consistent Hash implementation
3 * Please consult this very well detailed article for more information :
4 * http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
5 *
6 * Our implementation has to support both weighted hashing and weighted round
7 * robin because we'll use it to replace the previous map-based implementation
8 * which offered both algorithms.
9 *
Willy Tarreau4c14eaa2010-11-24 14:01:45 +010010 * Copyright 2000-2010 Willy Tarreau <w@1wt.eu>
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020011 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version
15 * 2 of the License, or (at your option) any later version.
16 *
17 */
18
19#include <common/compat.h>
20#include <common/config.h>
21#include <common/debug.h>
Willy Tarreau4c14eaa2010-11-24 14:01:45 +010022#include <common/standard.h>
Willy Tarreau45cb4fb2009-10-26 21:10:04 +010023#include <eb32tree.h>
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020024
25#include <types/global.h>
26#include <types/server.h>
27
28#include <proto/backend.h>
29#include <proto/queue.h>
30
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020031/* Return next tree node after <node> which must still be in the tree, or be
32 * NULL. Lookup wraps around the end to the beginning. If the next node is the
33 * same node, return NULL. This is designed to find a valid next node before
34 * deleting one from the tree.
35 */
36static inline struct eb32_node *chash_skip_node(struct eb_root *root, struct eb32_node *node)
37{
38 struct eb32_node *stop = node;
39
40 if (!node)
41 return NULL;
42 node = eb32_next(node);
43 if (!node)
44 node = eb32_first(root);
45 if (node == stop)
46 return NULL;
47 return node;
48}
49
50/* Remove all of a server's entries from its tree. This may be used when
51 * setting a server down.
52 */
53static inline void chash_dequeue_srv(struct server *s)
54{
55 while (s->lb_nodes_now > 0) {
56 if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
57 s->lb_nodes_now = s->lb_nodes_tot;
58 s->lb_nodes_now--;
59 if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
60 s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
61 eb32_delete(&s->lb_nodes[s->lb_nodes_now].node);
62 }
63}
64
65/* Adjust the number of entries of a server in its tree. The server must appear
66 * as many times as its weight indicates it. If it's there too often, we remove
67 * the last occurrences. If it's not there enough, we add more occurrences. To
68 * remove a server from the tree, normally call this with eweight=0.
Willy Tarreau1b877482018-08-21 19:44:53 +020069 *
70 * The server's lock and the lbprm's lock must be held.
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020071 */
72static inline void chash_queue_dequeue_srv(struct server *s)
73{
Emeric Brun52a91d32017-08-31 14:41:55 +020074 while (s->lb_nodes_now > s->next_eweight) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020075 if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
76 s->lb_nodes_now = s->lb_nodes_tot;
77 s->lb_nodes_now--;
78 if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
79 s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
80 eb32_delete(&s->lb_nodes[s->lb_nodes_now].node);
81 }
82
Olivier Houchardf8eb8d52017-10-17 15:52:59 +020083 /* Attempt to increase the total number of nodes, if the user
84 * increased the weight beyond the original weight
85 */
86 if (s->lb_nodes_tot < s->next_eweight) {
Christopher Faulet366ad862019-07-26 13:52:13 +020087 struct tree_occ *new_nodes = realloc(s->lb_nodes, s->next_eweight * sizeof(*new_nodes));
Olivier Houchardf8eb8d52017-10-17 15:52:59 +020088
89 if (new_nodes) {
90 unsigned int j;
91
92 s->lb_nodes = new_nodes;
93 memset(&s->lb_nodes[s->lb_nodes_tot], 0,
94 (s->next_eweight - s->lb_nodes_tot) * sizeof(*s->lb_nodes));
95 for (j = s->lb_nodes_tot; j < s->next_eweight; j++) {
96 s->lb_nodes[j].server = s;
97 s->lb_nodes[j].node.key = full_hash(s->puid * SRV_EWGHT_RANGE + j);
98 }
99 s->lb_nodes_tot = s->next_eweight;
100 }
101 }
Emeric Brun52a91d32017-08-31 14:41:55 +0200102 while (s->lb_nodes_now < s->next_eweight) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200103 if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
104 break;
105 if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
106 s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
107 eb32_insert(s->lb_tree, &s->lb_nodes[s->lb_nodes_now].node);
108 s->lb_nodes_now++;
109 }
110}
111
112/* This function updates the server trees according to server <srv>'s new
113 * state. It should be called when server <srv>'s status changes to down.
114 * It is not important whether the server was already down or not. It is not
115 * important either that the new state is completely down (the caller may not
116 * know all the variables of a server's state).
Willy Tarreau1b877482018-08-21 19:44:53 +0200117 *
118 * The server's lock must be held. The lbprm lock will be used.
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200119 */
120static void chash_set_server_status_down(struct server *srv)
121{
122 struct proxy *p = srv->proxy;
123
Willy Tarreauc5150da2014-05-13 19:27:31 +0200124 if (!srv_lb_status_changed(srv))
Christopher Faulet5b517552017-06-09 14:17:53 +0200125 return;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200126
Willy Tarreau1b877482018-08-21 19:44:53 +0200127 HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
128
Emeric Brun52a91d32017-08-31 14:41:55 +0200129 if (srv_willbe_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200130 goto out_update_state;
131
Emeric Brun52a91d32017-08-31 14:41:55 +0200132 if (!srv_currently_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200133 /* server was already down */
134 goto out_update_backend;
135
Willy Tarreauc93cd162014-05-13 15:54:22 +0200136 if (srv->flags & SRV_F_BACKUP) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200137 p->lbprm.tot_wbck -= srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200138 p->srv_bck--;
139
140 if (srv == p->lbprm.fbck) {
141 /* we lost the first backup server in a single-backup
142 * configuration, we must search another one.
143 */
144 struct server *srv2 = p->lbprm.fbck;
145 do {
146 srv2 = srv2->next;
147 } while (srv2 &&
Willy Tarreauc93cd162014-05-13 15:54:22 +0200148 !((srv2->flags & SRV_F_BACKUP) &&
Emeric Brun52a91d32017-08-31 14:41:55 +0200149 srv_willbe_usable(srv2)));
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200150 p->lbprm.fbck = srv2;
151 }
152 } else {
Emeric Brun52a91d32017-08-31 14:41:55 +0200153 p->lbprm.tot_wact -= srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200154 p->srv_act--;
155 }
156
157 chash_dequeue_srv(srv);
158
159out_update_backend:
160 /* check/update tot_used, tot_weight */
161 update_backend_weight(p);
162 out_update_state:
Willy Tarreauc5150da2014-05-13 19:27:31 +0200163 srv_lb_commit_status(srv);
Willy Tarreau1b877482018-08-21 19:44:53 +0200164
165 HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200166}
167
168/* This function updates the server trees according to server <srv>'s new
169 * state. It should be called when server <srv>'s status changes to up.
170 * It is not important whether the server was already down or not. It is not
171 * important either that the new state is completely UP (the caller may not
172 * know all the variables of a server's state). This function will not change
173 * the weight of a server which was already up.
Willy Tarreau1b877482018-08-21 19:44:53 +0200174 *
175 * The server's lock must be held. The lbprm lock will be used.
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200176 */
177static void chash_set_server_status_up(struct server *srv)
178{
179 struct proxy *p = srv->proxy;
180
Willy Tarreauc5150da2014-05-13 19:27:31 +0200181 if (!srv_lb_status_changed(srv))
Christopher Faulet5b517552017-06-09 14:17:53 +0200182 return;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200183
Willy Tarreau1b877482018-08-21 19:44:53 +0200184 HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
185
Emeric Brun52a91d32017-08-31 14:41:55 +0200186 if (!srv_willbe_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200187 goto out_update_state;
188
Emeric Brun52a91d32017-08-31 14:41:55 +0200189 if (srv_currently_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200190 /* server was already up */
191 goto out_update_backend;
192
Willy Tarreauc93cd162014-05-13 15:54:22 +0200193 if (srv->flags & SRV_F_BACKUP) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200194 p->lbprm.tot_wbck += srv->next_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200195 p->srv_bck++;
196
197 if (!(p->options & PR_O_USE_ALL_BK)) {
198 if (!p->lbprm.fbck) {
199 /* there was no backup server anymore */
200 p->lbprm.fbck = srv;
201 } else {
202 /* we may have restored a backup server prior to fbck,
203 * in which case it should replace it.
204 */
205 struct server *srv2 = srv;
206 do {
207 srv2 = srv2->next;
208 } while (srv2 && (srv2 != p->lbprm.fbck));
209 if (srv2)
210 p->lbprm.fbck = srv;
211 }
212 }
213 } else {
Emeric Brun52a91d32017-08-31 14:41:55 +0200214 p->lbprm.tot_wact += srv->next_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200215 p->srv_act++;
216 }
217
218 /* note that eweight cannot be 0 here */
219 chash_queue_dequeue_srv(srv);
220
221 out_update_backend:
222 /* check/update tot_used, tot_weight */
223 update_backend_weight(p);
224 out_update_state:
Willy Tarreauc5150da2014-05-13 19:27:31 +0200225 srv_lb_commit_status(srv);
Willy Tarreau1b877482018-08-21 19:44:53 +0200226
227 HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200228}
229
230/* This function must be called after an update to server <srv>'s effective
231 * weight. It may be called after a state change too.
Willy Tarreau1b877482018-08-21 19:44:53 +0200232 *
233 * The server's lock must be held. The lbprm lock may be used.
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200234 */
235static void chash_update_server_weight(struct server *srv)
236{
237 int old_state, new_state;
238 struct proxy *p = srv->proxy;
239
Willy Tarreauc5150da2014-05-13 19:27:31 +0200240 if (!srv_lb_status_changed(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200241 return;
242
243 /* If changing the server's weight changes its state, we simply apply
244 * the procedures we already have for status change. If the state
245 * remains down, the server is not in any tree, so it's as easy as
246 * updating its values. If the state remains up with different weights,
247 * there are some computations to perform to find a new place and
248 * possibly a new tree for this server.
249 */
250
Emeric Brun52a91d32017-08-31 14:41:55 +0200251 old_state = srv_currently_usable(srv);
252 new_state = srv_willbe_usable(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200253
254 if (!old_state && !new_state) {
Willy Tarreauc5150da2014-05-13 19:27:31 +0200255 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200256 return;
257 }
258 else if (!old_state && new_state) {
259 chash_set_server_status_up(srv);
260 return;
261 }
262 else if (old_state && !new_state) {
263 chash_set_server_status_down(srv);
264 return;
265 }
266
Willy Tarreau1b877482018-08-21 19:44:53 +0200267 HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
268
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200269 /* only adjust the server's presence in the tree */
270 chash_queue_dequeue_srv(srv);
271
Willy Tarreauc93cd162014-05-13 15:54:22 +0200272 if (srv->flags & SRV_F_BACKUP)
Emeric Brun52a91d32017-08-31 14:41:55 +0200273 p->lbprm.tot_wbck += srv->next_eweight - srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200274 else
Emeric Brun52a91d32017-08-31 14:41:55 +0200275 p->lbprm.tot_wact += srv->next_eweight - srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200276
277 update_backend_weight(p);
Willy Tarreauc5150da2014-05-13 19:27:31 +0200278 srv_lb_commit_status(srv);
Willy Tarreau1b877482018-08-21 19:44:53 +0200279
280 HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200281}
282
283/*
Andrew Rodland4f88c632016-10-25 12:50:37 -0400284 * This function implements the "Consistent Hashing with Bounded Loads" algorithm
285 * of Mirrokni, Thorup, and Zadimoghaddam (arxiv:1608.01350), adapted for use with
286 * unequal server weights.
287 */
288int chash_server_is_eligible(struct server *s)
289{
290 /* The total number of slots to allocate is the total number of outstanding requests
291 * (including the one we're about to make) times the load-balance-factor, rounded up.
292 */
Willy Tarreau76e84f52019-01-14 16:50:58 +0100293 unsigned tot_slots = ((s->proxy->served + 1) * s->proxy->lbprm.hash_balance_factor + 99) / 100;
Andrew Rodland4f88c632016-10-25 12:50:37 -0400294 unsigned slots_per_weight = tot_slots / s->proxy->lbprm.tot_weight;
295 unsigned remainder = tot_slots % s->proxy->lbprm.tot_weight;
296
297 /* Allocate a whole number of slots per weight unit... */
Emeric Brun52a91d32017-08-31 14:41:55 +0200298 unsigned slots = s->cur_eweight * slots_per_weight;
Andrew Rodland4f88c632016-10-25 12:50:37 -0400299
300 /* And then distribute the rest among servers proportionally to their weight. */
Emeric Brun52a91d32017-08-31 14:41:55 +0200301 slots += ((s->cumulative_weight + s->cur_eweight) * remainder) / s->proxy->lbprm.tot_weight
Andrew Rodland4f88c632016-10-25 12:50:37 -0400302 - (s->cumulative_weight * remainder) / s->proxy->lbprm.tot_weight;
303
304 /* But never leave a server with 0. */
305 if (slots == 0)
306 slots = 1;
307
308 return s->served < slots;
309}
310
311/*
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200312 * This function returns the running server from the CHASH tree, which is at
313 * the closest distance from the value of <hash>. Doing so ensures that even
314 * with a well imbalanced hash, if some servers are close to each other, they
315 * will still both receive traffic. If any server is found, it will be returned.
Willy Tarreau59884a62019-01-02 14:48:31 +0100316 * It will also skip server <avoid> if the hash result ends on this one.
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200317 * If no valid server is found, NULL is returned.
318 */
Willy Tarreau59884a62019-01-02 14:48:31 +0100319struct server *chash_get_server_hash(struct proxy *p, unsigned int hash, const struct server *avoid)
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200320{
321 struct eb32_node *next, *prev;
322 struct server *nsrv, *psrv;
323 struct eb_root *root;
324 unsigned int dn, dp;
Andrew Rodland4f88c632016-10-25 12:50:37 -0400325 int loop;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200326
Willy Tarreau1b877482018-08-21 19:44:53 +0200327 HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
328
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200329 if (p->srv_act)
330 root = &p->lbprm.chash.act;
Willy Tarreau1b877482018-08-21 19:44:53 +0200331 else if (p->lbprm.fbck) {
332 nsrv = p->lbprm.fbck;
333 goto out;
334 }
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200335 else if (p->srv_bck)
336 root = &p->lbprm.chash.bck;
Willy Tarreau1b877482018-08-21 19:44:53 +0200337 else {
338 nsrv = NULL;
339 goto out;
340 }
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200341
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200342 /* find the node after and the node before */
343 next = eb32_lookup_ge(root, hash);
344 if (!next)
345 next = eb32_first(root);
Willy Tarreau1b877482018-08-21 19:44:53 +0200346 if (!next) {
347 nsrv = NULL; /* tree is empty */
348 goto out;
349 }
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200350
351 prev = eb32_prev(next);
352 if (!prev)
353 prev = eb32_last(root);
354
355 nsrv = eb32_entry(next, struct tree_occ, node)->server;
356 psrv = eb32_entry(prev, struct tree_occ, node)->server;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200357
Andrew Rodland18330ab2017-04-26 02:57:03 -0400358 /* OK we're located between two servers, let's
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200359 * compare distances between hash and the two servers
360 * and select the closest server.
361 */
362 dp = hash - prev->key;
363 dn = next->key - hash;
364
Andrew Rodland4f88c632016-10-25 12:50:37 -0400365 if (dp <= dn) {
366 next = prev;
367 nsrv = psrv;
368 }
369
370 loop = 0;
Willy Tarreau76e84f52019-01-14 16:50:58 +0100371 while (nsrv == avoid || (p->lbprm.hash_balance_factor && !chash_server_is_eligible(nsrv))) {
Andrew Rodland4f88c632016-10-25 12:50:37 -0400372 next = eb32_next(next);
373 if (!next) {
374 next = eb32_first(root);
375 if (++loop > 1) // protection against accidental loop
376 break;
377 }
378 nsrv = eb32_entry(next, struct tree_occ, node)->server;
379 }
380
Willy Tarreau1b877482018-08-21 19:44:53 +0200381 out:
382 HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
Andrew Rodland4f88c632016-10-25 12:50:37 -0400383 return nsrv;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200384}
385
386/* Return next server from the CHASH tree in backend <p>. If the tree is empty,
387 * return NULL. Saturated servers are skipped.
388 */
389struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid)
390{
391 struct server *srv, *avoided;
392 struct eb32_node *node, *stop, *avoided_node;
393 struct eb_root *root;
394
395 srv = avoided = NULL;
396 avoided_node = NULL;
397
Christopher Faulet2a944ee2017-11-07 10:42:54 +0100398 HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200399 if (p->srv_act)
400 root = &p->lbprm.chash.act;
Christopher Faulet5b517552017-06-09 14:17:53 +0200401 else if (p->lbprm.fbck) {
402 srv = p->lbprm.fbck;
403 goto out;
404 }
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200405 else if (p->srv_bck)
406 root = &p->lbprm.chash.bck;
Christopher Faulet5b517552017-06-09 14:17:53 +0200407 else {
408 srv = NULL;
409 goto out;
410 }
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200411
412 stop = node = p->lbprm.chash.last;
413 do {
414 struct server *s;
415
416 if (node)
417 node = eb32_next(node);
418 if (!node)
419 node = eb32_first(root);
420
421 p->lbprm.chash.last = node;
Willy Tarreau1ed90ac2017-11-05 10:54:50 +0100422 if (!node) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200423 /* no node is available */
Willy Tarreau1ed90ac2017-11-05 10:54:50 +0100424 srv = NULL;
425 goto out;
426 }
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200427
Willy Tarreaud16a1b22013-04-12 14:46:51 +0200428 /* Note: if we came here after a down/up cycle with no last
429 * pointer, and after a redispatch (srvtoavoid is set), we
430 * must set stop to non-null otherwise we can loop forever.
431 */
432 if (!stop)
433 stop = node;
434
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200435 /* OK, we have a server. However, it may be saturated, in which
436 * case we don't want to reconsider it for now, so we'll simply
437 * skip it. Same if it's the server we try to avoid, in which
438 * case we simply remember it for later use if needed.
439 */
440 s = eb32_entry(node, struct tree_occ, node)->server;
441 if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) {
442 if (s != srvtoavoid) {
443 srv = s;
444 break;
445 }
446 avoided = s;
447 avoided_node = node;
448 }
449 } while (node != stop);
450
451 if (!srv) {
452 srv = avoided;
453 p->lbprm.chash.last = avoided_node;
454 }
455
Christopher Faulet5b517552017-06-09 14:17:53 +0200456 out:
Christopher Faulet2a944ee2017-11-07 10:42:54 +0100457 HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200458 return srv;
459}
460
461/* This function is responsible for building the active and backup trees for
462 * constistent hashing. The servers receive an array of initialized nodes
463 * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to
464 * uweight ratio.
465 */
466void chash_init_server_tree(struct proxy *p)
467{
468 struct server *srv;
469 struct eb_root init_head = EB_ROOT;
470 int node;
471
472 p->lbprm.set_server_status_up = chash_set_server_status_up;
473 p->lbprm.set_server_status_down = chash_set_server_status_down;
474 p->lbprm.update_server_eweight = chash_update_server_weight;
475 p->lbprm.server_take_conn = NULL;
476 p->lbprm.server_drop_conn = NULL;
477
478 p->lbprm.wdiv = BE_WEIGHT_SCALE;
479 for (srv = p->srv; srv; srv = srv->next) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200480 srv->next_eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult;
Willy Tarreauc5150da2014-05-13 19:27:31 +0200481 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200482 }
483
484 recount_servers(p);
485 update_backend_weight(p);
486
487 p->lbprm.chash.act = init_head;
488 p->lbprm.chash.bck = init_head;
489 p->lbprm.chash.last = NULL;
490
491 /* queue active and backup servers in two distinct groups */
492 for (srv = p->srv; srv; srv = srv->next) {
Willy Tarreauc93cd162014-05-13 15:54:22 +0200493 srv->lb_tree = (srv->flags & SRV_F_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200494 srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE;
495 srv->lb_nodes_now = 0;
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200496 srv->lb_nodes = calloc(srv->lb_nodes_tot, sizeof(struct tree_occ));
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200497
498 for (node = 0; node < srv->lb_nodes_tot; node++) {
499 srv->lb_nodes[node].server = srv;
Willy Tarreau4c14eaa2010-11-24 14:01:45 +0100500 srv->lb_nodes[node].node.key = full_hash(srv->puid * SRV_EWGHT_RANGE + node);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200501 }
502
Emeric Brun52a91d32017-08-31 14:41:55 +0200503 if (srv_currently_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200504 chash_queue_dequeue_srv(srv);
505 }
506}