1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// ---
6// Author: Sainbayar Sukhbaatar
7//         Dai Mikurube
8//
9
10#include "deep-heap-profile.h"
11
12#ifdef USE_DEEP_HEAP_PROFILE
13#include <algorithm>
14#include <fcntl.h>
15#include <sys/stat.h>
16#include <sys/types.h>
17#include <time.h>
18#ifdef HAVE_UNISTD_H
19#include <unistd.h>  // for getpagesize and getpid
20#endif  // HAVE_UNISTD_H
21
22#if defined(__linux__)
23#include <endian.h>
24#if !defined(__LITTLE_ENDIAN__) and !defined(__BIG_ENDIAN__)
25#if __BYTE_ORDER == __BIG_ENDIAN
26#define __BIG_ENDIAN__
27#endif  // __BYTE_ORDER == __BIG_ENDIAN
28#endif  // !defined(__LITTLE_ENDIAN__) and !defined(__BIG_ENDIAN__)
29#if defined(__BIG_ENDIAN__)
30#include <byteswap.h>
31#endif  // defined(__BIG_ENDIAN__)
32#endif  // defined(__linux__)
33#if defined(COMPILER_MSVC)
34#include <Winsock2.h>  // for gethostname
35#endif  // defined(COMPILER_MSVC)
36
37#include "base/cycleclock.h"
38#include "base/sysinfo.h"
39#include "internal_logging.h"  // for ASSERT, etc
40
41static const int kProfilerBufferSize = 1 << 20;
42static const int kHashTableSize = 179999;  // Same as heap-profile-table.cc.
43
44static const int PAGEMAP_BYTES = 8;
45static const int KPAGECOUNT_BYTES = 8;
46static const uint64 MAX_ADDRESS = kuint64max;
47
48// Tag strings in heap profile dumps.
49static const char kProfileHeader[] = "heap profile: ";
50static const char kProfileVersion[] = "DUMP_DEEP_6";
51static const char kMetaInformationHeader[] = "META:\n";
52static const char kMMapListHeader[] = "MMAP_LIST:\n";
53static const char kGlobalStatsHeader[] = "GLOBAL_STATS:\n";
54static const char kStacktraceHeader[] = "STACKTRACES:\n";
55static const char kProcSelfMapsHeader[] = "\nMAPPED_LIBRARIES:\n";
56
57static const char kVirtualLabel[] = "virtual";
58static const char kCommittedLabel[] = "committed";
59
60#if defined(__linux__)
61#define OS_NAME "linux"
62#elif defined(_WIN32) || defined(_WIN64)
63#define OS_NAME "windows"
64#else
65#define OS_NAME "unknown-os"
66#endif
67
68bool DeepHeapProfile::AppendCommandLine(TextBuffer* buffer) {
69#if defined(__linux__)
70  RawFD fd;
71  char filename[100];
72  char cmdline[4096];
73  snprintf(filename, sizeof(filename), "/proc/%d/cmdline",
74           static_cast<int>(getpid()));
75  fd = open(filename, O_RDONLY);
76  if (fd == kIllegalRawFD) {
77    RAW_VLOG(0, "Failed to open /proc/self/cmdline");
78    return false;
79  }
80
81  size_t length = read(fd, cmdline, sizeof(cmdline) - 1);
82  close(fd);
83
84  for (int i = 0; i < length; ++i)
85    if (cmdline[i] == '\0')
86      cmdline[i] = ' ';
87  cmdline[length] = '\0';
88
89  buffer->AppendString("CommandLine: ", 0);
90  buffer->AppendString(cmdline, 0);
91  buffer->AppendChar('\n');
92
93  return true;
94#else
95  return false;
96#endif
97}
98
99#if defined(_WIN32) || defined(_WIN64)
100
101// TODO(peria): Implement this function.
102void DeepHeapProfile::MemoryInfoGetterWindows::Initialize() {
103}
104
105// TODO(peria): Implement this function.
106size_t DeepHeapProfile::MemoryInfoGetterWindows::CommittedSize(
107    uint64 first_address,
108    uint64 last_address,
109    TextBuffer* buffer) const {
110  return 0;
111}
112
113// TODO(peria): Implement this function.
114bool DeepHeapProfile::MemoryInfoGetterWindows::IsPageCountAvailable() const {
115  return false;
116}
117
118#endif  // defined(_WIN32) || defined(_WIN64)
119
120#if defined(__linux__)
121
122void DeepHeapProfile::MemoryInfoGetterLinux::Initialize() {
123  char filename[100];
124  snprintf(filename, sizeof(filename), "/proc/%d/pagemap",
125           static_cast<int>(getpid()));
126  pagemap_fd_ = open(filename, O_RDONLY);
127  RAW_CHECK(pagemap_fd_ != -1, "Failed to open /proc/self/pagemap");
128
129  if (pageframe_type_ == DUMP_PAGECOUNT) {
130    snprintf(filename, sizeof(filename), "/proc/kpagecount");
131    kpagecount_fd_ = open(filename, O_RDONLY);
132    if (kpagecount_fd_ == -1)
133      RAW_VLOG(0, "Failed to open /proc/kpagecount");
134  }
135}
136
137size_t DeepHeapProfile::MemoryInfoGetterLinux::CommittedSize(
138    uint64 first_address,
139    uint64 last_address,
140    DeepHeapProfile::TextBuffer* buffer) const {
141  int page_size = getpagesize();
142  uint64 page_address = (first_address / page_size) * page_size;
143  size_t committed_size = 0;
144  size_t pageframe_list_length = 0;
145
146  Seek(first_address);
147
148  // Check every page on which the allocation resides.
149  while (page_address <= last_address) {
150    // Read corresponding physical page.
151    State state;
152    // TODO(dmikurube): Read pagemap in bulk for speed.
153    // TODO(dmikurube): Consider using mincore(2).
154    if (Read(&state, pageframe_type_ != DUMP_NO_PAGEFRAME) == false) {
155      // We can't read the last region (e.g vsyscall).
156#ifndef NDEBUG
157      RAW_VLOG(0, "pagemap read failed @ %#llx %" PRId64 " bytes",
158              first_address, last_address - first_address + 1);
159#endif
160      return 0;
161    }
162
163    // Dump pageframes of resident pages.  Non-resident pages are just skipped.
164    if (pageframe_type_ != DUMP_NO_PAGEFRAME &&
165        buffer != NULL && state.pfn != 0) {
166      if (pageframe_list_length == 0) {
167        buffer->AppendString("  PF:", 0);
168        pageframe_list_length = 5;
169      }
170      buffer->AppendChar(' ');
171      if (page_address < first_address)
172        buffer->AppendChar('<');
173      buffer->AppendBase64(state.pfn, 4);
174      pageframe_list_length += 5;
175      if (pageframe_type_ == DUMP_PAGECOUNT && IsPageCountAvailable()) {
176        uint64 pagecount = ReadPageCount(state.pfn);
177        // Assume pagecount == 63 if the pageframe is mapped more than 63 times.
178        if (pagecount > 63)
179          pagecount = 63;
180        buffer->AppendChar('#');
181        buffer->AppendBase64(pagecount, 1);
182        pageframe_list_length += 2;
183      }
184      if (last_address < page_address - 1 + page_size)
185        buffer->AppendChar('>');
186      // Begins a new line every 94 characters.
187      if (pageframe_list_length > 94) {
188        buffer->AppendChar('\n');
189        pageframe_list_length = 0;
190      }
191    }
192
193    if (state.is_committed) {
194      // Calculate the size of the allocation part in this page.
195      size_t bytes = page_size;
196
197      // If looking at the last page in a given region.
198      if (last_address <= page_address - 1 + page_size) {
199        bytes = last_address - page_address + 1;
200      }
201
202      // If looking at the first page in a given region.
203      if (page_address < first_address) {
204        bytes -= first_address - page_address;
205      }
206
207      committed_size += bytes;
208    }
209    if (page_address > MAX_ADDRESS - page_size) {
210      break;
211    }
212    page_address += page_size;
213  }
214
215  if (pageframe_type_ != DUMP_NO_PAGEFRAME &&
216      buffer != NULL && pageframe_list_length != 0) {
217    buffer->AppendChar('\n');
218  }
219
220  return committed_size;
221}
222
223uint64 DeepHeapProfile::MemoryInfoGetterLinux::ReadPageCount(uint64 pfn) const {
224  int64 index = pfn * KPAGECOUNT_BYTES;
225  int64 offset = lseek64(kpagecount_fd_, index, SEEK_SET);
226  RAW_DCHECK(offset == index, "Failed in seeking in kpagecount.");
227
228  uint64 kpagecount_value;
229  int result = read(kpagecount_fd_, &kpagecount_value, KPAGECOUNT_BYTES);
230  if (result != KPAGECOUNT_BYTES)
231    return 0;
232
233  return kpagecount_value;
234}
235
236bool DeepHeapProfile::MemoryInfoGetterLinux::Seek(uint64 address) const {
237  int64 index = (address / getpagesize()) * PAGEMAP_BYTES;
238  RAW_DCHECK(pagemap_fd_ != -1, "Failed to seek in /proc/self/pagemap");
239  int64 offset = lseek64(pagemap_fd_, index, SEEK_SET);
240  RAW_DCHECK(offset == index, "Failed in seeking.");
241  return offset >= 0;
242}
243
244bool DeepHeapProfile::MemoryInfoGetterLinux::Read(
245    State* state, bool get_pfn) const {
246  static const uint64 U64_1 = 1;
247  static const uint64 PFN_FILTER = (U64_1 << 55) - U64_1;
248  static const uint64 PAGE_PRESENT = U64_1 << 63;
249  static const uint64 PAGE_SWAP = U64_1 << 62;
250  static const uint64 PAGE_RESERVED = U64_1 << 61;
251  static const uint64 FLAG_NOPAGE = U64_1 << 20;
252  static const uint64 FLAG_KSM = U64_1 << 21;
253  static const uint64 FLAG_MMAP = U64_1 << 11;
254
255  uint64 pagemap_value;
256  RAW_DCHECK(pagemap_fd_ != -1, "Failed to read from /proc/self/pagemap");
257  int result = read(pagemap_fd_, &pagemap_value, PAGEMAP_BYTES);
258  if (result != PAGEMAP_BYTES) {
259    return false;
260  }
261
262  // Check if the page is committed.
263  state->is_committed = (pagemap_value & (PAGE_PRESENT | PAGE_SWAP));
264
265  state->is_present = (pagemap_value & PAGE_PRESENT);
266  state->is_swapped = (pagemap_value & PAGE_SWAP);
267  state->is_shared = false;
268
269  if (get_pfn && state->is_present && !state->is_swapped)
270    state->pfn = (pagemap_value & PFN_FILTER);
271  else
272    state->pfn = 0;
273
274  return true;
275}
276
277bool DeepHeapProfile::MemoryInfoGetterLinux::IsPageCountAvailable() const {
278  return kpagecount_fd_ != -1;
279}
280
281#endif  // defined(__linux__)
282
283DeepHeapProfile::MemoryResidenceInfoGetterInterface::
284    MemoryResidenceInfoGetterInterface() {}
285
286DeepHeapProfile::MemoryResidenceInfoGetterInterface::
287    ~MemoryResidenceInfoGetterInterface() {}
288
289DeepHeapProfile::MemoryResidenceInfoGetterInterface*
290    DeepHeapProfile::MemoryResidenceInfoGetterInterface::Create(
291        PageFrameType pageframe_type) {
292#if defined(_WIN32) || defined(_WIN64)
293  return new MemoryInfoGetterWindows(pageframe_type);
294#elif defined(__linux__)
295  return new MemoryInfoGetterLinux(pageframe_type);
296#else
297  return NULL;
298#endif
299}
300
301DeepHeapProfile::DeepHeapProfile(HeapProfileTable* heap_profile,
302                                 const char* prefix,
303                                 enum PageFrameType pageframe_type)
304    : memory_residence_info_getter_(
305          MemoryResidenceInfoGetterInterface::Create(pageframe_type)),
306      most_recent_pid_(-1),
307      stats_(),
308      dump_count_(0),
309      filename_prefix_(NULL),
310      deep_table_(kHashTableSize, heap_profile->alloc_, heap_profile->dealloc_),
311      pageframe_type_(pageframe_type),
312      heap_profile_(heap_profile) {
313  // Copy filename prefix.
314  const int prefix_length = strlen(prefix);
315  filename_prefix_ =
316      reinterpret_cast<char*>(heap_profile_->alloc_(prefix_length + 1));
317  memcpy(filename_prefix_, prefix, prefix_length);
318  filename_prefix_[prefix_length] = '\0';
319
320  strncpy(run_id_, "undetermined-run-id", sizeof(run_id_));
321}
322
323DeepHeapProfile::~DeepHeapProfile() {
324  heap_profile_->dealloc_(filename_prefix_);
325  delete memory_residence_info_getter_;
326}
327
328// Global malloc() should not be used in this function.
329// Use LowLevelAlloc if required.
330void DeepHeapProfile::DumpOrderedProfile(const char* reason,
331                                         char raw_buffer[],
332                                         int buffer_size,
333                                         RawFD fd) {
334  TextBuffer buffer(raw_buffer, buffer_size, fd);
335
336#ifndef NDEBUG
337  int64 starting_cycles = CycleClock::Now();
338#endif
339
340  // Get the time before starting snapshot.
341  // TODO(dmikurube): Consider gettimeofday if available.
342  time_t time_value = time(NULL);
343
344  ++dump_count_;
345
346  // Re-open files in /proc/pid/ if the process is newly forked one.
347  if (most_recent_pid_ != getpid()) {
348    char hostname[64];
349    if (0 == gethostname(hostname, sizeof(hostname))) {
350      char* dot = strchr(hostname, '.');
351      if (dot != NULL)
352        *dot = '\0';
353    } else {
354      strcpy(hostname, "unknown");
355    }
356
357    most_recent_pid_ = getpid();
358
359    snprintf(run_id_, sizeof(run_id_), "%s-" OS_NAME "-%d-%lu",
360             hostname, most_recent_pid_, time(NULL));
361
362    if (memory_residence_info_getter_)
363      memory_residence_info_getter_->Initialize();
364    deep_table_.ResetIsLogged();
365
366    // Write maps into "|filename_prefix_|.<pid>.maps".
367    WriteProcMaps(filename_prefix_, raw_buffer, buffer_size);
368  }
369
370  // Reset committed sizes of buckets.
371  deep_table_.ResetCommittedSize();
372
373  // Record committed sizes.
374  stats_.SnapshotAllocations(this);
375
376  // TODO(dmikurube): Eliminate dynamic memory allocation caused by snprintf.
377  // glibc's snprintf internally allocates memory by alloca normally, but it
378  // allocates memory by malloc if large memory is required.
379
380  buffer.AppendString(kProfileHeader, 0);
381  buffer.AppendString(kProfileVersion, 0);
382  buffer.AppendString("\n", 0);
383
384  // Fill buffer with meta information.
385  buffer.AppendString(kMetaInformationHeader, 0);
386
387  buffer.AppendString("Time: ", 0);
388  buffer.AppendUnsignedLong(time_value, 0);
389  buffer.AppendChar('\n');
390
391  if (reason != NULL) {
392    buffer.AppendString("Reason: ", 0);
393    buffer.AppendString(reason, 0);
394    buffer.AppendChar('\n');
395  }
396
397  AppendCommandLine(&buffer);
398
399  buffer.AppendString("RunID: ", 0);
400  buffer.AppendString(run_id_, 0);
401  buffer.AppendChar('\n');
402
403  buffer.AppendString("PageSize: ", 0);
404  buffer.AppendInt(getpagesize(), 0, 0);
405  buffer.AppendChar('\n');
406
407  // Assumes the physical memory <= 64GB (PFN < 2^24).
408  if (pageframe_type_ == DUMP_PAGECOUNT && memory_residence_info_getter_ &&
409      memory_residence_info_getter_->IsPageCountAvailable()) {
410    buffer.AppendString("PageFrame: 24,Base64,PageCount", 0);
411    buffer.AppendChar('\n');
412  } else if (pageframe_type_ != DUMP_NO_PAGEFRAME) {
413    buffer.AppendString("PageFrame: 24,Base64", 0);
414    buffer.AppendChar('\n');
415  }
416
417  // Fill buffer with the global stats.
418  buffer.AppendString(kMMapListHeader, 0);
419
420  stats_.SnapshotMaps(memory_residence_info_getter_, this, &buffer);
421
422  // Fill buffer with the global stats.
423  buffer.AppendString(kGlobalStatsHeader, 0);
424
425  stats_.Unparse(&buffer);
426
427  buffer.AppendString(kStacktraceHeader, 0);
428  buffer.AppendString(kVirtualLabel, 10);
429  buffer.AppendChar(' ');
430  buffer.AppendString(kCommittedLabel, 10);
431  buffer.AppendString("\n", 0);
432
433  // Fill buffer.
434  deep_table_.UnparseForStats(&buffer);
435
436  buffer.Flush();
437
438  // Write the bucket listing into a .bucket file.
439  deep_table_.WriteForBucketFile(
440      filename_prefix_, dump_count_, raw_buffer, buffer_size);
441
442#ifndef NDEBUG
443  int64 elapsed_cycles = CycleClock::Now() - starting_cycles;
444  double elapsed_seconds = elapsed_cycles / CyclesPerSecond();
445  RAW_VLOG(0, "Time spent on DeepProfiler: %.3f sec\n", elapsed_seconds);
446#endif
447}
448
449int DeepHeapProfile::TextBuffer::Size() {
450  return size_;
451}
452
453int DeepHeapProfile::TextBuffer::FilledBytes() {
454  return cursor_;
455}
456
457void DeepHeapProfile::TextBuffer::Clear() {
458  cursor_ = 0;
459}
460
461void DeepHeapProfile::TextBuffer::Flush() {
462  RawWrite(fd_, buffer_, cursor_);
463  cursor_ = 0;
464}
465
466// TODO(dmikurube): These Append* functions should not use snprintf.
467bool DeepHeapProfile::TextBuffer::AppendChar(char value) {
468  return ForwardCursor(snprintf(buffer_ + cursor_, size_ - cursor_,
469                                "%c", value));
470}
471
472bool DeepHeapProfile::TextBuffer::AppendString(const char* value, int width) {
473  char* position = buffer_ + cursor_;
474  int available = size_ - cursor_;
475  int appended;
476  if (width == 0)
477    appended = snprintf(position, available, "%s", value);
478  else
479    appended = snprintf(position, available, "%*s",
480                        width, value);
481  return ForwardCursor(appended);
482}
483
484bool DeepHeapProfile::TextBuffer::AppendInt(int value, int width,
485                                            bool leading_zero) {
486  char* position = buffer_ + cursor_;
487  int available = size_ - cursor_;
488  int appended;
489  if (width == 0)
490    appended = snprintf(position, available, "%d", value);
491  else if (leading_zero)
492    appended = snprintf(position, available, "%0*d", width, value);
493  else
494    appended = snprintf(position, available, "%*d", width, value);
495  return ForwardCursor(appended);
496}
497
498bool DeepHeapProfile::TextBuffer::AppendLong(long value, int width) {
499  char* position = buffer_ + cursor_;
500  int available = size_ - cursor_;
501  int appended;
502  if (width == 0)
503    appended = snprintf(position, available, "%ld", value);
504  else
505    appended = snprintf(position, available, "%*ld", width, value);
506  return ForwardCursor(appended);
507}
508
509bool DeepHeapProfile::TextBuffer::AppendUnsignedLong(unsigned long value,
510                                                     int width) {
511  char* position = buffer_ + cursor_;
512  int available = size_ - cursor_;
513  int appended;
514  if (width == 0)
515    appended = snprintf(position, available, "%lu", value);
516  else
517    appended = snprintf(position, available, "%*lu", width, value);
518  return ForwardCursor(appended);
519}
520
521bool DeepHeapProfile::TextBuffer::AppendInt64(int64 value, int width) {
522  char* position = buffer_ + cursor_;
523  int available = size_ - cursor_;
524  int appended;
525  if (width == 0)
526    appended = snprintf(position, available, "%" PRId64, value);
527  else
528    appended = snprintf(position, available, "%*" PRId64, width, value);
529  return ForwardCursor(appended);
530}
531
532bool DeepHeapProfile::TextBuffer::AppendPtr(uint64 value, int width) {
533  char* position = buffer_ + cursor_;
534  int available = size_ - cursor_;
535  int appended;
536  if (width == 0)
537    appended = snprintf(position, available, "%" PRIx64, value);
538  else
539    appended = snprintf(position, available, "%0*" PRIx64, width, value);
540  return ForwardCursor(appended);
541}
542
543bool DeepHeapProfile::TextBuffer::AppendBase64(uint64 value, int width) {
544  static const char base64[65] =
545      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
546#if defined(__BIG_ENDIAN__)
547  value = bswap_64(value);
548#endif
549  for (int shift = (width - 1) * 6; shift >= 0; shift -= 6) {
550    if (!AppendChar(base64[(value >> shift) & 0x3f]))
551      return false;
552  }
553  return true;
554}
555
556bool DeepHeapProfile::TextBuffer::ForwardCursor(int appended) {
557  if (appended < 0 || appended >= size_ - cursor_)
558    return false;
559  cursor_ += appended;
560  if (cursor_ > size_ * 4 / 5)
561    Flush();
562  return true;
563}
564
565void DeepHeapProfile::DeepBucket::UnparseForStats(TextBuffer* buffer) {
566  buffer->AppendInt64(bucket->alloc_size - bucket->free_size, 10);
567  buffer->AppendChar(' ');
568  buffer->AppendInt64(committed_size, 10);
569  buffer->AppendChar(' ');
570  buffer->AppendInt(bucket->allocs, 6, false);
571  buffer->AppendChar(' ');
572  buffer->AppendInt(bucket->frees, 6, false);
573  buffer->AppendString(" @ ", 0);
574  buffer->AppendInt(id, 0, false);
575  buffer->AppendString("\n", 0);
576}
577
578void DeepHeapProfile::DeepBucket::UnparseForBucketFile(TextBuffer* buffer) {
579  buffer->AppendInt(id, 0, false);
580  buffer->AppendChar(' ');
581  buffer->AppendString(is_mmap ? "mmap" : "malloc", 0);
582
583#if defined(TYPE_PROFILING)
584  buffer->AppendString(" t0x", 0);
585  buffer->AppendPtr(reinterpret_cast<uintptr_t>(type), 0);
586  if (type == NULL) {
587    buffer->AppendString(" nno_typeinfo", 0);
588  } else {
589    buffer->AppendString(" n", 0);
590    buffer->AppendString(type->name(), 0);
591  }
592#endif
593
594  for (int depth = 0; depth < bucket->depth; depth++) {
595    buffer->AppendString(" 0x", 0);
596    buffer->AppendPtr(reinterpret_cast<uintptr_t>(bucket->stack[depth]), 8);
597  }
598  buffer->AppendString("\n", 0);
599}
600
601DeepHeapProfile::DeepBucketTable::DeepBucketTable(
602    int table_size,
603    HeapProfileTable::Allocator alloc,
604    HeapProfileTable::DeAllocator dealloc)
605    : table_(NULL),
606      table_size_(table_size),
607      alloc_(alloc),
608      dealloc_(dealloc),
609      bucket_id_(0) {
610  const int bytes = table_size * sizeof(DeepBucket*);
611  table_ = reinterpret_cast<DeepBucket**>(alloc(bytes));
612  memset(table_, 0, bytes);
613}
614
615DeepHeapProfile::DeepBucketTable::~DeepBucketTable() {
616  ASSERT(table_ != NULL);
617  for (int db = 0; db < table_size_; db++) {
618    for (DeepBucket* x = table_[db]; x != 0; /**/) {
619      DeepBucket* db = x;
620      x = x->next;
621      dealloc_(db);
622    }
623  }
624  dealloc_(table_);
625}
626
627DeepHeapProfile::DeepBucket* DeepHeapProfile::DeepBucketTable::Lookup(
628    Bucket* bucket,
629#if defined(TYPE_PROFILING)
630    const std::type_info* type,
631#endif
632    bool is_mmap) {
633  // Make hash-value
634  uintptr_t h = 0;
635
636  AddToHashValue(reinterpret_cast<uintptr_t>(bucket), &h);
637  if (is_mmap) {
638    AddToHashValue(1, &h);
639  } else {
640    AddToHashValue(0, &h);
641  }
642
643#if defined(TYPE_PROFILING)
644  if (type == NULL) {
645    AddToHashValue(0, &h);
646  } else {
647    AddToHashValue(reinterpret_cast<uintptr_t>(type->name()), &h);
648  }
649#endif
650
651  FinishHashValue(&h);
652
653  // Lookup stack trace in table
654  unsigned int buck = ((unsigned int) h) % table_size_;
655  for (DeepBucket* db = table_[buck]; db != 0; db = db->next) {
656    if (db->bucket == bucket) {
657      return db;
658    }
659  }
660
661  // Create a new bucket
662  DeepBucket* db = reinterpret_cast<DeepBucket*>(alloc_(sizeof(DeepBucket)));
663  memset(db, 0, sizeof(*db));
664  db->bucket         = bucket;
665#if defined(TYPE_PROFILING)
666  db->type           = type;
667#endif
668  db->committed_size = 0;
669  db->is_mmap        = is_mmap;
670  db->id             = (bucket_id_++);
671  db->is_logged      = false;
672  db->next           = table_[buck];
673  table_[buck] = db;
674  return db;
675}
676
677// TODO(dmikurube): Eliminate dynamic memory allocation caused by snprintf.
678void DeepHeapProfile::DeepBucketTable::UnparseForStats(TextBuffer* buffer) {
679  for (int i = 0; i < table_size_; i++) {
680    for (DeepBucket* deep_bucket = table_[i];
681         deep_bucket != NULL;
682         deep_bucket = deep_bucket->next) {
683      Bucket* bucket = deep_bucket->bucket;
684      if (bucket->alloc_size - bucket->free_size == 0) {
685        continue;  // Skip empty buckets.
686      }
687      deep_bucket->UnparseForStats(buffer);
688    }
689  }
690}
691
692void DeepHeapProfile::DeepBucketTable::WriteForBucketFile(
693    const char* prefix, int dump_count, char raw_buffer[], int buffer_size) {
694  char filename[100];
695  snprintf(filename, sizeof(filename),
696           "%s.%05d.%04d.buckets", prefix, getpid(), dump_count);
697  RawFD fd = RawOpenForWriting(filename);
698  RAW_DCHECK(fd != kIllegalRawFD, "");
699
700  TextBuffer buffer(raw_buffer, buffer_size, fd);
701
702  for (int i = 0; i < table_size_; i++) {
703    for (DeepBucket* deep_bucket = table_[i];
704         deep_bucket != NULL;
705         deep_bucket = deep_bucket->next) {
706      Bucket* bucket = deep_bucket->bucket;
707      if (deep_bucket->is_logged) {
708        continue;  // Skip the bucket if it is already logged.
709      }
710      if (!deep_bucket->is_mmap &&
711          bucket->alloc_size - bucket->free_size <= 64) {
712        continue;  // Skip small malloc buckets.
713      }
714
715      deep_bucket->UnparseForBucketFile(&buffer);
716      deep_bucket->is_logged = true;
717    }
718  }
719
720  buffer.Flush();
721  RawClose(fd);
722}
723
724void DeepHeapProfile::DeepBucketTable::ResetCommittedSize() {
725  for (int i = 0; i < table_size_; i++) {
726    for (DeepBucket* deep_bucket = table_[i];
727         deep_bucket != NULL;
728         deep_bucket = deep_bucket->next) {
729      deep_bucket->committed_size = 0;
730    }
731  }
732}
733
734void DeepHeapProfile::DeepBucketTable::ResetIsLogged() {
735  for (int i = 0; i < table_size_; i++) {
736    for (DeepBucket* deep_bucket = table_[i];
737         deep_bucket != NULL;
738         deep_bucket = deep_bucket->next) {
739      deep_bucket->is_logged = false;
740    }
741  }
742}
743
744// This hash function is from HeapProfileTable::GetBucket.
745// static
746void DeepHeapProfile::DeepBucketTable::AddToHashValue(
747    uintptr_t add, uintptr_t* hash_value) {
748  *hash_value += add;
749  *hash_value += *hash_value << 10;
750  *hash_value ^= *hash_value >> 6;
751}
752
753// This hash function is from HeapProfileTable::GetBucket.
754// static
755void DeepHeapProfile::DeepBucketTable::FinishHashValue(uintptr_t* hash_value) {
756  *hash_value += *hash_value << 3;
757  *hash_value ^= *hash_value >> 11;
758}
759
760void DeepHeapProfile::RegionStats::Initialize() {
761  virtual_bytes_ = 0;
762  committed_bytes_ = 0;
763}
764
765uint64 DeepHeapProfile::RegionStats::Record(
766    const MemoryResidenceInfoGetterInterface* memory_residence_info_getter,
767    uint64 first_address,
768    uint64 last_address,
769    TextBuffer* buffer) {
770  uint64 committed = 0;
771  virtual_bytes_ += static_cast<size_t>(last_address - first_address + 1);
772  if (memory_residence_info_getter)
773    committed = memory_residence_info_getter->CommittedSize(first_address,
774                                                            last_address,
775                                                            buffer);
776  committed_bytes_ += committed;
777  return committed;
778}
779
780void DeepHeapProfile::RegionStats::Unparse(const char* name,
781                                           TextBuffer* buffer) {
782  buffer->AppendString(name, 25);
783  buffer->AppendChar(' ');
784  buffer->AppendLong(virtual_bytes_, 12);
785  buffer->AppendChar(' ');
786  buffer->AppendLong(committed_bytes_, 12);
787  buffer->AppendString("\n", 0);
788}
789
790// Snapshots all virtual memory mapping stats by merging mmap(2) records from
791// MemoryRegionMap and /proc/maps, the OS-level memory mapping information.
792// Memory regions described in /proc/maps, but which are not created by mmap,
793// are accounted as "unhooked" memory regions.
794//
795// This function assumes that every memory region created by mmap is covered
796// by VMA(s) described in /proc/maps except for http://crbug.com/189114.
797// Note that memory regions created with mmap don't align with borders of VMAs
798// in /proc/maps.  In other words, a memory region by mmap can cut across many
799// VMAs.  Also, of course a VMA can include many memory regions by mmap.
800// It means that the following situation happens:
801//
802// => Virtual address
803// <----- VMA #1 -----><----- VMA #2 ----->...<----- VMA #3 -----><- VMA #4 ->
804// ..< mmap #1 >.<- mmap #2 -><- mmap #3 ->...<- mmap #4 ->..<-- mmap #5 -->..
805//
806// It can happen easily as permission can be changed by mprotect(2) for a part
807// of a memory region.  A change in permission splits VMA(s).
808//
809// To deal with the situation, this function iterates over MemoryRegionMap and
810// /proc/maps independently.  The iterator for MemoryRegionMap is initialized
811// at the top outside the loop for /proc/maps, and it goes forward inside the
812// loop while comparing their addresses.
813//
814// TODO(dmikurube): Eliminate dynamic memory allocation caused by snprintf.
815void DeepHeapProfile::GlobalStats::SnapshotMaps(
816    const MemoryResidenceInfoGetterInterface* memory_residence_info_getter,
817    DeepHeapProfile* deep_profile,
818    TextBuffer* mmap_dump_buffer) {
819  MemoryRegionMap::LockHolder lock_holder;
820  ProcMapsIterator::Buffer procmaps_iter_buffer;
821  ProcMapsIterator procmaps_iter(0, &procmaps_iter_buffer);
822  uint64 vma_start_addr, vma_last_addr, offset;
823  int64 inode;
824  char* flags;
825  char* filename;
826  enum MapsRegionType type;
827
828  for (int i = 0; i < NUMBER_OF_MAPS_REGION_TYPES; ++i) {
829    all_[i].Initialize();
830    unhooked_[i].Initialize();
831  }
832  profiled_mmap_.Initialize();
833
834  MemoryRegionMap::RegionIterator mmap_iter =
835      MemoryRegionMap::BeginRegionLocked();
836  DeepBucket* deep_bucket = NULL;
837  if (mmap_iter != MemoryRegionMap::EndRegionLocked()) {
838    deep_bucket = GetInformationOfMemoryRegion(
839        mmap_iter, memory_residence_info_getter, deep_profile);
840  }
841
842  while (procmaps_iter.Next(&vma_start_addr, &vma_last_addr,
843                            &flags, &offset, &inode, &filename)) {
844    if (mmap_dump_buffer) {
845      char buffer[1024];
846      int written = procmaps_iter.FormatLine(buffer, sizeof(buffer),
847                                             vma_start_addr, vma_last_addr,
848                                             flags, offset, inode, filename, 0);
849      mmap_dump_buffer->AppendString(buffer, 0);
850    }
851
852    // 'vma_last_addr' should be the last inclusive address of the region.
853    vma_last_addr -= 1;
854    if (strcmp("[vsyscall]", filename) == 0) {
855      continue;  // Reading pagemap will fail in [vsyscall].
856    }
857
858    // TODO(dmikurube): |type| will be deprecated in the dump.
859    // See http://crbug.com/245603.
860    type = ABSENT;
861    if (filename[0] == '/') {
862      if (flags[2] == 'x')
863        type = FILE_EXEC;
864      else
865        type = FILE_NONEXEC;
866    } else if (filename[0] == '\0' || filename[0] == '\n') {
867      type = ANONYMOUS;
868    } else if (strcmp(filename, "[stack]") == 0) {
869      type = STACK;
870    } else {
871      type = OTHER;
872    }
873    // TODO(dmikurube): This |all_| count should be removed in future soon.
874    // See http://crbug.com/245603.
875    uint64 vma_total = all_[type].Record(
876        memory_residence_info_getter, vma_start_addr, vma_last_addr, NULL);
877    uint64 vma_subtotal = 0;
878
879    // TODO(dmikurube): Stop double-counting pagemap.
880    // It will be fixed when http://crbug.com/245603 finishes.
881    if (MemoryRegionMap::IsRecordingLocked()) {
882      uint64 cursor = vma_start_addr;
883      bool first = true;
884
885      // Iterates over MemoryRegionMap until the iterator moves out of the VMA.
886      do {
887        if (!first) {
888          cursor = mmap_iter->end_addr;
889          ++mmap_iter;
890          // Don't break here even if mmap_iter == EndRegionLocked().
891
892          if (mmap_iter != MemoryRegionMap::EndRegionLocked()) {
893            deep_bucket = GetInformationOfMemoryRegion(
894                mmap_iter, memory_residence_info_getter, deep_profile);
895          }
896        }
897        first = false;
898
899        uint64 last_address_of_unhooked;
900        // If the next mmap entry is away from the current VMA.
901        if (mmap_iter == MemoryRegionMap::EndRegionLocked() ||
902            mmap_iter->start_addr > vma_last_addr) {
903          last_address_of_unhooked = vma_last_addr;
904        } else {
905          last_address_of_unhooked = mmap_iter->start_addr - 1;
906        }
907
908        if (last_address_of_unhooked + 1 > cursor) {
909          RAW_CHECK(cursor >= vma_start_addr,
910                    "Wrong calculation for unhooked");
911          RAW_CHECK(last_address_of_unhooked <= vma_last_addr,
912                    "Wrong calculation for unhooked");
913          uint64 committed_size = unhooked_[type].Record(
914              memory_residence_info_getter,
915              cursor,
916              last_address_of_unhooked,
917              mmap_dump_buffer);
918          vma_subtotal += committed_size;
919          if (mmap_dump_buffer) {
920            mmap_dump_buffer->AppendString("  ", 0);
921            mmap_dump_buffer->AppendPtr(cursor, 0);
922            mmap_dump_buffer->AppendString(" - ", 0);
923            mmap_dump_buffer->AppendPtr(last_address_of_unhooked + 1, 0);
924            mmap_dump_buffer->AppendString("  unhooked ", 0);
925            mmap_dump_buffer->AppendInt64(committed_size, 0);
926            mmap_dump_buffer->AppendString(" / ", 0);
927            mmap_dump_buffer->AppendInt64(
928                last_address_of_unhooked - cursor + 1, 0);
929            mmap_dump_buffer->AppendString("\n", 0);
930          }
931          cursor = last_address_of_unhooked + 1;
932        }
933
934        if (mmap_iter != MemoryRegionMap::EndRegionLocked() &&
935            mmap_iter->start_addr <= vma_last_addr &&
936            mmap_dump_buffer) {
937          bool trailing = mmap_iter->start_addr < vma_start_addr;
938          bool continued = mmap_iter->end_addr - 1 > vma_last_addr;
939          uint64 partial_first_address, partial_last_address;
940          if (trailing)
941            partial_first_address = vma_start_addr;
942          else
943            partial_first_address = mmap_iter->start_addr;
944          if (continued)
945            partial_last_address = vma_last_addr;
946          else
947            partial_last_address = mmap_iter->end_addr - 1;
948          uint64 committed_size = 0;
949          if (memory_residence_info_getter)
950            committed_size = memory_residence_info_getter->CommittedSize(
951                partial_first_address, partial_last_address, mmap_dump_buffer);
952          vma_subtotal += committed_size;
953          mmap_dump_buffer->AppendString(trailing ? " (" : "  ", 0);
954          mmap_dump_buffer->AppendPtr(mmap_iter->start_addr, 0);
955          mmap_dump_buffer->AppendString(trailing ? ")" : " ", 0);
956          mmap_dump_buffer->AppendString("-", 0);
957          mmap_dump_buffer->AppendString(continued ? "(" : " ", 0);
958          mmap_dump_buffer->AppendPtr(mmap_iter->end_addr, 0);
959          mmap_dump_buffer->AppendString(continued ? ")" : " ", 0);
960          mmap_dump_buffer->AppendString(" hooked ", 0);
961          mmap_dump_buffer->AppendInt64(committed_size, 0);
962          mmap_dump_buffer->AppendString(" / ", 0);
963          mmap_dump_buffer->AppendInt64(
964              partial_last_address - partial_first_address + 1, 0);
965          mmap_dump_buffer->AppendString(" @ ", 0);
966          if (deep_bucket != NULL) {
967            mmap_dump_buffer->AppendInt(deep_bucket->id, 0, false);
968          } else {
969            mmap_dump_buffer->AppendInt(0, 0, false);
970          }
971          mmap_dump_buffer->AppendString("\n", 0);
972        }
973      } while (mmap_iter != MemoryRegionMap::EndRegionLocked() &&
974               mmap_iter->end_addr - 1 <= vma_last_addr);
975    }
976
977    if (vma_total != vma_subtotal) {
978      char buffer[1024];
979      int written = procmaps_iter.FormatLine(buffer, sizeof(buffer),
980                                             vma_start_addr, vma_last_addr,
981                                             flags, offset, inode, filename, 0);
982      RAW_VLOG(0, "[%d] Mismatched total in VMA %" PRId64 ":"
983              "%" PRId64 " (%" PRId64 ")",
984              getpid(), vma_total, vma_subtotal, vma_total - vma_subtotal);
985      RAW_VLOG(0, "[%d]   in %s", getpid(), buffer);
986    }
987  }
988
989  // TODO(dmikurube): Investigate and fix http://crbug.com/189114.
990  //
991  // The total committed memory usage in all_ (from /proc/<pid>/maps) is
992  // sometimes smaller than the sum of the committed mmap'ed addresses and
993  // unhooked regions.  Within our observation, the difference was only 4KB
994  // in committed usage, zero in reserved virtual addresses
995  //
996  // A guess is that an uncommitted (but reserved) page may become committed
997  // during counting memory usage in the loop above.
998  //
999  // The difference is accounted as "ABSENT" to investigate such cases.
1000  //
1001  // It will be fixed when http://crbug.com/245603 finishes (no double count).
1002
1003  RegionStats all_total;
1004  RegionStats unhooked_total;
1005  for (int i = 0; i < NUMBER_OF_MAPS_REGION_TYPES; ++i) {
1006    all_total.AddAnotherRegionStat(all_[i]);
1007    unhooked_total.AddAnotherRegionStat(unhooked_[i]);
1008  }
1009
1010  size_t absent_virtual = profiled_mmap_.virtual_bytes() +
1011                          unhooked_total.virtual_bytes() -
1012                          all_total.virtual_bytes();
1013  if (absent_virtual > 0)
1014    all_[ABSENT].AddToVirtualBytes(absent_virtual);
1015
1016  size_t absent_committed = profiled_mmap_.committed_bytes() +
1017                            unhooked_total.committed_bytes() -
1018                            all_total.committed_bytes();
1019  if (absent_committed > 0)
1020    all_[ABSENT].AddToCommittedBytes(absent_committed);
1021}
1022
1023void DeepHeapProfile::GlobalStats::SnapshotAllocations(
1024    DeepHeapProfile* deep_profile) {
1025  profiled_malloc_.Initialize();
1026
1027  deep_profile->heap_profile_->address_map_->Iterate(RecordAlloc, deep_profile);
1028}
1029
1030void DeepHeapProfile::GlobalStats::Unparse(TextBuffer* buffer) {
1031  RegionStats all_total;
1032  RegionStats unhooked_total;
1033  for (int i = 0; i < NUMBER_OF_MAPS_REGION_TYPES; ++i) {
1034    all_total.AddAnotherRegionStat(all_[i]);
1035    unhooked_total.AddAnotherRegionStat(unhooked_[i]);
1036  }
1037
1038  // "# total (%lu) %c= profiled-mmap (%lu) + nonprofiled-* (%lu)\n"
1039  buffer->AppendString("# total (", 0);
1040  buffer->AppendUnsignedLong(all_total.committed_bytes(), 0);
1041  buffer->AppendString(") ", 0);
1042  buffer->AppendChar(all_total.committed_bytes() ==
1043                     profiled_mmap_.committed_bytes() +
1044                     unhooked_total.committed_bytes() ? '=' : '!');
1045  buffer->AppendString("= profiled-mmap (", 0);
1046  buffer->AppendUnsignedLong(profiled_mmap_.committed_bytes(), 0);
1047  buffer->AppendString(") + nonprofiled-* (", 0);
1048  buffer->AppendUnsignedLong(unhooked_total.committed_bytes(), 0);
1049  buffer->AppendString(")\n", 0);
1050
1051  // "                               virtual    committed"
1052  buffer->AppendString("", 26);
1053  buffer->AppendString(kVirtualLabel, 12);
1054  buffer->AppendChar(' ');
1055  buffer->AppendString(kCommittedLabel, 12);
1056  buffer->AppendString("\n", 0);
1057
1058  all_total.Unparse("total", buffer);
1059  all_[ABSENT].Unparse("absent", buffer);
1060  all_[FILE_EXEC].Unparse("file-exec", buffer);
1061  all_[FILE_NONEXEC].Unparse("file-nonexec", buffer);
1062  all_[ANONYMOUS].Unparse("anonymous", buffer);
1063  all_[STACK].Unparse("stack", buffer);
1064  all_[OTHER].Unparse("other", buffer);
1065  unhooked_total.Unparse("nonprofiled-total", buffer);
1066  unhooked_[ABSENT].Unparse("nonprofiled-absent", buffer);
1067  unhooked_[ANONYMOUS].Unparse("nonprofiled-anonymous", buffer);
1068  unhooked_[FILE_EXEC].Unparse("nonprofiled-file-exec", buffer);
1069  unhooked_[FILE_NONEXEC].Unparse("nonprofiled-file-nonexec", buffer);
1070  unhooked_[STACK].Unparse("nonprofiled-stack", buffer);
1071  unhooked_[OTHER].Unparse("nonprofiled-other", buffer);
1072  profiled_mmap_.Unparse("profiled-mmap", buffer);
1073  profiled_malloc_.Unparse("profiled-malloc", buffer);
1074}
1075
1076// static
1077void DeepHeapProfile::GlobalStats::RecordAlloc(const void* pointer,
1078                                               AllocValue* alloc_value,
1079                                               DeepHeapProfile* deep_profile) {
1080  uint64 address = reinterpret_cast<uintptr_t>(pointer);
1081  size_t committed = deep_profile->memory_residence_info_getter_->CommittedSize(
1082      address, address + alloc_value->bytes - 1, NULL);
1083
1084  DeepBucket* deep_bucket = deep_profile->deep_table_.Lookup(
1085      alloc_value->bucket(),
1086#if defined(TYPE_PROFILING)
1087      LookupType(pointer),
1088#endif
1089      /* is_mmap */ false);
1090  deep_bucket->committed_size += committed;
1091  deep_profile->stats_.profiled_malloc_.AddToVirtualBytes(alloc_value->bytes);
1092  deep_profile->stats_.profiled_malloc_.AddToCommittedBytes(committed);
1093}
1094
1095DeepHeapProfile::DeepBucket*
1096    DeepHeapProfile::GlobalStats::GetInformationOfMemoryRegion(
1097        const MemoryRegionMap::RegionIterator& mmap_iter,
1098        const MemoryResidenceInfoGetterInterface* memory_residence_info_getter,
1099        DeepHeapProfile* deep_profile) {
1100  size_t committed = deep_profile->memory_residence_info_getter_->
1101      CommittedSize(mmap_iter->start_addr, mmap_iter->end_addr - 1, NULL);
1102
1103  // TODO(dmikurube): Store a reference to the bucket in region.
1104  Bucket* bucket = MemoryRegionMap::GetBucket(
1105      mmap_iter->call_stack_depth, mmap_iter->call_stack);
1106  DeepBucket* deep_bucket = NULL;
1107  if (bucket != NULL) {
1108    deep_bucket = deep_profile->deep_table_.Lookup(
1109        bucket,
1110#if defined(TYPE_PROFILING)
1111        NULL,  // No type information for memory regions by mmap.
1112#endif
1113        /* is_mmap */ true);
1114    if (deep_bucket != NULL)
1115      deep_bucket->committed_size += committed;
1116  }
1117
1118  profiled_mmap_.AddToVirtualBytes(
1119      mmap_iter->end_addr - mmap_iter->start_addr);
1120  profiled_mmap_.AddToCommittedBytes(committed);
1121
1122  return deep_bucket;
1123}
1124
1125// static
1126void DeepHeapProfile::WriteProcMaps(const char* prefix,
1127                                    char raw_buffer[],
1128                                    int buffer_size) {
1129  char filename[100];
1130  snprintf(filename, sizeof(filename),
1131           "%s.%05d.maps", prefix, static_cast<int>(getpid()));
1132
1133  RawFD fd = RawOpenForWriting(filename);
1134  RAW_DCHECK(fd != kIllegalRawFD, "");
1135
1136  int length;
1137  bool wrote_all;
1138  length = tcmalloc::FillProcSelfMaps(raw_buffer, buffer_size, &wrote_all);
1139  RAW_DCHECK(wrote_all, "");
1140  RAW_DCHECK(length <= buffer_size, "");
1141  RawWrite(fd, raw_buffer, length);
1142  RawClose(fd);
1143}
1144#else  // USE_DEEP_HEAP_PROFILE
1145
1146DeepHeapProfile::DeepHeapProfile(HeapProfileTable* heap_profile,
1147                                 const char* prefix,
1148                                 enum PageFrameType pageframe_type)
1149    : heap_profile_(heap_profile) {
1150}
1151
1152DeepHeapProfile::~DeepHeapProfile() {
1153}
1154
1155void DeepHeapProfile::DumpOrderedProfile(const char* reason,
1156                                         char raw_buffer[],
1157                                         int buffer_size,
1158                                         RawFD fd) {
1159}
1160
1161#endif  // USE_DEEP_HEAP_PROFILE
1162