Currently we collect (add) all roots into a global array in a single-threaded GC phase.
This hinders parallelism.
With this change we just kick off parallel for for number_of_goroutines+5 iterations.
Then parallel for callback decides whether it needs to scan stack of a goroutine
scan data segment, scan finalizers, etc. This eliminates the single-threaded phase entirely.
This requires to store all goroutines in an array instead of a linked list
(to allow direct indexing).
This CL also removes DebugScan functionality. It is broken because it uses
unbounded stack, so it can not run on g0. When it was working, I've found
it helpless for debugging issues because the two algorithms are too different now.
This change would require updating the DebugScan, so it's simpler to just delete it.

With 8 threads this change reduces GC pause by ~6%, while keeping cputime roughly the same.

garbage-8
allocated                 2987886      2989221      +0.04%
allocs                      62885        62887      +0.00%
cputime                  21286000     21272000      -0.07%
gc-pause-one             26633247     24885421      -6.56%
gc-pause-total             873570       811264      -7.13%
rss                     242089984    242515968      +0.18%
sys-gc                   13934336     13869056      -0.47%
sys-heap                205062144    205062144      +0.00%
sys-other                12628288     12628288      +0.00%
sys-stack                11534336     11927552      +3.41%
sys-total               243159104    243487040      +0.13%
time                      2809477      2740795      -2.44%

R=golang-codereviews, rsc
CC=cshapiro, golang-codereviews, khr
https://golang.org/cl/46860043

It's entirely outdated today.

R=golang-codereviews, bradfitz, gobot, r
CC=golang-codereviews
https://golang.org/cl/43500045

Instead of a per-goroutine stack of defers for all sizes,
introduce per-P defer pool for argument sizes 8, 24, 40, 56, 72 bytes.

For a program that starts 1e6 goroutines and then joins then:
old: rss=6.6g virtmem=10.2g time=4.85s
new: rss=4.5g virtmem= 8.2g time=3.48s

R=golang-codereviews, rsc
CC=golang-codereviews
https://golang.org/cl/42750044

R=golang-codereviews, dvyukov, khr
CC=golang-codereviews
https://golang.org/cl/54060043

Currently for 2-word blocks we set the flag to clear the flag. Makes no sense.
In particular on 32-bits we call memclr always.

R=golang-codereviews, dave, iant
CC=golang-codereviews, khr, rsc
https://golang.org/cl/41170044

The deadlock is between span->specialLock and proflock:

goroutine 11 [running]:
runtime.MProf_Free(0x7fa272d26508, 0xc210054180, 0xc0)
        src/pkg/runtime/mprof.goc:220 +0x27
runtime.freespecial(0x7fa272d1e088, 0xc210054180, 0xc0)
        src/pkg/runtime/mheap.c:691 +0x6a
runtime.freeallspecials(0x7fa272d1af50, 0xc210054180, 0xc0)
        src/pkg/runtime/mheap.c:717 +0xb5
runtime.free(0xc210054180)
        src/pkg/runtime/malloc.goc:190 +0xfd
selectgo(0x7fa272a5ef58)
        src/pkg/runtime/chan.c:1136 +0x2d8
runtime.selectgo(0xc210054180)
        src/pkg/runtime/chan.c:840 +0x12
runtime_test.func·058()
        src/pkg/runtime/proc_test.go:146 +0xb4
runtime.goexit()
        src/pkg/runtime/proc.c:1405
created by runtime_test.TestTimerFairness
        src/pkg/runtime/proc_test.go:152 +0xd1

goroutine 12 [running]:
addspecial(0xc2100540c0, 0x7fa272d1e0a0)
        src/pkg/runtime/mheap.c:569 +0x88
runtime.setprofilebucket(0xc2100540c0, 0x7fa272d26508)
        src/pkg/runtime/mheap.c:668 +0x73
runtime.MProf_Malloc(0xc2100540c0, 0xc0, 0x0)
        src/pkg/runtime/mprof.goc:212 +0x16b
runtime.mallocgc(0xc0, 0x0, 0xc200000000)
        src/pkg/runtime/malloc.goc:142 +0x239
runtime.mal(0xbc)
        src/pkg/runtime/malloc.goc:703 +0x38
newselect(0x2, 0x7fa272a5cf60)
        src/pkg/runtime/chan.c:632 +0x53
runtime.newselect(0xc200000002, 0xc21005f000)
        src/pkg/runtime/chan.c:615 +0x28
runtime_test.func·058()
        src/pkg/runtime/proc_test.go:146 +0x37
runtime.goexit()
        src/pkg/runtime/proc.c:1405
created by runtime_test.TestTimerFairness
        src/pkg/runtime/proc_test.go:152 +0xd1

Fixes #7099.

R=golang-codereviews, khr
CC=golang-codereviews
https://golang.org/cl/53120043

The test prints an excessive \n when /dev/null is not present.

R=golang-codereviews, bradfitz, dave
CC=golang-codereviews
https://golang.org/cl/54890043

Fixes #7157.

R=alex.brainman, bradfitz
CC=golang-codereviews
https://golang.org/cl/54880043

