Best way to dynamically allocate memory early on?

[j4cobgarby]

I'm at the stage of beginning to implement processes and paging tables for the processes. Every time I start thinking about how I'll implement these things, I hit a brick wall when I need to allocate an amount of memory somewhere of which I don't know the size at compile time.

For example, for my process table. I don't know how many processes there willll be before they're created, and so I'd need to grow this table whenever a new process is created. Alternatively, I could make the table way bigger than I'd reasonably need and just limit the processes allowed to the size of it at boot, but that would be a huge waste of memory.

Another time this problem comes up is when reading the mmap table from the multiboot info (I'm using the GRUB bootloader, so this is my best way of getting a memory map). I want to copy the memory map to somewhere in kernel space, so that I can use it whenever I want without worrying about overwriting the place where the mmap table originally came from. However, the mmap table has a size specified by a value in the multiboot info. What's the best way here to allocate enough space somewhere in the kernel to store this table?

I feel like this should be a relatively simple thing that I'm just not seeing.

Thanks for any advice

[iansjack]

You need to write some sort of memory allocator to dish out memory as needed. Tables of unknown size, such as process tables, can be implemented as linked lists rather than arrays so you allocate the memory dynamically as you need it rather than allocating it at compile time. This also lets you reclaim memory when you are not using it.

Allocating pages of physical memory is fairly easy - you could just have a bitmap representing all the available pages which keeps track of which pages are allocated and which are free. Rather more complicated is dealing out variable-sized blocks of memory (heap memory), which is where the allocator comes in. Memory allocation is a very frequent process, so it's important that your allocator is as efficient as possible. Fairly simple implementations are a simple linked list and the buddy allocator. Have a look here for some ideas: https://wiki.osdev.org/Memory_Allocatio ... ry_Manager

[iProgramInCpp]

My method of allocation is kind of limited, in that it can have up to 32768 blocks allocated. However, I wouldn't need more than that in my simple OS, and it's easy to expand. The 32k+ blocks can be any size, including less than 4096 bytes. Sadly, it doesn't make use of paging, but you don't need it for a "simple" OS that does simple stuff with memory. Later on, you will need what the other people suggested.

[AndrewAPrice]

I found liballoc very easy to port into both the kernel and userland. It's a .c and .h file, and you implement some hooks to grab free pages and release pages.

You should have a physical memory manager (here's my kernel) that manages physical memory pages. Get a free memory page, release this memory page, etc.

You should have a virtual memory manager (here's my kernel) that manages virtual memory pages. Scan through the page table to find a free range, allocate a page in kernel memory, allocate page in user memory, etc.

Some of those functions in my code are suffixed with ..PreVirtualMemory because I set up a temporary paging system before I jump to long mode and we have to work with those before we set up our permanent paging system. Just make sure that intializing your physical + virtual memory managers is one of the first things you do.

If you use 4 KiB pages - the nice thing is that your memory pages and structures (page tables, etc.) are the same size. So if you have implemented "Grab Page", "Release Page", you have all you need to initialize your physical + virtual manager, and all you need to implement the liballoc hooks, then you can use malloc/free in your kernel.

[neon]

Hi,

We use a hierarchy of techniques: a free stack is used for frame allocation. A PTE free list is used for allocating pages as the kernel pool expands. A slab allocator is used for kernel heap allocations & object allocations. Since the frame allocator is implemented in the free blocks themselves and the PTE free list is in the page tables themselves, required memory for management is almost nonexistent and allocation of free frames and PTE's are performed in constant time.

[thewrongchristian]

For example, for my process table. I don't know how many processes there willll be before they're created, and so I'd need to grow this table whenever a new process is created. Alternatively, I could make the table way bigger than I'd reasonably need and just limit the processes allowed to the size of it at boot, but that would be a huge waste of memory.

You'll need a general purpose allocator in your kernel anyway, as others have said, so things like process structures should be allocated dynamically, and managed using either linked lists (not the best plan - O(n)), or provide hash maps (O(1)) or binary tree maps (O(log2(n)) to go from process id to the process structure.

But that won't help at the very earliest stages of bootstrap. For bootstrap, I just have a very simple allocator, which is simply a pointer to the next data area to allocate, and initialized to the end of the kernel BSS data. Then, once grub has loaded my kernel, I have a pointer which I know points to no live data, and if I allocate a bootstrap data structure of, say, 32 bytes, I return a copy of this pointer and advance the pointer 32 bytes.

Once bootstrap is complete, the bootstrap allocator is abandoned, and the general purpose heap takes its place. The memory allocated by the bootstrap allocator is lost forever if it's no longer used, but in my instance, I do continue to use it. I use it, for example, for the free physical memory bitmap, which I'll always reference, and for the base structures that maintain the heap, so that isn't wasted either.

Another time this problem comes up is when reading the mmap table from the multiboot info (I'm using the GRUB bootloader, so this is my best way of getting a memory map). I want to copy the memory map to somewhere in kernel space, so that I can use it whenever I want without worrying about overwriting the place where the mmap table originally came from. However, the mmap table has a size specified by a value in the multiboot info. What's the best way here to allocate enough space somewhere in the kernel to store this table?

Using the simple bootstrap allocator above, I don't need to keep a reference to the multiboot info, because I create the physical memory management structures I need using the bootstrap allocator. But you can use the bootstrap allocator to copy the multiboot info as well if you want to keep it around.

My bootstrap allocator in full (just spotted a bug as well, I assume nextalloc is aligned to ALIGNMENT bytes):

Code: Select all

#define ALIGNMENT 16
/* _bootstrap_nextalloc is initialized to the end of bss */
static char * nextalloc = _bootstrap_nextalloc;
void * bootstrap_alloc(size_t size)
{
        void * m = (void*)nextalloc;
        size += (ALIGNMENT-1);
        size &= (~(ALIGNMENT-1));
        nextalloc += size;

        return m;
}

static void bootstrap_finish()
{
        nextalloc += ARCH_PAGE_SIZE;
        nextalloc = (char*)((uint32_t)nextalloc & ~(ARCH_PAGE_SIZE-1));
}

[j4cobgarby]

For example, for my process table. I don't know how many processes there willll be before they're created, and so I'd need to grow this table whenever a new process is created. Alternatively, I could make the table way bigger than I'd reasonably need and just limit the processes allowed to the size of it at boot, but that would be a huge waste of memory.

You'll need a general purpose allocator in your kernel anyway, as others have said, so things like process structures should be allocated dynamically, and managed using either linked lists (not the best plan - O(n)), or provide hash maps (O(1)) or binary tree maps (O(log2(n)) to go from process id to the process structure.

But that won't help at the very earliest stages of bootstrap. For bootstrap, I just have a very simple allocator, which is simply a pointer to the next data area to allocate, and initialized to the end of the kernel BSS data. Then, once grub has loaded my kernel, I have a pointer which I know points to no live data, and if I allocate a bootstrap data structure of, say, 32 bytes, I return a copy of this pointer and advance the pointer 32 bytes.

Once bootstrap is complete, the bootstrap allocator is abandoned, and the general purpose heap takes its place. The memory allocated by the bootstrap allocator is lost forever if it's no longer used, but in my instance, I do continue to use it. I use it, for example, for the free physical memory bitmap, which I'll always reference, and for the base structures that maintain the heap, so that isn't wasted either.

Another time this problem comes up is when reading the mmap table from the multiboot info (I'm using the GRUB bootloader, so this is my best way of getting a memory map). I want to copy the memory map to somewhere in kernel space, so that I can use it whenever I want without worrying about overwriting the place where the mmap table originally came from. However, the mmap table has a size specified by a value in the multiboot info. What's the best way here to allocate enough space somewhere in the kernel to store this table?

Using the simple bootstrap allocator above, I don't need to keep a reference to the multiboot info, because I create the physical memory management structures I need using the bootstrap allocator. But you can use the bootstrap allocator to copy the multiboot info as well if you want to keep it around.

My bootstrap allocator in full (just spotted a bug as well, I assume nextalloc is aligned to ALIGNMENT bytes):

Code: Select all

#define ALIGNMENT 16
/* _bootstrap_nextalloc is initialized to the end of bss */
static char * nextalloc = _bootstrap_nextalloc;
void * bootstrap_alloc(size_t size)
{
        void * m = (void*)nextalloc;
        size += (ALIGNMENT-1);
        size &= (~(ALIGNMENT-1));
        nextalloc += size;

        return m;
}

static void bootstrap_finish()
{
        nextalloc += ARCH_PAGE_SIZE;
        nextalloc = (char*)((uint32_t)nextalloc & ~(ARCH_PAGE_SIZE-1));
}

Hi, thanks for the detailed answer. When you say the pointer to the next data to allocate is initialised at the _end_ of the kernel's BSS, does that mean that in terms of memory addresses it's at the _beginning_ of the BSS? Since the stack grows down from the top, and you're adding the size to nextalloc, rather than subtracting. Also I'm wondering what the bootstrap_finish() function is for.

[nullplan]

Hi, thanks for the detailed answer. When you say the pointer to the next data to allocate is initialised at the _end_ of the kernel's BSS, does that mean that in terms of memory addresses it's at the _beginning_ of the BSS? Since the stack grows down from the top, and you're adding the size to nextalloc, rather than subtracting.

No, it's the end of the BSS section. This is common for kernels that know where they get loaded to, they just begin using addresses behind the kernel image, effectively enlarging the BSS section at runtime.

[thewrongchristian]

Code: Select all

...
static void bootstrap_finish()
{
        nextalloc += ARCH_PAGE_SIZE;
        nextalloc = (char*)((uint32_t)nextalloc & ~(ARCH_PAGE_SIZE-1));
}

Hi, thanks for the detailed answer. When you say the pointer to the next data to allocate is initialised at the _end_ of the kernel's BSS, does that mean that in terms of memory addresses it's at the _beginning_ of the BSS? Since the stack grows down from the top, and you're adding the size to nextalloc, rather than subtracting. Also I'm wondering what the bootstrap_finish() function is for.

My stack doesn't grow down from the top of anything but the single page frame I set aside for my kernel stack. At this bootstrap stage, I'm still on my statically allocated bootstrap stack.

My memory map looks like this:

Code: Select all

+-------+
|       |
|  heap |
|       |
+-------+<--nextalloc ends up here at bootstrap_finish
|  data |
+-------+<--nextalloc starts here for bootstrap_alloc
|       |
|  mods |}<-modules loaded by grub (nextalloc is skipped over grub loaded modules)
|       |
+-------+<--_bootstrap_nextalloc (nextalloc is initialized to here)
| .bss  |
+-------+
| stack |}<-static bootstrap stack
+-------+
| .data |
+-------+
|       |
| .text |
|       |
+-------+<--grub loads kernel here

I use bootstrap_finish() at the point where my heap is created and any further allocations will now use the heap, which at this point, will start at nextalloc (aligned to a page boundary.)

At this point, I could also put in code to ensure further bootstrap allocations do not take place, by example panicing.