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 enum { MProf, BProf };  // profile types
  19
  20 // Per-call-stack profiling information.
  21 // Lookup by hashing call stack into a linked-list hash table.
  22 typedef struct Bucket Bucket;
  23 struct Bucket
  24 {
  25         Bucket  *next;  // next in hash list
  26         Bucket  *allnext;       // next in list of all mbuckets/bbuckets
  27         int32   typ;
  28         union
  29         {
  30                 struct  // typ == MProf
  31                 {
  32                         uintptr allocs;
  33                         uintptr frees;
  34                         uintptr alloc_bytes;
  35                         uintptr free_bytes;
  36                         uintptr recent_allocs;  // since last gc
  37                         uintptr recent_frees;
  38                         uintptr recent_alloc_bytes;
  39                         uintptr recent_free_bytes;
  40                 };
  41                 struct  // typ == BProf
  42                 {
  43                         int64   count;
  44                         int64   cycles;
  45                 };
  46         };
  47         uintptr hash;
  48         uintptr nstk;
  49         uintptr stk[1];
  50 };
  51 enum {
  52         BuckHashSize = 179999,
  53 };
  54 static Bucket **buckhash;
  55 static Bucket *mbuckets;  // memory profile buckets
  56 static Bucket *bbuckets;  // blocking profile buckets
  57 static uintptr bucketmem;
  58
  59 // Return the bucket for stk[0:nstk], allocating new bucket if needed.
  60 static Bucket*
  61 stkbucket(int32 typ, uintptr *stk, int32 nstk, bool alloc)
  62 {
  63         int32 i;
  64         uintptr h;
  65         Bucket *b;
  66
  67         if(buckhash == nil) {
  68                 buckhash = runtime_SysAlloc(BuckHashSize*sizeof buckhash[0]);
  69                 mstats.buckhash_sys += BuckHashSize*sizeof buckhash[0];
  70         }
  71
  72         // Hash stack.
  73         h = 0;
  74         for(i=0; i<nstk; i++) {
  75                 h += stk[i];
  76                 h += h<<10;
  77                 h ^= h>>6;
  78         }
  79         h += h<<3;
  80         h ^= h>>11;
  81
  82         i = h%BuckHashSize;
  83         for(b = buckhash[i]; b; b=b->next)
  84                 if(b->typ == typ && b->hash == h && b->nstk == (uintptr)nstk &&
  85                    runtime_mcmp((byte*)b->stk, (byte*)stk, nstk*sizeof stk[0]) == 0)
  86                         return b;
  87
  88         if(!alloc)
  89                 return nil;
  90
  91         b = runtime_mallocgc(sizeof *b + nstk*sizeof stk[0], FlagNoProfiling, 0, 1);
  92         bucketmem += sizeof *b + nstk*sizeof stk[0];
  93         runtime_memmove(b->stk, stk, nstk*sizeof stk[0]);
  94         b->typ = typ;
  95         b->hash = h;
  96         b->nstk = nstk;
  97         b->next = buckhash[i];
  98         buckhash[i] = b;
  99         if(typ == MProf) {
 100                 b->allnext = mbuckets;
 101                 mbuckets = b;
 102         } else {
 103                 b->allnext = bbuckets;
 104                 bbuckets = b;
 105         }
 106         return b;
 107 }
 108
 109 // Record that a gc just happened: all the 'recent' statistics are now real.
 110 void
 111 runtime_MProf_GC(void)
 112 {
 113         Bucket *b;
 114
 115         runtime_lock(&proflock);
 116         for(b=mbuckets; b; b=b->allnext) {
 117                 b->allocs += b->recent_allocs;
 118                 b->frees += b->recent_frees;
 119                 b->alloc_bytes += b->recent_alloc_bytes;
 120                 b->free_bytes += b->recent_free_bytes;
 121                 b->recent_allocs = 0;
 122                 b->recent_frees = 0;
 123                 b->recent_alloc_bytes = 0;
 124                 b->recent_free_bytes = 0;
 125         }
 126         runtime_unlock(&proflock);
 127 }
 128
 129 // Map from pointer to Bucket* that allocated it.
 130 // Three levels:
 131 //      Linked-list hash table for top N-AddrHashShift bits.
 132 //      Array index for next AddrDenseBits bits.
 133 //      Linked list for next AddrHashShift-AddrDenseBits bits.
 134 // This is more efficient than using a general map,
 135 // because of the typical clustering of the pointer keys.
 136
 137 typedef struct AddrHash AddrHash;
 138 typedef struct AddrEntry AddrEntry;
 139
 140 enum {
 141         AddrHashBits = 12,      // good for 4GB of used address space
 142         AddrHashShift = 20,     // each AddrHash knows about 1MB of address space
 143         AddrDenseBits = 8,      // good for a profiling rate of 4096 bytes
 144 };
 145
 146 struct AddrHash
 147 {
 148         AddrHash *next; // next in top-level hash table linked list
 149         uintptr addr;   // addr>>20
 150         AddrEntry *dense[1<<AddrDenseBits];
 151 };
 152
 153 struct AddrEntry
 154 {
 155         AddrEntry *next;        // next in bottom-level linked list
 156         uint32 addr;
 157         Bucket *b;
 158 };
 159
 160 static AddrHash *addrhash[1<<AddrHashBits];
 161 static AddrEntry *addrfree;
 162 static uintptr addrmem;
 163
 164 // Multiplicative hash function:
 165 // hashMultiplier is the bottom 32 bits of int((sqrt(5)-1)/2 * (1<<32)).
 166 // This is a good multiplier as suggested in CLR, Knuth.  The hash
 167 // value is taken to be the top AddrHashBits bits of the bottom 32 bits
 168 // of the multiplied value.
 169 enum {
 170         HashMultiplier = 2654435769U
 171 };
 172
 173 // Set the bucket associated with addr to b.
 174 static void
 175 setaddrbucket(uintptr addr, Bucket *b)
 176 {
 177         int32 i;
 178         uint32 h;
 179         AddrHash *ah;
 180         AddrEntry *e;
 181
 182         h = (uint32)((addr>>AddrHashShift)*HashMultiplier) >> (32-AddrHashBits);
 183         for(ah=addrhash[h]; ah; ah=ah->next)
 184                 if(ah->addr == (addr>>AddrHashShift))
 185                         goto found;
 186
 187         ah = runtime_mallocgc(sizeof *ah, FlagNoProfiling, 0, 1);
 188         addrmem += sizeof *ah;
 189         ah->next = addrhash[h];
 190         ah->addr = addr>>AddrHashShift;
 191         addrhash[h] = ah;
 192
 193 found:
 194         if((e = addrfree) == nil) {
 195                 e = runtime_mallocgc(64*sizeof *e, FlagNoProfiling, 0, 0);
 196                 addrmem += 64*sizeof *e;
 197                 for(i=0; i+1<64; i++)
 198                         e[i].next = &e[i+1];
 199                 e[63].next = nil;
 200         }
 201         addrfree = e->next;
 202         e->addr = (uint32)~(addr & ((1<<AddrHashShift)-1));
 203         e->b = b;
 204         h = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1); // entry in dense is top 8 bits of low 20.
 205         e->next = ah->dense[h];
 206         ah->dense[h] = e;
 207 }
 208
 209 // Get the bucket associated with addr and clear the association.
 210 static Bucket*
 211 getaddrbucket(uintptr addr)
 212 {
 213         uint32 h;
 214         AddrHash *ah;
 215         AddrEntry *e, **l;
 216         Bucket *b;
 217
 218         h = (uint32)((addr>>AddrHashShift)*HashMultiplier) >> (32-AddrHashBits);
 219         for(ah=addrhash[h]; ah; ah=ah->next)
 220                 if(ah->addr == (addr>>AddrHashShift))
 221                         goto found;
 222         return nil;
 223
 224 found:
 225         h = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1); // entry in dense is top 8 bits of low 20.
 226         for(l=&ah->dense[h]; (e=*l) != nil; l=&e->next) {
 227                 if(e->addr == (uint32)~(addr & ((1<<AddrHashShift)-1))) {
 228                         *l = e->next;
 229                         b = e->b;
 230                         e->next = addrfree;
 231                         addrfree = e;
 232                         return b;
 233                 }
 234         }
 235         return nil;
 236 }
 237
 238 // Called by malloc to record a profiled block.
 239 void
 240 runtime_MProf_Malloc(void *p, uintptr size)
 241 {
 242         M *m;
 243         int32 nstk;
 244         uintptr stk[32];
 245         Bucket *b;
 246
 247         m = runtime_m();
 248         if(m->nomemprof > 0)
 249                 return;
 250
 251         m->nomemprof++;
 252         nstk = runtime_callers(1, stk, 32);
 253         runtime_lock(&proflock);
 254         b = stkbucket(MProf, stk, nstk, true);
 255         b->recent_allocs++;
 256         b->recent_alloc_bytes += size;
 257         setaddrbucket((uintptr)p, b);
 258         runtime_unlock(&proflock);
 259         m = runtime_m();
 260         m->nomemprof--;
 261 }
 262
 263 // Called when freeing a profiled block.
 264 void
 265 runtime_MProf_Free(void *p, uintptr size)
 266 {
 267         M *m;
 268         Bucket *b;
 269
 270         m = runtime_m();
 271         if(m->nomemprof > 0)
 272                 return;
 273
 274         m->nomemprof++;
 275         runtime_lock(&proflock);
 276         b = getaddrbucket((uintptr)p);
 277         if(b != nil) {
 278                 b->recent_frees++;
 279                 b->recent_free_bytes += size;
 280         }
 281         runtime_unlock(&proflock);
 282         m = runtime_m();
 283         m->nomemprof--;
 284 }
 285
 286 int64 runtime_blockprofilerate;  // in CPU ticks
 287
 288 void runtime_SetBlockProfileRate(intgo) asm("runtime.SetBlockProfileRate");
 289
 290 void
 291 runtime_SetBlockProfileRate(intgo rate)
 292 {
 293         runtime_atomicstore64((uint64*)&runtime_blockprofilerate, rate * runtime_tickspersecond() / (1000*1000*1000));
 294 }
 295
 296 void
 297 runtime_blockevent(int64 cycles, int32 skip)
 298 {
 299         int32 nstk;
 300         int64 rate;
 301         uintptr stk[32];
 302         Bucket *b;
 303
 304         if(cycles <= 0)
 305                 return;
 306         rate = runtime_atomicload64((uint64*)&runtime_blockprofilerate);
 307         if(rate <= 0 || (rate > cycles && runtime_fastrand1()%rate > cycles))
 308                 return;
 309
 310         nstk = runtime_callers(skip, stk, 32);
 311         runtime_lock(&proflock);
 312         b = stkbucket(BProf, stk, nstk, true);
 313         b->count++;
 314         b->cycles += cycles;
 315         runtime_unlock(&proflock);
 316 }
 317
 318 // Go interface to profile data.  (Declared in extern.go)
 319 // Assumes Go sizeof(int) == sizeof(int32)
 320
 321 // Must match MemProfileRecord in debug.go.
 322 typedef struct Record Record;
 323 struct Record {
 324         int64 alloc_bytes, free_bytes;
 325         int64 alloc_objects, free_objects;
 326         uintptr stk[32];
 327 };
 328
 329 // Write b's data to r.
 330 static void
 331 record(Record *r, Bucket *b)
 332 {
 333         uint32 i;
 334
 335         r->alloc_bytes = b->alloc_bytes;
 336         r->free_bytes = b->free_bytes;
 337         r->alloc_objects = b->allocs;
 338         r->free_objects = b->frees;
 339         for(i=0; i<b->nstk && i<nelem(r->stk); i++)
 340                 r->stk[i] = b->stk[i];
 341         for(; i<nelem(r->stk); i++)
 342                 r->stk[i] = 0;
 343 }
 344
 345 func MemProfile(p Slice, include_inuse_zero bool) (n int, ok bool) {
 346         Bucket *b;
 347         Record *r;
 348
 349         runtime_lock(&proflock);
 350         n = 0;
 351         for(b=mbuckets; b; b=b->allnext)
 352                 if(include_inuse_zero || b->alloc_bytes != b->free_bytes)
 353                         n++;
 354         ok = false;
 355         if(n <= p.__count) {
 356                 ok = true;
 357                 r = (Record*)p.__values;
 358                 for(b=mbuckets; b; b=b->allnext)
 359                         if(include_inuse_zero || b->alloc_bytes != b->free_bytes)
 360                                 record(r++, b);
 361         }
 362         runtime_unlock(&proflock);
 363 }
 364
 365 void
 366 runtime_MProf_Mark(void (*addroot)(byte *, uintptr))
 367 {
 368         // buckhash is not allocated via mallocgc.
 369         addroot((byte*)&mbuckets, sizeof mbuckets);
 370         addroot((byte*)&bbuckets, sizeof bbuckets);
 371         addroot((byte*)&addrhash, sizeof addrhash);
 372         addroot((byte*)&addrfree, sizeof addrfree);
 373 }
 374
 375 // Must match BlockProfileRecord in debug.go.
 376 typedef struct BRecord BRecord;
 377 struct BRecord {
 378         int64 count;
 379         int64 cycles;
 380         uintptr stk[32];
 381 };
 382
 383 func BlockProfile(p Slice) (n int, ok bool) {
 384         Bucket *b;
 385         BRecord *r;
 386         int32 i;
 387
 388         runtime_lock(&proflock);
 389         n = 0;
 390         for(b=bbuckets; b; b=b->allnext)
 391                 n++;
 392         ok = false;
 393         if(n <= p.__count) {
 394                 ok = true;
 395                 r = (BRecord*)p.__values;
 396                 for(b=bbuckets; b; b=b->allnext, r++) {
 397                         r->count = b->count;
 398                         r->cycles = b->cycles;
 399                         for(i=0; (uintptr)i<b->nstk && (uintptr)i<nelem(r->stk); i++)
 400                                 r->stk[i] = b->stk[i];
 401                         for(; (uintptr)i<nelem(r->stk); i++)
 402                                 r->stk[i] = 0;
 403                 }
 404         }
 405         runtime_unlock(&proflock);
 406 }
 407
 408 // Must match StackRecord in debug.go.
 409 typedef struct TRecord TRecord;
 410 struct TRecord {
 411         uintptr stk[32];
 412 };
 413
 414 func ThreadCreateProfile(p Slice) (n int, ok bool) {
 415         TRecord *r;
 416         M *first, *m;
 417
 418         first = runtime_atomicloadp(&runtime_allm);
 419         n = 0;
 420         for(m=first; m; m=m->alllink)
 421                 n++;
 422         ok = false;
 423         if(n <= p.__count) {
 424                 ok = true;
 425                 r = (TRecord*)p.__values;
 426                 for(m=first; m; m=m->alllink) {
 427                         runtime_memmove(r->stk, m->createstack, sizeof r->stk);
 428                         r++;
 429                 }
 430         }
 431 }
 432
 433 func Stack(b Slice, all bool) (n int) {
 434         byte *pc, *sp;
 435         bool enablegc;
 436
 437         sp = runtime_getcallersp(&b);
 438         pc = runtime_getcallerpc(&b);
 439
 440         if(all) {
 441                 runtime_semacquire(&runtime_worldsema);
 442                 runtime_m()->gcing = 1;
 443                 runtime_stoptheworld();
 444                 enablegc = mstats.enablegc;
 445                 mstats.enablegc = false;
 446         }
 447
 448         if(b.__count == 0)
 449                 n = 0;
 450         else{
 451                 G* g = runtime_g();
 452                 g->writebuf = (byte*)b.__values;
 453                 g->writenbuf = b.__count;
 454                 USED(pc);
 455                 USED(sp);
 456                 runtime_goroutineheader(g);
 457                 runtime_traceback();
 458                 runtime_goroutinetrailer(g);
 459                 if(all)
 460                         runtime_tracebackothers(g);
 461                 n = b.__count - g->writenbuf;
 462                 g->writebuf = nil;
 463                 g->writenbuf = 0;
 464         }
 465
 466         if(all) {
 467                 runtime_m()->gcing = 0;
 468                 mstats.enablegc = enablegc;
 469                 runtime_semrelease(&runtime_worldsema);
 470                 runtime_starttheworld();
 471         }
 472 }
 473
 474 static void
 475 saveg(G *g, TRecord *r)
 476 {
 477         int32 n;
 478
 479         if(g == runtime_g())
 480                 n = runtime_callers(0, r->stk, nelem(r->stk));
 481         else {
 482                 // FIXME: Not implemented.
 483                 n = 0;
 484         }
 485         if((size_t)n < nelem(r->stk))
 486                 r->stk[n] = 0;
 487 }
 488
 489 func GoroutineProfile(b Slice) (n int, ok bool) {
 490         TRecord *r;
 491         G *gp;
 492
 493         ok = false;
 494         n = runtime_gcount();
 495         if(n <= b.__count) {
 496                 runtime_semacquire(&runtime_worldsema);
 497                 runtime_m()->gcing = 1;
 498                 runtime_stoptheworld();
 499
 500                 n = runtime_gcount();
 501                 if(n <= b.__count) {
 502                         G* g = runtime_g();
 503                         ok = true;
 504                         r = (TRecord*)b.__values;
 505                         saveg(g, r++);
 506                         for(gp = runtime_allg; gp != nil; gp = gp->alllink) {
 507                                 if(gp == g || gp->status == Gdead)
 508                                         continue;
 509                                 saveg(gp, r++);
 510                         }
 511                 }
 512
 513                 runtime_m()->gcing = 0;
 514                 runtime_semrelease(&runtime_worldsema);
 515                 runtime_starttheworld();
 516         }
 517 }
 518