How the Mill CPU does fork() in a single address space

by fla • 11 years ago

74 18 11 years ago

willvarfar5• 11 years ago

(Mill team)

So every turf (aka 'process') has a special value. If this value is XORed with the high bits of a local pointer it turns it into a global pointer, and vice-versa.

Example: turf A has a local space register of 1010100000 (binary; lets keep the numbers small, but Mill addresses are really 60-bit). Note that the low five bits are 0. All local space masks will have some number of low bits 0.

A local address is 0000011000. Note that the high five bits happen to be zero. XORing in the local-space base would give the global address 1010111000.

Another local pointer might have the bit-pattern 0000100111. Note now that there is a bit set beyond the low zero bits in the mask; this time, the XOR will convert it into the global address 1010000111.

So as the local base mask has low bits all zero, all addresses within that span will be sequential in memory. But local space is disjoint in global space. This affects only the maximum continuous allocation size and not the total number of allocations.

When turf A forks, the child has to have local base mask that preserves the relative position of all allocations. But as the XOR mask will be different, the global addresses will not overlap for these 'local' allocations.

The vast majority of mmaps are actually shared (file buffers etc) and don't need this XORing. The CPU is transparently doing the XOR when needed and its nothing normal programs need to know about; only the kernel, when giving out new mmap regions, needs to know if it should hand out a global or local address.

caf• 11 years ago

So I think what you're saying here is that that if turf 10101 has an allocated local address 0000100111, then turf 10100 can't have an allocated local address of 0000000111, because they correspond to the same global address - they'd clash.

marcosdumay• 11 years ago

So you do have address translation hardware between the CPU and L1 cache. It's just that it's a very simple and fast one.

Very nice idea.

ablankst• 11 years ago

Have you thought much about address space randomization? It's a reasonably effective security strategy, but it essentially requires enough unused bits in the address space. If you have a system with one big memory space, presumably your address space is now more precious, or do you still have enough bits for randomization (both in the local and the global spaces).

willvarfar5• 11 years ago

We have thought about it a lot :)

Being SAS and having PIC and data makes the way ASLR works different. But we're big fans of exploit mitigation techniques and I will be preparing a decent white paper or talk about it shortly.

bakul• 11 years ago

I thought a "turf" was a protection domain? Has that changed? I thought one can have a turf without a thread running in it.

willvarfar5• 11 years ago

That's right. That hasn't changed.

Its natural for a normal OS to map their "processes" to Mill turfs. I make that jump in the explanation, but hold out hope that we can teach people to adopt a finer-grained approach where they sandbox and protect things within their program.

DiabloD3• 11 years ago

I just want to know why I can't buy a Mill yet. Stop teasing me, damnit!

jlebrech• 11 years ago

i guess it'll drastically lower transistor count?

sliverstorm• 11 years ago

Big Silicon?

CyberDildonics• 11 years ago

For starters they are creating real patents but so far the processor is virtual.

JoeAltmaier• 11 years ago

So, instead of switching page maps (and writing new TLB entries), the new process is allocated new TLB entries, corresponding to its process id in the high part of each pointer. Does this also require that the high bits of every pointer access have the local process ID inserted on use? Or are all pointers somehow tracked and rewritten on fork?

willvarfar5• 11 years ago

The XOR is applied inside the CPU when local pointers (any pointer with a particular high bit set) are actually dereferenced. Its transparent to the normal program. This is how we can COW the used pages without rewriting all the pointers (which is not a solvable problem in the face of memory-unsafe languages such as C).

vanderZwan• 11 years ago

Now that we have finally gotten the patent filings for this area of the Mill in

How much more to go?

willvarfar5• 11 years ago

Really not many. We are going to be getting a whole lot more implementation done now the filing phase is passing :D

hyc_symas• 11 years ago

Very nice. Much cleaner than the memory copying we had to do on ST-Minix. (But the Mill obviously still has an MMU, the MC68000 had nothing so we couldn't implement COW.)

stcredzero• 11 years ago

The result of all of this is that fork() on a Mill requires a cache flush of dirty lines from the parent local space that is not required on (some) MAS machines, but has no other added overheads. The gain is that sharing between processes has byte granularity, not page granularity, and is vastly cheaper to use.

What are the implications for server processes? The cache flush seems like a good tradeoff for things like Apache. Extremely fast communication using RAM between processes running on multi-core machines looks like a good capability to have. Language runtimes like Erlang's could benefit from this tremendously.

(How about something like Golang, but with Erlang-like actors and the ability to declare that certain modules cannon contain functions with side effects? Without lazy evaluation, it wouldn't be great for processing large datasets, but it could be awesome for games. (Actors would be distributed amongst processes, each of which would have their own GC.))

charpointer• 11 years ago

This work of Xoring and using shared mmaps is not new and it was published in 2009 and 2010 by two separate teams. See the following papers http://dl.acm.org/citation.cfm?id=1854288 and http://dl.acm.org/citation.cfm?id=1640096

I am not sure how this can be patented.

How the Mill CPU does fork() in a single address space

Related Stories