Virtual memory manager, physical memory manager and buddy allocator

Question

I'm writing memory manager for my toy operating system and I would like to get some feedback. There is physical memory manager, which uses bitmap, virtual memory manager which uses buddy algorithm for managing virtual space. Here is my code:

Physical_memory_manager.c

#include <stdint.h>
#include <stdbool.h>
#include <kernel/physical_memory_manager.h>
#include <string.h>
#include <stdio.h>
#include <kernel/common.h>
#include <kernel/math.h>
#include <kernel/bitmap.h>

static uint32_t memory_size_in_kb = 0;
static uint32_t used_blocks = 0;

static uint32_t total_blocks = 0;
static uint32_t *memory_bitmap = 0;

void init_free_region(uint64_t base_address, uint64_t size)
{

    uint64_t block_index = divide_round_up(base_address, BLOCK_SIZE);
    uint64_t number_of_blocks = divide_round_up(size, BLOCK_SIZE);
    printf("Free region address: %lli, number of blocks (4kb): %lli\n", base_address, number_of_blocks);

    for (; number_of_blocks > 0; number_of_blocks--)
    {
        bitmap_unset_bit(block_index++, memory_bitmap);
        used_blocks--;
    }
}

void init_reserved_region(uint32_t base_address, uint32_t size)
{

    uint32_t block_index = divide_round_up(base_address, BLOCK_SIZE);
    uint32_t number_of_blocks = divide_round_up(size, BLOCK_SIZE);

    for (; number_of_blocks > 0; number_of_blocks--)
    {
        bitmap_set_bit(block_index++, memory_bitmap);
        used_blocks++;
    }
}

static inline uint32_t get_free_block_count()
{
    return total_blocks - used_blocks;
}

void *allocate_block()
{

    if (get_free_block_count() <= 0)
        return 0;

    int32_t block_index = get_first_free_block_index(memory_bitmap, total_blocks);

    if (block_index == -1)
        return 0;

    bitmap_set_bit(block_index, memory_bitmap);

    uint32_t addr = block_index * BLOCK_SIZE;
    used_blocks++;
    return (void *)addr;
}

void *allocate_blocks(uint32_t number_of_blocks)
{

    if (get_free_block_count() <= 0)
        return 0;

    int32_t block_index = get_multiple_contiguous_free_blocks(number_of_blocks, total_blocks, memory_bitmap);

    if (block_index == -1)
        return 0;

    for (uint32_t i = 0; i < number_of_blocks; i++)
    {
        bitmap_set_bit(block_index + i, memory_bitmap);
        used_blocks++;
    }

    uint32_t addr = block_index * BLOCK_SIZE;

    return (void *)addr;
}

void free_blocks(void *p, uint32_t number_of_blocks)
{

    uint32_t addr = (uint32_t)p;
    uint32_t block = addr / BLOCK_SIZE;

    for (uint32_t i = 0; i < number_of_blocks; i++)
    {
        bitmap_unset_bit(block, memory_bitmap);
        used_blocks--;
    }
}

void free_block(void *p)
{

    uint32_t addr = (uint32_t)p;
    uint32_t block = addr / BLOCK_SIZE;

    bitmap_unset_bit(block, memory_bitmap);

    used_blocks--;
}

void initialize(memory_info memory_info)
{

    memory_size_in_kb = memory_info.memory_size;
    total_blocks = memory_info.memory_size / BLOCK_SIZE;
    used_blocks = total_blocks;
    uint32_t number_of_ints_in_bitmap = total_blocks / BLOCKS_PER_INT;

    for (uint32_t i = 0; i < memory_info.number_of_free_regions; i++)
    {
        memory_region region = memory_info.free_memory_regions[i];
        if (region.length > number_of_ints_in_bitmap)
        {
            if (region.address < FOUR_GIGABYTE)
            {
                uint32_t address = (uint32_t)region.address;
                memory_bitmap = (uint32_t *)address;
            }
            uint64_t bytes_used_for_bitmap = total_blocks / BLOCKS_PER_BYTE;
            region.address += bytes_used_for_bitmap;
            region.length -= bytes_used_for_bitmap;
            memory_info.free_memory_regions[i] = region;
            break;
        }
    }

    memset(memory_bitmap, 0xffffffff, number_of_ints_in_bitmap);

    for (uint32_t i = 0; i < memory_info.number_of_free_regions; i++)
    {
        memory_region region = memory_info.free_memory_regions[i];
        init_free_region(region.address, region.length);
    }
}

