1 /* 2 * include/common/mini-clist.h 3 * Circular list manipulation macros and structures. 4 * 5 * 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 20 */ 21 22 #ifndef _COMMON_MINI_CLIST_H 23 #define _COMMON_MINI_CLIST_H 24 25 #include <common/config.h> 26 27 /* 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 */ 32 struct list { 33 struct list *n; /* next */ 34 struct list *p; /* prev */ 35 }; 36 37 /* 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 */ 46 struct bref { 47 struct list users; 48 struct list *ref; /* pointer to the target's list entry */ 49 }; 50 51 /* a word list is a generic list with a pointer to a string in each element. */ 52 struct wordlist { 53 struct list list; 54 char *s; 55 }; 56 57 /* this is the same as above with an additional pointer to a condition. */ 58 struct cond_wordlist { 59 struct list list; 60 void *cond; 61 char *s; 62 }; 63 64 /* 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 71 /* 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 77 #define LIST_HEAD(a) ((void *)(&(a))) 78 79 #define LIST_INIT(l) ((l)->n = (l)->p = (l)) 80 81 #define LIST_HEAD_INIT(l) { &l, &l } 82 83 /* 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 92 /* 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 104 /* 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)(((const char *)(lh)) - ((size_t)&((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 122 /* returns a pointer of type <pt> to a structure preceding the element 123 * which contains list head <lh>, which is known as element <el> in 124 * struct pt. 125 */ 126 #undef LIST_PREV 127 #define LIST_PREV(lh, pt, el) (LIST_ELEM((lh)->p, pt, el)) 128 129 /* 130 * 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 /* 143 * 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 /* 153 * 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 167 /* 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 178 #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; \ 192 n = HA_ATOMIC_XCHG(&(lh)->n, LLIST_BUSY); \ 193 if (n == LLIST_BUSY) \ 194 continue; \ 195 __ha_barrier_store(); \ 196 p = HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \ 197 if (p == LLIST_BUSY) { \ 198 (lh)->n = n; \ 199 __ha_barrier_store(); \ 200 continue; \ 201 } \ 202 (el)->n = n; \ 203 (el)->p = p; \ 204 __ha_barrier_store(); \ 205 n->p = (el); \ 206 __ha_barrier_store(); \ 207 p->n = (el); \ 208 __ha_barrier_store(); \ 209 break; \ 210 } \ 211 } while (0) 212 213 #define LIST_ADDQ_LOCKED(lh, el) \ 214 do { \ 215 while (1) { \ 216 struct list *n; \ 217 struct list *p; \ 218 p = HA_ATOMIC_XCHG(&(lh)->p, LLIST_BUSY); \ 219 if (p == LLIST_BUSY) \ 220 continue; \ 221 __ha_barrier_store(); \ 222 n = HA_ATOMIC_XCHG(&p->n, LLIST_BUSY); \ 223 if (n == LLIST_BUSY) { \ 224 (lh)->p = p; \ 225 __ha_barrier_store(); \ 226 continue; \ 227 } \ 228 (el)->n = n; \ 229 (el)->p = p; \ 230 __ha_barrier_store(); \ 231 p->n = (el); \ 232 __ha_barrier_store(); \ 233 n->p = (el); \ 234 __ha_barrier_store(); \ 235 break; \ 236 } \ 237 } while (0) 238 239 #define LIST_DEL_LOCKED(el) \ 240 do { \ 241 while (1) { \ 242 struct list *n, *n2; \ 243 struct list *p, *p2 = NULL; \ 244 n = HA_ATOMIC_XCHG(&(el)->n, LLIST_BUSY); \ 245 if (n == LLIST_BUSY) \ 246 continue; \ 247 p = HA_ATOMIC_XCHG(&(el)->p, LLIST_BUSY); \ 248 if (p == LLIST_BUSY) { \ 249 (el)->n = n; \ 250 __ha_barrier_store(); \ 251 continue; \ 252 } \ 253 if (p != (el)) { \ 254 p2 = HA_ATOMIC_XCHG(&p->n, LLIST_BUSY); \ 255 if (p2 == LLIST_BUSY) { \ 256 (el)->p = p; \ 257 (el)->n = n; \ 258 __ha_barrier_store(); \ 259 continue; \ 260 } \ 261 } \ 262 if (n != (el)) { \ 263 n2 = HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \ 264 if (n2 == LLIST_BUSY) { \ 265 if (p2 != NULL) \ 266 p->n = p2; \ 267 (el)->p = p; \ 268 (el)->n = n; \ 269 __ha_barrier_store(); \ 270 continue; \ 271 } \ 272 } \ 273 n->p = p; \ 274 p->n = n; \ 275 __ha_barrier_store(); \ 276 (el)->p = (el); \ 277 (el)->n = (el); \ 278 __ha_barrier_store(); \ 279 break; \ 280 } \ 281 } while (0) 282 283 284 /* Remove the first element from the list, and return it */ 285 #define LIST_POP_LOCKED(lh, pt, el) \ 286 ({ \ 287 void *_ret; \ 288 while (1) { \ 289 struct list *n, *n2; \ 290 struct list *p, *p2; \ 291 n = HA_ATOMIC_XCHG(&(lh)->n, LLIST_BUSY); \ 292 if (n == LLIST_BUSY) \ 293 continue; \ 294 if (n == (lh)) { \ 295 (lh)->n = lh; \ 296 __ha_barrier_store(); \ 297 _ret = NULL; \ 298 break; \ 299 } \ 300 p = HA_ATOMIC_XCHG(&n->p, LLIST_BUSY); \ 301 if (p == LLIST_BUSY) { \ 302 (lh)->n = n; \ 303 __ha_barrier_store(); \ 304 continue; \ 305 } \ 306 n2 = HA_ATOMIC_XCHG(&n->n, LLIST_BUSY); \ 307 if (n2 == LLIST_BUSY) { \ 308 n->p = p; \ 309 __ha_barrier_store(); \ 310 (lh)->n = n; \ 311 __ha_barrier_store(); \ 312 continue; \ 313 } \ 314 p2 = HA_ATOMIC_XCHG(&n2->p, LLIST_BUSY); \ 315 if (p2 == LLIST_BUSY) { \ 316 n->n = n2; \ 317 n->p = p; \ 318 __ha_barrier_store(); \ 319 (lh)->n = n; \ 320 __ha_barrier_store(); \ 321 continue; \ 322 } \ 323 (lh)->n = n2; \ 324 (n2)->p = (lh); \ 325 __ha_barrier_store(); \ 326 (n)->p = (n); \ 327 (n)->n = (n); \ 328 __ha_barrier_store(); \ 329 _ret = LIST_ELEM(n, pt, el); \ 330 break; \ 331 } \ 332 (_ret); \ 333 }) 334 335 #endif /* _COMMON_MINI_CLIST_H */ 336