Create "persistent memory allocator" for persisting and sharing objects.

base/metrics/persistent_memory_allocator.h

Index: base/metrics/persistent_memory_allocator.h
diff --git a/base/metrics/persistent_memory_allocator.h b/base/metrics/persistent_memory_allocator.h
new file mode 100644
index 0000000000000000000000000000000000000000..0b0fb5567749a538ccf252da4e73c4719b1f422e
--- /dev/null
+++ b/base/metrics/persistent_memory_allocator.h
@@ -0,0 +1,328 @@
+// Copyright (c) 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_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_
+#define BASE_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_
+
+#include <stdint.h>
+#include <atomic>
+#include <string>
+
+#include "base/atomicops.h"
+#include "base/base_export.h"
+#include "base/gtest_prod_util.h"
+#include "base/macros.h"
+#include "base/memory/scoped_ptr.h"
+
+namespace base {
+
+class HistogramBase;
+class MemoryMappedFile;
+
+// Simple allocator for pieces of a memory block that may be persistent
+// to some storage or shared across multiple processes. This class resides
+// under base/metrics because it was written for that purpose. It is,
+// however, fully general-purpose and can be freely moved to base/memory
+// if other uses are found.
+//
+// This class provides for thread-secure (i.e. safe against other threads
+// or processes that may be compromised and thus have malicious intent)
+// allocation of memory within a designated block and also a mechanism by
+// which other threads can learn of these allocations.
+//
+// There is (currently) no way to release an allocated block of data because
+// doing so would risk invalidating pointers held by other processes and
+// greatly complicate the allocation algorithm.
+//
+// Construction of this object can accept new, clean (i.e. zeroed) memory
+// or previously initialized memory. In the first case, construction must
+// be allowed to complete before letting other allocators attach to the same
+// segment. In other words, don't share the segment until at least one
+// allocator has been attached to it.
+//
+// Note that memory not in active use is not accessed so it is possible to
+// use virtual memory, including memory-mapped files, as backing storage with
+// the OS "pinning" new (zeroed) physical RAM pages only as they are needed.
+class BASE_EXPORT PersistentMemoryAllocator {
+ public:
+  typedef uint32_t Reference;
+
+  // Internal state information when iterating over memory allocations.
+  class Iterator {
+   public:
+    Iterator() : last(0) {}
+
+    bool operator==(const Iterator& rhs) const { return last == rhs.last; }
+    bool operator!=(const Iterator& rhs) const { return last != rhs.last; }
+
+    void clear() { last = 0; }
+    bool is_clear() const { return last == 0; }
+
+   private:
+    friend class PersistentMemoryAllocator;
+
+    Reference last;
+    uint32_t niter;
+  };
+
+  // Returned information about the internal state of the heap.
+  struct MemoryInfo {
+    size_t total;
+    size_t free;
+  };
+
+  enum : uint32_t {
+    kTypeIdAny = 0  // Match any type-id inside GetAsObject().
+  };
+
+  // The allocator operates on any arbitrary block of memory. Creation and
+  // persisting or sharing of that block with another process is the
+  // responsibility of the caller. The allocator needs to know only the
+  // block's |base| address, the total |size| of the block, and any internal
+  // |page| size (zero if not paged) across which allocations should not span.
+  // The |id| is an arbitrary value the caller can use to identify a
+  // particular memory segment. It will only be loaded during the initial
+  // creation of the segment and can be checked by the caller for consistency.
+  // The |name|, if provided, is used to distinguish histograms for this
+  // allocator. Only the primary owner of the segment should define this value;
+  // other processes can learn it from the shared state. If the underlying
+  // memory is |readonly| then no changes will be made to it. The resulting
+  // object should be stored as a "const" pointer.
+  //
+  // PersistentMemoryAllocator does NOT take ownership of the memory block.
+  // The caller must manage it and ensure it stays available throughout the
+  // lifetime of this object.
+  //
+  // Memory segments for sharing must have had an allocator attached to them
+  // before actually being shared. If the memory segment was just created, it
+  // should be zeroed before being passed here. If it was an existing segment,
+  // the values here will be compared to copies stored in the shared segment
+  // as a guard against corruption.
+  //
+  // Make sure that the memory segment is acceptable (see IsMemoryAcceptable()
+  // method below) before construction if the definition of the segment can
+  // vary in any way at run-time. Invalid memory segments will cause a crash.
+  PersistentMemoryAllocator(void* base, size_t size, size_t page_size,
+                            uint32_t id, const std::string& name,
+                            bool readonly);
+  virtual ~PersistentMemoryAllocator();
+
+  // Check if memory segment is acceptable for creation of an Allocator. This
+  // doesn't do any analysis of the data and so doesn't guarantee that the
+  // contents are valid, just that the pramaters won't cause the program to

[chrisha, 2016/01/18 22:40:28]

parameters*

[bcwhite, 2016/01/19 19:49:40]

Done.

+  // abort. The IsCorrupt() method will report detection of data problems
+  // found during construction and general operation.
+  static bool IsMemoryAcceptable(const void* data, size_t size,
+                                 size_t page_size, bool readonly);
+
+  // Get the internal identifier for this persistent memory segment.
+  uint32_t Id() const;
+
+  // Get the internal name of this allocator (possibly an empty string).
+  const char* Name() const;
+
+  // Is this segment open only for read?
+  bool IsReadonly() { return readonly_; }
+
+  // Create histograms for tracking memory use and allocation sizes. This
+  // is done seperately from construction for situations such as when the
+  // histograms will be backed my memory provided by this very allocator.

[chrisha, 2016/01/18 22:40:28]

backed by*

[bcwhite, 2016/01/19 19:49:40]

Done.

+  void CreateHistograms(const std::string& name);

[chrisha, 2016/01/18 22:40:28]

I'm not sure I follow what this does? CreateHistograms, plural, but only a
single name is passed in? No bucket sizes? No other details?

If these have implicit sizes, etc, for tracking internal usage, maybe make that
a little more explicit in this comment?

The function name is also very generic and could be made more specific.

[bcwhite, 2016/01/19 19:49:40]

Done.

+
+  // Direct access to underlying memory segment. If the segment is shared
+  // across threads or processes, reading data through these values does
+  // not guarantee consistency. Use with care. Do not write.
+  const void* data() const { return const_cast<const char*>(mem_base_); }
+  size_t length() const { return mem_size_; }
+  size_t used() const;
+
+  // Get an object referenced by a |ref|. For safety reasons, the |type_id|
+  // code and size-of(|T|) are compared to ensure the reference is valid
+  // and cannot return an object outside of the memory segment. A |type_id| of
+  // zero will match any though the size is still checked. NULL is returned

[chrisha, 2016/01/18 22:40:28]

kTypeIdAny

[bcwhite, 2016/01/19 19:49:40]

Done.

+  // if any problem is detected, such as corrupted storage or incorrect
+  // parameters. Callers MUST check that the returned value is not-null EVERY
+  // TIME before accessing it or risk crashing!  Once dereferenced, the pointer

[chrisha, 2016/01/18 22:40:28]

Remove double space after .

[bcwhite, 2016/01/19 19:49:40]

Done.

+  // is safe to reuse forever.
+  //
+  // NOTE: Though this method will guarantee that an object of the specified
+  // type can be accessed without going outside the bounds of the memory
+  // segment, it makes no guarantees of the validity of the data within the
+  // object itself. If it is expected that the contents of the segment could
+  // be compromised with malicious intent, the object must be hardened as well.
+  //
+  // Though the persistent data may be "volatile" if it is shared with
+  // other processes, such is not necessarily the case. The internal
+  // "volatile" designation is discarded so as to not propagate the viral
+  // nature of that keyword to the caller. It can add it back, if necessary,
+  // based on knowledge of how the allocator is being used.
+  template <typename T>
+  T* GetAsObject(Reference ref, uint32_t type_id) {
+    static_assert(!std::is_polymorphic<T>::value, "no polymorphic objects");
+    return const_cast<T*>(
+        reinterpret_cast<volatile T*>(GetBlockData(ref, type_id, sizeof(T))));
+  }
+  template <typename T>
+  const T* GetAsObject(Reference ref, uint32_t type_id) const {
+    static_assert(!std::is_polymorphic<T>::value, "no polymorphic objects");
+    return const_cast<const T*>(
+        reinterpret_cast<const volatile T*>(GetBlockData(
+            ref, type_id, sizeof(T))));
+  }
+
+  // Get the number of bytes allocated to a block. This is useful when storing
+  // arrays in order to validate the ending boundary. The returned value will
+  // include any padding added to achieve the required alignment and so could
+  // be larger than given in the original Allocate() request.
+  size_t GetAllocSize(Reference ref) const;
+
+  // Access the internal "type" of an object. This generally isn't necessary
+  // but can be used to "clear" the type and so effectively mark it as deleted
+  // even though the memory stays valid and allocated.
+  uint32_t GetType(Reference ref) const;
+  void SetType(Reference ref, uint32_t type_id);
+
+  // Reserve space in the memory segment of the desired |size| and |type_id|.
+  // A return value of zero indicates the allocation failed, otherwise the
+  // returned reference can be used by any process to get a real pointer via
+  // the GetAsObject() call.
+  Reference Allocate(size_t size, uint32_t type_id);
+
+  // Allocated objects can be added to an internal list that can then be
+  // iterated over by other processes. If an allocated object can be found
+  // another way, such as by having its reference within a different object
+  // that will be made iterable, then this call is not necessary. This always
+  // succeeds unless corruption is detected; check IsCorrupted() to find out.
+  // Once an object is made iterable, its position in iteration can never
+  // change; new iterable objects will always be added after it in the series.
+  void MakeIterable(Reference ref);
+
+  // Get the information about the amount of free space in the allocator. The
+  // amount of free space should be treated as approximate due to extras from
+  // alignment and metadata. Concurrent allocations from other threads will
+  // also make the true amount less than what is reported.
+  void GetMemoryInfo(MemoryInfo* meminfo) const;
+
+  // Iterating uses a |state| structure (initialized by CreateIterator) and
+  // returns both the reference to the object as well as the |type_id| of
+  // that object. A zero return value indicates there are currently no more
+  // objects to be found but future attempts can be made without having to
+  // reset the iterator to "first". Creating an iterator |starting_after|
+  // a known iterable object allows "resume" from that point.
+  void CreateIterator(Iterator* state) const { CreateIterator(state, 0); };
+  void CreateIterator(Iterator* state, Reference starting_after) const;

[chrisha, 2016/01/18 22:40:28]

Not clear if the object pointer to by |starting_after| will be visited as the
first item in the iteration... this is consistent with typical iterator
semantics and the comment, but the name leads one to believe that the iteration
will first visit the item following it. Clarify the comment and/or name?

[bcwhite, 2016/01/19 19:49:40]

Done.

+  Reference GetNextIterable(Iterator* state, uint32_t* type_id) const;
+
+  // If there is some indication that the memory has become corrupted,
+  // calling this will attempt to prevent further damage by indicating to
+  // all processes that something is not as expected.
+  void SetCorrupt() const;
+
+  // This can be called to determine if corruption has been detected in the
+  // segment, possibly my a malicious actor. Once detected, future allocations
+  // will fail and iteration may not locate all objects.
+  bool IsCorrupt() const;
+
+  // Flag set if an allocation has failed because the memory segment was full.
+  bool IsFull() const;
+
+  // Update static-state histograms. This should be called on a periodic basis
+  // to record such things as how much of the total space is used.
+  void UpdateStaticHistograms();

[chrisha, 2016/01/18 22:40:28]

Maybe rename CreateHistograms above to CreateStaticHistograms?

[bcwhite, 2016/01/19 19:49:40]

Static referred to those that don't get updated automatically.  Names and
comment updated.

+
+ protected:
+  volatile char* const mem_base_;  // Memory base. (char so sizeof guaranteed 1)
+  const uint32_t mem_size_;        // Size of entire memory segment.
+  const uint32_t mem_page_;        // Page size allocations shouldn't cross.
+
+ private:
+  struct SharedMetadata;
+  struct BlockHeader;
+  static const Reference kReferenceQueue;
+  static const Reference kReferenceNull;
+
+  // The shared metadata is always located at the top of the memory segment.
+  // These convenience functions eliminate constant casting of the base
+  // pointer within the code.
+  const volatile SharedMetadata* shared_meta() const {
+    return reinterpret_cast<const volatile SharedMetadata*>(mem_base_);
+  }
+  volatile SharedMetadata* shared_meta() {
+    return reinterpret_cast<volatile SharedMetadata*>(mem_base_);
+  }
+
+  // Actual method for doing the allocation.
+  Reference AllocateImpl(size_t size, uint32_t type_id);
+
+  // Get the block header associated with a specific reference.
+  const volatile BlockHeader* GetBlock(Reference ref, uint32_t type_id,
+                                       uint32_t size, bool queue_ok,
+                                       bool free_ok) const;
+  volatile BlockHeader* GetBlock(Reference ref, uint32_t type_id, uint32_t size,
+                                 bool queue_ok, bool free_ok) {
+      return const_cast<volatile BlockHeader*>(
+          const_cast<const PersistentMemoryAllocator*>(this)->GetBlock(
+              ref, type_id, size, queue_ok, free_ok));
+  }
+
+  // Get the actual data within a block associated with a specific reference.
+  const volatile void* GetBlockData(Reference ref, uint32_t type_id,
+                                    uint32_t size) const;
+  volatile void* GetBlockData(Reference ref, uint32_t type_id,
+                              uint32_t size) {
+      return const_cast<volatile void*>(
+          const_cast<const PersistentMemoryAllocator*>(this)->GetBlockData(
+              ref, type_id, size));
+  }
+
+  const bool readonly_;              // Indicates access to read-only memory.
+  std::atomic<bool> corrupt_;        // Local version of "corrupted" flag.
+
+  HistogramBase* allocs_histogram_;  // Histogram recording allocs.
+  HistogramBase* used_histogram_;    // Histogram recording used space.
+
+  FRIEND_TEST_ALL_PREFIXES(PersistentMemoryAllocatorTest, AllocateAndIterate);
+  DISALLOW_COPY_AND_ASSIGN(PersistentMemoryAllocator);
+};
+
+
+// This allocator uses a local memory block it allocates from the general
+// heap. It is generally used when some kind of "death rattle" handler will
+// save the contents to persistent storage during process shutdown. It is
+// also useful for testing.
+class BASE_EXPORT LocalPersistentMemoryAllocator
+    : public PersistentMemoryAllocator {
+ public:
+  LocalPersistentMemoryAllocator(size_t size, uint32_t id,
+                                 const std::string& name);
+  ~LocalPersistentMemoryAllocator() override;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LocalPersistentMemoryAllocator);
+};
+
+
+// This allocator takes a memory-mapped file object and performs allocation
+// from it. The allocator takes ownership of the file object. Only read access
+// is provided due to limitions of the MemoryMappedFile class.
+class BASE_EXPORT FilePersistentMemoryAllocator

[chrisha, 2016/01/18 22:40:28]

Oh? There's no way to have a writable FilePersistent allocator, even if we
specify a maximum size up front? This seems like it would be eminently so
processes don't need to have a "death rattle" handler, but can rely on the OS to
do that for them...

[bcwhite, 2016/01/19 19:49:40]

Agreed but right now the underlying MemoryMappedFile allows for read-only
access.  I hope to change that (and this) when the time comes.

+    : public PersistentMemoryAllocator {
+ public:
+  FilePersistentMemoryAllocator(MemoryMappedFile* file, uint32_t id,
+                                const std::string& name);
+  ~FilePersistentMemoryAllocator() override;
+
+  // Ensure that the file isn't so invalid that it won't crash when passing it
+  // to the allocator. This doesn't guarantee the file is valid, just that it
+  // won't cause program to abort. The existing IsCorrupt() call will handle
+  // the rest.
+  static bool IsFileAcceptable(const MemoryMappedFile& file);
+
+ private:
+  scoped_ptr<MemoryMappedFile> mapped_file_;
+};
+
+}  // namespace base
+
+#endif  // BASE_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_