1 /*
2 * libwebsockets - small server side websockets and web server implementation
3 *
4 * Copyright (C) 2010 - 2019 Andy Green <andy@warmcat.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to
8 * deal in the Software without restriction, including without limitation the
9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 * sell copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 */
24
25 #include "private-lib-core.h"
26
27 #ifdef LWS_HAVE_SYS_TYPES_H
28 #include <sys/types.h>
29 #endif
30
31 int
lws_dll2_is_detached(const struct lws_dll2 * d)32 lws_dll2_is_detached(const struct lws_dll2 *d)
33 {
34 if (d->owner)
35 return 0;
36
37 if (d->next || d->prev) {
38 lwsl_err("%s: dll2 %p: detached but next %p, prev %p\n",
39 __func__, d, d->next, d->prev);
40 /*
41 * New lws_dll2 objects and removed lws_dll2 objects
42 * have .owner, .next and .prev all set to NULL, so we
43 * can just check .owner to see if we are detached.
44 *
45 * We assert here if we encounter an lws_dll2 in the illegal
46 * state of NULL .owner, but non-NULL in .next or .prev,
47 * it's evidence of corruption, use-after-free, threads
48 * contending on accessing without locking etc.
49 */
50 assert(0);
51 }
52
53 return 1;
54 }
55
56 int
lws_dll2_foreach_safe(struct lws_dll2_owner * owner,void * user,int (* cb)(struct lws_dll2 * d,void * user))57 lws_dll2_foreach_safe(struct lws_dll2_owner *owner, void *user,
58 int (*cb)(struct lws_dll2 *d, void *user))
59 {
60 lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp, owner->head) {
61 if (cb(p, user))
62 return 1;
63 } lws_end_foreach_dll_safe(p, tp);
64
65 return 0;
66 }
67
68 void
lws_dll2_add_head(struct lws_dll2 * d,struct lws_dll2_owner * owner)69 lws_dll2_add_head(struct lws_dll2 *d, struct lws_dll2_owner *owner)
70 {
71 if (!lws_dll2_is_detached(d)) {
72 assert(0); /* only wholly detached things can be added */
73 return;
74 }
75
76 /* our next guy is current first guy, if any */
77 if (owner->head != d)
78 d->next = owner->head;
79
80 /* if there is a next guy, set his prev ptr to our next ptr */
81 if (d->next)
82 d->next->prev = d;
83 /* there is nobody previous to us, we are the head */
84 d->prev = NULL;
85
86 /* set the first guy to be us */
87 owner->head = d;
88
89 if (!owner->tail)
90 owner->tail = d;
91
92 d->owner = owner;
93 owner->count++;
94 }
95
96 /*
97 * add us to the list that 'after' is in, just before him
98 */
99
100 void
lws_dll2_add_before(struct lws_dll2 * d,struct lws_dll2 * after)101 lws_dll2_add_before(struct lws_dll2 *d, struct lws_dll2 *after)
102 {
103 lws_dll2_owner_t *owner = after->owner;
104
105 if (!lws_dll2_is_detached(d)) {
106 assert(0); /* only wholly detached things can be added */
107 return;
108 }
109
110 if (lws_dll2_is_detached(after)) {
111 assert(0); /* can't add after something detached */
112 return;
113 }
114
115 d->owner = owner;
116
117 /* we need to point forward to after */
118
119 d->next = after;
120
121 /* we need to point back to after->prev */
122
123 d->prev = after->prev;
124
125 /* guy that used to point to after, needs to point to us */
126
127 if (after->prev)
128 after->prev->next = d;
129 else
130 owner->head = d;
131
132 /* then after needs to point back to us */
133
134 after->prev = d;
135
136 owner->count++;
137 }
138
139 void
lws_dll2_add_tail(struct lws_dll2 * d,struct lws_dll2_owner * owner)140 lws_dll2_add_tail(struct lws_dll2 *d, struct lws_dll2_owner *owner)
141 {
142 if (!lws_dll2_is_detached(d)) {
143 assert(0); /* only wholly detached things can be added */
144 return;
145 }
146
147 /* our previous guy is current last guy */
148 d->prev = owner->tail;
149 /* if there is a prev guy, set his next ptr to our prev ptr */
150 if (d->prev)
151 d->prev->next = d;
152 /* our next ptr is NULL */
153 d->next = NULL;
154 /* set the last guy to be us */
155 owner->tail = d;
156
157 /* list head is also us if we're the first */
158 if (!owner->head)
159 owner->head = d;
160
161 d->owner = owner;
162 owner->count++;
163 }
164
165 void
lws_dll2_remove(struct lws_dll2 * d)166 lws_dll2_remove(struct lws_dll2 *d)
167 {
168 if (lws_dll2_is_detached(d))
169 return;
170
171 /* if we have a next guy, set his prev to our prev */
172 if (d->next)
173 d->next->prev = d->prev;
174
175 /* if we have a previous guy, set his next to our next */
176 if (d->prev)
177 d->prev->next = d->next;
178
179 /* if we have phead, track the tail and head if it points to us... */
180
181 if (d->owner->tail == d)
182 d->owner->tail = d->prev;
183
184 if (d->owner->head == d)
185 d->owner->head = d->next;
186
187 d->owner->count--;
188
189 /* we're out of the list, we should not point anywhere any more */
190 d->owner = NULL;
191 d->prev = NULL;
192 d->next = NULL;
193 }
194
195 void
lws_dll2_clear(struct lws_dll2 * d)196 lws_dll2_clear(struct lws_dll2 *d)
197 {
198 d->owner = NULL;
199 d->prev = NULL;
200 d->next = NULL;
201 }
202
203 void
lws_dll2_owner_clear(struct lws_dll2_owner * d)204 lws_dll2_owner_clear(struct lws_dll2_owner *d)
205 {
206 d->head = NULL;
207 d->tail = NULL;
208 d->count = 0;
209 }
210
211 void
lws_dll2_add_sorted_priv(lws_dll2_t * d,lws_dll2_owner_t * own,void * priv,int (* compare3)(void * priv,const lws_dll2_t * d,const lws_dll2_t * i))212 lws_dll2_add_sorted_priv(lws_dll2_t *d, lws_dll2_owner_t *own, void *priv,
213 int (*compare3)(void *priv, const lws_dll2_t *d,
214 const lws_dll2_t *i))
215 {
216 lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp,
217 lws_dll2_get_head(own)) {
218 assert(p != d);
219
220 if (compare3(priv, p, d) >= 0) {
221 /* drop us in before this guy */
222 lws_dll2_add_before(d, p);
223
224 return;
225 }
226 } lws_end_foreach_dll_safe(p, tp);
227
228 /*
229 * Either nobody on the list yet to compare him to, or he's the
230 * furthest away timeout... stick him at the tail end
231 */
232
233 lws_dll2_add_tail(d, own);
234 }
235
236 void
lws_dll2_add_sorted(lws_dll2_t * d,lws_dll2_owner_t * own,int (* compare)(const lws_dll2_t * d,const lws_dll2_t * i))237 lws_dll2_add_sorted(lws_dll2_t *d, lws_dll2_owner_t *own,
238 int (*compare)(const lws_dll2_t *d, const lws_dll2_t *i))
239 {
240 lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp,
241 lws_dll2_get_head(own)) {
242 assert(p != d);
243
244 if (compare(p, d) >= 0) {
245 /* drop us in before this guy */
246 lws_dll2_add_before(d, p);
247
248 return;
249 }
250 } lws_end_foreach_dll_safe(p, tp);
251
252 /*
253 * Either nobody on the list yet to compare him to, or he's the
254 * furthest away timeout... stick him at the tail end
255 */
256
257 lws_dll2_add_tail(d, own);
258 }
259
260 void *
_lws_dll2_search_sz_pl(lws_dll2_owner_t * own,const char * name,size_t namelen,size_t dll2_ofs,size_t ptr_ofs)261 _lws_dll2_search_sz_pl(lws_dll2_owner_t *own, const char *name, size_t namelen,
262 size_t dll2_ofs, size_t ptr_ofs)
263 {
264 lws_start_foreach_dll(struct lws_dll2 *, p, lws_dll2_get_head(own)) {
265 uint8_t *ref = ((uint8_t *)p) - dll2_ofs;
266 /*
267 * We have to read the const char * at the computed place and
268 * the string is where that points
269 */
270 const char *str = *((const char **)(ref + ptr_ofs));
271
272 if (str && !strncmp(str, name, namelen) && !str[namelen])
273 return (void *)ref;
274 } lws_end_foreach_dll(p);
275
276 return NULL;
277 }
278
279 #if defined(_DEBUG)
280
281 void
lws_dll2_describe(lws_dll2_owner_t * owner,const char * desc)282 lws_dll2_describe(lws_dll2_owner_t *owner, const char *desc)
283 {
284 #if _LWS_ENABLED_LOGS & LLL_INFO
285 int n = 1;
286
287 lwsl_info("%s: %s: owner %p: count %d, head %p, tail %p\n",
288 __func__, desc, owner, (int)owner->count, owner->head, owner->tail);
289
290 lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp,
291 lws_dll2_get_head(owner)) {
292 lwsl_info("%s: %d: %p: owner %p, prev %p, next %p\n",
293 __func__, n++, p, p->owner, p->prev, p->next);
294 } lws_end_foreach_dll_safe(p, tp);
295 #endif
296 }
297
298 #endif
299