summaryrefslogtreecommitdiffstats
path: root/lib/vio_fifo.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/vio_fifo.c')
-rw-r--r--lib/vio_fifo.c572
1 files changed, 572 insertions, 0 deletions
diff --git a/lib/vio_fifo.c b/lib/vio_fifo.c
new file mode 100644
index 00000000..fb62f192
--- /dev/null
+++ b/lib/vio_fifo.c
@@ -0,0 +1,572 @@
+/* VTY I/O FIFO
+ * Copyright (C) 2010 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2, or (at your
+ * option) any later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING. If not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <stddef.h>
+#include <string.h>
+
+#include "vio_fifo.h"
+#include "list_util.h"
+
+#include "memory.h"
+#include "zassert.h"
+
+/*==============================================================================
+ * VTY I/O FIFO manages an arbitrary length byte-wise FIFO buffer.
+ *
+ * The FIFO is arranged as lumps of some given size. Lumps are allocated
+ * as and when necessary, and released once emptied.
+ *
+ * The last lump is never released. So, it may be that only one lump is
+ * ever needed.
+ *
+ *------------------------------------------------------------------------------
+ * Implementation notes:
+ *
+ * The FIFO is initialised with all pointers NULL -- so with no lumps at all.
+ *
+ * Once a lump has been allocated there is always one lump in the FIFO.
+ *
+ * The following are expected to be true:
+ *
+ * * put_ptr == get_ptr => FIFO empty
+ *
+ * * put_ptr == tail->end -- at all times (NULL when no lumps)
+ *
+ * put_ptr >= tail->data ) otherwise something is broken
+ * put_ptr <= tail->end )
+ *
+ * * get_ptr == head->end -- when there is more than one lump
+ * get_ptr <= put_ptr -- when there is only one lump
+ *
+ * get_ptr >= head->data ) otherwise something is broken
+ * get_ptr <= head->end )
+ *
+ * * put_ptr == put_end => tail lump is full
+ * put_ptr < put_end => space exists in the tail lump
+ * put_ptr > put_end => broken
+ *
+ * * get_ptr == get_end => head lump is empty
+ * BUT if there is only one lump, make sure that
+ * get_end == put_ptr.
+ * get_ptr < get_end => data exists in the head lump
+ * get_ptr > get_end => broken
+ *
+ * Note that:
+ *
+ * * when the get_ptr reaches the put_ptr the pointers are reset to the
+ * start of the one and only lump.
+ *
+ * Everywhere that the get_ptr is moved, must check for meeting the
+ * put_ptr and reset pointers. At the same time, when reaches the end of
+ * a lump, gets rid of it.
+ *
+ * * when advancing the put_ptr does not check for advancing the get_end.
+ *
+ * The one exception to this, is that when the put_ptr advances to a new
+ * block, if there was one lump, sets the get_end to the end of that block.
+ *
+ * Everywhere that the get_end is used, must check for there being one
+ * lump and the possibility that put_ptr has changed.
+ */
+
+/*==============================================================================
+ * Initialisation, allocation and freeing of FIFO and lumps thereof.
+ */
+
+/* Return default size, or given size rounded up to 16 byte boundary */
+static size_t
+vio_fifo_size(size_t size)
+{
+ if (size == 0)
+ return 4096 ;
+ else
+ return ((size + 16 - 1) / 16) * 16 ;
+} ;
+
+/*==============================================================================
+ * Initialise VTY I/O FIFO -- allocating if required.
+ */
+extern vio_fifo
+vio_fifo_init_new(vio_fifo vf, size_t size)
+{
+ if (vf == NULL)
+ vf = XCALLOC(MTYPE_VIO_FIFO, sizeof(vio_fifo_t)) ;
+ else
+ memset(vf, 0, sizeof(vio_fifo_t)) ;
+
+ /* Zeroising the the vio_fifo_t has set:
+ *
+ * lump -- base pair, both pointers NULL => list is empty
+ *
+ * put_ptr -- NULL ) no lump to put anything into
+ * put_end -- NULL ) put_ptr == put_end => no room in current lump
+ *
+ * get_ptr -- NULL ) no lump to get anything from
+ * get_end -- NULL ) get_ptr -- get_end => nothing left in current lump
+ *
+ * ALSO put_ptr == get_ptr => FIFO is empty !
+ */
+
+ vf->size = vio_fifo_size(size) ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ return vf ;
+}
+
+/*------------------------------------------------------------------------------
+ * Free contents of given FIFO, and free FIFO structure as well, if required.
+ *
+ * Does nothing if given a NULL pointer -- must already have been freed !
+ *
+ * If does not free the FIFO structure, resets it all empty.
+ *
+ * See also: vio_fifo_reset_keep(vio_fifo)
+ * vio_fifo_reset_free(vio_fifo)
+ */
+extern vio_fifo
+vio_fifo_reset(vio_fifo vf, int free_structure)
+{
+ vio_fifo_lump lump ;
+
+ if (vf == NULL)
+ return NULL ;
+
+ while (ddl_pop(&lump, vf->base, list) != NULL)
+ XFREE(MTYPE_VIO_FIFO_LUMP, lump) ;
+
+ if (free_structure)
+ XFREE(MTYPE_VIO_FIFO, vf) ; /* sets vf = NULL */
+ else
+ vio_fifo_init_new(vf, vf->size) ;
+
+ return vf ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Set FIFO empty, discarding current contents -- will continue to use the FIFO.
+ */
+extern void
+vio_fifo_set_empty(vio_fifo vf)
+{
+ vio_fifo_lump lump ;
+
+ assert(vf != NULL) ;
+
+ while (ddl_head(vf->base) != ddl_tail(vf->base))
+ {
+ ddl_pop(&lump, vf->base, list) ;
+ XFREE(MTYPE_VIO_FIFO_LUMP, lump) ;
+ } ;
+
+ lump = ddl_head(vf->base) ;
+ if (lump != NULL)
+ {
+ vf->get_ptr = vf->get_end = vf->put_ptr = lump->data ;
+ vf->put_end = lump->end ;
+ } ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Allocate another lump for putting into.
+ *
+ * Call when (vf->put_ptr >= vf->put_end) -- asserts that the pointers are equal.
+ *
+ * Set the put_ptr/put_end pointers to point at the new lump.
+ *
+ * If this is the first lump allocated, set the get_ptr/get_end pointers too.
+ *
+ * If have just filled the first lump on the list, update the get_end pointer
+ * to reflect the fact that the out lump is now full.
+ */
+extern void
+vio_fifo_lump_new(vio_fifo vf)
+{
+ vio_fifo_lump lump ;
+ size_t size ;
+ int first_alloc ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ passert(vf->put_ptr == vf->put_end) ; /* must be end of tail lump */
+
+ lump = ddl_tail(vf->base) ;
+
+ /* When there is only one lump, the get_end tracks the put_ptr.
+ * But when there is more than one lump, it must be the end of that lump.
+ */
+ if (vf->one)
+ vf->get_end = lump->end ;
+
+ first_alloc = (lump == NULL) ; /* extra initialisation needed */
+
+ if (first_alloc)
+ assert(vf->put_ptr == NULL) ; /* must all be NULL together */
+ else
+ assert(vf->put_ptr == lump->end) ; /* must be end of tail lump */
+
+ size = vio_fifo_size(vf->size) ;
+ lump = XMALLOC(MTYPE_VIO_FIFO_LUMP, offsetof(vio_fifo_lump_t, data[size])) ;
+ lump->end = (char*)lump->data + vf->size ;
+
+ ddl_append(vf->base, lump, list) ;
+
+ vf->one = first_alloc ;
+
+ vf->put_ptr = lump->data ;
+ vf->put_end = lump->end ;
+
+ if (first_alloc)
+ {
+ vf->get_ptr = vf->put_ptr ; /* get_ptr == put_ptr => empty */
+ vf->get_end = vf->put_ptr ;
+ } ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+} ;
+
+/*==============================================================================
+ * Put data to the FIFO.
+ */
+
+/*------------------------------------------------------------------------------
+ * Store 'n' bytes -- allocate new lump if current is exhausted.
+ */
+extern void
+vio_fifo_put(vio_fifo vf, const char* src, size_t n)
+{
+ size_t take ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ while (n > 0)
+ {
+ if (vf->put_ptr >= vf->put_end)
+ vio_fifo_lump_new(vf) ; /* traps broken vf->put_ptr > vf->put_end */
+
+ take = (vf->put_end - vf->put_ptr) ;
+ if (take > n)
+ take = n ;
+
+ memcpy(vf->put_ptr, src, take) ;
+ vf->put_ptr += take ;
+
+ src += take ;
+ n -= take ;
+ } ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+} ;
+
+/*==============================================================================
+ * Get data from the FIFO.
+ */
+
+static bool vio_fifo_get_next_lump(vio_fifo vf) ;
+
+/*------------------------------------------------------------------------------
+ * Get ready to read something out of the FIFO.
+ *
+ * Makes sure vf->get_end is up to date (if required) and if the FIFO is not
+ * empty, makes sure vf->get_ptr points at the next byte to be read.
+ *
+ * Returns: true <=> there is something in the FIFO.
+ */
+static inline bool
+vio_fifo_get_ready(vio_fifo vf)
+{
+ if (vf->one)
+ vf->get_end = vf->put_ptr ; /* make sure have everything */
+
+ if (vf->get_ptr >= vf->get_end)
+ if (!vio_fifo_get_next_lump(vf))
+ return 0 ; /* quit now if nothing there */
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ return 1 ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Get upto 'n' bytes.
+ *
+ * Returns: number of bytes got -- may be zero.
+ */
+extern size_t
+vio_fifo_get(vio_fifo vf, void* dst, size_t n)
+{
+ size_t have ;
+ void* dst_in ;
+
+ if (!vio_fifo_get_ready(vf))
+ return 0 ; /* quit now if nothing there */
+
+ dst_in = dst ;
+ while (n > 0)
+ {
+ have = vf->get_end - vf->get_ptr ;
+
+ if (have > n)
+ have = n ;
+
+ memcpy(dst, vf->get_ptr, have) ;
+ vf->get_ptr += have ;
+ dst = (char*)dst + have ;
+
+ if (vf->get_ptr >= vf->get_end) /* deal with exhausted lump */
+ if (!vio_fifo_get_next_lump(vf))
+ break ; /* quit if nothing more to come */
+
+ n -= have ;
+ } ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ return (char*)dst - (char*)dst_in ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Get byte -- the long winded way.
+ *
+ * See the inline vio_fifo_get_byte().
+ *
+ * The version is used when the get_ptr is at or just before the end of the
+ * current lump. Looks after all the necessary pointer updates associated with
+ * hitting end of lump, or hitting end of FIFO.
+ *
+ * Returns: 0x00..0xFF -- byte value (as an int)
+ * -1 => FIFO is empty.
+ */
+
+extern int
+vio_fifo_get_next_byte(vio_fifo vf)
+{
+ unsigned char u ;
+
+ if (!vio_fifo_get_ready(vf))
+ return -1 ; /* quit now if nothing there */
+
+ u = *vf->get_ptr++ ;
+
+ /* As soon as reach the end want either to discard empty lump, or reset
+ * the pointers.
+ */
+ if (vf->get_ptr >= vf->get_end) /* deal with exhausted lump */
+ vio_fifo_get_next_lump(vf) ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ return u ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Get pointer to a lump of bytes.
+ *
+ * Returns: address of next byte to get, *have = number of bytes available
+ * or: NULL => FIFO is empty, *have = 0
+ *
+ * If the FIFO is not empty, will return pointer to at least one byte.
+ *
+ * Returns number of bytes to the end of the current lump. There may be
+ * further lumps beyond the current one.
+ */
+extern void*
+vio_fifo_get_lump(vio_fifo vf, size_t* have)
+{
+ if (!vio_fifo_get_ready(vf))
+ {
+ *have = 0 ;
+ return NULL ;
+ } ;
+
+ *have = (vf->get_end - vf->get_ptr) ;
+ return vf->get_ptr ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Advance FIFO to position reached.
+ *
+ * Having done vio_fifo_get_lump(), can take any number of bytes (up to the
+ * number that "have"), then call this function to advance the pointers.
+ *
+ * The "here" argument must the the address returned by vio_fifo_get_lump()
+ * plus the number of bytes taken.
+ */
+extern void
+vio_fifo_got_upto(vio_fifo vf, void* here)
+{
+ vf->get_ptr = here ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ if (vf->get_ptr >= vf->get_end)
+ vio_fifo_get_next_lump(vf) ;
+} ;
+
+/*------------------------------------------------------------------------------
+ * Move on to next lump to get stuff from.
+ *
+ * Advance pointers etc. so that have at least one byte available, unless
+ * the FIFO is entirely empty.
+ *
+ * This should be called if (vf->get_ptr >= vf->get_end) -- asserts that
+ * these are equal !
+ *
+ * NB: when there is only one block, it may be that get_end is out of date,
+ * and should be advanced to the current put_ptr position.
+ *
+ * That is done here, but may be worth updating get_end before testing
+ * against get_ptr.
+ *
+ * Returns: true <=> at least one byte in FIFO.
+ *
+ * NB: if finds that the FIFO is empty, resets the pointers to the start
+ * of the last lump.
+ */
+static bool
+vio_fifo_get_next_lump(vio_fifo vf)
+{
+ vio_fifo_lump head ;
+ vio_fifo_lump tail ;
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+ assert(vf->get_ptr == vf->get_end) ;
+
+ head = ddl_head(vf->base) ; /* current lump for put */
+ tail = ddl_tail(vf->base) ; /* current lump for get */
+
+ /* Deal with case of one lump only */
+ if (vf->one)
+ {
+ assert( (head != NULL)
+ && (head == tail) ) ;
+
+ if (vf->get_ptr == vf->put_ptr)
+ {
+ /* FIFO is empty -- reset pointers and exit */
+ vf->get_ptr = vf->get_end = vf->put_ptr = head->data ;
+ assert(vf->put_end == head->end) ;
+
+ return 0 ; /* FIFO empty */
+ } ;
+
+ /* Had an out of date vf->get_end */
+ assert(vf->get_end < vf->put_ptr) ;
+ vf->get_end = vf->put_ptr ;
+
+ return 1 ; /* FIFO not empty after all */
+ } ;
+
+ /* Deal with case of not yet allocated */
+ if (head == NULL)
+ {
+ assert( (tail == NULL)
+ && (vf->put_ptr == vf->get_ptr) );
+
+ return 0 ; /* FIFO empty */
+ } ;
+
+ /* Deal with (remaining) case of two or more lumps */
+ assert(vf->get_ptr == head->end) ;
+
+ ddl_del_head(vf->base, list) ;
+ XFREE(MTYPE_VIO_FIFO_LUMP, head) ;
+
+ head = ddl_head(vf->base) ;
+ assert(head != NULL) ;
+
+ vf->one = (head == tail) ;
+
+ vf->get_ptr = head->data ; /* at start of next lump */
+
+ if (vf->one)
+ vf->get_end = vf->put_ptr ; /* up to current put */
+ else
+ vf->get_end = head->end ; /* up to end of lump */
+
+ VIO_FIFO_DEBUG_VERIFY(vf) ;
+
+ return (vf->get_ptr < vf->get_end) ;
+} ;
+
+/*==============================================================================
+ * For debug purposes -- verify the state of the given FIFO
+ */
+Private void
+vio_fifo_verify(vio_fifo vf)
+{
+ vio_fifo_lump head ;
+ vio_fifo_lump tail ;
+
+ head = ddl_head(vf->base) ;
+ tail = ddl_tail(vf->base) ;
+
+ /* If nothing allocated, should all be NULL & !vf->one */
+ /* If something allocated, tail must not be NULL */
+ if (head == NULL)
+ {
+ if ( (tail != NULL)
+ || (vf->put_ptr != NULL)
+ || (vf->put_end != NULL)
+ || (vf->get_ptr != NULL)
+ || (vf->get_end != NULL)
+ || (vf->one) )
+ zabort("nothing allocated, but not all NULL") ;
+ return ;
+ }
+ else
+ {
+ if (tail == NULL)
+ zabort("head pointer not NULL, but tail pointer is") ;
+ } ;
+
+ /* Check that all the pointers are within respective lumps
+ *
+ * Know that put_end is always tail->end, but get_end need not be.
+ * */
+ if ( (tail->data > vf->put_ptr)
+ || (vf->put_ptr > vf->put_end)
+ || (vf->put_end != tail->end) )
+ zabort("put pointers outside the tail lump") ;
+
+ if ( (head->data > vf->get_ptr)
+ || (vf->get_ptr > vf->get_end)
+ || (vf->get_end > head->end) )
+ zabort("get pointers outside the head lump") ;
+
+ /* If head == tail, should be vf->one, etc. */
+ if (head == tail)
+ {
+ if (!vf->one)
+ zabort("have one lump, but !vf->one") ;
+
+ if (vf->get_end > vf->put_ptr)
+ zabort("get_end is greater than put_ptr when vf->one") ;
+ }
+ else
+ {
+ if (vf->one)
+ zabort("have two or more lumps, but vf->one is true") ;
+
+ if (vf->get_end != head->end)
+ zabort("get_end is not head->end when !vf->one") ;
+ }
+} ;
generated by cgit v1.2.3 (git 2.25.1) at 2025-09-13 07:05:08 +0000