libgo: Update to revision 15193:6fdc1974457c of master library.

From-SVN: r194692

12 files changed, 517 insertions, 223 deletions

diff --git a/libgo/runtime/env_posix.c b/libgo/runtime/env_posix.c
new file mode 100644
index 0000000..31f4179
--- /dev/null
+++ b/libgo/runtime/env_posix.c
@@ -0,0 +1,37 @@
+// 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.
+
+// +build darwin freebsd linux netbsd openbsd windows
+
+#include "runtime.h"
+#include "array.h"
+
+extern Slice syscall_Envs asm ("syscall.Envs");
+
+const byte*
+runtime_getenv(const char *s)
+{
+	int32 i, j, len;
+	const byte *v, *bs;
+	String* envv;
+	int32 envc;
+
+	bs = (const byte*)s;
+	len = runtime_findnull(bs);
+	envv = (String*)syscall_Envs.__values;
+	envc = syscall_Envs.__count;
+	for(i=0; i<envc; i++){
+		if(envv[i].len <= len)
+			continue;
+		v = (const byte*)envv[i].str;
+		for(j=0; j<len; j++)
+			if(bs[j] != v[j])
+				goto nomatch;
+		if(v[len] != '=')
+			goto nomatch;
+		return v+len+1;
+	nomatch:;
+	}
+	return nil;
+}
diff --git a/libgo/runtime/go-trampoline.c b/libgo/runtime/go-trampoline.c
index 2d8d9e6..17f73d4 100644
--- a/libgo/runtime/go-trampoline.c
+++ b/libgo/runtime/go-trampoline.c
@@ -106,8 +106,8 @@ __go_allocate_trampoline (uintptr_t size, void *closure)
    no other references to it.  */
 
 void
-runtime_trampoline_scan (void (*addroot) (byte *, uintptr))
+runtime_trampoline_scan (void (*addroot) (Obj))
 {
   if (trampoline_page != NULL)
-    addroot ((byte *) &trampoline_page, sizeof trampoline_page);
+    addroot ((Obj){(byte *) &trampoline_page, sizeof trampoline_page, 0});
 }
diff --git a/libgo/runtime/malloc.goc b/libgo/runtime/malloc.goc
index f1f3fcd..2a614e5 100644
--- a/libgo/runtime/malloc.goc
+++ b/libgo/runtime/malloc.goc
@@ -491,7 +491,7 @@ runtime_MHeap_SysAlloc(MHeap *h, uintptr n)
 static Lock settype_lock;
 
 void
-runtime_settype_flush(M *m, bool sysalloc)
+runtime_settype_flush(M *mp, bool sysalloc)
 {
 	uintptr *buf, *endbuf;
 	uintptr size, ofs, j, t;
@@ -503,8 +503,8 @@ runtime_settype_flush(M *m, bool sysalloc)
 	uintptr typ, p;
 	MSpan *s;
 
-	buf = m->settype_buf;
-	endbuf = buf + m->settype_bufsize;
+	buf = mp->settype_buf;
+	endbuf = buf + mp->settype_bufsize;
 
 	runtime_lock(&settype_lock);
 	while(buf < endbuf) {
@@ -602,7 +602,7 @@ runtime_settype_flush(M *m, bool sysalloc)
 	}
 	runtime_unlock(&settype_lock);
 
-	m->settype_bufsize = 0;
+	mp->settype_bufsize = 0;
 }
 
 // It is forbidden to use this function if it is possible that