What was happenning is as follows:
Each writer goroutine always triggers GC during its scheduling quntum.
After GC goroutines are shuffled so that the timer goroutine is always second in the queue.
This repeats infinitely, causing timer goroutine starvation.
Fixes #7126.

R=golang-codereviews, shanemhansen, khr, khr
CC=golang-codereviews
https://golang.org/cl/53080043

It's pretty distracting to use expvar with the output of both
the top-level map and map values jumping around randomly.

Also fixes a potential race where multiple clients trying to
increment a map int or float key at the same time could lose
updates.

R=golang-codereviews, couchmoney
CC=golang-codereviews
https://golang.org/cl/54320043

Use testing.AllocsPerRun now that it exists, instead of doing it by hand.

Fixes #6076

R=golang-codereviews, alex.brainman
CC=golang-codereviews
https://golang.org/cl/53810043

R=golang-codereviews, bradfitz
CC=golang-codereviews
https://golang.org/cl/54290043

R=r
CC=golang-codereviews
https://golang.org/cl/54040043

Fixes bug 7145

R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/53970043

R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/54000043

R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/53690043

Vararg C calls present a problem for the GC because the
argument types are not derivable from the signature.  Remove
them by passing pointers to channel elements instead of the
channel elements directly.

R=golang-codereviews, gobot, rsc, dvyukov
CC=golang-codereviews
https://golang.org/cl/53430043

Fixes #7138.

R=r, bradfitz, dave
CC=dvyukov, golang-codereviews
https://golang.org/cl/53910043

The compiler change is an ugly hack.
We can do better.

««« original CL description
syscall: mark arguments to Syscall as noescape
Heap arguments to "async" syscalls will break when/if we have moving GC anyway.
With this change is must not break until moving GC, because a user must
reference the object in Go to preserve liveness. Otherwise the code is broken already.
Reduces number of leaked params from 125 to 36 on linux.

R=golang-codereviews, mikioh.mikioh, bradfitz
CC=cshapiro, golang-codereviews, khr, rsc
https://golang.org/cl/45930043
»»»

R=golang-codereviews, r
CC=bradfitz, dvyukov, golang-codereviews
https://golang.org/cl/53870043

Recent crashes on 386 Darwin appear to be caused by this system call
smashing the stack. Phenomenology shows that allocating more data
here addresses the probem.
The guess is that since the actual system call is getdirentries64, 64 is
what we should allocate.

Should fix the darwin/386 build.

R=rsc
CC=golang-codereviews
https://golang.org/cl/53840043

R=r
CC=golang-codereviews
https://golang.org/cl/53720043

R=rsc, iant
CC=golang-codereviews
https://golang.org/cl/53190046

Generated by addca.

R=gobot
CC=golang-codereviews
https://golang.org/cl/53730043

Heap arguments to "async" syscalls will break when/if we have moving GC anyway.
With this change is must not break until moving GC, because a user must
reference the object in Go to preserve liveness. Otherwise the code is broken already.
Reduces number of leaked params from 125 to 36 on linux.

R=golang-codereviews, mikioh.mikioh, bradfitz
CC=cshapiro, golang-codereviews, khr, rsc
https://golang.org/cl/45930043

decrypt: reduced the number of copy calls from 2n to 1.
encrypt: reduced the number of copy calls from n to 1.

Encryption is straight-forward: use dst instead of tmp when
xoring the block with the iv.

Decryption now loops backwards through the blocks abusing the
fact that the previous block's ciphertext (src) is the iv. This
means we don't need to copy the iv every time, in addition to
using dst instead of tmp like encryption.

R=golang-codereviews, agl, mikioh.mikioh
CC=golang-codereviews
https://golang.org/cl/50900043

Generated by addca.

R=gobot
CC=golang-codereviews
https://golang.org/cl/53710043

R=alex.brainman, dave, jsing, gobot, rsc
CC=golang-codereviews
https://golang.org/cl/35990043

Falsely claimed an old, no longer true condition that the first argument
must be a pointer.
Fixes #6697

R=golang-codereviews, bradfitz
CC=golang-codereviews
https://golang.org/cl/53480043

Update #5001

This test is flakey on linux servers and fails otherwise good builds. Mikio has some proposals to fix the test, but they require additional plumbing.

In the meantime, disable this test in -short mode so it will run during the full net test suite, but not during builder ci.

R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/53410043

No changes, just rearrangement. The tests were in need of a little
housekeeping.

R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/53400043

Matches Darwin and the BSDs. This means leveldb-go, kv,
Camlistore, etc can stop defining these structs on Linux by
hand.

Update #7059

R=golang-codereviews, dave, iant
CC=golang-codereviews
https://golang.org/cl/53350043

Reflect used to communicate to the runtime using interface words,
which is bad for precise GC because sometimes iwords hold a pointer
and sometimes they don't.  This change rewrites channel and select
operations to always pass pointers to the runtime.

reflect.Select gets somewhat more expensive, as we now do an allocation
per receive case instead of one allocation whose size is the max of
all the received types.  This seems unavoidable to get preciseness
(unless we move the allocation into selectgo, which is a much bigger
change).

Fixes #6490