Virtual_memory_manager.c

#include <kernel/virtual_memory_manager.h>
#include <stdint.h>
#include <stdbool.h>
#include <kernel/physical_memory_manager.h>
#include <string.h>
#include <kernel/math.h>
#include <stdio.h>
#include <kernel/memory_detecting.h>
#include <kernel/heap.h>
#include <kernel/buddy_alocator.h>

uint32_t *current_directory = 0;

extern void load_page_directory(uint32_t *);
extern void enable_paging();
extern void flush_tlb_entry(uint32_t *);

free_pages_region_info_t *address_of_first_free_region_kernelspace;
uint32_t next_free_address_for_heap = KERNEL_VIRTUAL_ADDRESS_START + KERNEL_IMAGE_SIZE;

virtual_address next_free_virtual_address;

void allocate_page_for_table(uint32_t table_virtual_address)
{
    physical_address table_physical_address = (physical_address)allocate_block();
    pt_entry page_directory_entry_for_table_address = current_directory[PAGE_TABLE_INDEX(table_virtual_address)];
    page_directory_entry_for_table_address = SET_FRAME(page_directory_entry_for_table_address, table_physical_address);
    page_directory_entry_for_table_address = SET_BIT(page_directory_entry_for_table_address, IS_PRESENT);
    current_directory[PAGE_TABLE_INDEX(table_virtual_address)] = page_directory_entry_for_table_address;
    flush_tlb_entry((uint32_t *)table_virtual_address);
}

void map_page(physical_address physical_addr, virtual_address virtual_addr)
{

    pd_entry page_directory_entry = current_directory[PAGE_DIRECTORY_INDEX(virtual_addr)];
    virtual_address table_virtual_address = VIRTUAL_ADDRESS_OF_PAGE_TABLE_0 + PAGE_DIRECTORY_INDEX(virtual_addr) * PAGE_SIZE;
    if (!IS_BIT_SET(page_directory_entry, IS_PRESENT))
    {
        allocate_page_for_table(table_virtual_address);
    }

    uint32_t *table = (uint32_t *)table_virtual_address;
    pt_entry table_entry = table[PAGE_TABLE_INDEX((uint32_t)virtual_addr)];
    table_entry = SET_FRAME(table_entry, physical_addr);
    table_entry = SET_BIT(table_entry, IS_PRESENT);
    table[PAGE_TABLE_INDEX(virtual_addr)] = table_entry;
    flush_tlb_entry((uint32_t *)virtual_addr);
}

void *allocate_pages(uint32_t number_of_pages)
{

    virtual_address virtual_block_address = (virtual_address)allocate_virtual_block(number_of_pages * PAGE_SIZE);
    if (!virtual_block_address)
    {
        return 0;
    }
    for (uint32_t j = 0; j < number_of_pages; j++)
    {
        physical_address physical_block_address = allocate_block();
        map_page(physical_block_address, virtual_block_address + j * PAGE_SIZE);
    }
    return virtual_block_address;
}

void unmap_page(virtual_address virtual_address)
{
    uint32_t *table = (uint32_t *)(VIRTUAL_ADDRESS_OF_PAGE_TABLE_0 + PAGE_DIRECTORY_INDEX(virtual_address) * PAGE_SIZE);
    physical_address frame_address = GET_FRAME(table[PAGE_TABLE_INDEX(virtual_address)]);
    printf("freeing block: %d", frame_address);
    free_block((void *)frame_address);

    table[PAGE_TABLE_INDEX(virtual_address)] = 0;
}

void free_pages(uint32_t *virtual_address, uint32_t number_of_pages)
{
    free_virtual_block(virtual_address, number_of_pages * PAGE_SIZE);
    for (uint32_t i = 0; i < number_of_pages; i++)
    {
        unmap_page((uint32_t)virtual_address + PAGE_SIZE * i);
    }
}

