How to implement a memory manager?

[onlyonemac]

So the theoretical design for my OS is coming together (no code written yet). I'm working on the layout of the various data tables used, and I've hit a snag which I tried to skirt around last time I did an OS design and failed that time also. It's the one thing that I STILL can't quite work out...

So basically one part of my kernel is responsible for allocating blocks of memory. I've got a data table which stores, for each block, a base address, size, and reference count (the last of which I'm not sure if it's standard practice but it is required for my design).

Now the problem is with actually allocating the memory blocks. How do I keep track of where to allocate the next block? How do I deal with the resulting "hole" when a block lower in memory is freed while there are still blocks allocated higher in memory?

In case it matters, processes are given an index into the allocated memory block table rather than a pointer itself. This is a characteristic of my design and is necessary and does not appear to be causing any further complications (other than when it comes to accessing the memory, but I have a mechanism for dealing with that).

[onlyonemac]

Actually I'm thinking of changing the design slightly such that processes (and the kernel) work with traditional memory pointers rather than table indexes, however the same basic issue remains with keeping track of memory blocks.

[Octocontrabass]

Have you read this yet?

It sounds like you've got the virtual memory manager pretty well figured out, and you just need a physical memory manager to keep track of free memory. I'd guess the easiest thing to implement is a bitmap, but allocating can get pretty slow since you have to search the bitmap every time. (Of course, you can always implement the bitmap first and then figure out some other, better method once you have it working.)

Just to check, you are using paging, right?

[onlyonemac]

Just to check, you are using paging, right?

No I am not using paging. I read a few articles about paging and freaked out because I didn't understand the complex table layout used. I was using segmentation for my previous design, and I started freaking out over the messy complicated tables. So for this design I decided to do just a flat memory model.

Also I have decided to switch to using pointers (as is standard) to address memory blocks rather than table indecies. The only issue that I'm having with this (apart from the aforementioned issues) is that freeing a memory block is going to require a (potentially lengthly) search through the allocated block table. Is there a better way to do this, possibly with the use of an additional table?

[onlyonemac]

It sounds like you've got the virtual memory manager pretty well figured out, and you just need a physical memory manager to keep track of free memory.

Is that basically like this:
-virtual memory manager says "these are all the currently allocated blocks of memory and where to find them and how big they are"
-physical memory manager says "these are all the bytes of memory that are currently in use"

So when I want to allocate a block of memory, I go to the virtual memory manager and say "give me a block of memory x bytes in size" and the virtual memory manager goes to the physical memory manager and says "find me the next block of memory that has at least x bytes free" and the physical memory manager returns a pointer which the virtual memory manager stores and returns to the caller?

How do I deal with framentation though? Also won't the physical memory manager's bitmap be large, like 1/8th of the amount of available memory? (1 bit stored for each byte of memory.) Should I use a larger allocation unit size and not allocate in individual bytes, like 1 bit in the bitmap for every 4 bytes of memory? (4 bytes not likely to cause much wastage as most values are likely to be 32-bit anyway.) That would make the bitmap only 1/32th of the available memory?

[onlyonemac]

Having read a little more on the topic, I will see if I can figure out the paging thing. It seems that it will also resolve the code relocation issue that I had just been ignoring until now.

[tkausl]

-virtual memory manager says "these are all the currently allocated blocks of memory and where to find them and how big they are"

It says "these are all the currently usable pages (which are mapped in) and where they are located physically (but thats not as impossible, it shouldn't make any difference to the "outside" where they are mapped to).

-physical memory manager says "these are all the bytes of memory that are currently in use"

There are no bytes in virtual memory management, only full pages (4K, or 4MB with big pages) so the physical memory manager keeps track of all physical pages, if they're used or free to use

So when I want to allocate a block of memory, I go to the virtual memory manager and say "give me a block of memory x bytes in size" and the virtual memory manager goes to the physical memory manager and says "find me the next block of memory that has at least x bytes free" and the physical memory manager returns a pointer which the virtual memory manager stores and returns to the caller?

