The buddy allocator: physical memory, in blocks of 2^n pages. More...

#include <core/system.h>
#include <core/panic.h>
#include <ds/bitmap.h>
#include <ds/buddy.h>
#include <mm/buddy.h>
#include <boot/boot.h>

Data Structures
struct	[struct].reserved

Macros
#define	RESERVED_MAX 64

Functions
static void *	alloc (size_t size, size_t align)
	Allocates memory for the bitmaps at boot, from what mm_setup() set aside: their size depends on how much RAM there is.
static size_t	buddy_recursive_alloc (int zone, size_t order)
	Takes a free block of order order from zone, splitting a bigger block if there is none.
static void	buddy_recursive_free (int zone, size_t order, size_t idx)
	Frees the block at index idx of order order in zone, merging it with its buddy, and that block with its own, as long as they are free.
static void	buddy_reserved_done (void)
	Frees the pages of the blocks set unusable at boot that no reserved range covers, at the first allocation.
paddr_t	buddy_alloc (int zone, size_t _sz)
	Allocates a block of physical memory from a zone, rounded up to a power of two pages.
void	buddy_free (int zone, paddr_t addr, size_t size)
	Frees a block that buddy_alloc() gave.
void	buddy_set_unusable (paddr_t addr, size_t size)
	Marks a range of physical memory as not free, at boot, before the first allocation: the kernel, the modules, the firmware's ranges.
static int	reserved_page (paddr_t page)
	Returns whether a range set unusable at boot covers page.
int	buddy_setup (size_t total_mem)
	Sets up the allocator at boot: a bitmap for each zone and order, every top-order block of RAM free, then the kernel and its symbol tables set unusable.

Variables
size_t	k_total_mem
size_t	k_used_mem
static uintptr_t	kstart = 0
static uintptr_t	kend = 0
static struct	reserved [RESERVED_MAX]
static int	reserved_nr
static int	reserved_done
static size_t	zone_blocks [BUDDY_ZONE_NR]
struct buddy	buddies [BUDDY_ZONE_NR][BUDDY_MAX_ORDER+1]
uintptr_t	buddy_zone_offset [BUDDY_ZONE_NR+1]

Detailed Description

The buddy allocator: physical memory, in blocks of 2^n pages.

Each zone of RAM has one bitmap per block size (order), from one page (order 0) to BUDDY_MAX_BS (order BUDDY_MAX_ORDER); a set bit is a block that isn't free. Allocating takes a free block of the size asked for, or splits a bigger one in two "buddies", one used and one free, as many times as needed. Freeing a block merges it with its buddy when that one is free too, and so on up. Both take a few steps, whatever the amount of RAM. See docs/kernel/memory.md.

Definition in file buddy.c.

Macro Definition Documentation

◆ RESERVED_MAX

#define RESERVED_MAX 64

Definition at line 29 of file buddy.c.

Referenced by buddy_set_unusable().

Function Documentation

◆ alloc()

void * alloc	(	size_t	size,
		size_t	align )

inlinestatic

Allocates memory for the bitmaps at boot, from what mm_setup() set aside: their size depends on how much RAM there is.

Definition at line 42 of file buddy.c.

References mm_boot_alloc().

Referenced by buddy_setup().

◆ buddy_alloc()

paddr_t buddy_alloc	(	int	zone,
		size_t	_sz )

Allocates a block of physical memory from a zone, rounded up to a power of two pages.

Parameters

zone	the zone to take it from (BUDDY_ZONE_DMA or BUDDY_ZONE_NORMAL)
_sz	the size wanted, in bytes, at most BUDDY_MAX_BS

Returns: the block's physical address, or (paddr_t) -1 if the zone has no free block that large

Definition at line 149 of file buddy.c.

References buddy_alloc(), BUDDY_MAX_BS, BUDDY_MAX_ORDER, BUDDY_MIN_BS, buddy_recursive_alloc(), buddy_reserved_done(), buddy_zone_offset, k_used_mem, panic, and reserved_done.

Referenced by buddy_alloc(), and mm_page_alloc().

◆ buddy_free()

void buddy_free	(	int	zone,
		paddr_t	addr,
		size_t	size )

Frees a block that buddy_alloc() gave.

Parameters

zone	the zone it came from
addr	its physical address
size	the size that was asked for, in bytes

Definition at line 183 of file buddy.c.

References buddy_free(), BUDDY_MAX_ORDER, BUDDY_MIN_BS, buddy_recursive_free(), buddy_zone_offset, k_used_mem, kend, kstart, and panic.

Referenced by buddy_free(), and mm_page_dealloc().

◆ buddy_recursive_alloc()

size_t buddy_recursive_alloc	(	int	zone,
		size_t	order )

