Bug Summary

File:list.h
Warning:line 722, column 9
Casting a non-structure type to a structure type and accessing a field can lead to memory access errors or data corruption

Annotated Source Code

1/*
2 * list - double linked list routines
3 * Author: Rusty Russell <rusty@rustcorp.com.au>
4 *
5 * The list header contains routines for manipulating double linked lists.
6 * It defines two types: struct list_head used for anchoring lists, and
7 * struct list_node which is usually embedded in the structure which is placed
8 * in the list.
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining a
11 * copy of this software and associated documentation files (the
12 * "Software"), to deal in the Software without restriction, including
13 * without limitation the rights to use, copy, modify, merge, publish,
14 * distribute, sublicense, and/or sell copies of the Software, and to permit
15 * persons to whom the Software is furnished to do so, subject to the
16 * following conditions:
17 *
18 * The above copyright notice and this permission notice shall be included
19 * in all copies or substantial portions of the Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
24 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
25 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
26 * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
27 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 */
29
30#pragma once
31#include <stdbool.h>
32#include <stddef.h>
33#include <assert.h>
34
35/**
36 * check_type - issue a warning or build failure if type is not correct.
37 * @expr: the expression whose type we should check (not evaluated).
38 * @type: the exact type we expect the expression to be.
39 *
40 * This macro is usually used within other macros to try to ensure that a macro
41 * argument is of the expected type. No type promotion of the expression is
42 * done: an unsigned int is not the same as an int!
43 *
44 * check_type() always evaluates to 0.
45 *
46 * If your compiler does not support typeof, then the best we can do is fail
47 * to compile if the sizes of the types are unequal (a less complete check).
48 *
49 * Example:
50 * // They should always pass a 64-bit value to _set_some_value!
51 * #define set_some_value(expr) \
52 * _set_some_value((check_type((expr), uint64_t), (expr)))
53 */
54#define check_type(expr, type)((typeof(expr) *)0 != (type *)0) \
55 ((typeof(expr) *)0 != (type *)0)
56
57/**
58 * check_types_match - issue a warning or build failure if types are not same.
59 * @expr1: the first expression (not evaluated).
60 * @expr2: the second expression (not evaluated).
61 *
62 * This macro is usually used within other macros to try to ensure that
63 * arguments are of identical types. No type promotion of the expressions is
64 * done: an unsigned int is not the same as an int!
65 *
66 * check_types_match() always evaluates to 0.
67 *
68 * If your compiler does not support typeof, then the best we can do is fail
69 * to compile if the sizes of the types are unequal (a less complete check).
70 *
71 * Example:
72 * // Do subtraction to get to enclosing type, but make sure that
73 * // pointer is of correct type for that member.
74 * #define container_of(mbr_ptr, encl_type, mbr) \
75 * (check_types_match((mbr_ptr), &((encl_type *)0)->mbr), \
76 * ((encl_type *) \
77 * ((char *)(mbr_ptr) - offsetof(enclosing_type, mbr))))
78 */
79
80#define check_types_match(expr1, expr2)((typeof(expr1) *)0 != (typeof(expr2) *)0) \
81 ((typeof(expr1) *)0 != (typeof(expr2) *)0)
82
83/**
84 * container_of - get pointer to enclosing structure
85 * @member_ptr: pointer to the structure member
86 * @containing_type: the type this member is within
87 * @member: the name of this member within the structure.
88 *
89 * Given a pointer to a member of a structure, this macro does pointer
90 * subtraction to return the pointer to the enclosing type.
91 *
92 * Example:
93 * struct foo {
94 * int fielda, fieldb;
95 * // ...
96 * };
97 * struct info {
98 * int some_other_field;
99 * struct foo my_foo;
100 * };
101 *
102 * static struct info *foo_to_info(struct foo *foo)
103 * {
104 * return container_of(foo, struct info, my_foo);
105 * }
106 */
107#define container_of(member_ptr, containing_type, member)((containing_type *) ((char *)(member_ptr) - __builtin_offsetof
(containing_type, member)) + ((typeof(*(member_ptr)) *)0 != (
typeof(((containing_type *)0)->member) *)0))
\
108 ((containing_type *) \
109 ((char *)(member_ptr) \
110 - container_off(containing_type, member)__builtin_offsetof(containing_type, member)) \
111 + check_types_match(*(member_ptr), ((containing_type *)0)->member)((typeof(*(member_ptr)) *)0 != (typeof(((containing_type *)0)
->member) *)0)
)
112
113/**
114 * container_of_var - get pointer to enclosing structure using a variable
115 * @member_ptr: pointer to the structure member
116 * @container_var: a pointer of same type as this member's container
117 * @member: the name of this member within the structure.
118 *
119 * Given a pointer to a member of a structure, this macro does pointer
120 * subtraction to return the pointer to the enclosing type.
121 *
122 * Example:
123 * static struct info *foo_to_i(struct foo *foo)
124 * {
125 * struct info *i = container_of_var(foo, i, my_foo);
126 * return i;
127 * }
128 */
129#if HAVE_TYPEOF
130#define container_of_var(member_ptr, container_var, member)((void *)((char *)(member_ptr) - __builtin_offsetof(typeof(*container_var
), member)))
\
131 container_of(member_ptr, typeof(*container_var), member)((typeof(*container_var) *) ((char *)(member_ptr) - __builtin_offsetof
(typeof(*container_var), member)) + ((typeof(*(member_ptr)) *
)0 != (typeof(((typeof(*container_var) *)0)->member) *)0))
132#else
133#define container_of_var(member_ptr, container_var, member)((void *)((char *)(member_ptr) - __builtin_offsetof(typeof(*container_var
), member)))
\
134 ((void *)((char *)(member_ptr) - \
135 container_off_var(container_var, member)__builtin_offsetof(typeof(*container_var), member)))
136#endif
137
138/**
139 * container_off - get offset to enclosing structure
140 * @containing_type: the type this member is within
141 * @member: the name of this member within the structure.
142 *
143 * Given a pointer to a member of a structure, this macro does
144 * typechecking and figures out the offset to the enclosing type.
145 *
146 * Example:
147 * struct foo {
148 * int fielda, fieldb;
149 * // ...
150 * };
151 * struct info {
152 * int some_other_field;
153 * struct foo my_foo;
154 * };
155 *
156 * static struct info *foo_to_info(struct foo *foo)
157 * {
158 * size_t off = container_off(struct info, my_foo);
159 * return (void *)((char *)foo - off);
160 * }
161 */
162#define container_off(containing_type, member)__builtin_offsetof(containing_type, member) \
163 offsetof(containing_type, member)__builtin_offsetof(containing_type, member)
164
165/**
166 * container_off_var - get offset of a field in enclosing structure
167 * @container_var: a pointer to a container structure
168 * @member: the name of a member within the structure.
169 *
170 * Given (any) pointer to a structure and a its member name, this
171 * macro does pointer subtraction to return offset of member in a
172 * structure memory layout.
173 *
174 */
175#define container_off_var(var, member)__builtin_offsetof(typeof(*var), member) \
176 container_off(typeof(*var), member)__builtin_offsetof(typeof(*var), member)
177
178/**
179 * struct list_node - an entry in a doubly-linked list
180 * @next: next entry (self if empty)
181 * @prev: previous entry (self if empty)
182 *
183 * This is used as an entry in a linked list.
184 * Example:
185 * struct child {
186 * const char *name;
187 * // Linked list of all us children.
188 * struct list_node list;
189 * };
190 */
191struct list_node
192{
193 struct list_node *next, *prev;
194};
195
196/**
197 * struct list_head - the head of a doubly-linked list
198 * @h: the list_head (containing next and prev pointers)
199 *
200 * This is used as the head of a linked list.
201 * Example:
202 * struct parent {
203 * const char *name;
204 * struct list_head children;
205 * unsigned int num_children;
206 * };
207 */
208struct list_head
209{
210 struct list_node n;
211};
212
213/**
214 * list_check - check head of a list for consistency
215 * @h: the list_head
216 * @abortstr: the location to print on aborting, or NULL.
217 *
218 * Because list_nodes have redundant information, consistency checking between
219 * the back and forward links can be done. This is useful as a debugging check.
220 * If @abortstr is non-NULL, that will be printed in a diagnostic if the list
221 * is inconsistent, and the function will abort.
222 *
223 * Returns the list head if the list is consistent, NULL if not (it
224 * can never return NULL if @abortstr is set).
225 *
226 * See also: list_check_node()
227 *
228 * Example:
229 * static void dump_parent(struct parent *p)
230 * {
231 * struct child *c;
232 *
233 * printf("%s (%u children):\n", p->name, p->num_children);
234 * list_check(&p->children, "bad child list");
235 * list_for_each(&p->children, c, list)
236 * printf(" -> %s\n", c->name);
237 * }
238 */
239struct list_head *list_check(const struct list_head *h, const char *abortstr);
240
241/**
242 * list_check_node - check node of a list for consistency
243 * @n: the list_node
244 * @abortstr: the location to print on aborting, or NULL.
245 *
246 * Check consistency of the list node is in (it must be in one).
247 *
248 * See also: list_check()
249 *
250 * Example:
251 * static void dump_child(const struct child *c)
252 * {
253 * list_check_node(&c->list, "bad child list");
254 * printf("%s\n", c->name);
255 * }
256 */
257struct list_node *list_check_node(const struct list_node *n,
258 const char *abortstr);
259
260#ifdef _LIST_DEBUG
261#define list_debug(h)(h) list_check((h), __func__)
262#define list_debug_node(n)(n) list_check_node((n), __func__)
263#else
264#define list_debug(h)(h) (h)
265#define list_debug_node(n)(n) (n)
266#endif
267
268/**
269 * LIST_HEAD_INIT - initializer for an empty list_head
270 * @name: the name of the list.
271 *
272 * Explicit initializer for an empty list.
273 *
274 * See also:
275 * LIST_HEAD, list_head_init()
276 *
277 * Example:
278 * static struct list_head my_list = LIST_HEAD_INIT(my_list);
279 */
280#define LIST_HEAD_INIT(name){ { &name.n, &name.n } } { { &name.n, &name.n } }
281
282/**
283 * LIST_HEAD - define and initialize an empty list_head
284 * @name: the name of the list.
285 *
286 * The LIST_HEAD macro defines a list_head and initializes it to an empty
287 * list. It can be prepended by "static" to define a static list_head.
288 *
289 * See also:
290 * LIST_HEAD_INIT, list_head_init()
291 *
292 * Example:
293 * static LIST_HEAD(my_global_list);
294 */
295#define LIST_HEAD(name)struct list_head name = { { &name.n, &name.n } } \
296 struct list_head name = LIST_HEAD_INIT(name){ { &name.n, &name.n } }
297
298/**
299 * list_head_init - initialize a list_head
300 * @h: the list_head to set to the empty list
301 *
302 * Example:
303 * ...
304 * struct parent *parent = malloc(sizeof(*parent));
305 *
306 * list_head_init(&parent->children);
307 * parent->num_children = 0;
308 */
309static inline void list_head_init(struct list_head *h)
310{
311 h->n.next = h->n.prev = &h->n;
312}
313
314/**
315 * list_add - add an entry at the start of a linked list.
316 * @h: the list_head to add the node to
317 * @n: the list_node to add to the list.
318 *
319 * The list_node does not need to be initialized; it will be overwritten.
320 * Example:
321 * struct child *child = malloc(sizeof(*child));
322 *
323 * child->name = "marvin";
324 * list_add(&parent->children, &child->list);
325 * parent->num_children++;
326 */
327static inline void list_add(struct list_head *h, struct list_node *n)
328{
329 n->next = h->n.next;
330 n->prev = &h->n;
331 h->n.next->prev = n;
332 h->n.next = n;
333 (void)list_debug(h)(h);
334}
335
336/**
337 * list_add_tail - add an entry at the end of a linked list.
338 * @h: the list_head to add the node to
339 * @n: the list_node to add to the list.
340 *
341 * The list_node does not need to be initialized; it will be overwritten.
342 * Example:
343 * list_add_tail(&parent->children, &child->list);
344 * parent->num_children++;
345 */
346static inline void list_add_tail(struct list_head *h, struct list_node *n)
347{
348 n->next = &h->n;
349 n->prev = h->n.prev;
350 h->n.prev->next = n;
351 h->n.prev = n;
352 (void)list_debug(h)(h);
353}
354
355/**
356 * list_empty - is a list empty?
357 * @h: the list_head
358 *
359 * If the list is empty, returns true.
360 *
361 * Example:
362 * assert(list_empty(&parent->children) == (parent->num_children == 0));
363 */
364static inline bool_Bool list_empty(const struct list_head *h)
365{
366 (void)list_debug(h)(h);
367 return h->n.next == &h->n;
368}
369
370/**
371 * list_del - delete an entry from an (unknown) linked list.
372 * @n: the list_node to delete from the list.
373 *
374 * Note that this leaves @n in an undefined state; it can be added to
375 * another list, but not deleted again.
376 *
377 * See also:
378 * list_del_from()
379 *
380 * Example:
381 * list_del(&child->list);
382 * parent->num_children--;
383 */
384static inline void list_del(struct list_node *n)
385{
386 (void)list_debug_node(n)(n);
387 n->next->prev = n->prev;
388 n->prev->next = n->next;
389#ifdef _LIST_DEBUG
390 /* Catch use-after-del. */
391 n->next = n->prev = NULL((void*)0);
392#endif
393}
394
395/**
396 * list_del_from - delete an entry from a known linked list.
397 * @h: the list_head the node is in.
398 * @n: the list_node to delete from the list.
399 *
400 * This explicitly indicates which list a node is expected to be in,
401 * which is better documentation and can catch more bugs.
402 *
403 * See also: list_del()
404 *
405 * Example:
406 * list_del_from(&parent->children, &child->list);
407 * parent->num_children--;
408 */
409static inline void list_del_from(struct list_head *h, struct list_node *n)
410{
411#ifdef _LIST_DEBUG
412 {
413 /* Thorough check: make sure it was in list! */
414 struct list_node *i;
415 for (i = h->n.next; i != n; i = i->next)
416 assert(i != &h->n)({ if (i != &h->n) ; else __assert_fail ("i != &h->n"
, "/home/buildbot/lwan-worker/clang-analyze/build/common/list.h"
, 416, __PRETTY_FUNCTION__); })
;
417 }
418#else
419 (void)h;
420#endif /* _LIST_DEBUG */
421
422 /* Quick test that catches a surprising number of bugs. */
423 assert(!list_empty(h))({ if (!list_empty(h)) ; else __assert_fail ("!list_empty(h)"
, "/home/buildbot/lwan-worker/clang-analyze/build/common/list.h"
, 423, __PRETTY_FUNCTION__); })
;
424 list_del(n);
425}
426
427/**
428 * list_entry - convert a list_node back into the structure containing it.
429 * @n: the list_node
430 * @type: the type of the entry
431 * @member: the list_node member of the type
432 *
433 * Example:
434 * // First list entry is children.next; convert back to child.
435 * child = list_entry(parent->children.n.next, struct child, list);
436 *
437 * See Also:
438 * list_top(), list_for_each()
439 */
440#define list_entry(n, type, member)((type *) ((char *)(n) - __builtin_offsetof(type, member)) + (
(typeof(*(n)) *)0 != (typeof(((type *)0)->member) *)0))
container_of(n, type, member)((type *) ((char *)(n) - __builtin_offsetof(type, member)) + (
(typeof(*(n)) *)0 != (typeof(((type *)0)->member) *)0))
441
442/**
443 * list_top - get the first entry in a list
444 * @h: the list_head
445 * @type: the type of the entry
446 * @member: the list_node member of the type
447 *
448 * If the list is empty, returns NULL.
449 *
450 * Example:
451 * struct child *first;
452 * first = list_top(&parent->children, struct child, list);
453 * if (!first)
454 * printf("Empty list!\n");
455 */
456#define list_top(h, type, member)((type *)list_top_((h), (__builtin_offsetof(type, member) + (
(typeof(((type *)0)->member) *)0 != (struct list_node *)0)
)))
\
457 ((type *)list_top_((h), list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)->
member) *)0 != (struct list_node *)0))
))
458
459static inline const void *list_top_(const struct list_head *h, size_t off)
460{
461 if (list_empty(h))
462 return NULL((void*)0);
463 return (const char *)h->n.next - off;
464}
465
466/**
467 * list_pop - remove the first entry in a list
468 * @h: the list_head
469 * @type: the type of the entry
470 * @member: the list_node member of the type
471 *
472 * If the list is empty, returns NULL.
473 *
474 * Example:
475 * struct child *one;
476 * one = list_pop(&parent->children, struct child, list);
477 * if (!one)
478 * printf("Empty list!\n");
479 */
480#define list_pop(h, type, member)((type *)list_pop_((h), (__builtin_offsetof(type, member) + (
(typeof(((type *)0)->member) *)0 != (struct list_node *)0)
)))
\
481 ((type *)list_pop_((h), list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)->
member) *)0 != (struct list_node *)0))
))
482
483static inline const void *list_pop_(const struct list_head *h, size_t off)
484{
485 struct list_node *n;
486
487 if (list_empty(h))
488 return NULL((void*)0);
489 n = h->n.next;
490 list_del(n);
491 return (const char *)n - off;
492}
493
494/**
495 * list_tail - get the last entry in a list
496 * @h: the list_head
497 * @type: the type of the entry
498 * @member: the list_node member of the type
499 *
500 * If the list is empty, returns NULL.
501 *
502 * Example:
503 * struct child *last;
504 * last = list_tail(&parent->children, struct child, list);
505 * if (!last)
506 * printf("Empty list!\n");
507 */
508#define list_tail(h, type, member)((type *)list_tail_((h), (__builtin_offsetof(type, member) + (
(typeof(((type *)0)->member) *)0 != (struct list_node *)0)
)))
\
509 ((type *)list_tail_((h), list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)->
member) *)0 != (struct list_node *)0))
))
510
511static inline const void *list_tail_(const struct list_head *h, size_t off)
512{
513 if (list_empty(h))
514 return NULL((void*)0);
515 return (const char *)h->n.prev - off;
516}
517
518/**
519 * list_for_each - iterate through a list.
520 * @h: the list_head (warning: evaluated multiple times!)
521 * @i: the structure containing the list_node
522 * @member: the list_node member of the structure
523 *
524 * This is a convenient wrapper to iterate @i over the entire list. It's
525 * a for loop, so you can break and continue as normal.
526 *
527 * Example:
528 * list_for_each(&parent->children, child, list)
529 * printf("Name: %s\n", child->name);
530 */
531#define list_for_each(h, i, member)for (i = list_node_to_off_((h)->n.next, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))); list_node_from_off_((void *)i, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))) != &(h)->n; i = list_node_to_off_(list_node_from_off_
((void *)i, ((__builtin_offsetof(typeof(*i), member) + ((typeof
(i->member) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))))
\
532 list_for_each_off(h, i, list_off_var_(i, member))for (i = list_node_to_off_((h)->n.next, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))); list_node_from_off_((void *)i, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))) != &(h)->n; i = list_node_to_off_(list_node_from_off_
((void *)i, ((__builtin_offsetof(typeof(*i), member) + ((typeof
(i->member) *)0 != (struct list_node *)0))))->next, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))))
533
534/**
535 * list_for_each_rev - iterate through a list backwards.
536 * @h: the list_head
537 * @i: the structure containing the list_node
538 * @member: the list_node member of the structure
539 *
540 * This is a convenient wrapper to iterate @i over the entire list. It's
541 * a for loop, so you can break and continue as normal.
542 *
543 * Example:
544 * list_for_each_rev(&parent->children, child, list)
545 * printf("Name: %s\n", child->name);
546 */
547#define list_for_each_rev(h, i, member)for (i = ((void *)((char *)((h)->n.prev) - __builtin_offsetof
(typeof(*i), member))); &i->member != &(h)->n; i
= ((void *)((char *)(i->member.prev) - __builtin_offsetof
(typeof(*i), member))))
\
548 for (i = container_of_var(list_debug(h)->n.prev, i, member)((void *)((char *)((h)->n.prev) - __builtin_offsetof(typeof
(*i), member)))
; \
549 &i->member != &(h)->n; \
550 i = container_of_var(i->member.prev, i, member)((void *)((char *)(i->member.prev) - __builtin_offsetof(typeof
(*i), member)))
)
551
552/**
553 * list_for_each_safe - iterate through a list, maybe during deletion
554 * @h: the list_head
555 * @i: the structure containing the list_node
556 * @nxt: the structure containing the list_node
557 * @member: the list_node member of the structure
558 *
559 * This is a convenient wrapper to iterate @i over the entire list. It's
560 * a for loop, so you can break and continue as normal. The extra variable
561 * @nxt is used to hold the next element, so you can delete @i from the list.
562 *
563 * Example:
564 * struct child *next;
565 * list_for_each_safe(&parent->children, child, next, list) {
566 * list_del(&child->list);
567 * parent->num_children--;
568 * }
569 */
570#define list_for_each_safe(h, i, nxt, member)for (i = list_node_to_off_((h)->n.next, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))), nxt = list_node_to_off_(list_node_from_off_(i, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0))))->next, ((__builtin_offsetof(typeof(*i), member) +
((typeof(i->member) *)0 != (struct list_node *)0)))); list_node_from_off_
(i, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->
member) *)0 != (struct list_node *)0)))) != &(h)->n; i
= nxt, nxt = list_node_to_off_(list_node_from_off_(i, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0))))->next, ((__builtin_offsetof(typeof(*i), member) +
((typeof(i->member) *)0 != (struct list_node *)0)))))
\
571 list_for_each_safe_off(h, i, nxt, list_off_var_(i, member))for (i = list_node_to_off_((h)->n.next, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0)))), nxt = list_node_to_off_(list_node_from_off_(i, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0))))->next, ((__builtin_offsetof(typeof(*i), member) +
((typeof(i->member) *)0 != (struct list_node *)0)))); list_node_from_off_
(i, ((__builtin_offsetof(typeof(*i), member) + ((typeof(i->
member) *)0 != (struct list_node *)0)))) != &(h)->n; i
= nxt, nxt = list_node_to_off_(list_node_from_off_(i, ((__builtin_offsetof
(typeof(*i), member) + ((typeof(i->member) *)0 != (struct list_node
*)0))))->next, ((__builtin_offsetof(typeof(*i), member) +
((typeof(i->member) *)0 != (struct list_node *)0)))))
572
573/**
574 * list_append_list - empty one list onto the end of another.
575 * @to: the list to append into
576 * @from: the list to empty.
577 *
578 * This takes the entire contents of @from and moves it to the end of
579 * @to. After this @from will be empty.
580 *
581 * Example:
582 * struct list_head adopter;
583 *
584 * list_append_list(&adopter, &parent->children);
585 * assert(list_empty(&parent->children));
586 * parent->num_children = 0;
587 */
588static inline void list_append_list(struct list_head *to,
589 struct list_head *from)
590{
591 struct list_node *from_tail = list_debug(from)(from)->n.prev;
592 struct list_node *to_tail = list_debug(to)(to)->n.prev;
593
594 /* Sew in head and entire list. */
595 to->n.prev = from_tail;
596 from_tail->next = &to->n;
597 to_tail->next = &from->n;
598 from->n.prev = to_tail;
599
600 /* Now remove head. */
601 list_del(&from->n);
602 list_head_init(from);
603}
604
605/**
606 * list_prepend_list - empty one list into the start of another.
607 * @to: the list to prepend into
608 * @from: the list to empty.
609 *
610 * This takes the entire contents of @from and moves it to the start
611 * of @to. After this @from will be empty.
612 *
613 * Example:
614 * list_prepend_list(&adopter, &parent->children);
615 * assert(list_empty(&parent->children));
616 * parent->num_children = 0;
617 */
618static inline void list_prepend_list(struct list_head *to,
619 struct list_head *from)
620{
621 struct list_node *from_tail = list_debug(from)(from)->n.prev;
622 struct list_node *to_head = list_debug(to)(to)->n.next;
623
624 /* Sew in head and entire list. */
625 to->n.next = &from->n;
626 from->n.prev = &to->n;
627 to_head->prev = from_tail;
628 from_tail->next = to_head;
629
630 /* Now remove head. */
631 list_del(&from->n);
632 list_head_init(from);
633}
634
635/**
636 * list_for_each_off - iterate through a list of memory regions.
637 * @h: the list_head
638 * @i: the pointer to a memory region wich contains list node data.
639 * @off: offset(relative to @i) at which list node data resides.
640 *
641 * This is a low-level wrapper to iterate @i over the entire list, used to
642 * implement all oher, more high-level, for-each constructs. It's a for loop,
643 * so you can break and continue as normal.
644 *
645 * WARNING! Being the low-level macro that it is, this wrapper doesn't know
646 * nor care about the type of @i. The only assumtion made is that @i points
647 * to a chunk of memory that at some @offset, relative to @i, contains a
648 * properly filled `struct node_list' which in turn contains pointers to
649 * memory chunks and it's turtles all the way down. Whith all that in mind
650 * remember that given the wrong pointer/offset couple this macro will
651 * happilly churn all you memory untill SEGFAULT stops it, in other words
652 * caveat emptor.
653 *
654 * It is worth mentioning that one of legitimate use-cases for that wrapper
655 * is operation on opaque types with known offset for `struct list_node'
656 * member(preferably 0), because it allows you not to disclose the type of
657 * @i.
658 *
659 * Example:
660 * list_for_each_off(&parent->children, child,
661 * offsetof(struct child, list))
662 * printf("Name: %s\n", child->name);
663 */
664#define list_for_each_off(h, i, off)for (i = list_node_to_off_((h)->n.next, (off)); list_node_from_off_
((void *)i, (off)) != &(h)->n; i = list_node_to_off_(list_node_from_off_
((void *)i, (off))->next, (off)))
\
665 for (i = list_node_to_off_(list_debug(h)(h)->n.next, (off)); \
666 list_node_from_off_((void *)i, (off)) != &(h)->n; \
667 i = list_node_to_off_(list_node_from_off_((void *)i, (off))->next, \
668 (off)))
669
670/**
671 * list_for_each_safe_off - iterate through a list of memory regions, maybe
672 * during deletion
673 * @h: the list_head
674 * @i: the pointer to a memory region wich contains list node data.
675 * @nxt: the structure containing the list_node
676 * @off: offset(relative to @i) at which list node data resides.
677 *
678 * For details see `list_for_each_off' and `list_for_each_safe'
679 * descriptions.
680 *
681 * Example:
682 * list_for_each_safe_off(&parent->children, child,
683 * next, offsetof(struct child, list))
684 * printf("Name: %s\n", child->name);
685 */
686#define list_for_each_safe_off(h, i, nxt, off)for (i = list_node_to_off_((h)->n.next, (off)), nxt = list_node_to_off_
(list_node_from_off_(i, (off))->next, (off)); list_node_from_off_
(i, (off)) != &(h)->n; i = nxt, nxt = list_node_to_off_
(list_node_from_off_(i, (off))->next, (off)))
\
687 for (i = list_node_to_off_(list_debug(h)(h)->n.next, (off)), \
688 nxt = list_node_to_off_(list_node_from_off_(i, (off))->next, \
689 (off)); \
690 list_node_from_off_(i, (off)) != &(h)->n; \
691 i = nxt, \
692 nxt = list_node_to_off_(list_node_from_off_(i, (off))->next, \
693 (off)))
694
695
696/* Other -off variants. */
697#define list_entry_off(n, type, off)((type *)list_node_from_off_((n), (off))) \
698 ((type *)list_node_from_off_((n), (off)))
699
700#define list_head_off(h, type, off)((type *)list_head_off((h), (off))) \
701 ((type *)list_head_off((h), (off)))
702
703#define list_tail_off(h, type, off)((type *)list_tail_((h), (off))) \
704 ((type *)list_tail_((h), (off)))
705
706#define list_add_off(h, n, off)list_add((h), list_node_from_off_((n), (off))) \
707 list_add((h), list_node_from_off_((n), (off)))
708
709#define list_del_off(n, off)list_del(list_node_from_off_((n), (off))) \
710 list_del(list_node_from_off_((n), (off)))
711
712#define list_del_from_off(h, n, off)list_del_from(h, list_node_from_off_((n), (off))) \
713 list_del_from(h, list_node_from_off_((n), (off)))
714
715/* Offset helper functions so we only single-evaluate. */
716static inline void *list_node_to_off_(struct list_node *node, size_t off)
717{
718 return (void *)((char *)node - off);
719}
720static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
721{
722 return (struct list_node *)((char *)ptr + off);
Casting a non-structure type to a structure type and accessing a field can lead to memory access errors or data corruption
723}
724
725/* Get the offset of the member, but make sure it's a list_node. */
726#define list_off_(type, member)(__builtin_offsetof(type, member) + ((typeof(((type *)0)->
member) *)0 != (struct list_node *)0))
\
727 (container_off(type, member)__builtin_offsetof(type, member) + \
728 check_type(((type *)0)->member, struct list_node)((typeof(((type *)0)->member) *)0 != (struct list_node *)0
)
)
729
730#define list_off_var_(var, member)(__builtin_offsetof(typeof(*var), member) + ((typeof(var->
member) *)0 != (struct list_node *)0))
\
731 (container_off_var(var, member)__builtin_offsetof(typeof(*var), member) + \
732 check_type(var->member, struct list_node)((typeof(var->member) *)0 != (struct list_node *)0))