@@ -610,7 +610,7 @@ runtime_settype_flush(M *m, bool sysalloc)
 void
 runtime_settype(void *v, uintptr t)
 {
-	M *m1;
+	M *mp;
 	uintptr *buf;
 	uintptr i;
 	MSpan *s;
@@ -618,16 +618,16 @@ runtime_settype(void *v, uintptr t)
 	if(t == 0)
 		runtime_throw("settype: zero type");
 
-	m1 = runtime_m();
-	buf = m1->settype_buf;
-	i = m1->settype_bufsize;
+	mp = runtime_m();
+	buf = mp->settype_buf;
+	i = mp->settype_bufsize;
 	buf[i+0] = (uintptr)v;
 	buf[i+1] = t;
 	i += 2;
-	m1->settype_bufsize = i;
+	mp->settype_bufsize = i;
 
-	if(i == nelem(m1->settype_buf)) {
-		runtime_settype_flush(m1, false);
+	if(i == nelem(mp->settype_buf)) {
+		runtime_settype_flush(mp, false);
 	}
 
 	if(DebugTypeAtBlockEnd) {
diff --git a/libgo/runtime/malloc.h b/libgo/runtime/malloc.h
index b3baaec..710484e 100644
--- a/libgo/runtime/malloc.h
+++ b/libgo/runtime/malloc.h
@@ -468,17 +468,25 @@ enum
 	FlagNoGC = 1<<2,	// must not free or scan for pointers
 };
 
+typedef struct Obj Obj;
+struct Obj
+{
+	byte	*p;	// data pointer
+	uintptr	n;	// size of data in bytes
+	uintptr	ti;	// type info
+};
+
 void	runtime_MProf_Malloc(void*, uintptr);
 void	runtime_MProf_Free(void*, uintptr);
 void	runtime_MProf_GC(void);
-void	runtime_MProf_Mark(void (*addroot)(byte *, uintptr));
+void	runtime_MProf_Mark(void (*addroot)(Obj));
 int32	runtime_gcprocs(void);
 void	runtime_helpgc(int32 nproc);
 void	runtime_gchelper(void);
 
 struct __go_func_type;
 bool	runtime_getfinalizer(void *p, bool del, void (**fn)(void*), const struct __go_func_type **ft);
-void	runtime_walkfintab(void (*fn)(void*), void (*scan)(byte *, uintptr));
+void	runtime_walkfintab(void (*fn)(void*), void (*scan)(Obj));
 
 enum
 {
@@ -494,3 +502,6 @@ enum
 void	runtime_gc_m_ptr(Eface*);
 
 void	runtime_memorydump(void);
+
+void	runtime_time_scan(void (*)(Obj));
+void	runtime_trampoline_scan(void (*)(Obj));
diff --git a/libgo/runtime/mfinal.c b/libgo/runtime/mfinal.c
index f2f640a..7c906da 100644
--- a/libgo/runtime/mfinal.c
+++ b/libgo/runtime/mfinal.c
@@ -193,7 +193,7 @@ runtime_getfinalizer(void *p, bool del, void (**fn)(void*), const struct __go_fu
 }
 
 void
-runtime_walkfintab(void (*fn)(void*), void (*addroot)(byte *, uintptr))
+runtime_walkfintab(void (*fn)(void*), void (*addroot)(Obj))
 {
 	void **key;
 	void **ekey;
@@ -206,8 +206,8 @@ runtime_walkfintab(void (*fn)(void*), void (*addroot)(byte *, uintptr))
 		for(; key < ekey; key++)
 			if(*key != nil && *key != ((void*)-1))
 				fn(*key);
-		addroot((byte*)&fintab[i].fkey, sizeof(void*));
-		addroot((byte*)&fintab[i].val, sizeof(void*));
+		addroot((Obj){(byte*)&fintab[i].fkey, sizeof(void*), 0});
+		addroot((Obj){(byte*)&fintab[i].val, sizeof(void*), 0});
 		runtime_unlock(&fintab[i]);
 	}
 }
diff --git a/libgo/runtime/mgc0.c b/libgo/runtime/mgc0.c
index 45f8a56..698400b 100644
--- a/libgo/runtime/mgc0.c
+++ b/libgo/runtime/mgc0.c
@@ -9,6 +9,7 @@
 #include "runtime.h"
 #include "arch.h"
 #include "malloc.h"
+#include "mgc0.h"
 #include "race.h"
 
 #ifdef USING_SPLIT_STACK
@@ -24,11 +25,13 @@ extern void * __splitstack_find_context (void *context[10], size_t *, void **,
 enum {
 	Debug = 0,
 	DebugMark = 0,  // run second pass to check mark
-	DataBlock = 8*1024,
 
 	// Four bits per word (see #defines below).
 	wordsPerBitmapWord = sizeof(void*)*8/4,
 	bitShift = sizeof(void*)*8/4,
+
+	handoffThreshold = 4,
+	IntermediateBufferCapacity = 64,
 };
 
 // Bits in per-word bitmap.
@@ -81,12 +84,16 @@ uint32 runtime_worldsema = 1;
 
 static int32 gctrace;
 
+// The size of Workbuf is N*PageSize.
 typedef struct Workbuf Workbuf;
 struct Workbuf
 {
-	LFNode node; // must be first
+#define SIZE (2*PageSize-sizeof(LFNode)-sizeof(uintptr))
+	LFNode  node; // must be first
 	uintptr nobj;
-	byte *obj[512-(sizeof(LFNode)+sizeof(uintptr))/sizeof(byte*)];
+	Obj     obj[SIZE/sizeof(Obj) - 1];
+	uint8   _padding[SIZE%sizeof(Obj) + sizeof(Obj)];
+#undef SIZE
 };
 
 typedef struct Finalizer Finalizer;
@@ -120,13 +127,6 @@ static Workbuf* getfull(Workbuf*);
 static void	putempty(Workbuf*);
 static Workbuf* handoff(Workbuf*);
 
-typedef struct GcRoot GcRoot;
-struct GcRoot
-{
-	byte *p;
-	uintptr n;
-};
-
 static struct {
 	uint64	full;  // lock-free list of full blocks
 	uint64	empty; // lock-free list of empty blocks
@@ -143,77 +143,122 @@ static struct {
 	byte	*chunk;
 	uintptr	nchunk;
 
-	GcRoot	*roots;
+	Obj	*roots;
 	uint32	nroot;
 	uint32	rootcap;
 } work;
 
-// scanblock scans a block of n bytes starting at pointer b for references
-// to other objects, scanning any it finds recursively until there are no
-// unscanned objects left.  Instead of using an explicit recursion, it keeps
-// a work list in the Workbuf* structures and loops in the main function
-// body.  Keeping an explicit work list is easier on the stack allocator and
-// more efficient.
+enum {
+	// TODO(atom): to be expanded in a next CL
+	GC_DEFAULT_PTR = GC_NUM_INSTR,
+};
+
+// PtrTarget and BitTarget are structures used by intermediate buffers.
+// The intermediate buffers hold GC data before it
+// is moved/flushed to the work buffer (Workbuf).
+// The size of an intermediate buffer is very small,
+// such as 32 or 64 elements.
+struct PtrTarget
+{
+	void *p;
+	uintptr ti;
+};
+
+struct BitTarget
+{
+	void *p;
+	uintptr ti;
+	uintptr *bitp, shift;
+};
+
+struct BufferList
+{
+	struct PtrTarget ptrtarget[IntermediateBufferCapacity];
+	struct BitTarget bittarget[IntermediateBufferCapacity];
+	struct BufferList *next;
+};
+static struct BufferList *bufferList;
+
+static Lock lock;
+
+// flushptrbuf moves data from the PtrTarget buffer to the work buffer.
+// The PtrTarget buffer contains blocks irrespective of whether the blocks have been marked or scanned,
+// while the work buffer contains blocks which have been marked
+// and are prepared to be scanned by the garbage collector.
+//
+// _wp, _wbuf, _nobj are input/output parameters and are specifying the work buffer.
+// bitbuf holds temporary data generated by this function.
+//
+// A simplified drawing explaining how the todo-list moves from a structure to another:
+//
+//     scanblock
+//  (find pointers)
+//    Obj ------> PtrTarget (pointer targets)
+//     ↑          |
+//     |          | flushptrbuf (1st part,
+//     |          | find block start)
+//     |          ↓
+//     `--------- BitTarget (pointer targets and the corresponding locations in bitmap)
+//  flushptrbuf
+//  (2nd part, mark and enqueue)
 static void
-scanblock(byte *b, uintptr n)
+flushptrbuf(struct PtrTarget *ptrbuf, uintptr n, Obj **_wp, Workbuf **_wbuf, uintptr *_nobj, struct BitTarget *bitbuf)
 {
-	byte *obj, *arena_start, *arena_used, *p;
-	void **vp;
-	uintptr size, *bitp, bits, shift, i, j, x, xbits, off, nobj, nproc;
+	byte *p, *arena_start, *obj;
+	uintptr size, *bitp, bits, shift, j, x, xbits, off, nobj, ti;
 	MSpan *s;
 	PageID k;
-	void **wp;
+	Obj *wp;
 	Workbuf *wbuf;
-	bool keepworking;
-
-	if((intptr)n < 0) {
-		runtime_printf("scanblock %p %D\n", b, (int64)n);
-		runtime_throw("scanblock");
-	}
+	struct PtrTarget *ptrbuf_end;
+	struct BitTarget *bitbufpos, *bt;
 
-	// Memory arena parameters.
 	arena_start = runtime_mheap.arena_start;
-	arena_used = runtime_mheap.arena_used;
-	nproc = work.nproc;
 
-	wbuf = nil;  // current work buffer
-	wp = nil;  // storage for next queued pointer (write pointer)
-	nobj = 0;  // number of queued objects
+	wp = *_wp;
+	wbuf = *_wbuf;
+	nobj = *_nobj;
 
-	// Scanblock helpers pass b==nil.
-	// Procs needs to return to make more
-	// calls to scanblock.  But if work.nproc==1 then
-	// might as well process blocks as soon as we
-	// have them.
-	keepworking = b == nil || work.nproc == 1;
+	ptrbuf_end = ptrbuf + n;
 
-	// Align b to a word boundary.
-	off = (uintptr)b & (PtrSize-1);
-	if(off != 0) {
-		b += PtrSize - off;
-		n -= PtrSize - off;
+	// If buffer is nearly full, get a new one.
+	if(wbuf == nil || nobj+n >= nelem(wbuf->obj)) {
+		if(wbuf != nil)
+			wbuf->nobj = nobj;
+		wbuf = getempty(wbuf);
+		wp = wbuf->obj;
+		nobj = 0;
+
+		if(n >= nelem(wbuf->obj))
+			runtime_throw("ptrbuf has to be smaller than WorkBuf");
 	}
 
-	for(;;) {
-		// Each iteration scans the block b of length n, queueing pointers in
-		// the work buffer.
-		if(Debug > 1)
-			runtime_printf("scanblock %p %D\n", b, (int64)n);
+	// TODO(atom): This block is a branch of an if-then-else statement.
+	//             The single-threaded branch may be added in a next CL.
+	{
+		// Multi-threaded version.
 
-		vp = (void**)b;
-		n >>= (2+PtrSize/8);  /* n /= PtrSize (4 or 8) */
-		for(i=0; i<(uintptr)n; i++) {
-			obj = (byte*)vp[i];
+		bitbufpos = bitbuf;
 
-			// Words outside the arena cannot be pointers.
-			if((byte*)obj < arena_start || (byte*)obj >= arena_used)
-				continue;
+		while(ptrbuf < ptrbuf_end) {
+			obj = ptrbuf->p;
+			ti = ptrbuf->ti;
+			ptrbuf++;
+
+			// obj belongs to interval [mheap.arena_start, mheap.arena_used).
+			if(Debug > 1) {
+				if(obj < runtime_mheap.arena_start || obj >= runtime_mheap.arena_used)
+					runtime_throw("object is outside of mheap");
+			}
 
 			// obj may be a pointer to a live object.
 			// Try to find the beginning of the object.
 
 			// Round down to word boundary.
-			obj = (void*)((uintptr)obj & ~((uintptr)PtrSize-1));
+			if(((uintptr)obj & ((uintptr)PtrSize-1)) != 0) {
+				obj = (void*)((uintptr)obj & ~((uintptr)PtrSize-1));
+				ti = 0;
+			}
 
 			// Find bits for this word.
 			off = (uintptr*)obj - (uintptr*)arena_start;
@@ -226,6 +271,8 @@ scanblock(byte *b, uintptr n)
 			if((bits & (bitAllocated|bitBlockBoundary)) != 0)
 				goto found;
 
+			ti = 0;
+
 			// Pointing just past the beginning?
 			// Scan backward a little to find a block boundary.
 			for(j=shift; j-->0; ) {
@@ -246,13 +293,13 @@ scanblock(byte *b, uintptr n)
 			s = runtime_mheap.map[x];
 			if(s == nil || k < s->start || k - s->start >= s->npages || s->state != MSpanInUse)
 				continue;
-			p =  (byte*)((uintptr)s->start<<PageShift);
+			p = (byte*)((uintptr)s->start<<PageShift);
 			if(s->sizeclass == 0) {
 				obj = p;
 			} else {
 				if((byte*)obj >= (byte*)s->limit)
 					continue;
-				size = runtime_class_to_size[s->sizeclass];
+				size = s->elemsize;
 				int32 i = ((byte*)obj - p)/size;
 				obj = p+i*size;
 			}
@@ -265,81 +312,203 @@ scanblock(byte *b, uintptr n)
 			bits = xbits >> shift;
 
 		found:
-			// If another proc wants a pointer, give it some.
-			if(work.nwait > 0 && nobj > 4 && work.full == 0) {
-				wbuf->nobj = nobj;
-				wbuf = handoff(wbuf);
-				nobj = wbuf->nobj;
-				wp = (void**)(wbuf->obj + nobj);
-			}
-
 			// Now we have bits, bitp, and shift correct for
 			// obj pointing at the base of the object.
 			// Only care about allocated and not marked.
 			if((bits & (bitAllocated|bitMarked)) != bitAllocated)
 				continue;
-			if(nproc == 1)
-				*bitp |= bitMarked<<shift;
-			else {
-				for(;;) {
-					x = *bitp;
-					if(x & (bitMarked<<shift))
-						goto continue_obj;
-					if(runtime_casp((void**)bitp, (void*)x, (void*)(x|(bitMarked<<shift))))
-						break;
-				}
-			}
+
+			*bitbufpos = (struct BitTarget){obj, ti, bitp, shift};
+			bitbufpos++;
+		}
+
+		runtime_lock(&lock);
+		for(bt=bitbuf; bt<bitbufpos; bt++){
+			xbits = *bt->bitp;
+			bits = xbits >> bt->shift;
+			if((bits & bitMarked) != 0)
+				continue;
+
+			// Mark the block
+			*bt->bitp = xbits | (bitMarked << bt->shift);
 
 			// If object has no pointers, don't need to scan further.
 			if((bits & bitNoPointers) != 0)
 				continue;
 
+			obj = bt->p;
+
+			// Ask span about size class.
+			// (Manually inlined copy of MHeap_Lookup.)
+			x = (uintptr)obj >> PageShift;
+			if(sizeof(void*) == 8)
+				x -= (uintptr)arena_start>>PageShift;
+			s = runtime_mheap.map[x];
+
 			PREFETCH(obj);
 
-			// If buffer is full, get a new one.
-			if(wbuf == nil || nobj >= nelem(wbuf->obj)) {
-				if(wbuf != nil)
-					wbuf->nobj = nobj;
-				wbuf = getempty(wbuf);
-				wp = (void**)(wbuf->obj);
-				nobj = 0;
-			}
-			*wp++ = obj;
+			*wp = (Obj){obj, s->elemsize, bt->ti};
+			wp++;
 			nobj++;
-		continue_obj:;
 		}
+		runtime_unlock(&lock);
+
+		// If another proc wants a pointer, give it some.
+		if(work.nwait > 0 && nobj > handoffThreshold && work.full == 0) {
+			wbuf->nobj = nobj;
+			wbuf = handoff(wbuf);
+			nobj = wbuf->nobj;
+			wp = wbuf->obj + nobj;
+		}
+	}
+
+	*_wp = wp;
+	*_wbuf = wbuf;
+	*_nobj = nobj;
+}
+
+// Program that scans the whole block and treats every block element as a potential pointer
+static uintptr defaultProg[2] = {PtrSize, GC_DEFAULT_PTR};
+
+// scanblock scans a block of n bytes starting at pointer b for references
+// to other objects, scanning any it finds recursively until there are no
+// unscanned objects left.  Instead of using an explicit recursion, it keeps
+// a work list in the Workbuf* structures and loops in the main function
+// body.  Keeping an explicit work list is easier on the stack allocator and
+// more efficient.
+//
+// wbuf: current work buffer
+// wp:   storage for next queued pointer (write pointer)
+// nobj: number of queued objects
+static void
+scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
+{
+	byte *b, *arena_start, *arena_used;
+	uintptr n, i, end_b;
+	void *obj;
+
+	// TODO(atom): to be expanded in a next CL
+	struct Frame {uintptr count, b; uintptr *loop_or_ret;};
+	struct Frame stack_top;
+
+	uintptr *pc;
+
+	struct BufferList *scanbuffers;
+	struct PtrTarget *ptrbuf, *ptrbuf_end;
+	struct BitTarget *bitbuf;
+
+	struct PtrTarget *ptrbufpos;
+
+	// End of local variable declarations.
+
+	if(sizeof(Workbuf) % PageSize != 0)
+		runtime_throw("scanblock: size of Workbuf is suboptimal");
+
+	// Memory arena parameters.
+	arena_start = runtime_mheap.arena_start;
+	arena_used = runtime_mheap.arena_used;
+
+	// Allocate ptrbuf, bitbuf
+	{
+		runtime_lock(&lock);
+
+		if(bufferList == nil) {
+			bufferList = runtime_SysAlloc(sizeof(*bufferList));
+			bufferList->next = nil;
+		}
+		scanbuffers = bufferList;
+		bufferList = bufferList->next;
+
+		ptrbuf = &scanbuffers->ptrtarget[0];
+		ptrbuf_end = &scanbuffers->ptrtarget[0] + nelem(scanbuffers->ptrtarget);
+		bitbuf = &scanbuffers->bittarget[0];
+
+		runtime_unlock(&lock);
+	}
+
+	ptrbufpos = ptrbuf;
+
+	goto next_block;
 
+	for(;;) {
+		// Each iteration scans the block b of length n, queueing pointers in
+		// the work buffer.
+		if(Debug > 1) {
+			runtime_printf("scanblock %p %D\n", b, (int64)n);
+		}
+
+		// TODO(atom): to be replaced in a next CL
+		pc = defaultProg;
+
+		pc++;
+		stack_top.b = (uintptr)b;
+
+		end_b = (uintptr)b + n - PtrSize;
+
+	next_instr:
+		// TODO(atom): to be expanded in a next CL
+		switch(pc[0]) {
+		case GC_DEFAULT_PTR:
+			while(true) {
+				i = stack_top.b;
+				if(i > end_b)
+					goto next_block;
+				stack_top.b += PtrSize;
+
+				obj = *(byte**)i;
+				if((byte*)obj >= arena_start && (byte*)obj < arena_used) {
+					*ptrbufpos = (struct PtrTarget){obj, 0};
+					ptrbufpos++;
+					if(ptrbufpos == ptrbuf_end)
+						goto flush_buffers;
+				}
+			}
+
+		default:
+			runtime_throw("scanblock: invalid GC instruction");
+			return;
+		}
+
+	flush_buffers:
+		flushptrbuf(ptrbuf, ptrbufpos-ptrbuf, &wp, &wbuf, &nobj, bitbuf);
+		ptrbufpos = ptrbuf;
+		goto next_instr;
+
+	next_block:
 		// Done scanning [b, b+n).  Prepare for the next iteration of
-		// the loop by setting b and n to the parameters for the next block.
+		// the loop by setting b, n to the parameters for the next block.
 
-		// Fetch b from the work buffer.
 		if(nobj == 0) {
-			if(!keepworking) {
-				if(wbuf)
-					putempty(wbuf);
-				return;
+			flushptrbuf(ptrbuf, ptrbufpos-ptrbuf, &wp, &wbuf, &nobj, bitbuf);
+			ptrbufpos = ptrbuf;
+
+			if(nobj == 0) {
+				if(!keepworking) {
+					if(wbuf)
+						putempty(wbuf);
+					goto endscan;
+				}
+				// Emptied our buffer: refill.
+				wbuf = getfull(wbuf);
+				if(wbuf == nil)
+					goto endscan;
+				nobj = wbuf->nobj;
+				wp = wbuf->obj + wbuf->nobj;
 			}
-			// Emptied our buffer: refill.
-			wbuf = getfull(wbuf);
-			if(wbuf == nil)
-				return;
-			nobj = wbuf->nobj;
-			wp = (void**)(wbuf->obj + wbuf->nobj);
 		}
-		b = *--wp;
-		nobj--;
 
-		// Ask span about size class.
-		// (Manually inlined copy of MHeap_Lookup.)
-		x = (uintptr)b>>PageShift;
-		if(sizeof(void*) == 8)
-			x -= (uintptr)arena_start>>PageShift;
-		s = runtime_mheap.map[x];
-		if(s->sizeclass == 0)
-			n = s->npages<<PageShift;
-		else
-			n = runtime_class_to_size[s->sizeclass];
+		// Fetch b from the work buffer.
+		--wp;
+		b = wp->p;
+		n = wp->n;
+		nobj--;
 	}
+
+endscan:
+	runtime_lock(&lock);
+	scanbuffers->next = bufferList;
+	bufferList = scanbuffers;
+	runtime_unlock(&lock);
 }
 
 // debug_scanblock is the debug copy of scanblock.
@@ -386,13 +555,12 @@ debug_scanblock(byte *b, uintptr n)
 			continue;
 
 		p =  (byte*)((uintptr)s->start<<PageShift);
+		size = s->elemsize;
 		if(s->sizeclass == 0) {
 			obj = p;
-			size = (uintptr)s->npages<<PageShift;
 		} else {
 			if((byte*)obj >= (byte*)s->limit)
 				continue;
-			size = runtime_class_to_size[s->sizeclass];
 			int32 i = ((byte*)obj - p)/size;
 			obj = p+i*size;
 		}
@@ -421,11 +589,74 @@ debug_scanblock(byte *b, uintptr n)
 	}
 }
 
+// Append obj to the work buffer.
+// _wbuf, _wp, _nobj are input/output parameters and are specifying the work buffer.
+static void
+enqueue(Obj obj, Workbuf **_wbuf, Obj **_wp, uintptr *_nobj)
+{
+	uintptr nobj, off;
+	Obj *wp;
+	Workbuf *wbuf;
+
+	if(Debug > 1)
+		runtime_printf("append obj(%p %D %p)\n", obj.p, (int64)obj.n, obj.ti);
+
+	// Align obj.b to a word boundary.
+	off = (uintptr)obj.p & (PtrSize-1);
+	if(off != 0) {
+		obj.p += PtrSize - off;
+		obj.n -= PtrSize - off;
+		obj.ti = 0;
+	}
+
+	if(obj.p == nil || obj.n == 0)
+		return;
+
+	// Load work buffer state
+	wp = *_wp;
+	wbuf = *_wbuf;
+	nobj = *_nobj;
+
+	// If another proc wants a pointer, give it some.
+	if(work.nwait > 0 && nobj > handoffThreshold && work.full == 0) {
+		wbuf->nobj = nobj;
+		wbuf = handoff(wbuf);
+		nobj = wbuf->nobj;
+		wp = wbuf->obj + nobj;
+	}
+
+	// If buffer is full, get a new one.
+	if(wbuf == nil || nobj >= nelem(wbuf->obj)) {
+		if(wbuf != nil)
+			wbuf->nobj = nobj;
+		wbuf = getempty(wbuf);
+		wp = wbuf->obj;
+		nobj = 0;
+	}
+
+	*wp = obj;
+	wp++;
+	nobj++;
+
+	// Save work buffer state
+	*_wp = wp;
+	*_wbuf = wbuf;
+	*_nobj = nobj;
+}
+
 static void
 markroot(ParFor *desc, uint32 i)
 {
+	Obj *wp;
+	Workbuf *wbuf;
+	uintptr nobj;
+
 	USED(&desc);
-	scanblock(work.roots[i].p, work.roots[i].n);
+	wp = nil;
+	wbuf = nil;
+	nobj = 0;
+	enqueue(work.roots[i], &wbuf, &wp, &nobj);
+	scanblock(wbuf, wp, nobj, false);
 }
 
 // Get an empty work buffer off the work.empty list,
@@ -520,25 +751,24 @@ handoff(Workbuf *b)
 }
 
 static void
-addroot(byte *p, uintptr n)
+addroot(Obj obj)
 {
 	uint32 cap;
-	GcRoot *new;
+	Obj *new;
 
 	if(work.nroot >= work.rootcap) {
-		cap = PageSize/sizeof(GcRoot);
+		cap = PageSize/sizeof(Obj);
 		if(cap < 2*work.rootcap)
 			cap = 2*work.rootcap;
-		new = (GcRoot*)runtime_SysAlloc(cap*sizeof(GcRoot));
+		new = (Obj*)runtime_SysAlloc(cap*sizeof(Obj));
 		if(work.roots != nil) {
-			runtime_memmove(new, work.roots, work.rootcap*sizeof(GcRoot));
-			runtime_SysFree(work.roots, work.rootcap*sizeof(GcRoot));
+			runtime_memmove(new, work.roots, work.rootcap*sizeof(Obj));
+			runtime_SysFree(work.roots, work.rootcap*sizeof(Obj));
 		}
 		work.roots = new;
 		work.rootcap = cap;
 	}
-	work.roots[work.nroot].p = p;
-	work.roots[work.nroot].n = n;
+	work.roots[work.nroot] = obj;
 	work.nroot++;
 }
 
@@ -582,11 +812,11 @@ addstackroots(G *gp)
 		}
 	}
 	if(sp != nil) {
-		addroot(sp, spsize);
+		addroot((Obj){sp, spsize, 0});
 		while((sp = __splitstack_find(next_segment, next_sp,
 					      &spsize, &next_segment,
 					      &next_sp, &initial_sp)) != nil)
-			addroot(sp, spsize);
+			addroot((Obj){sp, spsize, 0});
 	}
 #else
 	M *mp;
@@ -608,9 +838,9 @@ addstackroots(G *gp)
 	}
 	top = (byte*)gp->gcinitial_sp + gp->gcstack_size;
 	if(top > bottom)
-		addroot(bottom, top - bottom);
+		addroot((Obj){bottom, top - bottom, 0});
 	else
-		addroot(top, bottom - top);
+		addroot((Obj){top, bottom - top, 0});
 #endif
 }
 
@@ -624,7 +854,7 @@ addfinroots(void *v)
 		runtime_throw("mark - finalizer inconsistency");
 
 	// do not mark the finalizer block itself.  just mark the things it points at.
-	addroot(v, size);
+	addroot((Obj){v, size, 0});
 }
 
 static struct root_list* roots;
@@ -656,15 +886,15 @@ addroots(void)
 			void *decl = pr->decl;
 			if(decl == nil)
 				break;
-			addroot(decl, pr->size);
+			addroot((Obj){decl, pr->size, 0});
 			pr++;
 		}
 	}
 
