/*
* Copyright (c) 2024 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. The rights granted to you under the License
* may not be used to create, or enable the creation or redistribution of,
* unlawful or unlicensed copies of an Apple operating system, or to
* circumvent, violate, or enable the circumvention or violation of, any
* terms of an Apple operating system software license agreement.
*
* Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
*/
#ifndef KERN_MPSC_RING_H
#define KERN_MPSC_RING_H
/**
* @header
* This is an atomic multi-producer, single-consumer ringbuffer. Producers do
* not need to synchronize with each other, but only a single consumer can be
* active at one time.
*
* @discussion
* The data structures are defined here to allow them to be stored intrusively
* in other structures. Their fields are only documented to aid in
* understanding; do not manipulate them outside of the function interfaces
* declared below.
*/
#include <stdint.h>
#include <stdbool.h>
#include <sys/cdefs.h>
__BEGIN_DECLS
/**
* The data structure for an MPSC ringbuffer.
*
* @field mr_buffer
* The buffer that stores data, @link mr_capacity @/link in size. Field is
* constant after initialization but contents will be updated by writers.
*
* @field mr_capacity
* The size of the buffer to store data. Field is constant after
* initialization.
*
* @field mr_writer_holds
* Any pending reservations on the buffer, sized by @link mr_writer_count
* @/link. Field is constant after initialization but array elements will be
* updated by writers.
*
* @field mr_writer_count
* The number of concurrent potential writers. Field is constant after
* initialization.
*
* @field mr_head_tail
* A 64-bit value that holds the head and tail of the ringbuffer.
*/
struct mpsc_ring {
char *mr_buffer;
uint32_t *mr_writer_holds;
/**
* A view into the head, tail, and both offsets in the ringbuffer.
*
* @field mrht_head
* The head offset into the ringbuffer data, where writers will write new
* data.
*
* @field mrht_tail
* The tail offset into the ringbuffer data, where the reader has read up
* to.
*
* @field mrht_head_tail
* A combined view of head and tail for atomic updates.
*/
union mpsc_ring_head_tail {
struct {
uint32_t mrht_head;
uint32_t mrht_tail;
};
uint64_t mrht_head_tail;
} mr_head_tail;
uint32_t mr_capacity;
uint8_t mr_writer_count;
};
/**
* Initialize the ringbuffer.
*
* @discussion
* This must be called from a preemptible context, as it allocates memory.
*
* @param buf
* The ringbuffer to initialize.
*
* @param capacity_pow_2
* The size of the ringbuffer as a power of 2. For example, passing 10 here
* would allocate 2^10 (1KiB) bytes.
*
* @param writers_max
* The maximum number of writers that will be active at once.
*/
void mpsc_ring_init(
struct mpsc_ring *buf,
uint8_t capacity_pow_2,
uint8_t writers_max);
/**
* Write data to the ringbuffer.
*
* @discussion
* No external synchronization or mutual exclusion is necessary.
*
* @param buf
* The ringbuffer to write data to.
*
* @param writer_id
* The identity of the writer, must be less than the maximum writer count passed
* to @link mpsc_ring_init @/link.
*
* @param data
* The memory location to data to write to the ringbuffer.
*
* @param size
* The size of the memory location to write.
*
* @return
* Returns how much space was available before trying to write.
* Compare this to the requested write size to determine if the data was
* written.
*/
uint32_t mpsc_ring_write(
struct mpsc_ring *buf,
uint8_t writer_id,
const void *data,
uint32_t size);
/**
* A cursor to read data out of a ringbuffer.
*
* @discussion
* This structure is defined in the header to allow it to be treated as a value.
* Do not manipulate its fields manually.
*
* @field mrc_commit_pos
* The position of the cursor that will be written back to the ringbuffer when
* the read finishes.
*
* @field mrc_pos
* The position of the cursor to read data from in @link
* mpsc_ring_cursor_advance @/link.
*
* @field mrc_limit
* The maximum position that the cursor can advance.
*/
typedef struct {
uint32_t mrc_commit_pos;
uint32_t mrc_pos;
uint32_t mrc_limit;
} mpsc_ring_cursor_t;
/**
* Read data from the ringbuffer, consuming it.
*
* @discussion
* Only one thread may call this function at a time for the same buffer.
* This function must be paired with @link mpsc_ring_read_finish @/link or
* @link mpsc_ring_read_cancel @/link.
*
* @param buf
* The ringbuffer to start reading from.
*
* @return
* Returns a cursor to consume data from the ringbuffer.
*/
mpsc_ring_cursor_t mpsc_ring_read_start(struct mpsc_ring *buf);
/**
* Advance the cursor, copying it out of the ringbuffer and updating the next
* position to advance from.
*
* @param buf
* The ringbuffer the cursor is associated with.
*
* @param cursor
* The cursor to advance.
*
* @param destination
* The memory to write the ringbuffer contents into.
*
* @param size
* The amount of ringbuffer contents to read.
*
* @return
* True iff all the requested memory can be read, false otherwise.
*/
bool mpsc_ring_cursor_advance(
const struct mpsc_ring *buf,
mpsc_ring_cursor_t *cursor,
void *destination,
uint32_t size);
/**
* Commit any advancements in the cursor, ensuring that @link
* mpsc_ring_read_finish @/link will consume the memory up to the last call to
* @link mpsc_ring_cursor_advance @/link.
*
* @param buf
* The ringbuffer the cursor is associated with.
*
* @param cursor
* The cursor to commit advancements on.
*/
void mpsc_ring_cursor_commit(
const struct mpsc_ring *buf,
mpsc_ring_cursor_t *cursor);
/**
* Complete a read operation on the ringbuffer after manipulating a cursor.
*
* @discussion
* This function msut only be called after a previous call to @link
* mpsc_ring_read_start @/link. This call consumes the cursor and no further
* operations can be called on it.
*
* @param buf
* The ringbuffer to end reading on.
*
* @param cursor
* The cursor provided by @link mpsc_ring_read_start @/link.
*/
void mpsc_ring_read_finish(
struct mpsc_ring *buf,
mpsc_ring_cursor_t cursor);
/**
* Cancel a read operation on the ringbuffer, destroying the cursor and rolling
* back any advancement into the buffer.
*
* @discussion
* This function must only be called after a previous call to @link
* mpsc_ring_read_start @/link. This call consumes the cursor and no further
* operations can be called on it.
*
* @param buf
* The ringbuffer to cancel a read from.
*
* @param cursor
* The cursor provided by @link mpsc_ring_read_start @/link.
*/
void
mpsc_ring_read_cancel(
struct mpsc_ring *buf,
mpsc_ring_cursor_t cursor);
__END_DECLS
#endif /* !defined(KERN_MPSC_RING_H) */