blob: 0bbce85836935cd6154e3068ec800edd95f771ec [file] [log] [blame]
// 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);
}
}