-	addroot((byte*)&runtime_m0, sizeof runtime_m0);
-	addroot((byte*)&runtime_g0, sizeof runtime_g0);
-	addroot((byte*)&runtime_allg, sizeof runtime_allg);
-	addroot((byte*)&runtime_allm, sizeof runtime_allm);
+	addroot((Obj){(byte*)&runtime_m0, sizeof runtime_m0, 0});
+	addroot((Obj){(byte*)&runtime_g0, sizeof runtime_g0, 0});
+	addroot((Obj){(byte*)&runtime_allg, sizeof runtime_allg, 0});
+	addroot((Obj){(byte*)&runtime_allm, sizeof runtime_allm, 0});
 	runtime_MProf_Mark(addroot);
 	runtime_time_scan(addroot);
 	runtime_trampoline_scan(addroot);
@@ -680,12 +910,14 @@ addroots(void)
 				break;
 			case MTypes_Words:
 			case MTypes_Bytes:
-				addroot((byte*)&s->types.data, sizeof(void*));
+				// TODO(atom): consider using defaultProg instead of 0
+				addroot((Obj){(byte*)&s->types.data, sizeof(void*), 0});
 				break;
 			}
 		}
 	}
 
+	// stacks
 	for(gp=runtime_allg; gp!=nil; gp=gp->alllink) {
 		switch(gp->status){
 		default:
@@ -709,9 +941,9 @@ addroots(void)
 	runtime_walkfintab(addfinroots, addroot);
 
 	for(fb=allfin; fb; fb=fb->alllink)
-		addroot((byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]));
+		addroot((Obj){(byte*)fb->fin, fb->cnt*sizeof(fb->fin[0]), 0});
 
-	addroot((byte*)&work, sizeof work);
+	addroot((Obj){(byte*)&work, sizeof work, 0});
 }
 
 static bool
