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
27struct 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
37static 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
41static size_t
42lws_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
52lws_dsh_t *
53lws_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
105static int
106search_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
123void
124lws_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
140size_t
141lws_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
149static int
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
272int
273lws_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
279static int
280buf_compare(const lws_dll2_t *d, const lws_dll2_t *i)
281{
282	return (int)lws_ptr_diff(d, i);
283}
284
285void
286lws_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
357int
358lws_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
385static int
386describe_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
397void
398lws_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