Where to go from here?

[Kaius]

Hello all.

It's been a while since I've done any development on my OS, but recently I've been thinking of picking it back up again. At present, I have a basic kernel set up, with a bare-bones GDT, an IDT, and a couple of drivers (keyboard, VGA output) and a hard-coded "terminal".

I'm wanting to build up to the point where I can have executable files (probably in userspace), and work from there, but I'm not really sure where to go from this point. Does anybody have any advice on what to implement next?

Current git commit: https://github.com/TylerSelden/nox/tree ... f491bf00d3

(Suggestions on current code are always welcome and appreciated, if you have any)

[Octocontrabass]

The wiki has some good advice.

If you're satisfied with your current debug output capabilities, the next thing you need is memory management.

[Kaius]

The wiki has some good advice.

If you're satisfied with your current debug output capabilities, the next thing you need is memory management.

Thanks for the reply. I'm looking into this now, and I'm a bit confused when it comes to detecting a memory map through GRUB. My understanding is that it will provide me with sections of memory that are marked as either reserved or usable, but also that the memory that the kernel was loaded into is still marked as usable. How can I prevent my kernel from allocating that section of memory to another program? In other words, how can the kernel know where it's loaded, so it can avoid overwriting its own memory?

[nullplan]

My understanding is that it will provide me with sections of memory that are marked as either reserved or usable, but also that the memory that the kernel was loaded into is still marked as usable. How can I prevent my kernel from allocating that section of memory to another program?

Normally by marking that memory as used in the allocator. Your physical memory allocator has to know what memory is available and what memory isn't, and because of the arcane semantics of the old E820 list, you also have to deal with overlap between the lists. And normally, your physical allocator just marks memory as used when it gets allocated by, for example, adding it to the "reserved" list. It then gets freed by removing it from that list. You just need an interface to mark the kernel memory as used, that is all. And you sort of need to know where you were loaded to.

[Octocontrabass]

In other words, how can the kernel know where it's loaded, so it can avoid overwriting its own memory?

One method is to define some symbols in your linker script at the start and end of your kernel, so you can use the address of those symbols to figure out where your kernel was loaded.

[Kaius]

One method is to define some symbols in your linker script at the start and end of your kernel, so you can use the address of those symbols to figure out where your kernel was loaded.

Thanks for the tip, that's what I went ahead and did. I've started working with the multiboot-provided memory map, but I don't think the values I'm getting are correct. I'm using the provided "multiboot.h" file (the one included with the multiboot spec), and my code is below.

Code: Select all

#include <stdint.h>
#include <lib/mem.h>
#include <drivers/vga.h>
#include <multiboot.h>
#include <lib/panic.h>

void mem_init(multiboot_info_t *mbi) {
  if (!(mbi->flags & 0x41)) {
    panic("Essential memory information is not available.");
  }

  uint32_t mmap_size = mbi->mmap_length;
  memory_map_t *mmap = (memory_map_t *)mbi->mmap_addr;

  printf("\nMemory map:\n mem_lower: 0x%x\n mem_upper: 0x%x\n", mbi->mem_lower, mbi->mem_upper);

  // Loop through the memory map entries
  while (mmap_size > 0) {
    printf("Addr: 0x%x%x; Length: 0x%x%x; Type: %x",
               mmap->base_addr_high, mmap->base_addr_low,
               mmap->length_high, mmap->length_low,
               mmap->type);

    mmap_size -= mmap->size + sizeof(uint32_t);
    mmap = (memory_map_t *)((uint32_t)mmap + mmap->size + sizeof(uint32_t));
  }
}

I'm running QEMU with the "-m 3M" option, which should only give me 0x300000 memory. However, the memory map produced by the above code leaves me with:

Code: Select all

Memory map:
  mem_lower: 0x27f
  mem_upper: 0x780

Addr: 0x00; Length: 0x09fc00; Type: 1
Addr: 0x09fc00; Length: 0x0400; Type: 2
Addr: 0x0f0000; Length: 0x010000; Type: 2
Addr: 0x0100000; Length: 0x01e0000; Type: 1
Addr: 0x02e0000; Length: 0x020000; Type: 2
Addr: 0x0fffc0000; Length: 0x040000; Type: 2

Clearly, I didn't give QEMU enough memory for that last entry... right? Does this look correct, or is something wrong here? I'll also have the chance to test on real hardware soon, so I'll try that when I can.

