Modified Best Buddy Memory Allocator. More...

Data Structures
struct	memMngrHead
	Contains the full information about the memory block. More...

struct	memBlckhead
	Contains the only the flag information about the memory block. More...

Macros
#define	malloc rMalloc
	Redefine malloc to rMalloc in order not to have to alter the already existing code.

#define	calloc rCalloc
	Redefine calloc to rCalloc in order not to have to alter the already existing code.

#define	realloc rRealloc
	Redefine realloc to rRealloc in order not to have to alter the already existing code.

#define	free rFree
	Redefine free to rFree in order not to have to alter the already existing code.

#define	BIGGEST_BLCK ((BlckSize)0x100u)
	Size of the biggest possible buddy. More...

#define	BIGGEST_BLCK_MSK ((BlckSize)(BIGGEST_BLCK - (BlckSize)1u))
	Mask for blocks bigger than BIGGER_BLCK. More...

#define	SMALLEST_BLCK ((BlckSize)0x8u)
	Size of the smallest possible buddy. More...

#define	SMALLER_BLCK_MSK ((BlckSize)(SMALLEST_BLCK - (BlckSize)1u))
	Mask for blocks smaller than SMALLEST_BLCK. More...

#define	SMALLER_BLCK_DIVISOR (MemIndex)(0x3u)
	Bit shifts needed for a division through SMALLEST_BLCK. More...

#define	CACHE_SIZE ((uint8_t)0x10u)
	Size of the object cache. More...

Typedefs
typedef uint16_t	BlckSize
	Size of a block of memory.

typedef uint8_t	MemPoolID
	8Bit ID value of a memory pool.

typedef uint16_t	MemFlags
	16Bit flag value.

typedef void *	stdPtr
	Simple void pointer. More...

typedef uint16_t	MemIndex
	Used for indexing memory blocks.

typedef struct memMngrHead	MemMngrHead
	memMngrHead

typedef struct memBlckhead	MemBlckHead
	memBlckhead

Functions
RetCode	initMEM (void)
	Initialize the memory manager. More...

static void	delMemBlck (MemMngrHead *const blckToDelete)
	Delete a block from the list it is contained in. More...

static MemMngrHead *	getAdjacentPrevBlck (MemMngrHead *const curBlck)
	Calculate and return the block prior to the given block. More...

static MemMngrHead *	getAdjacentNxtBlck (MemMngrHead *const curBlck)
	Calculate and return the block next to the given block. More...

static MemMngrHead *	getBuddyBlck (MemMngrHead *const curBlck)
	Calculate and return the buddy block to the given block. More...

static void	fitBlckBackIntoFreeLst (MemMngrHead *const curBlck)
	Put the given block back into the free memory blocks list according to its address. More...

static uint8_t	mergeMemBlck (MemMngrHead **blckToMerge)
	The given memory block is merged with its buddy block if it is free and not cached. More...

static void	reMergeMemBlck (MemMngrHead **blckToMerge)
	The given memory block is merged continuously with its buddy blocks as long as these are neither taken nor cached. More...

static void	splitMemBlck (MemMngrHead **const blckToSplit)
	The given memory block is split into two equally sized buddies. More...

static void	unMergeUnevenBlcks (MemMngrHead *const blckToUnMerge)
	The given memory block is split into the unequal buddy blocks it consisted of. More...

static void	mergeUnevenBlocks (MemMngrHead const basis, MemMngrHead const added)
	The two given memory blocks of unequal size are merged into one memory block. More...

static void	shrinkCacheFIFO (void)
	Remove the last element out of the cache. More...

static void	addBlckToCache (MemMngrHead *const blckToAdd)
	Add the given block to the objCache. More...

void *	rMalloc (MemSize desiredSize)
	Allocate a block of memory satisfying the desiredSize property. More...

void *	rCalloc (const MemSize desiredSize)

void *	rRealloc (void *ptrToExistingMem, MemSize desiredSize)
	Allocate a block of memory satisfying the desiredSize property. More...

void	rFree (void *pToBeFreed)
	The provided block of memory will be added to the memory block cache. More...

void	rFullyFree (MemMngrHead *blckToFullyFree)
	Free a block of memory previously allocated with either rMalloc, rCalloc or rRealloc. More...

