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.
diff --git a/include/proto/queue.h b/include/proto/queue.h
index 11696db..166da12 100644
--- a/include/proto/queue.h
+++ b/include/proto/queue.h
@@ -52,7 +52,7 @@
*/
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 234a142..37a5060 100644
--- a/include/types/proxy.h
+++ b/include/types/proxy.h
@@ -322,7 +322,7 @@
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 575cc59..361c704 100644
--- a/include/types/queue.h
+++ b/include/types/queue.h
@@ -37,7 +37,7 @@
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 7d0ba45..8825928 100644
--- a/include/types/server.h
+++ b/include/types/server.h
@@ -215,7 +215,7 @@
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 4d42b1f..bea9c46 100644
--- a/src/hlua.c
+++ b/src/hlua.c
@@ -8007,7 +8007,7 @@
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 @@
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 bf87a2f..ff094d2 100644
--- a/src/proxy.c
+++ b/src/proxy.c
@@ -726,7 +726,7 @@
{
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 4c8c4c9..6bcaba5 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 <common/memory.h>
#include <common/time.h>
#include <common/hathreads.h>
+#include <eb32tree.h>
#include <proto/queue.h>
#include <proto/server.h>
@@ -137,8 +138,7 @@
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 @@
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 @@
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 @@
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 @@
*/
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 @@
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_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 @@
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 @@
* 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 c885deb..1d7a5a7 100644
--- a/src/server.c
+++ b/src/server.c
@@ -1627,7 +1627,7 @@
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;