src/pkg/runtime/mprof.goc - go - Git at Google

 // Copyright 2009 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.

 // Malloc profiling.
 // Patterned after tcmalloc's algorithms; shorter code.

 package runtime
 #include "runtime.h"
 #include "arch_GOARCH.h"
 #include "malloc.h"
 #include "defs_GOOS_GOARCH.h"
 #include "type.h"

 // NOTE(rsc): Everything here could use cas if contention became an issue.
 static Lock proflock;

 // Per-call-stack allocation information.
 // Lookup by hashing call stack into a linked-list hash table.
 typedef struct Bucket Bucket;
 struct Bucket
 {
 	Bucket	*next;	// next in hash list
 	Bucket	*allnext;	// next in list of all buckets
 	uintptr	allocs;
 	uintptr	frees;
 	uintptr	alloc_bytes;
 	uintptr	free_bytes;
 	uintptr	recent_allocs;  // since last gc
 	uintptr	recent_frees;
 	uintptr	recent_alloc_bytes;
 	uintptr	recent_free_bytes;
 	uintptr	hash;
 	uintptr	nstk;
 	uintptr	stk[1];
 };
 enum {
 	BuckHashSize = 179999,
 };
 static Bucket **buckhash;
 static Bucket *buckets;
 static uintptr bucketmem;

 // Return the bucket for stk[0:nstk], allocating new bucket if needed.
 static Bucket*
 stkbucket(uintptr *stk, int32 nstk, bool alloc)
 {
 	int32 i;
 	uintptr h;
 	Bucket *b;

 	if(buckhash == nil) {
 		buckhash = runtime·SysAlloc(BuckHashSize*sizeof buckhash[0]);
 		mstats.buckhash_sys += BuckHashSize*sizeof buckhash[0];
 	}

 	// Hash stack.
 	h = 0;
 	for(i=0; i<nstk; i++) {
 		h += stk[i];
 		h += h<<10;
 		h ^= h>>6;
 	}
 	h += h<<3;
 	h ^= h>>11;

 	i = h%BuckHashSize;
 	for(b = buckhash[i]; b; b=b->next)
 		if(b->hash == h && b->nstk == nstk &&
 		   runtime·mcmp((byte*)b->stk, (byte*)stk, nstk*sizeof stk[0]) == 0)
 			return b;

 	if(!alloc)
 		return nil;

 	b = runtime·mallocgc(sizeof *b + nstk*sizeof stk[0], FlagNoProfiling, 0, 1);
 	bucketmem += sizeof *b + nstk*sizeof stk[0];
 	runtime·memmove(b->stk, stk, nstk*sizeof stk[0]);
 	b->hash = h;
 	b->nstk = nstk;
 	b->next = buckhash[i];
 	buckhash[i] = b;
 	b->allnext = buckets;
 	buckets = b;
 	return b;
 }

 // Record that a gc just happened: all the 'recent' statistics are now real.
 void
 runtime·MProf_GC(void)
 {
 	Bucket *b;

 	runtime·lock(&proflock);
 	for(b=buckets; b; b=b->allnext) {
 		b->allocs += b->recent_allocs;
 		b->frees += b->recent_frees;
 		b->alloc_bytes += b->recent_alloc_bytes;
 		b->free_bytes += b->recent_free_bytes;
 		b->recent_allocs = 0;
 		b->recent_frees = 0;
 		b->recent_alloc_bytes = 0;
 		b->recent_free_bytes = 0;
 	}
 	runtime·unlock(&proflock);
 }

 // Map from pointer to Bucket* that allocated it.
 // Three levels:
 //	Linked-list hash table for top N-20 bits.
 //	Array index for next 13 bits.
 //	Linked list for next 7 bits.
 // This is more efficient than using a general map,
 // because of the typical clustering of the pointer keys.

 typedef struct AddrHash AddrHash;
 typedef struct AddrEntry AddrEntry;

 struct AddrHash
 {
 	AddrHash *next;	// next in top-level hash table linked list
 	uintptr addr;	// addr>>20
 	AddrEntry *dense[1<<13];
 };

 struct AddrEntry
 {
 	AddrEntry *next;	// next in bottom-level linked list
 	uint32 addr;
 	Bucket *b;
 };

 enum {
 	AddrHashBits = 12	// 1MB per entry, so good for 4GB of used address space
 };
 static AddrHash *addrhash[1<<AddrHashBits];
 static AddrEntry *addrfree;
 static uintptr addrmem;

 // Multiplicative hash function:
 // hashMultiplier is the bottom 32 bits of int((sqrt(5)-1)/2 * (1<<32)).
 // This is a good multiplier as suggested in CLR, Knuth.  The hash
 // value is taken to be the top AddrHashBits bits of the bottom 32 bits
 // of the multiplied value.
 enum {
 	HashMultiplier = 2654435769U
 };

 // Set the bucket associated with addr to b.
 static void
 setaddrbucket(uintptr addr, Bucket *b)
 {
 	int32 i;
 	uint32 h;
 	AddrHash *ah;
 	AddrEntry *e;

 	h = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);
 	for(ah=addrhash[h]; ah; ah=ah->next)
 		if(ah->addr == (addr>>20))
 			goto found;

 	ah = runtime·mallocgc(sizeof *ah, FlagNoProfiling, 0, 1);
 	addrmem += sizeof *ah;
 	ah->next = addrhash[h];
 	ah->addr = addr>>20;
 	addrhash[h] = ah;

 found:
 	if((e = addrfree) == nil) {
 		e = runtime·mallocgc(64*sizeof *e, FlagNoProfiling, 0, 0);
 		addrmem += 64*sizeof *e;
 		for(i=0; i+1<64; i++)
 			e[i].next = &e[i+1];
 		e[63].next = nil;
 	}
 	addrfree = e->next;
 	e->addr = (uint32)~(addr & ((1<<20)-1));
 	e->b = b;
 	h = (addr>>7)&(nelem(ah->dense)-1);	// entry in dense is top 13 bits of low 20.
 	e->next = ah->dense[h];
 	ah->dense[h] = e;
 }

 // Get the bucket associated with addr and clear the association.
 static Bucket*
 getaddrbucket(uintptr addr)
 {
 	uint32 h;
 	AddrHash *ah;
 	AddrEntry *e, **l;
 	Bucket *b;

 	h = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);
 	for(ah=addrhash[h]; ah; ah=ah->next)
 		if(ah->addr == (addr>>20))
 			goto found;
 	return nil;

 found:
 	h = (addr>>7)&(nelem(ah->dense)-1);	// entry in dense is top 13 bits of low 20.
 	for(l=&ah->dense[h]; (e=*l) != nil; l=&e->next) {
 		if(e->addr == (uint32)~(addr & ((1<<20)-1))) {
 			*l = e->next;
 			b = e->b;
 			e->next = addrfree;
 			addrfree = e;
 			return b;
 		}
 	}
 	return nil;
 }

 // Called by malloc to record a profiled block.
 void
 runtime·MProf_Malloc(void *p, uintptr size)
 {
 	int32 nstk;
 	uintptr stk[32];
 	Bucket *b;

 	if(m->nomemprof > 0)
 		return;

 	m->nomemprof++;
 	nstk = runtime·callers(1, stk, 32);
 	runtime·lock(&proflock);
 	b = stkbucket(stk, nstk, true);
 	b->recent_allocs++;
 	b->recent_alloc_bytes += size;
 	setaddrbucket((uintptr)p, b);
 	runtime·unlock(&proflock);
 	m->nomemprof--;
 }

 // Called when freeing a profiled block.
 void
 runtime·MProf_Free(void *p, uintptr size)
 {
 	Bucket *b;

 	if(m->nomemprof > 0)
 		return;

 	m->nomemprof++;
 	runtime·lock(&proflock);
 	b = getaddrbucket((uintptr)p);
 	if(b != nil) {
 		b->recent_frees++;
 		b->recent_free_bytes += size;
 	}
 	runtime·unlock(&proflock);
 	m->nomemprof--;
 }


 // Go interface to profile data.  (Declared in extern.go)
 // Assumes Go sizeof(int) == sizeof(int32)

 // Must match MemProfileRecord in debug.go.
 typedef struct Record Record;
 struct Record {
 	int64 alloc_bytes, free_bytes;
 	int64 alloc_objects, free_objects;
 	uintptr stk[32];
 };

 // Write b's data to r.
 static void
 record(Record *r, Bucket *b)
 {
 	int32 i;

 	r->alloc_bytes = b->alloc_bytes;
 	r->free_bytes = b->free_bytes;
 	r->alloc_objects = b->allocs;
 	r->free_objects = b->frees;
 	for(i=0; i<b->nstk && i<nelem(r->stk); i++)
 		r->stk[i] = b->stk[i];
 	for(; i<nelem(r->stk); i++)
 		r->stk[i] = 0;
 }

 func MemProfile(p Slice, include_inuse_zero bool) (n int32, ok bool) {
 	Bucket *b;
 	Record *r;

 	runtime·lock(&proflock);
 	n = 0;
 	for(b=buckets; b; b=b->allnext)
 		if(include_inuse_zero || b->alloc_bytes != b->free_bytes)
 			n++;
 	ok = false;
 	if(n <= p.len) {
 		ok = true;
 		r = (Record*)p.array;
 		for(b=buckets; b; b=b->allnext)
 			if(include_inuse_zero || b->alloc_bytes != b->free_bytes)
 				record(r++, b);
 	}
 	runtime·unlock(&proflock);
 }

 // Must match StackRecord in debug.go.
 typedef struct TRecord TRecord;
 struct TRecord {
 	uintptr stk[32];
 };

 func ThreadCreateProfile(p Slice) (n int32, ok bool) {
 	TRecord *r;
 	M *first, *m;

 	first = runtime·atomicloadp(&runtime·allm);
 	n = 0;
 	for(m=first; m; m=m->alllink)
 		n++;
 	ok = false;
 	if(n <= p.len) {
 		ok = true;
 		r = (TRecord*)p.array;
 		for(m=first; m; m=m->alllink) {
 			runtime·memmove(r->stk, m->createstack, sizeof r->stk);
 			r++;
 		}
 	}
 }

 func Stack(b Slice, all bool) (n int32) {
 	byte *pc, *sp;

 	sp = runtime·getcallersp(&b);
 	pc = runtime·getcallerpc(&b);

 	if(all) {
 		runtime·semacquire(&runtime·worldsema);
 		m->gcing = 1;
 		runtime·stoptheworld();
 	}

 	if(b.len == 0)
 		n = 0;
 	else{
 		g->writebuf = (byte*)b.array;
 		g->writenbuf = b.len;
 		runtime·goroutineheader(g);
 		runtime·traceback(pc, sp, 0, g);
 		if(all)
 			runtime·tracebackothers(g);
 		n = b.len - g->writenbuf;
 		g->writebuf = nil;
 		g->writenbuf = 0;
 	}

 	if(all) {
 		m->gcing = 0;
 		runtime·semrelease(&runtime·worldsema);
 		runtime·starttheworld(false);
 	}
 }

 static void
 saveg(byte *pc, byte *sp, G *g, TRecord *r)
 {
 	int32 n;

 	n = runtime·gentraceback(pc, sp, 0, g, 0, r->stk, nelem(r->stk));
 	if(n < nelem(r->stk))
 		r->stk[n] = 0;
 }

 func GoroutineProfile(b Slice) (n int32, ok bool) {
 	byte *pc, *sp;
 	TRecord *r;
 	G *gp;

 	sp = runtime·getcallersp(&b);
 	pc = runtime·getcallerpc(&b);

 	ok = false;
 	n = runtime·gcount();
 	if(n <= b.len) {
 		runtime·semacquire(&runtime·worldsema);
 		m->gcing = 1;
 		runtime·stoptheworld();

 		n = runtime·gcount();
 		if(n <= b.len) {
 			ok = true;
 			r = (TRecord*)b.array;
 			saveg(pc, sp, g, r++);
 			for(gp = runtime·allg; gp != nil; gp = gp->alllink) {
 				if(gp == g || gp->status == Gdead)
 					continue;
 				saveg(gp->sched.pc, gp->sched.sp, gp, r++);
 			}
 		}

 		m->gcing = 0;
 		runtime·semrelease(&runtime·worldsema);
 		runtime·starttheworld(false);
 	}
 }
	// Copyright 2009 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.

	// Malloc profiling.
	// Patterned after tcmalloc's algorithms; shorter code.

	package runtime
	#include "runtime.h"
	#include "arch_GOARCH.h"
	#include "malloc.h"
	#include "defs_GOOS_GOARCH.h"
	#include "type.h"

	// NOTE(rsc): Everything here could use cas if contention became an issue.
	static Lock proflock;

	// Per-call-stack allocation information.
	// Lookup by hashing call stack into a linked-list hash table.
	typedef struct Bucket Bucket;
	struct Bucket
	{
	Bucket *next; // next in hash list
	Bucket *allnext; // next in list of all buckets
	uintptr allocs;
	uintptr frees;
	uintptr alloc_bytes;
	uintptr free_bytes;
	uintptr recent_allocs; // since last gc
	uintptr recent_frees;
	uintptr recent_alloc_bytes;
	uintptr recent_free_bytes;
	uintptr hash;
	uintptr nstk;
	uintptr stk[1];
	};
	enum {
	BuckHashSize = 179999,
	};
	static Bucket **buckhash;
	static Bucket *buckets;
	static uintptr bucketmem;

	// Return the bucket for stk[0:nstk], allocating new bucket if needed.
	static Bucket*
	stkbucket(uintptr *stk, int32 nstk, bool alloc)
	{
	int32 i;
	uintptr h;
	Bucket *b;

	if(buckhash == nil) {
	buckhash = runtime·SysAlloc(BuckHashSize*sizeof buckhash[0]);
	mstats.buckhash_sys += BuckHashSize*sizeof buckhash[0];
	}

	// Hash stack.
	h = 0;
	for(i=0; i<nstk; i++) {
	h += stk[i];
	h += h<<10;
	h ^= h>>6;
	}
	h += h<<3;
	h ^= h>>11;

	i = h%BuckHashSize;
	for(b = buckhash[i]; b; b=b->next)
	if(b->hash == h && b->nstk == nstk &&
	runtime·mcmp((byte)b->stk, (byte)stk, nstk*sizeof stk[0]) == 0)
	return b;

	if(!alloc)
	return nil;

	b = runtime·mallocgc(sizeof b + nstksizeof stk[0], FlagNoProfiling, 0, 1);
	bucketmem += sizeof b + nstksizeof stk[0];
	runtime·memmove(b->stk, stk, nstk*sizeof stk[0]);
	b->hash = h;
	b->nstk = nstk;
	b->next = buckhash[i];
	buckhash[i] = b;
	b->allnext = buckets;
	buckets = b;
	return b;
	}

	// Record that a gc just happened: all the 'recent' statistics are now real.
	void
	runtime·MProf_GC(void)
	{
	Bucket *b;

	runtime·lock(&proflock);
	for(b=buckets; b; b=b->allnext) {
	b->allocs += b->recent_allocs;
	b->frees += b->recent_frees;
	b->alloc_bytes += b->recent_alloc_bytes;
	b->free_bytes += b->recent_free_bytes;
	b->recent_allocs = 0;
	b->recent_frees = 0;
	b->recent_alloc_bytes = 0;
	b->recent_free_bytes = 0;
	}
	runtime·unlock(&proflock);
	}

	// Map from pointer to Bucket* that allocated it.
	// Three levels:
	// Linked-list hash table for top N-20 bits.
	// Array index for next 13 bits.
	// Linked list for next 7 bits.
	// This is more efficient than using a general map,
	// because of the typical clustering of the pointer keys.

	typedef struct AddrHash AddrHash;
	typedef struct AddrEntry AddrEntry;

	struct AddrHash
	{
	AddrHash *next; // next in top-level hash table linked list
	uintptr addr; // addr>>20
	AddrEntry *dense[1<<13];
	};

	struct AddrEntry
	{
	AddrEntry *next; // next in bottom-level linked list
	uint32 addr;
	Bucket *b;
	};

	enum {
	AddrHashBits = 12 // 1MB per entry, so good for 4GB of used address space
	};
	static AddrHash *addrhash[1<<AddrHashBits];
	static AddrEntry *addrfree;
	static uintptr addrmem;

	// Multiplicative hash function:
	// hashMultiplier is the bottom 32 bits of int((sqrt(5)-1)/2 * (1<<32)).
	// This is a good multiplier as suggested in CLR, Knuth. The hash
	// value is taken to be the top AddrHashBits bits of the bottom 32 bits
	// of the multiplied value.
	enum {
	HashMultiplier = 2654435769U
	};

	// Set the bucket associated with addr to b.
	static void
	setaddrbucket(uintptr addr, Bucket *b)
	{
	int32 i;
	uint32 h;
	AddrHash *ah;
	AddrEntry *e;

	h = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);
	for(ah=addrhash[h]; ah; ah=ah->next)
	if(ah->addr == (addr>>20))
	goto found;

	ah = runtime·mallocgc(sizeof *ah, FlagNoProfiling, 0, 1);
	addrmem += sizeof *ah;
	ah->next = addrhash[h];
	ah->addr = addr>>20;
	addrhash[h] = ah;

	found:
	if((e = addrfree) == nil) {
	e = runtime·mallocgc(64sizeof e, FlagNoProfiling, 0, 0);
	addrmem += 64sizeof e;
	for(i=0; i+1<64; i++)
	e[i].next = &e[i+1];
	e[63].next = nil;
	}
	addrfree = e->next;
	e->addr = (uint32)~(addr & ((1<<20)-1));
	e->b = b;
	h = (addr>>7)&(nelem(ah->dense)-1); // entry in dense is top 13 bits of low 20.
	e->next = ah->dense[h];
	ah->dense[h] = e;
	}

	// Get the bucket associated with addr and clear the association.
	static Bucket*
	getaddrbucket(uintptr addr)
	{
	uint32 h;
	AddrHash *ah;
	AddrEntry e, *l;
	Bucket *b;

	h = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);
	for(ah=addrhash[h]; ah; ah=ah->next)
	if(ah->addr == (addr>>20))
	goto found;
	return nil;

	found:
	h = (addr>>7)&(nelem(ah->dense)-1); // entry in dense is top 13 bits of low 20.
	for(l=&ah->dense[h]; (e=*l) != nil; l=&e->next) {
	if(e->addr == (uint32)~(addr & ((1<<20)-1))) {
	*l = e->next;
	b = e->b;
	e->next = addrfree;
	addrfree = e;
	return b;
	}
	}
	return nil;
	}

	// Called by malloc to record a profiled block.
	void
	runtime·MProf_Malloc(void *p, uintptr size)
	{
	int32 nstk;
	uintptr stk[32];
	Bucket *b;

	if(m->nomemprof > 0)
	return;

	m->nomemprof++;
	nstk = runtime·callers(1, stk, 32);
	runtime·lock(&proflock);
	b = stkbucket(stk, nstk, true);
	b->recent_allocs++;
	b->recent_alloc_bytes += size;
	setaddrbucket((uintptr)p, b);
	runtime·unlock(&proflock);
	m->nomemprof--;
	}

	// Called when freeing a profiled block.
	void
	runtime·MProf_Free(void *p, uintptr size)
	{
	Bucket *b;

	if(m->nomemprof > 0)
	return;

	m->nomemprof++;
	runtime·lock(&proflock);
	b = getaddrbucket((uintptr)p);
	if(b != nil) {
	b->recent_frees++;
	b->recent_free_bytes += size;
	}
	runtime·unlock(&proflock);
	m->nomemprof--;
	}


	// Go interface to profile data. (Declared in extern.go)
	// Assumes Go sizeof(int) == sizeof(int32)

	// Must match MemProfileRecord in debug.go.
	typedef struct Record Record;
	struct Record {
	int64 alloc_bytes, free_bytes;
	int64 alloc_objects, free_objects;
	uintptr stk[32];
	};

	// Write b's data to r.
	static void
	record(Record r, Bucket b)
	{
	int32 i;

	r->alloc_bytes = b->alloc_bytes;
	r->free_bytes = b->free_bytes;
	r->alloc_objects = b->allocs;
	r->free_objects = b->frees;
	for(i=0; i<b->nstk && i<nelem(r->stk); i++)
	r->stk[i] = b->stk[i];
	for(; i<nelem(r->stk); i++)
	r->stk[i] = 0;
	}

	func MemProfile(p Slice, include_inuse_zero bool) (n int32, ok bool) {
	Bucket *b;
	Record *r;

	runtime·lock(&proflock);
	n = 0;
	for(b=buckets; b; b=b->allnext)
	if(include_inuse_zero \|\| b->alloc_bytes != b->free_bytes)
	n++;
	ok = false;
	if(n <= p.len) {
	ok = true;
	r = (Record*)p.array;
	for(b=buckets; b; b=b->allnext)
	if(include_inuse_zero \|\| b->alloc_bytes != b->free_bytes)
	record(r++, b);
	}
	runtime·unlock(&proflock);
	}

	// Must match StackRecord in debug.go.
	typedef struct TRecord TRecord;
	struct TRecord {
	uintptr stk[32];
	};

	func ThreadCreateProfile(p Slice) (n int32, ok bool) {
	TRecord *r;
	M first, m;

	first = runtime·atomicloadp(&runtime·allm);
	n = 0;
	for(m=first; m; m=m->alllink)
	n++;
	ok = false;
	if(n <= p.len) {
	ok = true;
	r = (TRecord*)p.array;
	for(m=first; m; m=m->alllink) {
	runtime·memmove(r->stk, m->createstack, sizeof r->stk);
	r++;
	}
	}
	}

	func Stack(b Slice, all bool) (n int32) {
	byte pc, sp;

	sp = runtime·getcallersp(&b);
	pc = runtime·getcallerpc(&b);

	if(all) {
	runtime·semacquire(&runtime·worldsema);
	m->gcing = 1;
	runtime·stoptheworld();
	}

	if(b.len == 0)
	n = 0;
	else{
	g->writebuf = (byte*)b.array;
	g->writenbuf = b.len;
	runtime·goroutineheader(g);
	runtime·traceback(pc, sp, 0, g);
	if(all)
	runtime·tracebackothers(g);
	n = b.len - g->writenbuf;
	g->writebuf = nil;
	g->writenbuf = 0;
	}

	if(all) {
	m->gcing = 0;
	runtime·semrelease(&runtime·worldsema);
	runtime·starttheworld(false);
	}
	}

	static void
	saveg(byte pc, byte sp, G g, TRecord r)
	{
	int32 n;

	n = runtime·gentraceback(pc, sp, 0, g, 0, r->stk, nelem(r->stk));
	if(n < nelem(r->stk))
	r->stk[n] = 0;
	}

	func GoroutineProfile(b Slice) (n int32, ok bool) {
	byte pc, sp;
	TRecord *r;
	G *gp;

	sp = runtime·getcallersp(&b);
	pc = runtime·getcallerpc(&b);

	ok = false;
	n = runtime·gcount();
	if(n <= b.len) {
	runtime·semacquire(&runtime·worldsema);
	m->gcing = 1;
	runtime·stoptheworld();

	n = runtime·gcount();
	if(n <= b.len) {
	ok = true;
	r = (TRecord*)b.array;
	saveg(pc, sp, g, r++);
	for(gp = runtime·allg; gp != nil; gp = gp->alllink) {
	if(gp == g \|\| gp->status == Gdead)
	continue;
	saveg(gp->sched.pc, gp->sched.sp, gp, r++);
	}
	}

	m->gcing = 0;
	runtime·semrelease(&runtime·worldsema);
	runtime·starttheworld(false);
	}
	}