Kernel dynamic allocator

Collaboration diagram for Kernel dynamic allocator:

Modules
	Kmalloc - Internals
	Internal functions and structures used for managing buckets.

Enumerations
enum	kmalloc_flags
	Feature flags passed to the kmalloc function family.

Functions
void *	kmalloc (size_t size, int flags)
	Allocate size bytes and return a pointer to the allocated memory. More...
void *	kcalloc (size_t nmemb, size_t size, int flags)
	Allocate nmemb members of size bytes and initialize its content to 0. More...
void	kfree (void *ptr)
	Free a pointer allocated through Kernel dynamic allocator.
void *	krealloc (void *ptr, size_t size, int flags)
	Change the size of the given memory block. More...
void *	krealloc_array (void *ptr, size_t nmemb, size_t size, int flags)
	Change the size of the given memory block. More...
void *	kmalloc_dma (size_t size)
	Allocate an addressable memory buffer suitable for DMA operations. More...
void	kfree_dma (void *dma_ptr)
	Free a buffer allocated through kmalloc_dma.

Detailed Description

Kmalloc

Kmalloc is the dynamic memory allocator used inside our kernel.

This must not be confused with malloc, which is the dynamic allocator implementation, provided by the libc, used inside user programs.

Design

The kmalloc allocator uses a bucket allocator design.

The idea is to have a mapped space, called a bucket, divided into blocks of the same given size. The size of these blocks is always a power of 2 (8 bytes, 16 bytes, etc.).

When the kernel wants memory, kmalloc chooses the bucket with the smallest block size that can fit the data. There is no metadata stored with the data inside the block, instead a metadata structure is kept at the beginning of each bucket. The free blocks are retrieved using an intrusive linked list, called freelist, whose head is kept inside the bucket's metadata.

Advantages

• Easy to implement
• RCU compatible, thanks to linked-lists
• No memory fragmentation
• Fast allocation

Downsides

• Not the most efficient memory-wise
• No caching for big structures like a slab allocator

Notes

• The minimum size of a block is 16B
• All addresses returned by this allocator are aligned onto a 16B boundary

Function Documentation

kcalloc()

void * kcalloc	(	size_t	nmemb,
		size_t	size,
		int	flags
	)

Parameters

nmemb	The number of members to allocate
size	The size of each members
flags	Feature flags, must be a combination of kmalloc_flags

Returns

The starting address of the newly allocated area

kmalloc()

void * kmalloc	(	size_t	size,
		int	flags
	)

An area allocated using this function MUST be freed manually.

Parameters

size	The number of bytes to allocate
flags	Feature flags, must be a combination of kmalloc_flags

Returns

The starting address of the newly allocated area

kmalloc_dma()

void * kmalloc_dma

(

size_t

size

)

Parameters

size	The size of the buffer

Note

DMA regions are by design always located inside the kernel's space

Returns

A buffer whose physical pageframes are contiguous

krealloc()

void * krealloc	(	void *	ptr,
		size_t	size,
		int	flags
	)

The content of the old memory block is transfered into the first fitting bytes of the new area, and the old one is automatically free'd.

The new area returned by this function MUST be freed manually.

This function can also be called to reallocate a memory block using different feature flags.

Parameters

ptr	Starting address of the memory block
size	New size of the memory block
flags	New flags of the memory block

Returns

The starting address of the relocated area

krealloc_array()

void * krealloc_array	(	void *	ptr,
		size_t	nmemb,
		size_t	size,
		int	flags
	)

See also

kcalloc krealloc