code review 3975046: runtime: faster allocator, garbage collector

runtime: faster allocator, garbage collector

GC is still single-threaded.
Multiple threads will happen in another CL.

Garbage collection pauses are typically
about half as long as they were before this CL.

[brainman, 2011-01-25 23:22:14]

Just a quick look, Russ.

http://codereview.appspot.com/3975046/diff/2001/src/pkg/runtime/windows/mem.c
File src/pkg/runtime/windows/mem.c (right):

http://codereview.appspot.com/3975046/diff/2001/src/pkg/runtime/windows/mem.c...
src/pkg/runtime/windows/mem.c:73: p = runtime·stdcall(runtime·VirtualAlloc, 4,
nil, n, MEM_RESERVE, 0);
p = runtime·stdcall(runtime·VirtualAlloc, 4, nil, arena, MEM_RESERVE,
PAGE_EXECUTE_READWRITE);

[rsc, 2011-01-31 23:52:48]

Hello brainman, iant, r (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[brainman, 2011-02-01 00:29:50]

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/windows/mem.c
File src/pkg/runtime/windows/mem.c (right):

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/windows/mem....
src/pkg/runtime/windows/mem.c:61: return runtime·stdcall(runtime·VirtualAlloc,
4, v, n, MEM_RESERVE, PAGE_EXECUTE_READWRITE);
return runtime·stdcall(runtime·VirtualAlloc, 4, v, n, MEM_RESERVE, 0);

fails with ERROR_INVALID_PARAMETER.

return runtime·stdcall(runtime·VirtualAlloc, 4, v, n, MEM_RESERVE,
PAGE_EXECUTE_READWRITE);

doesn't complain about paramters, but still fails with ERROR_INVALID_ADDRESS.

If I change it to:

return runtime·stdcall(runtime·VirtualAlloc, 4, 0, n, MEM_RESERVE,
PAGE_EXECUTE_READWRITE);

to ask for page anywhere, like we do for SysAlloc, then the call succeeds, but
runtime·mallocinit fails because it checks returned area is in the place it has
asked for (runtime·throw("runtime: cannot reserve memory bitmap virtual addre
...)

From VirtualAlloc doco:

"
lpAddress [in, optional]

    The starting address of the region to allocate. If the memory is being
reserved, the specified address is rounded down to the nearest multiple of the
allocation granularity. If the memory is already reserved and is being
committed, the address is rounded down to the next page boundary. To determine
the size of a page and the allocation granularity on the host computer, use the
GetSystemInfo function. If this parameter is NULL, the system determines where
to allocate the region.

"


Alex

[iant, 2011-02-01 06:23:45]

LGTM

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mcentral.c
File src/pkg/runtime/mcentral.c (right):

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mcentral.c#n...
src/pkg/runtime/mcentral.c:76: //runtime·printf("MCentral_Alloc %p<\n", c);
Do you want to leave these commented out printf calls here?

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:105: shift = off%wordsPerBitmapWord;
Spaces around % here?

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:146: shift = off%wordsPerBitmapWord;
Space around %?  It's a bit hard to read without the space, at least in
codereview, since % looks so much like a letter.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:193: bits &=
((bitBlockBoundary|bitAllocated)<<(bitShift-shift)) -
(bitBlockBoundary|bitAllocated);
I can not figure out this expression.  if bitShift - shift >= 5, you seem to be
clearing bits that you want to check in the loop.  Or else I have no idea what
is going on, which is likely.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:544: USED(heap0);
Do you need these USED lines, given the printf call?

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:638: if((bits & (bitBlockBoundary|bitAllocated)) !=
(bitBlockBoundary|bitAllocated)) {
This test looks wrong.  If bitAllocated is set, bitBlockBoundary will not be
set.  It should only be testing bitAllocated.  This only works because as far as
I can see nothing calls this function.

[rsc, 2011-02-01 17:41:41]

PTAL

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mcentral.c
File src/pkg/runtime/mcentral.c (right):

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mcentral.c#n...
src/pkg/runtime/mcentral.c:76: //runtime·printf("MCentral_Alloc %p<\n", c);
On 2011/02/01 06:23:46, iant wrote:
> Do you want to leave these commented out printf calls here?

Done.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:105: shift = off%wordsPerBitmapWord;
On 2011/02/01 06:23:46, iant wrote:
> Spaces around % here?

Done.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:146: shift = off%wordsPerBitmapWord;
On 2011/02/01 06:23:46, iant wrote:
> Space around %?  It's a bit hard to read without the space, at least in
> codereview, since % looks so much like a letter.

Done.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:193: bits &=
((bitBlockBoundary|bitAllocated)<<(bitShift-shift)) -
(bitBlockBoundary|bitAllocated);
On 2011/02/01 06:23:46, iant wrote:
> I can not figure out this expression.  if bitShift - shift >= 5, you seem to
be
> clearing bits that you want to check in the loop.  Or else I have no idea what
> is going on, which is likely.

Took me a little while to reconstruct the logic, but
I believe it is correct.  Please see if the expanded 
comment clarifies things.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:544: USED(heap0);
On 2011/02/01 06:23:46, iant wrote:
> Do you need these USED lines, given the printf call?

Done.

http://codereview.appspot.com/3975046/diff/16001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:638: if((bits & (bitBlockBoundary|bitAllocated)) !=
(bitBlockBoundary|bitAllocated)) {
On 2011/02/01 06:23:46, iant wrote:
> This test looks wrong.  If bitAllocated is set, bitBlockBoundary will not be
> set.  It should only be testing bitAllocated.  This only works because as far
as
> I can see nothing calls this function.

Deleted the function.

[r, 2011-02-02 05:09:00]

LGTM

it seems fine; i can't internalize this in finite time.

is there a guide to the dungeon in a comment somewhere? in some places one line
of code gets 20 lines of comments; in other pages of bitwhacking go by without
remark.  not for this round, but please for instance put comments on the
functions.  scanblock, for instance, starts with a forever loop with gotos
inside and it's not obvious what its invariants or termination conditions are.

http://codereview.appspot.com/3975046/diff/17015/src/pkg/runtime/debug.go
File src/pkg/runtime/debug.go (right):

http://codereview.appspot.com/3975046/diff/17015/src/pkg/runtime/debug.go#new...
src/pkg/runtime/debug.go:72: BySize [61]struct {
please explain where 61 comes from

[rsc, 2011-02-02 23:01:52]

PTAL.

More comments added.

[iant, 2011-02-02 23:39:58]

LGTM

http://codereview.appspot.com/3975046/diff/20002/src/pkg/runtime/malloc.h
File src/pkg/runtime/malloc.h (right):

http://codereview.appspot.com/3975046/diff/20002/src/pkg/runtime/malloc.h#new...
src/pkg/runtime/malloc.h:377: int32	runtime·checking;
What's runtime·checking for?  Should it have a comment?

http://codereview.appspot.com/3975046/diff/20002/src/pkg/runtime/malloc.h#new...
src/pkg/runtime/malloc.h:385: FlagNoPointers = 0x80000000U,	// flag - no
pointers here
Formerly you needed large values here because you were leaving room for the
reference count.  But these values are no longer stored in memory.  Why not use
1, 2, 4, 8?

http://codereview.appspot.com/3975046/diff/20002/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/3975046/diff/20002/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:12: UseCas = 1,
UseCas does not seem to be used anywhere.

[r, 2011-02-02 23:40:33]

LGTM

new comments are a big help

[rsc, 2011-02-03 04:03:43]

Hello brainman, iant, r (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[rsc, 2011-02-03 04:03:49]

*** Submitted as http://code.google.com/p/go/source/detail?r=1e800f6ac9dc ***

runtime: faster allocator, garbage collector

GC is still single-threaded.
Multiple threads will happen in another CL.

Garbage collection pauses are typically
about half as long as they were before this CL.

R=brainman, iant, r
CC=golang-dev
http://codereview.appspot.com/3975046

[mattn, 2011-02-03 05:10:48]

After applying this patch, I get below.

C:\>cgo
throw: runtime: cannot reserve memory bitmap virtual address space

On 2011/02/03 04:03:49, rsc wrote:
> *** Submitted as http://code.google.com/p/go/source/detail?r=1e800f6ac9dc ***
> 
> runtime: faster allocator, garbage collector
> 
> GC is still single-threaded.
> Multiple threads will happen in another CL.
> 
> Garbage collection pauses are typically
> about half as long as they were before this CL.
> 
> R=brainman, iant, r
> CC=golang-dev
> http://codereview.appspot.com/3975046

[rsc, 2011-02-03 05:18:21]

On Thu, Feb 3, 2011 at 00:10,  <mattn.jp@gmail.com> wrote:
> After applying this patch, I get below.
>
> C:\>cgo
> throw: runtime: cannot reserve memory bitmap virtual address space

Thanks for the report.  Looks like issue 1464 in another guise.
I will have to make a different plan for managing the address space.

Russ

[brainman, 2011-02-03 05:27:12]

On 2011/02/03 05:18:21, rsc wrote:
> On Thu, Feb 3, 2011 at 00:10,  <mailto:mattn.jp@gmail.com> wrote:
> > After applying this patch, I get below.
> >
> > C:\>cgo
> > throw: runtime: cannot reserve memory bitmap virtual address space
> 
> Thanks for the report.  Looks like issue 1464 in another guise.
> I will have to make a different plan for managing the address space.
> 

This is a process map:

Memory map
Address   Size      Owner     Section    Contains           Type  Access  
Initial >Mapped as
00010000  00001000 >         >           Environment        Priv >RW       RW
00020000  00001000 >         >           Process Parameters Priv >RW       RW
0022D000  00001000 >         >                              Priv >RW  Guar>RW 
Guar>
0022E000  00002000 >         >           Stack of main thre>Priv >RW       RW
00230000  00003000 >         >                              Priv >RW       RW
00330000  00003000 >         >                              Map  >RW       RW
00340000  00016000 >         >                              Map  >R        R    
   \Device\HarddiskVolume2\WINNT\system32\unicode.nls
00360000  0002F000 >         >                              Map  >R        R    
   \Device\HarddiskVolume2\WINNT\system32\locale.nls
00390000  00041000 >         >                              Map  >R        R    
   \Device\HarddiskVolume2\WINNT\system32\sortkey.nls
003E0000  00004000 >         >                              Map  >R        R    
   \Device\HarddiskVolume2\WINNT\system32\sorttbls.nls
00400000  00001000 >test     >           PE header          Img  >R        RWE
Copy>
00401000  00102000 >test     >.text      Code               Img  >R E      RWE
Copy>
00503000  00410000 >test     >.data      Data               Img  >RW  Copy>RWE
Copy>
00913000  00001000 >test     >.idata     Imports            Img  >RW  Copy>RWE
Copy>
00914000  00001000 >test     >/4                            Img  >R        RWE
Copy>
00915000  0000B000 >test     >/18                           Img  >R        RWE
Copy>
00920000  00007000 >test     >/30                           Img  >R        RWE
Copy>
00927000  0003D000 >test     >/43                           Img  >R        RWE
Copy>
00964000  0000D000 >test     >/55                           Img  >R        RWE
Copy>
00971000  0001A000 >test     >/71                           Img  >R        RWE
Copy>
0098B000  00001000 >test     >/87                           Img  >R        RWE
Copy>
0098C000  00001000 >test     >/102                          Img  >R        RWE
Copy>
0098D000  00001000 >test     >.symtab                       Img  >R        RWE
Copy>
77F80000  00001000 >ntdll    >           PE header          Img  >R        RWE
Copy>
77F81000  00044000 >ntdll    >.text      Code,exports       Img  >R E      RWE
Copy>
77FC5000  00005000 >ntdll    >ECODE      Code               Img  >R E      RWE
Copy>
77FCA000  00004000 >ntdll    >PAGE       Code               Img  >R E      RWE
Copy>
77FCE000  00003000 >ntdll    >.data      Data               Img  >RW  Copy>RWE
Copy>
77FD1000  00001000 >ntdll    >EDATA                         Img  >RW  Copy>RWE
Copy>
77FD2000  00027000 >ntdll    >.rsrc      Resources          Img  >R        RWE
Copy>
77FF9000  00003000 >ntdll    >.reloc     Relocations        Img  >R        RWE
Copy>
7C570000  00001000 >kernel32 >           PE header          Img  >R        RWE
Copy>
7C571000  0005A000 >kernel32 >.text      Code,imports,expor>Img  >R E      RWE
Copy>
7C5CB000  00004000 >kernel32 >.data      Data               Img  >RW       RWE
Copy>
7C5CF000  00051000 >kernel32 >.rsrc      Resources          Img  >R        RWE
Copy>
7C620000  00004000 >kernel32 >.reloc     Relocations        Img  >R        RWE
Copy>
7F6F0000  00007000 >         >                              Map  >R E      R E
7FFB0000  00024000 >         >           Code pages         Map  >R        R
7FFDE000  00001000 >         >           Data block of main>Priv >RWE      RWE
7FFDF000  00001000 >         >           Process Environmen>Priv >RWE      RWE
7FFE0000  00001000 >         >                              Priv >R        R

As you can see we have plenty of staff in memory after .data section, so you
can't just assume to find free address space there.

You are asking for block of 805306368 bytes at 0x920000

SysReserve: 0x920000, 805306368
SysReserve failed with errno=487

to be reserved, but we have dwarf debug info sitting there. Perhaps, you could
just to ask for a block anywhere, but I'm not sure what your idea is.

Alex

[brainman, 2011-02-03 05:40:44]

On 2011/02/03 05:27:12, brainman wrote:
> You are asking for block of 805306368 bytes at 0x920000
> 
> SysReserve: 0x920000, 805306368
> SysReserve failed with errno=487
> 
> to be reserved, but we have dwarf debug info sitting there. ...

Just to confirm, I build my .exe without "dwarf" sections (8g -s ....), and my
program runs to completion.

Alex

[dho, 2011-02-03 05:45:08]

I'm too tired to look at this in detail right now (just got home from
work and it's past bedtime, heh), but the freebsd builder is reporting
similar issues.

--dho

2011/2/3  <alex.brainman@gmail.com>:
> On 2011/02/03 05:27:12, brainman wrote:
>>
>> You are asking for block of 805306368 bytes at 0x920000
>
>> SysReserve: 0x920000, 805306368
>> SysReserve failed with errno=487
>
>> to be reserved, but we have dwarf debug info sitting there. ...
>
> Just to confirm, I build my .exe without "dwarf" sections (8g -s ....),
> and my program runs to completion.
>
> Alex
>
> http://codereview.appspot.com/3975046/
>

[rsc, 2011-02-03 05:53:05]

On Thu, Feb 3, 2011 at 00:45, Devon H. O'Dell <devon.odell@gmail.com> wrote:
> I'm too tired to look at this in detail right now (just got home from
> work and it's past bedtime, heh), but the freebsd builder is reporting
> similar issues.

yes, everything is broken.

russ

[rsc, 2011-02-03 05:54:38]

On Thu, Feb 3, 2011 at 00:52, Russ Cox <rsc@golang.org> wrote:
> On Thu, Feb 3, 2011 at 00:45, Devon H. O'Dell <devon.odell@gmail.com> wrote:
>> I'm too tired to look at this in detail right now (just got home from
>> work and it's past bedtime, heh), but the freebsd builder is reporting
>> similar issues.
>
> yes, everything is broken.

sorry, not everything: linux and darwin work fine if you
have ulimit -v unlimited.  i suspect the freebsd problem
is similar (run ulimit -v unlimited).

but in general this approach to managing memory is
breaking a lot of common situations.  i need to rethink.

russ