bool switch_page_directory(uint32_t *directory)
{

    if (!directory)
        return false;

    current_directory = directory;
    load_page_directory(directory);
    return true;
}

uint32_t *allocate_block_for_page_table()
{
    uint32_t *page_table = (uint32_t *)allocate_block();
    if (!page_table)
    {
        return 0;
    }
    memset(page_table, 0, PAGES_PER_TABLE * sizeof(uint32_t));
    return page_table;
}

void identity_map_first_4_megabyte(physical_address physical_address, virtual_address virtual_address, uint32_t *table)
{
    for (uint32_t i = 0; i < PAGES_PER_TABLE; i++)
    {

        pt_entry table_entry = 0;
        table_entry = SET_BIT(table_entry, IS_PRESENT);
        table_entry = SET_FRAME(table_entry, physical_address);

        table[PAGE_TABLE_INDEX(virtual_address)] = table_entry;
        physical_address += BLOCK_SIZE;
        virtual_address += BLOCK_SIZE;
    }
}

void map_pd_entry_to_page_table(uint32_t *table_address, uint32_t page_directory_index, uint32_t *page_directory)
{
    uint32_t pd_entry = 0;
    pd_entry = SET_BIT(pd_entry, IS_PRESENT);
    pd_entry = SET_BIT(pd_entry, IS_WRITABLE);
    pd_entry = SET_FRAME(pd_entry, (physical_address)table_address);
    page_directory[page_directory_index] = pd_entry;
}

void map_kernel_to_3_gb(physical_address physical_address, virtual_address virtual_address, uint32_t *page_dir)
{
    for (uint32_t i = 0; i < KERNEL_IMAGE_SIZE / (PAGES_PER_TABLE * PAGE_SIZE); i++)
    {
        uint32_t *table_physical_and_virtual_address = allocate_block_for_page_table();
        for (uint32_t i = 0; i < PAGES_PER_TABLE; i++)
        {

            pt_entry table_entry = 0;
            table_entry = SET_BIT(table_entry, IS_PRESENT);
            table_entry = SET_FRAME(table_entry, physical_address);

            table_physical_and_virtual_address[PAGE_TABLE_INDEX(virtual_address)] = table_entry;
            physical_address += BLOCK_SIZE;
            virtual_address += BLOCK_SIZE;
        }
        map_pd_entry_to_page_table(table_physical_and_virtual_address, PAGE_DIRECTORY_INDEX(KERNEL_VIRTUAL_ADDRESS_START + BLOCK_SIZE * PAGES_PER_TABLE * i), page_dir);
    }
}

void set_up_paging()
{

    uint32_t *page_dir = (uint32_t *)allocate_blocks(divide_round_up(sizeof(uint32_t) * PAGE_TABLES_PER_DIRECTORY, BLOCK_SIZE));
    if (!page_dir)
    {
        return;
    }
    memset(page_dir, 0, PAGE_TABLES_PER_DIRECTORY * sizeof(uint32_t));

    uint32_t *identity_map_page_table = allocate_block_for_page_table();

    identity_map_first_4_megabyte(0, 0, identity_map_page_table);

    map_pd_entry_to_page_table(page_dir, RECURSIVELY_MAPPED_PAGE_DIRECTORY_INDEX, page_dir);
    map_pd_entry_to_page_table(identity_map_page_table, 0, page_dir);

    map_kernel_to_3_gb(KERNEL_LOCATION_START, KERNEL_VIRTUAL_ADDRESS_START, page_dir);

    switch_page_directory(page_dir);

    enable_paging();
}

void initialize_virtual_memory_regions()
{
    virtual_address address_for_buddy_region_infos = VIRTUAL_MEMORY_START + power(2, log2(KERNEL_VIRTUAL_ADDRESS_START - VIRTUAL_MEMORY_START));
    physical_address physical_block = (physical_address)allocate_block();

    map_page(physical_block, address_for_buddy_region_infos);
    initialize_buddy_blocks(KERNEL_VIRTUAL_ADDRESS_START, address_for_buddy_region_infos);
    next_free_virtual_address = address_for_buddy_region_infos + PAGE_SIZE;
}

