[Tracing] Add allocation register for heap profiling

base/trace_event/memory_profiler_allocation_register.h

Index: base/trace_event/memory_profiler_allocation_register.h
diff --git a/base/trace_event/memory_profiler_allocation_register.h b/base/trace_event/memory_profiler_allocation_register.h
new file mode 100644
index 0000000000000000000000000000000000000000..f7516bdd058ca8ee2f4cf75688010fa4cc9f716a
--- /dev/null
+++ b/base/trace_event/memory_profiler_allocation_register.h
@@ -0,0 +1,156 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_REGISTER_H_
+#define BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_REGISTER_H_
+
+#include <stdint.h>
+
+#include "base/logging.h"
+#include "base/trace_event/memory_profiler_allocation_context.h"
+
+namespace base {
+namespace trace_event {
+
+// The allocation register keeps track of all allocations that have not been
+// freed. It is an mmap-backed hash table that stores size and context indexed

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

nit: s/an mmap/a mmap/

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Changed to “a memory map-backed” to avoid all ambiguity.

+// by address. The hash table is tailored specifically for this use case. The
+// common case is that an entry is inserted and removed after a while, lookup
+// without modifying the table is not an intended use case. The hash table is
+// implemented as an array of linked lists. The size of this array is fixed,
+// but it does not limit the amount of entries that can be stored.
+//
+// Replaying a recording of Chrome's allocations and frees against this hash
+// table takes about 15% of the time that it takes to replay them against
+// |std::map|.
+class BASE_EXPORT AllocationRegister {
+ public:
+  // An entry in the hash table; contains the details about an allocation.

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

Hmm not really (w.r.t. comment). The real entry here is Cell. Allocation is the
public-facing information stored

[Ruud van Asseldonk, 2015/10/06 15:44:35]

To me, an entry is the thing you put in / get out, |Cell| is an implementation
detail. Changed the comment.

+  struct Allocation {
+    void* address;
+    size_t size;
+    AllocationContext context;
+  };
+
+  // An iterator that iterates entries in the hash table efficiently, but in no
+  // particular order. It can do this by iterating the cells and ignoring the
+  // linked lists altogether. Instead of checking whether a cell is in the free
+  // list to see if it should be skipped, a null address is used to indicate
+  // that a cell is free.
+  class ConstIterator {
+   public:
+    void operator++();
+    bool operator!=(const ConstIterator& other) const;
+    const Allocation& operator*() const;
+
+   private:
+    friend class AllocationRegister;
+    using CellIndex = uint32_t;
+
+    ConstIterator(const AllocationRegister& alloc_register, CellIndex index);
+
+    const AllocationRegister& register_;
+    CellIndex index_;
+  };
+
+  AllocationRegister();
+  ~AllocationRegister();
+
+  // Inserts the address, size and context into the table. If the address was

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

I'd just say "Inserts an allocation and its metadata into the table"
so you don't have to keep the comment updated if you add more stuff

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done.

+  // present already, the size and context are updated. |address| must not be
+  // null. (This is because null is used to mark free cells, to allow efficient
+  // iteration of the hash table.)
+  void Insert(void* address, size_t size, AllocationContext context);
+
+  // Removes the address from the table if it is present. It is ok to call this
+  // with a null pointer.
+  void Remove(void* address);
+
+  ConstIterator begin() const;
+  ConstIterator end() const;
+
+ private:
+  friend class AllocationRegisterTest;
+  using CellIndex = uint32_t;
+
+  // A cell can store allocation details (size and context) by address. Cells
+  // are part of a linked list via the |next| member. This list is either the
+  // list for a particular hash, or the free list. All cells are contiguous in
+  // memory in one big array. Therefore, on 64-bit systems, space can be saved
+  // by storing 32-bit indices instead of pointers as links. Index 0 is used as
+  // the list terminator. Address, size and context are not stored directly but

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

I'd remove the latter sentence, in the beginning it was a bit confusing.
For a moment I though that address, size and context were not part of the memory
record of Cell, which is not true. You are just saying taht you are
encapsulating, but IMHO there is no actual need for a comment.

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done.

+  // wrapped in |Allocation| to avoid exposing implementation details via the
+  // iterator.
+  struct Cell {
+    CellIndex next;
+    Allocation allocation;
+  };
+
+  // Returns a value in the range [0, kNumBuckets - 1] (inclusive).
+  uint32_t Hash(void* address);

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

shouldn't this be a static method?

[Ruud van Asseldonk, 2015/10/06 15:44:35]

It can be, yes.

+
+  // Returns a pointer to the variable that contains or should contain the
+  // index of the cell that stores the entry for |address|. The pointer may
+  // point at an element of |buckets_| or at the |next| member of an element of
+  // |cells_|. If the value pointed at is 0, |address| is not in the table.
+  CellIndex* Lookup(void* address);
+
+  // Returns the index of a cell that is not being used to store an entry.

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

Probably want to make this comment a bit stronger to highlight the fact that
this operation is not idempotent and every time carves out a new cell. Something
like "Acquires a new cell, either from the freelist or bumping up the
water-mark, and returns its index"

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done.

+  CellIndex GetFreeCell();
+
+  // Allocates a region of virtual address space of |min_size| rounded up to the
+  // system page size. The memory is zeroed by the system. A guard page is added
+  // after the end.
+  static void* AllocateVirtualMemory(size_t min_size);

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

plz move static methods before other non-static methods

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

I'd just call the 2nd method size, just because then FreeVirtualMemory's
signature becomes clearer.

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done. At least I grouped all the static methods together this time ...
Done.

+
+  // Frees a region of virtual address space allocated by a call to
+  // |AllocateVirtualMemory|.
+  static void FreeVirtualMemory(void* address, size_t allocated_min_size);
+
+  // The number of buckets, 2^18, approximately 260 000, has been tuned for
+  // Chrome's typical number of outstanding allocations. (This number varies
+  // between processes. Most processes have a sustained load of ~30k unfreed
+  // allocations, but some processes have peeks around 100k-400k allocations.)
+  // Because of the size of the table, it is likely that every |buckets_|
+  // access and every |cells_| access will incur a cache miss. Microbenchmarks
+  // suggest that it is worthwile to use more memory for the table to avoid
+  // chasing down the linked list, until the size is 2^18. The number of buckets
+  // is a power of two so modular indexing can be done with bitwise and.
+  const uint32_t kNumBuckets = 0x40000;

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

move these constants up to line 93. From
https://google-styleguide.googlecode.com/svn/trunk/cppguide.html#Declaration_...

Within each section, the declarations generally should be in the following
order:

Typedefs and Enums
Constants (static const data members)
Constructors
Destructor
Methods, including static methods
Data Members (except static const data members)

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done.

+  const uint32_t kNumBucketsMask = kNumBuckets - 1;
+
+  // Reserve address space to store at most this number of entries. High
+  // capacity does not imply high memory usage due to the access pattern. The
+  // only constraint on the number of cells is that on 32-bit systems address
+  // space is scarce (i.e. reserving 2GiB of address space for the entries is
+  // not an option). A value of ~3M entries is large enough to handle spikes in
+  // the number of allocations, and modest enough to require no more than a few
+  // dozens of MiB of address space.
+  const uint32_t kNumCells = kNumBuckets * 10;
+
+  // The array of cells. This array is backed by mmapped memory. Lower indices
+  // are accessed first, higher indices are only accessed when required. In
+  // this way, even if a huge amount of address space has been mmapped, only
+  // the cells that are actually used will be backed by physical memory.
+  Cell* const cells_;
+
+  // The array of indices into |cells_|. |buckets_[Hash(address)]| will contain
+  // the index of the head of the linked list for |Hash(key)|. A value of 0
+  // indicates an empty list. This array is backed by mmapped memory.
+  CellIndex* const buckets_;
+
+  // The head of the free list. This is the index of the cell. A value of 0
+  // means that the free list is empty.
+  CellIndex free_list_;
+
+  // The index of the first element of |cells_| that has not been used before.
+  // If the free list is empty and a new cell is needed, the cell at this index
+  // is used. This is the high water mark for the number of entries stored.
+  CellIndex next_unused_cell_;
+};
+
+}  // namespace trace_event
+}  // namespace base
+
+#endif  // BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_REGISTER_H_