[Octocontrabass]

Does this look correct, or is something wrong here?

That looks correct. The memory map is not limited to just RAM, and RAM can exist at any physical address.

[MichaelPetch]

As an addendum the 256KiB of Type2 memory from 0x0fffc0000 to 0xffffffff is system ROM which is mapped into the last part of the 4GiB physical memory space.

[Kaius]

Thanks for the input.

I'm beginning to plan out my memory allocator, but I'm struggling with converting the memory map to something useful. Since I can't really guarantee that the entries are in order, I'm having trouble writing something to collapse the messy, overlapping mmap from GRUB into a more usable flat model of available space. Is there an existing algorithm somewhere that you'd recommend? I've read through the wiki and the multiboot spec to see if there's anything that could help, but so far I haven't found anything.

[sounds]

Here's what worked for me, please consider this as a starting point and develop your own approach.

First, the number of memory map entries is not going to be very large. What I mean is, I didn't worry about the O(n^2) scaling here.

My approach starts with this data structure:

Code: Select all

memory block = {
  start physical addr: 64 bit unsigned
  end physical addr: 64 bit unsigned ; technically this is 1 byte past the end
}

There are two lists. The first is a sorted list of available memory:

Code: Select all

available list: list<memory block>

Sorted means I wrote a function to add a memory block to the list, and it will search the list and add the block so that start physical addr is always sorted.

But once you really get into it, you will need to add code to merge memory blocks if they touch. Here's a simple example:

Code: Select all

Grub-provided multiboot memory map:

0x100000 - 0x200000: available memory
0x300000 - 0x800000: available memory
0x200000 - 0x300000: available mrmory

After you add 0x100000, the available list looks like this:

Code: Select all

available list: [
memory block { 0x100000 - 0x200000 }
]

After you add 0x300000, the available list looks like this:

Code: Select all

available list: [
memory block { 0x100000 - 0x200000 }
memory block { 0x300000 - 0x800000 }
]

But to add 0x200000, it merges with 0x100000 and it merges with 0x300000 so the available list looks like this:

Code: Select all

available list: [
memory block { 0x100000 - 0x800000 }
]

Instead of a hash table, I do a linear search across the available list, so adding all the blocks in the multiboot memory map ends up taking O(n^2) time. That would be very slow if there were 100,000 entries.

There are two lists, and the second is a sorted list of memory holes. Here's why that's important: some devices will need to memory-map their IO (mmio) and without keeping track of it, you could end up trying to access the device mmio and instead you're writing into ACPI memory, or System Management Mode memory (which might triple-fault and reset the CPU).

Code: Select all

The two lists:
available list: list<memory block>
hole list: list<memory block>

Good luck!

[nullplan]

I have a similar system as sounds. Only I preallocate these lists statically so they can have 128 nodes without requiring dynamic allocation. This is usually enough to initialize these lists enough to reserve all memory that needs reserving. Once that is done, the physical allocator can allocate virtual memory without fear of trampling on something important.

[Kaius]

Thanks for the help everybody. Sorry for bombarding the forum with questions, but I've got one more: is there anything wrong with using uint64_t when I'm only in 32-bit protected mode? It seems like it would make things easier in terms of working with 64-bit addresses, but I don't know if it comes with any major downsides. I'm asking because I noticed that multiboot.h uses two long values for addresses, high and low. Are there significant downsides to simply merging these into one uint64_t?

[Octocontrabass]

Where did you find a copy of the Multiboot header that doesn't already use uint64_t for 64-bit integers?

[Kaius]

Where did you find a copy of the Multiboot header that doesn't already use uint64_t for 64-bit integers?

Thought I'd gotten it from multiboot spec, but I ended up with a weird copy somehow. Must've gotten it from Github by accident, but I guess that answers my question

[nullplan]

Thanks for the help everybody. Sorry for bombarding the forum with questions, but I've got one more: is there anything wrong with using uint64_t when I'm only in 32-bit protected mode?

Physical address space can exceed 4GB, and with PAE you can address all of that space even in 32-bit mode. Even if you don't intend to use PAE, it seems to me like you are attempting a premature optimization that will end up hobbling you in the long run. Just use the 64-bit integers; it's what the memory map comes in, and if you can't use anything above 4GB right now you still might at some point.