Line data    Source code

       1             : #ifndef HEADER_fd_src_disco_events_fd_circq_h
       2             : #define HEADER_fd_src_disco_events_fd_circq_h
       3             : 
       4             : /* The circular buffer is a structure, which stores a queue of messages,
       5             :    supporting two operations: push_back and pop_front.  Unlike a regular
       6             :    queue, the circular buffer is fixed size and push_back must always
       7             :    succeed.
       8             : 
       9             :    To ensure push_back always succeeds, the circular buffer will evict
      10             :    old messages if necessary to make room for the new one.
      11             : 
      12             :    One more complication is that the circular buffer must store
      13             :    metadata about the messages in the data buffer itself, as it does not
      14             :    have a separate metadata region.  The structure of the buffer then
      15             :    looks as follows:
      16             : 
      17             :     +-------+-----+------+-----+-------+-----+------+-----+-------+-----+------+
      18             :     + meta0 | pad | msg0 | pad | meta1 | pad | msg1 | pad | meta2 | pad | msg2 |
      19             :     +-------+-----+------+-----+-------+-----+------+-----+-------+-----+------+
      20             :      ^  |                        ^  |                        ^  |
      21             :      |  +-----next---------next--+  +------------------------+  |
      22             :      |                                                          |
      23             :    head                                                        tail
      24             : 
      25             :    Here, the meta elements are fd_circq_message_t, which each point to
      26             :    the next message in the queue, and head, tail are the head and tail
      27             :    of the queue respectively. */
      28             : 
      29             : #include "../../util/fd_util_base.h"
      30             : 
      31           0 : #define FD_CIRCQ_ALIGN (4096UL)
      32             : 
      33             : struct __attribute__((aligned(FD_CIRCQ_ALIGN))) fd_circq_private {
      34             :   /* Current count of elements in the queue. */
      35             :   ulong cnt;
      36             : 
      37             :   /* These are offsets relative to the end of this struct of the
      38             :      metadata for the first, and last message in the queue,
      39             :      respectively. */
      40             :   ulong head;
      41             :   ulong tail;
      42             : 
      43             :   ulong size;
      44             : 
      45             :   ulong cursor;          /* Current offset in buffer for iteration, or ULONG_MAX if at end */
      46             :   ulong cursor_seq;      /* Monotonic counter - cursor value for current position */
      47             :   ulong cursor_push_seq; /* Monotonic counter - incremented on each push */
      48             : 
      49             :   struct {
      50             :     ulong drop_cnt;
      51             :   } metrics;
      52             : 
      53             :   /* padding out to 4k here ... */
      54             : };
      55             : 
      56             : typedef struct fd_circq_private fd_circq_t;
      57             : 
      58             : FD_PROTOTYPES_BEGIN
      59             : 
      60             : FD_FN_CONST ulong
      61             : fd_circq_align( void );
      62             : 
      63             : FD_FN_CONST ulong
      64             : fd_circq_footprint( ulong sz );
      65             : 
      66             : void *
      67             : fd_circq_new( void * shmem,
      68             :               ulong  sz );
      69             : 
      70             : fd_circq_t *
      71             : fd_circq_join( void * shbuf );
      72             : 
      73             : void *
      74             : fd_circq_leave( fd_circq_t * buf );
      75             : 
      76             : void *
      77             : fd_circq_delete( void * shbuf );
      78             : 
      79             : /* fd_circq_push_back appends a message of size sz into the circular
      80             :    buffer, evicting any old messages if they would be overwritten when
      81             :    the buffer wraps around.  Returns the address of the memory contents
      82             :    in the buffer on success, or NULL on failure.  The only two reasons
      83             :    for failure are if the requested sz (along with the message metadata)
      84             :    exceeds the size of the entire buffer and can't fit, or if the
      85             :    requested alignment is not a power of 2, or is larger than 4096. */
      86             : 
      87             : uchar *
      88             : fd_circq_push_back( fd_circq_t * circq,
      89             :                     ulong        align,
      90             :                     ulong        footprint );
      91             : 
      92             : void
      93             : fd_circq_resize_back( fd_circq_t * circq,
      94             :                       ulong        new_footprint );
      95             : 
      96             : /* fd_circq_cursor_advance moves an internal cursor forward to the next
      97             :    message in the circular buffer, returning the message at the previous
      98             :    cursor position, or NULL if there are no more messages.
      99             : 
     100             :    Moving the cursor does not remove the message from the circular
     101             :    buffer, which only happens when fd_circq_pop_until is called. */
     102             : 
     103             : uchar const *
     104             : fd_circq_cursor_advance( fd_circq_t * circq,
     105             :                          ulong *      msg_sz );
     106             : 
     107             : /* fd_circq_pop_until removes messages from the front of the circular
     108             :    buffer up to and including the message with the given cursor value.
     109             :    Returns 0 on success, or -1 if the given cursor value is invalid
     110             :    (i.e., it is higher than the present cursor of the circq and has
     111             :    never existed.) */
     112             : 
     113             : int
     114             : fd_circq_pop_until( fd_circq_t * circq,
     115             :                     ulong        cursor );
     116             : 
     117             : /* fd_circq_reset_cursor resets the internal cursor to the front of the
     118             :    circular buffer.  This is useful if you want to re-process all
     119             :    messages in the buffer from the start. */
     120             : 
     121             : void
     122             : fd_circq_reset_cursor( fd_circq_t * circq );
     123             : 
     124             : /* fd_circq_bytes_used returns the total number of bytes currently used
     125             :    in the circular buffer, including message metadata and padding. */
     126             : 
     127             : ulong
     128             : fd_circq_bytes_used( fd_circq_t const * circq );
     129             : 
     130             : FD_PROTOTYPES_END
     131             : 
     132             : #endif /* HEADER_fd_src_disco_events_fd_circq_h */