On heap tracking datastructure overflow, degrade instead of CHECK()

base/trace_event/heap_profiler_allocation_register.h

 // 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_HEAP_PROFILER_ALLOCATION_REGISTER_H_
 #define BASE_TRACE_EVENT_HEAP_PROFILER_ALLOCATION_REGISTER_H_
 
 #include <stddef.h>
 #include <stdint.h>
 
@@ skipping 30 matching lines @@
   // To keep things simple we don't call destructors.
   static_assert(is_trivially_destructible<Key>::value &&
                     is_trivially_destructible<Value>::value,
                 "Key and Value shouldn't have destructors");
  public:
   using KVPair = std::pair<const Key, Value>;
 
   // For implementation simplicity API uses integer index instead
   // of iterators. Most operations (except Find) on KVIndex are O(1).
   using KVIndex = size_t;
-  static const KVIndex kInvalidKVIndex = static_cast<KVIndex>(-1);
+  enum { kInvalidKVIndex = static_cast<KVIndex>(-1) };

[Primiano Tucci (use gerrit), 2017/03/31 19:05:47]

unfortunately now we are one bug out and one bug in.
Apparently  this is not enough for MSVC.
See also crbug.com/707288

enum : KVIndex { ...} seems to do the trick

 
   // Capacity controls how many items this hash map can hold, and largely
   // affects memory footprint.
   FixedHashMap(size_t capacity)
-    : num_cells_(capacity),
-      cells_(static_cast<Cell*>(
-          AllocateGuardedVirtualMemory(num_cells_ * sizeof(Cell)))),
-      buckets_(static_cast<Bucket*>(
-          AllocateGuardedVirtualMemory(NumBuckets * sizeof(Bucket)))),
-      free_list_(nullptr),
-      next_unused_cell_(0) {}
+      : num_cells_(capacity),
+        num_inserts_dropped_(0),
+        cells_(static_cast<Cell*>(
+            AllocateGuardedVirtualMemory(num_cells_ * sizeof(Cell)))),
+        buckets_(static_cast<Bucket*>(
+            AllocateGuardedVirtualMemory(NumBuckets * sizeof(Bucket)))),
+        free_list_(nullptr),
+        next_unused_cell_(0) {}
 
   ~FixedHashMap() {
     FreeGuardedVirtualMemory(cells_, num_cells_ * sizeof(Cell));
     FreeGuardedVirtualMemory(buckets_, NumBuckets * sizeof(Bucket));
   }
 
+  // Returns {kInvalidKVIndex, false} if the table is full.
   std::pair<KVIndex, bool> Insert(const Key& key, const Value& value) {
     Cell** p_cell = Lookup(key);
     Cell* cell = *p_cell;
     if (cell) {
       return {static_cast<KVIndex>(cell - cells_), false};  // not inserted
     }
 
     // Get a free cell and link it.
-    *p_cell = cell = GetFreeCell();
+    cell = GetFreeCell();
+    if (!cell) {
+      if (num_inserts_dropped_ <
+          std::numeric_limits<decltype(num_inserts_dropped_)>::max()) {
+        ++num_inserts_dropped_;
+      }
+      return {kInvalidKVIndex, false};
+    }
+    *p_cell = cell;
     cell->p_prev = p_cell;
     cell->next = nullptr;
 
     // Initialize key/value pair. Since key is 'const Key' this is the
     // only way to initialize it.
     new (&cell->kv) KVPair(key, value);
 
     return {static_cast<KVIndex>(cell - cells_), true};  // inserted
   }
 
@@ skipping 42 matching lines @@
 
   // Estimates number of bytes used in allocated memory regions.
   size_t EstimateUsedMemory() const {
     size_t page_size = base::GetPageSize();
     // |next_unused_cell_| is the first cell that wasn't touched, i.e.
     // it's the number of touched cells.
     return bits::Align(sizeof(Cell) * next_unused_cell_, page_size) +
            bits::Align(sizeof(Bucket) * NumBuckets, page_size);
   }
 
