1 /*
2 * libwebsockets - small server side websockets and web server implementation
3 *
4 * Copyright (C) 2010 - 2021 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 struct lws_dsh_search {
28 size_t required;
29 int kind;
30 lws_dsh_obj_t *best;
31 lws_dsh_t *dsh;
32
33 lws_dsh_t *already_checked;
34 lws_dsh_t *this_dsh;
35 };
36
37 static int
38 _lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
39 const void *src2, size_t size2, lws_dll2_t *replace);
40
41 static size_t
lws_dsh_align(size_t length)42 lws_dsh_align(size_t length)
43 {
44 size_t align = sizeof(int *);
45
46 if (length & (align - 1))
47 length += align - (length & (align - 1));
48
49 return length;
50 }
51
52 lws_dsh_t *
lws_dsh_create(lws_dll2_owner_t * owner,size_t buf_len,int count_kinds)53 lws_dsh_create(lws_dll2_owner_t *owner, size_t buf_len, int count_kinds)
54 {
55 size_t oha_len = sizeof(lws_dsh_obj_head_t) * (unsigned int)(++count_kinds);
56 lws_dsh_obj_t *obj;
57 lws_dsh_t *dsh;
58 int n;
59
60 assert(buf_len);
61 assert(count_kinds > 1);
62 assert(buf_len > sizeof(lws_dsh_t) + oha_len);
63 buf_len += 64;
64
65 dsh = lws_malloc(sizeof(lws_dsh_t) + buf_len + oha_len, __func__);
66 if (!dsh)
67 return NULL;
68
69 /* set convenience pointers to the overallocated parts */
70
71 dsh->oha = (lws_dsh_obj_head_t *)&dsh[1];
72 dsh->buf = ((uint8_t *)dsh->oha) + oha_len;
73 dsh->count_kinds = count_kinds;
74 dsh->buffer_size = buf_len;
75 dsh->being_destroyed = 0;
76
77 /* clear down the obj heads array */
78
79 memset(dsh->oha, 0, oha_len);
80 for (n = 0; n < count_kinds; n++) {
81 dsh->oha[n].kind = n;
82 dsh->oha[n].total_size = 0;
83 }
84
85 /* initially the whole buffer is on the free kind (0) list */
86
87 obj = (lws_dsh_obj_t *)dsh->buf;
88 memset(obj, 0, sizeof(*obj));
89 obj->asize = buf_len - sizeof(*obj);
90
91 lws_dll2_add_head(&obj->list, &dsh->oha[0].owner);
92
93 dsh->locally_free = obj->asize;
94 dsh->locally_in_use = 0;
95
96 lws_dll2_clear(&dsh->list);
97 if (owner)
98 lws_dll2_add_head(&dsh->list, owner);
99
100 // lws_dsh_describe(dsh, "post-init");
101
102 return dsh;
103 }
104
105 static int
search_best_free(struct lws_dll2 * d,void * user)106 search_best_free(struct lws_dll2 *d, void *user)
107 {
108 struct lws_dsh_search *s = (struct lws_dsh_search *)user;
109 lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
110
111 lwsl_debug("%s: obj %p, asize %zu (req %zu)\n", __func__, obj,
112 obj->asize, s->required);
113
114 if (obj->asize >= s->required &&
115 (!s->best || obj->asize < s->best->asize)) {
116 s->best = obj;
117 s->dsh = s->this_dsh;
118 }
119
120 return 0;
121 }
122
123 void
lws_dsh_destroy(lws_dsh_t ** pdsh)124 lws_dsh_destroy(lws_dsh_t **pdsh)
125 {
126 lws_dsh_t *dsh = *pdsh;
127
128 if (!dsh)
129 return;
130
131 dsh->being_destroyed = 1;
132
133 lws_dll2_remove(&dsh->list);
134
135 /* everything else is in one heap allocation */
136
137 lws_free_set_NULL(*pdsh);
138 }
139
140 size_t
lws_dsh_get_size(struct lws_dsh * dsh,int kind)141 lws_dsh_get_size(struct lws_dsh *dsh, int kind)
142 {
143 kind++;
144 assert(kind < dsh->count_kinds);
145
146 return dsh->oha[kind].total_size;
147 }
148
149 static int
_lws_dsh_alloc_tail(lws_dsh_t * dsh,int kind,const void * src1,size_t size1,const void * src2,size_t size2,lws_dll2_t * replace)150 _lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
151 const void *src2, size_t size2, lws_dll2_t *replace)
152 {
153 size_t asize = sizeof(lws_dsh_obj_t) + lws_dsh_align(size1 + size2);
154 struct lws_dsh_search s;
155
156 assert(kind >= 0);
157 kind++;
158 assert(!dsh || kind < dsh->count_kinds);
159
160 /*
161 * Search our free list looking for the smallest guy who will fit
162 * what we want to allocate
163 */
164 s.required = asize;
165 s.kind = kind;
166 s.best = NULL;
167 s.already_checked = NULL;
168 s.this_dsh = dsh;
169
170 if (dsh && !dsh->being_destroyed)
171 lws_dll2_foreach_safe(&dsh->oha[0].owner, &s, search_best_free);
172
173 if (!s.best) {
174 lwsl_notice("%s: no buffer has space\n", __func__);
175
176 return 1;
177 }
178
179 /* anything coming out of here must be aligned */
180 assert(!(((unsigned long)s.best) & (sizeof(int *) - 1)));
181
182 if (s.best->asize < asize + (2 * sizeof(*s.best))) {
183 /*
184 * Exact fit, or close enough we can't / don't want to have to
185 * track the little bit of free area that would be left.
186 *
187 * Move the object from the free list to the oha of the
188 * desired kind
189 */
190 lws_dll2_remove(&s.best->list);
191 s.best->dsh = s.dsh;
192 s.best->kind = kind;
193 s.best->size = size1 + size2;
194 memcpy(&s.best[1], src1, size1);
195 if (src2)
196 memcpy((uint8_t *)&s.best[1] + size1, src2, size2);
197
198 if (replace) {
199 s.best->list.prev = replace->prev;
200 s.best->list.next = replace->next;
201 s.best->list.owner = replace->owner;
202 if (replace->prev)
203 replace->prev->next = &s.best->list;
204 if (replace->next)
205 replace->next->prev = &s.best->list;
206 } else
207 if (dsh) {
208 assert(!(((unsigned long)(intptr_t)(s.best)) & (sizeof(int *) - 1)));
209 lws_dll2_add_tail(&s.best->list, &dsh->oha[kind].owner);
210 }
211
212 assert(s.dsh->locally_free >= s.best->asize);
213 s.dsh->locally_free -= s.best->asize;
214 s.dsh->locally_in_use += s.best->asize;
215 dsh->oha[kind].total_size += s.best->asize;
216 assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
217 } else {
218 lws_dsh_obj_t *obj;
219
220 /*
221 * Free area was oversize enough that we need to split it.
222 *
223 * Leave the first part of the free area where it is and
224 * reduce its extent by our asize. Use the latter part of
225 * the original free area as the allocation.
226 */
227 lwsl_debug("%s: splitting... free reduce %zu -> %zu\n",
228 __func__, s.best->asize, s.best->asize - asize);
229
230 s.best->asize -= asize;
231
232 /* latter part becomes new object */
233
234 obj = (lws_dsh_obj_t *)(((uint8_t *)s.best) + lws_dsh_align(s.best->asize));
235
236 lws_dll2_clear(&obj->list);
237 obj->dsh = s.dsh;
238 obj->kind = kind;
239 obj->size = size1 + size2;
240 obj->asize = asize;
241
242 memcpy(&obj[1], src1, size1);
243 if (src2)
244 memcpy((uint8_t *)&obj[1] + size1, src2, size2);
245
246 if (replace) {
247 s.best->list.prev = replace->prev;
248 s.best->list.next = replace->next;
249 s.best->list.owner = replace->owner;
250 if (replace->prev)
251 replace->prev->next = &s.best->list;
252 if (replace->next)
253 replace->next->prev = &s.best->list;
254 } else
255 if (dsh) {
256 assert(!(((unsigned long)(intptr_t)(obj)) & (sizeof(int *) - 1)));
257 lws_dll2_add_tail(&obj->list, &dsh->oha[kind].owner);
258 }
259
260 assert(s.dsh->locally_free >= asize);
261 s.dsh->locally_free -= asize;
262 s.dsh->locally_in_use += asize;
263 dsh->oha[kind].total_size += asize;
264 assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
265 }
266
267 // lws_dsh_describe(dsh, "post-alloc");
268
269 return 0;
270 }
271
272 int
lws_dsh_alloc_tail(lws_dsh_t * dsh,int kind,const void * src1,size_t size1,const void * src2,size_t size2)273 lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
274 const void *src2, size_t size2)
275 {
276 return _lws_dsh_alloc_tail(dsh, kind, src1, size1, src2, size2, NULL);
277 }
278
279 static int
buf_compare(const lws_dll2_t * d,const lws_dll2_t * i)280 buf_compare(const lws_dll2_t *d, const lws_dll2_t *i)
281 {
282 return (int)lws_ptr_diff(d, i);
283 }
284
285 void
lws_dsh_free(void ** pobj)286 lws_dsh_free(void **pobj)
287 {
288 lws_dsh_obj_t *_o = (lws_dsh_obj_t *)((uint8_t *)(*pobj) - sizeof(*_o)),
289 *_o2;
290 lws_dsh_t *dsh = _o->dsh;
291
292 /* anything coming out of here must be aligned */
293 assert(!(((unsigned long)_o) & (sizeof(int *) - 1)));
294
295 /*
296 * Remove the object from its list and place on the free list of the
297 * dsh the buffer space belongs to
298 */
299
300 lws_dll2_remove(&_o->list);
301 *pobj = NULL;
302
303 assert(dsh->locally_in_use >= _o->asize);
304 dsh->locally_free += _o->asize;
305 dsh->locally_in_use -= _o->asize;
306 dsh->oha[_o->kind].total_size -= _o->asize; /* account for usage by kind */
307 assert(dsh->locally_in_use <= dsh->buffer_size);
308
309 /*
310 * The free space list is sorted in buffer address order, so detecting
311 * coalescing opportunities is cheap. Because the free list should be
312 * continuously tending to reduce by coalescing, the sorting should not
313 * be expensive to maintain.
314 */
315 _o->size = 0; /* not meaningful when on free list */
316 lws_dll2_add_sorted(&_o->list, &_o->dsh->oha[0].owner, buf_compare);
317
318 /* First check for already-free block at the end we can subsume.
319 * Because the free list is sorted, if there is such a guy he is
320 * already our list.next */
321
322 _o2 = (lws_dsh_obj_t *)_o->list.next;
323 if (_o2 && (uint8_t *)_o + _o->asize == (uint8_t *)_o2) {
324 /*
325 * since we are freeing _obj, we can coalesce with a
326 * free area immediately ahead of it
327 *
328 * [ _o (being freed) ][ _o2 (free) ] -> [ larger _o ]
329 */
330 _o->asize += _o2->asize;
331
332 /* guy next to us was absorbed into us */
333 lws_dll2_remove(&_o2->list);
334 }
335
336 /* Then check if we can be subsumed by a free block behind us.
337 * Because the free list is sorted, if there is such a guy he is
338 * already our list.prev */
339
340 _o2 = (lws_dsh_obj_t *)_o->list.prev;
341 if (_o2 && (uint8_t *)_o2 + _o2->asize == (uint8_t *)_o) {
342 /*
343 * since we are freeing obj, we can coalesce it with
344 * the previous free area that abuts it
345 *
346 * [ _o2 (free) ][ _o (being freed) ] -> [ larger _o2 ]
347 */
348 _o2->asize += _o->asize;
349
350 /* we were absorbed! */
351 lws_dll2_remove(&_o->list);
352 }
353
354 // lws_dsh_describe(dsh, "post-alloc");
355 }
356
357 int
lws_dsh_get_head(lws_dsh_t * dsh,int kind,void ** obj,size_t * size)358 lws_dsh_get_head(lws_dsh_t *dsh, int kind, void **obj, size_t *size)
359 {
360 lws_dsh_obj_t *_obj;
361
362 if (!dsh)
363 return 1;
364
365 _obj = (lws_dsh_obj_t *)lws_dll2_get_head(&dsh->oha[kind + 1].owner);
366
367 if (!_obj) {
368 *obj = 0;
369 *size = 0;
370
371 return 1; /* there is no head */
372 }
373
374 *obj = (void *)(&_obj[1]);
375 *size = _obj->size;
376
377 /* anything coming out of here must be aligned */
378 assert(!(((unsigned long)(intptr_t)(*obj)) & (sizeof(int *) - 1)));
379
380 return 0; /* we returned the head */
381 }
382
383 #if defined(_DEBUG) && !defined(LWS_WITH_NO_LOGS)
384
385 static int
describe_kind(struct lws_dll2 * d,void * user)386 describe_kind(struct lws_dll2 *d, void *user)
387 {
388 lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
389
390 lwsl_info(" _obj %p - %p, dsh %p, size %zu, asize %zu\n",
391 obj, (uint8_t *)obj + obj->asize,
392 obj->dsh, obj->size, obj->asize);
393
394 return 0;
395 }
396
397 void
lws_dsh_describe(lws_dsh_t * dsh,const char * desc)398 lws_dsh_describe(lws_dsh_t *dsh, const char *desc)
399 {
400 int n = 0;
401
402 lwsl_info("%s: dsh %p, bufsize %zu, kinds %d, lf: %zu, liu: %zu, %s\n",
403 __func__, dsh, dsh->buffer_size, dsh->count_kinds,
404 dsh->locally_free, dsh->locally_in_use, desc);
405
406 for (n = 0; n < dsh->count_kinds; n++) {
407 lwsl_info(" Kind %d:\n", n);
408 lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, describe_kind);
409 }
410 }
411 #endif
412