Few questions before I start writing my memory allocator.

[austanss]

I've come up with a rather good design, IMO, for a memory allocator.

Let me just quote my source file here:

Code: Select all

// Memory Index
//
// The memory index takes the form of a bitmap.
// For every 64 bits, there is one bit in the
// bitmap signaling if it is allocated or free.
// This works out to about ~1.5% memory usage,
// and this indexes all of the addressable RAM.
// Therefore, the minimum amount of RAM that can
// be allocated is 64 bits (8 bytes), which is
// the perfect amount for an x64-based kernel.

I say "perfect amount" because x86-64 CPUs read 8 bytes at a time, so this prevents any crosstalk between memory blocks, in the case of a packed struct, for example.

Anyway, there is a few things I need to know before I get started.

A. How do I obtain the amount of RAM that a computer has?
B. How do I dynamically allocate the space for the memory index?
I can't go with highest possible value, because that would be equal to 2TB, which would require an allocation of 32GB, which won't work out for me as I only have 16GB of RAM in my computer to begin with, and it also won't work
for majority of computers. I also can't use the memory allocator because it needs the table first...
C. Is 8 bytes minimum a reasonable amount?

Also note this must work under UEFI.

[Octocontrabass]

I say "perfect amount" because x86-64 CPUs read 8 bytes at a time, so this prevents any crosstalk between memory blocks, in the case of a packed struct, for example.

Most of them read 64 bytes at a time...

How do I obtain the amount of RAM that a computer has?

The memory map will tell you all about it.

How do I dynamically allocate the space for the memory index?

Good question! It's tough to have dynamic memory allocation that depends on dynamic memory allocation. One strategy is to carve out some space from one or more of the free memory ranges in your memory map when you initialize the allocator and use that space to keep track of the rest of it.

Is 8 bytes minimum a reasonable amount?

For your kernel heap? Yes. For tracking all free memory? No. Typically you would have a physical memory manager to keep track of free memory in page-sized increments, and use it to dynamically map free memory at a convenient virtual address for your kernel heap as it grows. (Typically you don't identity-map your kernel or any of the memory it uses.)

Also note this must work under UEFI.

The only thing that depends on firmware is the memory map format.

[austanss]

I say "perfect amount" because x86-64 CPUs read 8 bytes at a time, so this prevents any crosstalk between memory blocks, in the case of a packed struct, for example.

Most of them read 64 bytes at a time...

Oh really? When did the new 512-bit CPUs come out? I might want to get one...

[austanss]

How do I dynamically allocate the space for the memory index?

Good question! It's tough to have dynamic memory allocation that depends on dynamic memory allocation. One strategy is to carve out some space from one or more of the free memory ranges in your memory map when you initialize the allocator and use that space to keep track of the rest of it.

I don't fully understand this response. I get the free memory ranges part, but still a little confused on the dynamic sizing...

[Octocontrabass]

Oh really? When did the new 512-bit CPUs come out? I might want to get one...

Cache lines on most x64 CPUs are 64 bytes long, and the CPU typically reads or writes entire cache lines at once. You will need to worry about cache line size when you're dealing with data that's shared across multiple CPUs. (But if you're asking about AVX-512, that's been available since 2017.)

I get the free memory ranges part, but still a little confused on the dynamic sizing...

You can calculate how big your index needs to be based on how much memory it needs to track.

[austanss]

Oh really? When did the new 512-bit CPUs come out? I might want to get one...

Cache lines on most x64 CPUs are 64 bytes long, and the CPU typically reads or writes entire cache lines at once. You will need to worry about cache line size when you're dealing with data that's shared across multiple CPUs. (But if you're asking about AVX-512, that's been available since 2017.)

I get the free memory ranges part, but still a little confused on the dynamic sizing...

You can calculate how big your index needs to be based on how much memory it needs to track.

Wow. I didn't know 512 bit memory reading was actually a thing...
Also, yes I understand how to calculate the index, the size is TOTAL_RAM / 64.
But I don't know how I would set up a frame in memory or anything like that to initialize the memory allocator.

[austanss]

Oh really? When did the new 512-bit CPUs come out? I might want to get one...

Cache lines on most x64 CPUs are 64 bytes long, and the CPU typically reads or writes entire cache lines at once. You will need to worry about cache line size when you're dealing with data that's shared across multiple CPUs. (But if you're asking about AVX-512, that's been available since 2017.)

I get the free memory ranges part, but still a little confused on the dynamic sizing...

You can calculate how big your index needs to be based on how much memory it needs to track.

Wow. I didn't know 512 bit memory reading was actually a thing...
Also, yes I understand how to calculate the index, the size is TOTAL_RAM / 64.
But I don't know how I would set up a frame in memory or anything like that to initialize the memory allocator.

EDIT: I'm stupid, ignore me.

[austanss]

OK. I've parsed my memory map and found a few candidates for the memory index.
Here they are:

Code: Select all

0x0000000000100000: EfiConventionalMemory (1792)
0x0000000001500000: EfiConventionalMemory (731952)
0x00000000BBF56000: EfiConventionalMemory (10965)
0x0000000100000000: EfiConventionalMemory (262144)

The first one isn't really a candidate, because that is where the kernel is stored...
The second one is where I plan to use for general purpose...
Which leaves me to the third one and fourth one.
The fourth one is the last chunk in the map, so nothing comes after it other than the end of RAM.
The third one is a possible candidate, but most likely only for systems with <= 8GB of RAM, as the memory index can outgrow that size.
This leaves me to have the 4th chunk as the possible candidate.
However, I still need to test out the map on different amounts of RAM and see how it bodes, so I will get back to you on that.

Free to take advice.

[austanss]

OK, so I tested out different ram sizes.

Between 4-12GB (my tested range), the first, second, and third chunks of memory stay mostly static in size.

However, as the RAM sizes go up, the fourth chunk of memory grows (as is expected as the only boundary to it is the end of RAM).

This chunk of memory surely wins this election.

[nexos]

A few comments...
A physical memory allocator normally allocates 4K blocks of RAM, as pages are 4K in size. You can do 8 bytes, but allocating 4K of RAM (which is generally what you do) would be slow. If you want to do both, look into a buddy allocator system. Also, a bitmap works great, but I've abandoned bitmaps in favor free lists and free stacks. They are much faster all the way around.

[Octocontrabass]

OK. I've parsed my memory map and found a few candidates for the memory index.

There's no way the memory map will look like that on every computer. You have to come up with some way to find usable memory for your physical memory manager that doesn't depend on a particular memory map. Fortunately, paging makes it easy: with paging, you don't need contiguous physical memory, so you can just grab free pages in the order you find them.

[austanss]

yeah i know that. i'm not statically defining which chunk of memory to use.