NAME

malloc, free, realloc, calloc, _byte_size, _free, _ALLOC_Id, _ALLOC_StorageInUse, _ALLOC_StorageFree, _ALLOC_FreeBlocks, _ALLOC_ResetBlockMap − memory allocator

SYNOPSIS

#include <stdlib.h>
void ∗malloc(size_t size)

void free(void ∗ptr)

void ∗realloc(void ∗ptr, size_t size)

void ∗calloc(size_t nelem, size_t elsize)

#include <malloc.h>
size_t _byte_size(void ∗ptr)

void _free(void ∗ptr)

const char ∗_ALLOC_Id(void)

int _ALLOC_StorageInUse(void)

int _ALLOC_StorageFree(void)

int _ALLOC_FreeBlocks(size_t size)

int _ALLOC_FreeWordsLarge(void)

int _ALLOC_ResetBlockMap(const unsigned char new[256])

int _ALLOC_Options(int cmd, int value)

_ALLOC_info _ALLOC_Info(void);

DESCRIPTION

Malloc and free provide a general-purpose memory allocation package.  Malloc returns a pointer to a block of at least size bytes beginning on a word boundary. 

The argument to free is a pointer to a block previously allocated by malloc; this space is made available for further allocation, and its contents are altered.

Needless to say, grave disorder will result if the space assigned by malloc is overrun or if a block handed to free is used afterwards.  The storage allocator will spot an attempt to free an invalid pointer and (by default) will output a message on stderr and abort the program via abort(3).

Malloc maintains multiple lists of free blocks according to size, allocating space from the appropriate list.  It calls the equivalent of sbrk and brk (see brk(2)) to get more memory from the system when there is no suitable space already free.  These functions may be used directly if required, but they should normally only be used to permanently allocate large amounts of store − there is some overhead imposed on the storage allocator in dealing with interleaved malloc and sbrk calls (which will lose some storage) and there is no way of freeing the result of a sbrk. The heap limit should never be lowered using brk when malloc has been used as this will certainly cause the allocator to fail.  Interleaved use of sbrk and malloc is not a portable feature − such practices destroy the standard BSD43 allocator. 

Realloc changes the size of the block pointed to by ptr to size bytes and returns a pointer to the (possibly moved) block.  Realloc does not currently reduce the size of the block it is passed − but it may do so in the future. 

Calloc allocates space for an array of nelem elements of size elsize.  The space is initialized to zeros. 

Each of the allocation routines returns a pointer to space suitably aligned (after possible pointer coercion) for storage of any type of object.  If the storage cannot be allocated, or if 0 bytes are requested, both malloc and realloc return NULL.  On such failures the variable errno is set to the value ENOMEM as defined in <errno.h>.

The remaining functions are specific to this implementation of malloc. The header file <malloc.h> defines prototypes for the functions as well as the _ALLOC_Info type (a structure) and various #define values. 

_byte_size returns the size in bytes of the block pointed to by ptr or 0 if the pointer is invalid − it never fails and only returns 0 on an invalid pointer, so may be used to check pointer validity as well as to judge the size of a block. 

_free functions like free except that, when the M_KEEP option is specified (see below) it retains the passed pointer until the next call to _free. If the pointer is equal to the last pointer no action is taken, if it is different it is retained and the storage indicated by the previous pointer is freed using free. This function offers some compatibility with old versions of the BSD and System V storage allocators.

_ALLOC_Id returns a string which indicates the current revision of the storage manager.  The string may not be altered. 

_ALLOC_StorageInUse returns the amount of storage (in bytes) currently used by the system − this includes all of the system overhead which is not statically allocated. 

_ALLOC_FreeBlocks returns the number of blocks of size size words (sizeof (unsigned)) which are currently free.  In the default system overwrite checking consumes one extra word per block, so a request for w words will actually allocate a block of size (w+1).  An indirect consequence of calling _ALLOC_FreeBlocks is that all the free blocks of the given size in the system are checked for validity, thus a successful return from the routine means that the free list for that block size is not corrupt. 

_ALLOC_FreeWordsLarge returns the number of words of free storage currently available in the allocator for requests of size greater than the block map limit.  It also checks the consistency of this allocator. 

_ALLOC_StorageFree returns the total number of bytes of free storage (excluding the overwrite word in each block).  Thus the result of the function is a measure of the available storage when external fragmentation is ignored − external fragmentation of storage means that a request for a given number of bytes may not be satisfied even if it is less than _ALLOC_StorageFree() because there may not be a contiguous region of free store of this size.  Notice that all three of these routines describe the storage currently in the heap − the potential storage available will normally be more as the heap will be extended as required. 

