Help with memory manager.

[Quaker763]

Hi!

So I've followed the barebones tutorial, written a screen function, keyboard driver etc and am now at the point where I want to write a physical memory manager. I'm not sure how I should really go about doing it. I've read everything on the wiki and I'm still pretty stuck.

Basically, what I'm thinking, is having a doubly linked list to keep track of all of the blocks of memory, so each block points to the block before it and the block after it. Each block has a flags variable that tells the memory manager about the block. However, I can see two problems with this.

1. I don't know where to start the first block. I assume it would be somewhere after my kernel, but I don't know where the kernel is located. If it's high up, I could waste a heap of memory.
2. Freeing blocks could be a pain and I could have memory fragmentation up the whazoo.

Currently, the code I have looks something like this (note it's not finished):

Code: Select all

void* kalloc_block(uint32_t size)
{
    block_t* block = head;

    //Whoa... Something's wrong..
    if(head == NULL)
    {
        kpanic("memmmngr: Head is NULL", NULL);
    }

    while(block != NULL || block->flags & ~BLOCK_FREE)
    {

        //IMPORTANT NOTE: WE NEED TO ITERATE CURRENT POINTER LOCATION + CURRENT BLOCK SIZE!!!!!!!!
        //Looks like we've found a free block!
        if(block->next == NULL)
            break; //Get me outta here!



        kprintc("This block is taken!\n", 0x0C);
        block = block + block->size;
    }

    kprintc("Allocating a block!\n", 0x0A);

}

Where block_t is defined as:

Code: Select all

struct memblock
{
    struct memblock* prev; //Link to previous block

    /*BLOCK HEADER; 9-bytes wasted...*/
    uint32_t size; //Size of the block. This should be aligned
    uint8_t flags; //Block flags
    struct memblock* next;
};

I'm not really sure how I should go about finding the next block? Should I increment the current pointer by the size and then set that as the next block (if it's free)?

Sorry for such a basic question!

[BASICFreak]

You will want to page align the PMM table just after the kernel (add a variable to your link script such as eok)

With physical memory, assuming you will also be using virtual memory, you only need to keep track of free space not used.

The way I have do my PMM is storing Start Address and Length (both as 4K pages) using two uint32_t's (Base and Length), and each page can hold 64 fragments.

After each free() command I defragment the PMM Table so I don't end up with a million fragments. (my first test didn't do this and I ended up with 256K free ram due to not merging entries, and a page fault on next allocation of more than 4096 Bytes)

Each _PMM_malloc (as malloc is in my heap manager) will search by the length field for a segment of memory large enough for the request, allocates from the beginning of the block and Base += requested size and Length -= requested size. Returns the old Base.

As far as I can tell there is no need for flags in memory management (at least physical)


I am curious why you want to use a double linked list for PMM, IMNSHO it seems it would be slower and not provide any additional benefit.

[jnc100]

There are very few situations where you want your physical memory manager to return anything other that a page-sized area of memory. The only exceptions which spring to mind are OS-allocated buffers for certain hardware devices e.g. network cards where you may want a buffer larger that 4 kiB, but these situations are so rare that they can be special-cased later (note for simplicity's sake I am ignoring large pages here). Additionally, if you plan on supporting a virtual memory layer on top, then fragmentation is not a problem and you do not need to concern yourself with returning consecutive pages on each call to the alloc function.

Therefore, all you really need is some sort of data structure that contains a list of all available (page-sized) memory blocks, and can return one on demand. There is a discussion of the various algorithms available at Page Frame Allocation.

Obviously, somehow you need to initialize the structure with those memory areas which are 'known good'. Given that you state you are following barebones, I will assume you have booted from GRUB, which provides a memory map of all free/used areas for you, which you simply need to parse and feed into your memory manager. Note that GRUB does not mark your kernel, or any additional modules, as used in the memory map, and you will need to do this additionally. There are various methods available to determine where your kernel is loaded in memory for example Using Linker Script Values to insert a place marker for the beginning and end of your kernel.

Regards,
John.

[Quaker763]

You will want to page align the PMM table just after the kernel (add a variable to your link script such as eok)

With physical memory, assuming you will also be using virtual memory, you only need to keep track of free space not used.

The way I have do my PMM is storing Start Address and Length (both as 4K pages) using two uint32_t's (Base and Length), and each page can hold 64 fragments.

After each free() command I defragment the PMM Table so I don't end up with a million fragments. (my first test didn't do this and I ended up with 256K free ram due to not merging entries, and a page fault on next allocation of more than 4096 Bytes)

Each _PMM_malloc (as malloc is in my heap manager) will search by the length field for a segment of memory large enough for the request, allocates from the beginning of the block and Base += requested size and Length -= requested size. Returns the old Base.

Okay, so I should basically just use the MMU through the CPU then? Sorry, the amount of information on the topic has me REALLY bamboozled..

I am curious why you want to use a double linked list for PMM, IMNSHO it seems it would be slower and not provide any additional benefit.

I'm not too sure to be honest. I guess it seemed logical to me, as in each block points to the next block and so forth (I guess sort of like Linux's 'buddy' system [sort of haha]).

Therefore, all you really need is some sort of data structure that contains a list of all available (page-sized) memory blocks, and can return one on demand. There is a discussion of the various algorithms available at Page Frame Allocation.

So, what order should I do things in, then? I've seen bitmaps used before (as is shown on the page), but if I use a bitmap, do I even bother using the MMU (with paging/virtual memory)

EDIT*

