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
27struct lws_ring *
28lws_ring_create(size_t element_len, size_t count,
29		void (*destroy_element)(void *))
30{
31	struct lws_ring *ring = lws_malloc(sizeof(*ring), "ring create");
32
33	if (!ring)
34		return NULL;
35
36	ring->buflen = (uint32_t)(count * element_len);
37	ring->element_len = (uint32_t)element_len;
38	ring->head = 0;
39	ring->oldest_tail = 0;
40	ring->destroy_element = destroy_element;
41
42	ring->buf = lws_malloc(ring->buflen, "ring buf");
43	if (!ring->buf) {
44		lws_free(ring);
45
46		return NULL;
47	}
48
49	return ring;
50}
51
52void
53lws_ring_destroy(struct lws_ring *ring)
54{
55	if (ring->destroy_element)
56		while (ring->oldest_tail != ring->head) {
57			ring->destroy_element((uint8_t *)ring->buf +
58					      ring->oldest_tail);
59			ring->oldest_tail =
60				(ring->oldest_tail + ring->element_len) %
61				ring->buflen;
62		}
63	if (ring->buf)
64		lws_free_set_NULL(ring->buf);
65
66	lws_free(ring);
67}
68
69size_t
70lws_ring_get_count_free_elements(struct lws_ring *ring)
71{
72	int f;
73
74	/*
75	 * possible ringbuf patterns
76	 *
77	 * h == t
78	 * |--------t***h---|
79	 * |**h-----------t*|
80	 * |t**************h|
81	 * |*****ht*********|
82	 */
83	if (ring->head == ring->oldest_tail)
84		f = (int)(ring->buflen - ring->element_len);
85	else
86		if (ring->head < ring->oldest_tail)
87			f = (int)((ring->oldest_tail - ring->head) -
88			    ring->element_len);
89		else
90			f = (int)((ring->buflen - ring->head) + ring->oldest_tail -
91			    ring->element_len);
92
93	if (f < 2)
94		return 0;
95
96	return (unsigned int)f / ring->element_len;
97}
98
99size_t
100lws_ring_get_count_waiting_elements(struct lws_ring *ring, uint32_t *tail)
101{	int f;
102
103	if (!tail)
104		tail = &ring->oldest_tail;
105	/*
106	 * possible ringbuf patterns
107	 *
108	 * h == t
109	 * |--------t***h---|
110	 * |**h-----------t*|
111	 * |t**************h|
112	 * |*****ht*********|
113	 */
114	if (ring->head == *tail)
115		f = 0;
116	else
117		if (ring->head > *tail)
118			f = (int)(ring->head - *tail);
119		else
120			f = (int)((ring->buflen - *tail) + ring->head);
121
122	return (unsigned int)f / ring->element_len;
123}
124
125int
126lws_ring_next_linear_insert_range(struct lws_ring *ring, void **start,
127				  size_t *bytes)
128{
129	int n;
130
131	/* n is how many bytes the whole fifo can take */
132	n = (int)(lws_ring_get_count_free_elements(ring) * ring->element_len);
133
134	if (!n)
135		return 1;
136
137	if (ring->head + (unsigned int)n > ring->buflen) {
138		*start = (void *)(((uint8_t *)ring->buf) + ring->head);
139		*bytes = ring->buflen - ring->head;
140
141		return 0;
142	}
143
144	*start = (void *)(((uint8_t *)ring->buf) + ring->head);
145	*bytes = (unsigned int)n;
146
147	return 0;
148}
149
150void
151lws_ring_bump_head(struct lws_ring *ring, size_t bytes)
152{
153	ring->head = (ring->head + (uint32_t)bytes) % ring->buflen;
154}
155
156size_t
157lws_ring_insert(struct lws_ring *ring, const void *src, size_t max_count)
158{
159	const uint8_t *osrc = src;
160	size_t m;
161	int n;
162
163	/* n is how many bytes the whole fifo can take */
164	n = (int)(lws_ring_get_count_free_elements(ring) * ring->element_len);
165
166	/* restrict n to how much we want to insert */
167	if ((uint32_t)n > max_count * ring->element_len)
168		n = (int)(max_count * ring->element_len);
169
170	/*
171	 * n is legal to insert, but as an optimization we can cut the
172	 * insert into one or two memcpys, depending on if it wraps
173	 */
174	if (ring->head + (unsigned int)n > ring->buflen) {
175
176		/*
177		 * He does wrap.  The first memcpy should take us up to
178		 * the end of the buffer
179		 */
180
181		m = ring->buflen - ring->head;
182		memcpy(((uint8_t *)ring->buf) + ring->head, src, m);
183		/* we know it will wrap exactly back to zero */
184		ring->head = 0;
185
186		/* adapt the second memcpy for what we already did */
187
188		src = ((uint8_t *)src) + m;
189		n = n - (int)m;
190	}
191
192	memcpy(((uint8_t *)ring->buf) + ring->head, src, (size_t)n);
193	ring->head = (ring->head + (unsigned int)n) % ring->buflen;
194
195	return (unsigned long)(((uint8_t *)src + (unsigned int)n) - osrc) / ring->element_len;
196}
197
198size_t
199lws_ring_consume(struct lws_ring *ring, uint32_t *tail, void *dest,
200		 size_t max_count)
201{
202	uint8_t *odest = dest;
203	void *orig_tail = tail;
204	uint32_t fake_tail;
205	int m, n;
206
207	if (!tail) {
208		fake_tail = ring->oldest_tail;
209		tail = &fake_tail;
210	}
211
212	/* n is how many bytes the whole fifo has for us */
213	n = (int)(lws_ring_get_count_waiting_elements(ring, tail) *
214							ring->element_len);
215
216	/* restrict n to how much we want to insert */
217	if ((size_t)n > max_count * ring->element_len)
218		n = (int)(max_count * ring->element_len);
219
220	if (!dest) {
221		*tail = ((*tail) + (unsigned int)n) % ring->buflen;
222		if (!orig_tail) /* single tail */
223			lws_ring_update_oldest_tail(ring, *tail);
224
225		return (unsigned int)n / ring->element_len;
226	}
227	if (*tail + (unsigned int)n > ring->buflen) {
228
229		/*
230		 * He does wrap.  The first memcpy should take us up to
231		 * the end of the buffer
232		 */
233
234		m = (int32_t)(ring->buflen - *tail);
235		memcpy(dest, ((uint8_t *)ring->buf) + *tail, (size_t)m);
236		/* we know it will wrap exactly back to zero */
237		*tail = 0;
238
239		/* adapt the second memcpy for what we already did */
240
241		dest = ((uint8_t *)dest) + m;
242		n -= m;
243	}
244
245	memcpy(dest, ((uint8_t *)ring->buf) + *tail, (size_t)n);
246
247	*tail = ((*tail) + (unsigned int)n) % ring->buflen;
248	if (!orig_tail) /* single tail */
249		lws_ring_update_oldest_tail(ring, *tail);
250
251	return (unsigned int)(((uint8_t *)dest + n) - odest) / (unsigned int)ring->element_len;
252}
253
254const void *
255lws_ring_get_element(struct lws_ring *ring, uint32_t *tail)
256{
257	if (!tail)
258		tail = &ring->oldest_tail;
259
260	if (*tail == ring->head)
261		return NULL;
262
263	return ((uint8_t *)ring->buf) + *tail;
264}
265
266void
267lws_ring_update_oldest_tail(struct lws_ring *ring, uint32_t tail)
268{
269	if (!ring->destroy_element) {
270		ring->oldest_tail = tail;
271		return;
272	}
273
274	while (ring->oldest_tail != tail) {
275		ring->destroy_element((uint8_t *)ring->buf + ring->oldest_tail);
276		ring->oldest_tail = (ring->oldest_tail + ring->element_len) %
277				    ring->buflen;
278	}
279}
280
281uint32_t
282lws_ring_get_oldest_tail(struct lws_ring *ring)
283{
284	return ring->oldest_tail;
285}
286
287void
288lws_ring_dump(struct lws_ring *ring, uint32_t *tail)
289{
290	if (tail == NULL)
291		tail = &ring->oldest_tail;
292	lwsl_notice("ring %p: buflen %u, elem_len %u, head %u, oldest_tail %u\n"
293		    "     free_elems: %u; for tail %u, waiting elements: %u\n",
294		    ring, (int)ring->buflen, (int)ring->element_len,
295		    (int)ring->head, (int)ring->oldest_tail,
296		    (int)lws_ring_get_count_free_elements(ring), (int)*tail,
297		    (int)lws_ring_get_count_waiting_elements(ring, tail));
298}
299