RetCode	memMngr_CreateMemPool (const MemSize sizeOfElements, const uint8_t elements, MemPoolID *const memPoolID)
	Creates a memory pool with the given MemPoolID. More...

RetCode	memMngr_DeleteMemPool (const MemPoolID memPoolID)
	Delete a previously created memory pool linked to the provided MemPoolID. More...

RetCode	memMngr_MemPoolMalloc (void **ptrToMem, const MemPoolID memPoolID)
	Allocate an element from the memory pool specified by the provided MemPoolID. More...

RetCode	memMngr_MemPoolFree (void *ptrToMem, const MemPoolID memPoolID)
	Free a previously allocated block of memory from a memory pool and put it back into the memory pool. More...

Variables
static MemMngrHead *	freeMemLst = (MemMngrHead *) NULL
	List of free blocks of memory. More...

static MemMngrHead *	objCache = (MemMngrHead *) NULL
	List of free cached blocks of memory. More...

static MemMngrHead *	objCacheEnd = (MemMngrHead *) NULL
	End of the objCache List. More...

static uint8_t	buddyOffset = (uint8_t) 0x0u
	Memory address offset of buddy blocks. More...

static uint8_t	cacheSize = (uint8_t) 0x0u
	Counter for the current size of the objCache. More...

Detailed Description

Modified Best Buddy Memory Allocator.

Modified -> Can use adjacent blocks to fit memory needs -> reduce internal fragmentation

Object Cache -> Objects are put into an object cache upon freeing them -> alleviates frequent allocations of same-size objects

Macro Definition Documentation

#define BIGGEST_BLCK ((BlckSize)0x100u)

Size of the biggest possible buddy.

Restricted by the usage of flags.

#define BIGGEST_BLCK_MSK ((BlckSize)(BIGGEST_BLCK - (BlckSize)1u))

Mask for blocks bigger than BIGGER_BLCK.

Restricted by the maximum size of the MemMngrHead.

#define CACHE_SIZE ((uint8_t)0x10u)

Size of the object cache.

When an object is freed it is not directly inserted back into the free list. It is rather held in the object cache until the cache is full. FIFO principle is applied.

#define SMALLER_BLCK_DIVISOR (MemIndex)(0x3u)

Bit shifts needed for a division through SMALLEST_BLCK.

Note: log2(SMALLEST_BLCK).

#define SMALLER_BLCK_MSK ((BlckSize)(SMALLEST_BLCK - (BlckSize)1u))

Mask for blocks smaller than SMALLEST_BLCK.

Restricted by the minimum size of the MemMngrHead.

#define SMALLEST_BLCK ((BlckSize)0x8u)

Size of the smallest possible buddy.

Restricted by the minimum size of the MemMngrHead.

Note: Has to be a power of two.; Has to be at least the size of a MemMngrHead struct.

Typedef Documentation

stdPtr

Simple void pointer.

Might be deprecated.

Function Documentation

static void addBlckToCache ( MemMngrHead *const blckToAdd )

static

Add the given block to the objCache.

Parameters

[in] blckToAdd Pointer to the block to add to the cache.

Adds the given block to the beginning of the objCache. Check if the object is not already cached to avoid a loop in the cache! Also check the cacheSize and shrink the cache if it is bigger than the specified CACHE_SIZE.

static void delMemBlck ( MemMngrHead *const blckToDelete )

static

Delete a block from the list it is contained in.

Parameters

[in] blckToDelete Pointer to the block which shall be deleted from its list.

Adjusts the ptrNXT and ptrPREV of the block as well as the next and previous block's pointers.

static void fitBlckBackIntoFreeLst ( MemMngrHead *const curBlck )

static

Put the given block back into the free memory blocks list according to its address.

Parameters

[in] curBlck Pointer to the block to be reinserted into the free memory blocks list.

The next and previous free block of memory is calculated. The ptrNXT and ptrPREV of these and the curBlck are adjusted accordingly. The start of the freeMemLst is adjusted if there is no free previous block of memory.

static MemMngrHead * getAdjacentNxtBlck ( MemMngrHead *const curBlck )

static

Calculate and return the block next to the given block.

Parameters

[in] curBlck Pointer to the block to return the successor to.

