components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/stl_allocator.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 COMPONENTS_METRICS_LEAK_DETECTOR_STL_ALLOCATOR_H_
+#define COMPONENTS_METRICS_LEAK_DETECTOR_STL_ALLOCATOR_H_
+
+#include <stddef.h>
+
+#include "base/logging.h"
+
+// Generic allocator class for STL objects
+// that uses a given type-less allocator Alloc, which must provide:
+//   static void* Alloc::Allocate(size_t size);
+//   static void Alloc::Free(void* ptr, size_t size);
+//
+// STL_Allocator<T, MyAlloc> provides the same thread-safety
+// guarantees as MyAlloc.
+//
+// Usage example:
+//   set<T, less<T>, STL_Allocator<T, MyAlloc> > my_set;
+// CAVEAT: Parts of the code below are probably specific
+//         to the STL version(s) we are using.
+//         The code is simply lifted from what std::allocator<> provides.
+template <typename T, class Alloc>
+class STL_Allocator {
+ public:
+  typedef size_t     size_type;
+  typedef ptrdiff_t  difference_type;
+  typedef T*         pointer;
+  typedef const T*   const_pointer;
+  typedef T&         reference;
+  typedef const T&   const_reference;
+  typedef T          value_type;
+
+  template <class T1> struct rebind {
+    typedef STL_Allocator<T1, Alloc> other;
+  };
+
+  STL_Allocator() {}
+  STL_Allocator(const STL_Allocator&) {}

[jar (doing other things), 2015/08/21 02:48:43]

nit: explicit?

[Simon Que, 2015/08/21 21:59:20]

Done.

+  template <class T1> STL_Allocator(const STL_Allocator<T1, Alloc>&) {}
+  ~STL_Allocator() {}
+
+  pointer address(reference x) const { return &x; }
+  const_pointer address(const_reference x) const { return &x; }
+
+  pointer allocate(size_type n, const void* = 0) {
+    // Make sure the computation of the total allocation size does not cause an
+    // integer overflow.
+    RAW_CHECK((n * sizeof(T)) / sizeof(T) == n);

[jar (doing other things), 2015/08/21 02:48:43]

nit: Clearer and faster is probably:

n <= max_size()

[Simon Que, 2015/08/21 05:44:05]

That wouldn't catch the overflow of |n * sizeof(T)|, which is the value passed
to Allocate().

[jar (doing other things), 2015/08/21 17:32:31]

I must be missing something.  Isn't max_size() the largest legal value?

[Simon Que, 2015/08/21 21:59:20]

How could size_t n be > max_size()? Checking n <= max_size() is always going to
pass.

OTOH, suppose you have a 32-bit system with size_t = 32 bits. If you tried to
allocate N=2^24 copies of a struct of size 256, you'd be attempting to allocate
a total of N * 256 = 2^32 bytes. That is not possible because multiplying the
two would result in an overflow. And to check for this overflow:

  (n * sizeof(T)) / sizeof(T) == n

[jar (doing other things), 2015/08/22 00:21:47]

max_size() is defined on line 56 below.  It is the result of dividing the
largest size_t by sizeof(T).  So long as n is less than this value, the product
with sizeof(T) will always avoid an overflow (in a size_t capable variable).

What am I missing?

[Simon Que, 2015/08/23 23:30:53]

Done.

+    return static_cast<T*>(Alloc::Allocate(n * sizeof(T)));
+  }
+  void deallocate(pointer p, size_type n) { Alloc::Free(p, n * sizeof(T)); }
+
+  size_type max_size() const { return size_t(-1) / sizeof(T); }

[jar (doing other things), 2015/08/21 02:48:43]

Rather than size_t(-1), you should probably use
std::numeric_limits<size_t>::max()

[Simon Que, 2015/08/21 21:59:20]

Done.

+
+  void construct(pointer p, const T& val) { ::new(p) T(val); }
+  void construct(pointer p) { ::new(p) T(); }
+  void destroy(pointer p) { p->~T(); }
+
+  // There's no state, so these allocators always return the same value.
+  bool operator==(const STL_Allocator&) const { return true; }
+  bool operator!=(const STL_Allocator&) const { return false; }
+};
+
+#endif  // COMPONENTS_METRICS_LEAK_DETECTOR_STL_ALLOCATOR_H_