\hypertarget{RNG_8c}{ \section{RNG.c File Reference} \label{RNG_8c}\index{RNG.c@{RNG.c}} } Utility for configuring a pool of memory as a ring buffer. {\tt \#include $<$stdio.h$>$}\par {\tt \#include \char`\"{}BBC/RNG.h\char`\"{}}\par {\tt \#include \char`\"{}BBC/BUG.h\char`\"{}}\par \subsection*{Data Structures} \begin{CompactItemize} \item struct {\bf \_\-RNG\_\-rcb} \end{CompactItemize} \subsection*{Defines} \begin{CompactItemize} \item \hypertarget{RNG_8c_a0}{ \index{NULL@{NULL}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!NULL@{NULL}} \#define \hyperlink{RNG_8c_a0}{NULL}\ ((unsigned char $\ast$)0)} \label{RNG_8c_a0} \begin{CompactList}\small\item\em NULL pointer definition.\item\end{CompactList}\item \hypertarget{RNG_8c_a1}{ \index{RND_TO@{RND\_\-TO}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RND_TO@{RND\_\-TO}} \#define \hyperlink{RNG_8c_a1}{RND\_\-TO}(\_\-ptr, \_\-msk)\ (((unsigned int)(\_\-ptr) + \_\-msk) \& $\sim$\_\-msk)} \label{RNG_8c_a1} \begin{CompactList}\small\item\em Rounds the specified address up to the nearest binary boundary.\item\end{CompactList}\end{CompactItemize} \subsection*{Functions} \begin{CompactItemize} \item void \hyperlink{RNG_8c_a2}{rng\_\-bdestroy} (struct block $\ast$block) \begin{CompactList}\small\item\em Closes the blocking control structure.\item\end{CompactList}\item void \hyperlink{RNG_8c_a3}{rng\_\-binit} (struct block $\ast$block) \begin{CompactList}\small\item\em Initializes the blocking control structure.\item\end{CompactList}\item void \hyperlink{RNG_8c_a4}{rng\_\-wake} (struct block $\ast$block, int freeing) \begin{CompactList}\small\item\em Awakens an allocator if freeing the specified amount has a chance of satisfying the request.\item\end{CompactList}\item int \hyperlink{RNG_8c_a5}{rng\_\-wait} (struct block $\ast$block, unsigned char $\ast$volatile $\ast$rrd, unsigned char $\ast$rd, int needed, int timeout) \begin{CompactList}\small\item\em Blocks the requestor until enough memory is returned to satisfy the request or until timeout period expires.\item\end{CompactList}\item void $\ast$ \hyperlink{RNG_8c_a6}{allocate} (struct \_\-RNG\_\-rcb $\ast$rcb, int minimum, const void $\ast$cur\-Wrt, int $\ast$allocated, int timeout) \begin{CompactList}\small\item\em The underlying workhorse allocator.\item\end{CompactList}\item \hypertarget{RNG_8c_a7}{ \index{RNG_buf@{RNG\_\-buf}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_buf@{RNG\_\-buf}} void $\ast$ {\bf RNG\_\-buf} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a7} \item \hypertarget{RNG_8c_a8}{ \index{RNG_bsize@{RNG\_\-bsize}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_bsize@{RNG\_\-bsize}} int {\bf RNG\_\-bsize} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a8} \item \hypertarget{RNG_8c_a9}{ \index{RNG_beg@{RNG\_\-beg}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_beg@{RNG\_\-beg}} void $\ast$ {\bf RNG\_\-beg} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a9} \item \hypertarget{RNG_8c_a10}{ \index{RNG_rbeg@{RNG\_\-rbeg}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_rbeg@{RNG\_\-rbeg}} void $\ast$ {\bf RNG\_\-rbeg} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a10} \item \hypertarget{RNG_8c_a11}{ \index{RNG_rend@{RNG\_\-rend}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_rend@{RNG\_\-rend}} void $\ast$ {\bf RNG\_\-rend} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a11} \item \hypertarget{RNG_8c_a12}{ \index{RNG_end@{RNG\_\-end}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_end@{RNG\_\-end}} void $\ast$ {\bf RNG\_\-end} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a12} \item \hypertarget{RNG_8c_a13}{ \index{RNG_rd@{RNG\_\-rd}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_rd@{RNG\_\-rd}} void $\ast$ {\bf RNG\_\-rd} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a13} \item \hypertarget{RNG_8c_a14}{ \index{RNG_wr@{RNG\_\-wr}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_wr@{RNG\_\-wr}} void $\ast$ {\bf RNG\_\-wr} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a14} \item \hypertarget{RNG_8c_a15}{ \index{RNG_shard@{RNG\_\-shard}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_shard@{RNG\_\-shard}} void $\ast$ {\bf RNG\_\-shard} (const struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a15} \item \hypertarget{RNG_8c_a16}{ \index{RNG_destroy@{RNG\_\-destroy}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_destroy@{RNG\_\-destroy}} int {\bf RNG\_\-destroy} (struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a16} \item \hypertarget{RNG_8c_a17}{ \index{RNG_sizeof_rcb@{RNG\_\-sizeof\_\-rcb}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_sizeof_rcb@{RNG\_\-sizeof\_\-rcb}} int {\bf RNG\_\-sizeof\_\-rcb} ()} \label{RNG_8c_a17} \item \hypertarget{RNG_8c_a18}{ \index{RNG_init@{RNG\_\-init}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_init@{RNG\_\-init}} int {\bf RNG\_\-init} (struct \_\-RNG\_\-rcb $\ast$rcb, unsigned char $\ast$buf, int size, int underflow, int overflow, int alignment, \hyperlink{RNG_8h_a3}{RNG\_\-type} blocking)} \label{RNG_8c_a18} \item \hypertarget{RNG_8c_a19}{ \index{RNG_get@{RNG\_\-get}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_get@{RNG\_\-get}} void $\ast$ {\bf RNG\_\-get} (struct \_\-RNG\_\-rcb $\ast$rcb, int request, const void $\ast$nxt\-Wrt)} \label{RNG_8c_a19} \item \hypertarget{RNG_8c_a20}{ \index{RNG_getW@{RNG\_\-getW}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_getW@{RNG\_\-get\-W}} void $\ast$ {\bf RNG\_\-get\-W} (struct \_\-RNG\_\-rcb $\ast$rcb, int request, const void $\ast$nxt\-Wrt, int timeout)} \label{RNG_8c_a20} \item \hypertarget{RNG_8c_a21}{ \index{RNG_grab@{RNG\_\-grab}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_grab@{RNG\_\-grab}} void $\ast$ {\bf RNG\_\-grab} (struct \_\-RNG\_\-rcb $\ast$rcb, int minimum, const void $\ast$nxt\-Wrt, int $\ast$allocated)} \label{RNG_8c_a21} \item \hypertarget{RNG_8c_a22}{ \index{RNG_grabW@{RNG\_\-grabW}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_grabW@{RNG\_\-grab\-W}} void $\ast$ {\bf RNG\_\-grab\-W} (struct \_\-RNG\_\-rcb $\ast$rcb, int minimum, const void $\ast$nxt\-Wrt, int $\ast$allocated, int timeout)} \label{RNG_8c_a22} \item \hypertarget{RNG_8c_a23}{ \index{RNG_free@{RNG\_\-free}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_free@{RNG\_\-free}} int {\bf RNG\_\-free} (struct \_\-RNG\_\-rcb $\ast$rcb, const void $\ast$packet, int amount)} \label{RNG_8c_a23} \item \hypertarget{RNG_8c_a24}{ \index{RNG_shrink@{RNG\_\-shrink}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_shrink@{RNG\_\-shrink}} void $\ast$ {\bf RNG\_\-shrink} (struct \_\-RNG\_\-rcb $\ast$rcb, const void $\ast$new\-Wrt, int left)} \label{RNG_8c_a24} \item \hypertarget{RNG_8c_a25}{ \index{RNG_reset@{RNG\_\-reset}!RNG.c@{RNG.c}}\index{RNG.c@{RNG.c}!RNG_reset@{RNG\_\-reset}} int {\bf RNG\_\-reset} (struct \_\-RNG\_\-rcb $\ast$rcb)} \label{RNG_8c_a25} \end{CompactItemize} \subsection{Detailed Description} Utility for configuring a pool of memory as a ring buffer. \begin{Desc} \item[Author: ]\par JJRussell - \href{mailto:russell@slac.stanford.edu}{\tt russell@slac.stanford.edu}\end{Desc} {\bf IMPLEMENTATION} NOTE 1 \par {\bf ---------------------} \par 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 $\ast$$\ast$legitimate$\ast$$\ast$ reason for the free routine to be called. {\bf IMPLEMENTATION} NOTE 2 \par {\bf ---------------------} \par 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 $\ast$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. \subsection{Function Documentation} \hypertarget{RNG_8c_a6}{ \index{RNG.c@{RNG.c}!allocate@{allocate}} \index{allocate@{allocate}!RNG.c@{RNG.c}} \subsubsection[allocate]{\setlength{\rightskip}{0pt plus 5cm}void $\ast$ allocate (struct \_\-RNG\_\-rcb $\ast$ {\em rcb}, int {\em request}, const void $\ast$ {\em nxt\-Wrt}, int $\ast$ {\em allocated}, int {\em timeout})\hspace{0.3cm}{\tt \mbox{[}static\mbox{]}}}} \label{RNG_8c_a6} The underlying workhorse allocator. \begin{Desc} \item[Parameters: ]\par \begin{description} \item[{\em rcb}]The Ring Control Block \item[{\em minimum}]The minimum number of bytes needed to satisty the request \item[{\em cur\-Wrt}]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. \item[{\em allocated}]If specified as NULL, the allocation is for the amount specified by {\em minimum}. If NON NULL, then the request is satisfied with the all the contigious memory available, provided it is larger than {\em minimum}. The amount of memory allocated is returned in this address. \item[{\em timeout}]A timeout parameter. \end{description} \end{Desc} \begin{Desc} \item[Returns: ]\par If successful, a pointer to the allocated memory. If not, then NULL. \end{Desc} \hypertarget{RNG_8c_a2}{ \index{RNG.c@{RNG.c}!rng_bdestroy@{rng\_\-bdestroy}} \index{rng_bdestroy@{rng\_\-bdestroy}!RNG.c@{RNG.c}} \subsubsection[rng\_\-bdestroy]{\setlength{\rightskip}{0pt plus 5cm}void rng\_\-bdestroy (struct block $\ast$ {\em block})\hspace{0.3cm}{\tt \mbox{[}inline, static\mbox{]}}}} \label{RNG_8c_a2} Closes the blocking control structure. \begin{Desc} \item[Parameters: ]\par \begin{description} \item[{\em block}]The blocking control structure to close \end{description} \end{Desc} \hypertarget{RNG_8c_a3}{ \index{RNG.c@{RNG.c}!rng_binit@{rng\_\-binit}} \index{rng_binit@{rng\_\-binit}!RNG.c@{RNG.c}} \subsubsection[rng\_\-binit]{\setlength{\rightskip}{0pt plus 5cm}void rng\_\-binit (struct block $\ast$ {\em block})\hspace{0.3cm}{\tt \mbox{[}inline, static\mbox{]}}}} \label{RNG_8c_a3} Initializes the blocking control structure. \begin{Desc} \item[Parameters: ]\par \begin{description} \item[{\em block}]The blocking control structure to initialize \end{description} \end{Desc} \hypertarget{RNG_8c_a5}{ \index{RNG.c@{RNG.c}!rng_wait@{rng\_\-wait}} \index{rng_wait@{rng\_\-wait}!RNG.c@{RNG.c}} \subsubsection[rng\_\-wait]{\setlength{\rightskip}{0pt plus 5cm}int rng\_\-wait (struct block $\ast$ {\em block}, unsigned char $\ast$volatile $\ast$ {\em rrd}, unsigned char $\ast$ {\em rd}, int {\em needed}, int {\em timeout})\hspace{0.3cm}{\tt \mbox{[}inline, static\mbox{]}}}} \label{RNG_8c_a5} Blocks the requestor until enough memory is returned to satisfy the request or until timeout period expires. \begin{Desc} \item[Parameters: ]\par \begin{description} \item[{\em block}]The blocking control structure \item[{\em rrd}]The address of read pointer \item[{\em rd}]The current value of the read pointer \item[{\em needed}]The amount of memory needed \item[{\em timeout}]The timeout period \end{description} \end{Desc} \begin{Desc} \item[Returns: ]\par A pointer to the memory if successful, or NULL if the timeout period has expired. \end{Desc} \hypertarget{RNG_8c_a4}{ \index{RNG.c@{RNG.c}!rng_wake@{rng\_\-wake}} \index{rng_wake@{rng\_\-wake}!RNG.c@{RNG.c}} \subsubsection[rng\_\-wake]{\setlength{\rightskip}{0pt plus 5cm}void rng\_\-wake (struct block $\ast$ {\em block}, int {\em freeing})\hspace{0.3cm}{\tt \mbox{[}inline, static\mbox{]}}}} \label{RNG_8c_a4} Awakens an allocator if freeing the specified amount has a chance of satisfying the request. \begin{Desc} \item[Parameters: ]\par \begin{description} \item[{\em block}]The blocking control structure \item[{\em freeing}]The number of bytes being freed \end{description} \end{Desc}