OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 3:24 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Paging Praise
PostPosted: Fri Jul 11, 2014 1:01 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 923
Location: Finland
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:
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.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Fri Jul 11, 2014 1:28 am 
Offline
Member
Member
User avatar

Joined: Tue Oct 17, 2006 11:33 pm
Posts: 3882
Location: Eindhoven
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.


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Fri Jul 11, 2014 3:14 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 923
Location: Finland
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:
a = BLOCK OF CODE (32-bytes)

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

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

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Sat Jul 12, 2014 3:37 am 
Candy wrote:
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.


Top
  
 
 Post subject: Re: Paging Praise
PostPosted: Sat Jul 12, 2014 8:39 am 
Offline
Member
Member
User avatar

Joined: Wed Dec 01, 2010 3:41 am
Posts: 1761
Location: Hong Kong
Antti wrote:
Code:
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.


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Sat Jul 12, 2014 10:39 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 923
Location: Finland
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.

bluemoon wrote:
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.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Sat Jul 12, 2014 11:12 am 
Offline
Member
Member

Joined: Sat Nov 21, 2009 5:11 pm
Posts: 852
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.


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Sat Jul 12, 2014 2:00 pm 
Offline
Member
Member

Joined: Sat Mar 15, 2014 3:49 pm
Posts: 96
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/


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Sat Jul 12, 2014 4:11 pm 
Offline
Member
Member
User avatar

Joined: Fri Jun 13, 2008 3:21 pm
Posts: 1700
Location: Cambridge, United Kingdom
embryo wrote:
Candy wrote:
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!


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Mon Jul 14, 2014 1:36 am 
Owen wrote:
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.


Top
  
 
 Post subject: Re: Paging Praise
PostPosted: Mon Jul 14, 2014 3:02 am 
Offline
Member
Member

Joined: Sat Mar 15, 2014 3:49 pm
Posts: 96
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.


Top
 Profile  
 
 Post subject: Re: Paging Praise
PostPosted: Tue Jul 15, 2014 4:04 am 
willedwards wrote:
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.
willedwards wrote:
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.


Top
  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Google [Bot] and 23 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group