virtual_address allocate_page()
{
    void *physical_block = allocate_block();
    if (!physical_block || next_free_virtual_address == KERNEL_VIRTUAL_ADDRESS_START)
    {
        return 0;
    }
    virtual_address virtual_addr = next_free_virtual_address;
    map_page((physical_address)physical_block, virtual_addr);
    next_free_virtual_address += PAGE_SIZE;
    return virtual_addr;
}

buddy_allocator.c

#include <kernel/buddy_alocator.h>
#include <kernel/virtual_memory_manager.h>
#include <string.h>
#include <kernel/math.h>
#include <kernel/bitmap.h>

free_block_info_t *first_free_region_info;
regions_bitmap_info_t *first_regions_bitmap;

extern inline uint32_t get_regions_bitmap_size()
{
    return PAGE_SIZE / (8 * sizeof(free_block_info_t) + 1); // page size - size of bitmap = number of structs * size of struct in bytes, number of structs = 8 * size of bitmap in bytes
}

regions_bitmap_info_t *create_bitmap_info(virtual_address address)
{
    regions_bitmap_info_t *bitmap_info = (regions_bitmap_info_t *)address;
    memset(bitmap_info, 0, sizeof(regions_bitmap_info_t));
    uint32_t *bitmap = (uint32_t)bitmap_info + sizeof(regions_bitmap_info_t);
    uint32_t regions_bitmap_size = get_regions_bitmap_size();
    memset(bitmap, 0, regions_bitmap_size);
    bitmap_info->bitmap = bitmap;
    return bitmap_info;
}

void initialize_buddy_blocks(virtual_address free_addresses_end, virtual_address address_for_first_free_region_info)
{
    first_regions_bitmap = create_bitmap_info(address_for_first_free_region_info);

    first_free_region_info = (free_block_info_t *)((uint32_t)first_regions_bitmap->bitmap + get_regions_bitmap_size());
    memset(first_free_region_info, 0, sizeof(free_block_info_t));
    first_free_region_info->address_of_block = 0;
    first_free_region_info->next_block = 0;
    first_free_region_info->previous_block = 0;
    first_free_region_info->size_class = log2(free_addresses_end - VIRTUAL_MEMORY_START);
    first_free_region_info->regions_bitmap_info = first_regions_bitmap;
    bitmap_set_bit(0, first_regions_bitmap->bitmap);
}

void free_given_block_info(free_block_info_t *block)
{
    regions_bitmap_info_t *bitmap_info = first_regions_bitmap;
    uint32_t *bitmap = 0;
    while (bitmap_info != block->regions_bitmap_info && bitmap_info->next_bitmap)
    {
        bitmap_info = bitmap_info->next_bitmap;
    }
    uint32_t index_in_regions_bitmap = (uint32_t)block - ((uint32_t)bitmap_info->bitmap + get_regions_bitmap_size());
    index_in_regions_bitmap /= sizeof(free_block_info_t);
    bitmap_unset_bit(index_in_regions_bitmap, bitmap_info->bitmap);
}

free_block_info_t *allocate_free_block_info()
{
    uint32_t number_of_blocks = get_regions_bitmap_size() * BITS_PER_BYTE;

    regions_bitmap_info_t *bitmap_info = first_regions_bitmap;
    int32_t first_free_block = -1;
    while (bitmap_info)
    {
        first_free_block = get_first_free_block_index(bitmap_info->bitmap, number_of_blocks);
        if (first_free_block != -1)
        {
            printf("b %d,", first_free_block);
            bitmap_set_bit(first_free_block, bitmap_info->bitmap);
            free_block_info_t *free_block_info = (free_block_info_t *)((uint32_t)bitmap_info->bitmap + get_regions_bitmap_size() + first_free_block * sizeof(free_block_info_t));
            memset(free_block_info, 0, sizeof(free_block_info_t));
            free_block_info->regions_bitmap_info = bitmap_info;
            return free_block_info;
        }
        bitmap_info = bitmap_info->next_bitmap;
    }

    virtual_address new_page = allocate_page();
    if (!new_page)
    {
        return 0;
    }
    regions_bitmap_info_t *new_bitmap_info = create_bitmap_info(new_page);

    regions_bitmap_info_t *last_bitmap = first_regions_bitmap;
    while (last_bitmap->next_bitmap)
    {
        last_bitmap = last_bitmap->next_bitmap;
    }
    last_bitmap->next_bitmap = new_bitmap_info;
    return allocate_free_block_info();
}