No, what you're describing is heap-memory. You're allocating some bytes on your heap-space and if your heap run out, the heap-manager will again go to the virtual memory manager and allocate one or more pages to get mapped in. the physical and virtual memory manager work only with whole pages.

How do I deal with framentation though? Also won't the physical memory manager's bitmap be large, like 1/8th of the amount of available memory? (1 bit stored for each byte of memory.) Should I use a larger allocation unit size and not allocate in individual bytes, like 1 bit in the bitmap for every 4 bytes of memory? (4 bytes not likely to cause much wastage as most values are likely to be 32-bit anyway.) That would make the bitmap only 1/32th of the available memory?

There is no fragmentation in the virtual- and physical memory manager. Well... There probably is a lot of fragmentation physically, but this does not matter. Not at all. Since you can map your virtual pages to any physical page, so you can use a virtual contiguous address space even if your mapping to physical space is not contiguous.

And no, the bitmap is not 1/8th of the amount of memory, since it only works with whole pages, you only need one bit per page, so one bit for 4096 bytes. This means you need exactly 131072 bytes for your bitmap to handle 4GB of ram.

[onlyonemac]

What is this page/mapping/heap muddle? Don't I just say "give me a pointer to a block of memory" and I get teh pointer?

[Octocontrabass]

No.

The "give me a pointer to a block of memory" is part of the heap, which should be handled separately by each program. C programs will use malloc(), C++ programs will use new, and Java programs will rely on the virtual machine automatically allocating and freeing blocks of memory. All of those are part of the userspace program, not something your kernel should handle. (Your kernel might need a heap, but the kernel heap is only for use by the kernel.)

When the heap manager in one of those programs decides it needs more free RAM, it asks the virtual memory manager to map another page of RAM at a specific address. The VMM asks the physical memory manager to find a free page of RAM and mark it as allocated, then updates the page table so that the program's virtual address maps to that physical address. When the heap manager in one of those programs decides it's done with a page of RAM, it asks the VMM to remove the mapping, and the VMM tells the PMM to mark that page as free.

[iansjack]

Just to check, you are using paging, right?

No I am not using paging. I read a few articles about paging and freaked out because I didn't understand the complex table layout used. I was using segmentation for my previous design, and I started freaking out over the messy complicated tables. So for this design I decided to do just a flat memory model.

Also I have decided to switch to using pointers (as is standard) to address memory blocks rather than table indecies. The only issue that I'm having with this (apart from the aforementioned issues) is that freeing a memory block is going to require a (potentially lengthly) search through the allocated block table. Is there a better way to do this, possibly with the use of an additional table?

Use paging.

