A description of the selfish Nix allocator

This TR from the Lsub papers page describes the Nix allocator and provides a bit of initial evaluation for it. In short, half of the times allocation of resources could be done by the allocating process without interlocking with other processes or cores and without disturbing any other system component. Plus other benefits described in the TR.

Here is a picture of the allocator as a teaser:

Selfish allocators in action

This is the output from the alloc device. The last few lines show that for paths,
chans, and, what is more important, I/O blocks, most of the times a process
could do the allocation by itself. It took a free structure out of the small number
of structures that are kept in the process structure in case it later allocates
whatever it liberated before.
For example, 13891 block allocations were done without reaching the central block allocator,
and 14440 were done using the block allocator.

Ouch!, the writing was a mistake!. It's 13891 self-allocations out of a total of 14440 allocations. I'm making this note editing the post. Thus, note that almost all of the allocations are a self-service, not just half of the allocations.

This is utterly important for many-core machines. Half Most of the times it's a self-service.

I will post here a paper describing the allocator in a near future.

% cat /dev/alloc
3473408/67108864 cache bytes
72/100 cache segs 0/0 reclaims 1 procs
0/7 rpcs
98/102 segs
12/100 text segs 0/0 reclaims
1071104000 memory
15663104 kernel
0/0 1G pages 0 user 0 kernel 0 bundled 0 split
0/496 2M pages 0 user 0 kernel 0 bundled 6 split
423/968 16K pages 229 user 194 kernel 0 bundled 0 split
82/99 4K pages 0 user 82 kernel 3792 bundled 0 split
6/6 pgas
1447/1509 pgs
169/181 path 5535/5716 self allocs 5563/5575 self frees
103/123 chan 7269/7392 self allocs 7297/7317 self frees
13796608/14192640 malloc 1 segs
56/63 block 13891/14440 self allocs 13945/14438 self frees
0/8388608 ialloc bytes
61/82 mmu 4096 pages

Selfish processes

There is an important optimization not described in previous posts, and not
considered in the evaluation and the traces shown there. The idea is
to let processes keep a few of the resources they release in case
they are needed later.

In particular, we modified the process structure to keep up to 10 pages
(of the size used for user segments). When a process releases a page
and has less than 10 pages kept, it simply keeps the page without
releasing it. Later, if a new page is needed it would first try to use
one from the per-process pool. The pool is not released when a process dies.
Instead, the pool is kept in the process structure and will be used
again when a new process is allocated using it.

The trace output taken after applying this optimization shows that
most of the pages are reused, and that for small cached programs about 1/3
of the allocations are satisfied with the per-process pool. Thus,
the contention on the central page allocator is greatly reduced with this
change.

Per process resource pool should be used with care. For example, our
attempts to do the same with the kernel memory allocator indicated that
it is not a good idea in this case. Memory allocations have very different
sizes and some structures are very long lived while others are very short
lived. Thus, what happen was that memory was wasted in per process pools
and, at the same time, not many memory allocations could benefit from this
technique.

In general, per-process allocation pools are a good idea when the structures
are frequently used and have the same size. For example, this could be
applied also to Chan and Path structures as used on Nix.

A memory trace for command execution in Nix

This is the output for executing

% cat /dev/alloc

in the steady state. That is, after executing the same command a few times so that all the previous things that could be cached are indeed cached. The file used, by the way, is reporting the statistics of several allocators in Nix, including the page allocator. So there is more information in the trace described here than just the set of faults and pages allocated or deallocated.

The events include everything since we typed the command until the shell prints out its prompt.
Thus, there is no microbenchmark trick going on.

The first faults are due to fork, used by rc to spawn the child process. Then, we have more faults for the child while it proceeds to execute the cat command. Pid 21 is the original shell process; pid 27 is the child that will execute pwd.

Let's see the trace before and then make a few remarks near the end of this post.

A fault caused because fork makes the data segment memory shared, but copied on reference. Here the parent references a data page:

fault pid 21 0x400000 r
fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x400000 pg 0x3fe78000 r2 n1
newpage 0x400000 -> 0x3fe24000 src 0xfffffffff018711c
fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x400000 pg 0x3fe24000 ref 1


The child starts executing and references a new text address:

fault pid 27 0x20f9e0 r
fixfault pid 27 s /bin/rc sref 9 Text 0x200000 addr 0x20c000 pg 0x1160000 r1 n1
fixfaulted pid 27 s /bin/rc Text 0x200000 addr 0x20c000 pg 0x1160000 ref 1


Another fault in the parent due to the copy on reference. This is because we flushed the MMU state during fork, but the page is already there, there is nothing to do to handle this type of fault, other than updating the MMU state to refer to the page, which is already there.

fault pid 21 0x404b30 w
fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x404000 pg 0x3fe74000 r2 n1
newpage 0x404000 -> 0x3fe64000 src 0xfffffffff018711c
fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x404000 pg 0x3fe64000 ref 1


The child continues executing and references a new text address:

fault pid 27 0x20a9d9 r
fixfault pid 27 s /bin/rc sref 9 Text 0x200000 addr 0x208000 pg 0x1188000 r1 n1
fixfaulted pid 27 s /bin/rc Text 0x200000 addr 0x208000 pg 0x1188000 ref 1

The child continues executing and references a data address:

fault pid 27 0x400060 w
fixfault pid 27 s /bin/rc sref 1 Data 0x400000 addr 0x400000 pg 0x3fe78000 r1 n1
fixfaulted pid 27 s /bin/rc Data 0x400000 addr 0x400000 pg 0x3fe78000 ref 1

Another fault in the parent due to the copy on reference, like before.

fault pid 21 0x409d5c r
fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x408000 pg 0x3fe70000 r2 n1
newpage 0x408000 -> 0x3fe68000 src 0xfffffffff018711c
fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x408000 pg 0x3fe68000 ref 1

The child continues executing and references a new text address:

fault pid 27 0x202aec r
fixfixfault pid 27 s /bin/rc sref 9 Text 0x200000 addr 0x200000 pg 0x10cc000 r1 n1
fixfaulted pid 27 s /bin/rc Text 0x200000 addr 0x200000 pg 0x10cc000 ref 1

Another fault in the parent due to the copy on reference, like before.

fault pid 21 0x40c178 r
fault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x40c000 pg 0x3fe4c000 r2 n1
newpage 0x40c000 -> 0x3fe6c000 src 0xfffffffff018711c
fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x40c000 pg 0x3fe6c000 ref 1

The child continues executing and references a data address:

fault pid 27 0x40a738 r
fixfault pid 27 s /bin/rc sref 1 Data 0x400000 addr 0x408000 pg 0x3fe70000 r1 n1
fixfaulted pid 27 s /bin/rc Data 0x400000 addr 0x408000 pg 0x3fe70000 ref 1

The child continues executing and references a new text address:

fault pid 27 0x212b47 r
fixfault pid 27 s /bin/rc sref 9 Text 0x200000 addr 0x210000 pg 0x118c000 r1 n1
fixfaulted pid 27 s /bin/rc Text 0x200000 addr 0x210000 pg 0x118c000 ref 1

The child continues executing and references a data address:

fault pid 27 0x404b30 w
fixfault pid 27 s /bin/rc sref 1 Data 0x400000 addr 0x404000 pg 0x3fe74000 r1 n1
fixfaulted pid 27 s /bin/rc Data 0x400000 addr 0x404000 pg 0x3fe74000 ref 1

The child continues executing and references a data address:

fault pid 27 0x40c17c r
fixfault pid 27 s /bin/rc sref 1 Data 0x400000 addr 0x40c000 pg 0x3fe4c000 r1 n1
fixfaulted pid 27 s /bin/rc Data 0x400000 addr 0x40c000 pg 0x3fe4c000 ref 1


