1 /*
2 american fuzzy lop++ - linked list code
3 ---------------------------------------
4
5 Originally written by Michal Zalewski
6
7 Now maintained by Marc Heuse <[email protected]>,
8 Heiko Eißfeldt <[email protected]>,
9 Andrea Fioraldi <[email protected]>,
10 Dominik Maier <[email protected]>
11
12 Copyright 2016, 2017 Google Inc. All rights reserved.
13 Copyright 2019-2024 AFLplusplus Project. All rights reserved.
14
15 Licensed under the Apache License, Version 2.0 (the "License");
16 you may not use this file except in compliance with the License.
17 You may obtain a copy of the License at:
18
19 https://www.apache.org/licenses/LICENSE-2.0
20
21 This allocator is not designed to resist malicious attackers (the canaries
22 are small and predictable), but provides a robust and portable way to detect
23 use-after-free, off-by-one writes, stale pointers, and so on.
24
25 */
26
27 #ifndef AFL_LIST
28 #define AFL_LIST
29
30 #include <stdio.h>
31 #include <stdbool.h>
32 #include <string.h>
33
34 #include "debug.h"
35 #include "afl-prealloc.h"
36
37 /* How many elements to allocate before malloc is needed */
38 #define LIST_PREALLOC_SIZE (64)
39
40 typedef struct list_element {
41
42 PREALLOCABLE;
43
44 struct list_element *prev;
45 struct list_element *next;
46 void *data;
47
48 } element_t;
49
50 typedef struct list {
51
52 element_t element_prealloc_buf[LIST_PREALLOC_SIZE];
53 s32 element_prealloc_count;
54
55 } list_t;
56
get_head(list_t * list)57 static inline element_t *get_head(list_t *list) {
58
59 /* The first element is the head */
60 return list->element_prealloc_buf;
61
62 }
63
list_free_el(list_t * list,element_t * el)64 static inline void list_free_el(list_t *list, element_t *el) {
65
66 PRE_FREE(el, list->element_prealloc_count);
67
68 }
69
list_append(list_t * list,void * el)70 static inline void list_append(list_t *list, void *el) {
71
72 element_t *head = get_head(list);
73 if (!head->next) {
74
75 /* initialize */
76
77 memset(list, 0, sizeof(list_t));
78 PRE_ALLOC_FORCE(head, list->element_prealloc_count);
79 head->next = head->prev = head;
80
81 }
82
83 element_t *el_box = NULL;
84
85 PRE_ALLOC(el_box, list->element_prealloc_buf, LIST_PREALLOC_SIZE,
86 list->element_prealloc_count);
87 if (!el_box) { FATAL("failed to allocate list element"); }
88 el_box->data = el;
89 el_box->next = head;
90 el_box->prev = head->prev;
91 head->prev->next = el_box;
92 head->prev = el_box;
93
94 }
95
96 /* Simple foreach.
97 Pointer to the current element is in `el`,
98 casted to (a pointer) of the given `type`.
99 A return from this block will return from calling func.
100 */
101
102 #define LIST_FOREACH(list, type, block) \
103 do { \
104 \
105 list_t *li = (list); \
106 element_t *head = get_head((li)); \
107 element_t *el_box = (head)->next; \
108 if (!el_box) FATAL("foreach over uninitialized list"); \
109 while (el_box != head) { \
110 \
111 __attribute__((unused)) type *el = (type *)((el_box)->data); \
112 /* get next so el_box can be unlinked */ \
113 element_t *next = el_box->next; \
114 {block}; \
115 el_box = next; \
116 \
117 } \
118 \
119 } while (0);
120
121 /* In foreach: remove the current el from the list */
122
123 #define LIST_REMOVE_CURRENT_EL_IN_FOREACH() \
124 do { \
125 \
126 el_box->prev->next = next; \
127 el_box->next->prev = el_box->prev; \
128 list_free_el(li, el_box); \
129 \
130 } while (0);
131
132 /* Same as foreach, but will clear list in the process */
133
134 #define LIST_FOREACH_CLEAR(list, type, block) \
135 do { \
136 \
137 LIST_FOREACH((list), type, { \
138 \
139 {block}; \
140 LIST_REMOVE_CURRENT_EL_IN_FOREACH(); \
141 \
142 }); \
143 \
144 } while (0);
145
146 /* remove an item from the list */
147
list_remove(list_t * list,void * remove_me)148 static inline void list_remove(list_t *list, void *remove_me) {
149
150 LIST_FOREACH(list, void, {
151
152 if (el == remove_me) {
153
154 el_box->prev->next = el_box->next;
155 el_box->next->prev = el_box->prev;
156 el_box->data = NULL;
157 list_free_el(list, el_box);
158 return;
159
160 }
161
162 });
163
164 FATAL("List item to be removed not in list");
165
166 }
167
168 /* Returns true if el is in list */
169
list_contains(list_t * list,void * contains_me)170 static inline bool list_contains(list_t *list, void *contains_me) {
171
172 LIST_FOREACH(list, void, {
173
174 if (el == contains_me) return true;
175
176 });
177
178 return false;
179
180 }
181
182 #endif
183
184