There is a learning curve, but it then makes life so much easier, it is much more versatile, and it allows processes to protect their memory from other processes. And if you want to use 64-bit mode (Why wouldn't you? If you are writing a new OS why throw away three-quarters of the processor?) you have to use paging. So bite the bullet and do the sensible thing.

[onlyonemac]

The "give me a pointer to a block of memory" is part of the heap, which should be handled separately by each program. C programs will use malloc(), C++ programs will use new, and Java programs will rely on the virtual machine automatically allocating and freeing blocks of memory. All of those are part of the userspace program, not something your kernel should handle. (Your kernel might need a heap, but the kernel heap is only for use by the kernel.)

I am not implementing a heap. I don't see why processes can't request memory from the kernel each time they need it. This reduces memory consumption and increases efficiency. Furthermore, the somewhat unusual object-orientated design of my OS involves as a major characteristic the direct allocation of specific blocks of memory ("give me a pointer" style) both by the kernel and user processes.

Use paging.

There is a learning curve, but it then makes life so much easier, it is much more versatile, and it allows processes to protect their memory from other processes. And if you want to use 64-bit mode (Why wouldn't you? If you are writing a new OS why throw away three-quarters of the processor?) you have to use paging. So bite the bullet and do the sensible thing.

I'm busy learning about paging now. Will consider it and probably use it if I can figure it out. It seems that it will also resolve the issue with code relocation (loading excutable code at arbitrary addresses). I still need to figure out the details though, particularly with regards to how it works in conjunction with segmentation (not that I'm specifically using segmentation, but I mean simple things like how to set the segment registers, and also other issues like how to change which virtual memory model is used when switching between tasks, etc.). I'm trying to find some good tutorials, and if that fails I will make a separate thread for it.

Also I am not using 64-bit mode at least intially, as I want to be able to test/use the OS on my old 32-bit CPU. And as the project is mostly experimental in nature, it is not at this stage necessary to worry about getting the maximum performance from the CPU, and a 32-bit OS will still perform decently on a modern CPU (to be honest, apart from addressing larger amounts of RAM - not an issue as my laptop has only 4GB of RAM - I don't observe any notable difference between a 32-bit and a 64-bit OS in everyday use; there's supposed to be a slight performance increase with a 64-bit OS).

[Octocontrabass]

I am not implementing a heap. I don't see why processes can't request memory from the kernel each time they need it. This reduces memory consumption and increases efficiency.

I can only think of two interpretations for these statements, and neither improve performance or efficiency.

1. You aren't implementing a heap, and every allocation gets at least one page. A program that allocates lots of 64-byte objects assigns a whole 4kB page to each one, and you quickly run out of memory.

2. You're implementing a heap in kernel space instead of user space. The kernel is now responsible for all dynamic memory management, which means a significant performance hit due to all of the unnecessary context switches. All of the extra bookkeeping data in the kernel causes resource exhaustion with only a few programs running.

If neither of these are what you mean, please explain in more detail so I can understand.

Furthermore, the somewhat unusual object-orientated design of my OS involves as a major characteristic the direct allocation of specific blocks of memory ("give me a pointer" style) both by the kernel and user processes.

That sounds like a heap to me. Again, please explain in more detail so I can understand.

[onlyonemac]

There isn't really a "more detail". I guess you're going to complain about this, but all that I'm doing is exactly what you said. So yes, it might be "like a heap" but the memory blocks are not allocated by a language run-time out of one big memory block. They are allocated as needed by the kernel. So I guess it's like a heap running directly in the kernel. The explanation for why this is needed is because in my design, memory is allocated to store an object. Objects are allocated independently of a particular program. Objects may persist beyond the termination of their creating program. Objects are not owned by any one particular program. E.g. in my design a device driver is an object. A code library is an object. Everything is an object. When one considers that userspace memory blocks are allocated as "generic data objects", it really doesn't make sense to have a heap separate from the kernel's memory allocater.

[Octocontrabass]

It sounds like what you want is an object manager that works on top of a VMM that works on top of a PMM. The object manager is in charge of deciding how objects should be allocated, the VMM maps pages for those objects, and the PMM provides pages for the VMM. Now that I understand your goals a bit better, I don't have any complaints.

Are tasks able to protect their objects from other tasks? If so, that pretty much forces you to allocate a page per object, since you can't have address space protection with more granularity than individual pages.

[onlyonemac]

Are tasks able to protect their objects from other tasks? If so, that pretty much forces you to allocate a page per object, since you can't have address space protection with more granularity than individual pages.

Tasks are currently not able to protect their objects or take ownership in any way. The most that they can do (and this is recommended in most cases) is to create their objects as child objects of their own task object (the object containing the code being executed). While it may seem advisable to have some form of object protection, that is an implementation detail that is beyond the current scope of the project and which is relatively easy to add later once I have got the basics (like the memory managers, basic object manager, devices drivers, etc.) set up. Nevertheless, the system currently (inefficiently) will allocate one page per object attribute (so not just per object, but per each attribute which is a generic name that I am using for any parameters/properties/data/executable code that makes up the object). However it would again be relatively easy to change this at a later date, as the management of objects in memory is the complete responsibility of the object manager and is abstracted from everything else, especially running tasks. All that would really be needed is for the object manager to determine if there is space in an existing page for a new attribute and to allocate more pages if needed, rather than to default to allocating a new page for every attribute. But heh, I'm too lazy right now to be so clever .

Also I've been doing some research on paging and I think that most of my questions are answered with regards to paging (and how to deal with memory fragmentation) and I will try implementing a simple memory manager tomorrow before I start work on the rest of the code (as the memory manager is really at the core of the kernel).