We are now doing the exec in the child process...



pgfree pg 0x3fe78000
pgfree pg 0x3fe74000
pgfree pg 0x3fe70000
pgfree pg 0x3fe4c000

The child references a data address, which is not paged in from the file. The diagnostic indicates that the page is paged in from the cached image of the executable file, but no I/O was required. Simply, a new page is allocated and initial values for data are copied.

fault pid 27 0x400018 w
fixfault pid 27 s /bin/cat sref 1 Data 0x400000 addr 0x400000 pg 0x0 r0 n-1
pagein pid 27 s 0x400000 addr 0x400000 soff 0x0
newpage 0x400000 -> 0x3fe4c000 src 0xfffffffff018711c
fixfaulted pid 27 s /bin/cat Data 0x400000 addr 0x400000 pg 0x3fe4c000 ref 1

0/67108864 cache bytes
0/10 cache segs 0/0 reclaims 0 procs
0/3 rpcs
22/23 segs
8/10 text segs 0/0 reclaims
1071140864 memory
15663104 kernel
0/0 1G pages 0 user 0 kernel 0 bundled 0 split
0/502 2M pages 0 user 0 kernel 0 bundled 0 split
134/236 16K pages 119 user 15 kernel 0 bundled 0 split
61/61 4K pages 0 user 61 kernel 884 bundled 0 split
6/6 pgas
1447/1509 pgs
66/67 path
69/70 chan
11780256/14229504 malloc 1 segs
0/8388608 ialloc bytes
61/61 mmu 4096 pages

And we are done.

pgfree pg 0x3fe4c000

There are a few things to note here. One important thing is that there are no faults in the stack segments. That is because we copy stack memory and pre-install the entries in the MMU. Stacks in nix are small and it pays to copy them.

Another thing to note is that the text is not paged in. It is served from the cache. Thus, only updating the MMU is needed.

Note also how page allocation and deallocation is quite reduced, compared to what it could be. The reason is that stacks retain their memory, and that the page size is 16K, and so, not many page allocations are required.

Also, if you compare this with the trace from a standard Plan 9, you will notice other effects, described in a previous post in the Nix memory management TR.

Early evaluation of memory management in Nix mark IV

In a previous post I published a link to a TR describing the
recent work on memory management for Nix. Such TR has
been updated to include some early evaluation, which I reproduce
here.

To measure the  impact  of  the  different  changes  in  the
behavior  of the system, we took the final system and run it
with diagnostic output enabled for page allocation and  page
faults,  and measured the different events of interest. Then
we did the same disabling one or more of  the  improvements.
The  results  are not fully precise because debugging output
may miss some events sometimes. Further evaluation will  use
counters instead, and compare with a stock Plan 9 system.

     We have to say that the impact of the changes  is  more
dramatic  than shown by the results, because early modifica-
tions for the mount driver and other parts of the system, on
their  own, do a good job reducing the impact of system load
(e.g., by better caching).

     The variations of the system executed are  given  these
names in the results:

all

     The standard Nix mark IV. All new features are in.

nopf

     Prefaulting code for text and stack  segments  is  dis-
     abled.  Such  code  installs  into  the MMU entries for
     those pages already present in the segments (because of
     the  cache  or other optimizations). The alternative is
     installing entries on demand.

flush

     Prefaulting code is disabled and the MMU is flushed  on
     forks, as it is customary on Plan 9. The alternative to
     MMU flushes is flushing just the entries for  the  data
     segment  (others do not have to be because of optimiza-
     tions explained before).

nodeep

     Deep stack forks are disabled. Deep stack  forks  imply
     copying  the  actual  stack  memory  during  forks. The
     alternative is the standard copy on reference to fork a
     stack segment.

nostk

     Stack segments are not cached (their memory is not kept
     and  recycled) and deep stack copies are not performed.
     The alternative is the standard construction  by  zero-
     fill  on demand (due to page faults) and full dealloca-
     tion and allocation of stacks when processes  exit  and
     are created.

