OSDev.org

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?

#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));
}

thewrongchristian wrote:

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 wrote: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.

j4cobgarby wrote:

thewrongchristian wrote:

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.

+-------+
|       |
|  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