/* * include/haproxy/list.h * Circular list manipulation macros and functions. * * Copyright (C) 2002-2020 Willy Tarreau - w@1wt.eu * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation, version 2.1 * exclusively. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef _HAPROXY_LIST_H #define _HAPROXY_LIST_H #include #include /* First undefine some macros which happen to also be defined on OpenBSD, * in sys/queue.h, used by sys/event.h */ #undef LIST_HEAD #undef LIST_INIT #undef LIST_NEXT /* ILH = Initialized List Head : used to prevent gcc from moving an empty * list to BSS. Some older version tend to trim all the array and cause * corruption. */ #define ILH { .n = (struct list *)1, .p = (struct list *)2 } #define LIST_HEAD(a) ((void *)(&(a))) #define LIST_INIT(l) ((l)->n = (l)->p = (l)) #define LIST_HEAD_INIT(l) { &l, &l } /* adds an element at the beginning of a list ; returns the element */ #define LIST_INSERT(lh, el) ({ (el)->n = (lh)->n; (el)->n->p = (lh)->n = (el); (el)->p = (lh); (el); }) /* adds an element at the end of a list ; returns the element */ #define LIST_APPEND(lh, el) ({ (el)->p = (lh)->p; (el)->p->n = (lh)->p = (el); (el)->n = (lh); (el); }) /* adds the contents of a list at the beginning of another list . The old list head remains untouched. */ #define LIST_SPLICE(new, old) do { \ if (!LIST_ISEMPTY(old)) { \ (old)->p->n = (new)->n; (old)->n->p = (new); \ (new)->n->p = (old)->p; (new)->n = (old)->n; \ } \ } while (0) /* adds the contents of a list whose first element is and last one is * prev> at the end of another list . The old list DOES NOT have * any head here. */ #define LIST_SPLICE_END_DETACHED(new, old) do { \ typeof(new) __t; \ (new)->p->n = (old); \ (old)->p->n = (new); \ __t = (old)->p; \ (old)->p = (new)->p; \ (new)->p = __t; \ } while (0) /* removes an element from a list and returns it */ #if defined(DEBUG_LIST) /* purposely corrupt the detached element to detect use-after-delete */ #define LIST_DELETE(el) ({ typeof(el) __ret = (el); (el)->n->p = (el)->p; (el)->p->n = (el)->n; *(__ret) = (struct list)ILH; (__ret);}) #else #define LIST_DELETE(el) ({ typeof(el) __ret = (el); (el)->n->p = (el)->p; (el)->p->n = (el)->n; (__ret); }) #endif /* removes an element from a list, initializes it and returns it. * This is faster than LIST_DELETE+LIST_INIT as we avoid reloading the pointers. */ #define LIST_DEL_INIT(el) ({ \ typeof(el) __ret = (el); \ typeof(__ret->n) __n = __ret->n; \ typeof(__ret->p) __p = __ret->p; \ __n->p = __p; __p->n = __n; \ __ret->n = __ret->p = __ret; \ __ret; \ }) /* returns a pointer of type to a structure containing a list head called * at address . Note that can be the result of a function or macro * since it's used only once. * Example: LIST_ELEM(cur_node->args.next, struct node *, args) */ #define LIST_ELEM(lh, pt, el) ((pt)(((const char *)(lh)) - ((size_t)&((pt)NULL)->el))) /* checks if the list head is empty or not */ #define LIST_ISEMPTY(lh) ((lh)->n == (lh)) /* checks if the list element was added to a list or not. This only * works when detached elements are reinitialized (using LIST_DEL_INIT) */ #define LIST_INLIST(el) ((el)->n != (el)) /* checks if the list element has the same prev and next, i.e. it's either * detached or alone in a list since (it points to itself or to a single other * node). One can check that an element is strictly attached and alone by * combining this with LIST_INLIST(). */ #define LIST_ATMOST1(el) ((el)->n == (el)->p) /* atomically checks if the list element's next pointer points to anything * different from itself, implying the element should be part of a list. This * usually is similar to LIST_INLIST() except that while that one might be * instrumented using debugging code to perform further consistency checks, * the macro below guarantees to always perform a single atomic test and is * safe to use with barriers. */ #define LIST_INLIST_ATOMIC(el) ({ \ typeof(el) __ptr = (el); \ HA_ATOMIC_LOAD(&(__ptr)->n) != __ptr; \ }) /* returns a pointer of type to a structure following the element * which contains list head , which is known as element in * struct pt. * Example: LIST_NEXT(args, struct node *, list) */ #define LIST_NEXT(lh, pt, el) (LIST_ELEM((lh)->n, pt, el)) /* returns a pointer of type to a structure preceding the element * which contains list head , which is known as element in * struct pt. */ #undef LIST_PREV #define LIST_PREV(lh, pt, el) (LIST_ELEM((lh)->p, pt, el)) /* * Simpler FOREACH_ITEM macro inspired from Linux sources. * Iterates through a list of items of type "typeof(*item)" which are * linked via a "struct list" member named . A pointer to the head of * the list is passed in . No temporary variable is needed. Note * that must not be modified during the loop. * Example: list_for_each_entry(cur_acl, known_acl, list) { ... }; */ #define list_for_each_entry(item, list_head, member) \ for (item = LIST_ELEM((list_head)->n, typeof(item), member); \ &item->member != (list_head); \ item = LIST_ELEM(item->member.n, typeof(item), member)) /* * Same as list_for_each_entry but starting from current point * Iterates through the list starting from * It's basically the same macro but without initializing item to the head of * the list. */ #define list_for_each_entry_from(item, list_head, member) \ for ( ; &item->member != (list_head); \ item = LIST_ELEM(item->member.n, typeof(item), member)) /* * Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources. * Iterates through a list of items of type "typeof(*item)" which are * linked via a "struct list" member named . A pointer to the head of * the list is passed in . A temporary variable of same type * as is needed so that may safely be deleted if needed. * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list) { ... }; */ #define list_for_each_entry_safe(item, back, list_head, member) \ for (item = LIST_ELEM((list_head)->n, typeof(item), member), \ back = LIST_ELEM(item->member.n, typeof(item), member); \ &item->member != (list_head); \ item = back, back = LIST_ELEM(back->member.n, typeof(back), member)) /* * Same as list_for_each_entry_safe but starting from current point * Iterates through the list starting from * It's basically the same macro but without initializing item to the head of * the list. */ #define list_for_each_entry_safe_from(item, back, list_head, member) \ for (back = LIST_ELEM(item->member.n, typeof(item), member); \ &item->member != (list_head); \ item = back, back = LIST_ELEM(back->member.n, typeof(back), member)) /* * Iterate backwards through a list of items of type "typeof(*item)" * which are linked via a "struct list" member named . A pointer to * the head of the list is passed in . No temporary variable is * needed. Note that must not be modified during the loop. * Example: list_for_each_entry_rev(cur_acl, known_acl, list) { ... }; */ #define list_for_each_entry_rev(item, list_head, member) \ for (item = LIST_ELEM((list_head)->p, typeof(item), member); \ &item->member != (list_head); \ item = LIST_ELEM(item->member.p, typeof(item), member)) /* * Same as list_for_each_entry_rev but starting from current point * Iterate backwards through the list starting from * It's basically the same macro but without initializing item to the head of * the list. */ #define list_for_each_entry_from_rev(item, list_head, member) \ for ( ; &item->member != (list_head); \ item = LIST_ELEM(item->member.p, typeof(item), member)) /* * Iterate backwards through a list of items of type "typeof(*item)" * which are linked via a "struct list" member named . A pointer to * the head of the list is passed in . A temporary variable * of same type as is needed so that may safely be deleted * if needed. * Example: list_for_each_entry_safe_rev(cur_acl, tmp, known_acl, list) { ... }; */ #define list_for_each_entry_safe_rev(item, back, list_head, member) \ for (item = LIST_ELEM((list_head)->p, typeof(item), member), \ back = LIST_ELEM(item->member.p, typeof(item), member); \ &item->member != (list_head); \ item = back, back = LIST_ELEM(back->member.p, typeof(back), member)) /* * Same as list_for_each_entry_safe_rev but starting from current point * Iterate backwards through the list starting from * It's basically the same macro but without initializing item to the head of * the list. */ #define list_for_each_entry_safe_from_rev(item, back, list_head, member) \ for (back = LIST_ELEM(item->member.p, typeof(item), member); \ &item->member != (list_head); \ item = back, back = LIST_ELEM(back->member.p, typeof(back), member)) /* * Locked version of list manipulation macros. * It is OK to use those concurrently from multiple threads, as long as the * list is only used with the locked variants. */ #define MT_LIST_BUSY ((struct mt_list *)1) /* * Add an item at the beginning of a list. * Returns 1 if we added the item, 0 otherwise (because it was already in a * list). */ #define MT_LIST_TRY_INSERT(_lh, _el) \ ({ \ int _ret = 0; \ struct mt_list *lh = (_lh), *el = (_el); \ for (;;__ha_cpu_relax()) { \ 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; \ p = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) { \ (lh)->next = n; \ __ha_barrier_store(); \ continue; \ } \ 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(); \ n->prev = (el); \ __ha_barrier_store(); \ p->next = (el); \ __ha_barrier_store(); \ _ret = 1; \ break; \ } \ (_ret); \ }) /* * Add an item at the end of a list. * Returns 1 if we added the item, 0 otherwise (because it was already in a * list). */ #define MT_LIST_TRY_APPEND(_lh, _el) \ ({ \ int _ret = 0; \ struct mt_list *lh = (_lh), *el = (_el); \ for (;;__ha_cpu_relax()) { \ 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; \ n = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) { \ (lh)->prev = p; \ __ha_barrier_store(); \ continue; \ } \ p2 = _HA_ATOMIC_XCHG(&el->prev, MT_LIST_BUSY); \ if (p2 != el) { \ if (p2 != MT_LIST_BUSY) \ el->prev = p2; \ p->next = n; \ __ha_barrier_store(); \ lh->prev = p; \ __ha_barrier_store(); \ if (p2 == MT_LIST_BUSY) \ continue; \ break; \ } \ 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; \ el->prev = el; \ __ha_barrier_store(); \ lh->prev = p; \ __ha_barrier_store(); \ if (n2 == MT_LIST_BUSY) \ continue; \ break; \ } \ (el)->next = n; \ (el)->prev = p; \ __ha_barrier_store(); \ p->next = (el); \ __ha_barrier_store(); \ n->prev = (el); \ __ha_barrier_store(); \ _ret = 1; \ break; \ } \ (_ret); \ }) /* * Add an item at the beginning of a list. * It is assumed the element can't already be in a list, so it isn't checked. */ #define MT_LIST_INSERT(_lh, _el) \ ({ \ int _ret = 0; \ struct mt_list *lh = (_lh), *el = (_el); \ for (;;__ha_cpu_relax()) { \ struct mt_list *n; \ struct mt_list *p; \ n = _HA_ATOMIC_XCHG(&(lh)->next, MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) \ continue; \ p = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) { \ (lh)->next = n; \ __ha_barrier_store(); \ continue; \ } \ (el)->next = n; \ (el)->prev = p; \ __ha_barrier_store(); \ n->prev = (el); \ __ha_barrier_store(); \ p->next = (el); \ __ha_barrier_store(); \ _ret = 1; \ break; \ } \ (_ret); \ }) /* * Add an item at the end of a list. * It is assumed the element can't already be in a list, so it isn't checked */ #define MT_LIST_APPEND(_lh, _el) \ ({ \ int _ret = 0; \ struct mt_list *lh = (_lh), *el = (_el); \ for (;;__ha_cpu_relax()) { \ struct mt_list *n; \ struct mt_list *p; \ p = _HA_ATOMIC_XCHG(&(lh)->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) \ continue; \ n = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) { \ (lh)->prev = p; \ __ha_barrier_store(); \ continue; \ } \ (el)->next = n; \ (el)->prev = p; \ __ha_barrier_store(); \ p->next = (el); \ __ha_barrier_store(); \ n->prev = (el); \ __ha_barrier_store(); \ _ret = 1; \ break; \ } \ (_ret); \ }) /* * Add an item at the end of a list. * It is assumed the element can't already be in a list, so it isn't checked * Item will be added in busy/locked state, so that it is already * referenced in the list but no other thread can use it until we're ready. * * This returns a struct mt_list, that will be needed at unlock time. * (using MT_LIST_UNLOCK_ELT) */ #define MT_LIST_APPEND_LOCKED(_lh, _el) \ ({ \ struct mt_list np; \ struct mt_list *lh = (_lh), *el = (_el); \ (el)->next = MT_LIST_BUSY; \ (el)->prev = MT_LIST_BUSY; \ for (;;__ha_cpu_relax()) { \ struct mt_list *n; \ struct mt_list *p; \ p = _HA_ATOMIC_XCHG(&(lh)->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) \ continue; \ n = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) { \ (lh)->prev = p; \ __ha_barrier_store(); \ continue; \ } \ np.prev = p; \ np.next = n; \ break; \ } \ (np); \ }) /* * Detach a list from its head. A pointer to the first element is returned * and the list is closed. If the list was empty, NULL is returned. This may * exclusively be used with lists modified by MT_LIST_TRY_INSERT/MT_LIST_TRY_APPEND. This * is incompatible with MT_LIST_DELETE run concurrently. * If there's at least one element, the next of the last element will always * be NULL. */ #define MT_LIST_BEHEAD(_lh) ({ \ struct mt_list *lh = (_lh); \ struct mt_list *_n; \ struct mt_list *_p; \ for (;;__ha_cpu_relax()) { \ _p = _HA_ATOMIC_XCHG(&(lh)->prev, MT_LIST_BUSY); \ if (_p == MT_LIST_BUSY) \ continue; \ if (_p == (lh)) { \ (lh)->prev = _p; \ __ha_barrier_store(); \ _n = NULL; \ break; \ } \ _n = _HA_ATOMIC_XCHG(&(lh)->next, MT_LIST_BUSY); \ if (_n == MT_LIST_BUSY) { \ (lh)->prev = _p; \ __ha_barrier_store(); \ continue; \ } \ if (_n == (lh)) { \ (lh)->next = _n; \ (lh)->prev = _p; \ __ha_barrier_store(); \ _n = NULL; \ break; \ } \ (lh)->next = (lh); \ (lh)->prev = (lh); \ __ha_barrier_store(); \ _n->prev = _p; \ __ha_barrier_store(); \ _p->next = NULL; \ __ha_barrier_store(); \ break; \ } \ (_n); \ }) /* Remove an item from a list. * Returns 1 if we removed the item, 0 otherwise (because it was in no list). */ #define MT_LIST_DELETE(_el) \ ({ \ int _ret = 0; \ struct mt_list *el = (_el); \ for (;;__ha_cpu_relax()) { \ struct mt_list *n, *n2; \ struct mt_list *p, *p2 = NULL; \ n = _HA_ATOMIC_XCHG(&(el)->next, MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) \ continue; \ p = _HA_ATOMIC_XCHG(&(el)->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) { \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ if (p != (el)) { \ p2 = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY); \ if (p2 == MT_LIST_BUSY) { \ (el)->prev = p; \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ } \ if (n != (el)) { \ n2 = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \ if (n2 == MT_LIST_BUSY) { \ if (p2 != NULL) \ p->next = p2; \ (el)->prev = p; \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ } \ n->prev = p; \ p->next = n; \ if (p != (el) && n != (el)) \ _ret = 1; \ __ha_barrier_store(); \ (el)->prev = (el); \ (el)->next = (el); \ __ha_barrier_store(); \ break; \ } \ (_ret); \ }) /* Remove the first element from the list, and return it */ #define MT_LIST_POP(_lh, pt, el) \ ({ \ void *_ret; \ struct mt_list *lh = (_lh); \ for (;;__ha_cpu_relax()) { \ 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; \ if (n == (lh)) { \ (lh)->next = lh; \ __ha_barrier_store(); \ _ret = NULL; \ break; \ } \ p = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) { \ (lh)->next = n; \ __ha_barrier_store(); \ continue; \ } \ n2 = _HA_ATOMIC_XCHG(&n->next, MT_LIST_BUSY); \ if (n2 == MT_LIST_BUSY) { \ n->prev = p; \ __ha_barrier_store(); \ (lh)->next = n; \ __ha_barrier_store(); \ continue; \ } \ p2 = _HA_ATOMIC_XCHG(&n2->prev, MT_LIST_BUSY); \ if (p2 == MT_LIST_BUSY) { \ n->next = n2; \ n->prev = p; \ __ha_barrier_store(); \ (lh)->next = n; \ __ha_barrier_store(); \ continue; \ } \ (lh)->next = n2; \ (n2)->prev = (lh); \ __ha_barrier_store(); \ (n)->prev = (n); \ (n)->next = (n); \ __ha_barrier_store(); \ _ret = MT_LIST_ELEM(n, pt, el); \ break; \ } \ (_ret); \ }) #define MT_LIST_HEAD(a) ((void *)(&(a))) #define MT_LIST_INIT(l) ((l)->next = (l)->prev = (l)) #define MT_LIST_HEAD_INIT(l) { &l, &l } /* returns a pointer of type to a structure containing a list head called * at address . Note that can be the result of a function or macro * since it's used only once. * Example: MT_LIST_ELEM(cur_node->args.next, struct node *, args) */ #define MT_LIST_ELEM(lh, pt, el) ((pt)(((const char *)(lh)) - ((size_t)&((pt)NULL)->el))) /* checks if the list head is empty or not */ #define MT_LIST_ISEMPTY(lh) ((lh)->next == (lh)) /* returns a pointer of type to a structure following the element * which contains list head , which is known as element in * struct pt. * Example: MT_LIST_NEXT(args, struct node *, list) */ #define MT_LIST_NEXT(lh, pt, el) (MT_LIST_ELEM((lh)->next, pt, el)) /* returns a pointer of type to a structure preceding the element * which contains list head , which is known as element in * struct pt. */ #undef MT_LIST_PREV #define MT_LIST_PREV(lh, pt, el) (MT_LIST_ELEM((lh)->prev, pt, el)) /* checks if the list element was added to a list or not. This only * works when detached elements are reinitialized (using LIST_DEL_INIT) */ #define MT_LIST_INLIST(el) ((el)->next != (el)) /* Lock an element in the list, to be sure it won't be removed nor * accessed by another thread while the lock is held. * Locking behavior is inspired from MT_LIST_DELETE macro, * thus this macro can safely be used concurrently with MT_LIST_DELETE. * This returns a struct mt_list, that will be needed at unlock time. * (using MT_LIST_UNLOCK_ELT) */ #define MT_LIST_LOCK_ELT(_el) \ ({ \ struct mt_list ret; \ struct mt_list *el = (_el); \ for (;;__ha_cpu_relax()) { \ struct mt_list *n, *n2; \ struct mt_list *p, *p2 = NULL; \ n = _HA_ATOMIC_XCHG(&(el)->next, MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) \ continue; \ p = _HA_ATOMIC_XCHG(&(el)->prev, MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) { \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ if (p != (el)) { \ p2 = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY);\ if (p2 == MT_LIST_BUSY) { \ (el)->prev = p; \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ } \ if (n != (el)) { \ n2 = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY);\ if (n2 == MT_LIST_BUSY) { \ if (p2 != NULL) \ p->next = p2; \ (el)->prev = p; \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ } \ ret.next = n; \ ret.prev = p; \ break; \ } \ ret; \ }) /* Unlock an element previously locked by MT_LIST_LOCK_ELT. "np" is the * struct mt_list returned by MT_LIST_LOCK_ELT(). */ #define MT_LIST_UNLOCK_ELT(_el, np) \ do { \ struct mt_list *n = (np).next, *p = (np).prev; \ struct mt_list *el = (_el); \ (el)->next = n; \ (el)->prev = p; \ if (n != (el)) \ n->prev = (el); \ if (p != (el)) \ p->next = (el); \ } while (0) /* Internal macroes for the foreach macroes */ #define _MT_LIST_UNLOCK_NEXT(el, np) \ do { \ struct mt_list *n = (np); \ (el)->next = n; \ if (n != (el)) \ n->prev = (el); \ } while (0) /* Internal macroes for the foreach macroes */ #define _MT_LIST_UNLOCK_PREV(el, np) \ do { \ struct mt_list *p = (np); \ (el)->prev = p; \ if (p != (el)) \ p->next = (el); \ } while (0) #define _MT_LIST_LOCK_NEXT(el) \ ({ \ struct mt_list *n = NULL; \ for (;;__ha_cpu_relax()) { \ struct mt_list *n2; \ n = _HA_ATOMIC_XCHG(&((el)->next), MT_LIST_BUSY); \ if (n == MT_LIST_BUSY) \ continue; \ if (n != (el)) { \ n2 = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY);\ if (n2 == MT_LIST_BUSY) { \ (el)->next = n; \ __ha_barrier_store(); \ continue; \ } \ } \ break; \ } \ n; \ }) #define _MT_LIST_LOCK_PREV(el) \ ({ \ struct mt_list *p = NULL; \ for (;;__ha_cpu_relax()) { \ struct mt_list *p2; \ p = _HA_ATOMIC_XCHG(&((el)->prev), MT_LIST_BUSY); \ if (p == MT_LIST_BUSY) \ continue; \ if (p != (el)) { \ p2 = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY);\ if (p2 == MT_LIST_BUSY) { \ (el)->prev = p; \ __ha_barrier_store(); \ continue; \ } \ } \ break; \ } \ p; \ }) #define _MT_LIST_RELINK_DELETED(elt2) \ do { \ struct mt_list *n = elt2.next, *p = elt2.prev; \ ALREADY_CHECKED(p); \ n->prev = p; \ p->next = n; \ } while (0); /* Equivalent of MT_LIST_DELETE(), to be used when parsing the list with mt_list_entry_for_each_safe(). * It should be the element currently parsed (tmpelt1) */ #define MT_LIST_DELETE_SAFE(_el) \ do { \ struct mt_list *el = (_el); \ (el)->prev = (el); \ (el)->next = (el); \ (_el) = NULL; \ } while (0) /* Safe as MT_LIST_DELETE_SAFE, but it won't reinit the element */ #define MT_LIST_DELETE_SAFE_NOINIT(_el) \ do { \ (_el) = NULL; \ } while (0) /* Iterates through a list of items of type "typeof(*item)" which are * linked via a "struct mt_list" member named . A pointer to the head * of the list is passed in . * * is a temporary struct mt_list *, and is a temporary * struct mt_list, used internally, both are needed for MT_LIST_DELETE_SAFE. * * This macro is implemented using a nested loop. The inner loop will run for * each element in the list, and the upper loop will run only once to do some * cleanup when the end of the list is reached or user breaks from inner loop. * It's safe to break from this macro as the cleanup will be performed anyway, * but it is strictly forbidden to goto from the loop because skipping the * cleanup will lead to undefined behavior. * * In order to remove the current element, please use MT_LIST_DELETE_SAFE. * * Example: * mt_list_for_each_entry_safe(item, list_head, list_member, elt1, elt2) { * ... * } */ #define mt_list_for_each_entry_safe(item, list_head, member, tmpelt, tmpelt2) \ for ((tmpelt) = NULL; (tmpelt) != MT_LIST_BUSY; ({ \ /* post loop cleanup: \ * gets executed only once to perform cleanup \ * after child loop has finished \ */ \ if (tmpelt) { \ /* last elem still exists, unlocking it */ \ if (tmpelt2.prev) \ MT_LIST_UNLOCK_ELT(tmpelt, tmpelt2); \ else { \ /* special case: child loop did not run \ * so tmpelt2.prev == NULL \ * (empty list) \ */ \ _MT_LIST_UNLOCK_NEXT(tmpelt, tmpelt2.next); \ } \ } else { \ /* last elem was deleted by user, relink required: \ * prev->next = next \ * next->prev = prev \ */ \ _MT_LIST_RELINK_DELETED(tmpelt2); \ } \ /* break parent loop \ * (this loop runs exactly one time) \ */ \ (tmpelt) = MT_LIST_BUSY; \ })) \ for ((tmpelt) = (list_head), (tmpelt2).prev = NULL, (tmpelt2).next = _MT_LIST_LOCK_NEXT(tmpelt); ({ \ /* this gets executed before each user body loop */ \ (item) = MT_LIST_ELEM((tmpelt2.next), typeof(item), member); \ if (&item->member != (list_head)) { \ /* did not reach end of list \ * (back to list_head == end of list reached) \ */ \ if (tmpelt2.prev != &item->member) \ tmpelt2.next = _MT_LIST_LOCK_NEXT(&item->member); \ else { \ /* FIXME: is this even supposed to happen?? \ * I'm not understanding how \ * tmpelt2.prev could be equal to &item->member. \ * running 'test_list' multiple times with 8 \ * concurrent threads: this never gets reached \ */ \ tmpelt2.next = tmpelt; \ } \ if (tmpelt != NULL) { \ /* if tmpelt was not deleted by user */ \ if (tmpelt2.prev) { \ /* not executed on first run \ * (tmpelt2.prev == NULL on first run) \ */ \ _MT_LIST_UNLOCK_PREV(tmpelt, tmpelt2.prev); \ /* unlock_prev will implicitly relink: \ * elt->prev = prev \ * prev->next = elt \ */ \ } \ tmpelt2.prev = tmpelt; \ } \ (tmpelt) = &item->member; \ } \ /* else: end of list reached (loop stop cond) */ \ }), \ &item->member != (list_head);) static __inline struct list *mt_list_to_list(struct mt_list *list) { union { struct mt_list *mt_list; struct list *list; } mylist; mylist.mt_list = list; return mylist.list; } static __inline struct mt_list *list_to_mt_list(struct list *list) { union { struct mt_list *mt_list; struct list *list; } mylist; mylist.list = list; return mylist.mt_list; } #endif /* _HAPROXY_LIST_H */