none

     There are no prefaulting code, the MMU  is  flushed  on
     forks, deep stack copying is disabled, and stack memory
     is not cached. Quite similar to the state of the system
     before  any  modification was made, but for using 16KiB
     pages for user segments.


none4k

     This is the old system.  Like the  previous  variation,
     but using standard 4KiB pages for user segments.

The system booted normally from a remote file server to exe-
cute  a shell instead of the full standard start script, and
then we executed  pwd twice. The  first  table  reports  the
results  for the second run of  pwd, counting since we typed
the command to the time when the shell  printed  its  prompt
after   pwd completed. The first way to read the table is to
compare any row with the first or the last one, to  see  the
impact of a particular configuration.

     The second table shows the same counters  but  for  the
entire execution of the system, from a hardware reset to the
prompt after executing  pwd twice.

_________________________________________________________________________
 bench    page allocs   page frees   mmu faults   page faults   page-ins
_________________________________________________________________________
  all          6             5           14           11           1
_________________________________________________________________________
  nopf         6             5           16           12           1
_________________________________________________________________________
 flush         6             5           22           18           1
_________________________________________________________________________
 nodeep        6             6           17           12           1
_________________________________________________________________________
 nostk         6             7           16           15           1
_________________________________________________________________________
  none         8             8           24           17           1
_________________________________________________________________________
 none4k       15            15           65           68           1
_________________________________________________________________________

Page  allocations,  page  deallocations,  page  faults,  MMU
faults,  and  pages paged in for variations of the system on
the second execution of a simple command.

_________________________________________________________________________
 bench    page allocs   page frees   mmu faults   page faults   page-ins
_________________________________________________________________________
  all         229           41          219           210         107
_________________________________________________________________________
  nopf        231           41          246           232         109
_________________________________________________________________________
 flush        224           38          311           283         109
_________________________________________________________________________
 nodeep       227           41          244           237         109
_________________________________________________________________________
 nostk        232           56          245           233         109
_________________________________________________________________________
  none        236           60          321           296         109
_________________________________________________________________________
 none4k       501          107          847           843         313
_________________________________________________________________________

Page  allocations,  page  deallocations,  page  faults,  MMU
faults,  and pages paged in for variations of the system for
an entire boot and two executions of a simple command.

Several things can be seen:

∙    going from the old to the new system means  going  from
     68  down  to 11 page faults, just for running  pwd from
     the shell.  For the entire boot process it means  going
     from 843 down to 210.

∙    Using a more reasonable page size, without other  opti-
     mizations,  reduces a lot the number of page faults (as
     could be expected). We saw that almost all the 4K pages
     paged  in are actually used for 16K pages, thus it pays
     to change the page size. Also, the new page size has  a
     significant  impact  in  the size of reads performed by
     the mount driver, because it enables  concurrent  reads
     for larger sizes.

∙    Deep stack copying reduces a little the page faults  in
     the system, but it might not be worth if the time taken
     to zero out the stack pages kept in the cache is wasted
     when  they  are  not  used. In our system that does not
     seem to be case.

∙    More efforts should be  taken  to  avoid  flushing  MMU
     state.  As  it  could be expected, not flushing the MMU
     when it is not necessary reduces quite a bit the number
     of page faults.

As a reference, here we list the trace output for the

old  and  the new system for executing  pwd the second time.

It is illustrative to compare them.

This is for the new system:

% pwd

newpg 0x000000003fe44000 pgsz 0x4000 for 0x4000

fault pid 23 0x20f9e0 r

fault pid 21 0x400000 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20c000 pg 0x1174000 r1 n1

fixfixfault faulted pid 23 s /bin/rc Text 0x200000 addr 0x20c000 pg 0x1174000 ref 1

fault pid 23 0x20a9d9 r

pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x400000 pg 0x3fe6c000 r2 n1

newpg 0x000000003fe80000 pgsz 0x4000 for 0x4000

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x400000 pg 0x3fe80000 ref 1

fault pid 21 0x404b30 w

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x208000 pfixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x404000 pg 0x3fe70000 r2 n1

newpg 0x000000003fe84000 pgsz 0x4000 for 0x4000

g 0x11a4000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x404000 pg 0x3fe84000 ref 1

fault pid 21 0x409afc r

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x208000 pg 0x11a4000 ref 1

fault pid 23 0x400060 w

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x408000 pg 0x3fe78000 r2 n1

newpg 0x000000003fe88000 pgsz 0x4000 for 0x4000

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x408000 pg 0x3fe88000 ref 1

fault pid 21 0x40c178 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x400000 pg 0x3fe6c000 r1 n1

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x400000 pg 0x3fe6c000 ref 1

fault pid 23 0x202aec r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x40c000 pg 0x3fe74000 r2 n1

newpg 0x000000003feaddr 0x200000 pg 0x10e4000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x200000 pg 0x10e4000 ref 1

fault pid 23 0x40a698 r

8c000 pgsz 0x4000 for 0x4000

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x40c000 pg 0x3fe8c000 ref 1

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x408000 pg 0x3fe78000 r1 n1

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x408000 pg 0x3fe78000 ref 1

fault pid 23 0x212b47 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x210000 pg 0x11a8000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x210000 pg 0x11a8000 ref 1

fault pid 23 0x404b30 w

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x404000 pg 0x3fe70000 r1 n1

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x404000 pg 0x3fe70000 ref 1

fault pid 23 0x40c17c r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x40c000 pg 0x3fe74000 r1 n1

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x40c000 pg 0x3fe74000 ref 1

fault pid 23 0x7ffffeffbfe0 w

fixfault pid 23 s '' sref 1 Stack 0x7ffffdffc000 addr 0x7ffffeff8000 pg 0x3fe60000 r1 n1

fixfaulted pid 23 s '' Stack 0x7ffffdffc000 addr 0x7ffffeff8000 pg 0x3fe60000 ref 1

pgfree pg 0x3fe6c000

pgfree pg 0x3fe70000

pgfree pg 0x3fe78000

pgfree pg 0x3fe74000

fault pid 23 0x400018 w

fixfault pid 23 s /bin/pwd sref 1 Data 0x400000 addr 0x400000 pg 0x0 r0 n-1

pagein pid 23 s 0x400000 addr 0x400000 soff 0x0

newpg 0x000000003fe74000 pgsz 0x4000 for 0x4000

fixfaulted pid 23 s /bin/pwd Data 0x400000 addr 0x400000 pg 0x3fe74000 ref 1

/usr/nemo

pgfree pg 0x3fe74000

And this is for the old system:

fault pid 21 0x2000c4 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x200000 pg 0x116c000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x200000 pg 0x116c000 ref 1

fault pid 21 0x20170a r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x201000 pg 0x116f000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x201000 pg 0x116f000 ref 1

fault pid 21 0x205dfc r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x205000 pg 0x1132000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x205000 pg 0x1132000 ref 1

fault pid 21 0x40b834 w

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x40b000 pg 0x11b3000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x40b000 pg 0x11b3000 ref 1

fault pid 21 0x407c78 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x407000 pg 0x11ac000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x407000 pg 0x11ac000 ref 1

fault pid 23 0x20f9e0 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20f000 pg 0x1138000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x20f000 pg 0x1138000 ref 1

fault pid 23 0x7fffffffefe8 w

fixfault pid 23 s /bin/rc sref 1 Stack 0x7ffffefff000 addr 0x7fffffffe000 pg 0x11b0000 r2 n1

newpg 0x00000000011d2000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s '' Stack 0x7ffffefff000 addr 0x7fffffffe000 pg 0x11d2000 ref 1