void *allocate_virtual_block(uint32_t request_size)
{
    free_block_info_t *block = first_free_region_info;
    while (block->next_block && request_size > power(2, block->size_class))
    {
        block = block->next_block;
    };

    uint32_t size_class = block->size_class;

    while (size_class >= MINIMUM_BUDDY_BLOCK_SIZE_CLASS && request_size <= power(2, size_class - 1))
    {
        uint32_t buddy_address = TOGGLE_BIT(block->address_of_block, size_class - 1);
        free_block_info_t *buddy_block = allocate_free_block_info();
        if (!buddy_block)
        {
            return 0;
        }
        buddy_block->address_of_block = buddy_address;
        if (block->next_block)
        {
            block->next_block->previous_block = buddy_block;
        }
        buddy_block->size_class = size_class - 1;
        buddy_block->next_block = block->next_block;
        block->next_block = buddy_block;
        size_class--;
        block->size_class = size_class;
    };
    free_block_info_t *buddy = block->next_block;
    if (block->previous_block)
    {
        block->previous_block->next_block = buddy;
    }
    if (block->next_block)
    {
        block->next_block->previous_block = block->previous_block;
    }
    if (block == first_free_region_info)
    {
        first_free_region_info = buddy;
    }
    free_given_block_info(block);
    return (void *)block->address_of_block + VIRTUAL_MEMORY_START;
}

void create_new_block(virtual_address address, uint32_t size_class, free_block_info_t *block)
{
    free_block_info_t *new_free_block = (free_block_info_t *)allocate_free_block_info();
    if (!new_free_block)
    {
        printf("No more memory");
        return;
    }
    new_free_block->address_of_block = address;
    new_free_block->size_class = size_class;
    new_free_block->next_block = block;
    new_free_block->previous_block = block->previous_block;
    new_free_block->previous_block->next_block = new_free_block;
    block->previous_block = new_free_block;
    if (block == first_free_region_info)
    {
        first_free_region_info = new_free_block;
    }
}

void free_virtual_block(virtual_address address, uint32_t size)
{
    address -= VIRTUAL_MEMORY_START;
    uint32_t size_class_of_freed_block = log2(size - 1) + 1;
    uint32_t buddy_address = TOGGLE_BIT(address, size_class_of_freed_block);
    free_block_info_t *block = first_free_region_info;
    while (block && block->address_of_block < buddy_address)
    {

        block = block->next_block;
    }
    if (!block || block->address_of_block != buddy_address)
    {
        create_new_block(address, size_class_of_freed_block, block);
        return;
    }
    if (block->size_class == size_class_of_freed_block)
    {
        uint32_t size_class = size_class_of_freed_block + 1;
        block->size_class++;
        block->address_of_block = min(address, buddy_address);

        free_block_info_t *adjacent_block = block;
        while (adjacent_block)
        {
            buddy_address = TOGGLE_BIT(block->address_of_block, block->size_class);
            if (buddy_address < block->address_of_block)
            {
                adjacent_block = block->previous_block;
            }
            else
            {
                adjacent_block = block->next_block;
            }

            if (adjacent_block->size_class == size_class && adjacent_block->address_of_block == buddy_address)
            {
                if (buddy_address < block->address_of_block)
                {
                    block->previous_block = adjacent_block->previous_block;
                }
                else
                {
                    block->next_block = adjacent_block->next_block;
                }
                if (adjacent_block == first_free_region_info)
                {
                    first_free_region_info = block;
                }
                free_given_block_info(adjacent_block);
                size_class++;
                block->size_class++;
                block->address_of_block = min(block->address_of_block, adjacent_block->address_of_block);
                adjacent_block = block->next_block;
            }
            else
            {
                return;
            }
        }
    }
}

buddy_allocator.h

#ifndef BUDDY_ALOCATOR_H
#define BUDDY_ALOCATOR_H

