/src/libwebsockets/lib/misc/lwsac/lwsac.c

Source
/*
 * libwebsockets - small server side websockets and web server implementation
 *
 * Copyright (C) 2010 - 2025 Andy Green <andy@warmcat.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */

#include "private-lib-core.h"
#include "private-lib-misc-lwsac.h"

void
lws_list_ptr_insert(lws_list_ptr *head, lws_list_ptr *add,
        lws_list_ptr_sort_func_t sort_func)
{
  while (sort_func && *head) {
    if (sort_func(add, *head) <= 0)
      break;

    head = *head;
  }

  *add = *head;
  *head = add;
}

size_t
lwsac_align(size_t length)
{
  size_t align = sizeof(int *);

  if (length & (align - 1))
    length += align - (length & (align - 1));

  return length;
}

size_t
lwsac_sizeof(int first)
{
  return sizeof(struct lwsac) + (first ? sizeof(struct lwsac_head) : 0);
}

size_t
lwsac_get_tail_pos(struct lwsac *lac)
{
  return lac->ofs;
}

struct lwsac *
lwsac_get_next(struct lwsac *lac)
{
  return lac->next;
}

int
lwsac_extend(struct lwsac *head, size_t amount)
{
  struct lwsac_head *lachead;
  struct lwsac *bf;

  assert(head);
  lachead = (struct lwsac_head *)&head[1];

  bf = lachead->curr;
  assert(bf);

  if (bf->alloc_size - bf->ofs < lwsac_align(amount))
    return 1;

  /* memset so constant folding never sees uninitialized data */

  memset(((uint8_t *)bf) + bf->ofs, 0, lwsac_align(amount));
  bf->ofs += lwsac_align(amount);

  return 0;
}

static void *
_lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size, char backfill)
{
  struct lwsac_head *lachead = NULL;
  size_t ofs, alloc, al, hp;
  struct lwsac *bf = *head;

  if (bf)
    lachead = (struct lwsac_head *)&bf[1];

  al = lwsac_align(ensure);

  /* backfill into earlier chunks if that is allowed */

  if (backfill)
    /*
     * check if anything can take it, from the start
     */
    while (bf) {
      if (bf->alloc_size - bf->ofs >= ensure)
        goto do_use;

      bf = bf->next;
    }
  else {
    /*
     * If there's a current chunk, just check if he can take it
     */
    if (lachead && lachead->curr) {
      bf = lachead->curr;
      if (bf->alloc_size - bf->ofs >= ensure)
        goto do_use;
    }
  }

  /* nothing can currently take it... so we must allocate */

  hp = sizeof(*bf); /* always need the normal header part... */
  if (!*head)
    hp += sizeof(struct lwsac_head);

  if (!chunk_size)
    alloc = LWSAC_CHUNK_SIZE + hp;
  else
    alloc = chunk_size + hp;

  /*
   * If we get asked for something outside our expectation,
   * increase the allocation to meet it
   */

  if (al >= alloc - hp)
    alloc = al + hp;

//  lwsl_debug("%s: alloc %d for %d\n", __func__, (int)alloc, (int)ensure);
  bf = malloc(alloc);
  if (!bf) {
    lwsl_err("%s: OOM trying to alloc %llud\n", __func__,
        (unsigned long long)alloc);
    return NULL;
  }

  /*
   * belabouring the point... ofs is aligned to the platform's
   * generic struct alignment at the start then
   */
  bf->ofs = sizeof(*bf);

  if (!*head) {
    /*
     * We are the first, head, entry...
     */
    *head = bf;
    /*
     * ... allocate for the special head block
     */
    bf->ofs += sizeof(*lachead);
    lachead = (struct lwsac_head *)&bf[1];
    memset(lachead, 0, sizeof(*lachead));
  } else
    if (lachead->curr)
      lachead->curr->next = bf;

  lachead->curr = bf;
  bf->head = *head;
  bf->next = NULL;
  bf->alloc_size = alloc;

  lachead->total_alloc_size += alloc;
  lachead->total_blocks++;

do_use:

  ofs = bf->ofs;

  if (al > ensure)
    /* zero down the alignment padding part */
    memset((char *)bf + ofs + ensure, 0, al - ensure);

  bf->ofs += al;
  if (bf->ofs >= bf->alloc_size)
    bf->ofs = bf->alloc_size;

  return (char *)bf + ofs;
}

