[dev.cc] all: merge default (e4ab8f908aac) into dev.cc

TBR=austin
CC=golang-codereviews
https://codereview.appspot.com/179040044

1 files changed, 77 insertions, 0 deletions

diff --git a/src/runtime/mgc1.go b/src/runtime/mgc1.go
new file mode 100644
index 000000000..d1aab4554
--- /dev/null
+++ b/src/runtime/mgc1.go
@@ -0,0 +1,77 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Garbage collector (GC)
+
+package runtime
+
+const (
+	// Four bits per word (see #defines below).
+	gcBits             = 4
+	wordsPerBitmapByte = 8 / gcBits
+)
+
+const (
+	// GC type info programs.
+	// The programs allow to store type info required for GC in a compact form.
+	// Most importantly arrays take O(1) space instead of O(n).
+	// The program grammar is:
+	//
+	// Program = {Block} "insEnd"
+	// Block = Data | Array
+	// Data = "insData" DataSize DataBlock
+	// DataSize = int // size of the DataBlock in bit pairs, 1 byte
+	// DataBlock = binary // dense GC mask (2 bits per word) of size ]DataSize/4[ bytes
+	// Array = "insArray" ArrayLen Block "insArrayEnd"
+	// ArrayLen = int // length of the array, 8 bytes (4 bytes for 32-bit arch)
+	//
+	// Each instruction (insData, insArray, etc) is 1 byte.
+	// For example, for type struct { x []byte; y [20]struct{ z int; w *byte }; }
+	// the program looks as:
+	//
+	// insData 3 (BitsPointer BitsScalar BitsScalar)
+	//	insArray 20 insData 2 (BitsScalar BitsPointer) insArrayEnd insEnd
+	//
+	// Total size of the program is 17 bytes (13 bytes on 32-bits).
+	// The corresponding GC mask would take 43 bytes (it would be repeated
+	// because the type has odd number of words).
+	insData = 1 + iota
+	insArray
+	insArrayEnd
+	insEnd
+)
+
+const (
+	// Pointer map
+	_BitsPerPointer  = 2
+	_BitsMask        = (1 << _BitsPerPointer) - 1
+	_PointersPerByte = 8 / _BitsPerPointer
+
+	// If you change these, also change scanblock.
+	// scanblock does "if(bits == BitsScalar || bits == BitsDead)" as "if(bits <= BitsScalar)".
+	_BitsDead    = 0
+	_BitsScalar  = 1
+	_BitsPointer = 2
+
+	// 64 bytes cover objects of size 1024/512 on 64/32 bits, respectively.
+	_MaxGCMask = 64
+)
+
+// Bits in per-word bitmap.
+// #defines because we shift the values beyond 32 bits.
+//
+// Each word in the bitmap describes wordsPerBitmapWord words
+// of heap memory.  There are 4 bitmap bits dedicated to each heap word,
+// so on a 64-bit system there is one bitmap word per 16 heap words.
+//
+// The bitmap starts at mheap.arena_start and extends *backward* from
+// there.  On a 64-bit system the off'th word in the arena is tracked by
+// the off/16+1'th word before mheap.arena_start.  (On a 32-bit system,
+// the only difference is that the divisor is 8.)
+const (
+	bitBoundary = 1 // boundary of an object
+	bitMarked   = 2 // marked object
+	bitMask     = bitBoundary | bitMarked
+	bitPtrMask  = _BitsMask << 2
+)