blob: 648cbd5dca1a257736343e5e57899eacf5b79cd5 [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
Willy Tarreaubc04ce72008-12-07 20:00:15 +010037/* a back-ref is a pointer to a target list entry. It is used to detect when an
38 * element being deleted is currently being tracked by another user. The best
39 * example is a user dumping the session table. The table does not fit in the
40 * output buffer so we have to set a mark on a session and go on later. But if
41 * that marked session gets deleted, we don't want the user's pointer to go in
42 * the wild. So we can simply link this user's request to the list of this
43 * session's users, and put a pointer to the list element in ref, that will be
44 * used as the mark for next iteration.
45 */
46struct bref {
47 struct list users;
48 struct list *ref; /* pointer to the target's list entry */
49};
50
Willy Tarreaudeb9ed82010-01-03 21:03:22 +010051/* a word list is a generic list with a pointer to a string in each element. */
52struct wordlist {
53 struct list list;
54 char *s;
55};
56
Willy Tarreauf4f04122010-01-28 18:10:50 +010057/* this is the same as above with an additional pointer to a condition. */
58struct cond_wordlist {
59 struct list list;
60 void *cond;
61 char *s;
62};
63
Willy Tarreaubd578bb2007-10-28 11:41:06 +010064/* First undefine some macros which happen to also be defined on OpenBSD,
65 * in sys/queue.h, used by sys/event.h
66 */
67#undef LIST_HEAD
68#undef LIST_INIT
69#undef LIST_NEXT
70
Willy Tarreaudc13c112013-06-21 23:16:39 +020071/* ILH = Initialized List Head : used to prevent gcc from moving an empty
72 * list to BSS. Some older version tend to trim all the array and cause
73 * corruption.
74 */
75#define ILH { .n = (struct list *)1, .p = (struct list *)2 }
76
Willy Tarreaubaaee002006-06-26 02:48:02 +020077#define LIST_HEAD(a) ((void *)(&(a)))
78
willy tarreau80862a32006-04-12 19:15:57 +020079#define LIST_INIT(l) ((l)->n = (l)->p = (l))
80
Willy Tarreau2b1dccd2007-05-07 00:18:32 +020081#define LIST_HEAD_INIT(l) { &l, &l }
82
willy tarreau80862a32006-04-12 19:15:57 +020083/* adds an element at the beginning of a list ; returns the element */
84#define LIST_ADD(lh, el) ({ (el)->n = (lh)->n; (el)->n->p = (lh)->n = (el); (el)->p = (lh); (el); })
85
86/* adds an element at the end of a list ; returns the element */
87#define LIST_ADDQ(lh, el) ({ (el)->p = (lh)->p; (el)->p->n = (lh)->p = (el); (el)->n = (lh); (el); })
88
89/* removes an element from a list and returns it */
90#define LIST_DEL(el) ({ typeof(el) __ret = (el); (el)->n->p = (el)->p; (el)->p->n = (el)->n; (__ret); })
91
Willy Tarreauc5bd3112019-03-06 19:32:11 +010092/* removes an element from a list, initializes it and returns it.
93 * This is faster than LIST_DEL+LIST_INIT as we avoid reloading the pointers.
94 */
95#define LIST_DEL_INIT(el) ({ \
96 typeof(el) __ret = (el); \
97 typeof(__ret->n) __n = __ret->n; \
98 typeof(__ret->p) __p = __ret->p; \
99 __n->p = __p; __p->n = __n; \
100 __ret->n = __ret->p = __ret; \
101 __ret; \
102})
103
willy tarreau80862a32006-04-12 19:15:57 +0200104/* returns a pointer of type <pt> to a structure containing a list head called
105 * <el> at address <lh>. Note that <lh> can be the result of a function or macro
106 * since it's used only once.
107 * Example: LIST_ELEM(cur_node->args.next, struct node *, args)
108 */
109#define LIST_ELEM(lh, pt, el) ((pt)(((void *)(lh)) - ((void *)&((pt)NULL)->el)))
110
111/* checks if the list head <lh> is empty or not */
112#define LIST_ISEMPTY(lh) ((lh)->n == (lh))
113
114/* returns a pointer of type <pt> to a structure following the element
115 * which contains list head <lh>, which is known as element <el> in
116 * struct pt.
117 * Example: LIST_NEXT(args, struct node *, list)
118 */
119#define LIST_NEXT(lh, pt, el) (LIST_ELEM((lh)->n, pt, el))
120
121
Joseph Herlant41abef72018-11-25 10:57:13 -0800122/* returns a pointer of type <pt> to a structure preceding the element
willy tarreau80862a32006-04-12 19:15:57 +0200123 * which contains list head <lh>, which is known as element <el> in
124 * struct pt.
125 */
Thierry FOURNIER1db96672015-11-03 19:17:37 +0100126#undef LIST_PREV
willy tarreau80862a32006-04-12 19:15:57 +0200127#define LIST_PREV(lh, pt, el) (LIST_ELEM((lh)->p, pt, el))
128
129/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200130 * Simpler FOREACH_ITEM macro inspired from Linux sources.
131 * Iterates <item> through a list of items of type "typeof(*item)" which are
132 * linked via a "struct list" member named <member>. A pointer to the head of
133 * the list is passed in <list_head>. No temporary variable is needed. Note
134 * that <item> must not be modified during the loop.
135 * Example: list_for_each_entry(cur_acl, known_acl, list) { ... };
136 */
137#define list_for_each_entry(item, list_head, member) \
138 for (item = LIST_ELEM((list_head)->n, typeof(item), member); \
139 &item->member != (list_head); \
140 item = LIST_ELEM(item->member.n, typeof(item), member))
141
142/*
William Lallemand83215a42017-09-24 11:26:02 +0200143 * Same as list_for_each_entry but starting from current point
144 * Iterates <item> through the list starting from <item>
145 * It's basically the same macro but without initializing item to the head of
146 * the list.
147 */
148#define list_for_each_entry_from(item, list_head, member) \
149 for ( ; &item->member != (list_head); \
150 item = LIST_ELEM(item->member.n, typeof(item), member))
151
152/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200153 * Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources.
154 * Iterates <item> through a list of items of type "typeof(*item)" which are
155 * linked via a "struct list" member named <member>. A pointer to the head of
156 * the list is passed in <list_head>. A temporary variable <back> of same type
157 * as <item> is needed so that <item> may safely be deleted if needed.
158 * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list) { ... };
159 */
160#define list_for_each_entry_safe(item, back, list_head, member) \
161 for (item = LIST_ELEM((list_head)->n, typeof(item), member), \
162 back = LIST_ELEM(item->member.n, typeof(item), member); \
163 &item->member != (list_head); \
164 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
165
166
William Lallemand83215a42017-09-24 11:26:02 +0200167/*
168 * Same as list_for_each_entry_safe but starting from current point
169 * Iterates <item> through the list starting from <item>
170 * It's basically the same macro but without initializing item to the head of
171 * the list.
172 */
173#define list_for_each_entry_safe_from(item, back, list_head, member) \
174 for (back = LIST_ELEM(item->member.n, typeof(item), member); \
175 &item->member != (list_head); \
176 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
177
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100178#include <common/hathreads.h>
179#define LLIST_BUSY ((struct list *)1)
180
181/*
182 * Locked version of list manipulation macros.
183 * It is OK to use those concurrently from multiple threads, as long as the
184 * list is only used with the locked variants. The only "unlocked" macro you
185 * can use with a locked list is LIST_INIT.
186 */
187#define LIST_ADD_LOCKED(lh, el) \
188 do { \
189 while (1) { \
190 struct list *n; \
191 struct list *p; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100192 n = _HA_ATOMIC_XCHG(&(lh)->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100193 if (n == LLIST_BUSY) \
194 continue; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100195 p = _HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100196 if (p == LLIST_BUSY) { \
197 (lh)->n = n; \
198 __ha_barrier_store(); \
199 continue; \
200 } \
201 (el)->n = n; \
202 (el)->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100203 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100204 n->p = (el); \
205 __ha_barrier_store(); \
206 p->n = (el); \
207 __ha_barrier_store(); \
208 break; \
209 } \
210 } while (0)
211
212#define LIST_ADDQ_LOCKED(lh, el) \
213 do { \
214 while (1) { \
215 struct list *n; \
216 struct list *p; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100217 p = _HA_ATOMIC_XCHG(&(lh)->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100218 if (p == LLIST_BUSY) \
219 continue; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100220 n = _HA_ATOMIC_XCHG(&p->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100221 if (n == LLIST_BUSY) { \
Willy Tarreaubd20ad52019-02-28 11:09:56 +0100222 (lh)->p = p; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100223 __ha_barrier_store(); \
224 continue; \
225 } \
226 (el)->n = n; \
227 (el)->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100228 __ha_barrier_store(); \
Willy Tarreau967de202019-03-04 11:19:49 +0100229 p->n = (el); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100230 __ha_barrier_store(); \
Willy Tarreau967de202019-03-04 11:19:49 +0100231 n->p = (el); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100232 __ha_barrier_store(); \
233 break; \
234 } \
235 } while (0)
236
237#define LIST_DEL_LOCKED(el) \
238 do { \
239 while (1) { \
240 struct list *n, *n2; \
Olivier Houcharddb644892019-02-26 18:46:07 +0100241 struct list *p, *p2 = NULL; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100242 n = _HA_ATOMIC_XCHG(&(el)->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100243 if (n == LLIST_BUSY) \
244 continue; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100245 p = _HA_ATOMIC_XCHG(&(el)->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100246 if (p == LLIST_BUSY) { \
247 (el)->n = n; \
248 __ha_barrier_store(); \
249 continue; \
250 } \
251 if (p != (el)) { \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100252 p2 = _HA_ATOMIC_XCHG(&p->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100253 if (p2 == LLIST_BUSY) { \
254 (el)->p = p; \
255 (el)->n = n; \
256 __ha_barrier_store(); \
257 continue; \
258 } \
259 } \
260 if (n != (el)) { \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100261 n2 = _HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100262 if (n2 == LLIST_BUSY) { \
Olivier Houcharddb644892019-02-26 18:46:07 +0100263 if (p2 != NULL) \
Willy Tarreaub0cef352019-03-13 14:03:28 +0100264 p->n = p2; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100265 (el)->p = p; \
266 (el)->n = n; \
267 __ha_barrier_store(); \
268 continue; \
269 } \
270 } \
271 n->p = p; \
272 p->n = n; \
273 __ha_barrier_store(); \
Willy Tarreau4c747e82019-02-28 15:05:53 +0100274 (el)->p = (el); \
275 (el)->n = (el); \
276 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100277 break; \
278 } \
279 } while (0)
280
281
282/* Remove the first element from the list, and return it */
283#define LIST_POP_LOCKED(lh, pt, el) \
284 ({ \
285 void *_ret; \
286 while (1) { \
287 struct list *n, *n2; \
288 struct list *p, *p2; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100289 n = _HA_ATOMIC_XCHG(&(lh)->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100290 if (n == LLIST_BUSY) \
291 continue; \
292 if (n == (lh)) { \
293 (lh)->n = lh; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100294 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100295 _ret = NULL; \
296 break; \
297 } \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100298 p = _HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100299 if (p == LLIST_BUSY) { \
300 (lh)->n = n; \
301 __ha_barrier_store(); \
302 continue; \
303 } \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100304 n2 = _HA_ATOMIC_XCHG(&n->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100305 if (n2 == LLIST_BUSY) { \
306 n->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100307 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100308 (lh)->n = n; \
309 __ha_barrier_store(); \
310 continue; \
311 } \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100312 p2 = _HA_ATOMIC_XCHG(&n2->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100313 if (p2 == LLIST_BUSY) { \
314 n->n = n2; \
315 n->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100316 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100317 (lh)->n = n; \
318 __ha_barrier_store(); \
319 continue; \
320 } \
321 (lh)->n = n2; \
322 (n2)->p = (lh); \
323 __ha_barrier_store(); \
Willy Tarreau4c747e82019-02-28 15:05:53 +0100324 (n)->p = (n); \
325 (n)->n = (n); \
326 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100327 _ret = LIST_ELEM(n, pt, el); \
328 break; \
329 } \
330 (_ret); \
331 })
William Lallemand83215a42017-09-24 11:26:02 +0200332
Willy Tarreau2dd0d472006-06-29 17:53:05 +0200333#endif /* _COMMON_MINI_CLIST_H */