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 ///@{ 80 struct 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 */ 99 LWS_VISIBLE LWS_EXTERN struct lws_ring * 100 lws_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 */ 110 LWS_VISIBLE LWS_EXTERN void 111 lws_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 */ 121 LWS_VISIBLE LWS_EXTERN size_t 122 lws_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 */ 133 LWS_VISIBLE LWS_EXTERN size_t 134 lws_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 */ 146 LWS_VISIBLE LWS_EXTERN size_t 147 lws_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 */ 170 LWS_VISIBLE LWS_EXTERN size_t 171 lws_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 */ 190 LWS_VISIBLE LWS_EXTERN const void * 191 lws_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 */ 203 LWS_VISIBLE LWS_EXTERN void 204 lws_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 */ 214 LWS_VISIBLE LWS_EXTERN uint32_t 215 lws_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 */ 235 LWS_VISIBLE LWS_EXTERN int 236 lws_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 */ 245 LWS_VISIBLE LWS_EXTERN void 246 lws_ring_bump_head(struct lws_ring *ring, size_t bytes); 247 248 LWS_VISIBLE LWS_EXTERN void 249 lws_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