_ALLOC_ResetBlockMap resets the block map of the system.  The block map is a byte array which maps a request for n words into the actual block size (including the overwrite guard word) which will be used to satisfy the request.  The array can be up to 256 bytes long (for requests up to 255 words), however the storage manager is currently built to only manage requests up to a maximum of 126 words in this way.  Requests for more than 126 words (127 words if overwrite checking is compiled out) are allocated separately.  The routine will fail (returning a non-zero value) if it is called after malloc or realloc has been used for the first time otherwise it returns zero indicating success.  It may be used (normally as the very first function call in a program) to tailor the system to the particular pattern of allocations which a program generates.  The default blockmap is suitable for most programs, including programs which do large amounts of allocation and deallocation.  A new blockmap would only be of advantage to a program which had a very unusal pattern of storage allocation.  The function will also fail if the block map is invalid − with the current version of the storage manager this will occur if entry n in the map specifies less than n+1 words, or more than 127 words.  Any entry may specify 0 words (meaning that allocation will be from the separate large block allocator).  Entry 127 must specify zero words, entries beyond 127 are not examined. 

_ALLOC_Options allows control of various features of the storage manager.  The interface is analogous to the System V mallopt function, and the file <malloc.h> contains a #define which defines mallopt as _ALLOC_Options. If any of the System V options are used the storage manager behaviour is reset to resemble a System V storage allocator as closely as possible.  In particular malloc and free calls which fail are no longer faulted and storage corruption is ignored.  If the _ALLOC_Options call fails it returns non-zero, else it returns zero. 

The following command values are supported for compatibility with the System V Interface Definition:-

M_MXFAST
Implements the mallopt option of the same name.  The default maxfast value is not zero on this system.  The value supplied is interpreted as the maximum number of bytes to allocate using the fast (small block) allocator.  The block map is reset to agree with this. 

M_NLBLKS
The value is stored but ignored.  The storage allocator uses constant size chunks of memory for small block allocation − the standard System V storage allocator uses variable size chunks with a fixed number of units (of a given size) in them.

M_GRAIN
The value supplied is interpreted as the base size unit for small blocks.  All blocks are a multiple of this (byte) size.  In fact each size generated by this algorithm is rounded up to the next largest size (in whole words) which will result in the same number of blocks in a chunk.

M_KEEP
This option is for backwards compatibility with old storage allocators, it switches on the facility to retain the last pointer passed to _free until the next call of _free. The argument is ignored.

The following commands are specific to this storage allocator, in each case the argument is interpreted as a flag which allows the switch to be turned on or off. 

M_FLTFREE
Abort fault an invalid free call by calling the fatal error handler (see below).  This is on by default. 

M_FLTMALLOC
Fault a malloc call which fails (because the system has run out of memory) rather than returning NULL.  This is off by default. 

M_FLTSMASH
Fault corruption of the heap as soon as it is detected.  This is on by default.

M_MALLOC0
Return valid store in answer to a request for 0 bytes.  This is off by default − malloc will return the NULL pointer.  Notice that this does not alter the behaviour of realloc when called with a size of 0 − it still passes the supplied pointer to free and returns NULL.  This facility is off by default. 

The following commands are also specific to this allocator, they take a function pointer which may be ((void(∗)())NULL). 

M_WARNING
Specifies a (void (∗)(const char ∗)) function to call when outputing a warning message.  The function will be called when a fatal error occurs if a separate handler has not been specified (see below).  On return the allocator will abort the program using abort(3). The argument is an error message string, as described below.

M_ERROR
Specifies a (void (∗)(const char ∗)) function to call when a fatal error occurs.  The argument is a string describing the error.  If the function returns execution of the program will continue. 

M_NOMEM
Specifies a (void ∗(∗)(size_t)) function to call when storage allocation fails.  The function may make arbitrary calls to the storage manager, although if it calls malloc or realloc it must protect itself against being called recursively.  The function must return a pointer which will be returned as the result of the original malloc or realloc function call.  If the function returns the NULL pointer it is expected to set errno to the value ENOMEM. 

_ALLOC_Info returns an _ALLOC_Info structure, which is similar to the System V mallinfo structure and contains similar information.  Some values are generated by a heuristic method − accurate statistics for this storage manager can be obtained using the statistical functions above. 

NOTES

The functions malloc, free, realloc and calloc are available in most storage manager implementations (and in all UNIX ones) the other functions are specific to this implementation.  The alloca function provided in most BSD43 implementations cannot be implemented with some machine/compiler architectures − the aupcs(7) is such an architecture.

DIAGNOSTICS