static

Takes a free block of order order from zone, splitting a bigger block if there is none.

Returns its index in that order's bitmap, or (size_t) -1 if the zone has no free block that large.

Definition at line 60 of file buddy.c.

References buddy::bitmap, buddies, BUDDY_IDX, BUDDY_MAX_ORDER, buddy_recursive_alloc(), buddy::first_free_idx, bitmap::max_idx, and buddy::usable.

Referenced by buddy_alloc(), and buddy_recursive_alloc().

◆ buddy_recursive_free()

void buddy_recursive_free	(	int	zone,
		size_t	order,
		size_t	idx )

static

Frees the block at index idx of order order in zone, merging it with its buddy, and that block with its own, as long as they are free.

Definition at line 113 of file buddy.c.

References buddies, BUDDY_IDX, BUDDY_MAX_ORDER, buddy_recursive_free(), buddy::first_free_idx, bitmap::max_idx, and buddy::usable.

Referenced by buddy_free(), buddy_recursive_free(), and buddy_reserved_done().

◆ buddy_reserved_done()

void buddy_reserved_done ( void )

static

Frees the pages of the blocks set unusable at boot that no reserved range covers, at the first allocation.

They merge back into bigger blocks as they would; the other pages stay used. After this, what is free is all of RAM except what is reserved, to the page.

Definition at line 289 of file buddy.c.

References buddy::bitmap, buddies, BUDDY_MAX_BS, BUDDY_MAX_ORDER, BUDDY_MIN_BS, buddy_recursive_free(), buddy_reserved_done(), BUDDY_ZONE_NR, buddy_zone_offset, k_total_mem, k_used_mem, reserved_done, reserved_page(), and zone_blocks.

Referenced by buddy_alloc(), and buddy_reserved_done().

◆ buddy_set_unusable()

void buddy_set_unusable	(	paddr_t	addr,
		size_t	size )

Marks a range of physical memory as not free, at boot, before the first allocation: the kernel, the modules, the firmware's ranges.

Parameters

addr	the range's start
size	its size, in bytes (0 does nothing)

Definition at line 212 of file buddy.c.

References buddy::bitmap, buddies, BUDDY_MAX_BS, BUDDY_MAX_ORDER, BUDDY_MIN_BS, buddy_set_unusable(), BUDDY_ZONE_NR, buddy_zone_offset, buddy::first_free_idx, MAX, bitmap::max_idx, MIN, panic, printk(), reserved, reserved_done, RESERVED_MAX, reserved_nr, and buddy::usable.

Referenced by arch_mm_setup(), buddy_set_unusable(), buddy_setup(), mm_mark_unusable(), and mm_setup().

◆ buddy_setup()

int buddy_setup ( size_t total_mem )

Sets up the allocator at boot: a bitmap for each zone and order, every top-order block of RAM free, then the kernel and its symbol tables set unusable.

Parameters

total_mem the end of RAM, in bytes

Returns: 0

Definition at line 328 of file buddy.c.

References __kboot, alloc(), buddy::bitmap, bitmap_clear_range(), bitmap_set_range(), bitmap_size(), buddies, BUDDY_MAX_BS, BUDDY_MAX_ORDER, buddy_set_unusable(), buddy_setup(), BUDDY_ZONE_NR, buddy_zone_offset, buddy::first_free_idx, k_total_mem, k_used_mem, kend, kernel_end, kstart, LMA, bitmap::map, bitmap::max_idx, MIN, printk(), elf32_shdr::sh_addr, elf32_shdr::sh_size, boot::shdr, boot::strtab, boot::symtab, buddy::usable, and zone_blocks.

Referenced by buddy_setup(), and mm_setup().

◆ reserved_page()

int reserved_page ( paddr_t page )

static

Returns whether a range set unusable at boot covers page.

Definition at line 274 of file buddy.c.

References reserved, reserved_nr, and reserved_page().

Referenced by buddy_reserved_done(), and reserved_page().

Variable Documentation

◆ buddies

struct buddy buddies[BUDDY_ZONE_NR][BUDDY_MAX_ORDER+1]

Definition at line 48 of file buddy.c.

Referenced by buddy_recursive_alloc(), buddy_recursive_free(), buddy_reserved_done(), buddy_set_unusable(), buddy_setup(), and procfs_buddyinfo().

◆ buddy_zone_offset

uintptr_t buddy_zone_offset[BUDDY_ZONE_NR+1]

Initial value:

                            = {
    [BUDDY_ZONE_DMA]     = 0,           
    [BUDDY_ZONE_NORMAL]  = 0x1000000,   
    [BUDDY_ZONE_NR]      = (uintptr_t) -1,
}