1 /* 2 * Copyright (c) 2024 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 #ifndef KERN_MPSC_RING_H 30 #define KERN_MPSC_RING_H 31 32 /** 33 * @header 34 * This is an atomic multi-producer, single-consumer ringbuffer. Producers do 35 * not need to synchronize with each other, but only a single consumer can be 36 * active at one time. 37 * 38 * @discussion 39 * The data structures are defined here to allow them to be stored intrusively 40 * in other structures. Their fields are only documented to aid in 41 * understanding; do not manipulate them outside of the function interfaces 42 * declared below. 43 */ 44 45 #include <stdint.h> 46 #include <stdbool.h> 47 #include <sys/cdefs.h> 48 49 __BEGIN_DECLS 50 51 /** 52 * The data structure for an MPSC ringbuffer. 53 * 54 * @field mr_buffer 55 * The buffer that stores data, @link mr_capacity @/link in size. Field is 56 * constant after initialization but contents will be updated by writers. 57 * 58 * @field mr_capacity 59 * The size of the buffer to store data. Field is constant after 60 * initialization. 61 * 62 * @field mr_writer_holds 63 * Any pending reservations on the buffer, sized by @link mr_writer_count 64 * @/link. Field is constant after initialization but array elements will be 65 * updated by writers. 66 * 67 * @field mr_writer_count 68 * The number of concurrent potential writers. Field is constant after 69 * initialization. 70 * 71 * @field mr_head_tail 72 * A 64-bit value that holds the head and tail of the ringbuffer. 73 */ 74 struct mpsc_ring { 75 char *mr_buffer; 76 uint32_t *mr_writer_holds; 77 78 /** 79 * A view into the head, tail, and both offsets in the ringbuffer. 80 * 81 * @field mrht_head 82 * The head offset into the ringbuffer data, where writers will write new 83 * data. 84 * 85 * @field mrht_tail 86 * The tail offset into the ringbuffer data, where the reader has read up 87 * to. 88 * 89 * @field mrht_head_tail 90 * A combined view of head and tail for atomic updates. 91 */ 92 union mpsc_ring_head_tail { 93 struct { 94 uint32_t mrht_head; 95 uint32_t mrht_tail; 96 }; 97 uint64_t mrht_head_tail; 98 } mr_head_tail; 99 100 uint32_t mr_capacity; 101 uint8_t mr_writer_count; 102 }; 103 104 /** 105 * Initialize the ringbuffer. 106 * 107 * @discussion 108 * This must be called from a preemptible context, as it allocates memory. 109 * 110 * @param buf 111 * The ringbuffer to initialize. 112 * 113 * @param capacity_pow_2 114 * The size of the ringbuffer as a power of 2. For example, passing 10 here 115 * would allocate 2^10 (1KiB) bytes. 116 * 117 * @param writers_max 118 * The maximum number of writers that will be active at once. 119 */ 120 void mpsc_ring_init( 121 struct mpsc_ring *buf, 122 uint8_t capacity_pow_2, 123 uint8_t writers_max); 124 125 /** 126 * Write data to the ringbuffer. 127 * 128 * @discussion 129 * No external synchronization or mutual exclusion is necessary. 130 * 131 * @param buf 132 * The ringbuffer to write data to. 133 * 134 * @param writer_id 135 * The identity of the writer, must be less than the maximum writer count passed 136 * to @link mpsc_ring_init @/link. 137 * 138 * @param data 139 * The memory location to data to write to the ringbuffer. 140 * 141 * @param size 142 * The size of the memory location to write. 143 * 144 * @return 145 * Returns how much space was available before trying to write. 146 * Compare this to the requested write size to determine if the data was 147 * written. 148 */ 149 uint32_t mpsc_ring_write( 150 struct mpsc_ring *buf, 151 uint8_t writer_id, 152 const void *data, 153 uint32_t size); 154 155 /** 156 * A cursor to read data out of a ringbuffer. 157 * 158 * @discussion 159 * This structure is defined in the header to allow it to be treated as a value. 160 * Do not manipulate its fields manually. 161 * 162 * @field mrc_commit_pos 163 * The position of the cursor that will be written back to the ringbuffer when 164 * the read finishes. 165 * 166 * @field mrc_pos 167 * The position of the cursor to read data from in @link 168 * mpsc_ring_cursor_advance @/link. 169 * 170 * @field mrc_limit 171 * The maximum position that the cursor can advance. 172 */ 173 typedef struct { 174 uint32_t mrc_commit_pos; 175 uint32_t mrc_pos; 176 uint32_t mrc_limit; 177 } mpsc_ring_cursor_t; 178 179 /** 180 * Read data from the ringbuffer, consuming it. 181 * 182 * @discussion 183 * Only one thread may call this function at a time for the same buffer. 184 * This function must be paired with @link mpsc_ring_read_finish @/link or 185 * @link mpsc_ring_read_cancel @/link. 186 * 187 * @param buf 188 * The ringbuffer to start reading from. 189 * 190 * @return 191 * Returns a cursor to consume data from the ringbuffer. 192 */ 193 mpsc_ring_cursor_t mpsc_ring_read_start(struct mpsc_ring *buf); 194 195 /** 196 * Advance the cursor, copying it out of the ringbuffer and updating the next 197 * position to advance from. 198 * 199 * @param buf 200 * The ringbuffer the cursor is associated with. 201 * 202 * @param cursor 203 * The cursor to advance. 204 * 205 * @param destination 206 * The memory to write the ringbuffer contents into. 207 * 208 * @param size 209 * The amount of ringbuffer contents to read. 210 * 211 * @return 212 * True iff all the requested memory can be read, false otherwise. 213 */ 214 bool mpsc_ring_cursor_advance( 215 const struct mpsc_ring *buf, 216 mpsc_ring_cursor_t *cursor, 217 void *destination, 218 uint32_t size); 219 220 /** 221 * Commit any advancements in the cursor, ensuring that @link 222 * mpsc_ring_read_finish @/link will consume the memory up to the last call to 223 * @link mpsc_ring_cursor_advance @/link. 224 * 225 * @param buf 226 * The ringbuffer the cursor is associated with. 227 * 228 * @param cursor 229 * The cursor to commit advancements on. 230 */ 231 void mpsc_ring_cursor_commit( 232 const struct mpsc_ring *buf, 233 mpsc_ring_cursor_t *cursor); 234 235 /** 236 * Complete a read operation on the ringbuffer after manipulating a cursor. 237 * 238 * @discussion 239 * This function msut only be called after a previous call to @link 240 * mpsc_ring_read_start @/link. This call consumes the cursor and no further 241 * operations can be called on it. 242 * 243 * @param buf 244 * The ringbuffer to end reading on. 245 * 246 * @param cursor 247 * The cursor provided by @link mpsc_ring_read_start @/link. 248 */ 249 void mpsc_ring_read_finish( 250 struct mpsc_ring *buf, 251 mpsc_ring_cursor_t cursor); 252 253 /** 254 * Cancel a read operation on the ringbuffer, destroying the cursor and rolling 255 * back any advancement into the buffer. 256 * 257 * @discussion 258 * This function must only be called after a previous call to @link 259 * mpsc_ring_read_start @/link. This call consumes the cursor and no further 260 * operations can be called on it. 261 * 262 * @param buf 263 * The ringbuffer to cancel a read from. 264 * 265 * @param cursor 266 * The cursor provided by @link mpsc_ring_read_start @/link. 267 */ 268 void 269 mpsc_ring_read_cancel( 270 struct mpsc_ring *buf, 271 mpsc_ring_cursor_t cursor); 272 273 __END_DECLS 274 275 #endif /* !defined(KERN_MPSC_RING_H) */ 276