Heap memory allocation. More...

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.

Detailed Description

Heap memory allocation.

The heap uses a "segregated free list" allocator with a set of bins where each bin stores free blocks of size n * 64 bytes up to a threshold, beyond which large allocations are mapped directly.

We also keep track of a physical list of blocks which is be used to split and coalesce blocks when freeing memory.

Below 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.

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 31 of file heap.h.

◆ _HEAP_HEADER_MAGIC

#define _HEAP_HEADER_MAGIC 0xDEADBEEF

Magic number used to validate heap integrity.

Definition at line 36 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 41 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 46 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 51 of file heap.h.

Function Documentation

◆ _heap_acquire()

void _heap_acquire ( void )

Acquire the heap lock.

Must be paired with a call to _heap_release().

Definition at line 81 of file heap.c.

References lock_acquire(), mtx_lock(), and mutex.

Referenced by calloc(), free(), malloc(), and realloc().

◆ _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 174 of file heap.c.

References _heap_get_bin_index(), bitmap_set(), ERR, freeBitmap, _heap_header_t::freeEntry, freeLists, list_push(), and _heap_header_t::size.

Referenced by _heap_free().

◆ _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.

In the kernel underlying functions will cause this function to set errno on failure.

Parameters

size	The size of memory to allocate, in bytes.

Returns: On success, pointer to the allocated heap block header. On failure, NULL.

Definition at line 199 of file heap.c.

References _HEAP_ALIGNMENT, _HEAP_ALLOCATED, _heap_block_new(), _heap_block_split(), _heap_get_bin_index(), _HEAP_HEADER_MAGIC, _HEAP_LARGE_ALLOC_THRESHOLD, _heap_map_memory(), _HEAP_MAPPED, _HEAP_ZEROED, bitmap_clear(), bitmap_find_first_set(), BYTES_TO_PAGES, CONTAINER_OF, _heap_header_t::flags, freeBitmap, _heap_header_t::freeEntry, freeLists, bitmap_t::length, list_entry_init(), list_is_empty(), list_pop(), _heap_header_t::listEntry, _heap_header_t::magic, NULL, PAGE_SIZE, pageAmount, ROUND_UP, and _heap_header_t::size.

Referenced by calloc(), and malloc().

◆ _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 114 of file heap.c.

References _HEAP_HEADER_MAGIC, _heap_map_memory(), _HEAP_ZEROED, _heapList, BYTES_TO_PAGES, CONTAINER_OF_SAFE, _heap_header_t::flags, _heap_header_t::freeEntry, list_append(), list_entry_init(), list_last(), list_push(), _heap_header_t::listEntry, _heap_header_t::magic, MAX, NULL, PAGE_SIZE, pageAmount, list_entry_t::prev, and _heap_header_t::size.

Referenced by _heap_alloc().

◆ _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 154 of file heap.c.

References _HEAP_ALIGNMENT, _heap_free(), _HEAP_HEADER_MAGIC, _HEAP_ZEROED, _heapList, assert, _heap_header_t::flags, list_append(), list_entry_init(), _heap_header_t::listEntry, _heap_header_t::magic, remainder(), and _heap_header_t::size.

Referenced by _heap_alloc(), and realloc().

◆ _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 259 of file heap.c.

References _heap_add_to_free_list(), _HEAP_ALLOCATED, _HEAP_LARGE_ALLOC_THRESHOLD, _HEAP_MAPPED, _heap_remove_from_free_list(), _heap_unmap_memory(), _HEAP_ZEROED, _heapList, assert, CONTAINER_OF_SAFE, _heap_header_t::data, _heap_header_t::flags, list_remove(), _heap_header_t::listEntry, list_entry_t::next, next, NULL, list_entry_t::prev, and _heap_header_t::size.

Referenced by _heap_block_split(), and free().

◆ _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 99 of file heap.c.

References _HEAP_ALIGNMENT, _HEAP_LARGE_ALLOC_THRESHOLD, and ERR.

Referenced by _heap_add_to_free_list(), _heap_alloc(), and _heap_remove_from_free_list().

◆ _heap_init()

void _heap_init ( void )

Initialize the heap.

Definition at line 62 of file heap.c.

References _HEAP_NUM_BINS, abort(), bitmap_init(), ERR, freeBitmap, freeBitmapBuffer, freeLists, list_init(), lock_init(), mtx_init(), mtx_plain, mutex, open(), and zeroDev.

Referenced by _std_init().

◆ _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.

References mmap(), NULL, PROT_READ, PROT_WRITE, and zeroDev.

Referenced by _heap_alloc(), and _heap_block_new().

◆ _heap_release()

void _heap_release ( void )

Release the heap lock.

Definition at line 90 of file heap.c.

References lock_release(), mtx_unlock(), and mutex.

Referenced by calloc(), free(), malloc(), and realloc().

◆ _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 185 of file heap.c.

References _heap_get_bin_index(), bitmap_clear(), ERR, freeBitmap, _heap_header_t::freeEntry, freeLists, list_is_empty(), list_remove(), and _heap_header_t::size.

Referenced by _heap_free(), and realloc().

◆ _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.

References munmap().

Referenced by _heap_free().

Variable Documentation

◆ _heapList

list_t _heapList

extern

A list of all blocks sorted by address.

Definition at line 60 of file heap.c.

Referenced by _heap_block_new(), _heap_block_split(), _heap_free(), and realloc().

Data Structures

Macros

Enumerations

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ _HEAP_ALIGNMENT

◆ _HEAP_HEADER_MAGIC

◆ _HEAP_LARGE_ALLOC_THRESHOLD

◆ _HEAP_NUM_BINS

Enumeration Type Documentation

◆ _heap_flags_t

Function Documentation

◆ _heap_acquire()

◆ _heap_add_to_free_list()

◆ _heap_alloc()

◆ _heap_block_new()

◆ _heap_block_split()

◆ _heap_free()

◆ _heap_get_bin_index()

◆ _heap_init()

◆ _heap_map_memory()

◆ _heap_release()

◆ _heap_remove_from_free_list()

◆ _heap_unmap_memory()

Variable Documentation

◆ _heapList