Paging Praise

[Antti]

This post is a kind of special because I am not going to criticize anything. The current flow of new topics is not too excessive so I thought one not-so-important topic may fit in. As usual, I have been in a tight loop of rewriting from scratch and I have not made any significant progress on the kernel itself. Nevertheless, I have again started to think about fancy things like memory management. I have not played with paging for a long time and now it feels that the whole concept is very fresh and exciting.

Paging is excellent. I am not talking about one of the memory- management schemes by which a computer can store and retrieve data from secondary storage for use in main memory, as defined in Wikipedia. I am not interested in using that feature at the moment. What I am talking about are virtual memory tricks. The fact that we can have a huge continuous virtual memory area, without consuming physical memory excessively, is something really powerful and elegant. The key concepts: a page fault handler, read-only pages, and a physical page full of zeros. These things are very widely known but I keep wondering whether the power of them is harnessed well enough. With 32-bit addressing, there are noticeable limits. With 64-bit addressing, the limits are not so severe.

There are numerous uses for this but best things are usually quite simple: arrays.

Code: Select all

uint32_t hugeStorageArray[0x100000000];

uint32_t GetValue(uint32_t key) {
    return hugeStorageArray[key];   /* Every key is valid */
}

I am impressed. There are so many elegant uses that I am not even realizing it yet. There are old discussions about this subject but I thought it would be nice if new OS developers think about this.

[Candy]

I believe the JVM typically does this - it allocates 2TB of virtual space and then starts doing something. That functionally allocates nothing, as you noticed, but does give it the space to do Java allocations in a linear-ish address space without fear of fragmentation.

[Antti]

One virtual memory trick could be to do extremely aggressive loop unrolling. I am not sure whether it is optimal or not. An example:

Code: Select all

a = BLOCK OF CODE (32-bytes)

Page 0:
    a
    a
    ...
    ...
    a
    <end of page>

Pages 1-?:
    a
    a
    ...
    ...
    a
    <end of page>

[embryo]

I believe the JVM typically does this - it allocates 2TB of virtual space and then starts doing something.

Actually the JVM allocates just some minimal amount of memory, which is now defaults to something like 16Mb. When a Java application requests more memory the JVM extends the allocated amount. It means there is no flat memory within the JVM bigger than 16Mb unless an application requests one big chunk for a very long array. And there is no point in having flat memory from the Java application point of view, because application works with objects without any knowledge about addresses.

[bluemoon]

Code: Select all

uint32_t hugeStorageArray[0x100000000];

uint32_t GetValue(uint32_t key) {
    return hugeStorageArray[key];   /* Every key is valid */
}

I am impressed. There are so many elegant uses that I am not even realizing it yet. There are old discussions about this subject but I thought it would be nice if new OS developers think about this.

This should be optimised in algorithm instead of abuse the paging system, since there is no contract between you and the OS.

Also, a seemingly harmless memset(hugeStorageArray, 0, sizeof(hugeStorageArray)); bring the system down.
So you end up making a lot of non-trivial DON'Ts when using the language.

[Antti]

This mechanism is the main point but the usage policy may cause problems. There are severe worst case scenarios, e.g. setting only one entry per page.

Also, a seemingly harmless memset(hugeStorageArray, 0, sizeof(hugeStorageArray)); bring the system down.

True. This should be somehow be implemented as a syscall that does this efficiently.

[Gigasoft]

For this type of allocation I suggest associating a maximum commit size with each allocation. If the application exceeds it, the OS should raise an exception. That would eliminate surprises.

[willedwards]

This is an area where the new Mill CPU architecture is quite novel.

The Mill is Single Address Space (with special secret sauce for fork()).

Memory is implicitly zero, so reading from unbacked memory doesn't back it, but rather shortcuts and gets zeros.

Memsetting a large range to zero can be cheaply achieved by simply unbacking any wholely covered pages.

The actual allocation of pages is done by hardware from a free list when dirty lines are evicted from bottom cache, so is also faster than conventional architectures.

In all we see around 20% less memory traffic from these features iirc.

Implicit zero is also used to zero the stack automatically.

There are more details in our memory talk: http://millcomputing.com/forum/the-mill/architecture/

[Owen]

I believe the JVM typically does this - it allocates 2TB of virtual space and then starts doing something.

Actually the JVM allocates just some minimal amount of memory, which is now defaults to something like 16Mb. When a Java application requests more memory the JVM extends the allocated amount. It means there is no flat memory within the JVM bigger than 16Mb unless an application requests one big chunk for a very long array. And there is no point in having flat memory from the Java application point of view, because application works with objects without any knowledge about addresses.

Sun/Oracle HotSpot most definitely allocates one big chunk of address space. Indeed, this is essential to the way HotSpot's GC works (being as its' a moving garbage collector).

It only commits a small amount of address space at startup - typically 16MB or so - and then incrementally increases the size of its' allocation as this space fills up.

Yes, the Java application doesn't care - but the implementation certainly can!

[embryo]

Sun/Oracle HotSpot most definitely allocates one big chunk of address space.

If you disagree then it is possible to run Java application and take a look at working and private sets.

[willedwards]

Embryo you are misunderstanding how mainstream operating systems manage memory.

Virtual ranges are reserved, and physical pages are committed. Looking at "working" and "private sets" is telling you how much memory is committed, not what address space is reserved.

In a forum for OS devs, its important to understand the distinction.

[embryo]

Embryo you are misunderstanding how mainstream operating systems manage memory.

Virtual ranges are reserved, and physical pages are committed. Looking at "working" and "private sets" is telling you how much memory is committed, not what address space is reserved.

Yes, virtual range really shows JVM's maximum allowed memory allocation. I use Windows and do not know it's memory allocator algorithm, but at least it is possible to implement flat memory access for the JVM.

In a forum for OS devs, its important to understand the distinction.

If it is a question about "flat or not flat" then yes, I haven't paid attention to all those gigabytes of virtual memory ranges, when even Notepad or Calculator reserve about 30 megabytes.

But if we speak about actual memory usage and Java application requirements, then my claim is valid.

However, the distinction is actually here and should be considered. I haven't paid attention to it.