Malloc, realloc and calloc return a null pointer (0) if there is no available memory.  Various options in the source code allow the memory allocator to call abort(3) or some program specified function instead if this occurs.

The allocator is very secure − it checks each block passed to free for overwrite errors and will not free an invalid pointer.  It is also very fast for small allocations (less than the the block map limit − by default requests for up to 84 words are satisfied this way).  The old BSD43 alloca call should be replaced by appropriate calls to malloc and free which are faster than any possible implementation of alloca which conforms to the procedure call mechanism used by cc(1).

In the event of storage corruption the allocator will either output a message on stderr and abort the program or it will simply crash.  In particular overwriting the end of a block of store will first corrupt the guard word (in the standard system) then the following block.  If the block is allocated whatever is using it will go wrong, if it is not allocated the first word is used to maintain a list of free blocks and so a change to it will probably crash the allocator. 

If necessary the _ALLOC_StorageFree function and appropriate calls to _byte_size can be used to spot storage corruption − a single call to _ALLOC_StorageFree followed by a call to _byte_size for each allocated pointer will spot any corruption. 

The allocator outputs the following messages on detection of errors:

allocate failed
When the manager fails to allocate the requested storage; only if allocation fail checking is switched on and a program supplied function to handle allocation failure has not be specified. − otherwise the malloc, calloc or realloc call returns 0 and sets errno to ENOMEM. 

recursive If compiled with reentrancy checking and a recursive call to the storage manager occurs (from a signal handler).  The default manager does not check this.  errno would be set to EDEADLK. 

no lock If reentrancy checking is compiled in this indicates an internal error in the manager − otherwise the message will not be produced.  errno would be set to ENOLCK. 

cannot open <analysis file name>
When the manager is compiled for storage analysis and the given analysis file cannot be opened. errno would be set to the result of the open(2) call.

request too large
If the manager is compiled with allocation fail checking on large requests this message will be produced when a silly request is made (by default more than 4Mbyte) (subject to the qualifications above about the allocate failed message). errno is set to ENOMEM. 

bad pointer
This is produced by free when a badly aligned pointer or a pointer which does not point to a valid block is freed.  errno is set to EINVAL. 

bad free This is produced only when debugging code is compiled in and when large request allocator detects a corrupted heap.  errno is set to EINVAL. 

list not empty
This is also only produced when debugging code is compiled in − it corresponds to an internal error in the code. errno is set to EFAULT. 

internal error
This message is produced when an internal inconsistency is detected during a free operation − it should never occur. errno is set to EFAULT. 

unallocated block
This is produced by free when the pointer corresponds to a part of the heap which has not been allocated yet.  errno is set to EINVAL. 

header block
This is produced when the pointer passed to free corresponds to part of the control structure of the allocator rather than to a valid part of the heap.  errno is set to EINVAL. 

heap corrupt
This message is produced whenever the allocator detects corruption of the heap − a more common symptom of this problem is for the program to crash. errno is set to EFAULT. 

bad block size
This message is produced if the blockmap has been corrupted. errno is set to EFAULT. 

misaligned pointer
Free produces this message when the pointer which it is passed does not point to the head of a block (although it is correctly aligned).  errno is set to EINVAL. 

already freed
This is produced by free when a block is freed twice or a block which has not yet been allocated is freed.  errno is set to EINVAL. 

end of block overwritten
This message is produced in the standard allocator when a block with an invalid guard word is freed (notice that the guard word is at the end of each block). errno is set to EINVAL. 

FEATURES

The code contains checking features which are available all the time and analysis features which can be turn on when the code is compiled.  Developers of large applications who feel they need the analysis facilities should contact Acorn Computers Ltd (the code is not related to the BSD4.3 implementation which is effectively unusable on an ARM). 

The overwrite checking can be switched off at compile time.  This is only worth doing if the program in question allocates a very large number of very small blocks (less than 4 words) − in this case it may also be worth tailoring the block map.  Again this requires access to the source code. 

BUGS

There are no facilities for spotting storage leaks. 

It is not safe to use the storage allocator in a signal handler unless it is possible to guarantee that the handler has not interrupted a call to malloc, calloc, realloc or free. This is because the storage allocator does not protect itself against reentrance in this way and the code itself is not reentrant. (This is also true of the standard BSD43 storage manager and of most other implementations of this functionality).

It is not safe to longjmp out of a signal handler which has interrupted one of these storage manager calls either, although the normal consequence of doing so will simply be a storage leak. 

SEE ALSO

brk(2)

AUTHORS

JB Acorn Computers Ltd 1988

7th Edition  —  Revision 1.6 of 26/11/90