Hi everyone, I don't know if someone needs this, but I thought it could come in handy.
I missed a lot some form of memory allocation in CircleOS, so I wrote my own. I used the Buddy System Allocation. See Wikipedia or "The Art of Computer Programming" for info on how it works.
Essentially, what I do is to allocate a static array and manage chunks of it through malloc calls. 4 functions are provided: POOL_Malloc POOL_Calloc POOL_Realloc POOL_Free
They work as their stdlib counterparts.
It's NOT production ready, but I'm posting it AS IS, for everyone who wants a quickstart for dynamic allocation. Just, make sure to check the 2 constants POOL_BUFFER_SIZE_LOG2 and POOL_BUFFER_BLOCK_SIZE_LOG2 in pool.h to select the size of the buffer to allocate. Predefined size is 128KB.
Everything in 2 files: pool.h and pool.c
pool.h:
Code:
/****************************************************************************************
* Copyright (c) 2011, Alberto Chiesa
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * The name of Alberto Chiesa may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY Alberto Chiesa "AS IS" AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL Alberto Chiesa BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Contact: chiesa80 HAT yahoo DOT it
****************************************************************************************
*
* pool.h / pool.c
*
* Implementation of a simple memory pool using the Buddy System Algorithms.
* See Knuth's The Art of Computer Programming Vol. 1, 3rd Ed., pag.442
* for algorithm details.
*
* Malloc, Calloc, Realloc and Free functions are provided.
*
****************************************************************************************/
#ifndef _POOL_H
#define _POOL_H
/* Redefine NULL if required */
#ifndef NULL
#define NULL 0
#endif
/* Type for storing sizes (substitute for size_t) */
typedef unsigned long int POOL_Size;
/* Public functions Declaration. */
void *POOL_Malloc(POOL_Size size);
void *POOL_Calloc(POOL_Size nelements, POOL_Size elementSize);
void *POOL_Realloc(void *pointer, POOL_Size size);
void POOL_Free(void *pointer);
/************************************************************
* Private Area: only implementation and test files should
* worry about this.
************************************************************/
#ifdef POOL_INCLUDE_PRIVATE
/* Size of the internal buffer expressed as a Log2:
* Actual size in bytes of the managed buffer is
* 1 << POOL_MANAGED_MEMORY_SIZE_IN_LOG2
* 10 means 1 KB will be reserved and managed
* 17 means 128KB will be managed */
#define POOL_BUFFER_SIZE_LOG2 17
/* Minimum size of a reserved block (log2).
* The actual size is (1 << POOL_BUFFER_BLOCK_SIZE_LOG2)
* E.g. 6 means a minimum of (1<<6)=64 bytes will be reserved
* for each request, even for requests of smaller quantities */
#define POOL_BUFFER_BLOCK_SIZE_LOG2 6
/* Buffer size in bytes */
#define POOL_BUFFER_SIZE (1 << POOL_BUFFER_SIZE_LOG2)
/* We will return blocks of size equal to a power of two and
* size in the interval [1<<POOL_BUFFER_BLOCK_SIZE_LOG2; 1<<POOL_BUFFER_SIZE_LOG2]
* POOL_AVAILABLE_SIZES is the number of powers of 2 in the interval */
#define POOL_AVAILABLE_SIZES ((POOL_BUFFER_SIZE_LOG2 - POOL_BUFFER_BLOCK_SIZE_LOG2) + 1)
/* Number of blocks of minimum size */
#define POOL_NUMBER_OF_BLOCKS (POOL_BUFFER_SIZE >> POOL_BUFFER_BLOCK_SIZE_LOG2)
/* Declaration of data to be stored in available blocks
* Note that a BlockDataStruct is allocated in each block,
* either free or occupied, but in allocated blocks
* the 2 pointers are useless and overwritten, in order to
* reserve more space for actual data */
typedef struct POOL_BlockDataStruct {
unsigned char AvailableTag; /* 0 if free, else 1 */
unsigned char SizeLog2; /* Size of the available block as a log2 */
struct POOL_BlockDataStruct *NextBlock;
struct POOL_BlockDataStruct *PrevBlock;
} POOL_BlockData;
/* Forward declaration of the managed buffer */
extern char _POOL_ManagedBuffer[];
/* "Buddy" Macro:
* Returns a pointer (char *) to the buddy block of the current one.
* B is the internal Buffer base address, P is a pointer to the current block
* K is the size of the block (and of the buddy) in log2.
* I.e.
* P + (1 << K) if (P % (2 << K)) = 0
* P - (1 << K) if (P % (2 << K)) = 1 << K */
#define POOL_BUDDY_ADDRESS(B, P, K) ((char *)(B) + (((char *)(P) - (char *)(B)) ^ (1 << (K))))
/* Returns the Tag (bit) associated with N-th block. */
#define POOL_GET_BLOCK_TAG_INDEX(N) POOL_GET_BLOCK_TAG(_POOL_ManagedBuffer + ((N) << POOL_BUFFER_BLOCK_SIZE_LOG2))
/* Sets (marks as allocated) the N-th block */
#define POOL_SET_BLOCK_TAG_INDEX(N) POOL_SET_BLOCK_TAG(_POOL_ManagedBuffer + ((N) << POOL_BUFFER_BLOCK_SIZE_LOG2))
/* Resets (marks as free) the N-th block */
#define POOL_RESET_BLOCK_TAG_INDEX(N) POOL_RESET_BLOCK_TAG(_POOL_ManagedBuffer + ((N) << POOL_BUFFER_BLOCK_SIZE_LOG2))
/* Returns the Tag (bit) associated with a block, given a block pointer. */
#define POOL_GET_BLOCK_TAG(PTR) (((POOL_BlockDataStruct *)(PTR))->AvailableTag)
/* Sets the Tag (bit) associated with a block, given a block pointer. */
#define POOL_SET_BLOCK_TAG(PTR) (POOL_GET_BLOCK_TAG(PTR) = 1)
/* Resets the Tag (bit) associated with a block, given a block pointer. */
#define POOL_RESET_BLOCK_TAG(PTR) (POOL_GET_BLOCK_TAG(PTR) = 0)
/* Initialization Function is private because it's auto-managed, usually. */
void POOL_Initialize();
unsigned char POOL_GetK(POOL_Size size);
#endif /* POOL_INCLUDE_PRIVATE */
#endif /* _POOL_H */
pool.c:
Code:
/****************************************************************************************
* Copyright (c) 2011, Alberto Chiesa
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * The name of Alberto Chiesa may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY Alberto Chiesa "AS IS" AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL Alberto Chiesa BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Contact: MySurname 80 hat yahoo dot it
****************************************************************************************
*
* pool.h / pool.c
*
* Implementation of a simple memory pool using the Buddy System Algorithms.
* See Knuth's The Art of Computer Programming Vol. 1, 3rd Ed., pag.442
* for algorithm details.
*
* Malloc, Calloc, Realloc and Free functions are provided.
*
****************************************************************************************/
#define POOL_INCLUDE_PRIVATE
#include "pool.h"
#include <string.h>
/* Managed Memory Definition.
* Initialized to zeros */
char _POOL_ManagedBuffer[POOL_BUFFER_SIZE] = {0};
/* Array storing Linked List Heads, one for each possible
* size of released blocks. */
POOL_BlockData _POOL_AvailableBlocks[POOL_AVAILABLE_SIZES];
/* Flag telling us if we should still initialize the managed memory */
char _POOL_Uninitialized = 1;
void POOL_Initialize()
{
POOL_BlockData *blockPtr;
POOL_Size k;
/* Initialization of buffer: 1 block of maximum size */
blockPtr = (POOL_BlockData *)_POOL_ManagedBuffer;
blockPtr->AvailableTag = 1;
blockPtr->SizeLog2 = POOL_BUFFER_SIZE_LOG2;
/* Points to the last head */
blockPtr->NextBlock = blockPtr->PrevBlock =
_POOL_AvailableBlocks + POOL_AVAILABLE_SIZES - 1;
/* Initialization of Linked List Heads: only one block of maximum size;
* every other size has no blocks
*/
k = POOL_BUFFER_SIZE_LOG2;
blockPtr = _POOL_AvailableBlocks + POOL_AVAILABLE_SIZES - 1;
blockPtr->SizeLog2 = (unsigned char)k;
blockPtr->NextBlock = blockPtr->PrevBlock = (POOL_BlockData *)_POOL_ManagedBuffer;
while(k > POOL_BUFFER_BLOCK_SIZE_LOG2)
{
(--blockPtr)->SizeLog2 = (unsigned char)--k;
blockPtr->NextBlock = blockPtr->PrevBlock = blockPtr;
}
_POOL_Uninitialized = 0;
}
/* k is the size of the block to be allocated in log2
* The block must be at least "size" bytes + 2 bytes for
* unsigned char AvailableTag and
* unsigned char SizeLog2 */
unsigned char POOL_GetK(POOL_Size size)
{
/* Magic numbers for log2 computing */
static const unsigned char _POOL_MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
register POOL_Size x;
/* reserve 2 more bytes for AvailableTag and SizeLog2 */
x = size + sizeof(unsigned char) * 2;
/* if size is under a minimum, reserve the minimum */
if (x <= (1 << POOL_BUFFER_BLOCK_SIZE_LOG2))
return POOL_BUFFER_BLOCK_SIZE_LOG2;
/* k = log2(size - 1) + 1
* i.e. the log2 of the minimum power of 2 greater than or
* equal to size */
/* Compute the Log2 of an POOL_Size int (unsigned long)
* See http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
* for explanation. */
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return _POOL_MultiplyDeBruijnBitPosition[(POOL_Size)(x * 0x07C4ACDDU) >> 27] + 1;
}
/* Implementation of Knuth's Algorithm "R". */
static void *_POOL_Reserve(POOL_Size size)
{
unsigned char k, j;
POOL_BlockData *_headPtr, *_freeArea, *_buddyPtr;
if ((size == 0) || (size > POOL_BUFFER_SIZE))
return NULL;
/* 1 - find k: smallest power of 2 greater or equal than size, minimum */
k = POOL_GetK(size);
/* 2 - Find j: minimum block size with available blocks
* If k = 6 and POOL_BUFFER_BLOCK_SIZE_LOG2 = 6, start with
* _POOL_AvailableBlocks[0], else skip some values consequently.
*/
_headPtr = _POOL_AvailableBlocks + (k - POOL_BUFFER_BLOCK_SIZE_LOG2);
for(j = k; _headPtr->NextBlock == _headPtr; j++, _headPtr++)
{
if (j > POOL_BUFFER_SIZE_LOG2)
{
/* No available memory... probably should Yell out or something */
return NULL;
}
}
/* Remove the free Area from the linked list */
_freeArea = _headPtr->NextBlock;
(_headPtr->NextBlock = _freeArea->NextBlock)->PrevBlock = _headPtr;
POOL_SET_BLOCK_TAG(_freeArea);
/* Split and decrease j until j == k */
while(j > k)
{
j--;
_headPtr--;
/* Get the buddy pointer */
_buddyPtr = (POOL_BlockData *)((char *)_freeArea + (1 << j));
_buddyPtr->SizeLog2 = (unsigned char)j;
/* Update linked list */
(_buddyPtr->NextBlock = _headPtr->NextBlock)->PrevBlock = _buddyPtr;
(_buddyPtr->PrevBlock = _headPtr)->NextBlock = _buddyPtr;
POOL_RESET_BLOCK_TAG(_buddyPtr);
}
_freeArea->SizeLog2 = k;
/* AvailableTag and SizeLog2 are preserved,
* NextBlock and PrevBlock pointers are overwritten */
return (void *)((char *)_freeArea + 2);
}
void *POOL_Malloc(POOL_Size size)
{
if (size == 0) return NULL;
/* Init if needed */
if (_POOL_Uninitialized) POOL_Initialize();
return _POOL_Reserve(size);
}
void *POOL_Realloc(void *pointer, POOL_Size size)
{
void *_ptr;
POOL_BlockData *blockPtr;
if (size == 0) return NULL;
/* Init if needed */
if (_POOL_Uninitialized) POOL_Initialize();
/* Get pointer to block */
blockPtr = (POOL_BlockData *)((char *)pointer - 2);
/* Alloc a new block */
_ptr = _POOL_Reserve(size);
/* Copy content */
memcpy(_ptr, pointer, size > (1 << blockPtr->SizeLog2) ? size : (1 << blockPtr->SizeLog2));
/* Release previously allocated block */
POOL_Free(pointer);
return _ptr;
}
void *POOL_Calloc(POOL_Size nelements, POOL_Size elementSize)
{
void *_ptr;
if ((nelements == 0) || (elementSize == 0))
return NULL;
/* Init if needed */
if (_POOL_Uninitialized) POOL_Initialize();
_ptr = _POOL_Reserve(nelements * elementSize);
memset(_ptr, 0, nelements * elementSize);
return _ptr;
}
void POOL_Free(void *pointer)
{
unsigned char k;
POOL_BlockData *_blockPtr, *_buddyPtr, *_headPtr;
if (pointer == NULL) return;
/* Subtract 2 to get Block Start */
_blockPtr = (POOL_BlockData *)((char *)pointer - 2);
k = _blockPtr->SizeLog2;
while (1)
{
/* Get the buddy */
_buddyPtr = (POOL_BlockData *)POOL_BUDDY_ADDRESS(_POOL_ManagedBuffer, _blockPtr, k);
/* Check merge conditions */
if ((_buddyPtr->AvailableTag != 0) ||
(_buddyPtr->SizeLog2 != k) ||
(k >= POOL_BUFFER_SIZE_LOG2))
{
break;
}
/* Buddy is free: combine blocks */
_buddyPtr->PrevBlock->NextBlock = _buddyPtr->NextBlock;
_buddyPtr->NextBlock->PrevBlock = _buddyPtr->PrevBlock;
k++;
if (_buddyPtr < _blockPtr)
{
_blockPtr = _buddyPtr;
}
}
/* Add the freed block to the corresponding linked list */
POOL_RESET_BLOCK_TAG(_blockPtr);
_blockPtr->SizeLog2 = k;
/* Insert block in linked list */
_headPtr = _POOL_AvailableBlocks + (k - POOL_BUFFER_BLOCK_SIZE_LOG2);
(_blockPtr->NextBlock = _headPtr->NextBlock)->PrevBlock = _blockPtr;
(_blockPtr->PrevBlock = _headPtr)->NextBlock = _blockPtr;
return;
}
Released under BSD license. This means you can basically do what you want with this code, just don't pretend you wrote it if it works or that I wrote it if it breaks. Drop me a line for information, bugs, thanks, death menaces, etc.
Sorry, I'm not following you What are you using? A standard malloc implementation from a library or a custom made one? Statically allocated memory or what?
The Buddy System allocates a STATIC array and returns chunks of it.
It is very understandable you don't understand the message from 'harrymac'. Harry is a spam-bot, in this case it took part of the web site http://stackoverflow.com/questions/8520 … alloc-free and inserted it in this blog yesterday based on the keyword 'malloc' in the subject line. Note that Harry became a member the same day he (it) put in this spam message. Surely if you would click the link in Harry's message, you end up where you don't want to go. (I didn't try ;-)
I appreciate the effort the Raisonance team put in this blog to try to keep spammers out. Just be aware of new members, who post message the day they sign up, and show a link at the bottom of their message. There're a number of those inside 'our' blog at this time.