@@ -955,8 +1187,9 @@ runtime_gchelper(void)
 {
 	// parallel mark for over gc roots
 	runtime_parfordo(work.markfor);
+
 	// help other threads scan secondary blocks
-	scanblock(nil, 0);
+	scanblock(nil, nil, 0, true);
 
 	if(DebugMark) {
 		// wait while the main thread executes mark(debug_scanblock)
@@ -983,16 +1216,16 @@ static int32 gcpercent = -2;
 static void
 stealcache(void)
 {
-	M *m;
+	M *mp;
 
-	for(m=runtime_allm; m; m=m->alllink)
-		runtime_MCache_ReleaseAll(m->mcache);
+	for(mp=runtime_allm; mp; mp=mp->alllink)
+		runtime_MCache_ReleaseAll(mp->mcache);
 }
 
 static void
 cachestats(GCStats *stats)
 {
-	M *m;
+	M *mp;
 	MCache *c;
 	uint32 i;
 	uint64 stacks_inuse;
@@ -1003,17 +1236,17 @@ cachestats(GCStats *stats)
 		runtime_memclr((byte*)stats, sizeof(*stats));
 	stacks_inuse = 0;
 	stacks_sys = runtime_stacks_sys;
-	for(m=runtime_allm; m; m=m->alllink) {
-		c = m->mcache;
+	for(mp=runtime_allm; mp; mp=mp->alllink) {
+		c = mp->mcache;
 		runtime_purgecachedstats(c);
-		// stacks_inuse += m->stackalloc->inuse;
-		// stacks_sys += m->stackalloc->sys;
+		// stacks_inuse += mp->stackalloc->inuse;
+		// stacks_sys += mp->stackalloc->sys;
 		if(stats) {
-			src = (uint64*)&m->gcstats;
+			src = (uint64*)&mp->gcstats;
 			dst = (uint64*)stats;
 			for(i=0; i<sizeof(*stats)/sizeof(uint64); i++)
 				dst[i] += src[i];
-			runtime_memclr((byte*)&m->gcstats, sizeof(m->gcstats));
+			runtime_memclr((byte*)&mp->gcstats, sizeof(mp->gcstats));
 		}
 		for(i=0; i<nelem(c->local_by_size); i++) {
 			mstats.by_size[i].nmalloc += c->local_by_size[i].nmalloc;
@@ -1100,7 +1333,7 @@ gc(struct gc_args *args)
 	int64 t0, t1, t2, t3;
 	uint64 heap0, heap1, obj0, obj1;
 	GCStats stats;
-	M *m1;
+	M *mp;
 	uint32 i;
 
 	runtime_semacquire(&runtime_worldsema);
@@ -1116,8 +1349,8 @@ gc(struct gc_args *args)
 	m->gcing = 1;
 	runtime_stoptheworld();
 
-	for(m1=runtime_allm; m1; m1=m1->alllink)
-		runtime_settype_flush(m1, false);
+	for(mp=runtime_allm; mp; mp=mp->alllink)
+		runtime_settype_flush(mp, false);
 
 	heap0 = 0;
 	obj0 = 0;
@@ -1127,26 +1360,27 @@ gc(struct gc_args *args)
 		obj0 = mstats.nmalloc - mstats.nfree;
 	}
 
+	m->locks++;	// disable gc during mallocs in parforalloc
+	if(work.markfor == nil)
+		work.markfor = runtime_parforalloc(MaxGcproc);
+	if(work.sweepfor == nil)
+		work.sweepfor = runtime_parforalloc(MaxGcproc);
+	m->locks--;
+
 	work.nwait = 0;
 	work.ndone = 0;
 	work.debugmarkdone = 0;
 	work.nproc = runtime_gcprocs();
 	addroots();
-	m->locks++;	// disable gc during mallocs in parforalloc
-	if(work.markfor == nil)
-		work.markfor = runtime_parforalloc(MaxGcproc);
 	runtime_parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot);
-	if(work.sweepfor == nil)
-		work.sweepfor = runtime_parforalloc(MaxGcproc);
 	runtime_parforsetup(work.sweepfor, work.nproc, runtime_mheap.nspan, nil, true, sweepspan);
-	m->locks--;
 	if(work.nproc > 1) {
 		runtime_noteclear(&work.alldone);
 		runtime_helpgc(work.nproc);
 	}
 
 	runtime_parfordo(work.markfor);
-	scanblock(nil, 0);
+	scanblock(nil, nil, 0, true);
 
 	if(DebugMark) {
 		for(i=0; i<work.nroot; i++)
diff --git a/libgo/runtime/mgc0.h b/libgo/runtime/mgc0.h
new file mode 100644
index 0000000..a2798ef
--- /dev/null
+++ b/libgo/runtime/mgc0.h
@@ -0,0 +1,42 @@
+// 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)
+
+// GC instruction opcodes.
+//
+// The opcode of an instruction is followed by zero or more
+// arguments to the instruction.
+//
+// Meaning of arguments:
+//   off      Offset (in bytes) from the start of the current object
+//   objgc    Pointer to GC info of an object
+//   len      Length of an array
+//   elemsize Size (in bytes) of an element
+//   size     Size (in bytes)
+enum {
+	GC_END,         // End of object, loop or subroutine. Args: none
+	GC_PTR,         // A typed pointer. Args: (off, objgc)
+	GC_APTR,        // Pointer to an arbitrary object. Args: (off)
+	GC_ARRAY_START, // Start an array with a fixed length. Args: (off, len, elemsize)
+	GC_ARRAY_NEXT,  // The next element of an array. Args: none
+	GC_CALL,        // Call a subroutine. Args: (off, objgc)
+	GC_MAP_PTR,     // Go map. Args: (off, MapType*)
+	GC_STRING,      // Go string. Args: (off)
+	GC_EFACE,       // interface{}. Args: (off)
+	GC_IFACE,       // interface{...}. Args: (off)
+	GC_SLICE,       // Go slice. Args: (off, objgc)
+	GC_REGION,      // A region/part of the current object. Args: (off, size, objgc)
+
+	GC_NUM_INSTR,   // Number of instruction opcodes
+};
+
+enum {
+	// Size of GC's fixed stack.
+	//
+	// The current GC implementation permits:
+	//  - at most 1 stack allocation because of GC_CALL
+	//  - at most GC_STACK_CAPACITY allocations because of GC_ARRAY_START
+	GC_STACK_CAPACITY = 8,	
+};
diff --git a/libgo/runtime/mprof.goc b/libgo/runtime/mprof.goc
index a92ef40..8b3a195 100644
--- a/libgo/runtime/mprof.goc
+++ b/libgo/runtime/mprof.goc
@@ -362,13 +362,13 @@ func MemProfile(p Slice, include_inuse_zero bool) (n int, ok bool) {
 }
 
 void
-runtime_MProf_Mark(void (*addroot)(byte *, uintptr))
+runtime_MProf_Mark(void (*addroot)(Obj))
 {
 	// buckhash is not allocated via mallocgc.
-	addroot((byte*)&mbuckets, sizeof mbuckets);
-	addroot((byte*)&bbuckets, sizeof bbuckets);
-	addroot((byte*)&addrhash, sizeof addrhash);
-	addroot((byte*)&addrfree, sizeof addrfree);
+	addroot((Obj){(byte*)&mbuckets, sizeof mbuckets, 0});
+	addroot((Obj){(byte*)&bbuckets, sizeof bbuckets, 0});
+	addroot((Obj){(byte*)&addrhash, sizeof addrhash, 0});
+	addroot((Obj){(byte*)&addrfree, sizeof addrfree, 0});
 }
 
 // Must match BlockProfileRecord in debug.go.
@@ -412,18 +412,18 @@ struct TRecord {
 
 func ThreadCreateProfile(p Slice) (n int, ok bool) {
 	TRecord *r;
-	M *first, *m;
+	M *first, *mp;
 	
 	first = runtime_atomicloadp(&runtime_allm);
 	n = 0;
-	for(m=first; m; m=m->alllink)
+	for(mp=first; mp; mp=mp->alllink)
 		n++;
 	ok = false;
 	if(n <= p.__count) {
 		ok = true;
 		r = (TRecord*)p.__values;
-		for(m=first; m; m=m->alllink) {
-			runtime_memmove(r->stk, m->createstack, sizeof r->stk);
+		for(mp=first; mp; mp=mp->alllink) {
+			runtime_memmove(r->stk, mp->createstack, sizeof r->stk);
 			r++;
 		}
 	}
@@ -471,11 +471,11 @@ func Stack(b Slice, all bool) (n int) {
 }
 
 static void
-saveg(G *g, TRecord *r)
+saveg(G *gp, TRecord *r)
 {
 	int32 n;
 
-	if(g == runtime_g())
+	if(gp == runtime_g())
 		n = runtime_callers(0, r->stk, nelem(r->stk));
 	else {
 		// FIXME: Not implemented.
diff --git a/libgo/runtime/proc.c b/libgo/runtime/proc.c
index d90bb2c..9b229d6 100644
--- a/libgo/runtime/proc.c
+++ b/libgo/runtime/proc.c
@@ -555,13 +555,13 @@ schedlock(void)
 static void
 schedunlock(void)
 {
-	M *m;
+	M *mp;
 
-	m = mwakeup;
+	mp = mwakeup;
 	mwakeup = nil;
 	runtime_unlock(&runtime_sched);
-	if(m != nil)
-		runtime_notewakeup(&m->havenextg);
+	if(mp != nil)
+		runtime_notewakeup(&mp->havenextg);
 }
 
 void
diff --git a/libgo/runtime/runtime.c b/libgo/runtime/runtime.c
index 211edc0..ecd804d 100644
--- a/libgo/runtime/runtime.c
+++ b/libgo/runtime/runtime.c
@@ -79,33 +79,6 @@ runtime_goenvs_unix(void)
 	syscall_Envs.__capacity = n;
 }
 
-const byte*
-runtime_getenv(const char *s)
-{
-	int32 i, j, len;
-	const byte *v, *bs;
-	String* envv;
-	int32 envc;
-
-	bs = (const byte*)s;
-	len = runtime_findnull(bs);
-	envv = (String*)syscall_Envs.__values;
-	envc = syscall_Envs.__count;
-	for(i=0; i<envc; i++){
-		if(envv[i].len <= len)
-			continue;
-		v = (const byte*)envv[i].str;
-		for(j=0; j<len; j++)
-			if(bs[j] != v[j])
-				goto nomatch;
-		if(v[len] != '=')
-			goto nomatch;
-		return v+len+1;
-	nomatch:;
-	}
-	return nil;
-}
-
 int32
 runtime_atoi(const byte *p)
 {
diff --git a/libgo/runtime/runtime.h b/libgo/runtime/runtime.h
index 977ae49..c5cd3a0 100644
--- a/libgo/runtime/runtime.h
+++ b/libgo/runtime/runtime.h
@@ -599,9 +599,6 @@ enum
 	UseSpanType = 1,
 };
 
-void	runtime_time_scan(void (*)(byte*, uintptr));
-void	runtime_trampoline_scan(void (*)(byte *, uintptr));
-
 void	runtime_setsig(int32, bool, bool);
 #define runtime_setitimer setitimer
 
diff --git a/libgo/runtime/time.goc b/libgo/runtime/time.goc
index 5077b71..d497361 100644
--- a/libgo/runtime/time.goc
+++ b/libgo/runtime/time.goc
@@ -255,7 +255,7 @@ siftdown(int32 i)
 }
 
 void
-runtime_time_scan(void (*addroot)(byte*, uintptr))
+runtime_time_scan(void (*addroot)(Obj))
 {
-	addroot((byte*)&timers, sizeof timers);
+	addroot((Obj){(byte*)&timers, sizeof timers, 0});
 }