void *
lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size)
{
  return _lwsac_use(head, ensure, chunk_size, 0);
}

void *
lwsac_use_backfill(struct lwsac **head, size_t ensure, size_t chunk_size)
{
  return _lwsac_use(head, ensure, chunk_size, 1);
}

uint8_t *
lwsac_scan_extant(struct lwsac *head, uint8_t *find, size_t len, int nul)
{
  while (head) {
    uint8_t *pos = (uint8_t *)&head[1],
      *end = ((uint8_t *)head) + head->ofs - len;

    if (head->ofs - sizeof(*head) >= len)
      while (pos < end) {
        if (*pos == *find && (!nul || !pos[len]) &&
            pos[len - 1] == find[len - 1] &&
            !memcmp(pos, find, len))
          /* found the blob */
          return pos;
        pos++;
      }

    head = head->next;
  }

  return NULL;
}

uint64_t
lwsac_total_overhead(struct lwsac *head)
{
  uint64_t overhead = 0;

  while (head) {
    overhead += (head->alloc_size - head->ofs) + sizeof(*head);

    head = head->next;
  }

  return overhead;
}

void *
lwsac_use_zero(struct lwsac **head, size_t ensure, size_t chunk_size)
{
  void *p = lwsac_use(head, ensure, chunk_size);

  if (p)
    memset(p, 0, ensure);

  return p;
}

void
lwsac_free(struct lwsac **head)
{
  struct lwsac *it = *head;

  *head = NULL;
  // lwsl_debug("%s: head %p\n", __func__, *head);

  while (it) {
    struct lwsac *tmp = it->next;

    free(it);
    it = tmp;
  }
}

void
lwsac_info(struct lwsac *head)
{
#if _LWS_ENABLED_LOGS & LLL_DEBUG
  struct lwsac_head *lachead;

  if (!head) {
    lwsl_debug("%s: empty\n", __func__);
    return;
  }

  lachead = (struct lwsac_head *)&head[1];

  lwsl_debug("%s: lac %p: %dKiB in %d blocks\n", __func__, head,
       (int)(lachead->total_alloc_size >> 10), lachead->total_blocks);
#endif
}

uint64_t
lwsac_total_alloc(struct lwsac *head)
{
  struct lwsac_head *lachead;

  if (!head)
    return 0;

  lachead = (struct lwsac_head *)&head[1];
  return lachead->total_alloc_size;
}

void
lwsac_reference(struct lwsac *head)
{
  struct lwsac_head *lachead = (struct lwsac_head *)&head[1];

  lachead->refcount++;
  lwsl_debug("%s: head %p: (det %d) refcount -> %d\n",
        __func__, head, lachead->detached, lachead->refcount);
}

void
lwsac_unreference(struct lwsac **head)
{
  struct lwsac_head *lachead;

  if (!(*head))
    return;

  lachead = (struct lwsac_head *)&(*head)[1];

  if (!lachead->refcount)
    lwsl_warn("%s: refcount going below zero\n", __func__);

  lachead->refcount--;

  lwsl_debug("%s: head %p: (det %d) refcount -> %d\n",
        __func__, *head, lachead->detached, lachead->refcount);

  if (lachead->detached && !lachead->refcount) {
    lwsl_debug("%s: head %p: FREED\n", __func__, *head);
    lwsac_free(head);
  }
}

void
lwsac_detach(struct lwsac **head)
{
  struct lwsac_head *lachead;

  if (!(*head))
    return;

  lachead = (struct lwsac_head *)&(*head)[1];

  lachead->detached = 1;
  if (!lachead->refcount) {
    lwsl_debug("%s: head %p: FREED\n", __func__, *head);
    lwsac_free(head);
  } else
    lwsl_debug("%s: head %p: refcount %d: Marked as detached\n",
          __func__, *head, lachead->refcount);
}

