mirror of
https://github.com/warmcat/libwebsockets.git
synced 2025-03-16 00:00:07 +01:00
501 lines
12 KiB
C
501 lines
12 KiB
C
/*
|
|
* libwebsockets - small server side websockets and web server implementation
|
|
*
|
|
* Copyright (C) 2010-2019 Andy Green <andy@warmcat.com>
|
|
*
|
|
* This library is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU Lesser General Public
|
|
* License as published by the Free Software Foundation:
|
|
* version 2.1 of the License.
|
|
*
|
|
* This library is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
* Lesser General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU Lesser General Public
|
|
* License along with this library; if not, write to the Free Software
|
|
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
|
|
* MA 02110-1301 USA
|
|
*/
|
|
|
|
#include "core/private.h"
|
|
|
|
struct lws_dsh_search {
|
|
size_t required;
|
|
int kind;
|
|
lws_dsh_obj_t *best;
|
|
lws_dsh_t *dsh;
|
|
|
|
lws_dsh_t *already_checked;
|
|
lws_dsh_t *this_dsh;
|
|
};
|
|
|
|
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);
|
|
|
|
static size_t
|
|
lws_dsh_align(size_t length)
|
|
{
|
|
size_t align = sizeof(int *);
|
|
|
|
if (length & (align - 1))
|
|
length += align - (length & (align - 1));
|
|
|
|
return length;
|
|
}
|
|
|
|
lws_dsh_t *
|
|
lws_dsh_create(lws_dll2_owner_t *owner, size_t buf_len, int count_kinds)
|
|
{
|
|
size_t oha_len = sizeof(lws_dsh_obj_head_t) * ++count_kinds;
|
|
lws_dsh_obj_t *obj;
|
|
lws_dsh_t *dsh;
|
|
int n;
|
|
|
|
assert(buf_len);
|
|
assert(count_kinds > 1);
|
|
|
|
dsh = lws_malloc(sizeof(lws_dsh_t) + buf_len + oha_len, __func__);
|
|
if (!dsh)
|
|
return NULL;
|
|
|
|
/* set convenience pointers to the overallocated parts */
|
|
|
|
dsh->oha = (lws_dsh_obj_head_t *)&dsh[1];
|
|
dsh->buf = ((uint8_t *)dsh->oha) + oha_len;
|
|
dsh->count_kinds = count_kinds;
|
|
dsh->buffer_size = buf_len;
|
|
dsh->being_destroyed = 0;
|
|
|
|
/* clear down the obj heads array */
|
|
|
|
memset(dsh->oha, 0, oha_len);
|
|
for (n = 0; n < count_kinds; n++)
|
|
dsh->oha[n].kind = n;
|
|
|
|
/* initially the whole buffer is on the free kind (0) list */
|
|
|
|
obj = (lws_dsh_obj_t *)dsh->buf;
|
|
memset(obj, 0, sizeof(*obj));
|
|
obj->asize = buf_len - sizeof(*obj);
|
|
|
|
lws_dll2_add_head(&obj->list, &dsh->oha[0].owner);
|
|
|
|
dsh->locally_free = obj->asize;
|
|
dsh->locally_in_use = 0;
|
|
|
|
lws_dll2_clear(&dsh->list);
|
|
if (owner)
|
|
lws_dll2_add_head(&dsh->list, owner);
|
|
|
|
// lws_dsh_describe(dsh, "post-init");
|
|
|
|
return dsh;
|
|
}
|
|
|
|
static int
|
|
search_best_free(struct lws_dll2 *d, void *user)
|
|
{
|
|
struct lws_dsh_search *s = (struct lws_dsh_search *)user;
|
|
lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
|
|
|
|
lwsl_debug("%s: obj %p, asize %zu (req %zu)\n", __func__, obj,
|
|
obj->asize, s->required);
|
|
|
|
if (obj->asize >= s->required &&
|
|
(!s->best || obj->asize < s->best->asize)) {
|
|
s->best = obj;
|
|
s->dsh = s->this_dsh;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
static int
|
|
try_foreign(struct lws_dll2 *d, void *user)
|
|
{
|
|
struct lws_dsh_search *s = (struct lws_dsh_search *)user;
|
|
lws_dsh_t *dsh1 = lws_container_of(d, lws_dsh_t, list);
|
|
|
|
if (dsh1 == s->already_checked)
|
|
return 0;
|
|
|
|
if (dsh1->being_destroyed)
|
|
return 0;
|
|
|
|
if (dsh1->count_kinds < s->kind + 1)
|
|
return 0;
|
|
|
|
lwsl_debug("%s: actual try_foreign: dsh %p (free list size %d)\n",
|
|
__func__, dsh1, dsh1->oha[0].owner.count);
|
|
|
|
s->this_dsh = dsh1;
|
|
if (lws_dll2_foreach_safe(&dsh1->oha[0].owner, s, search_best_free))
|
|
return 1;
|
|
|
|
return 0;
|
|
}
|
|
|
|
static int
|
|
free_foreign(struct lws_dll2 *d, void *user)
|
|
{
|
|
lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
|
|
lws_dsh_t *dsh = (lws_dsh_t *)user;
|
|
void *p = (void *)&obj[1];
|
|
|
|
if (obj->dsh != dsh)
|
|
lws_dsh_free(&p);
|
|
|
|
return 0;
|
|
}
|
|
|
|
static int
|
|
evict2(struct lws_dll2 *d, void *user)
|
|
{
|
|
lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
|
|
lws_dsh_t *dsh = (lws_dsh_t *)user;
|
|
void *p;
|
|
|
|
if (obj->dsh != dsh)
|
|
return 0;
|
|
|
|
/*
|
|
* If we are here, it means obj is a live object that is allocated on
|
|
* the dsh being destroyed, from a different dsh. We need to migrate
|
|
* the object to a dsh that isn't being destroyed.
|
|
*/
|
|
|
|
lwsl_debug("%s: migrating object size %zu\n", __func__, obj->size);
|
|
|
|
if (_lws_dsh_alloc_tail(dsh, 0, (void *)&obj[1], obj->size, NULL, 0, &obj->list)) {
|
|
lwsl_notice("%s: failed to migrate object\n", __func__);
|
|
/*
|
|
* only thing we can do is drop the logical object
|
|
*/
|
|
p = (uint8_t *)&obj[1];
|
|
lws_dsh_free(&p);
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
static int
|
|
evict1(struct lws_dll2 *d, void *user)
|
|
{
|
|
lws_dsh_t *dsh1 = lws_container_of(d, lws_dsh_t, list);
|
|
lws_dsh_t *dsh = (lws_dsh_t *)user;
|
|
int n;
|
|
|
|
if (dsh1->being_destroyed)
|
|
return 0;
|
|
|
|
/*
|
|
* For every dsh that's not being destroyed, send every object to
|
|
* evict2 for checking.
|
|
*/
|
|
|
|
lwsl_debug("%s: checking dsh %p\n", __func__, dsh1);
|
|
|
|
for (n = 1; n < dsh1->count_kinds; n++) {
|
|
lws_dll2_describe(&dsh1->oha[n].owner, "check dsh1");
|
|
lws_dll2_foreach_safe(&dsh1->oha[n].owner, dsh, evict2);
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
void
|
|
lws_dsh_destroy(lws_dsh_t **pdsh)
|
|
{
|
|
lws_dsh_t *dsh = *pdsh;
|
|
int n;
|
|
|
|
if (!dsh)
|
|
return;
|
|
|
|
lwsl_debug("%s: destroying dsh %p\n", __func__, dsh);
|
|
|
|
dsh->being_destroyed = 1;
|
|
|
|
/* we need to explicitly free any of our allocations in foreign dsh */
|
|
|
|
for (n = 1; n < dsh->count_kinds; n++)
|
|
lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, free_foreign);
|
|
|
|
/*
|
|
* We need to have anybody else with allocations in us evict them
|
|
* and make a copy in a buffer that isn't being destroyed
|
|
*/
|
|
|
|
if (dsh->list.owner)
|
|
lws_dll2_foreach_safe(dsh->list.owner, dsh, evict1);
|
|
|
|
lws_dll2_remove(&dsh->list);
|
|
|
|
/* everything else is in one heap allocation */
|
|
|
|
lws_free_set_NULL(*pdsh);
|
|
}
|
|
|
|
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)
|
|
{
|
|
size_t asize = sizeof(lws_dsh_obj_t) + lws_dsh_align(size1 + size2);
|
|
struct lws_dsh_search s;
|
|
|
|
assert(kind >= 0);
|
|
kind++;
|
|
assert(!dsh || kind < dsh->count_kinds);
|
|
|
|
/*
|
|
* Search our free list looking for the smallest guy who will fit
|
|
* what we want to allocate
|
|
*/
|
|
s.required = asize;
|
|
s.kind = kind;
|
|
s.best = NULL;
|
|
s.already_checked = NULL;
|
|
s.this_dsh = dsh;
|
|
|
|
if (dsh && !dsh->being_destroyed)
|
|
lws_dll2_foreach_safe(&dsh->oha[0].owner, &s, search_best_free);
|
|
|
|
if (!s.best) {
|
|
/*
|
|
* Let's see if any other buffer has room
|
|
*/
|
|
s.already_checked = dsh;
|
|
|
|
if (dsh && dsh->list.owner)
|
|
lws_dll2_foreach_safe(dsh->list.owner, &s, try_foreign);
|
|
|
|
if (!s.best) {
|
|
lwsl_notice("%s: no buffer has space\n", __func__);
|
|
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
/* anything coming out of here must be aligned */
|
|
assert(!(((unsigned long)s.best) & (sizeof(int *) - 1)));
|
|
|
|
if (s.best->asize < asize + (2 * sizeof(*s.best))) {
|
|
/*
|
|
* Exact fit, or close enough we can't / don't want to have to
|
|
* track the little bit of free area that would be left.
|
|
*
|
|
* Move the object from the free list to the oha of the
|
|
* desired kind
|
|
*/
|
|
lws_dll2_remove(&s.best->list);
|
|
s.best->dsh = s.dsh;
|
|
s.best->size = size1 + size2;
|
|
memcpy(&s.best[1], src1, size1);
|
|
if (src2)
|
|
memcpy((uint8_t *)&s.best[1] + size1, src2, size2);
|
|
|
|
if (replace) {
|
|
s.best->list.prev = replace->prev;
|
|
s.best->list.next = replace->next;
|
|
s.best->list.owner = replace->owner;
|
|
if (replace->prev)
|
|
replace->prev->next = &s.best->list;
|
|
if (replace->next)
|
|
replace->next->prev = &s.best->list;
|
|
} else
|
|
if (dsh)
|
|
lws_dll2_add_tail(&s.best->list, &dsh->oha[kind].owner);
|
|
|
|
assert(s.dsh->locally_free >= s.best->asize);
|
|
s.dsh->locally_free -= s.best->asize;
|
|
s.dsh->locally_in_use += s.best->asize;
|
|
assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
|
|
} else {
|
|
lws_dsh_obj_t *obj;
|
|
|
|
/*
|
|
* Free area was oversize enough that we need to split it.
|
|
*
|
|
* Leave the first part of the free area where it is and
|
|
* reduce its extent by our asize. Use the latter part of
|
|
* the original free area as the allocation.
|
|
*/
|
|
lwsl_debug("%s: splitting... free reduce %zu -> %zu\n",
|
|
__func__, s.best->asize, s.best->asize - asize);
|
|
|
|
s.best->asize -= asize;
|
|
|
|
/* latter part becomes new object */
|
|
|
|
obj = (lws_dsh_obj_t *)(((uint8_t *)s.best) + s.best->asize);
|
|
|
|
lws_dll2_clear(&obj->list);
|
|
obj->dsh = s.dsh;
|
|
obj->size = size1 + size2;
|
|
obj->asize = asize;
|
|
|
|
memcpy(&obj[1], src1, size1);
|
|
if (src2)
|
|
memcpy((uint8_t *)&obj[1] + size1, src2, size2);
|
|
|
|
if (replace) {
|
|
s.best->list.prev = replace->prev;
|
|
s.best->list.next = replace->next;
|
|
s.best->list.owner = replace->owner;
|
|
if (replace->prev)
|
|
replace->prev->next = &s.best->list;
|
|
if (replace->next)
|
|
replace->next->prev = &s.best->list;
|
|
} else
|
|
if (dsh)
|
|
lws_dll2_add_tail(&obj->list, &dsh->oha[kind].owner);
|
|
|
|
assert(s.dsh->locally_free >= asize);
|
|
s.dsh->locally_free -= asize;
|
|
s.dsh->locally_in_use += asize;
|
|
assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
|
|
}
|
|
|
|
// lws_dsh_describe(dsh, "post-alloc");
|
|
|
|
return 0;
|
|
}
|
|
|
|
int
|
|
lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
|
|
const void *src2, size_t size2)
|
|
{
|
|
return _lws_dsh_alloc_tail(dsh, kind, src1, size1, src2, size2, NULL);
|
|
}
|
|
|
|
static int
|
|
buf_compare(const lws_dll2_t *d, const lws_dll2_t *i)
|
|
{
|
|
return (int)lws_ptr_diff(d, i);
|
|
}
|
|
|
|
void
|
|
lws_dsh_free(void **pobj)
|
|
{
|
|
lws_dsh_obj_t *_o = (lws_dsh_obj_t *)((uint8_t *)(*pobj) - sizeof(*_o)),
|
|
*_o2;
|
|
lws_dsh_t *dsh = _o->dsh;
|
|
|
|
/* anything coming out of here must be aligned */
|
|
assert(!(((unsigned long)_o) & (sizeof(int *) - 1)));
|
|
|
|
/*
|
|
* Remove the object from its list and place on the free list of the
|
|
* dsh the buffer space belongs to
|
|
*/
|
|
|
|
lws_dll2_remove(&_o->list);
|
|
*pobj = NULL;
|
|
|
|
assert(dsh->locally_in_use >= _o->asize);
|
|
dsh->locally_free += _o->asize;
|
|
dsh->locally_in_use -= _o->asize;
|
|
assert(dsh->locally_in_use <= dsh->buffer_size);
|
|
|
|
/*
|
|
* The free space list is sorted in buffer address order, so detecting
|
|
* coalescing opportunities is cheap. Because the free list should be
|
|
* continuously tending to reduce by coalescing, the sorting should not
|
|
* be expensive to maintain.
|
|
*/
|
|
_o->size = 0; /* not meaningful when on free list */
|
|
lws_dll2_add_sorted(&_o->list, &_o->dsh->oha[0].owner, buf_compare);
|
|
|
|
/* First check for already-free block at the end we can subsume.
|
|
* Because the free list is sorted, if there is such a guy he is
|
|
* already our list.next */
|
|
|
|
_o2 = (lws_dsh_obj_t *)_o->list.next;
|
|
if (_o2 && (uint8_t *)_o + _o->asize == (uint8_t *)_o2) {
|
|
/*
|
|
* since we are freeing _obj, we can coalesce with a
|
|
* free area immediately ahead of it
|
|
*
|
|
* [ _o (being freed) ][ _o2 (free) ] -> [ larger _o ]
|
|
*/
|
|
_o->asize += _o2->asize;
|
|
|
|
/* guy next to us was absorbed into us */
|
|
lws_dll2_remove(&_o2->list);
|
|
}
|
|
|
|
/* Then check if we can be subsumed by a free block behind us.
|
|
* Because the free list is sorted, if there is such a guy he is
|
|
* already our list.prev */
|
|
|
|
_o2 = (lws_dsh_obj_t *)_o->list.prev;
|
|
if (_o2 && (uint8_t *)_o2 + _o2->asize == (uint8_t *)_o) {
|
|
/*
|
|
* since we are freeing obj, we can coalesce it with
|
|
* the previous free area that abuts it
|
|
*
|
|
* [ _o2 (free) ][ _o (being freed) ] -> [ larger _o2 ]
|
|
*/
|
|
_o2->asize += _o->asize;
|
|
|
|
/* we were absorbed! */
|
|
lws_dll2_remove(&_o->list);
|
|
}
|
|
|
|
// lws_dsh_describe(dsh, "post-alloc");
|
|
}
|
|
|
|
int
|
|
lws_dsh_get_head(lws_dsh_t *dsh, int kind, void **obj, size_t *size)
|
|
{
|
|
lws_dsh_obj_t *_obj = (lws_dsh_obj_t *)
|
|
lws_dll2_get_head(&dsh->oha[kind + 1].owner);
|
|
|
|
if (!_obj) {
|
|
*obj = 0;
|
|
*size = 0;
|
|
|
|
return 1; /* there is no head */
|
|
}
|
|
|
|
*obj = (void *)(&_obj[1]);
|
|
*size = _obj->size;
|
|
|
|
/* anything coming out of here must be aligned */
|
|
assert(!(((unsigned long)(*obj)) & (sizeof(int *) - 1)));
|
|
|
|
return 0; /* we returned the head */
|
|
}
|
|
|
|
#if defined(_DEBUG)
|
|
|
|
static int
|
|
describe_kind(struct lws_dll2 *d, void *user)
|
|
{
|
|
lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
|
|
|
|
lwsl_info(" _obj %p - %p, dsh %p, size %zu, asize %zu\n",
|
|
obj, (uint8_t *)obj + obj->asize,
|
|
obj->dsh, obj->size, obj->asize);
|
|
|
|
return 0;
|
|
}
|
|
|
|
void
|
|
lws_dsh_describe(lws_dsh_t *dsh, const char *desc)
|
|
{
|
|
int n = 0;
|
|
|
|
lwsl_info("%s: dsh %p, bufsize %zu, kinds %d, lf: %zu, liu: %zu, %s\n",
|
|
__func__, dsh, dsh->buffer_size, dsh->count_kinds,
|
|
dsh->locally_free, dsh->locally_in_use, desc);
|
|
|
|
for (n = 0; n < dsh->count_kinds; n++) {
|
|
lwsl_info(" Kind %d:\n", n);
|
|
lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, describe_kind);
|
|
}
|
|
}
|
|
#endif
|