fault pid 23 0x20a9d9 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20a000 pg 0x1146000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x20a000 pg 0x1146000 ref 1

fault pid 23 0x20be91 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20b000 pg 0x1135000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x20b000 pg 0x1135000 ref 1

fault pid 23 0x400060 w

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x400000 pg 0x11aa000 r2 n1

newpg 0x00000000011d0000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x400000 pg 0x11d0000 ref 1

fault pid 23 0x202aec r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x202000 pg 0x1130000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x202000 pg 0x1130000 ref 1

fault pid 23 0x40a698 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x40a000 pg 0x119e000 r2 n1

newpg 0x00000000011d6000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x40a000 pg 0x11d6000 ref 1

fault pid 23 0x20977d r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x209000 pg 0x1139000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x209000 pg 0x1139000 ref 1

fault pid 23 0x20dbe3 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20d000 pg 0x113b000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x20d000 pg 0x113b000 ref 1

fault pid 23 0x212b47 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x212000 pg 0x113c000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x212000 pg 0x113c000 ref 1

fault pid 23 0x401338 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x401000 pg 0x11af000 r2 n1

newpg 0x00000000011ce000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x401000 pg 0x11ce000 ref 1

fault pid 23 0x210670 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x210000 pg 0x113d000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x210000 pg 0x113d000 ref 1

fault pid 23 0x404b30 w

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x404000 pg 0x11ae000 r2 n1

newpg 0x00000000011d3000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x404000 pg 0x11d3000 ref 1

fault pid 23 0x21107c r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x211000 pg 0x1143000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x211000 pg 0x1143000 ref 1

fault pid 23 0x40c17c r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x40c000 pg 0x11b2000 r2 n1

newpg 0x00000000011cf000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x40c000 pg 0x11cf000 ref 1

fault pid 23 0x4097fc r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x409000 pg 0x1196000 r2 n1

newpg 0x00000000011ca000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x409000 pg 0x11ca000 ref 1

fault pid 23 0x20e02d r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20e000 pg 0x1147000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x20e000 pg 0x1147000 ref 1

fault pid 23 0x20cbb0 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x20c000 pg 0x1129000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x20c000 pg 0x1129000 ref 1

fault pid 23 0x40204a r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x402000 pg 0x11a7000 r2 n1

newpg 0x00000000011c6000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x402000 pg 0x11c6000 ref 1

fault pid 23 0x2086dc r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x208000 pg 0x1165000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x208000 pg 0x1165000 ref 1

fault pid 23 0x213000 r

fixfault pid 23 s /bin/rc sref 9 Text 0x200000 addr 0x213000 pg 0x1142000 r1 n1

fixfaulted pid 23 s /bin/rc Text 0x200000 addr 0x213000 pg 0x1142000 ref 1

fault pid 23 0x4055b8 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x405000 pg 0x11a9000 r2 n1

newpg 0x00000000011d8000 pgsz 0x4000 for 0x1000

splitbundle pg 0x00000000011d8000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x405000 pg 0x11d8000 ref 1

fault pid 23 0x4081a8 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x408000 pg 0x11a8000 r2 n1

newpg 0x00000000011db000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x408000 pg 0x11db000 ref 1

fault pid 23 0x407c78 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x407000 pg 0x11ac000 r2 n1

newpg 0x00000000011da000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x407000 pg 0x11da000 ref 1

fault pid 23 0x406dd8 r

fixfault pid 23 s /bin/rc sref 1 Data 0x400000 addr 0x406000 pg 0x11ad000 r2 n1

newpg 0x00000000011d9000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/rc Data 0x400000 addr 0x406000 pg 0x11d9000 ref 1

fault pid 21 0x7fffffffefe8 w

fixfault pid 23 0x7ffffeffefe0 w

fixfault pid 23 s '' sref 1 Stack 0x7ffffdfff000 addr 0x7ffffeffe000 pg 0x0 r0 n-1