There are various methods available to determine where your kernel is loaded in memory for example Using Linker Script Values to insert a place marker for the beginning and end of your kernel.

Thank you, that's done the trick.

Sorry for such basic questions, I know they've probably been asked a million times before, I'm just really stumped at the moment.

[BASICFreak]

I don't feel like quoting multiple times so I'll just list facts (to my knowledge):

Either way you look at it you SHOULD use the MMU. (The MMU deals with virtual to physical addressing and permissions for said address. - If you don't use the MMU you will have to use memory segmentation in the GDT, which to me does not seem worth it.

A bitmap is the easiest solution but also one of the slowest, as you use more memory the loop to find a free page will get longer and longer. I have used this method in my first PMM - it worked well, but I also only use 512KB of RAM and if I allocated more it would have slowed.

Here is an example of my PMM:

Code: Select all

typedef struct PMM_Entry {
	uint32_t Base;
	uint32_t Length;
} __attribute__((packed)) PMME_t, *PMME_p;

typedef struct PMM_Stack {
	PMME_t Entry[64];
} __attribute__((packed)) PMMS_t, *PMMS_p;

PMMS_p PMMStack;
void _PMM_free(uint32_t Addr, uint32_t Len)
{
	for(int e = 0; e < _PMM_MAXENT; e++)
		if(PMMStack->Entry[e].Length == 0) {
			PMMStack->Entry[e].Base = (Addr >> 12);
			PMMStack->Entry[e].Length = Len;
			// Need to Defrag ...
			_PMM_defrag();
			_PMM_update();
			return;
		}
}

void *_PMM_malloc(uint32_t Pages)
{
	for (int e = 0; e < _PMM_MAXENT; e++)
		if(PMMStack->Entry[e].Length >= Pages) {
			//Do stuff
			uint32_t TempBase = PMMStack->Entry[e].Base;
			PMMStack->Entry[e].Base += Pages;
			PMMStack->Entry[e].Length -= Pages;
			_PMM_update();
			return (void*) (TempBase * 0x1000);
		}
	return 0; // returns 0 on error (remember the first 64KB are Reserved By Kernel)
}

NOTE: I am not the best coder on the forums and my code may look terrible, but it works so far for what I needed. And also remember there are millions of ways to "skin a cat" and one's solution may not be suitable for another.

P.S. I reread my first post and it seems I got the wrong point across:
When I said each page holds 64-fragments I was talking about the PMM Table, not the actual pages being allocated. As the smaller fragments are done VIA my heap manager - which calls VMM which calls PMM.

[jnc100]

So, what order should I do things in, then? I've seen bitmaps used before (as is shown on the page), but if I use a bitmap, do I even bother using the MMU (with paging/virtual memory)

You should also have a separate virtual memory manager. The role of this is to create and manage individual 'address spaces' for every process running on the system. The address space is the sum total of all memory available to the process and (on IA-32) is 4 GiB in size. Typically it contains the code and data for the process, along with (in a monolithic design) the kernel. Having a separate address space per process has several advantages: you get the full 4 GiB per process (rather than having to share it) and all of your processes can run at the same (virtual) address i.e. you don't need special linker options per process. If you don't use the virtual memory capabilities of your processor then you need to run each process at a different memory location (otherwise they would overwrite each other).

The way a virtual memory manager actually works is that it creates 'paging structures' (page directories and tables and other levels in paging models other than the default IA-32 one) which are then fed to the CPU's MMU, which does the actual virtual->physical translation in hardware.

Obviously the virtual memory manager needs to get the physical memory from somewhere (which is where your physical memory manager comes in) and then build an address space from that memory for each process. As the virtual manager deals with regions rather than individual pages, you probably want to implement it using data structures more like what you originally described (e.g. a linked list), however if you fix the number of regions (e.g. kernel code, kernel data, kernel stack, kernel heap, process code, data, stack and heap) you can do away with this requirement.

Thus to summarise, classically what you'd do is have a physical memory manager with one function: uintptr AllocPage(), and a virtual memory manager with functions like: uintptr CreateAddressSpace(); void MapPage(uintptr virtual_address, uintptr physical_address);

Note this is a great oversimplification and avoids topics like PAE, allocate-on-demand, memory-mapped files etc which your virtual manager should one day also support.

Regards,
John.

[Brendan]

Hi,

So I've followed the barebones tutorial, written a screen function, keyboard driver etc and am now at the point where I want to write a physical memory manager. I'm not sure how I should really go about doing it. I've read everything on the wiki and I'm still pretty stuck.

You're not the first and won't be the last. I think the problem is that wiki is missing some "higher level theory" to tie the practical information (examples, paging mechanics, etc) together.

With this in mind I've created Brendan's Memory Management Guide. Hopefully it helps to fill the gap and isn't too awful.


Cheers,

Brendan

[Quaker763]

Sorry for the late reply, I've been a bit busy (got final exams in 2 months )

I think I get somewhat get it now. Basically I'd have Physical memory manager->Paged/Virtual Memory Manager->something like a heap/malloc that a programmer would use?

Thanks for all the help so far guys, I really appreciate it.

[linguofreak]

Sorry for the late reply, I've been a bit busy (got final exams in 2 months )

I think I get somewhat get it now. Basically I'd have Physical memory manager->Paged/Virtual Memory Manager->something like a heap/malloc that a programmer would use?

Yes, though the heap manager that would be part of your kernel would be for the kernel's use only and wouldn't be the one used by programmers writing applications (which would be part of their programming language's runtime library and would get memory from the OS using the virtual memory manager).