+  size_t num_inserts_dropped() const { return num_inserts_dropped_; }
+
  private:
   friend base::trace_event::AllocationRegisterTest;
 
   struct Cell {
     KVPair kv;
     Cell* next;
 
     // Conceptually this is |prev| in a doubly linked list. However, buckets
     // also participate in the bucket's cell list - they point to the list's
     // head and also need to be linked / unlinked properly. To treat these two
@@ skipping 18 matching lines @@
     // Chase down the list until the cell that holds |key| is found,
     // or until the list ends.
     while (*p_cell && (*p_cell)->kv.first != key) {
       p_cell = &(*p_cell)->next;
     }
 
     return p_cell;
   }
 
   // Returns a cell that is not being used to store an entry (either by
-  // recycling from the free list or by taking a fresh cell).
+  // recycling from the free list or by taking a fresh cell). May return
+  // nullptr if the hash table has run out of memory.
   Cell* GetFreeCell() {
     // First try to re-use a cell from the free list.
     if (free_list_) {
       Cell* cell = free_list_;
       free_list_ = cell->next;
       return cell;
     }
 
+    // If the hash table has too little capacity (when too little address space
+    // was reserved for |cells_|), return nullptr.
+    if (next_unused_cell_ >= num_cells_) {
+      return nullptr;
+    }
+
     // Otherwise pick the next cell that has not been touched before.
-    size_t idx = next_unused_cell_;
-    next_unused_cell_++;
-
-    // If the hash table has too little capacity (when too little address space
-    // was reserved for |cells_|), |next_unused_cell_| can be an index outside
-    // of the allocated storage. A guard page is allocated there to crash the
-    // program in that case. There are alternative solutions:
-    // - Deal with it, increase capacity by reallocating |cells_|.
-    // - Refuse to insert and let the caller deal with it.
-    // Because free cells are re-used before accessing fresh cells with a higher
-    // index, and because reserving address space without touching it is cheap,
-    // the simplest solution is to just allocate a humongous chunk of address
-    // space.
-
-    CHECK_LT(next_unused_cell_, num_cells_ + 1)
-        << "Allocation Register hash table has too little capacity. Increase "
-           "the capacity to run heap profiler in large sessions.";
-
-    return &cells_[idx];
+    return &cells_[next_unused_cell_++];
   }
 
   // Returns a value in the range [0, NumBuckets - 1] (inclusive).
   size_t Hash(const Key& key) const {
     if (NumBuckets == (NumBuckets & ~(NumBuckets - 1))) {
       // NumBuckets is a power of 2.
       return KeyHasher()(key) & (NumBuckets - 1);
     } else {
       return KeyHasher()(key) % NumBuckets;
     }
   }
 
   // Number of cells.
   size_t const num_cells_;
 
+  // Number of calls to Insert() that were lost because the hashtable was full.
+  size_t num_inserts_dropped_;
+
   // The array of cells. This array is backed by mmapped memory. Lower indices
   // are accessed first, higher indices are accessed only when the |free_list_|
   // is empty. This is to minimize the amount of resident memory used.
   Cell* const cells_;
 
   // The array of buckets (pointers into |cells_|). |buckets_[Hash(key)]| will
   // contain the pointer to the linked list of cells for |Hash(key)|.
   // This array is backed by mmapped memory.
   mutable Bucket* buckets_;
 
@@ skipping 43 matching lines @@
     AllocationIndex index_;
   };
 
   AllocationRegister();
   AllocationRegister(size_t allocation_capacity, size_t backtrace_capacity);
 
   ~AllocationRegister();
 
   // Inserts allocation details into the table. If the address was present
   // already, its details are updated. |address| must not be null.
-  void Insert(const void* address,
+  //
+  // Returns true if an insert occurred. Inserts may fail because the table
+  // is full.
+  bool Insert(const void* address,
               size_t size,
               const AllocationContext& context);
 
   // Removes the address from the table if it is present. It is ok to call this
   // with a null pointer.
   void Remove(const void* address);
 
   // Finds allocation for the address and fills |out_allocation|.
   bool Get(const void* address, Allocation* out_allocation) const;
 
@@ skipping 63 matching lines @@
   AllocationMap allocations_;
   BacktraceMap backtraces_;
 
   DISALLOW_COPY_AND_ASSIGN(AllocationRegister);
 };
 
 }  // namespace trace_event
 }  // namespace base
 
 #endif  // BASE_TRACE_EVENT_HEAP_PROFILER_ALLOCATION_REGISTER_H_