#include <kernel/virtual_memory_manager.h>
#include <stdint.h>
#include <stdbool.h>
#include <kernel/bitmap.h>

#define MINIMUM_BUDDY_BLOCK_SIZE_CLASS 12
#define SIZE_OF_BLOCK_REGIONS_INFO_BITMAP ((PAGE_SIZE) / (BLOCKS_PER_INT))

typedef struct free_block_info
{
    virtual_address address_of_block;
    uint32_t size_class; // exponent of power of 2
    struct free_block_info *previous_block;
    struct free_block_info *next_block;
    regions_bitmap_info_t *regions_bitmap_info;

} free_block_info_t;

void initialize_buddy_blocks(virtual_address free_addresses_end, virtual_address address_for_first_buddy_region_info);
void *allocate_virtual_block(uint32_t request_size);
void free_virtual_block(virtual_address address, uint32_t size);

#endif

physical_memory_manager.h

#ifndef PHYSICAL_MEMORY_MANAGER
#define PHYSICAL_MEMORY_MANAGER

#include <stdint.h>
#include <stdbool.h>

#define BLOCKS_PER_BYTE 8
#define BLOCK_SIZE 4096
#define BLOCK_ALIGNMENT BLOCK_SIZE

typedef struct
{
    uint64_t address;
    uint64_t length;
} memory_region;

typedef struct
{

    uint64_t memory_size;
    memory_region *free_memory_regions;
    uint32_t number_of_free_regions;

} memory_info;

void initialize(memory_info memory_info);

void *allocate_block();
void free_block(void *p);
void *allocate_blocks(uint32_t number_of_blocks);
void free_blocks(void *p, uint32_t number_of_blocks);

#endif

virtual_memory_manager.h

#ifndef PAGE_TABLE_ENTRY
#define PAGE_TABLE_ENTRY

#include <stdint.h>
#include <stdbool.h>
#include <kernel/heap.h>

#define PAGES_PER_TABLE 1024
#define PAGE_TABLES_PER_DIRECTORY 1024

#define PAGE_DIRECTORY_INDEX(x) (((x) >> 22) & 0x3ff)
#define PAGE_TABLE_INDEX(x) (((x) >> 12) & 0x3ff)

#define SET_BIT(pte, bit) ((pte) | (1 << (bit)))
#define UNSET_BIT(pte, bit) ((pte) & ~(1 << (bit)))
#define IS_BIT_SET(pte, bit) ((pte) & (1 << (bit)))
#define TOGGLE_BIT(number, bit_index) ((number) ^ (1 << (bit_index)))
#define SET_FRAME(pte, address) ((pte) | (address))
#define GET_FRAME(pte) ((pte)&0xFFFFF000)

#define RECURSIVELY_MAPPED_PAGE_DIRECTORY_INDEX 1023

#define VIRTUAL_ADDRESS_OF_PAGE_TABLE_0 0xffc00000

#define KERNEL_IMAGE_SIZE 16777216

#define PAGE_SIZE 4096
#define VIRTUAL_MEMORY_LIMIT_32_BIT 0xFFFFFFFF

#define VIRTUAL_MEMORY_START 0x400000

typedef uint32_t pt_entry;
typedef uint32_t pd_entry;

typedef uint32_t virtual_address;
typedef uint32_t physical_address;

enum PTE_BIT_NUMBERS
{

    IS_PRESENT = 0,
    IS_WRITABLE = 1,
    USER_MODE = 2,
    WRITETHOUGH = 3,
    NOT_CACHEABLE = 4,
    IS_ACCESSED = 5,
    IS_DIRTY = 6,
    PAT = 7,
    CPU_GLOBAL = 8,
    LV4_GLOBAL = 9,
};

typedef struct free_pages_region_info
{

    virtual_address address;
    uint32_t number_of_pages;
    struct free_pages_region_info *address_of_next_region_info;

} free_pages_region_info_t;

void set_up_paging();
void *allocate_pages(uint32_t number_of_pages);
free_region_info_t *allocate_pages_for_heap();
virtual_address allocate_page();
void free_pages(uint32_t *virtual_address, uint32_t number_of_pages);
void initialize_virtual_memory_regions();

#endif
```