<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
<TITLE>RVM: Recoverable Virtual Memory, Release 1.3: RDS, A Dynamic Heap Allocator for RVM </TITLE>
<LINK HREF="rvm_manual-7.html" REL=next>
<LINK HREF="rvm_manual-5.html" REL=previous>
<LINK HREF="rvm_manual.html#toc6" REL=contents>
</HEAD>
<BODY>
<A HREF="rvm_manual-7.html">Next</A>
<A HREF="rvm_manual-5.html">Previous</A>
<A HREF="rvm_manual.html#toc6">Contents</A>
<HR>
<H2><A NAME="RDS"></A> <A NAME="s6">6. RDS, A Dynamic Heap Allocator for RVM </A></H2>
<P><EM>Designed and programmed by David C. Steere</EM>
<P>
<H2><A NAME="ss6.1">6.1 Introduction to RDS</A>
</H2>
<P>
<P>
<P>The Recoverable Dynamic Storage (RDS) library provides
a heap similar to that of the C library, although with persistence,
for RVM segments.
Additional provisions for convenient initialization and reloading of
the heap after shutdown or crash are included.
<P>RDS uses the Quick Fit method </I>] for allocation.
In this method, separate free lists are maintained for a specified
number of sizes. Most programs tend to repeatedly allocate a small
number of distinct sized blocks. Quick Fit avoids overhead by
retaining those block sizes as long as possible in the expectation
that they will be re-allocated when freed. Coalescing of adjacent
free blocks is deferred until a request cannot be satisfied.
<P>The free list sizes are integer multiples of the
<EM>chunk size</EM>, which is specified when the recoverable heap is created
and cannot be modified thereafter except by re-initializing the heap.
The chunk size must be an integral multiple of <CODE>sizeof (char *)</CODE>, and
be at least <CODE>RDS_MIN_CHUNK_SIZE</CODE>.
The free lists are maintained in sizes of one chunk to <EM>n</EM> chunks,
where <EM>n</EM> is the maximum number of free lists. The
number of lists is also specified at heap creation and cannot be
modified thereafter.
<P>When an allocation request is made, the requested size is rounded up
to an integral multiple of the chunk size. The free list for that size
is checked first, and if not empty, the first block is returned.
Otherwise, the next larger free list is checked, and if not empty, the
first block is selected, the requested size split off, and the
remainder placed on the appropriate free list. If the free list is
empty, the next is searched. If no specific-sized free list can
allocate the block, the request is taken from the single list of larger
blocks by splitting the first block on the list. The remainder is
returned to the appropriate free list.
Sizes larger than <EM>n</EM> times the chunksize are also
allocated from the large blocks list on a first-fit basis.
This list is always created in addition to the fixed size lists.
<P>When a block is freed, it is simply placed on the appropriate free
list with no attempt coalesce it with adjacent free blocks.
Coalescing is deferred until an allocation request
can not be satisfied.
<P>The allocation and deallocation functions, rds_malloc and
rds_free, resemble malloc and
free, although they are modified for transactions.
To help prevent fragmentation, RDS also provides for pre-allocation of
pools of block sizes that the
application will repeatedly allocate with the function
rds_prealloc.
<P>The function rds_load_heap provides a convenient way to use the
RVM segment loader to
load the persistent heap and a statically allocated region.
rds_load_heap will make the necessary RVM mapping
calls and initialize RDS. When it completes, the
allocations persistent data is ready for use.
<P>Initialization of an RDS heap is done with the function
rds_init_heap. A second function, rds_zap_heap, which calls
rds_init_heap and rvm_create_segment, can be used to prepare a
segment for loading via rds_load_heap. However, heap
initialization is usually done with the utility rdsinit, which
will prompt for the necessary parameters to call rds_zap_heap.
<P>To assist in detecting buffer overruns and other memory clobbers, RDS
puts special <EM>guard</EM> constants at the beginning and end of each
block. These are not within the space allocated to satisfy an
allocation request and will never be addressed by a correctly
operating application. The rounding up of allocation request sizes to
integral multiples of the chunk size automatically includes
space for the guard constants.
<P>If memory damage is detected by the corruption
of one of the guards when a block is deallocated, or when damage to a
free list is detected during allocation, the error code
ECORRUPT is returned. If this error is detected during
deallocation, the block is not put on a free list, but is left
unmodified for analysis of how the overwrite occurred.
<P>RDS generally returns error indications in a parameter whose address
must be specified in the call. However, a few functions return the
error code as their value. RDS error codes are all defined as
negative integers in rds.h. Because RDS must perform its actions
via transactions, the RVM error codes can also be returned in the error
code parameter or as function values. These are defined in <CODE>rvm.h</CODE>,
and are all positive values. Success is always indicated by the code
SUCCESS, which is defined to be zero.
<P>The header file giving all necessary definitions for RDS is
included in Appendix
<A HREF="rvm_manual-10.html#RVMheaders">of C declarations</A>.
<P>
<H2><A NAME="ss6.2">6.2 Transactions and RDS</A>
</H2>
<P>
<P>All functions in RDS use RVM transactions. Some, particularly
rds_malloc and rds_free, must interact with the applications
transactions, requiring some care from the caller.
RDS does not hold its lock until after commit so that greater concurrency
can possibly be achieved in Coda. This is not generally recommended
because it permits uncommitted state to be
used by other than the calling transaction.
See the notes on good programming practice with RVM, Section
<A HREF="rvm_manual-2.html#GoodLocking">of Transactions in Critical Sections</A>.
<P>Since the lock is not held until commit, some additional
complexity must be introduced to insure that allocation and
deallocation actions are independent.
There are two cases that must be recognized: if the caller
guarantees that no context swaps among application threads
will occur before transaction commit, and if such swaps must be allowed.
<P>If context swapsare avoided, the application can supply the
transaction to be
used by RDS in the allocation/deallocation calls and be sure that if the
transaction must later be aborted, all will be restored correctly.
The transaction must be started in restore mode, which is required
for all RDS calls.
The transaction will not be committed or aborted by RDS.
<P>If context swaps must be allowed (frequently the case), a null
transaction parameter must be specified. This will force an internal
transaction to be created by RDS.
This transaction will be committed by RDS before the function returns.
In this case, if <CODE>rds_malloc</CODE> is called and
the application transaction requesting the allocation must abort, the
block must be explicitly deallocated by a call to rds_free.
Otherwise, recoverable heap space will be lost.
<P>When the application deallocates blocks in a transaction
that could later abort and context swaps are possible, two special
functions are provided,
rds_fake_free and rds_do_free. These functions manage an
<EM>intention list</EM> that records the intended deallocations, but defers
the actual deallocation until the application transaction is ready to
commit. If the transaction aborts, the intention list is discarded.
The application must call rds_fake_free at the point where
the block would logically be freed, and then
call rds_do_free
immediately before committing the application transaction.
The application must provide the intention list header, of type
<CODE>intentionList_t</CODE>; RDS will manage the actual list.
<P>Note that these methods are safe <EM>only</EM> in a coroutine thread
environment. If pre-emptive threads, or a multiprocessor, are required,
RDS cannot safely be used.
<P><HR>
<P>
<P>
NAME
<H3><A HREF="rvm_manual-2.html#GoodLocking">of Transactions in Critical Sections</A></H3>
<P>rds_malloc - allocate from recoverable heap
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_malloc (size, tid, err);
unsigned long size; /* length of allocation request */
rvm_tid_t *tid; /* optional pointer to transaction identifier */
int *err; /* pointer to error return location */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rds_malloc</CODE> allocates from the recoverable heap a block large
enough to hold the request, specified in bytes by the <CODE>size</CODE> parameter.
The address of the allocated block is returned as type
<CODE>int</CODE> and must be cast to the desired type.
If the request cannot be satisfied, zero is returned, and the <CODE>err</CODE>
parameter is set to the appropriate error code.
<P>Because allocation actions in the recoverable heap must be done
via transactions, <CODE>rds_malloc</CODE> offers two choices for the transaction.
In the first case, <CODE>rds_malloc</CODE> can be instructed to use an existing
transaction begun in <CODE>restore</CODE> mode, by passing the address of a
valid <CODE>rvm_tid_t</CODE> record in the <CODE>tid</CODE> parameter.
This avoids extra transaction start and commit
overhead and provides automatic deallocation if the transaction must
later abort.
However, no context swap can be permitted between allocation and
transaction commit or abort since the
modified, but uncommitted, free lists are visible to other RDS actions.
<P>If context swaps cannot be prohibited, or the available transaction was
started in <CODE>no_restore</CODE> mode, the <CODE>tid</CODE> parameter should be
set to null, instructing <CODE>rds_malloc</CODE> to start an internal
transaction.
This transaction will be committed in <CODE>no_flush</CODE> mode if the
allocation is made, and aborted otherwise.
In this case, an explicit <CODE>rds_free</CODE> must be done if the allocating
transaction later aborts.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>ENO_ROOM</B><DD><P>RDS heap exhausted
<DT><B>ECORRUPT</B><DD><P>RDS heap damaged
<DT><B>EHEAP_INIT</B><DD><P>RDS not initialized
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_free (3)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
BUGS
<H3></H3>
<P>The internal synchronization is not valid with pre-emptive threads.
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_free - return a block to the recoverable heap
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_free (addr, tid, err)
char *addr; /* address of block to be freed */
rvm_tid_t *tid; /* optional pointer to transaction identifier */
int *err; /* pointer to error return location */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rds_free</CODE> deallocates recoverable storage allocated by <CODE>rds_malloc</CODE>.
The block to be deallocated is passed in the <CODE>addr</CODE> parameter. This
block must not already be free, or the <CODE>EFREED_TWICE</CODE> error
code will be returned in <CODE>err</CODE>.
<P>Because deallocation actions in the recoverable heap must be done via
transactions, <CODE>rds_free</CODE> offers two choices for the transaction.
In the first case, <CODE>rds_free</CODE> can be instructed to use an existing
transaction by passing the address of a valid <CODE>rvm_tid_t</CODE> record in
the <CODE>tid</CODE> parameter. This avoids extra transaction start and commit
overhead and provides automatic reallocation if the transaction must
later abort.
<P>If the available transaction was started in <CODE>no_restore</CODE> mode, the
<CODE>tid</CODE> parameter should be set to null, instructing <CODE>rds_free</CODE> to
start an internal transaction.
This transaction will be committed in <CODE>no_flush</CODE> mode if the
allocation is made, and aborted otherwise.
<P>In neither case can context swaps be permitted between deallocation and
transaction commit or abort since the modified, but uncommitted, free lists are visible to other RDS actions.
If this condition cannot be met, or if there is a
possibility that the transaction will abort, the functions
<CODE>rds_fake_free</CODE> and <CODE>rds_do_free</CODE> must be used.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>EFREED_TWICE</B><DD><P>block is already free
<DT><B>ECORRUPT</B><DD><P>RDS heap damaged
<DT><B>EBAD_ARGS</B><DD><P>block is not on 4 byte boundary
<DT><B>EHEAP_INIT</B><DD><P>RDS not initialized
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_malloc (3)</CODE>, <CODE>rds_fake_free (3)</CODE>, <CODE>rds_do_free (3)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
BUGS
<H3></H3>
<P>The internal synchronization is not valid with pre-emptive threads.
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_fake_free - deferred return of blocks to the recoverable heap
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
typedef struct intlist {
unsigned long size;
unsigned long count;
char **table;
} intentionList_t;
int rds_fake_free(addr, list);
char *addr; /* address of block to be freed */
intentionList_t *list; /* pointer to intention list */
int rds_do_free(addr, list);
intentionList_t *list; /* pointer to intention list */
rvm_mode_t mode; /* transaction commit mode */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P>In cases where the application must free recoverable storage without
knowing whether the transaction will later abort, <CODE>rds_free</CODE> should
not be used since the internal free list lock is not held until commit
or abort.
To handle these cases, RDS allows the creation of an <EM>intention
list</EM> for the blocks to be freed. At the point where the block would
logically be freed, <CODE>rds_fake_free</CODE> is called to place the block on
the intention list.
To actually free the blocks on the intention list, <CODE>rds_do_free</CODE> is
called. This must be done immediately before calling
<CODE>rvm_end_transaction</CODE> for the deallocating transaction, and must not
be done if
<CODE>rvm_abort_transaction</CODE> is called. Also, no context swaps can be
allowed between the calls on <CODE>rds_do_free</CODE> and <CODE>rvm_end_transaction</CODE>.
<P>The intention list header (type <CODE>intentionList_t</CODE>) must be provided
by the application. The <CODE>table</CODE>
field must be null on the first call to <CODE>rds_fake_free</CODE>. RDS will
allocate space as necessary for the blocks to be freed.
<CODE>rds_do_free</CODE> will deallocate the <CODE>table</CODE> vector. The application
is responsible for deallocation of <CODE>table</CODE> if the transaction is
aborted. Deallocation of the <CODE>intentionList_t</CODE> itself is always the
responsibility of the application.
RDS does not internally synchronize access to the intention list.
If more than one thread is involved in the transaction,
synchronization of access to the intention list is the responsibility
of the application.
<P>The block to be deallocated is passed in the <CODE>addr</CODE> parameter to
<CODE>rds_fake_free</CODE> . This
block must not already be free, or the <CODE>EFREED_TWICE</CODE> error
code will be returned.
The <CODE>ECORRUPT</CODE> error return is given by <CODE>rds_fake_free</CODE> if the
block guards are damaged. <CODE>rds_do_free</CODE> returns this code if
internal damage to the free lists is found.
<P>These functions return error codes as the
value of the function rather than in a parameter.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>EFREED_TWICE</B><DD><P>block is already free
<DT><B>ECORRUPT</B><DD><P>block or heap damaged
<DT><B>EBAD_ARGS</B><DD><P>block is not on 4 byte boundary
<DT><B>EHEAP_INIT</B><DD><P>RDS not initialized
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_free (3)</CODE>, <CODE>rds_malloc (3)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_init_heap - initialize a recoverable heap
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_init_heap (base, length, chunkSize, nlists, tid, err)
char *base; /* base address of heap */
unsigned long length; /* length of heap */
unsigned long chunkSize; /* size of allocation unit */
unsigned long nlists; /* number of allocation lists */
rvm_tid_t *tid; /* pointer to transaction identifier */
int *err; /* pointer to error return location */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rds_init_heap</CODE> initializes a recoverable heap in the previously
mapped memory region specified by the address <CODE>base</CODE> and <CODE>length</CODE>
parameters.
Allocation requests will be rounded up to an integral number of
allocation units <CODE>chunkSize</CODE>, which is specified in bytes, and must
be an integral multiple of <CODE>sizeof (char *)</CODE>, and be at least
<CODE>RDS_MIN_CHUNK_SIZE</CODE>.
<P>For rapid allocation, RDS maintains separate allocation lists for
blocks of different sizes. The sizes are integrals of <CODE>chunkSize</CODE>,
beginning with 1 and extending to the number of lists specified by
<CODE>nlists</CODE>, which must be at least <CODE>RDS_MIN_FREE_LISTS</CODE>. These
lists are initially empty and the entire heap is
placed on the large block list as a single block. <CODE>rds_malloc</CODE> will
split this block as required.
<P>If a number of blocks of specific sizes are required by the
application, the function <CODE>rds_prealloc</CODE> is provided for efficient
pre-allocation. It should be called immediately after initializing
the heap.
<P>An active transaction must be specified in the <CODE>tid</CODE> parameter; RDS
will not create an internal transaction for this function.
This transaction must be committed by the application for the
initialization to be permanent.
<P>Since this function is called only to initialize the heap, RDS assumes
there is no concurrent access and does no internal locking.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>ENO_ROOM</B><DD><P>heap length not long enough for heap structures
<DT><B>EBAD_CHUNK_SIZE</B><DD><P>the chunk size is not large enough or is not a
multiple of sizeof(char *)
<DT><B>EBAD_LIST_LENGTH</B><DD><P>the number of free lists is not at least
RDS_MIN_FREE_LISTS
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_zap_heap (3)</CODE>, <CODE>rds_prealloc (3)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_load_heap, rds_start_heap - map recoverable storage
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_load_heap (DevName, DevLength, staticAddr, err);
char *DevName; /* name of heap segment */
rvm_length_t DevLength; /* length of heap raw partition */
char **staticAddr; /* address of static region (out)*/
int *err; /* pointer to error return location */
int rds_start_heap (staticAddr, err);
char **staticAddr; /* address of static region (out)*/
int *err; /* pointer to error return location */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rds_load_heap</CODE> provides a convenient method of mapping the heap
segment and initializing RDS. The name of the file or partition
containing the recoverable heap is specified by <CODE>DevName</CODE>, and the
length of the partition is specified in <CODE>DevLength</CODE>. If the heap
is in a file, <CODE>DevLength</CODE> should be zero.
<P><CODE>rds_load_heap</CODE> calls <CODE>rvm_load_segment</CODE> to map the heap. This
requires that the heap file or partition be created with
<CODE>rds_zap_heap</CODE> or <CODE>rvm_create_segment</CODE>, which is most conveniently
done with the <CODE>rdsinit</CODE> utility.
After the heap is mapped, the address of the static region is returned
in <CODE>staticAddr</CODE>. <CODE>rds_start_heap</CODE> is automatically called to
initialize RDS.
<P>If the actual mapping of the heap and static regions is done by the
application, <CODE>rds_start_heap</CODE> should be used to initialize RDS. In this
case, the address of the static region must be specified to RDS in the
<CODE>staticAddr</CODE> parameter.
<P>With either function, the version of RDS that the heap was built with
is compared with the version of the currently linked RDS library.
If there is a mismatch, the error code <CODE>EHEAP_VERSION_SKEW</CODE> is returned.
<P>Since these functions are called only to initialize the application,
RDS assumes there is no concurrent access and does no internal locking.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>EHEAP_VERSION_SKEW</B><DD><P>RDS heap and library have different versions
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rvm_load_segment (3)</CODE>, <CODE>rvm_map (3)</CODE>, <CODE>rdsinit (1)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_zap_heap - initialize an RVM segment as an RDS heap
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_zap_heap (DevName, DevLength, startAddr, staticLength,
heapLength, nlists, chunkSize, err)
char *DevName; /* name of heap segment */
rvm_length_t DevLength; /* length of heap raw partition */
char *startAddr;/* base address of heap */
rvm_length_t staticLength; /* length of static region */
rvm_length_t heapLength;/* length of heap region */
unsigned long nlist; /* number of allocation lists */
unsigned long chunkSize; /* size of allocation unit */
int *err; /* pointer to error return location */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rds_zap_heap</CODE> prepares a recoverable heap for loading by
<CODE>rds_load_heap</CODE>. Two regions are created in the heap segment named
by <CODE>DevName</CODE>, one for the applications statically allocated region
and one for the recoverable heap.
The lengths of the regions, specified by <CODE>staticLength</CODE> and
<CODE>heapLength</CODE>, must be integrals of the system page size. The heap
region is allocated at <CODE>*startAddr</CODE> in virtual memory, which must be
on a page
boundary. This address is the permanent address of the heap. The
static region starts at <CODE>*startAddr</CODE> + <CODE>heapLength</CODE> and is also
permanent. One additional region is created at the beginning of the
segment for the segment header, and is one page long. This region is
only temporarily mapped by <CODE>rds_load_heap</CODE>. The heap region follows
the header in the segment, and the static region follows the heap.
<P>If the segment is represented by a raw partition, the maximum usable
length of the partition must be specified in <CODE>DevLength</CODE>. For
files, this length should be zero.
<P>The region of virtual memory for the heap and static regions should
not be allocated by the application. <CODE>rds_zap_heap</CODE> uses the RVM
segment utilities to build the segment header and map the regions.
When <CODE>rds_zap_heap</CODE> is complete, the memory will be mapped.
<P><CODE>rds_zap_heap</CODE> uses <CODE>rvm_create_segment</CODE> to build the segment, and
then calls <CODE>rds_init_heap</CODE> to initialize the free
lists as specified by the <CODE>nlists</CODE> and <CODE>chunkSize</CODE> parameters.
<CODE>chunkSize</CODE> is specified in bytes, and must
be an integral multiple of <CODE>sizeof (char *)</CODE>, and be at least
<CODE>RDS_MIN_CHUNK_SIZE</CODE>. The number of free lists must be at least
<CODE>RDS_MIN_FREE_LISTS</CODE>.
The transaction required by <CODE>rds_init_heap</CODE> is created and
terminated internally.
<P>If a number of blocks of specific sizes are required by the
application, the function <CODE>rds_prealloc</CODE> is provided for efficient
pre-allocation. It should be called immediately after initializing
the heap.
<P>The utility <CODE>rdsinit</CODE> is usually used to create recoverable heap
segments. It prompts for the parameters and calls <CODE>rds_zap_heap</CODE>.
<P>Since this function is called only to initialize the heap, RDS assumes
there is no concurrent access and does no internal locking.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>ENO_ROOM</B><DD><P>heap length not long enough for header
<DT><B>EBAD_CHUNK_SIZE</B><DD><P>the chunk size is not large enough or is not a
muliple of <CODE>sizeof(char *)</CODE>
<DT><B>EBAD_LIST_LENGTH</B><DD><P>the number of free lists is not at least
<CODE>RDS_MIN_FREE_LISTS</CODE>
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_init_heap (3)</CODE>, <CODE>rds_load_heap (3)</CODE>, <CODE>rvm_create_segment (3)</CODE>,
<CODE>rvm_load_segment (3)</CODE>, <CODE>rdsinit (1)</CODE>, <CODE>rds_prealloc (3)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_prealloc - initialize allocation pools
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_prealloc (size, nblocks, tid, err)
unsigned long size; /* size of allocation request */
unsigned long nblocks; /* length of allocation request */
rvm_tid_t *tid; /* pointer to transaction identifer */
int *err; /* pointer to error return location */
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rds_prealloc</CODE> assists applications in minimizing heap fragmentation
by pre-allocating pools of blocks in sizes that the application is
known to use in relatively large numbers.
<CODE>rds_prealloc</CODE> is best called immediately after the heap is
initialized, although it can be called anytime.
When pools of several block sizes are pre-allocated, they should be
allocated in increasing block size order so that the larger blocks are
not split to make the smaller.
<P>The <CODE>size</CODE> parameter specifies the size, in bytes, of the blocks to
be pre-allocated, and <CODE>nblocks</CODE> controls the number of blocks
pre-allocated.
<P>Because allocation actions in the recoverable heap must be done via
transactions, <CODE>rds_prealloc</CODE> offers two choices for the transaction.
In the first case, <CODE>rds_prealloc</CODE> can be instructed to use an existing
transaction begun in <CODE>restore</CODE> mode, by passing the address of a
valid <CODE>rvm_tid_t</CODE> record in the <CODE>tid</CODE> parameter.
This avoids extra transaction start and commit
overhead and provides automatic deallocation if the transaction must
later abort.
However, no context swap can be permitted between allocation and
transaction commit or abort since the uncommitted state is visible to
other allocations.
<P>If context swaps cannot be prohibited, or the available transaction was
started in <CODE>no_restore</CODE> mode, the <CODE>tid</CODE> parameter should be
set to null, instructing <CODE>rds_prealloc</CODE> to start an internal
transaction.
This transaction will be committed in <CODE>no_flush</CODE> mode if the
allocation is made, and aborted otherwise.
In this case, if the allocating
transaction later aborts, the pre-allocated blocks remain allocated.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>ENO_ROOM</B><DD><P>RDS heap exhausted
<DT><B>ECORRUPT</B><DD><P>RDS heap damaged
<DT><B>EHEAP_INIT</B><DD><P>RDS not initialized
<DT><B>positive values</B><DD><P>RVM return codes
</DL>
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_malloc(3)</CODE>, <CODE>rds_init_heap(3)</CODE>, <CODE>rds_zap_heap(3)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
BUGS
<H3></H3>
<P>The internal synchronization is not valid with pre-emptive threads.
<P>
<P>
<HR>NAME
<H3></H3>
<P>rds_get_stats, rds_clear_stats, rds_print_stats - RDS statistics functions
<P>
SYNOPSIS
<H3></H3>
<P>
<PRE>
#include "rds.h"
int rds_get_stats (stats);
rds_stats_t *stats; /* pointer to RDS statistics record */
int rds_clear_stats (err);
int *err; /* pointer to error return location */
int rds_print_stats();
</PRE>
<P>
DESCRIPTION
<H3></H3>
<P>RDS maintains simple statistics about the recoverable heap and the
allocations performed. The statistics area is kept in the recoverable
heap region and is initialized when the heap is initialized.
<P>The statistics can be read by <CODE>rds_get_stats</CODE> into an <CODE>rds_stats_t</CODE>
record for analysis by the application, or printed on <CODE>stdout</CODE> by
<CODE>rds_print_stats</CODE>.
<CODE>rds_get_stats (stats)</CODE> and <CODE>rds_print_stats ()</CODE> return error codes as the
value of the function rather than in a parameter.
<P>After heap initialization, the statistics area can be cleared by
calling <CODE>rds_clear_stats</CODE>.
<CODE>rds_clear_stats</CODE> simply zeroes the statistics area via an internal
transaction. The space
allocated and free counts will not be accurate if it is called after
initializing the RDS heap. Note that <CODE>rds_clear_stats</CODE> requires an
error return code as a parameter, while the others return the error
status as the function value.
<P>RDS performs no internal synchronization for these calls, so if there
is a possibility of concurrent access to the statistics, the accesses
must be serialized by the application.
<P>
<P>
DIAGNOSTICS
<H3></H3>
<P>
<DL>
<DT><B>SUCCESS</B><DD><P>success
<DT><B>EHEAP_INIT</B><DD><P>RDS not initialized
<DT><B>EBAD_ARGS</B><DD><P>null RDS statistics record pointer
</DL>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere
<P>
<P>
<HR>NAME
<H3></H3>
<P>rdsinit - RDS heap initialization utility
<P>
SYNOPSIS
<H3></H3>
<P>
<P><B>rdsinit</B> <EM>log</EM> <EM>data_seg</EM>
<P><B>rdsinit</B> <EM>log</EM> <EM>data_seg</EM> <EM>datalen</EM> <EM>saddr</EM>
<EM>hlen</EM> <EM>slen</EM> <EM>nl</EM> <EM>chunk</EM>
<P><B>rdsinit</B> <EM>-f</EM> <EM>log</EM> <EM>data_seg</EM> <EM>datalen</EM> <EM>saddr</EM>
<EM>hlen</EM> <EM>slen</EM> <EM>nl</EM> <EM>chunk</EM>
<P>
<P>
DESCRIPTION
<H3></H3>
<P><CODE>rdsinit</CODE> is a utility that constructs an initialized RDS heap in an
RVM segment. It is intended to create a structure that can be loaded
by <CODE>rds_load_heap</CODE>.
<P>There are three different ways of using rdsinit. General users are
expected to use first two interactive modes, where users may supply
parameters for the rds heap interactively or on command line
arguments. However, in both cases, users will be asked interactively
to confirm their choice of parameters before rdsinit goes ahead to
make any permanent change. These are the preferred modes of using
rdsinit. Script writers, however, may prefer to supply all the
parameters on the command line and <EM>no</EM> confirmation required for
those parameters. This is accomodate in the third mode where an
additional switch of -f (firm) is supplied on the command line.
<P>In any case, two command-line parameters are always
required: <CODE>log</CODE> and <CODE>data_seg</CODE>. The former is the name of the
RVM log, which must have previously been initialized by
<CODE>rvmutl</CODE>; the latter is the name of the data segment that will
be initialized with an RDS heap. If either is missing, a command line
error is printed. If the log has not been initialized, an RVM error
will result. A short message indicating RVM initialization succeeded
is then printed. Both the log and data segment can be regular files or
raw partitions.
<P>After the name of log and data segment, there are six other numeric
parameters required. They are summarized here and will be
explained one by one in the following paragraphs:
<P>
<DL>
<DT><B>datalen</B><DD><P>Length of data segment
<DT><B>saddr</B><DD><P>Starting address of rvm
<DT><B>hlen</B><DD><P>Heap region length
<DT><B>slen</B><DD><P>Static region length
<DT><B>nl</B><DD><P>Number of lists of free block
<DT><B>chunk</B><DD><P>Chunk size
</DL>
<P>While entering these six numeric parameters, either on command line on
via the interactive prompt, users may use numeric number in
hexadecimal, decimal or even octal notation. Hexadecimal numbers are
preceeded by <CODE>Ox</CODE>, decimal numbers are preceeded by nothing and
octal numbers are preceded by <CODE>0</CODE>.
<P>Special note for long time rdsinit user: the old rdsinit automatically
assumed <CODE>saddr</CODE>, <CODE>hlen</CODE> and <CODE>slen</CODE> parameters supplied on
command lines are in hexidecimal and <EM>did not</EM> require the prefix
<CODE>0x</CODE>. <EM>This is no longer true with this version of rdsinit.</EM>
<P>Users specify the length of the data segment with the parameter
<EM>datalen</EM>. Again, old version of rdsinit did not require this
parameter if the data segment was a regular file and it existed
already at the time of running rdsinit. This special case is
eliminated: <EM>length of data segment must to be supplied in all
circumstances.</EM>
<P>Starting address of rvm, or <EM>saddr</EM>, is where heap and static
region will be mapped into virtual memory. Heap region is located
right at the starting address, while static region is located at
starting address plus heap region length. Users may need to have some
knowledges of the overall layout of the virtual memory use by the
system before they can make the right choice of starting address. For
example, the starting address of rvm must be much larger than the
largest possible break point of your application, and it should not be
in conflict other uses of virtual memory (such as use by shared
libraries). It must also be on a page boundary. In CMU, we use
0x20000000 (536870912) with Linux and BSD44, or 0x70000000 (1879048192)
with Mach. It is possible to choose other values, but you have to
choose them carefully.
<P>Length of regions of heap and static are specified by the parameter
<EM>hlen</EM> and <EM>slen</EM> respectively. They both must be integral
multiple of pagesize of the system. Also, the combined length of the
two regions must be smaller than the length of data segment minus one
extra page.
<P>Note that the above three parameters: saddr, hlen, slen, are
permanent. They can't be changed without re-initizing (and
brain-wiping) the data segment.
<P>The next two parameters: <EM>nl</EM> and <EM>chunk</EM> are related to
underlying structure of management of the heap. RDS uses the Quick
Fit method for heap allocation. In this method, free blocks are
maintained by a number of free lists, each list for one particular
size of free blocks. Specifically, there will be <CODE>nl</CODE> free lists,
and each of them will have free blocks of size <CODE>1..nl</CODE> chunk
respectively.
<P>Chunk size must be integral multiple of <CODE>sizeof(char *)</CODE>, and be at
least <CODE>RDS_MIN_CHUNK_SIZE</CODE>. Number of lists must be at least
<CODE>RDS_MIN_FREE_LISTS</CODE>. For example, a reasonable choice is to have
100 free list with chunk size 32 bytes.
<P>Once all the parameters are chosen, rdsinit will ask user for
confirmation before it goes ahead and make permanent change on the log
and data segment. Note in the following example that those numerical
arguments are presented in both hexidecimal and decimal (in bracket).
It is safe to quit at this point and no permanent changes will be made.
<PRE>
The following parameters are chosen:
length of data segment: 0xf5000 ( 1003520)
starting address of rvm: 0x20000000 ( 536870912)
heap len: 0xf0000 ( 983040)
static len: 0x4000 ( 16384)
nlists: 0x64 ( 100)
chunk size: 0x20 ( 32)
Do you agree with these parameters ? (y|n|q) y
</PRE>
<P>If user supplied the -f (firm) switch on command line, this last
confirmation will not show up.
<P>
<P>
SEE ALSO
<H3></H3>
<P><CODE>rds_init_heap (3)</CODE>, <CODE>rds_load_heap (3)</CODE>, <CODE>rds_zap_heap (3)</CODE>,
<CODE>rvm_create_segment (3)</CODE>, <CODE>rvm_load_segment (3)</CODE>, <CODE>rvmutl (1)</CODE>
<P>
<P>
AUTHOR
<H3></H3>
<P>David C. Steere, created man page
<P>Yui W. Lee, modified (Sept 1997)
<P>
<P>
<HR>
<HR>
<A HREF="rvm_manual-7.html">Next</A>
<A HREF="rvm_manual-5.html">Previous</A>
<A HREF="rvm_manual.html#toc6">Contents</A>
</BODY>
</HTML>
distrib
>
Mandriva
>
8.2
>
i586
>
media
>
contrib
>
by-pkgid
>
211238da6d926d1ca4390483bb29f586
>
files
>
72
