From 0355dabd7cf19bcb25afef41e666435f05f01e37 Mon Sep 17 00:00:00 2001 From: Patrick Hemmer Date: Fri, 11 May 2018 12:52:31 -0400 Subject: [PATCH] MINOR: queue: replace the linked list with a tree We'll need trees to manage the queues by priorities. This change replaces the list with a tree based on a single key. It's effectively a list but allows us to get rid of the list management right now. --- include/proto/queue.h | 2 +- include/types/proxy.h | 2 +- include/types/queue.h | 2 +- include/types/server.h | 2 +- src/hlua.c | 4 ++-- src/proxy.c | 2 +- src/queue.c | 35 ++++++++++++++++++++++------------- src/server.c | 2 +- 8 files changed, 30 insertions(+), 21 deletions(-) diff --git a/include/proto/queue.h b/include/proto/queue.h index 11696dbc47..166da12f40 100644 --- a/include/proto/queue.h +++ b/include/proto/queue.h @@ -52,7 +52,7 @@ void pendconn_unlink(struct pendconn *p); */ static inline void pendconn_cond_unlink(struct pendconn *p) { - if (p && !LIST_ISEMPTY(&p->list)) + if (p && p->node.node.leaf_p) pendconn_unlink(p); } diff --git a/include/types/proxy.h b/include/types/proxy.h index 234a142c06..37a50609ca 100644 --- a/include/types/proxy.h +++ b/include/types/proxy.h @@ -322,7 +322,7 @@ struct proxy { int serverfin; /* timeout to apply to server half-closed connections */ } timeout; char *id, *desc; /* proxy id (name) and description */ - struct list pendconns; /* pending connections with no server assigned yet */ + struct eb_root pendconns; /* pending connections with no server assigned yet */ int nbpend; /* number of pending connections with no server assigned yet */ int totpend; /* total number of pending connections on this instance (for stats) */ unsigned int queue_idx; /* number of pending connections which have been de-queued */ diff --git a/include/types/queue.h b/include/types/queue.h index 575cc59298..361c704d04 100644 --- a/include/types/queue.h +++ b/include/types/queue.h @@ -37,7 +37,7 @@ struct pendconn { struct proxy *px; struct server *srv; /* the server we are waiting for, may be NULL if don't care */ struct server *target; /* the server that was assigned, = srv except if srv==NULL */ - struct list list; /* next pendconn */ + struct eb32_node node; }; #endif /* _TYPES_QUEUE_H */ diff --git a/include/types/server.h b/include/types/server.h index 7d0ba4571e..88259281d1 100644 --- a/include/types/server.h +++ b/include/types/server.h @@ -215,7 +215,7 @@ struct server { struct freq_ctr sess_per_sec; /* sessions per second on this server */ struct be_counters counters; /* statistics counters */ - struct list pendconns; /* pending connections */ + struct eb_root pendconns; /* pending connections */ struct list actconns; /* active connections */ struct list *priv_conns; /* private idle connections attached to stream interfaces */ struct list *idle_conns; /* sharable idle connections attached or not to a stream interface */ diff --git a/src/hlua.c b/src/hlua.c index 4d42b1fec8..bea9c46949 100644 --- a/src/hlua.c +++ b/src/hlua.c @@ -8007,7 +8007,7 @@ void hlua_init(void) socket_tcp.proxy = &socket_proxy; socket_tcp.obj_type = OBJ_TYPE_SERVER; LIST_INIT(&socket_tcp.actconns); - LIST_INIT(&socket_tcp.pendconns); + socket_tcp.pendconns = EB_ROOT; socket_tcp.priv_conns = NULL; socket_tcp.idle_conns = NULL; socket_tcp.safe_conns = NULL; @@ -8053,7 +8053,7 @@ void hlua_init(void) socket_ssl.proxy = &socket_proxy; socket_ssl.obj_type = OBJ_TYPE_SERVER; LIST_INIT(&socket_ssl.actconns); - LIST_INIT(&socket_ssl.pendconns); + socket_ssl.pendconns = EB_ROOT; socket_tcp.priv_conns = NULL; socket_tcp.idle_conns = NULL; socket_tcp.safe_conns = NULL; diff --git a/src/proxy.c b/src/proxy.c index bf87a2f9c2..ff094d210f 100644 --- a/src/proxy.c +++ b/src/proxy.c @@ -726,7 +726,7 @@ void init_new_proxy(struct proxy *p) { memset(p, 0, sizeof(struct proxy)); p->obj_type = OBJ_TYPE_PROXY; - LIST_INIT(&p->pendconns); + p->pendconns = EB_ROOT; LIST_INIT(&p->acl); LIST_INIT(&p->http_req_rules); LIST_INIT(&p->http_res_rules); diff --git a/src/queue.c b/src/queue.c index 4c8c4c9cd5..6bcaba5c14 100644 --- a/src/queue.c +++ b/src/queue.c @@ -21,7 +21,7 @@ * A stream does not necessarily have such a pendconn. Thus the pendconn is * designated by the stream->pend_pos pointer. This results in some properties : * - pendconn->strm->pend_pos is never NULL for any valid pendconn - * - if LIST_ISEMPTY(pendconn->list) is true, the element is unlinked, + * - if p->node.node.leaf_p is NULL, the element is unlinked, * otherwise it necessarily belongs to one of the other lists ; this may * not be atomically checked under threads though ; * - pendconn->px is never NULL if pendconn->list is not empty @@ -73,6 +73,7 @@ #include #include #include +#include #include #include @@ -137,8 +138,7 @@ static void __pendconn_unlink(struct pendconn *p) p->px->nbpend--; } HA_ATOMIC_SUB(&p->px->totpend, 1); - LIST_DEL(&p->list); - LIST_INIT(&p->list); + eb32_delete(&p->node); } /* Locks the queue the pendconn element belongs to. This relies on both p->px @@ -204,20 +204,24 @@ static int pendconn_process_next_strm(struct server *srv, struct proxy *px) struct pendconn *p = NULL; struct pendconn *pp = NULL; struct server *rsrv; + struct eb32_node *node; rsrv = srv->track; if (!rsrv) rsrv = srv; p = NULL; - if (srv->nbpend) - p = LIST_ELEM(srv->pendconns.n, struct pendconn *, list); + if (srv->nbpend) { + node = eb32_first(&srv->pendconns); + p = eb32_entry(node, struct pendconn, node); + } if (srv_currently_usable(rsrv) && px->nbpend && (!(srv->flags & SRV_F_BACKUP) || (!px->srv_act && (srv == px->lbprm.fbck || (px->options & PR_O_USE_ALL_BK))))) { - pp = LIST_ELEM(px->pendconns.n, struct pendconn *, list); + node = eb32_first(&px->pendconns); + pp = eb32_entry(node, struct pendconn, node); /* If the server pendconn is older than the proxy one, * we process the server one. @@ -303,6 +307,7 @@ struct pendconn *pendconn_add(struct stream *strm) px = strm->be; p->target = NULL; p->srv = srv; + p->node.key = 0; p->px = px; p->strm = strm; p->strm_flags = strm->flags; @@ -314,14 +319,14 @@ struct pendconn *pendconn_add(struct stream *strm) if (srv->nbpend > srv->counters.nbpend_max) srv->counters.nbpend_max = srv->nbpend; p->queue_idx = srv->queue_idx - 1; // for increment - LIST_ADDQ(&srv->pendconns, &p->list); + eb32_insert(&srv->pendconns, &p->node); } else { px->nbpend++; if (px->nbpend > px->be_counters.nbpend_max) px->be_counters.nbpend_max = px->nbpend; p->queue_idx = px->queue_idx - 1; // for increment - LIST_ADDQ(&px->pendconns, &p->list); + eb32_insert(&px->pendconns, &p->node); } strm->pend_pos = p; @@ -336,7 +341,8 @@ struct pendconn *pendconn_add(struct stream *strm) */ int pendconn_redistribute(struct server *s) { - struct pendconn *p, *pback; + struct pendconn *p; + struct eb32_node *node; int xferred = 0; /* The REDISP option was specified. We will ignore cookie and force to @@ -345,7 +351,8 @@ int pendconn_redistribute(struct server *s) return 0; HA_SPIN_LOCK(SERVER_LOCK, &s->lock); - list_for_each_entry_safe(p, pback, &s->pendconns, list) { + for (node = eb32_first(&s->pendconns); node; node = eb32_next(node)) { + p = eb32_entry(&node, struct pendconn, node); if (p->strm_flags & SF_FORCE_PRST) continue; @@ -366,7 +373,8 @@ int pendconn_redistribute(struct server *s) */ int pendconn_grab_from_px(struct server *s) { - struct pendconn *p, *pback; + struct pendconn *p; + struct eb32_node *node; int maxconn, xferred = 0; if (!srv_currently_usable(s)) @@ -383,7 +391,8 @@ int pendconn_grab_from_px(struct server *s) HA_SPIN_LOCK(PROXY_LOCK, &s->proxy->lock); maxconn = srv_dynamic_maxconn(s); - list_for_each_entry_safe(p, pback, &s->proxy->pendconns, list) { + while ((node = eb32_first(&s->proxy->pendconns))) { + p = eb32_entry(&node, struct pendconn, node); if (s->maxconn && s->served + xferred >= maxconn) break; @@ -428,7 +437,7 @@ int pendconn_dequeue(struct stream *strm) * unlinked, these functions were completely done. */ pendconn_queue_lock(p); - is_unlinked = LIST_ISEMPTY(&p->list); + is_unlinked = !p->node.node.leaf_p; pendconn_queue_unlock(p); if (!is_unlinked) diff --git a/src/server.c b/src/server.c index c885debca6..1d7a5a771e 100644 --- a/src/server.c +++ b/src/server.c @@ -1627,7 +1627,7 @@ static struct server *new_server(struct proxy *proxy) srv->obj_type = OBJ_TYPE_SERVER; srv->proxy = proxy; LIST_INIT(&srv->actconns); - LIST_INIT(&srv->pendconns); + srv->pendconns = EB_ROOT; if ((srv->priv_conns = calloc(global.nbthread, sizeof(*srv->priv_conns))) == NULL) goto free_srv; -- 2.39.5