blob: 5d3954cd41a1ac0e40f680117648b16bd0ade1aa [file] [log] [blame]
willy tarreau80862a32006-04-12 19:15:57 +02001/*
Willy Tarreau3dd717c2014-12-23 13:58:43 +01002 * include/common/mini-clist.h
3 * Circular list manipulation macros and structures.
willy tarreau80862a32006-04-12 19:15:57 +02004 *
Willy Tarreau3dd717c2014-12-23 13:58:43 +01005 * Copyright (C) 2002-2014 Willy Tarreau - w@1wt.eu
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation, version 2.1
10 * exclusively.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
willy tarreau80862a32006-04-12 19:15:57 +020020 */
21
Willy Tarreau2dd0d472006-06-29 17:53:05 +020022#ifndef _COMMON_MINI_CLIST_H
23#define _COMMON_MINI_CLIST_H
willy tarreau80862a32006-04-12 19:15:57 +020024
Willy Tarreaue3ba5f02006-06-29 18:54:54 +020025#include <common/config.h>
26
willy tarreau80862a32006-04-12 19:15:57 +020027/* these are circular or bidirectionnal lists only. Each list pointer points to
28 * another list pointer in a structure, and not the structure itself. The
29 * pointer to the next element MUST be the first one so that the list is easily
30 * cast as a single linked list or pointer.
31 */
32struct list {
33 struct list *n; /* next */
34 struct list *p; /* prev */
35};
36
Olivier Houchard859dc802019-08-08 15:47:21 +020037/* This is similar to struct list, but we want to be sure the compiler will
38 * yell at you if you use macroes for one when you're using the other. You have
39 * to expicitely cast if that's really what you want to do.
40 */
41struct mt_list {
42 struct mt_list *next;
43 struct mt_list *prev;
44};
45
46
Willy Tarreaubc04ce72008-12-07 20:00:15 +010047/* a back-ref is a pointer to a target list entry. It is used to detect when an
48 * element being deleted is currently being tracked by another user. The best
49 * example is a user dumping the session table. The table does not fit in the
50 * output buffer so we have to set a mark on a session and go on later. But if
51 * that marked session gets deleted, we don't want the user's pointer to go in
52 * the wild. So we can simply link this user's request to the list of this
53 * session's users, and put a pointer to the list element in ref, that will be
54 * used as the mark for next iteration.
55 */
56struct bref {
57 struct list users;
58 struct list *ref; /* pointer to the target's list entry */
59};
60
Willy Tarreaudeb9ed82010-01-03 21:03:22 +010061/* a word list is a generic list with a pointer to a string in each element. */
62struct wordlist {
63 struct list list;
64 char *s;
65};
66
Willy Tarreauf4f04122010-01-28 18:10:50 +010067/* this is the same as above with an additional pointer to a condition. */
68struct cond_wordlist {
69 struct list list;
70 void *cond;
71 char *s;
72};
73
Willy Tarreaubd578bb2007-10-28 11:41:06 +010074/* First undefine some macros which happen to also be defined on OpenBSD,
75 * in sys/queue.h, used by sys/event.h
76 */
77#undef LIST_HEAD
78#undef LIST_INIT
79#undef LIST_NEXT
80
Willy Tarreaudc13c112013-06-21 23:16:39 +020081/* ILH = Initialized List Head : used to prevent gcc from moving an empty
82 * list to BSS. Some older version tend to trim all the array and cause
83 * corruption.
84 */
85#define ILH { .n = (struct list *)1, .p = (struct list *)2 }
86
Willy Tarreaubaaee002006-06-26 02:48:02 +020087#define LIST_HEAD(a) ((void *)(&(a)))
88
willy tarreau80862a32006-04-12 19:15:57 +020089#define LIST_INIT(l) ((l)->n = (l)->p = (l))
90
Willy Tarreau2b1dccd2007-05-07 00:18:32 +020091#define LIST_HEAD_INIT(l) { &l, &l }
92
willy tarreau80862a32006-04-12 19:15:57 +020093/* adds an element at the beginning of a list ; returns the element */
94#define LIST_ADD(lh, el) ({ (el)->n = (lh)->n; (el)->n->p = (lh)->n = (el); (el)->p = (lh); (el); })
95
96/* adds an element at the end of a list ; returns the element */
97#define LIST_ADDQ(lh, el) ({ (el)->p = (lh)->p; (el)->p->n = (lh)->p = (el); (el)->n = (lh); (el); })
98
Willy Tarreau9bead8c2019-08-16 11:27:50 +020099/* adds the contents of a list <old> at the beginning of another list <new>. The old list head remains untouched. */
100#define LIST_SPLICE(new, old) do { \
101 if (!LIST_ISEMPTY(old)) { \
102 (old)->p->n = (new)->n; (old)->n->p = (new); \
103 (new)->n->p = (old)->p; (new)->n = (old)->n; \
104 } \
105 } while (0)
106
Willy Tarreauc32a0e52019-10-04 18:01:39 +0200107/* adds the contents of a list whose first element is <old> and last one is
108 * <old->prev> at the end of another list <new>. The old list DOES NOT have
109 * any head here.
110 */
111#define LIST_SPLICE_END_DETACHED(new, old) do { \
112 typeof(new) __t; \
113 (new)->p->n = (old); \
114 (old)->p->n = (new); \
115 __t = (old)->p; \
116 (old)->p = (new)->p; \
117 (new)->p = __t; \
118 } while (0)
119
willy tarreau80862a32006-04-12 19:15:57 +0200120/* removes an element from a list and returns it */
121#define LIST_DEL(el) ({ typeof(el) __ret = (el); (el)->n->p = (el)->p; (el)->p->n = (el)->n; (__ret); })
122
Willy Tarreauc5bd3112019-03-06 19:32:11 +0100123/* removes an element from a list, initializes it and returns it.
124 * This is faster than LIST_DEL+LIST_INIT as we avoid reloading the pointers.
125 */
126#define LIST_DEL_INIT(el) ({ \
127 typeof(el) __ret = (el); \
128 typeof(__ret->n) __n = __ret->n; \
129 typeof(__ret->p) __p = __ret->p; \
130 __n->p = __p; __p->n = __n; \
131 __ret->n = __ret->p = __ret; \
132 __ret; \
133})
134
willy tarreau80862a32006-04-12 19:15:57 +0200135/* returns a pointer of type <pt> to a structure containing a list head called
136 * <el> at address <lh>. Note that <lh> can be the result of a function or macro
137 * since it's used only once.
138 * Example: LIST_ELEM(cur_node->args.next, struct node *, args)
139 */
Willy Tarreau855796b2020-03-11 11:54:04 +0100140#define LIST_ELEM(lh, pt, el) ((pt)(((const char *)(lh)) - ((size_t)&((pt)NULL)->el)))
willy tarreau80862a32006-04-12 19:15:57 +0200141
142/* checks if the list head <lh> is empty or not */
143#define LIST_ISEMPTY(lh) ((lh)->n == (lh))
144
Willy Tarreau42ccb5a2019-05-13 17:48:46 +0200145/* checks if the list element <el> was added to a list or not. This only
146 * works when detached elements are reinitialized (using LIST_DEL_INIT)
147 */
148#define LIST_ADDED(el) ((el)->n != (el))
149
willy tarreau80862a32006-04-12 19:15:57 +0200150/* returns a pointer of type <pt> to a structure following the element
151 * which contains list head <lh>, which is known as element <el> in
152 * struct pt.
153 * Example: LIST_NEXT(args, struct node *, list)
154 */
155#define LIST_NEXT(lh, pt, el) (LIST_ELEM((lh)->n, pt, el))
156
157
Joseph Herlant41abef72018-11-25 10:57:13 -0800158/* returns a pointer of type <pt> to a structure preceding the element
willy tarreau80862a32006-04-12 19:15:57 +0200159 * which contains list head <lh>, which is known as element <el> in
160 * struct pt.
161 */
Thierry FOURNIER1db96672015-11-03 19:17:37 +0100162#undef LIST_PREV
willy tarreau80862a32006-04-12 19:15:57 +0200163#define LIST_PREV(lh, pt, el) (LIST_ELEM((lh)->p, pt, el))
164
165/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200166 * Simpler FOREACH_ITEM macro inspired from Linux sources.
167 * Iterates <item> through a list of items of type "typeof(*item)" which are
168 * linked via a "struct list" member named <member>. A pointer to the head of
169 * the list is passed in <list_head>. No temporary variable is needed. Note
170 * that <item> must not be modified during the loop.
171 * Example: list_for_each_entry(cur_acl, known_acl, list) { ... };
172 */
173#define list_for_each_entry(item, list_head, member) \
174 for (item = LIST_ELEM((list_head)->n, typeof(item), member); \
175 &item->member != (list_head); \
176 item = LIST_ELEM(item->member.n, typeof(item), member))
177
178/*
William Lallemand83215a42017-09-24 11:26:02 +0200179 * Same as list_for_each_entry but starting from current point
180 * Iterates <item> through the list starting from <item>
181 * It's basically the same macro but without initializing item to the head of
182 * the list.
183 */
184#define list_for_each_entry_from(item, list_head, member) \
185 for ( ; &item->member != (list_head); \
186 item = LIST_ELEM(item->member.n, typeof(item), member))
187
188/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200189 * Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources.
190 * Iterates <item> through a list of items of type "typeof(*item)" which are
191 * linked via a "struct list" member named <member>. A pointer to the head of
192 * the list is passed in <list_head>. A temporary variable <back> of same type
193 * as <item> is needed so that <item> may safely be deleted if needed.
194 * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list) { ... };
195 */
196#define list_for_each_entry_safe(item, back, list_head, member) \
197 for (item = LIST_ELEM((list_head)->n, typeof(item), member), \
198 back = LIST_ELEM(item->member.n, typeof(item), member); \
199 &item->member != (list_head); \
200 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
201
202
William Lallemand83215a42017-09-24 11:26:02 +0200203/*
204 * Same as list_for_each_entry_safe but starting from current point
205 * Iterates <item> through the list starting from <item>
206 * It's basically the same macro but without initializing item to the head of
207 * the list.
208 */
209#define list_for_each_entry_safe_from(item, back, list_head, member) \
210 for (back = LIST_ELEM(item->member.n, typeof(item), member); \
211 &item->member != (list_head); \
212 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
213
Christopher Fauletbc1f54b2020-03-23 14:13:26 +0100214/*
215 * Iterate backwards <item> through a list of items of type "typeof(*item)"
216 * which are linked via a "struct list" member named <member>. A pointer to
217 * the head of the list is passed in <list_head>. No temporary variable is
218 * needed. Note that <item> must not be modified during the loop.
219 * Example: list_for_each_entry_rev(cur_acl, known_acl, list) { ... };
220 */
221#define list_for_each_entry_rev(item, list_head, member) \
222 for (item = LIST_ELEM((list_head)->p, typeof(item), member); \
223 &item->member != (list_head); \
224 item = LIST_ELEM(item->member.p, typeof(item), member))
225
226/*
227 * Same as list_for_each_entry_rev but starting from current point
228 * Iterate backwards <item> through the list starting from <item>
229 * It's basically the same macro but without initializing item to the head of
230 * the list.
231 */
232#define list_for_each_entry_from_rev(item, list_head, member) \
233 for ( ; &item->member != (list_head); \
234 item = LIST_ELEM(item->member.p, typeof(item), member))
235
236/*
237 * Iterate backwards <item> through a list of items of type "typeof(*item)"
238 * which are linked via a "struct list" member named <member>. A pointer to
239 * the head of the list is passed in <list_head>. A temporary variable <back>
240 * of same type as <item> is needed so that <item> may safely be deleted
241 * if needed.
242 * Example: list_for_each_entry_safe_rev(cur_acl, tmp, known_acl, list) { ... };
243 */
244#define list_for_each_entry_safe_rev(item, back, list_head, member) \
245 for (item = LIST_ELEM((list_head)->p, typeof(item), member), \
246 back = LIST_ELEM(item->member.p, typeof(item), member); \
247 &item->member != (list_head); \
248 item = back, back = LIST_ELEM(back->member.p, typeof(back), member))
249
250/*
251 * Same as list_for_each_entry_safe_rev but starting from current point
252 * Iterate backwards <item> through the list starting from <item>
253 * It's basically the same macro but without initializing item to the head of
254 * the list.
255 */
256#define list_for_each_entry_safe_from_rev(item, back, list_head, member) \
257 for (back = LIST_ELEM(item->member.p, typeof(item), member); \
258 &item->member != (list_head); \
259 item = back, back = LIST_ELEM(back->member.p, typeof(back), member))
260
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100261#include <common/hathreads.h>
Olivier Houchard859dc802019-08-08 15:47:21 +0200262#define MT_LIST_BUSY ((struct mt_list *)1)
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100263
264/*
265 * Locked version of list manipulation macros.
266 * It is OK to use those concurrently from multiple threads, as long as the
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200267 * list is only used with the locked variants.
268 */
269
270/*
271 * Add an item at the beginning of a list.
272 * Returns 1 if we added the item, 0 otherwise (because it was already in a
273 * list).
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100274 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200275#define MT_LIST_ADD(_lh, _el) \
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200276 ({ \
277 int _ret = 0; \
Olivier Houchard74715da2019-10-11 16:55:11 +0200278 struct mt_list *lh = (_lh), *el = (_el); \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100279 while (1) { \
280 struct mt_list *n; \
281 struct mt_list *p; \
282 n = _HA_ATOMIC_XCHG(&(lh)->next, MT_LIST_BUSY); \
283 if (n == MT_LIST_BUSY) \
284 continue; \
285 p = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \
286 if (p == MT_LIST_BUSY) { \
287 (lh)->next = n; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100288 __ha_barrier_store(); \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100289 continue; \
290 } \
291 if ((el)->next != (el) || (el)->prev != (el)) { \
292 (n)->prev = p; \
293 (lh)->next = n; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100294 break; \
295 } \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100296 (el)->next = n; \
297 (el)->prev = p; \
298 __ha_barrier_store(); \
299 n->prev = (el); \
300 __ha_barrier_store(); \
301 p->next = (el); \
302 __ha_barrier_store(); \
303 _ret = 1; \
304 break; \
305 } \
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200306 (_ret); \
307 })
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100308
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200309/*
310 * Add an item at the end of a list.
311 * Returns 1 if we added the item, 0 otherwise (because it was already in a
312 * list).
313 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200314#define MT_LIST_ADDQ(_lh, _el) \
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200315 ({ \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100316 int _ret = 0; \
317 struct mt_list *lh = (_lh), *el = (_el); \
318 while (1) { \
319 struct mt_list *n; \
320 struct mt_list *p; \
321 p = _HA_ATOMIC_XCHG(&(lh)->prev, MT_LIST_BUSY); \
322 if (p == MT_LIST_BUSY) \
323 continue; \
324 n = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY); \
325 if (n == MT_LIST_BUSY) { \
326 (lh)->prev = p; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100327 __ha_barrier_store(); \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100328 continue; \
329 } \
330 if ((el)->next != (el) || (el)->prev != (el)) { \
331 p->next = n; \
332 (lh)->prev = p; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100333 break; \
334 } \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100335 (el)->next = n; \
336 (el)->prev = p; \
337 __ha_barrier_store(); \
338 p->next = (el); \
339 __ha_barrier_store(); \
340 n->prev = (el); \
341 __ha_barrier_store(); \
342 _ret = 1; \
343 break; \
344 } \
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200345 (_ret); \
346 })
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100347
Willy Tarreaud7f2bbc2019-10-04 18:02:40 +0200348/*
349 * Detach a list from its head. A pointer to the first element is returned
350 * and the list is closed. If the list was empty, NULL is returned. This may
351 * exclusively be used with lists modified by MT_LIST_ADD/MT_LIST_ADDQ. This
352 * is incompatible with MT_LIST_DEL run concurrently.
Olivier Houchard2068ec42019-10-17 17:46:01 +0200353 * If there's at least one element, the next of the last element will always
354 * be NULL.
Willy Tarreaud7f2bbc2019-10-04 18:02:40 +0200355 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200356#define MT_LIST_BEHEAD(_lh) ({ \
357 struct mt_list *lh = (_lh); \
Willy Tarreaud7f2bbc2019-10-04 18:02:40 +0200358 struct mt_list *_n; \
359 struct mt_list *_p; \
360 while (1) { \
361 _p = _HA_ATOMIC_XCHG(&(lh)->prev, MT_LIST_BUSY); \
362 if (_p == MT_LIST_BUSY) \
363 continue; \
364 if (_p == (lh)) { \
365 (lh)->prev = _p; \
366 _n = NULL; \
367 break; \
368 } \
369 _n = _HA_ATOMIC_XCHG(&(lh)->next, MT_LIST_BUSY); \
370 if (_n == MT_LIST_BUSY) { \
371 (lh)->prev = _p; \
372 __ha_barrier_store(); \
373 continue; \
374 } \
375 if (_n == (lh)) { \
376 (lh)->next = _n; \
377 (lh)->prev = _p; \
378 _n = NULL; \
379 break; \
380 } \
381 (lh)->next = (lh); \
382 (lh)->prev = (lh); \
383 _n->prev = _p; \
Olivier Houchard2068ec42019-10-17 17:46:01 +0200384 _p->next = NULL; \
Willy Tarreaud7f2bbc2019-10-04 18:02:40 +0200385 __ha_barrier_store(); \
386 break; \
387 } \
388 (_n); \
389})
390
391
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200392/* Remove an item from a list.
393 * Returns 1 if we removed the item, 0 otherwise (because it was in no list).
394 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200395#define MT_LIST_DEL(_el) \
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200396 ({ \
397 int _ret = 0; \
Olivier Houchard74715da2019-10-11 16:55:11 +0200398 struct mt_list *el = (_el); \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100399 while (1) { \
400 struct mt_list *n, *n2; \
401 struct mt_list *p, *p2 = NULL; \
402 n = _HA_ATOMIC_XCHG(&(el)->next, MT_LIST_BUSY); \
403 if (n == MT_LIST_BUSY) \
404 continue; \
405 p = _HA_ATOMIC_XCHG(&(el)->prev, MT_LIST_BUSY); \
406 if (p == MT_LIST_BUSY) { \
407 (el)->next = n; \
408 __ha_barrier_store(); \
409 continue; \
410 } \
411 if (p != (el)) { \
412 p2 = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY); \
413 if (p2 == MT_LIST_BUSY) { \
414 (el)->prev = p; \
Olivier Houchard859dc802019-08-08 15:47:21 +0200415 (el)->next = n; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100416 __ha_barrier_store(); \
417 continue; \
418 } \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100419 } \
420 if (n != (el)) { \
421 n2 = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \
422 if (n2 == MT_LIST_BUSY) { \
423 if (p2 != NULL) \
424 p->next = p2; \
425 (el)->prev = p; \
426 (el)->next = n; \
427 __ha_barrier_store(); \
428 continue; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100429 } \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100430 } \
Willy Tarreau160ad9e2020-02-11 10:17:52 +0100431 n->prev = p; \
432 p->next = n; \
433 if (p != (el) && n != (el)) \
434 _ret = 1; \
435 __ha_barrier_store(); \
436 (el)->prev = (el); \
437 (el)->next = (el); \
438 __ha_barrier_store(); \
439 break; \
440 } \
Olivier Houchard0cd6a972019-09-20 17:32:47 +0200441 (_ret); \
442 })
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100443
444
445/* Remove the first element from the list, and return it */
Olivier Houchard74715da2019-10-11 16:55:11 +0200446#define MT_LIST_POP(_lh, pt, el) \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100447 ({ \
448 void *_ret; \
Olivier Houchard74715da2019-10-11 16:55:11 +0200449 struct mt_list *lh = (_lh); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100450 while (1) { \
Olivier Houchard859dc802019-08-08 15:47:21 +0200451 struct mt_list *n, *n2; \
452 struct mt_list *p, *p2; \
Olivier Houchard804ef242019-10-11 16:57:43 +0200453 n = _HA_ATOMIC_XCHG(&(lh)->next, MT_LIST_BUSY); \
454 if (n == MT_LIST_BUSY) \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100455 continue; \
456 if (n == (lh)) { \
Olivier Houchard859dc802019-08-08 15:47:21 +0200457 (lh)->next = lh; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100458 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100459 _ret = NULL; \
460 break; \
461 } \
Olivier Houchard804ef242019-10-11 16:57:43 +0200462 p = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY); \
463 if (p == MT_LIST_BUSY) { \
Olivier Houchard859dc802019-08-08 15:47:21 +0200464 (lh)->next = n; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100465 __ha_barrier_store(); \
466 continue; \
467 } \
Olivier Houchard804ef242019-10-11 16:57:43 +0200468 n2 = _HA_ATOMIC_XCHG(&n->next, MT_LIST_BUSY); \
469 if (n2 == MT_LIST_BUSY) { \
Olivier Houchard859dc802019-08-08 15:47:21 +0200470 n->prev = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100471 __ha_barrier_store(); \
Olivier Houchard859dc802019-08-08 15:47:21 +0200472 (lh)->next = n; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100473 __ha_barrier_store(); \
474 continue; \
475 } \
Olivier Houchard804ef242019-10-11 16:57:43 +0200476 p2 = _HA_ATOMIC_XCHG(&n2->prev, MT_LIST_BUSY); \
477 if (p2 == MT_LIST_BUSY) { \
Olivier Houchard859dc802019-08-08 15:47:21 +0200478 n->next = n2; \
479 n->prev = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100480 __ha_barrier_store(); \
Olivier Houchard859dc802019-08-08 15:47:21 +0200481 (lh)->next = n; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100482 __ha_barrier_store(); \
483 continue; \
484 } \
Olivier Houchard859dc802019-08-08 15:47:21 +0200485 (lh)->next = n2; \
486 (n2)->prev = (lh); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100487 __ha_barrier_store(); \
Olivier Houchard859dc802019-08-08 15:47:21 +0200488 (n)->prev = (n); \
489 (n)->next = (n); \
Willy Tarreau4c747e82019-02-28 15:05:53 +0100490 __ha_barrier_store(); \
Olivier Houchard859dc802019-08-08 15:47:21 +0200491 _ret = MT_LIST_ELEM(n, pt, el); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100492 break; \
493 } \
494 (_ret); \
495 })
William Lallemand83215a42017-09-24 11:26:02 +0200496
Olivier Houchard859dc802019-08-08 15:47:21 +0200497#define MT_LIST_HEAD(a) ((void *)(&(a)))
498
499#define MT_LIST_INIT(l) ((l)->next = (l)->prev = (l))
500
501#define MT_LIST_HEAD_INIT(l) { &l, &l }
502/* returns a pointer of type <pt> to a structure containing a list head called
503 * <el> at address <lh>. Note that <lh> can be the result of a function or macro
504 * since it's used only once.
505 * Example: MT_LIST_ELEM(cur_node->args.next, struct node *, args)
506 */
Willy Tarreau855796b2020-03-11 11:54:04 +0100507#define MT_LIST_ELEM(lh, pt, el) ((pt)(((const char *)(lh)) - ((size_t)&((pt)NULL)->el)))
Olivier Houchard859dc802019-08-08 15:47:21 +0200508
509/* checks if the list head <lh> is empty or not */
510#define MT_LIST_ISEMPTY(lh) ((lh)->next == (lh))
511
512/* returns a pointer of type <pt> to a structure following the element
513 * which contains list head <lh>, which is known as element <el> in
514 * struct pt.
515 * Example: MT_LIST_NEXT(args, struct node *, list)
516 */
517#define MT_LIST_NEXT(lh, pt, el) (MT_LIST_ELEM((lh)->next, pt, el))
518
519
520/* returns a pointer of type <pt> to a structure preceding the element
521 * which contains list head <lh>, which is known as element <el> in
522 * struct pt.
523 */
524#undef MT_LIST_PREV
525#define MT_LIST_PREV(lh, pt, el) (MT_LIST_ELEM((lh)->prev, pt, el))
526
527/* checks if the list element <el> was added to a list or not. This only
528 * works when detached elements are reinitialized (using LIST_DEL_INIT)
529 */
530#define MT_LIST_ADDED(el) ((el)->next != (el))
531
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200532/* Lock an element in the list, to be sure it won't be removed.
533 * It needs to be synchronized somehow to be sure it's not removed
534 * from the list in the meanwhile.
535 * This returns a struct mt_list, that will be needed at unlock time.
536 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200537#define MT_LIST_LOCK_ELT(_el) \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200538 ({ \
539 struct mt_list ret; \
Olivier Houchard74715da2019-10-11 16:55:11 +0200540 struct mt_liet *el = (_el); \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200541 while (1) { \
542 struct mt_list *n, *n2; \
543 struct mt_list *p, *p2 = NULL; \
Olivier Houchard804ef242019-10-11 16:57:43 +0200544 n = _HA_ATOMIC_XCHG(&(el)->next, MT_LIST_BUSY); \
545 if (n == MT_LIST_BUSY) \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200546 continue; \
Olivier Houchard804ef242019-10-11 16:57:43 +0200547 p = _HA_ATOMIC_XCHG(&(el)->prev, MT_LIST_BUSY); \
548 if (p == MT_LIST_BUSY) { \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200549 (el)->next = n; \
550 __ha_barrier_store(); \
551 continue; \
552 } \
553 if (p != (el)) { \
554 p2 = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY);\
Olivier Houchard804ef242019-10-11 16:57:43 +0200555 if (p2 == MT_LIST_BUSY) { \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200556 (el)->prev = p; \
557 (el)->next = n; \
558 __ha_barrier_store(); \
559 continue; \
560 } \
561 } \
562 if (n != (el)) { \
563 n2 = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY);\
Olivier Houchard804ef242019-10-11 16:57:43 +0200564 if (n2 == MT_LIST_BUSY) { \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200565 if (p2 != NULL) \
566 p->next = p2; \
567 (el)->prev = p; \
568 (el)->next = n; \
569 __ha_barrier_store(); \
570 continue; \
571 } \
572 } \
573 ret.next = n; \
574 ret.prev = p; \
575 break; \
576 } \
577 ret; \
578 })
579
580/* Unlock an element previously locked by MT_LIST_LOCK_ELT. "np" is the
581 * struct mt_list returned by MT_LIST_LOCK_ELT().
582 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200583#define MT_LIST_UNLOCK_ELT(_el, np) \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200584 do { \
585 struct mt_list *n = (np).next, *p = (np).prev; \
Olivier Houchard74715da2019-10-11 16:55:11 +0200586 struct mt_list *el = (_el); \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200587 (el)->next = n; \
588 (el)->prev = p; \
589 if (n != (el)) \
590 n->prev = (el); \
591 if (p != (el)) \
592 p->next = (el); \
593 } while (0)
594
595/* Internal macroes for the foreach macroes */
596#define _MT_LIST_UNLOCK_NEXT(el, np) \
597 do { \
598 struct mt_list *n = (np); \
599 (el)->next = n; \
600 if (n != (el)) \
601 n->prev = (el); \
602 } while (0)
603
604/* Internal macroes for the foreach macroes */
605#define _MT_LIST_UNLOCK_PREV(el, np) \
606 do { \
607 struct mt_list *p = (np); \
608 (el)->prev = p; \
609 if (p != (el)) \
610 p->next = (el); \
611 } while (0)
612
613#define _MT_LIST_LOCK_NEXT(el) \
614 ({ \
615 struct mt_list *n = NULL; \
616 while (1) { \
617 struct mt_list *n2; \
Olivier Houchard804ef242019-10-11 16:57:43 +0200618 n = _HA_ATOMIC_XCHG(&((el)->next), MT_LIST_BUSY); \
619 if (n == MT_LIST_BUSY) \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200620 continue; \
621 if (n != (el)) { \
622 n2 = _HA_ATOMIC_XCHG(&n->prev, MT_LIST_BUSY);\
Olivier Houchard804ef242019-10-11 16:57:43 +0200623 if (n2 == MT_LIST_BUSY) { \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200624 (el)->next = n; \
625 __ha_barrier_store(); \
626 continue; \
627 } \
628 } \
629 break; \
630 } \
631 n; \
632 })
633
634#define _MT_LIST_LOCK_PREV(el) \
635 ({ \
636 struct mt_list *p = NULL; \
637 while (1) { \
638 struct mt_list *p2; \
Olivier Houchard804ef242019-10-11 16:57:43 +0200639 p = _HA_ATOMIC_XCHG(&((el)->prev), MT_LIST_BUSY); \
640 if (p == MT_LIST_BUSY) \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200641 continue; \
642 if (p != (el)) { \
643 p2 = _HA_ATOMIC_XCHG(&p->next, MT_LIST_BUSY);\
Olivier Houchard804ef242019-10-11 16:57:43 +0200644 if (p2 == MT_LIST_BUSY) { \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200645 (el)->prev = p; \
646 __ha_barrier_store(); \
647 continue; \
648 } \
649 } \
650 break; \
651 } \
652 p; \
653 })
654
655#define _MT_LIST_RELINK_DELETED(elt2) \
656 do { \
657 struct mt_list *n = elt2.next, *p = elt2.prev; \
Olivier Houchard49983a92020-03-11 15:09:16 +0100658 ALREADY_CHECKED(p); \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200659 n->prev = p; \
660 p->next = n; \
661 } while (0);
662
663/* Equivalent of MT_LIST_DEL(), to be used when parsing the list with mt_list_entry_for_each_safe().
664 * It should be the element currently parsed (tmpelt1)
665 */
Olivier Houchard74715da2019-10-11 16:55:11 +0200666#define MT_LIST_DEL_SAFE(_el) \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200667 do { \
Olivier Houchard74715da2019-10-11 16:55:11 +0200668 struct mt_list *el = (_el); \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200669 (el)->prev = (el); \
670 (el)->next = (el); \
Olivier Houchard1d117e32020-03-10 17:41:53 +0100671 (_el) = NULL; \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200672 } while (0)
673
674/* Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources.
675 * Iterates <item> through a list of items of type "typeof(*item)" which are
676 * linked via a "struct list" member named <member>. A pointer to the head of
677 * the list is passed in <list_head>. A temporary variable <back> of same type
678 * as <item> is needed so that <item> may safely be deleted if needed.
679 * tmpelt1 is a temporary struct mt_list *, and tmpelt2 is a temporary
680 * struct mt_list, used internally, both are needed for MT_LIST_DEL_SAFE.
681 * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list, elt1, elt2)
682 * { ... };
683 * If you want to remove the current element, please use MT_LIST_DEL_SAFE.
684 */
685#define mt_list_for_each_entry_safe(item, list_head, member, tmpelt, tmpelt2) \
686 for ((tmpelt) = NULL; (tmpelt) != MT_LIST_BUSY; ({ \
687 if (tmpelt) { \
688 if (tmpelt2.prev) \
689 MT_LIST_UNLOCK_ELT(tmpelt, tmpelt2); \
690 else \
691 _MT_LIST_UNLOCK_NEXT(tmpelt, tmpelt2.next); \
692 } else \
693 _MT_LIST_RELINK_DELETED(tmpelt2); \
694 (tmpelt) = MT_LIST_BUSY; \
Olivier Houchard804ef242019-10-11 16:57:43 +0200695 })) \
Olivier Houchard74715da2019-10-11 16:55:11 +0200696 for ((tmpelt) = (list_head), (tmpelt2).prev = NULL, (tmpelt2).next = _MT_LIST_LOCK_NEXT(tmpelt); ({ \
Olivier Houchard5e9b92c2019-08-12 14:10:12 +0200697 (item) = MT_LIST_ELEM((tmpelt2.next), typeof(item), member); \
698 if (&item->member != (list_head)) { \
699 if (tmpelt2.prev != &item->member) \
700 tmpelt2.next = _MT_LIST_LOCK_NEXT(&item->member); \
701 else \
702 tmpelt2.next = tmpelt; \
703 if (tmpelt != NULL) { \
704 if (tmpelt2.prev) \
705 _MT_LIST_UNLOCK_PREV(tmpelt, tmpelt2.prev); \
706 tmpelt2.prev = tmpelt; \
707 } \
708 (tmpelt) = &item->member; \
709 } \
710 }), \
711 &item->member != (list_head);)
Olivier Houchard751e5e22020-03-11 14:57:52 +0100712
713static __inline struct list *mt_list_to_list(struct mt_list *list)
714{
715 union {
716 struct mt_list *mt_list;
717 struct list *list;
718 } mylist;
719
720 mylist.mt_list = list;
721 return mylist.list;
722}
723
724static __inline struct mt_list *list_to_mt_list(struct list *list)
725{
Olivier Houchard84fd8a72020-03-11 21:41:13 +0100726 union {
Olivier Houchard751e5e22020-03-11 14:57:52 +0100727 struct mt_list *mt_list;
728 struct list *list;
729 } mylist;
730
731 mylist.list = list;
732 return mylist.mt_list;
733
734}
735
Willy Tarreau2dd0d472006-06-29 17:53:05 +0200736#endif /* _COMMON_MINI_CLIST_H */