newpg 0x00000000011dc000 pgsz 0x4000 for 0x1000

splitbundle pg 0x00000000011dc000

fixfaulted pid 23 s '' Stack 0x7ffffdfff000 addr 0x7ffffeffe000 pg 0x11dc000 ref 1

pgfree pg 0x11d2000

pgfree pg 0x11d0000

pgfree pg 0x11ce000

pgfree pg 0x11c6000

pgfree pg 0x11d3000

pgfree pg 0x11d8000

pgfree pg 0x11d9000

pgfree pg 0x11da000

pgfree pg 0x11db000

pgfree pg 0x11ca000

pgfree pg 0x11d6000

pgfree pg 0x11cf000

faultfault pid 23 0x7fffffffef98 w

fixfault pid 23 s /bin/pwd sref 1 Stack 0x7ffffefff000 addr 0x7fffffffe000 pg 0x11dc000 r1 n1

fixfaulted pid 23 s '' Stack 0x7ffffefff000 addr 0x7fffffffe000 pg 0x11dc000 ref 1

fault pid 23 0x20008a r

fixfault pid 23 s /bin/pwd sref 3 Text 0x200000 addr 0x200000 pg 0x11cd000 r1 n1

fixfaulted pid 23 s /bin/pwd Text 0x200000 addr 0x200000 pg 0x11cd000 ref 1

fault pid 23 0x400018 w

fixfault pid 23 s /bin/pwd sref 1 Data 0x400000 addr 0x400000 pg 0x0 r0 n-1

pagein pid 23 s 0x400000 addr 0x400000 soff 0x0

newpg 0x00000000011cf000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/pwd Data 0x400000 addr 0x400000 pg 0x11cf000 ref 1

fault pid 23 0x201b6d r

fixfault pid 23 s /bin/pwd sref 3 Text 0x200000 addr 0x201000 pg 0x11d1000 r1 n1

fixfaulted pid 23 s /bin/pwd Text 0x200000 addr 0x201000 pg 0x11d1000 ref 1

 pid 21 s /bfault pid 23 0x2020ef r

fixfault pid 23 s /bin/pwd sref 3 Text 0x200000 addr 0x202000 pg 0x11d4000 r1 n1

fixfaulted pid 23 s /bin/pwd Text 0x200000 addr 0x202000 pg 0x11d4000 ref 1

fault pid 23 0x2040b2 r

fixfault pid 23 s /bin/pwd sref 3 Text 0x200000 addr 0x204000 pg 0x11d7000 r1 n1

fixfaulted pid 23 s /bin/pwd Text 0x200000 addr 0x204000 pg 0x11d7000 ref 1

/usr/nemo

fault pid 23 0x401098 r

fixfault pid 23 s /bin/pwd sref 1 Data 0x400000 addr 0x401000 pg 0x0 r0 n-1

pagein: zfod 0x401000

newpg 0x00000000011d6000 pgsz 0x1000 for 0x1000

fixfaulted pid 23 s /bin/pwd Data 0x400000 addr 0x401000 pg 0x11d6000 ref 1

pgfree pg 0x11dc000

pgfree pg 0x11cf000

pgfree pg 0x11d6000

in/rc sref 1 Stack 0x7ffffefff000 addr 0x7fffffffe000 pg 0x11b0000 r1 n1

fixfaulted pid 21 s '' Stack 0x7ffffefff000 addr 0x7fffffffe000 pg 0x11b0000 ref 1

fault pid 21 0x20f9e0 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x20f000 pg 0x1138000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x20f000 pg 0x1138000 ref 1

fault pid 21 0x20a9d9 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x20a000 pg 0x1146000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x20a000 pg 0x1146000 ref 1

fault pid 21 0x20bdca r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x20b000 pg 0x1135000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x20b000 pg 0x1135000 ref 1

fault pid 21 0x400000 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x400000 pg 0x11aa000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x400000 pg 0x11aa000 ref 1

