blob: 592bb9613666e991876e449a4a9b82b78bb7e314 [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
Willy Tarreau42ccb5a2019-05-13 17:48:46 +0200114/* checks if the list element <el> was added to a list or not. This only
115 * works when detached elements are reinitialized (using LIST_DEL_INIT)
116 */
117#define LIST_ADDED(el) ((el)->n != (el))
118
willy tarreau80862a32006-04-12 19:15:57 +0200119/* returns a pointer of type <pt> to a structure following the element
120 * which contains list head <lh>, which is known as element <el> in
121 * struct pt.
122 * Example: LIST_NEXT(args, struct node *, list)
123 */
124#define LIST_NEXT(lh, pt, el) (LIST_ELEM((lh)->n, pt, el))
125
126
Joseph Herlant41abef72018-11-25 10:57:13 -0800127/* returns a pointer of type <pt> to a structure preceding the element
willy tarreau80862a32006-04-12 19:15:57 +0200128 * which contains list head <lh>, which is known as element <el> in
129 * struct pt.
130 */
Thierry FOURNIER1db96672015-11-03 19:17:37 +0100131#undef LIST_PREV
willy tarreau80862a32006-04-12 19:15:57 +0200132#define LIST_PREV(lh, pt, el) (LIST_ELEM((lh)->p, pt, el))
133
134/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200135 * Simpler FOREACH_ITEM macro inspired from Linux sources.
136 * Iterates <item> through a list of items of type "typeof(*item)" which are
137 * linked via a "struct list" member named <member>. A pointer to the head of
138 * the list is passed in <list_head>. No temporary variable is needed. Note
139 * that <item> must not be modified during the loop.
140 * Example: list_for_each_entry(cur_acl, known_acl, list) { ... };
141 */
142#define list_for_each_entry(item, list_head, member) \
143 for (item = LIST_ELEM((list_head)->n, typeof(item), member); \
144 &item->member != (list_head); \
145 item = LIST_ELEM(item->member.n, typeof(item), member))
146
147/*
William Lallemand83215a42017-09-24 11:26:02 +0200148 * Same as list_for_each_entry but starting from current point
149 * Iterates <item> through the list starting from <item>
150 * It's basically the same macro but without initializing item to the head of
151 * the list.
152 */
153#define list_for_each_entry_from(item, list_head, member) \
154 for ( ; &item->member != (list_head); \
155 item = LIST_ELEM(item->member.n, typeof(item), member))
156
157/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200158 * Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources.
159 * Iterates <item> through a list of items of type "typeof(*item)" which are
160 * linked via a "struct list" member named <member>. A pointer to the head of
161 * the list is passed in <list_head>. A temporary variable <back> of same type
162 * as <item> is needed so that <item> may safely be deleted if needed.
163 * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list) { ... };
164 */
165#define list_for_each_entry_safe(item, back, list_head, member) \
166 for (item = LIST_ELEM((list_head)->n, typeof(item), member), \
167 back = LIST_ELEM(item->member.n, typeof(item), member); \
168 &item->member != (list_head); \
169 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
170
171
William Lallemand83215a42017-09-24 11:26:02 +0200172/*
173 * Same as list_for_each_entry_safe but starting from current point
174 * Iterates <item> through the list starting from <item>
175 * It's basically the same macro but without initializing item to the head of
176 * the list.
177 */
178#define list_for_each_entry_safe_from(item, back, list_head, member) \
179 for (back = LIST_ELEM(item->member.n, typeof(item), member); \
180 &item->member != (list_head); \
181 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
182
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100183#include <common/hathreads.h>
184#define LLIST_BUSY ((struct list *)1)
185
186/*
187 * Locked version of list manipulation macros.
188 * It is OK to use those concurrently from multiple threads, as long as the
189 * list is only used with the locked variants. The only "unlocked" macro you
190 * can use with a locked list is LIST_INIT.
191 */
192#define LIST_ADD_LOCKED(lh, el) \
193 do { \
194 while (1) { \
195 struct list *n; \
196 struct list *p; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100197 n = _HA_ATOMIC_XCHG(&(lh)->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100198 if (n == LLIST_BUSY) \
199 continue; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100200 p = _HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100201 if (p == LLIST_BUSY) { \
202 (lh)->n = n; \
203 __ha_barrier_store(); \
204 continue; \
205 } \
206 (el)->n = n; \
207 (el)->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100208 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100209 n->p = (el); \
210 __ha_barrier_store(); \
211 p->n = (el); \
212 __ha_barrier_store(); \
213 break; \
214 } \
215 } while (0)
216
217#define LIST_ADDQ_LOCKED(lh, el) \
218 do { \
219 while (1) { \
220 struct list *n; \
221 struct list *p; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100222 p = _HA_ATOMIC_XCHG(&(lh)->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100223 if (p == LLIST_BUSY) \
224 continue; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100225 n = _HA_ATOMIC_XCHG(&p->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100226 if (n == LLIST_BUSY) { \
Willy Tarreaubd20ad52019-02-28 11:09:56 +0100227 (lh)->p = p; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100228 __ha_barrier_store(); \
229 continue; \
230 } \
231 (el)->n = n; \
232 (el)->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100233 __ha_barrier_store(); \
Willy Tarreau967de202019-03-04 11:19:49 +0100234 p->n = (el); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100235 __ha_barrier_store(); \
Willy Tarreau967de202019-03-04 11:19:49 +0100236 n->p = (el); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100237 __ha_barrier_store(); \
238 break; \
239 } \
240 } while (0)
241
242#define LIST_DEL_LOCKED(el) \
243 do { \
244 while (1) { \
245 struct list *n, *n2; \
Olivier Houcharddb644892019-02-26 18:46:07 +0100246 struct list *p, *p2 = NULL; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100247 n = _HA_ATOMIC_XCHG(&(el)->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100248 if (n == LLIST_BUSY) \
249 continue; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100250 p = _HA_ATOMIC_XCHG(&(el)->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100251 if (p == LLIST_BUSY) { \
252 (el)->n = n; \
253 __ha_barrier_store(); \
254 continue; \
255 } \
256 if (p != (el)) { \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100257 p2 = _HA_ATOMIC_XCHG(&p->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100258 if (p2 == LLIST_BUSY) { \
259 (el)->p = p; \
260 (el)->n = n; \
261 __ha_barrier_store(); \
262 continue; \
263 } \
264 } \
265 if (n != (el)) { \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100266 n2 = _HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100267 if (n2 == LLIST_BUSY) { \
Olivier Houcharddb644892019-02-26 18:46:07 +0100268 if (p2 != NULL) \
Willy Tarreaub0cef352019-03-13 14:03:28 +0100269 p->n = p2; \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100270 (el)->p = p; \
271 (el)->n = n; \
272 __ha_barrier_store(); \
273 continue; \
274 } \
275 } \
276 n->p = p; \
277 p->n = n; \
278 __ha_barrier_store(); \
Willy Tarreau4c747e82019-02-28 15:05:53 +0100279 (el)->p = (el); \
280 (el)->n = (el); \
281 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100282 break; \
283 } \
284 } while (0)
285
286
287/* Remove the first element from the list, and return it */
288#define LIST_POP_LOCKED(lh, pt, el) \
289 ({ \
290 void *_ret; \
291 while (1) { \
292 struct list *n, *n2; \
293 struct list *p, *p2; \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100294 n = _HA_ATOMIC_XCHG(&(lh)->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100295 if (n == LLIST_BUSY) \
296 continue; \
297 if (n == (lh)) { \
298 (lh)->n = lh; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100299 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100300 _ret = NULL; \
301 break; \
302 } \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100303 p = _HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100304 if (p == LLIST_BUSY) { \
305 (lh)->n = n; \
306 __ha_barrier_store(); \
307 continue; \
308 } \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100309 n2 = _HA_ATOMIC_XCHG(&n->n, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100310 if (n2 == LLIST_BUSY) { \
311 n->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100312 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100313 (lh)->n = n; \
314 __ha_barrier_store(); \
315 continue; \
316 } \
Olivier Houchard9f8d8212019-03-13 18:50:33 +0100317 p2 = _HA_ATOMIC_XCHG(&n2->p, LLIST_BUSY); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100318 if (p2 == LLIST_BUSY) { \
319 n->n = n2; \
320 n->p = p; \
Willy Tarreau690d2ad2019-02-28 11:14:22 +0100321 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100322 (lh)->n = n; \
323 __ha_barrier_store(); \
324 continue; \
325 } \
326 (lh)->n = n2; \
327 (n2)->p = (lh); \
328 __ha_barrier_store(); \
Willy Tarreau4c747e82019-02-28 15:05:53 +0100329 (n)->p = (n); \
330 (n)->n = (n); \
331 __ha_barrier_store(); \
Olivier Houcharda8434ec2019-01-18 17:26:26 +0100332 _ret = LIST_ELEM(n, pt, el); \
333 break; \
334 } \
335 (_ret); \
336 })
William Lallemand83215a42017-09-24 11:26:02 +0200337
Willy Tarreau2dd0d472006-06-29 17:53:05 +0200338#endif /* _COMMON_MINI_CLIST_H */