summaryrefslogtreecommitdiffstats
path: root/src/lb_map.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/lb_map.c281
1 files changed, 281 insertions, 0 deletions
diff --git a/src/lb_map.c b/src/lb_map.c
new file mode 100644
index 0000000..592df91
--- /dev/null
+++ b/src/lb_map.c
@@ -0,0 +1,281 @@
+/*
+ * Map-based load-balancing (RR and HASH)
+ *
+ * Copyright 2000-2009 Willy Tarreau <w@1wt.eu>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ *
+ */
+
+#include <import/eb32tree.h>
+#include <haproxy/api.h>
+#include <haproxy/backend.h>
+#include <haproxy/lb_map.h>
+#include <haproxy/queue.h>
+#include <haproxy/server-t.h>
+
+/* this function updates the map according to server <srv>'s new state.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
+ */
+static void map_set_server_status_down(struct server *srv)
+{
+ struct proxy *p = srv->proxy;
+
+ if (!srv_lb_status_changed(srv))
+ return;
+
+ if (srv_willbe_usable(srv))
+ goto out_update_state;
+
+ /* FIXME: could be optimized since we know what changed */
+ HA_RWLOCK_WRLOCK(LBPRM_LOCK, &p->lbprm.lock);
+ recount_servers(p);
+ update_backend_weight(p);
+ recalc_server_map(p);
+ HA_RWLOCK_WRUNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+ out_update_state:
+ srv_lb_commit_status(srv);
+}
+
+/* This function updates the map according to server <srv>'s new state.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
+ */
+static void map_set_server_status_up(struct server *srv)
+{
+ struct proxy *p = srv->proxy;
+
+ if (!srv_lb_status_changed(srv))
+ return;
+
+ if (!srv_willbe_usable(srv))
+ goto out_update_state;
+
+ /* FIXME: could be optimized since we know what changed */
+ HA_RWLOCK_WRLOCK(LBPRM_LOCK, &p->lbprm.lock);
+ recount_servers(p);
+ update_backend_weight(p);
+ recalc_server_map(p);
+ HA_RWLOCK_WRUNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+ out_update_state:
+ srv_lb_commit_status(srv);
+}
+
+/* This function recomputes the server map for proxy px. It relies on
+ * px->lbprm.tot_wact, tot_wbck, tot_used, tot_weight, so it must be
+ * called after recount_servers(). It also expects px->lbprm.map.srv
+ * to be allocated with the largest size needed. It updates tot_weight.
+ *
+ * The lbprm's lock must be held.
+ */
+void recalc_server_map(struct proxy *px)
+{
+ int o, tot, flag;
+ struct server *cur, *best;
+
+ switch (px->lbprm.tot_used) {
+ case 0: /* no server */
+ return;
+ default:
+ tot = px->lbprm.tot_weight;
+ break;
+ }
+
+ /* here we *know* that we have some servers */
+ if (px->srv_act)
+ flag = 0;
+ else
+ flag = SRV_F_BACKUP;
+
+ /* this algorithm gives priority to the first server, which means that
+ * it will respect the declaration order for equivalent weights, and
+ * that whatever the weights, the first server called will always be
+ * the first declared. This is an important assumption for the backup
+ * case, where we want the first server only.
+ */
+ for (cur = px->srv; cur; cur = cur->next)
+ cur->wscore = 0;
+
+ for (o = 0; o < tot; o++) {
+ int max = 0;
+ best = NULL;
+ for (cur = px->srv; cur; cur = cur->next) {
+ if ((cur->flags & SRV_F_BACKUP) == flag &&
+ srv_willbe_usable(cur)) {
+ int v;
+
+ /* If we are forced to return only one server, we don't want to
+ * go further, because we would return the wrong one due to
+ * divide overflow.
+ */
+ if (tot == 1) {
+ best = cur;
+ /* note that best->wscore will be wrong but we don't care */
+ break;
+ }
+
+ _HA_ATOMIC_ADD(&cur->wscore, cur->next_eweight);
+ v = (cur->wscore + tot) / tot; /* result between 0 and 3 */
+ if (best == NULL || v > max) {
+ max = v;
+ best = cur;
+ }
+ }
+ }
+ px->lbprm.map.srv[o] = best;
+ if (best)
+ _HA_ATOMIC_SUB(&best->wscore, tot);
+ }
+}
+
+/* This function is responsible of building the server MAP for map-based LB
+ * algorithms, allocating the map, and setting p->lbprm.wmult to the GCD of the
+ * weights if applicable. It should be called only once per proxy, at config
+ * time.
+ */
+void init_server_map(struct proxy *p)
+{
+ struct server *srv;
+ int pgcd;
+ int act, bck;
+
+ p->lbprm.set_server_status_up = map_set_server_status_up;
+ p->lbprm.set_server_status_down = map_set_server_status_down;
+ p->lbprm.update_server_eweight = NULL;
+
+ if (!p->srv)
+ return;
+
+ /* We will factor the weights to reduce the table,
+ * using Euclide's largest common divisor algorithm.
+ * Since we may have zero weights, we have to first
+ * find a non-zero weight server.
+ */
+ pgcd = 1;
+ srv = p->srv;
+ while (srv && !srv->uweight)
+ srv = srv->next;
+
+ if (srv) {
+ pgcd = srv->uweight; /* note: cannot be zero */
+ while (pgcd > 1 && (srv = srv->next)) {
+ int w = srv->uweight;
+ while (w) {
+ int t = pgcd % w;
+ pgcd = w;
+ w = t;
+ }
+ }
+ }
+
+ /* It is sometimes useful to know what factor to apply
+ * to the backend's effective weight to know its real
+ * weight.
+ */
+ p->lbprm.wmult = pgcd;
+
+ act = bck = 0;
+ for (srv = p->srv; srv; srv = srv->next) {
+ srv->next_eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult;
+
+ if (srv->flags & SRV_F_BACKUP)
+ bck += srv->next_eweight;
+ else
+ act += srv->next_eweight;
+ srv_lb_commit_status(srv);
+ }
+
+ /* this is the largest map we will ever need for this servers list */
+ if (act < bck)
+ act = bck;
+
+ if (!act)
+ act = 1;
+
+ p->lbprm.map.srv = calloc(act, sizeof(*p->lbprm.map.srv));
+ /* recounts servers and their weights */
+ recount_servers(p);
+ update_backend_weight(p);
+ recalc_server_map(p);
+}
+
+/*
+ * This function tries to find a running server with free connection slots for
+ * the proxy <px> following the round-robin method.
+ * If any server is found, it will be returned and px->lbprm.map.rr_idx will be updated
+ * to point to the next server. If no valid server is found, NULL is returned.
+ *
+ * The lbprm's lock will be used.
+ */
+struct server *map_get_server_rr(struct proxy *px, struct server *srvtoavoid)
+{
+ int newidx, avoididx;
+ struct server *srv, *avoided;
+
+ HA_RWLOCK_SKLOCK(LBPRM_LOCK, &px->lbprm.lock);
+ if (px->lbprm.tot_weight == 0) {
+ avoided = NULL;
+ goto out;
+ }
+
+ if (px->lbprm.map.rr_idx < 0 || px->lbprm.map.rr_idx >= px->lbprm.tot_weight)
+ px->lbprm.map.rr_idx = 0;
+ newidx = px->lbprm.map.rr_idx;
+
+ avoided = NULL;
+ avoididx = 0; /* shut a gcc warning */
+ do {
+ srv = px->lbprm.map.srv[newidx++];
+ if (!srv->maxconn || (!srv->queue.length && srv->served < srv_dynamic_maxconn(srv))) {
+ /* make sure it is not the server we are try to exclude... */
+ /* ...but remember that is was selected yet avoided */
+ avoided = srv;
+ avoididx = newidx;
+ if (srv != srvtoavoid) {
+ px->lbprm.map.rr_idx = newidx;
+ goto out;
+ }
+ }
+ if (newidx == px->lbprm.tot_weight)
+ newidx = 0;
+ } while (newidx != px->lbprm.map.rr_idx);
+
+ if (avoided)
+ px->lbprm.map.rr_idx = avoididx;
+
+ out:
+ HA_RWLOCK_SKUNLOCK(LBPRM_LOCK, &px->lbprm.lock);
+ /* return NULL or srvtoavoid if found */
+ return avoided;
+}
+
+/*
+ * This function returns the running server from the map at the location
+ * pointed to by the result of a modulo operation on <hash>. The server map may
+ * be recomputed if required before being looked up. If any server is found, it
+ * will be returned. If no valid server is found, NULL is returned.
+ *
+ * The lbprm's lock will be used.
+ */
+struct server *map_get_server_hash(struct proxy *px, unsigned int hash)
+{
+ struct server *srv = NULL;
+
+ HA_RWLOCK_RDLOCK(LBPRM_LOCK, &px->lbprm.lock);
+ if (px->lbprm.tot_weight)
+ srv = px->lbprm.map.srv[hash % px->lbprm.tot_weight];
+ HA_RWLOCK_RDUNLOCK(LBPRM_LOCK, &px->lbprm.lock);
+ return srv;
+}
+
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */