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/** \defgroup lws_ring LWS Ringbuffer APIs
26 * ##lws_ring: generic ringbuffer struct
27 *
28 * Provides an abstract ringbuffer api supporting one head and one or an
29 * unlimited number of tails.
30 *
31 * All of the members are opaque and manipulated by lws_ring_...() apis.
32 *
33 * The lws_ring and its buffer is allocated at runtime on the heap, using
34 *
35 * - lws_ring_create()
36 * - lws_ring_destroy()
37 *
38 * It may contain any type, the size of the "element" stored in the ring
39 * buffer and the number of elements is given at creation time.
40 *
41 * When you create the ringbuffer, you can optionally provide an element
42 * destroy callback that frees any allocations inside the element. This is then
43 * automatically called for elements with no tail behind them, ie, elements
44 * which don't have any pending consumer are auto-freed.
45 *
46 * Whole elements may be inserted into the ringbuffer and removed from it, using
47 *
48 * - lws_ring_insert()
49 * - lws_ring_consume()
50 *
51 * You can find out how many whole elements are free or waiting using
52 *
53 * - lws_ring_get_count_free_elements()
54 * - lws_ring_get_count_waiting_elements()
55 *
56 * In addition there are special purpose optional byte-centric apis
57 *
58 * - lws_ring_next_linear_insert_range()
59 * - lws_ring_bump_head()
60 *
61 * which let you, eg, read() directly into the ringbuffer without needing
62 * an intermediate bounce buffer.
63 *
64 * The accessors understand that the ring wraps, and optimizes insertion and
65 * consumption into one or two memcpy()s depending on if the head or tail
66 * wraps.
67 *
68 * lws_ring only supports a single head, but optionally multiple tails with
69 * an API to inform it when the "oldest" tail has moved on. You can give
70 * NULL where-ever an api asks for a tail pointer, and it will use an internal
71 * single tail pointer for convenience.
72 *
73 * The "oldest tail", which is the only tail if you give it NULL instead of
74 * some other tail, is used to track which elements in the ringbuffer are
75 * still unread by anyone.
76 *
77 * - lws_ring_update_oldest_tail()
78 */
79///@{
80struct lws_ring;
81
82/**
83 * lws_ring_create(): create a new ringbuffer
84 *
85 * \param element_len: the size in bytes of one element in the ringbuffer
86 * \param count: the number of elements the ringbuffer can contain
87 * \param destroy_element: NULL, or callback to be called for each element
88 * that is removed from the ringbuffer due to the
89 * oldest tail moving beyond it
90 *
91 * Creates the ringbuffer and allocates the storage. Returns the new
92 * lws_ring *, or NULL if the allocation failed.
93 *
94 * If non-NULL, destroy_element will get called back for every element that is
95 * retired from the ringbuffer after the oldest tail has gone past it, and for
96 * any element still left in the ringbuffer when it is destroyed. It replaces
97 * all other element destruction code in your user code.
98 */
99LWS_VISIBLE LWS_EXTERN struct lws_ring *
100lws_ring_create(size_t element_len, size_t count,
101 void (*destroy_element)(void *element));
102
103/**
104 * lws_ring_destroy(): destroy a previously created ringbuffer
105 *
106 * \param ring: the struct lws_ring to destroy
107 *
108 * Destroys the ringbuffer allocation and the struct lws_ring itself.
109 */
110LWS_VISIBLE LWS_EXTERN void
111lws_ring_destroy(struct lws_ring *ring);
112
113/**
114 * lws_ring_get_count_free_elements(): return how many elements can fit
115 * in the free space
116 *
117 * \param ring: the struct lws_ring to report on
118 *
119 * Returns how much room is left in the ringbuffer for whole element insertion.
120 */
121LWS_VISIBLE LWS_EXTERN size_t
122lws_ring_get_count_free_elements(struct lws_ring *ring);
123
124/**
125 * lws_ring_get_count_waiting_elements(): return how many elements can be consumed
126 *
127 * \param ring: the struct lws_ring to report on
128 * \param tail: a pointer to the tail struct to use, or NULL for single tail
129 *
130 * Returns how many elements are waiting to be consumed from the perspective
131 * of the tail pointer given.
132 */
133LWS_VISIBLE LWS_EXTERN size_t
134lws_ring_get_count_waiting_elements(struct lws_ring *ring, uint32_t *tail);
135
136/**
137 * lws_ring_insert(): attempt to insert up to max_count elements from src
138 *
139 * \param ring: the struct lws_ring to report on
140 * \param src: the array of elements to be inserted
141 * \param max_count: the number of available elements at src
142 *
143 * Attempts to insert as many of the elements at src as possible, up to the
144 * maximum max_count. Returns the number of elements actually inserted.
145 */
146LWS_VISIBLE LWS_EXTERN size_t
147lws_ring_insert(struct lws_ring *ring, const void *src, size_t max_count);
148
149/**
150 * lws_ring_consume(): attempt to copy out and remove up to max_count elements
151 * to src
152 *
153 * \param ring: the struct lws_ring to report on
154 * \param tail: a pointer to the tail struct to use, or NULL for single tail
155 * \param dest: the array of elements to be inserted. or NULL for no copy
156 * \param max_count: the number of available elements at src
157 *
158 * Attempts to copy out as many waiting elements as possible into dest, from
159 * the perspective of the given tail, up to max_count. If dest is NULL, the
160 * copying out is not done but the elements are logically consumed as usual.
161 * NULL dest is useful in combination with lws_ring_get_element(), where you
162 * can use the element direct from the ringbuffer and then call this with NULL
163 * dest to logically consume it.
164 *
165 * Increments the tail position according to how many elements could be
166 * consumed.
167 *
168 * Returns the number of elements consumed.
169 */
170LWS_VISIBLE LWS_EXTERN size_t
171lws_ring_consume(struct lws_ring *ring, uint32_t *tail, void *dest,
172 size_t max_count);
173
174/**
175 * lws_ring_get_element(): get a pointer to the next waiting element for tail
176 *
177 * \param ring: the struct lws_ring to report on
178 * \param tail: a pointer to the tail struct to use, or NULL for single tail
179 *
180 * Points to the next element that tail would consume, directly in the
181 * ringbuffer. This lets you write() or otherwise use the element without
182 * having to copy it out somewhere first.
183 *
184 * After calling this, you must call lws_ring_consume(ring, &tail, NULL, 1)
185 * which will logically consume the element you used up and increment your
186 * tail (tail may also be NULL there if you use a single tail).
187 *
188 * Returns NULL if no waiting element, or a const void * pointing to it.
189 */
190LWS_VISIBLE LWS_EXTERN const void *
191lws_ring_get_element(struct lws_ring *ring, uint32_t *tail);
192
193/**
194 * lws_ring_update_oldest_tail(): free up elements older than tail for reuse
195 *
196 * \param ring: the struct lws_ring to report on
197 * \param tail: a pointer to the tail struct to use, or NULL for single tail
198 *
199 * If you are using multiple tails, you must use this API to inform the
200 * lws_ring when none of the tails still need elements in the fifo any more,
201 * by updating it when the "oldest" tail has moved on.
202 */
203LWS_VISIBLE LWS_EXTERN void
204lws_ring_update_oldest_tail(struct lws_ring *ring, uint32_t tail);
205
206/**
207 * lws_ring_get_oldest_tail(): get current oldest available data index
208 *
209 * \param ring: the struct lws_ring to report on
210 *
211 * If you are initializing a new ringbuffer consumer, you can set its tail to
212 * this to start it from the oldest ringbuffer entry still available.
213 */
214LWS_VISIBLE LWS_EXTERN uint32_t
215lws_ring_get_oldest_tail(struct lws_ring *ring);
216
217/**
218 * lws_ring_next_linear_insert_range(): used to write directly into the ring
219 *
220 * \param ring: the struct lws_ring to report on
221 * \param start: pointer to a void * set to the start of the next ringbuffer area
222 * \param bytes: pointer to a size_t set to the max length you may use from *start
223 *
224 * This provides a low-level, bytewise access directly into the ringbuffer
225 * allowing direct insertion of data without having to use a bounce buffer.
226 *
227 * The api reports the position and length of the next linear range that can
228 * be written in the ringbuffer, ie, up to the point it would wrap, and sets
229 * *start and *bytes accordingly. You can then, eg, directly read() into
230 * *start for up to *bytes, and use lws_ring_bump_head() to update the lws_ring
231 * with what you have done.
232 *
233 * Returns nonzero if no insertion is currently possible.
234 */
235LWS_VISIBLE LWS_EXTERN int
236lws_ring_next_linear_insert_range(struct lws_ring *ring, void **start,
237 size_t *bytes);
238
239/**
240 * lws_ring_bump_head(): used to write directly into the ring
241 *
242 * \param ring: the struct lws_ring to operate on
243 * \param bytes: the number of bytes you inserted at the current head
244 */
245LWS_VISIBLE LWS_EXTERN void
246lws_ring_bump_head(struct lws_ring *ring, size_t bytes);
247
248LWS_VISIBLE LWS_EXTERN void
249lws_ring_dump(struct lws_ring *ring, uint32_t *tail);
250
251/*
252 * This is a helper that combines the common pattern of needing to consume
253 * some ringbuffer elements, move the consumer tail on, and check if that
254 * has moved any ringbuffer elements out of scope, because it was the last
255 * consumer that had not already consumed them.
256 *
257 * Elements that go out of scope because the oldest tail is now after them
258 * get garbage-collected by calling the destroy_element callback on them
259 * defined when the ringbuffer was created.
260 */
261
262#define lws_ring_consume_and_update_oldest_tail(\
263 ___ring, /* the lws_ring object */ \
264 ___type, /* type of objects with tails */ \
265 ___ptail, /* ptr to tail of obj with tail doing consuming */ \
266 ___count, /* count of payload objects being consumed */ \
267 ___list_head, /* head of list of objects with tails */ \
268 ___mtail, /* member name of tail in ___type */ \
269 ___mlist /* member name of next list member ptr in ___type */ \
270 ) { \
271 int ___n, ___m; \
272 \
273 ___n = lws_ring_get_oldest_tail(___ring) == *(___ptail); \
274 lws_ring_consume(___ring, ___ptail, NULL, ___count); \
275 if (___n) { \
276 uint32_t ___oldest; \
277 ___n = 0; \
278 ___oldest = *(___ptail); \
279 lws_start_foreach_llp(___type **, ___ppss, ___list_head) { \
280 ___m = (int)lws_ring_get_count_waiting_elements( \
281 ___ring, &(*___ppss)->___mtail); \
282 if (___m >= ___n) { \
283 ___n = ___m; \
284 ___oldest = (*___ppss)->___mtail; \
285 } \
286 } lws_end_foreach_llp(___ppss, ___mlist); \
287 \
288 lws_ring_update_oldest_tail(___ring, ___oldest); \
289 } \
290}
291
292/*
293 * This does the same as the lws_ring_consume_and_update_oldest_tail()
294 * helper, but for the simpler case there is only one consumer, so one
295 * tail, and that tail is always the oldest tail.
296 */
297
298#define lws_ring_consume_single_tail(\
299 ___ring, /* the lws_ring object */ \
300 ___ptail, /* ptr to tail of obj with tail doing consuming */ \
301 ___count /* count of payload objects being consumed */ \
302 ) { \
303 lws_ring_consume(___ring, ___ptail, NULL, ___count); \
304 lws_ring_update_oldest_tail(___ring, *(___ptail)); \
305}
306///@}
307