Heap

Internal Heap Implementation. More...

Collaboration diagram for Heap:

Detailed Description

Internal Heap Implementation.

We use a "segregated free list" allocator with a set of bins where each bin stores free blocks of size \(n \cdot 64\) bytes where \(n\) is the index of the bin, up to _HEAP_LARGE_ALLOC_THRESHOLD. Above this size, blocks are mapped directly.

To allow for coalescing of free blocks, all blocks (allocated and free) are additionally stored in a linked list sorted by address. When a block is freed, we check the previous and next blocks in memory to see if they are free, and if so we merge them into a single larger block.

Included is the internal heap allocation, the functions that the kernel and user space should use are the expected malloc(), free(), realloc(), etc functions.

Todo:

Implement a slab allocator.

Data Structures
struct	_heap_header_t
struct	_heap_header
	Header for each heap block. More...

Macros
#define	_HEAP_ALIGNMENT   64
#define	_HEAP_HEADER_MAGIC   0xDEADBEEF
#define	_HEAP_LARGE_ALLOC_THRESHOLD   (PAGE_SIZE * 4)
#define	_HEAP_NUM_BINS   (_HEAP_LARGE_ALLOC_THRESHOLD / _HEAP_ALIGNMENT)

Enumerations
enum	_heap_flags_t { _HEAP_ALLOCATED = 1 << 0 , _HEAP_MAPPED = 1 << 1 , _HEAP_ZEROED = 1 << 2 }
	Flags for heap blocks. More...

Functions
void	_heap_init (void)
	Initialize the heap.
void	_heap_acquire (void)
	Acquire the heap lock.
void	_heap_release (void)
	Release the heap lock.
uint64_t	_heap_get_bin_index (uint64_t size)
	Get the bin index for a given size.
_heap_header_t *	_heap_block_new (uint64_t minSize)
	Directly maps a new heap block of at least minSize bytes.
void	_heap_block_split (_heap_header_t *block, uint64_t size)
	Splits a heap block into two blocks, the first of size bytes and the second with the remaining bytes.
void	_heap_add_to_free_list (_heap_header_t *block)
	Adds a block to the appropriate free list.
void	_heap_remove_from_free_list (_heap_header_t *block)
	Removes a block from its free list.
_heap_header_t *	_heap_alloc (uint64_t size)
	Allocates a block of memory of given size.
void	_heap_free (_heap_header_t *block)
	Frees a previously allocated heap block.
void *	_heap_map_memory (uint64_t size)
	Directly maps memory of the given size.
void	_heap_unmap_memory (void *addr, uint64_t size)
	Unmaps previously mapped memory.

Variables
list_t	_heapList
	A list of all blocks sorted by address.

Macro Definition Documentation

_HEAP_ALIGNMENT

#define _HEAP_ALIGNMENT   64

The memory alignment in bytes of all allocations on the heap.

We use 64 bytes for better cache line alignment on modern CPUs.

Definition at line 29 of file heap.h.

_HEAP_HEADER_MAGIC

#define _HEAP_HEADER_MAGIC   0xDEADBEEF

Magic number used to validate heap integrity.

Definition at line 34 of file heap.h.

_HEAP_LARGE_ALLOC_THRESHOLD

#define _HEAP_LARGE_ALLOC_THRESHOLD   (PAGE_SIZE * 4)

The threshold size for large allocations, above this size allocations will be mapped directly.

Definition at line 39 of file heap.h.

_HEAP_NUM_BINS

#define _HEAP_NUM_BINS   (_HEAP_LARGE_ALLOC_THRESHOLD / _HEAP_ALIGNMENT)

The number of bins for free lists.

Definition at line 44 of file heap.h.

Enumeration Type Documentation

_heap_flags_t

enum _heap_flags_t

Flags for heap blocks.

Enumerator
_HEAP_ALLOCATED	Block is allocated.
_HEAP_MAPPED	Block is not on the heap, but mapped directly, used for large allocations.
_HEAP_ZEROED	Block is zeroed.

Definition at line 49 of file heap.h.

Function Documentation

_heap_init()

void _heap_init

(

void

)

Initialize the heap.

Definition at line 64 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_acquire()

void _heap_acquire

(

void

)

Acquire the heap lock.

Must be paired with a call to _heap_release().

Definition at line 84 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_release()

void _heap_release

(

void

)

Release the heap lock.

Definition at line 98 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_get_bin_index()

uint64_t _heap_get_bin_index

(

uint64_t

size

)

Get the bin index for a given size.

Parameters

size	The size to get the bin index for.

Returns

The bin index, or ERR if the size is should be treated as a large allocation.

Definition at line 112 of file heap.c.

Here is the caller graph for this function:

_heap_block_new()

_heap_header_t * _heap_block_new

(

uint64_t

minSize

)

Directly maps a new heap block of at least minSize bytes.

Must be called with the heap acquired.

Parameters

minSize

The minimum size of the block to create, in bytes.

Returns

On success, pointer to the new heap block header. On failure, NULL.

Definition at line 127 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_block_split()

void _heap_block_split	(	_heap_header_t *	block,
		uint64_t	size
	)

Splits a heap block into two blocks, the first of size bytes and the second with the remaining bytes.

Must be called with the heap acquired.

Parameters

block	The block to split.
size	The size of the first block after the split, in bytes.

Definition at line 172 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_add_to_free_list()

void _heap_add_to_free_list

(

_heap_header_t *

block

)

Adds a block to the appropriate free list.

Must be called with the heap acquired.

Will not actually free the block, just add it to the free list.

Used to keep track of which bins have free blocks using a bitmap.

Parameters

block

The block to add.

Definition at line 202 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_remove_from_free_list()

void _heap_remove_from_free_list

(

_heap_header_t *

block

)

Removes a block from its free list.

Must be called with the heap acquired.

Will not actually allocate the block, just remove it from the free list.

Used to keep track of which bins have free blocks using a bitmap.

Parameters

block

The block to remove.

Definition at line 223 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_alloc()

_heap_header_t * _heap_alloc

(

uint64_t

size

)

Allocates a block of memory of given size.

Must be called with the heap acquired.

Parameters

size	The size of memory to allocate, in bytes.

Returns

On success, pointer to the allocated heap block header. On failure, NULL and errno is set.

Definition at line 247 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_free()

void _heap_free

(

_heap_header_t *

block

)

Frees a previously allocated heap block.

Must be called with the heap acquired.

Will attempt to coalesce adjacent free blocks.

Parameters

block

The block to free.

Definition at line 312 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_map_memory()

void * _heap_map_memory

(

uint64_t

size

)

Directly maps memory of the given size.

In the kernel this function uses the VMM to map new memory, in user space it uses /dev/zero.

Parameters

size	The size of memory to map, in bytes.

Returns

On success, pointer to the mapped memory. On failure, NULL.

Definition at line 39 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

_heap_unmap_memory()

void _heap_unmap_memory	(	void *	addr,
		uint64_t	size
	)

Unmaps previously mapped memory.

In the kernel this function uses the VMM to unmap memory, in user space it uses the munmap() function.

Parameters

addr	The address of the memory to unmap.
size	The size of memory to unmap, in bytes.

Definition at line 50 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

_heapList

list_t _heapList

extern

A list of all blocks sorted by address.

Definition at line 62 of file heap.c.