libgo/runtime/mprof.goc

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Malloc profiling.
   6 // Patterned after tcmalloc's algorithms; shorter code.
   7
   8 package runtime
   9 #include "runtime.h"
  10 #include "arch.h"
  11 #include "malloc.h"
  12 #include "defs.h"
  13 #include "go-type.h"
  14
  15 // NOTE(rsc): Everything here could use cas if contention became an issue.
  16 static Lock proflock;
  17
  18 // Per-call-stack allocation information.
  19 // Lookup by hashing call stack into a linked-list hash table.
  20 typedef struct Bucket Bucket;
  21 struct Bucket
  22 {
  23         Bucket  *next;  // next in hash list
  24         Bucket  *allnext;       // next in list of all buckets
  25         uintptr allocs;
  26         uintptr frees;
  27         uintptr alloc_bytes;
  28         uintptr free_bytes;
  29         uintptr hash;
  30         uintptr nstk;
  31         uintptr stk[1];
  32 };
  33 enum {
  34         BuckHashSize = 179999,
  35 };
  36 static Bucket **buckhash;
  37 static Bucket *buckets;
  38 static uintptr bucketmem;
  39
  40 // Return the bucket for stk[0:nstk], allocating new bucket if needed.
  41 static Bucket*
  42 stkbucket(uintptr *stk, int32 nstk)
  43 {
  44         int32 i;
  45         uintptr h;
  46         Bucket *b;
  47
  48         if(buckhash == nil) {
  49                 buckhash = runtime_SysAlloc(BuckHashSize*sizeof buckhash[0]);
  50                 mstats.buckhash_sys += BuckHashSize*sizeof buckhash[0];
  51         }
  52
  53         // Hash stack.
  54         h = 0;
  55         for(i=0; i<nstk; i++) {
  56                 h += stk[i];
  57                 h += h<<10;
  58                 h ^= h>>6;
  59         }
  60         h += h<<3;
  61         h ^= h>>11;
  62
  63         i = h%BuckHashSize;
  64         for(b = buckhash[i]; b; b=b->next)
  65                 if(b->hash == h && b->nstk == (uintptr)nstk &&
  66                    runtime_mcmp((byte*)b->stk, (byte*)stk, nstk*sizeof stk[0]) == 0)
  67                         return b;
  68
  69         b = runtime_mallocgc(sizeof *b + nstk*sizeof stk[0], FlagNoProfiling, 0, 1);
  70         bucketmem += sizeof *b + nstk*sizeof stk[0];
  71         runtime_memmove(b->stk, stk, nstk*sizeof stk[0]);
  72         b->hash = h;
  73         b->nstk = nstk;
  74         b->next = buckhash[i];
  75         buckhash[i] = b;
  76         b->allnext = buckets;
  77         buckets = b;
  78         return b;
  79 }
  80
  81 // Map from pointer to Bucket* that allocated it.
  82 // Three levels:
  83 //      Linked-list hash table for top N-20 bits.
  84 //      Array index for next 13 bits.
  85 //      Linked list for next 7 bits.
  86 // This is more efficient than using a general map,
  87 // because of the typical clustering of the pointer keys.
  88
  89 typedef struct AddrHash AddrHash;
  90 typedef struct AddrEntry AddrEntry;
  91
  92 struct AddrHash
  93 {
  94         AddrHash *next; // next in top-level hash table linked list
  95         uintptr addr;   // addr>>20
  96         AddrEntry *dense[1<<13];
  97 };
  98
  99 struct AddrEntry
 100 {
 101         AddrEntry *next;        // next in bottom-level linked list
 102         uint32 addr;
 103         Bucket *b;
 104 };
 105
 106 enum {
 107         AddrHashBits = 12       // 1MB per entry, so good for 4GB of used address space
 108 };
 109 static AddrHash *addrhash[1<<AddrHashBits];
 110 static AddrEntry *addrfree;
 111 static uintptr addrmem;
 112
 113 // Multiplicative hash function:
 114 // hashMultiplier is the bottom 32 bits of int((sqrt(5)-1)/2 * (1<<32)).
 115 // This is a good multiplier as suggested in CLR, Knuth.  The hash
 116 // value is taken to be the top AddrHashBits bits of the bottom 32 bits
 117 // of the multiplied value.
 118 enum {
 119         HashMultiplier = 2654435769U
 120 };
 121
 122 // Set the bucket associated with addr to b.
 123 static void
 124 setaddrbucket(uintptr addr, Bucket *b)
 125 {
 126         int32 i;
 127         uint32 h;
 128         AddrHash *ah;
 129         AddrEntry *e;
 130
 131         h = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);
 132         for(ah=addrhash[h]; ah; ah=ah->next)
 133                 if(ah->addr == (addr>>20))
 134                         goto found;
 135
 136         ah = runtime_mallocgc(sizeof *ah, FlagNoProfiling, 0, 1);
 137         addrmem += sizeof *ah;
 138         ah->next = addrhash[h];
 139         ah->addr = addr>>20;
 140         addrhash[h] = ah;
 141
 142 found:
 143         if((e = addrfree) == nil) {
 144                 e = runtime_mallocgc(64*sizeof *e, FlagNoProfiling, 0, 0);
 145                 addrmem += 64*sizeof *e;
 146                 for(i=0; i+1<64; i++)
 147                         e[i].next = &e[i+1];
 148                 e[63].next = nil;
 149         }
 150         addrfree = e->next;
 151         e->addr = (uint32)~(addr & ((1<<20)-1));
 152         e->b = b;
 153         h = (addr>>7)&(nelem(ah->dense)-1);     // entry in dense is top 13 bits of low 20.
 154         e->next = ah->dense[h];
 155         ah->dense[h] = e;
 156 }
 157
 158 // Get the bucket associated with addr and clear the association.
 159 static Bucket*
 160 getaddrbucket(uintptr addr)
 161 {
 162         uint32 h;
 163         AddrHash *ah;
 164         AddrEntry *e, **l;
 165         Bucket *b;
 166
 167         h = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);
 168         for(ah=addrhash[h]; ah; ah=ah->next)
 169                 if(ah->addr == (addr>>20))
 170                         goto found;
 171         return nil;
 172
 173 found:
 174         h = (addr>>7)&(nelem(ah->dense)-1);     // entry in dense is top 13 bits of low 20.
 175         for(l=&ah->dense[h]; (e=*l) != nil; l=&e->next) {
 176                 if(e->addr == (uint32)~(addr & ((1<<20)-1))) {
 177                         *l = e->next;
 178                         b = e->b;
 179                         e->next = addrfree;
 180                         addrfree = e;
 181                         return b;
 182                 }
 183         }
 184         return nil;
 185 }
 186
 187 // Called by malloc to record a profiled block.
 188 void
 189 runtime_MProf_Malloc(void *p, uintptr size)
 190 {
 191         M *m;
 192         int32 nstk;
 193         uintptr stk[32];
 194         Bucket *b;
 195
 196         m = runtime_m();
 197         if(m->nomemprof > 0)
 198                 return;
 199
 200         m->nomemprof++;
 201 #if 0
 202         nstk = runtime_callers(1, stk, 32);
 203 #else
 204         nstk = 0;
 205 #endif
 206         runtime_lock(&proflock);
 207         b = stkbucket(stk, nstk);
 208         b->allocs++;
 209         b->alloc_bytes += size;
 210         setaddrbucket((uintptr)p, b);
 211         runtime_unlock(&proflock);
 212         m = runtime_m();
 213         m->nomemprof--;
 214 }
 215
 216 // Called when freeing a profiled block.
 217 void
 218 runtime_MProf_Free(void *p, uintptr size)
 219 {
 220         M *m;
 221         Bucket *b;
 222
 223         m = runtime_m();
 224         if(m->nomemprof > 0)
 225                 return;
 226
 227         m->nomemprof++;
 228         runtime_lock(&proflock);
 229         b = getaddrbucket((uintptr)p);
 230         if(b != nil) {
 231                 b->frees++;
 232                 b->free_bytes += size;
 233         }
 234         runtime_unlock(&proflock);
 235         m = runtime_m();
 236         m->nomemprof--;
 237 }
 238
 239
 240 // Go interface to profile data.  (Declared in extern.go)
 241 // Assumes Go sizeof(int) == sizeof(int32)
 242
 243 // Must match MemProfileRecord in extern.go.
 244 typedef struct Record Record;
 245 struct Record {
 246         int64 alloc_bytes, free_bytes;
 247         int64 alloc_objects, free_objects;
 248         uintptr stk[32];
 249 };
 250
 251 // Write b's data to r.
 252 static void
 253 record(Record *r, Bucket *b)
 254 {
 255         uint32 i;
 256
 257         r->alloc_bytes = b->alloc_bytes;
 258         r->free_bytes = b->free_bytes;
 259         r->alloc_objects = b->allocs;
 260         r->free_objects = b->frees;
 261         for(i=0; i<b->nstk && i<nelem(r->stk); i++)
 262                 r->stk[i] = b->stk[i];
 263         for(; i<nelem(r->stk); i++)
 264                 r->stk[i] = 0;
 265 }
 266
 267 func MemProfile(p Slice, include_inuse_zero bool) (n int32, ok bool) {
 268         Bucket *b;
 269         Record *r;
 270
 271         runtime_lock(&proflock);
 272         n = 0;
 273         for(b=buckets; b; b=b->allnext)
 274                 if(include_inuse_zero || b->alloc_bytes != b->free_bytes)
 275                         n++;
 276         ok = false;
 277         if(n <= p.__count) {
 278                 ok = true;
 279                 r = (Record*)p.__values;
 280                 for(b=buckets; b; b=b->allnext)
 281                         if(include_inuse_zero || b->alloc_bytes != b->free_bytes)
 282                                 record(r++, b);
 283         }
 284         runtime_unlock(&proflock);
 285 }
 286
 287 void
 288 runtime_MProf_Mark(void (*scan)(byte *, int64))
 289 {
 290         // buckhash is not allocated via mallocgc.
 291         scan((byte*)&buckets, sizeof buckets);
 292         scan((byte*)&addrhash, sizeof addrhash);
 293         scan((byte*)&addrfree, sizeof addrfree);
 294 }