Using the saved size of the curBlck ( in flagsForMemBlock ) the next block is calculated, casted to MemMngrHead * and returned.

static MemMngrHead * getAdjacentPrevBlck ( MemMngrHead *const curBlck )

static

Calculate and return the block prior to the given block.

Parameters

[in] curBlck Pointer to the block to return the predecessor to.

Using the saved size of the previous block ( in additionalFlags ) the previous block is calculated, casted to MemMngrHead * and returned.

static MemMngrHead * getBuddyBlck ( MemMngrHead *const curBlck )

static

Calculate and return the buddy block to the given block.

Parameters

[in] curBlck Pointer to the block to return the buddy block to.

Using the buddyOffset the address of curBlck is XORed with the block's size to get its buddy block. The result is casted to MemMngrHead and returned.

Warning: DO NOT USE THE BUDDY BLOCK, AS IT IS NOT GUARANTEED, THAT THE BLOCK IS FREE. NOR IS THERE ANY GUARANTEE, THAT THE BLOCK IS NOT INSIDE OF A COMBINATION OF BLOCKS. USE ONLY THE ADDRESS!

RetCode initMEM ( void )

Initialize the memory manager.

Returns: Return the success of the operation.

Warning: MUST BE CALLED BEFORE ANY CALL TO A MEMORY MANAGER RELATED FUNCTION!

RetCode memMngr_CreateMemPool	(	const MemSize	sizeOfElements,
		const uint8_t	elements,
		MemPoolID *const	memPoolID
	)

Creates a memory pool with the given MemPoolID.

Parameters

[in]	sizeOfElements	Size of one element
[in]	elements	Number of elements to allocate the pool for
[out]	memPoolID	Pointer to a MemPoolID that receives the ID of the created memory pool

Returns: Returns the success of the operation

This function allocates elements number of memory block with the size sizeOfElements and assigns its MemPoolID to memPoolID.

Warning: This function must have been called before the memory pool can be used!

RetCode memMngr_DeleteMemPool ( const MemPoolID memPoolID )

Delete a previously created memory pool linked to the provided MemPoolID.

Todo:: Implement!

Warning: DO NOT USE!

Parameters

[in] memPoolID Memory pool ID of the memory pool to be deleted.

Returns: Return the success of the operation

RetCode memMngr_MemPoolFree	(	void *	ptrToMem,
		const MemPoolID	memPoolID
	)

Free a previously allocated block of memory from a memory pool and put it back into the memory pool.

Parameters

[in]	ptrToMem	Pointer to the block of memory to free
[in]	memPoolID	MemPoolID of the memory pool the block of memory was allocated from

Returns: Return the success of the operation

Warning: The block must have been allocated from the memory pool corresponding to the given MemPoolID!

Note: The block is prepended to the memory pool's available block list.

RetCode memMngr_MemPoolMalloc	(	void **	ptrToMem,
		const MemPoolID	memPoolID
	)

Allocate an element from the memory pool specified by the provided MemPoolID.

Parameters

[out]	ptrToMem	Pointer to pointer that will receive the address of the allocated block
[in]	memPoolID	MemPoolID of the memory pool to allocate the block of memory from

Returns: Return the success of the operation

Warning: The memory pool must have been initialized upfront!

static uint8_t mergeMemBlck ( MemMngrHead ** blckToMerge )

static

The given memory block is merged with its buddy block if it is free and not cached.

Parameters

[in] blckToMerge Pointer to a pointer to the block to be merged.

The next and previous free block of memory is calculated. The ptrNXT and ptrPREV of these and the curBlck are adjusted accordingly. The start of the freeMemLst is adjusted if there is no free previous block of memory.

static void mergeUnevenBlocks	(	MemMngrHead *const	basis,
		MemMngrHead *const	added
	)

static

The two given memory blocks of unequal size are merged into one memory block.

Parameters

[in]	basis	Pointer to the block to be merged and used as the pointer to the combined memory.
[in]	added	Pointer to the block to be merged with the basis.

Two blocks of unequal size are merged to make up a new extraordinary sized block. Usually blocks are either split equally or merged with buddies (of the same size so to speak). In order to ease the impact of internal fragmentation, a block can be merged with only parts of its buddy. Flags and sizes of the buddies and the preceding as well as succeeding blocks are adjusted automatically.

