summaryrefslogtreecommitdiff
path: root/src/pkg/runtime/mprof.goc
diff options
context:
space:
mode:
authorOndřej Surý <ondrej@sury.org>2011-09-13 13:13:40 +0200
committerOndřej Surý <ondrej@sury.org>2011-09-13 13:13:40 +0200
commit5ff4c17907d5b19510a62e08fd8d3b11e62b431d (patch)
treec0650497e988f47be9c6f2324fa692a52dea82e1 /src/pkg/runtime/mprof.goc
parent80f18fc933cf3f3e829c5455a1023d69f7b86e52 (diff)
downloadgolang-upstream/60.tar.gz
Imported Upstream version 60upstream/60
Diffstat (limited to 'src/pkg/runtime/mprof.goc')
-rw-r--r--src/pkg/runtime/mprof.goc274
1 files changed, 274 insertions, 0 deletions
diff --git a/src/pkg/runtime/mprof.goc b/src/pkg/runtime/mprof.goc
new file mode 100644
index 000000000..517f96a31
--- /dev/null
+++ b/src/pkg/runtime/mprof.goc
@@ -0,0 +1,274 @@
+// 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 "malloc.h"
+#include "defs.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 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)
+{
+ 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;
+
+ 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;
+}
+
+// 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);
+ b->allocs++;
+ b->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->frees++;
+ b->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 extern.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);
+}