R=golang-codereviews, dvyukov, rsc
CC=golang-codereviews
https://golang.org/cl/52900043

Status codes 204, 304, and 1xx don't allow bodies. We already
had a function for this, but we were hard-coding just 304
(StatusNotModified) in a few places.  Use the function
instead, and flesh out tests for all codes.

Fixes #6685

R=golang-codereviews, r
CC=golang-codereviews
https://golang.org/cl/53290044

R=golang-codereviews, bradfitz
CC=golang-codereviews
https://golang.org/cl/8274046

Apparently this is expensive on Windows.

Fixes #7020

R=golang-codereviews, alex.brainman, mattn.jp, dvyukov
CC=golang-codereviews
https://golang.org/cl/52840043

We forgot to include the width of "0x" when computing the crossover
from internal buffer to allocated buffer.
Also add a helper function to the test for formatting large zero-padded
test strings.

Fixes #6777.

R=golang-codereviews, iant
CC=golang-codereviews
https://golang.org/cl/50820043

This CL makes the bitmaps a little more precise about variables
that have their address taken but for which the address does not
escape to the heap, so that the variables are kept in the stack frame
rather than allocated on the heap.

The code before this CL handled these variables by treating every
return statement as using every such variable and depending on
liveness analysis to essentially treat the variable as live during the
entire function. That approach has false positives and (worse) false
negatives. That is, it's both sloppy and buggy:

        func f(b1, b2 bool) {	// x live here! (sloppy)
                if b2 {
                        print(0) // x live here! (sloppy)
                        return
                }
                var z **int
                x := new(int)
                *x = 42
                z = &x
                print(**z) // x live here (conservative)
                if b2 {
                        print(1) // x live here (conservative)
                        return
                }
                for {
                        print(**z) // x not live here (buggy)
                }
        }

The first two liveness annotations (marked sloppy) are clearly
wrong: x cannot be live if it has not yet been declared.

The last liveness annotation (marked buggy) is also wrong:
x is live here as *z, but because there is no return statement
reachable from this point in the code, the analysis treats x as dead.

This CL changes the liveness calculation to mark such variables
live exactly at points in the code reachable from the variable
declaration. This keeps the conservative decisions but fixes
the sloppy and buggy ones.

The CL also detects ambiguously live variables, those that are
being marked live but may not actually have been initialized,
such as in this example:

        func f(b1 bool) {
                var z **int
                if b1 {
                        x := new(int)
                        *x = 42
                        z = &x
                } else {
                        y := new(int)
                        *y = 54
                        z = &y
                }
                print(**z) // x, y live here (conservative)
        }

Since the print statement is reachable from the declaration of x,
x must conservatively be marked live. The same goes for y.
Although both x and y are marked live at the print statement,
clearly only one of them has been initialized. They are both
"ambiguously live".

These ambiguously live variables cause problems for garbage
collection: the collector cannot ignore them but also cannot
depend on them to be initialized to valid pointer values.

Ambiguously live variables do not come up too often in real code,
but recent changes to the way map and interface runtime functions
are invoked has created a large number of ambiguously live
compiler-generated temporary variables. The next CL will adjust
the analysis to understand these temporaries better, to make
ambiguously live variables fairly rare.

Once ambiguously live variables are rare enough, another CL will
introduce code at the beginning of a function to zero those
slots on the stack. At that point the garbage collector and the
stack copying routines will be able to depend on the guarantee that
if a slot is marked as live in a liveness bitmap, it is initialized.

R=khr
CC=golang-codereviews, iant
https://golang.org/cl/51810043

Missed this case in CL 51010045.

TBR=khr
CC=golang-codereviews
https://golang.org/cl/53200043

Example of output:

goroutine 4 [sleep for 3 min]:
time.Sleep(0x34630b8a000)
        src/pkg/runtime/time.goc:31 +0x31
main.func·002()
        block.go:16 +0x2c
created by main.main
        block.go:17 +0x33

Full program and output are here:
http://play.golang.org/p/NEZdADI3Td

Fixes #6809.

R=golang-codereviews, khr, kamil.kisiel, bradfitz, rsc
CC=golang-codereviews
https://golang.org/cl/50420043

Use lock-free fixed-size ring for work queues
instead of an unbounded mutex-protected array.
The ring has single producer and multiple consumers.
If the ring overflows, work is put onto global queue.

benchmark              old ns/op    new ns/op    delta
BenchmarkMatmult               7            5  -18.12%
BenchmarkMatmult-4             2            2  -18.98%
BenchmarkMatmult-16            1            0  -12.84%

BenchmarkCreateGoroutines                     105           88  -16.10%
BenchmarkCreateGoroutines-4                   376          219  -41.76%
BenchmarkCreateGoroutines-16                  241          174  -27.80%
BenchmarkCreateGoroutinesParallel             103           87  -14.66%
BenchmarkCreateGoroutinesParallel-4           169          143  -15.38%
BenchmarkCreateGoroutinesParallel-16          158          151   -4.43%

R=golang-codereviews, rsc
CC=ddetlefs, devon.odell, golang-codereviews
https://golang.org/cl/46170044