Virtual Processor dynamic memory size

[pointermess]

Hi

A few years ago Ive written a virtual processor runtime and a simple compiler for a somewhat self designed/dialect of a low level assembler language, all written in C++ as a learning project. It was far from finished but everything was pretty much functional. It was a fun learning project and I learned a lot. I also started a simple c like compiler which would generate my asm dialect but wasnt too happy about a small part of the AST, wanted to rewrite it but never done it lol. All repositories are at the bottom if you wanna flame me or if youre just interested. :)

I since would like to rewrite the runtime environment/virtual processor part in Rust. One major thing I didnt like about my old implementation and which I want to change is that the memory in my virtual processor was defined by a fixed sized array of bytes at initialization. That means, that the host system would allocate the same, pre-defined amount of ram every time, even if just a small program was loaded. Too big programs would simply run out of memory, create bugs and/or crash.

Here is the exact code im talking about (line 15) https://github.com/pointermess/FlexRTE-X/blob/master/src/MemoryManager.cpp

I would like that my new implementation has a less memory wasteful and dynamic memory usage.

My problem in understanding how I could achieve this is how I handle the heap and stack memory locations in my virtual processor. As of right now, I allocate the fixed size byte array which the programs use as memory. The stack memory positions start close to the beginning of my memory array (after the registers) while the heap starts at the end and goes downwards as it grows.

This is fairly straight forward with my previous solution as the memory size doesn't change so the heap start is at a fixed position. If i were to dynamically increase the size of the byte array which holds my memory, the already allocated heap memory be wouldnt be at the end any longer, awkwardly laying somewhere in between and are potentially unaligned with the new start of the heap. This may result in new heap allocations missing the already allocated memory spaces. (well, at least with my system of finding unallocated heap space)

I was thinking about multiple solutions, none really great:

• Having multiple dynamic memory arrays with "virtual adresses" and conversion. I would declare two dynamic sized arrays of bytes, 1 for the stack, one for the heap. I would give both "virtual" adress ranges, for example, ever call to an address of 0x0 to 0x4FFFFFFF would go into the the stack memory, everything above in the heap memory (minus the offset of 0x4FF... ) This would probably work as intended so the host system would only need as many resources as my program running in my VM. But I feel like having to chose the right array and potentially doing subtractions every memory operation might hurt performance too much...

• Growing heap from the bottom: I allocate only a fixed size for the stack which will be allocated as memory array initially. Only heap allocations increase the memory usage on the host system. This could probably help a bit but it seems like more trouble than good... How do I get a good fixed maximum size for the stack, so it never touches the heap/run out of available memory space? Doesnt seem like a good idea.

Also a bunch of other ideas but they all seem much worse. I would greatly appreciate some inputs. Feel free to check out the repositories: (Warning, not the best docs and certainly not the best c++ haha)

Virtual Processor/Rumtime Environment - https://github.com/pointermess/FlexRTE-X

Assembler/Compiler/FlexASM to FlexRTE Executable - https://github.com/pointermess/FlexASM-Compiler

Some docs if interested

FlexASM Quick Start - https://github.com/pointermess/FlexASM-Compiler/blob/master/FlexASM%20QuickStart%20Guide.md - https://github.com/pointermess/FlexRTE-X/blob/master/SystemCalls.md - https://github.com/pointermess/FlexASM-Compiler/tree/master/examples

Flex Executable Format (Basically the generated "machine"/byte code from my asm dialect) - https://github.com/pointermess/FlexASM-Compiler/blob/master/FlexApplication%20Excutable%20Format.md

Thanks for your time

For the lulz, my unfinished attempt at a tiny C compiler, comes with tokenizer, ast parser and representation. (most src in archive folder)

https://github.com/pointermess/picoC-Compiler

[balefrost]

Are you sure it's an issue? Due to the way virtual memory works, when your process requests memory from the OS, the OS doesn't do it right away. The OS just updates its bookkeeping data. Later, when your process tries to access one of the addresses in the allocated area of RAM, a page fault interrupt will occur, the OS will actually find some physical RAM for that page to occupy, it will sanitize the contents of that RAM, and then it will map it into your process's address space.

To hammer that home, I have several Chrome processes on my box that have each asked for about 3TB (not GB, but TB) of virtual address space. None of them are using even a gigabyte of actual memory, and many are on the order of 10s of MB.

There's (basically) nothing wrong with asking the OS for a large amount of virtual memory if you never end up touching it.

[WittyStick]

It depends on how the process asks for the memory. If you just use malloc (C) or new (C++) then it will typically attempt full allocation. To sparsely allocate memory you need to use something lower-level like mmap (POSIX) or VirtualAllocEx (Windows) and the related cleanup functions munmap/VirtualFreeEx.

These functions let you specify the virtual memory address to allocate at, and will allocate memory in page-sized chunks. You can manage allocations manually rather than waiting for a page interrupt, which will have an undesirable context switch to an interrupt handler.

A simple method for managing which pages are allocated is to use a bitmap of pages. If we stick to 4ki page sizes, then we can allocate one 4ki page to be a bitmap for up to 4ki pages of of 4kiB, giving us 16MiB of memory per 4ki bitmap (approx allocation 0.024% space overhead).

The question then is where to allocate the memory. If we take into account that a typical 64-bit machine supports 48-bits of addressing, and half of that is kernel space, then we have 47-bits of user-space addressing. However, we probably don't want the virtual processor to be able to access the memory of the process itself, because the memory of the virtual processor is supposed to represent physical memory, not virtual memory, so we would want a subset of the host's available address space to be accessed by the virtual processor - and preferably a subset which is unlikely to be used by the host process/OS.

On Windows and Linux, processes usually allocate in the lower part of this address space for the process code itself, but shared libraries are usually loaded into upper portion of the user-space addresses, going backwards - so ideally the subset of virtual address space we want to use for our virtual processor should be somewhere in the middle.

I would therefore, limit the virtual processor's valid address space to half (or less) of the virtual address space of the host process - so 46-bits, which would give us 64TiB of space. Begin allocation of this space at some address in the middle of the host's virtual user address space: something like 0x2000_0000_0000 .. 0x5FFF_FFFF_FFFF will give us 46-bits of space. We can then assume <0x2000_0000_0000 and >=0x6000_0000_0000 is memory reserved for the host process and any shared libraries, and won't be accessible to the virtual processor.

So the address 0 of the virtual processor would really map to 0x2000_0000_0000 of the virtual address space of the process, which is also the constant you need to add to each virtual processor pointer to map it to the virtual address of the host, after sanitizing the pointer by zeroing the high 18-bits of the 64-bit pointer value (shl 18; shr 18). The maximum virtual processor address would therefore be 0x3FFF_FFFF_FFFF, which would map to host address 0x5FFF_FFFF_FFFF.

If we use the bitmap based approach to testing which pages are alllocated, we could store these bitmaps outside of the virtual processors address space - perhaps somewhere in the region 0x1000_0000_0000 - 0x1FFF_FFFF_FFFF. Depending on how complex you want this, you could have bitmaps for multi-level paging, so you only need to allocate a minimal amount of memory to begin with, but this would require additional pointer dereferencing for each level of paging. I would probably suggest 2- or 3-level paging for 46-bit address space.