fault pid 21 0x20ddb3 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x20d000 pg 0x113b000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x20d000 pg 0x113b000 ref 1

fault pid 21 0x212ea2 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x212000 pg 0x113c000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x212000 pg 0x113c000 ref 1

fault pid 21 0x401338 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x401000 pg 0x11af000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x401000 pg 0x11af000 ref 1

fault pid 21 0x210670 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x210000 pg 0x113d000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x210000 pg 0x113d000 ref 1

fault pid 21 0x404b30 w

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x404000 pg 0x11ae000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x404000 pg 0x11ae000 ref 1

fault pid 21 0x409afc r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x409000 pg 0x1196000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x409000 pg 0x1196000 ref 1

fault pid 21 0x211ba3 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x211000 pg 0x1143000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x211000 pg 0x1143000 ref 1

fault pid 21 0x20e02d r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x20e000 pg 0x1147000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x20e000 pg 0x1147000 ref 1

fault pid 21 0x208574 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x208000 pg 0x1165000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x208000 pg 0x1165000 ref 1

fault pid 21 0x202c39 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x202000 pg 0x1130000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x202000 pg 0x1130000 ref 1

fault pid 21 0x40a698 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x40a000 pg 0x119e000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x40a000 pg 0x119e000 ref 1

fault pid 21 0x2097b7 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x209000 pg 0x1139000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x209000 pg 0x1139000 ref 1

fault pid 21 0x213000 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x213000 pg 0x1142000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x213000 pg 0x1142000 ref 1

fault pid 21 0x40c178 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x40c000 pg 0x11b2000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x40c000 pg 0x11b2000 ref 1

fault pid 21 0x20ce7e r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x20c000 pg 0x1129000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x20c000 pg 0x1129000 ref 1

fault pid 21 0x204bba r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x204000 pg 0x1133000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x204000 pg 0x1133000 ref 1

fault pid 21 0x402611 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x402000 pg 0x11a7000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x402000 pg 0x11a7000 ref 1

fault pid 21 0x405e00 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x405000 pg 0x11a9000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x405000 pg 0x11a9000 ref 1

fault pid 21 0x408d48 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x408000 pg 0x11a8000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x408000 pg 0x11a8000 ref 1

fault pid 21 0x20310e r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x203000 pg 0x1136000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x203000 pg 0x1136000 ref 1

fault pid 21 0x40b834 w

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x40b000 pg 0x11b3000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x40b000 pg 0x11b3000 ref 1

fault pid 21 0x206ab9 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x206000 pg 0x113a000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x206000 pg 0x113a000 ref 1

fault pid 21 0x406820 r

fixfault pid 21 s /bin/rc sref 1 Data 0x400000 addr 0x406000 pg 0x11ad000 r1 n1

fixfaulted pid 21 s /bin/rc Data 0x400000 addr 0x406000 pg 0x11ad000 ref 1

fault pid 21 0x7fffffffce78 w

fixfault pid 21 s /bin/rc sref 1 Stack 0x7ffffefff000 addr 0x7fffffffc000 pg 0x11bd000 r1 n1

fixfaulted pid 21 s '' Stack 0x7ffffefff000 addr 0x7fffffffc000 pg 0x11bd000 ref 1

fault pid 21 0x2071d8 r

fixfault pid 21 s /bin/rc sref 7 Text 0x200000 addr 0x207000 pg 0x116b000 r1 n1

fixfaulted pid 21 s /bin/rc Text 0x200000 addr 0x207000 pg 0x116b000 ref 1

Memory management in Nix Mark IV

There is a draft TR describing how the memory management has been fully reworked in Nix mark IV. The resulting system is faster, suffers a lot fewer page faults than its predecessor, and exploits better concurrent access to file servers.

We are still testing the implementation, and hopefully will make it public soon.
In the future I will write another post showing some evaluation for the system and traces we obtained from debug output that are quite illustrative.