int
_lwsac_assert_valid(struct lwsac *aco, void *check, size_t len, const char *name_ac, const char *name_blob,
        const char *filename, int line)
{
  struct lwsac *ac = aco;

  while (ac) {
    void *pos = (uint8_t *)&ac[1],
         *end = ((uint8_t *)ac) + ac->ofs;

    if (check >= pos && (void *)(((uint8_t *)check) + len) <= end)
      return 0;

    ac = ac->next;
  }

#if !defined(LWS_WITH_NO_LOGS) && (_LWS_ENABLED_LOGS & LLL_NOTICE)
  ac = aco;

  while (ac) {
    void *pos = (uint8_t *)&ac[1],
         *end = ((uint8_t *)ac) + ac->ofs;

    lwsl_notice("%s: ac chunk  %p -> %p\n", __func__, pos, end);

    ac = ac->next;
  }
#endif

  lwsl_err("%s:%d:  %s (%p) len %u is not found inside lwsac %s (%p)\n", filename, line, name_blob, check, (unsigned int)len, name_ac, aco);
  assert(0); /* checked ptr is not in ac */

  return 1;
}


Coverage Report

Created: 2025-12-10 06:58

Line	Count	Source
1		/*
2		* libwebsockets - small server side websockets and web server implementation
3		*
4		* Copyright (C) 2010 - 2025 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		#include "private-lib-misc-lwsac.h"
27
28		void
29		lws_list_ptr_insert(lws_list_ptr head, lws_list_ptr add,
30		lws_list_ptr_sort_func_t sort_func)
31	0	{
32	0	while (sort_func && *head) {
33	0	if (sort_func(add, *head) <= 0)
34	0	break;
35
36	0	head = *head;
37	0	}
38
39	0	add = head;
40	0	*head = add;
41	0	}
42
43		size_t
44		lwsac_align(size_t length)
45	0	{
46	0	size_t align = sizeof(int *);
47
48	0	if (length & (align - 1))
49	0	length += align - (length & (align - 1));
50
51	0	return length;
52	0	}
53
54		size_t
55		lwsac_sizeof(int first)
56	0	{
57	0	return sizeof(struct lwsac) + (first ? sizeof(struct lwsac_head) : 0);
58	0	}
59
60		size_t
61		lwsac_get_tail_pos(struct lwsac *lac)
62	0	{
63	0	return lac->ofs;
64	0	}
65
66		struct lwsac *
67		lwsac_get_next(struct lwsac *lac)
68	0	{
69	0	return lac->next;
70	0	}
71
72		int
73		lwsac_extend(struct lwsac *head, size_t amount)
74	0	{
75	0	struct lwsac_head *lachead;
76	0	struct lwsac *bf;
77
78	0	assert(head);
79	0	lachead = (struct lwsac_head *)&head[1];
80
81	0	bf = lachead->curr;
82	0	assert(bf);
83
84	0	if (bf->alloc_size - bf->ofs < lwsac_align(amount))
85	0	return 1;
86
87		/* memset so constant folding never sees uninitialized data */
88
89	0	memset(((uint8_t *)bf) + bf->ofs, 0, lwsac_align(amount));
90	0	bf->ofs += lwsac_align(amount);
91
92	0	return 0;
93	0	}
94
95		static void *
96		_lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size, char backfill)
97	0	{
98	0	struct lwsac_head *lachead = NULL;
99	0	size_t ofs, alloc, al, hp;
100	0	struct lwsac bf = head;
101
102	0	if (bf)
103	0	lachead = (struct lwsac_head *)&bf[1];
104
105	0	al = lwsac_align(ensure);
106
107		/* backfill into earlier chunks if that is allowed */
108
109	0	if (backfill)
110		/*
111		* check if anything can take it, from the start
112		*/
113	0	while (bf) {
114	0	if (bf->alloc_size - bf->ofs >= ensure)
115	0	goto do_use;
116
117	0	bf = bf->next;
118	0	}
119	0	else {
120		/*
121		* If there's a current chunk, just check if he can take it
122		*/
123	0	if (lachead && lachead->curr) {
124	0	bf = lachead->curr;
125	0	if (bf->alloc_size - bf->ofs >= ensure)
126	0	goto do_use;
127	0	}
128	0	}
129
130		/* nothing can currently take it... so we must allocate */
131
132	0	hp = sizeof(bf); / always need the normal header part... */
133	0	if (!*head)
134	0	hp += sizeof(struct lwsac_head);
135
136	0	if (!chunk_size)
137	0	alloc = LWSAC_CHUNK_SIZE + hp;
138	0	else
139	0	alloc = chunk_size + hp;
140
141		/*
142		* If we get asked for something outside our expectation,
143		* increase the allocation to meet it
144		*/
145
146	0	if (al >= alloc - hp)
147	0	alloc = al + hp;
148
149		// lwsl_debug("%s: alloc %d for %d\n", __func__, (int)alloc, (int)ensure);
150	0	bf = malloc(alloc);
151	0	if (!bf) {
152	0	lwsl_err("%s: OOM trying to alloc %llud\n", __func__,
153	0	(unsigned long long)alloc);
154	0	return NULL;
155	0	}
156
157		/*
158		* belabouring the point... ofs is aligned to the platform's
159		* generic struct alignment at the start then
160		*/
161	0	bf->ofs = sizeof(*bf);
162
163	0	if (!*head) {
164		/*
165		* We are the first, head, entry...
166		*/
167	0	*head = bf;
168		/*
169		* ... allocate for the special head block
170		*/
171	0	bf->ofs += sizeof(*lachead);
172	0	lachead = (struct lwsac_head *)&bf[1];
173	0	memset(lachead, 0, sizeof(*lachead));
174	0	} else
175	0	if (lachead->curr)
176	0	lachead->curr->next = bf;
177
178	0	lachead->curr = bf;
179	0	bf->head = *head;
180	0	bf->next = NULL;
181	0	bf->alloc_size = alloc;
182
183	0	lachead->total_alloc_size += alloc;
184	0	lachead->total_blocks++;
185
186	0	do_use:
187
188	0	ofs = bf->ofs;
189
190	0	if (al > ensure)
191		/* zero down the alignment padding part */
192	0	memset((char *)bf + ofs + ensure, 0, al - ensure);
193
194	0	bf->ofs += al;
195	0	if (bf->ofs >= bf->alloc_size)
196	0	bf->ofs = bf->alloc_size;
197
198	0	return (char *)bf + ofs;
199	0	}
200
201		void *
202		lwsac_use(struct lwsac **head, size_t ensure, size_t chunk_size)
203	0	{
204	0	return _lwsac_use(head, ensure, chunk_size, 0);
205	0	}
206
207		void *
208		lwsac_use_backfill(struct lwsac **head, size_t ensure, size_t chunk_size)
209	0	{
210	0	return _lwsac_use(head, ensure, chunk_size, 1);
211	0	}
212
213		uint8_t *
214		lwsac_scan_extant(struct lwsac head, uint8_t find, size_t len, int nul)
215	0	{
216	0	while (head) {
217	0	uint8_t pos = (uint8_t )&head[1],
218	0	end = ((uint8_t )head) + head->ofs - len;
219
220	0	if (head->ofs - sizeof(*head) >= len)
221	0	while (pos < end) {
222	0	if (pos == find && (!nul \|\| !pos[len]) &&
223	0	pos[len - 1] == find[len - 1] &&
224	0	!memcmp(pos, find, len))
225		/* found the blob */
226	0	return pos;
227	0	pos++;
228	0	}
229
230	0	head = head->next;
231	0	}
232
233	0	return NULL;
234	0	}
235
236		uint64_t
237		lwsac_total_overhead(struct lwsac *head)
238	0	{
239	0	uint64_t overhead = 0;
240
241	0	while (head) {
242	0	overhead += (head->alloc_size - head->ofs) + sizeof(*head);
243
244	0	head = head->next;
245	0	}
246
247	0	return overhead;
248	0	}
249
250		void *
251		lwsac_use_zero(struct lwsac **head, size_t ensure, size_t chunk_size)
252	0	{
253	0	void *p = lwsac_use(head, ensure, chunk_size);
254
255	0	if (p)
256	0	memset(p, 0, ensure);
257
258	0	return p;
259	0	}
260
261		void
262		lwsac_free(struct lwsac **head)
263	0	{
264	0	struct lwsac it = head;
265
266	0	*head = NULL;
267		// lwsl_debug("%s: head %p\n", __func__, *head);
268
269	0	while (it) {
270	0	struct lwsac *tmp = it->next;
271
272	0	free(it);
273	0	it = tmp;
274	0	}
275	0	}
276
277		void
278		lwsac_info(struct lwsac *head)
279	0	{
280	0	#if _LWS_ENABLED_LOGS & LLL_DEBUG
281	0	struct lwsac_head *lachead;
282
283	0	if (!head) {
284	0	lwsl_debug("%s: empty\n", __func__);
285	0	return;
286	0	}
287
288	0	lachead = (struct lwsac_head *)&head[1];
289
290	0	lwsl_debug("%s: lac %p: %dKiB in %d blocks\n", __func__, head,
291	0	(int)(lachead->total_alloc_size >> 10), lachead->total_blocks);
292	0	#endif
293	0	}
294
295		uint64_t
296		lwsac_total_alloc(struct lwsac *head)
297	0	{
298	0	struct lwsac_head *lachead;
299
300	0	if (!head)
301	0	return 0;
302
303	0	lachead = (struct lwsac_head *)&head[1];
304	0	return lachead->total_alloc_size;
305	0	}
306
307		void
308		lwsac_reference(struct lwsac *head)
309	0	{
310	0	struct lwsac_head lachead = (struct lwsac_head )&head[1];
311
312	0	lachead->refcount++;
313	0	lwsl_debug("%s: head %p: (det %d) refcount -> %d\n",
314	0	__func__, head, lachead->detached, lachead->refcount);
315	0	}
316
317		void
318		lwsac_unreference(struct lwsac **head)
319	0	{
320	0	struct lwsac_head *lachead;
321
322	0	if (!(*head))
323	0	return;
324
325	0	lachead = (struct lwsac_head )&(head)[1];
326
327	0	if (!lachead->refcount)
328	0	lwsl_warn("%s: refcount going below zero\n", __func__);
329
330	0	lachead->refcount--;
331
332	0	lwsl_debug("%s: head %p: (det %d) refcount -> %d\n",
333	0	__func__, *head, lachead->detached, lachead->refcount);
334
335	0	if (lachead->detached && !lachead->refcount) {
336	0	lwsl_debug("%s: head %p: FREED\n", __func__, *head);
337	0	lwsac_free(head);
338	0	}
339	0	}
340
341		void
342		lwsac_detach(struct lwsac **head)
343	0	{
344	0	struct lwsac_head *lachead;
345
346	0	if (!(*head))
347	0	return;
348
349	0	lachead = (struct lwsac_head )&(head)[1];
350
351	0	lachead->detached = 1;
352	0	if (!lachead->refcount) {
353	0	lwsl_debug("%s: head %p: FREED\n", __func__, *head);
354	0	lwsac_free(head);
355	0	} else
356	0	lwsl_debug("%s: head %p: refcount %d: Marked as detached\n",
357	0	__func__, *head, lachead->refcount);
358	0	}
359
360		int
361		_lwsac_assert_valid(struct lwsac aco, void check, size_t len, const char name_ac, const char name_blob,
362		const char *filename, int line)
363	0	{
364	0	struct lwsac *ac = aco;
365
366	0	while (ac) {
367	0	void pos = (uint8_t )&ac[1],
368	0	end = ((uint8_t )ac) + ac->ofs;
369
370	0	if (check >= pos && (void )(((uint8_t )check) + len) <= end)
371	0	return 0;
372
373	0	ac = ac->next;
374	0	}
375
376	0	#if !defined(LWS_WITH_NO_LOGS) && (_LWS_ENABLED_LOGS & LLL_NOTICE)
377	0	ac = aco;
378
379	0	while (ac) {
380	0	void pos = (uint8_t )&ac[1],
381	0	end = ((uint8_t )ac) + ac->ofs;
382
383	0	lwsl_notice("%s: ac chunk %p -> %p\n", __func__, pos, end);
384
385	0	ac = ac->next;
386	0	}
387	0	#endif
388
389	0	lwsl_err("%s:%d: %s (%p) len %u is not found inside lwsac %s (%p)\n", filename, line, name_blob, check, (unsigned int)len, name_ac, aco);
390	0	assert(0); /* checked ptr is not in ac */
391
392	0	return 1;
393	0	}
394