Example:

Requested size: 0xC4
Next bigger block: 0x100
Next smaller block: 0x80
Loss: 0x20

Therefore split bigger block ( to 0x80) and add the remaining need from its ( again split) buddy (0x40). If the size is insufficient the process can be repeated. Again add a split buddy (0x10) to suffice the need best fitting (0xD0)

Requested size: 0xC4
Next bigger block: 0x100
Split once: 0x80
Remainder: 0x44
Split buddy: 0x40
Remainder: 0x4
Split buddy best fit: 0x10
Combined size: 0xD0
Loss: 0xC
SAVED: 0x14

void * rCalloc ( MemSize desiredSize )

Warning: DO NOT USE, UNFINISHED

Parameters

desiredSize

Warning: UNTESTED!

static void reMergeMemBlck ( MemMngrHead ** blckToMerge )

static

The given memory block is merged continuously with its buddy blocks as long as these are neither taken nor cached.

Parameters

[in] blckToMerge Pointer to a pointer to the block to be merged.

Using mergeMemBlck a Block is merged to its biggest possible size with is free and uncached buddies.

void rFree ( void * pToBeFreed )

The provided block of memory will be added to the memory block cache.

Parameters

pToBeFreed [in] Pointer to the block of memory to free.

void rFullyFree ( MemMngrHead * blckToFullyFree )

Free a block of memory previously allocated with either rMalloc, rCalloc or rRealloc.

Parameters

blckToFullyFree [in] Pointer to the block of memory (MemMngrHead) to free and put back onto the free memory blocks list.

void * rMalloc ( MemSize desiredSize )

Allocate a block of memory satisfying the desiredSize property.

Parameters

desiredSize [in] The size of the memory block needed.

void * rRealloc	(	void *	ptrToExistingMem,
		MemSize	desiredSize
	)

Allocate a block of memory satisfying the desiredSize property.

Parameters

ptrToExistingMem	[in, out] Pointer to the already allocated memory.
desiredSize	[in] The size of the memory block needed.

Warning: UNTESTED!

static void shrinkCacheFIFO ( void )

static

Remove the last element out of the cache.

Simply removes the last element of the objCache and sets the new list end accordingly.

static void splitMemBlck ( MemMngrHead **const blckToSplit )

static

The given memory block is split into two equally sized buddies.

Parameters

[in] blckToSplit Pointer to a pointer to the block to be split.

The given block of memory is split in half. The flags of both blocks are adjusted accordingly.

static void unMergeUnevenBlcks ( MemMngrHead *const blckToUnMerge )

static

The given memory block is split into the unequal buddy blocks it consisted of.

Parameters

[in] blckToUnMerge Pointer to the block to be unmerged.

A block can be made up of unequally sized buddies. This function extracts these buddies and adds them back to the freeMemLst. Flags and sizes of the buddies and the preceding as well as succeeding blocks are adjusted automatically.

Variable Documentation

buddyOffset = (uint8_t) 0x0u

static

Memory address offset of buddy blocks.

In order to be able to XOR the address of a block with its size and get its buddy, addresses have to be altered with an offset beforehand.

E.g.:
Actual address: 0x1ffff38
Offset: 0x8
Possible size: 0x20
Buddy block = ( (0x1ffff38 - 0x8) ^ 0x20 ) + 0x8

Initialized to 0x0.

cacheSize = (uint8_t) 0x0u

static

Counter for the current size of the objCache.

Keeps track of the elements in the objCache. Decreases and increases automatically when objects are added, removed or kicked out.

Initialized to 0x0.

freeMemLst = (MemMngrHead *) NULL

static

List of free blocks of memory.

Contains free blocks of memory that are not cached.

Initialized to NULL.

objCache = (MemMngrHead *) NULL

static

List of free cached blocks of memory.

As soon as a block of memory is freed it is added to the objCache. The size of the obCache is define by CACHE_SIZE. If the size exceeds this limit elements are removed according to FIFO principle.

Initialized to NULL.

objCacheEnd = (MemMngrHead *) NULL

static

End of the objCache List.

The last element in the object cache.

Initialized to NULL.

Data Structures

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation