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 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) * ++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
63 dsh = lws_malloc(sizeof(lws_dsh_t) + buf_len + oha_len, __func__);
64 if (!dsh)
65 return NULL;
66
67 /* set convenience pointers to the overallocated parts */
68
69 dsh->oha = (lws_dsh_obj_head_t *)&dsh[1];
70 dsh->buf = ((uint8_t *)dsh->oha) + oha_len;
71 dsh->count_kinds = count_kinds;
72 dsh->buffer_size = buf_len;
73 dsh->being_destroyed = 0;
74
75 /* clear down the obj heads array */
76
77 memset(dsh->oha, 0, oha_len);
78 for (n = 0; n < count_kinds; n++)
79 dsh->oha[n].kind = n;
80
81 /* initially the whole buffer is on the free kind (0) list */
82
83 obj = (lws_dsh_obj_t *)dsh->buf;
84 memset(obj, 0, sizeof(*obj));
85 obj->asize = buf_len - sizeof(*obj);
86
87 lws_dll2_add_head(&obj->list, &dsh->oha[0].owner);
88
89 dsh->locally_free = obj->asize;
90 dsh->locally_in_use = 0;
91
92 lws_dll2_clear(&dsh->list);
93 if (owner)
94 lws_dll2_add_head(&dsh->list, owner);
95
96 // lws_dsh_describe(dsh, "post-init");
97
98 return dsh;
99 }
100
101 static int
search_best_free(struct lws_dll2 * d,void * user)102 search_best_free(struct lws_dll2 *d, void *user)
103 {
104 struct lws_dsh_search *s = (struct lws_dsh_search *)user;
105 lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
106
107 lwsl_debug("%s: obj %p, asize %zu (req %zu)\n", __func__, obj,
108 obj->asize, s->required);
109
110 if (obj->asize >= s->required &&
111 (!s->best || obj->asize < s->best->asize)) {
112 s->best = obj;
113 s->dsh = s->this_dsh;
114 }
115
116 return 0;
117 }
118
119 static int
try_foreign(struct lws_dll2 * d,void * user)120 try_foreign(struct lws_dll2 *d, void *user)
121 {
122 struct lws_dsh_search *s = (struct lws_dsh_search *)user;
123 lws_dsh_t *dsh1 = lws_container_of(d, lws_dsh_t, list);
124
125 if (dsh1 == s->already_checked)
126 return 0;
127
128 if (dsh1->being_destroyed)
129 return 0;
130
131 if (dsh1->count_kinds < s->kind + 1)
132 return 0;
133
134 lwsl_debug("%s: actual try_foreign: dsh %p (free list size %d)\n",
135 __func__, dsh1, dsh1->oha[0].owner.count);
136
137 s->this_dsh = dsh1;
138 if (lws_dll2_foreach_safe(&dsh1->oha[0].owner, s, search_best_free))
139 return 1;
140
141 return 0;
142 }
143
144 static int
free_foreign(struct lws_dll2 * d,void * user)145 free_foreign(struct lws_dll2 *d, void *user)
146 {
147 lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
148 lws_dsh_t *dsh = (lws_dsh_t *)user;
149 void *p = (void *)&obj[1];
150
151 if (obj->dsh != dsh)
152 lws_dsh_free(&p);
153
154 return 0;
155 }
156
157 static int
evict2(struct lws_dll2 * d,void * user)158 evict2(struct lws_dll2 *d, void *user)
159 {
160 lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
161 lws_dsh_t *dsh = (lws_dsh_t *)user;
162 void *p;
163
164 if (obj->dsh != dsh)
165 return 0;
166
167 /*
168 * If we are here, it means obj is a live object that is allocated on
169 * the dsh being destroyed, from a different dsh. We need to migrate
170 * the object to a dsh that isn't being destroyed.
171 */
172
173 lwsl_debug("%s: migrating object size %zu\n", __func__, obj->size);
174
175 if (_lws_dsh_alloc_tail(dsh, 0, (void *)&obj[1], obj->size, NULL, 0, &obj->list)) {
176 lwsl_notice("%s: failed to migrate object\n", __func__);
177 /*
178 * only thing we can do is drop the logical object
179 */
180 p = (uint8_t *)&obj[1];
181 lws_dsh_free(&p);
182 }
183
184 return 0;
185 }
186
187 static int
evict1(struct lws_dll2 * d,void * user)188 evict1(struct lws_dll2 *d, void *user)
189 {
190 lws_dsh_t *dsh1 = lws_container_of(d, lws_dsh_t, list);
191 lws_dsh_t *dsh = (lws_dsh_t *)user;
192 int n;
193
194 if (dsh1->being_destroyed)
195 return 0;
196
197 /*
198 * For every dsh that's not being destroyed, send every object to
199 * evict2 for checking.
200 */
201
202 lwsl_debug("%s: checking dsh %p\n", __func__, dsh1);
203
204 for (n = 1; n < dsh1->count_kinds; n++) {
205 lws_dll2_describe(&dsh1->oha[n].owner, "check dsh1");
206 lws_dll2_foreach_safe(&dsh1->oha[n].owner, dsh, evict2);
207 }
208
209 return 0;
210 }
211
212 void
lws_dsh_destroy(lws_dsh_t ** pdsh)213 lws_dsh_destroy(lws_dsh_t **pdsh)
214 {
215 lws_dsh_t *dsh = *pdsh;
216 int n;
217
218 if (!dsh)
219 return;
220
221 lwsl_debug("%s: destroying dsh %p\n", __func__, dsh);
222
223 dsh->being_destroyed = 1;
224
225 /* we need to explicitly free any of our allocations in foreign dsh */
226
227 for (n = 1; n < dsh->count_kinds; n++)
228 lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, free_foreign);
229
230 /*
231 * We need to have anybody else with allocations in us evict them
232 * and make a copy in a buffer that isn't being destroyed
233 */
234
235 if (dsh->list.owner)
236 lws_dll2_foreach_safe(dsh->list.owner, dsh, evict1);
237
238 lws_dll2_remove(&dsh->list);
239
240 /* everything else is in one heap allocation */
241
242 lws_free_set_NULL(*pdsh);
243 }
244
245 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)246 _lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
247 const void *src2, size_t size2, lws_dll2_t *replace)
248 {
249 size_t asize = sizeof(lws_dsh_obj_t) + lws_dsh_align(size1 + size2);
250 struct lws_dsh_search s;
251
252 assert(kind >= 0);
253 kind++;
254 assert(!dsh || kind < dsh->count_kinds);
255
256 /*
257 * Search our free list looking for the smallest guy who will fit
258 * what we want to allocate
259 */
260 s.required = asize;
261 s.kind = kind;
262 s.best = NULL;
263 s.already_checked = NULL;
264 s.this_dsh = dsh;
265
266 if (dsh && !dsh->being_destroyed)
267 lws_dll2_foreach_safe(&dsh->oha[0].owner, &s, search_best_free);
268
269 if (!s.best) {
270 /*
271 * Let's see if any other buffer has room
272 */
273 s.already_checked = dsh;
274
275 if (dsh && dsh->list.owner)
276 lws_dll2_foreach_safe(dsh->list.owner, &s, try_foreign);
277
278 if (!s.best) {
279 lwsl_notice("%s: no buffer has space\n", __func__);
280
281 return 1;
282 }
283 }
284
285 /* anything coming out of here must be aligned */
286 assert(!(((unsigned long)s.best) & (sizeof(int *) - 1)));
287
288 if (s.best->asize < asize + (2 * sizeof(*s.best))) {
289 /*
290 * Exact fit, or close enough we can't / don't want to have to
291 * track the little bit of free area that would be left.
292 *
293 * Move the object from the free list to the oha of the
294 * desired kind
295 */
296 lws_dll2_remove(&s.best->list);
297 s.best->dsh = s.dsh;
298 s.best->size = size1 + size2;
299 memcpy(&s.best[1], src1, size1);
300 if (src2)
301 memcpy((uint8_t *)&s.best[1] + size1, src2, size2);
302
303 if (replace) {
304 s.best->list.prev = replace->prev;
305 s.best->list.next = replace->next;
306 s.best->list.owner = replace->owner;
307 if (replace->prev)
308 replace->prev->next = &s.best->list;
309 if (replace->next)
310 replace->next->prev = &s.best->list;
311 } else
312 if (dsh)
313 lws_dll2_add_tail(&s.best->list, &dsh->oha[kind].owner);
314
315 assert(s.dsh->locally_free >= s.best->asize);
316 s.dsh->locally_free -= s.best->asize;
317 s.dsh->locally_in_use += s.best->asize;
318 assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
319 } else {
320 lws_dsh_obj_t *obj;
321
322 /*
323 * Free area was oversize enough that we need to split it.
324 *
325 * Leave the first part of the free area where it is and
326 * reduce its extent by our asize. Use the latter part of
327 * the original free area as the allocation.
328 */
329 lwsl_debug("%s: splitting... free reduce %zu -> %zu\n",
330 __func__, s.best->asize, s.best->asize - asize);
331
332 s.best->asize -= asize;
333
334 /* latter part becomes new object */
335
336 obj = (lws_dsh_obj_t *)(((uint8_t *)s.best) + s.best->asize);
337
338 lws_dll2_clear(&obj->list);
339 obj->dsh = s.dsh;
340 obj->size = size1 + size2;
341 obj->asize = asize;
342
343 memcpy(&obj[1], src1, size1);
344 if (src2)
345 memcpy((uint8_t *)&obj[1] + size1, src2, size2);
346
347 if (replace) {
348 s.best->list.prev = replace->prev;
349 s.best->list.next = replace->next;
350 s.best->list.owner = replace->owner;
351 if (replace->prev)
352 replace->prev->next = &s.best->list;
353 if (replace->next)
354 replace->next->prev = &s.best->list;
355 } else
356 if (dsh)
357 lws_dll2_add_tail(&obj->list, &dsh->oha[kind].owner);
358
359 assert(s.dsh->locally_free >= asize);
360 s.dsh->locally_free -= asize;
361 s.dsh->locally_in_use += asize;
362 assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
363 }
364
365 // lws_dsh_describe(dsh, "post-alloc");
366
367 return 0;
368 }
369
370 int
lws_dsh_alloc_tail(lws_dsh_t * dsh,int kind,const void * src1,size_t size1,const void * src2,size_t size2)371 lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
372 const void *src2, size_t size2)
373 {
374 return _lws_dsh_alloc_tail(dsh, kind, src1, size1, src2, size2, NULL);
375 }
376
377 static int
buf_compare(const lws_dll2_t * d,const lws_dll2_t * i)378 buf_compare(const lws_dll2_t *d, const lws_dll2_t *i)
379 {
380 return (int)lws_ptr_diff(d, i);
381 }
382
383 void
lws_dsh_free(void ** pobj)384 lws_dsh_free(void **pobj)
385 {
386 lws_dsh_obj_t *_o = (lws_dsh_obj_t *)((uint8_t *)(*pobj) - sizeof(*_o)),
387 *_o2;
388 lws_dsh_t *dsh = _o->dsh;
389
390 /* anything coming out of here must be aligned */
391 assert(!(((unsigned long)_o) & (sizeof(int *) - 1)));
392
393 /*
394 * Remove the object from its list and place on the free list of the
395 * dsh the buffer space belongs to
396 */
397
398 lws_dll2_remove(&_o->list);
399 *pobj = NULL;
400
401 assert(dsh->locally_in_use >= _o->asize);
402 dsh->locally_free += _o->asize;
403 dsh->locally_in_use -= _o->asize;
404 assert(dsh->locally_in_use <= dsh->buffer_size);
405
406 /*
407 * The free space list is sorted in buffer address order, so detecting
408 * coalescing opportunities is cheap. Because the free list should be
409 * continuously tending to reduce by coalescing, the sorting should not
410 * be expensive to maintain.
411 */
412 _o->size = 0; /* not meaningful when on free list */
413 lws_dll2_add_sorted(&_o->list, &_o->dsh->oha[0].owner, buf_compare);
414
415 /* First check for already-free block at the end we can subsume.
416 * Because the free list is sorted, if there is such a guy he is
417 * already our list.next */
418
419 _o2 = (lws_dsh_obj_t *)_o->list.next;
420 if (_o2 && (uint8_t *)_o + _o->asize == (uint8_t *)_o2) {
421 /*
422 * since we are freeing _obj, we can coalesce with a
423 * free area immediately ahead of it
424 *
425 * [ _o (being freed) ][ _o2 (free) ] -> [ larger _o ]
426 */
427 _o->asize += _o2->asize;
428
429 /* guy next to us was absorbed into us */
430 lws_dll2_remove(&_o2->list);
431 }
432
433 /* Then check if we can be subsumed by a free block behind us.
434 * Because the free list is sorted, if there is such a guy he is
435 * already our list.prev */
436
437 _o2 = (lws_dsh_obj_t *)_o->list.prev;
438 if (_o2 && (uint8_t *)_o2 + _o2->asize == (uint8_t *)_o) {
439 /*
440 * since we are freeing obj, we can coalesce it with
441 * the previous free area that abuts it
442 *
443 * [ _o2 (free) ][ _o (being freed) ] -> [ larger _o2 ]
444 */
445 _o2->asize += _o->asize;
446
447 /* we were absorbed! */
448 lws_dll2_remove(&_o->list);
449 }
450
451 // lws_dsh_describe(dsh, "post-alloc");
452 }
453
454 int
lws_dsh_get_head(lws_dsh_t * dsh,int kind,void ** obj,size_t * size)455 lws_dsh_get_head(lws_dsh_t *dsh, int kind, void **obj, size_t *size)
456 {
457 lws_dsh_obj_t *_obj = (lws_dsh_obj_t *)
458 lws_dll2_get_head(&dsh->oha[kind + 1].owner);
459
460 if (!_obj) {
461 *obj = 0;
462 *size = 0;
463
464 return 1; /* there is no head */
465 }
466
467 *obj = (void *)(&_obj[1]);
468 *size = _obj->size;
469
470 /* anything coming out of here must be aligned */
471 assert(!(((unsigned long)(*obj)) & (sizeof(int *) - 1)));
472
473 return 0; /* we returned the head */
474 }
475
476 #if defined(_DEBUG)
477
478 static int
describe_kind(struct lws_dll2 * d,void * user)479 describe_kind(struct lws_dll2 *d, void *user)
480 {
481 lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
482
483 lwsl_info(" _obj %p - %p, dsh %p, size %zu, asize %zu\n",
484 obj, (uint8_t *)obj + obj->asize,
485 obj->dsh, obj->size, obj->asize);
486
487 return 0;
488 }
489
490 void
lws_dsh_describe(lws_dsh_t * dsh,const char * desc)491 lws_dsh_describe(lws_dsh_t *dsh, const char *desc)
492 {
493 int n = 0;
494
495 lwsl_info("%s: dsh %p, bufsize %zu, kinds %d, lf: %zu, liu: %zu, %s\n",
496 __func__, dsh, dsh->buffer_size, dsh->count_kinds,
497 dsh->locally_free, dsh->locally_in_use, desc);
498
499 for (n = 0; n < dsh->count_kinds; n++) {
500 lwsl_info(" Kind %d:\n", n);
501 lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, describe_kind);
502 }
503 }
504 #endif
505