---

RNG.c File Reference

Utility for configuring a pool of memory as a ring buffer. More...

#include <stdio.h>
#include "BBC/RNG.h"
#include "BBC/BUG.h"

Data Structures
struct	_RNG_rcb
Defines
#define	NULL   ((unsigned char *)0)
	NULL pointer definition.
#define	RND_TO(_ptr, _msk)   (((unsigned int)(_ptr) + _msk) & ~_msk)
	Rounds the specified address up to the nearest binary boundary.
Functions
void	rng_bdestroy (struct block *block)
	Closes the blocking control structure. More...
void	rng_binit (struct block *block)
	Initializes the blocking control structure. More...
void	rng_wake (struct block *block, int freeing)
	Awakens an allocator if freeing the specified amount has a chance of satisfying the request. More...
int	rng_wait (struct block *block, unsigned char *volatile *rrd, unsigned char *rd, int needed, int timeout)
	Blocks the requestor until enough memory is returned to satisfy the request or until timeout period expires. More...
void *	allocate (struct _RNG_rcb *rcb, int minimum, const void *curWrt, int *allocated, int timeout)
	The underlying workhorse allocator. More...
void *	RNG_buf (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to the original buffer. More...
int	RNG_bsize (const struct _RNG_rcb *rcb)
	Query routine to return the size of the original buffer. More...
void *	RNG_beg (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to the beginning of the underflow area. More...
void *	RNG_rbeg (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to the beginning of the ring buffer area. More...
void *	RNG_rend (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to the end of the ring buffer area. More...
void *	RNG_end (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to the end of the overflow area. More...
void *	RNG_rd (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to current read pointer the ring buffer area. More...
void *	RNG_wr (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to the current write pointer. More...
void *	RNG_shard (const struct _RNG_rcb *rcb)
	Query routine to return a pointer to current list of shards. More...
int	RNG_destroy (struct _RNG_rcb *rcb)
	Returns any resources associated with this ring buffer. More...
int	RNG_sizeof_rcb ()
	Returns the size of the Ring Contol Block. More...
int	RNG_init (struct _RNG_rcb *rcb, unsigned char *buf, int size, int underflow, int overflow, int alignment, RNG_type blocking)
	Initializes the control structure for a Ring buffer. More...
void *	RNG_get (struct _RNG_rcb *rcb, int request, const void *nxtWrt)
	Non-blocking allocation request for a specified amount of memory. More...
void *	RNG_getW (struct _RNG_rcb *rcb, int request, const void *nxtWrt, int timeout)
	Blocking allocation request for a specified amount of memory. More...
void *	RNG_grab (struct _RNG_rcb *rcb, int minimum, const void *nxtWrt, int *allocated)
	Non-blocking allocation request for all the remaining contigious memory. More...
void *	RNG_grabW (struct _RNG_rcb *rcb, int minimum, const void *nxtWrt, int *allocated, int timeout)
	Bocking allocation request for all the remaining contigious memory. More...
int	RNG_free (struct _RNG_rcb *rcb, const void *packet, int amount)
	Frees the requested amount of memory from the specified address. More...
void *	RNG_shrink (struct _RNG_rcb *rcb, const void *newWrt, int left)
	Shrinks the previously allocated packet back to the specified address. More...
int	RNG_reset (struct _RNG_rcb *rcb)
	If the pool is empty, resets the WR/RD pointers to their initial values. More...

---

Detailed Description

Utility for configuring a pool of memory as a ring buffer.

Author:

JJRussell - russell@slac.stanford.edu

IMPLEMENTATION NOTE 1
---------------------
A circular buffer has a couple of very nice properties. The one exploited here is one can implement a single writer/single reader (or if you prefer, a single allocator/single freer) set of routines without the need for memory interlocks. Of course if you want the allocator to block on insufficient memory, then this is not the case. One needs a synchronization mechanism.

The writer (allocator) only need modify the WRITE pointer, while the reader (freer) need only modify the READ pointer. Each may reference the contents of the other pointer. These references may be 'stale', in the sense that the actual value may change, but the consequences of this are beign. For instance, consider the allocater. It must determine how much memory is still available in the pool. It does this by calculating the distance between the READ and WRITE pointers. Potentially, a freer could interrupt this thread of execution just after this value is calculated. However, all this really means is that the allocator may not see all the memory that is available at that exact instance in time. So two things will happen in this case

1. There is enough memory to satisfy the request 2. There is not enough memory to satisfy the request

In the first case, all is well, the allocator got what he wanted. In the second case, the allocator is forced to retry. This is really no different than if the allocator had been called slightly sooner (before the free routine could put back the memory), so unless there is some highly determinestic reason which sequences the allocator and freer, this is just the luck of the draw.

There is, as always, one complication; how to distinguish the completely full state from the completely empty state. The tact taken here is to always contain the WRITE pointer within the pool, but, when the pool is completely empty, to represent the READ pointer by the WRITE pointer + the size of the buffer. This means that the READ buffer can potentially point outside the buffer. This is okay, provided that anytime this value is used, it is first checked to see if it is outside the pool. It can then be constrained to be within the pool simply be subtracting the size of the pool.

The WRITE (allocator) does this when the distance between the two pointers is calculated. If this distance is the size of the pool, read pointer can be safely pushed to it's value - length of the pool. There is no danger of the FREER manipulating the pointer, since all the memory is allocated, ie there is no **legitimate** reason for the free routine to be called.

IMPLEMENTATION NOTE 2
---------------------
These first two variables WR and RD can potentially be modified from different threads, so references to these values cannot be optimized out. After much experimenting, I finally landed on the following syntax for declaring the value of the pointer to be volatile. Note that this is not the same as

volatile unsigned char *adr;

This declares the contents at the location adr to be volatile, not the value of adr. The former is what one usually wants, but in this case, it is the value of adr that is volatile.

Without the volatile declaration the optimizer is free to tranform

w1 = rcb->wr; w1 = rcb->wr; w2 = rcb->wr; into w2 = w1; w3 = rcb->wr; w3 = w1;

If rcb->wr is being modified from another thread of execution, this is incorrect.

---

Function Documentation

void * allocate (  struct _RNG_rcb *    rcb, int    request, const void *    nxtWrt, int *    allocated, int    timeout )  [static]

The underlying workhorse allocator. Parameters: rcb  The Ring Control Block minimum  The minimum number of bytes needed to satisty the request curWrt  The value of the current write pointer. This is used as an integrity check. If specified as NON-NULL, then it must match the Ring Buffer's current value of the write pointer. If specified as NULL, the caller is living dangerously, and skipping the check. allocated  If specified as NULL, the allocation is for the amount specified by minimum. If NON NULL, then the request is satisfied with the all the contigious memory available, provided it is larger than minimum. The amount of memory allocated is returned in this address. timeout  A timeout parameter. Returns: If successful, a pointer to the allocated memory. If not, then NULL.

void rng_bdestroy (  struct block *    block )  [inline, static]

Closes the blocking control structure. Parameters: block  The blocking control structure to close

void * RNG_beg (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to the beginning of the underflow area. Parameters: rcb  The Ring Control Block Returns: A pointer to the beginning of the underflow area. This routine is primarily used for debugging purposes, but is also useful when determining whether a region of memory occupies any of the underflow area. The underflow area ends at the beginning of the ring buffer area, set RNG_rbeg(). Warning: Note that due to rounding to alignment boundaries this pointer may or may not be the same as the beginning of the original buffer.

void rng_binit (  struct block *    block )  [inline, static]

Initializes the blocking control structure. Parameters: block  The blocking control structure to initialize

int RNG_bsize (  const struct _RNG_rcb *    rcb )

Query routine to return the size of the original buffer. Parameters: rcb  The Ring Control Block Returns: A pointer to the original pool of memory the RNG utilities where requested to manage. This routine, along with RNG_bsize(), returns the original buffer address and size that the RNG utilities where requested to manage. These two values may be useful when the RNG buffer is being destroyed, allowing the user to return the buffer to whereever it belongs.

void * RNG_buf (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to the original buffer. Parameters: rcb  The Ring Control Block Returns: A pointer to the original pool of memory the RNG utilities where requested to manage. This routine, along with RNG_bsize(), returns the original buffer address and size that the RNG utilities where requested to manage. These two values may be useful when the RNG buffer is being destroyed, allowing the user to return the buffer to whereever it belongs.

int RNG_destroy (  struct _RNG_rcb *    rcb )

Returns any resources associated with this ring buffer. Parameters: rcb  The Ring Control Block Returns: Status Frees any internally gathered resources associated with the specified ring buffer. The rcb is no longer usable as ring buffer after this call. Warning: It is the user's responsibility to dispose of the memory associated with the buffer that was being managed and the memory containing the Ring Control Block.

void * RNG_end (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to the end of the overflow area. Parameters: rcb  The Ring Control Block Returns: A pointer to the end of the overflow area This routine is primarily used for debugging purposes, but may be useful when determining whether a region of memory occupies the overflow area. Warning: Due to rounding to alignment boundaries, this pointer may or may not coincide with the ending of the original pool of memory the RNG utilities where asked to manage.

void * RNG_free (  struct _RNG_rcb *    rcb, const void *    ptr, int    amount )

Frees the requested amount of memory from the specified address. Parameters: rcb  The Ring Control Block ptr  The pointer where the free begins amount  The amount of memory to free Returns: Status Frees the requested amount of memory beginning at ptr. Note that, unlike many other allocators, RNG_free allows partial freeing. One is not obligated to match allocations and deallocations. The only restriction is that the free \ptr must be consistent with the next location to be freed by the Ring Buffer utilities, and that one frees only that which is allocated.

void * RNG_get (  struct _RNG_rcb *    rcb, int    request, const void *    chkWrt )

Non-blocking allocation request for a specified amount of memory. Parameters: rcb  The Ring Control Block request  The size, in bytes, of the request chkWrt  The anticipated allocation value, to within alignment factors. This maybe specified as NULL. Returns: If successful, a pointer to the allocated memory, else NULL. Attempts to allocate the requested amount of memory. If insufficient memory is available or the chkWrt pointer is inconsistent with the internal write pointer, NULL is returned. The user can distinguish these two cases by calling RNG_wr(), to fetch the current value of the write pointer. The user may also live dangerously and specify NULL for the chkWrt argument, in which case the consistency check is bypassed.

void * RNG_getW (  struct _RNG_rcb *    rcb, int    request, const void *    chkWrt, int    timeout )

Blocking allocation request for a specified amount of memory. Parameters: rcb  The Ring Control Block request  The size, in bytes, of the request chkWrt  The anticipated allocation value, to within alignment factors. This maybe specified as NULL. timeout  The timeout period. Currently only RNG_K_WTO_NO_WAIT (0) and RNG_K_WTO_FOREVER (-1) are supported. Returns: If successful, a pointer to the allocated memory, else NULL. Attempts to allocate the requested amount of memory. If the chkWrt pointer is inconsistent with the internal write pointer, or insufficeint memory is available and the timeout period expires, NULL is returned. The user can distinguish these two cases by calling RNG_wr(), to fetch the current value of the write pointer. The user may also live dangerously and specify NULL for the chkWrt argument, in which case the consistency check is bypassed. Warning: Blocking on a RNG buffer that is does not have blocking enable will be treated as a NO WAIT call.

void * RNG_grab (  struct _RNG_rcb *    rcb, int    minimum, const void *    chkWrt, int *    allocated )

Non-blocking allocation request for all the remaining contigious memory. Parameters: rcb  The Ring Control Block request  The size, in bytes, of the request chkWrt  The anticipated allocation value, to within alignment factors. This maybe specified as NULL. allocated  Pointer to receive the actual amount, in bytes, that was allocated. Returns: If successful, a pointer to the allocated memory, else NULL. This is a greedy form of allocation. All the contigious memory from the current write pointer on is allocated to the caller provided this amount is larger than the minimum requested. This allows the user to continually fill memory even if does not know at allocation time how much is needed. This routine is often used with RNG_shrink(). Here one allocates as much as one can with RNG_grab, uses what he wants, then returns the unused portion by calling RNG_shrink(). If there is less than the minimum amount of memory in the pool, NULL is returned.

void * RNG_grabW (  struct _RNG_rcb *    rcb, int    minimum, const void *    chkWrt, int *    allocated, int    timeout )

Bocking allocation request for all the remaining contigious memory. Parameters: rcb  The Ring Control Block request  The size, in bytes, of the request chkWrt  The anticipated allocation value, to within alignment factors. This maybe specified as NULL. allocated  Pointer to receive the actual amount, in bytes, that was allocated. timeout  The timeout period. Currently only RNG_K_WTO_NO_WAIT (0) and RNG_K_WTO_FOREVER (-1) are supported. Returns: If successful, a pointer to the allocated memory, else NULL. This is a greedy form of allocation. All the contigious memory from the current write pointer on is allocated to the caller provided this amount is larger than the minimum requested. This allows the user to continually fill memory even if does not know at allocation time how much is needed. This routine is often used with RNG_shrink(). Here one allocates as much as one can with RNG_grab, uses what he wants, then returns the unused portion by calling RNG_shrink(). If less the timeout period expires or the internal write pointer is inconsistent with the chkWrt argument, NULL is returned. The user may distinguish these cases by calling RNG_wr(). Warning: Blocking on a RNG buffer that is does not have blocking enable will be treated as a NO WAIT call.

int RNG_init (  struct _RNG_rcb *    rcb, unsigned char *    buf, int    size, int    underflow, int    overflow, int    alignment, RNG_type    type )

Initializes the control structure for a Ring buffer. Parameters: rcb  The Ring Control Block buf  The buffer to be managed size  The size, in bytes, of the buffer to be managed underflow  The size, in bytes, of the underflow area overflow  The size, in bytes, of the overflow area alignment  The desired alignment of all requests, expressed as a power of 2, eg 0 => 1 byte alignment, 1 => 2 byte alignment, 2 => 4 byte alignment, etc. blocking  The type of blocking the user wishes. See RNG_type for the types available and their description. Returns: Status Initializes a Ring Control Block to manage a pool of memory. The memory is carved into three pieces, an underflow area, a ring buffer area, and an overflow area. The detailed use and meaning of these areas is described elsewhere.

void * RNG_rbeg (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to the beginning of the ring buffer area. Parameters: rcb  The Ring Control Block Returns: A pointer to the beginning of the ring buffer area. By definition, this is also the end of the underflow area. This routine is primarily used for debugging purposes, but is also useful when determining whether a region of memory occupies any of the underflow area or is in the ring buffer pool proper. The underflow area extends from the pointer returned by RNG_beg() to the pointer returned by this routine. The end of the ring buffer pool is returned from RNG_rend().

void * RNG_rd (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to current read pointer the ring buffer area. Parameters: rcb  The Ring Control Block Returns: The value of the current read pointer This routine is primarily used for debugging purposes. Warning: Whereas many of the other query routines return pointers or values that are static and valid once the ring buffer has been initialized, this pointer is dynamic. Let the user beware.

void * RNG_rend (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to the end of the ring buffer area. Parameters: rcb  The Ring Control Block Returns: A pointer to the end of the ring buffer area. By definition this is also the start of the overflow area. This routine is primarily used for debugging purposes, but is also useful when determining whether a region of memory occupies either the ring buffer pool proper or the overflow area. This pointer is the boundary between those two regions.

int RNG_reset (  struct _RNG_rcb *    rcb )

If the pool is empty, resets the WR/RD pointers to their initial values. Parameters: The  ring control block Returns: Status Normally the read and write pointers are not diddle with except on allocation and deallocation. In an empty pool, the read and write pointers will can be anywhere. This means that the maximum contigious memory may not be available for use. This routine allows the user to reset these pointers to their initial positions, thus maximizing the amount of contigious memory. The downside of this move is that the Ring Buffer loses some of its 'history' feature, which may be valuable as a debugging aid.

void * RNG_shard (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to current list of shards. Parameters: rcb  The Ring Control Block Returns: A pointer to any abandoned memory Warning: This is provided for debugging purposes only.

void * RNG_shrink (  struct _RNG_rcb *    rcb, const void *    newWrt, int    left )

Shrinks the previously allocated packet back to the specified address. Parameters: rcb  The Ring Control Block newWrt  The address to shrink to. The current write pointer, up to alignment factors, is moved to this address. left  The number of unused bytes from the previous allocation. This is used as a consistency check. Returns: If successful, the next write pointer. Due to alignment reasons, this may or may not be the same as \newWrt. Routine shrinks the previously allocated packet back to the specified address. A check is performed to see if this newWrt pointer plus the number of bytes \left in the old allocation is consistent with the Ring Buffer Manager's internal write pointer. If not, NULL is returned.

int RNG_sizeof_rcb (  void    )

Returns the size of the Ring Contol Block. Returns: The size of a Ring Control Block This routine allows the user to allocate or set aside a block of memory to be used as Ring Control Block. It is the first step when initializing a Ring Control buffer. This routine allows the implementation to hide the internal structure of a Ring Control Block, but still allow the user to control its allocation.

int rng_wait (  struct block *    block, unsigned char *volatile *    rrd, unsigned char *    rd, int    needed, int    timeout )  [inline, static]

Blocks the requestor until enough memory is returned to satisfy the request or until timeout period expires. Parameters: block  The blocking control structure rrd  The address of read pointer rd  The current value of the read pointer needed  The amount of memory needed timeout  The timeout period Returns: A pointer to the memory if successful, or NULL if the timeout period has expired.

void rng_wake (  struct block *    block, int    freeing )  [inline, static]

Awakens an allocator if freeing the specified amount has a chance of satisfying the request. Parameters: block  The blocking control structure freeing  The number of bytes being freed

void * RNG_wr (  const struct _RNG_rcb *    rcb )

Query routine to return a pointer to the current write pointer. Parameters: rcb  The Ring Control Block Returns: The value of the current write pointer This routine is primarily used for debugging purposes. Warning: Whereas many of the other query routines return pointers or values that are static and valid once the ring buffer has been initialized, this pointer is dynamic. Let the user beware.

---