BUG/MEDIUM: lists: Lock the element while we check if it is in a list.
In MT_LIST_TRY_ADDQ() and MT_LIST_TRY_ADD() we can't just check if the
element is already in a list, because there's a small race condition, it
could be added between the time we checked, and the time we actually set
its next and prev, so we have to lock it first.
This is required to address issue #958.
This should be backported to 2.3, 2.2 and 2.1.
(cherry picked from commit 1f05324cbe92a7dde71f44dc740eb8240539746f)
Signed-off-by: Christopher Faulet <cfaulet@haproxy.com>
diff --git a/include/haproxy/list.h b/include/haproxy/list.h
index dae5ca2..6db2f92 100644
--- a/include/haproxy/list.h
+++ b/include/haproxy/list.h
@@ -230,8 +230,8 @@
int _ret = 0; \
struct mt_list *lh = (_lh), *el = (_el); \
while (1) { \
- struct mt_list *n; \
- struct mt_list *p; \
+ struct mt_list *n, *n2; \
+ struct mt_list *p, *p2; \
n = _HA_ATOMIC_XCHG(&(lh)->next, MT_LIST_BUSY); \
if (n == MT_LIST_BUSY) \
continue; \
@@ -241,12 +241,31 @@
__ha_barrier_store(); \
continue; \
} \
- if ((el)->next != (el) || (el)->prev != (el)) { \
- (n)->prev = p; \
- (lh)->next = n; \
+ n2 = _HA_ATOMIC_XCHG(&el->next, MT_LIST_BUSY); \
+ if (n2 != el) { /* element already linked */ \
+ if (n2 != MT_LIST_BUSY) \
+ el->next = n2; \
+ n->prev = p; \
+ __ha_barrier_store(); \
+ lh->next = n; \
__ha_barrier_store(); \
+ if (n2 == MT_LIST_BUSY) \
+ continue; \
break; \
} \
+ p2 = _HA_ATOMIC_XCHG(&el->prev, MT_LIST_BUSY); \
+ if (p2 != el) { \
+ if (p2 != MT_LIST_BUSY) \
+ el->prev = p2; \
+ n->prev = p; \
+ el->next = el; \
+ __ha_barrier_store(); \
+ lh->next = n; \
+ __ha_barrier_store(); \
+ if (p2 == MT_LIST_BUSY) \
+ continue; \
+ break; \
+ } \
(el)->next = n; \
(el)->prev = p; \
__ha_barrier_store(); \
@@ -270,8 +289,8 @@
int _ret = 0; \
struct mt_list *lh = (_lh), *el = (_el); \
while (1) { \
- struct mt_list *n; \
- struct mt_list *p; \
+ struct mt_list *n, *n2; \
+ struct mt_list *p, *p2; \
p = _HA_ATOMIC_XCHG(&(lh)->prev, MT_LIST_BUSY); \
if (p == MT_LIST_BUSY) \
continue; \
@@ -281,10 +300,29 @@
__ha_barrier_store(); \
continue; \
} \
- if ((el)->next != (el) || (el)->prev != (el)) { \
+ n2 = _HA_ATOMIC_XCHG(&el->next, MT_LIST_BUSY); \
+ if (n2 != el) { /* element already linked */ \
+ if (n2 != MT_LIST_BUSY) \
+ el->next = n2; \
p->next = n; \
- (lh)->prev = p; \
+ __ha_barrier_store(); \
+ lh->prev = p; \
+ __ha_barrier_store(); \
+ if (n2 == MT_LIST_BUSY) \
+ continue; \
+ break; \
+ } \
+ p2 = _HA_ATOMIC_XCHG(&el->prev, MT_LIST_BUSY); \
+ if (p2 != el) { \
+ if (p2 != MT_LIST_BUSY) \
+ el->prev = p2; \
+ p->next = n; \
+ el->next = el; \
+ __ha_barrier_store(); \
+ lh->prev = p; \
__ha_barrier_store(); \
+ if (p2 == MT_LIST_BUSY) \
+ continue; \
break; \
} \
(el)->next = n; \