Improved support for objects inside persistent memory.

base/metrics/persistent_memory_allocator.h

 // 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>
@@ skipping 31 matching lines @@
 // 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.
 //
-// All persistent memory segments can be freely accessed by builds of different
-// natural word widths (i.e. 32/64-bit) but users of this module must manually
-// ensure that the data recorded within are similarly safe. The GetAsObject<>()
-// methods use the kExpectedInstanceSize attribute of the structs to check this.
+// OBJECTS: Although the allocator can be used in a "malloc" sense, fetching
+// character arrays and manipulating that memory manually, the better way is
+// generally to use the "Object" methods to create and manage allocations. In
+// this way the sizing, type-checking, and construction are all automatic. For
+// this to work, however, every type of stored object must define two public
+// "constexpr" values, kPersistentTypeId and kExpectedInstanceSize, as such:
 //
-// Memory segments can NOT, however, be exchanged between CPUs of different
-// endianess. Attempts to do so will simply see the existing data as corrupt
-// and refuse to access any of it.
+// struct MyPersistentObjectType {
+//     // SHA1(MyPersistentObjectType): Increment this if structure changes!
+//     static constexpr uint32_t kPersistentTypeId = 0x3E15F6DE + 1;
+//
+//     // Expected size for 32/64-bit check. Update this if structure changes!
+//     static constexpr size_t kExpectedInstanceSize = 20;
+//
+//     ...
+// };
+//
+// kPersistentTypeId: This value is an arbitrary identifier that allows the
+//   identification of these objects in the allocator, including the ability
+//   to find them via iteration. The number is arbitrary but using the first
+//   four bytes of the SHA1 hash of the type name means that there shouldn't
+//   be any conflicts with other types that may also be stored in the memory.
+//   The fully qualified name (e.g. base::debug::MyPersistentObjectType) could
+//   be used to generate the hash if the type name seems common. Use a command
+//   like this to get the hash: echo -n "MyPersistentObjectType" | sha1sum
+//   If the structure layout changes, ALWAYS increment this number so that
+//   newer versions of the code don't try to interpret persistent data written
+//   by older versions with a different layout.
+//
+// kExpectedInstanceSize: This value is the hard-coded number that matches
+//   what sizeof(T) would return. By providing it explicitly, the allocator can
+//   verify that the structure is compatible between both 32-bit and 64-bit
+//   versions of the code.
+//
+// Using AllocateObject (and ChangeObject) will zero the memory and then call
+// the default constructor for the object. Given that objects are persistent,
+// no destructor is ever called automatically though a caller can explicitly
+// call DeleteObject to destruct it and change the type to something indicating
+// it is no longer in use.
+//
+// Though persistent memory segments are transferrable between programs built
+// for different natural word widths, they CANNOT be exchanged between CPUs
+// of different endianess. Attempts to do so will simply see the existing data
+// as corrupt and refuse to access any of it.
 class BASE_EXPORT PersistentMemoryAllocator {
  public:
   typedef uint32_t Reference;
 
   // Iterator for going through all iterable memory records in an allocator.
   // Like the allocator itself, iterators are lock-free and thread-secure.
   // That means that multiple threads can share an iterator and the same
   // reference will not be returned twice.
   //
   // The order of the items returned by an iterator matches the order in which
@@ skipping 37 matching lines @@
     // zero if there are no more. GetNext() may still be called again at a
     // later time to retrieve any new allocations that have been added.
     Reference GetNext(uint32_t* type_return);
 
     // Similar to above but gets the next iterable of a specific |type_match|.
     // This should not be mixed with calls to GetNext() because any allocations
     // skipped here due to a type mis-match will never be returned by later
     // calls to GetNext() meaning it's possible to completely miss entries.
     Reference GetNextOfType(uint32_t type_match);
 
+    // As above but works using object type.
+    template <typename T>
+    Reference GetNextOfType() {
+      return GetNextOfType(T::kPersistentTypeId);
+    }
+
+    // As above but works using objects and returns null if not found.
+    template <typename T>
+    const T* GetNextOfObject() {
+      return GetAsObject<T>(GetNextOfType<T>());
+    }
+
     // Converts references to objects. This is a convenience method so that
     // users of the iterator don't need to also have their own pointer to the
     // allocator over which the iterator runs in order to retrieve objects.
     // Because the iterator is not read/write, only "const" objects can be
     // fetched. Non-const objects can be fetched using the reference on a
     // non-const (external) pointer to the same allocator (or use const_cast
     // to remove the qualifier).
     template <typename T>
-    const T* GetAsObject(Reference ref, uint32_t type_id) const {
-      return allocator_->GetAsObject<T>(ref, type_id);
+    const T* GetAsObject(Reference ref) const {
+      return allocator_->GetAsObject<T>(ref);
     }
 
-    // Similar to GetAsObject() but converts references to arrays of objects.
+    // Similar to GetAsObject() but converts references to arrays of things.
     template <typename T>
     const T* GetAsArray(Reference ref, uint32_t type_id, size_t count) const {
       return allocator_->GetAsArray<T>(ref, type_id, count);
     }
 
+    // Helper function to convert a generic pointer back into a reference.

[Alexei Svitkine (slow), 2017/01/06 16:29:33]

Nit: "Helper function to" is redundant. Just "Converts a generic pointer back
into a reference.". Maybe mention what happens if the pointer is not found as
well?

Same for the function below.

[bcwhite, 2017/01/06 17:27:07]

Done.

+    Reference GetAsReference(const void* memory, uint32_t type_id) const {
+      return allocator_->GetAsReference(memory, type_id);
+    }
+
+    // Helper function to convert an object back into a reference.
+    template <typename T>
+    Reference GetAsReference(const T* obj) const {
+      return allocator_->GetAsReference(obj);
+    }
+
    private:
     // Weak-pointer to memory allocator being iterated over.
     const PersistentMemoryAllocator* allocator_;
 
     // The last record that was returned.
     std::atomic<Reference> last_record_;
 
     // The number of records found; used for detecting loops.
     std::atomic<uint32_t> record_count_;
 
     DISALLOW_COPY_AND_ASSIGN(Iterator);
   };
 
   // Returned information about the internal state of the heap.
   struct MemoryInfo {
     size_t total;
     size_t free;
   };
 
   enum : Reference {
-    kReferenceNull = 0  // A common "null" reference value.
-  };
+    // A common "null" reference value.
+    kReferenceNull = 0,
 
-  enum : uint32_t {
-    kTypeIdAny = 0  // Match any type-id inside GetAsObject().
+    // A value indicating that the type is in transition. Work is being done
+    // on the contents to prepare it for a new type to come.
+    kReferenceTransitioning = 0xFFFFFFFF,
   };
 
   enum : size_t {
     kSizeAny = 1  // Constant indicating that any array size is acceptable.
   };
 
   // This is the standard file extension (suitable for being passed to the
   // AddExtension() method of base::FilePath) for dumps of persistent memory.
   static const base::FilePath::CharType kFileExtension[];
 
@@ skipping 100 matching lines @@
   // 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_pod<T>::value, "only simple objects");
+  T* GetAsObject(Reference ref) {
+    static_assert(std::is_standard_layout<T>::value, "only standard objects");
+    static_assert(!std::is_array<T>::value, "use GetAsArray<>()");
     static_assert(T::kExpectedInstanceSize == sizeof(T), "inconsistent size");
-    return const_cast<T*>(
-        reinterpret_cast<volatile T*>(GetBlockData(ref, type_id, sizeof(T))));
+    return const_cast<T*>(reinterpret_cast<volatile T*>(
+        GetBlockData(ref, T::kPersistentTypeId, sizeof(T))));
   }
   template <typename T>
-  const T* GetAsObject(Reference ref, uint32_t type_id) const {
-    static_assert(std::is_pod<T>::value, "only simple objects");
+  const T* GetAsObject(Reference ref) const {
+    static_assert(std::is_standard_layout<T>::value, "only standard objects");
+    static_assert(!std::is_array<T>::value, "use GetAsArray<>()");
     static_assert(T::kExpectedInstanceSize == sizeof(T), "inconsistent size");
-    return const_cast<const T*>(
-        reinterpret_cast<const volatile T*>(GetBlockData(
-            ref, type_id, sizeof(T))));
+    return const_cast<const T*>(reinterpret_cast<const volatile T*>(
+        GetBlockData(ref, T::kPersistentTypeId, sizeof(T))));
   }
 
   // Like GetAsObject but get an array of simple, fixed-size types.
   //
   // Use a |count| of the required number of array elements, or kSizeAny.
   // GetAllocSize() can be used to calculate the upper bound but isn't reliable
   // because padding can make space for extra elements that were not written.
   //
   // Remember that an array of char is a string but may not be NUL terminated.
   //
@@ skipping 11 matching lines @@
     static_assert(std::is_fundamental<T>::value, "use GetAsObject<>()");
     return const_cast<const char*>(reinterpret_cast<const volatile T*>(
         GetBlockData(ref, type_id, count * sizeof(T))));
   }
 
   // Get the corresponding reference for an object held in persistent memory.
   // If the |memory| is not valid or the type does not match, a kReferenceNull
   // result will be returned.
   Reference GetAsReference(const void* memory, uint32_t type_id) const;
 
+  // As above but works with objects allocated from persistent memory.
+  template <typename T>
+  Reference GetAsReference(const T* obj) const {
+    return GetAsReference(obj, T::kPersistentTypeId);
+  }
+
   // 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. Changing the type is
   // an atomic compare/exchange and so requires knowing the existing value.
   // It will return false if the existing type is not what is expected.
+  // Changing the type doesn't mean the data is compatible with the new type.
+  // It will likely be necessary to clear or reconstruct the type before it
+  // can be used.

[Alexei Svitkine (slow), 2017/01/06 16:29:33]

I'm curious what the use case for ChangeType and ChangeObjects are?

Why have this complexity in the underlying class rather than just not supporting
it directly and letting the caller delete and create new objects as necessary?

If it's not a widely used case, I'd rather we don't include support for it so
that the code is that much simpler and there's less room for errors.

[bcwhite, 2017/01/06 17:27:06]

The nature of persistent allocation is such that "free" is not practical.  The
lock-free complexity of managing of multiple blocks of unallocated space is huge
and so the decision was made during development to omit it.

Even changing the type can be problematic but then it's something that is being
done outside this class which leaves the management of potential problems to the
caller which, because it has more knowledge about how the data is being used,
can ensure proper operation.

Changing the type is generally used to mark an object as "free" because it is
being destroyed and shouldn't be found by later iteration.  Sometimes the "free
type" is used to re-use that space when creating new objects of that same type
(and thus same size).

   uint32_t GetType(Reference ref) const;
   bool ChangeType(Reference ref, uint32_t to_type_id, uint32_t from_type_id);
 
+  // Like ChangeType() but gets the "to" type from the object type, clears
+  // the memory, and constructs a new object of the desired type just as
+  // though it was fresh from AllocateObject<>(). The old type simply ceases
+  // to exist; no destructor is called for it.

[Alexei Svitkine (slow), 2017/01/06 16:29:34]

Is it worth adding a warning here that this may result in undefined behavior if
someone has a pointer to the existing object and is modifying/using it at the
same time?

[bcwhite, 2017/01/06 17:27:06]

Done.

+  template <typename T>
+  T* ChangeObject(Reference ref, uint32_t from_type_id) {
+    DCHECK_LE(sizeof(T), GetAllocSize(ref)) << "alloc not big enough for obj";
+    // Make sure the memory is appropriate. This won't be used until after
+    // the type is changed but checking first avoids the possibility of having
+    // to change the type back.
+    void* mem = const_cast<void*>(GetBlockData(ref, 0, sizeof(T)));
+    if (!mem)
+      return nullptr;
+    DCHECK_EQ(0U, reinterpret_cast<uintptr_t>(mem) & (ALIGNOF(T) - 1));

[Alexei Svitkine (slow), 2017/01/06 16:29:34]

Nit: Add a comment about this - why is it expected?

[bcwhite, 2017/01/06 17:27:07]

Done.

+    // First change the type to "transitioning" so that there is no race
+    // condition with the clearing and construction of the object should
+    // another thread be simultaneously iterating over data. This will
+    // "acquire" the memory so no changes get reordered before it.
+    if (!ChangeType(ref, kReferenceTransitioning, from_type_id))
+      return nullptr;
+    // Clear the memory so that the property of all memory being zero after an
+    // allocation also applies here.
+    memset(mem, 0, GetAllocSize(ref));
+    // Construct an object of the desired type on this memory, just as if
+    // AllocateObject had been called to create it.
+    T* obj = new (mem) T();
+    // Finally change the type to the desired one. This will "release" all of
+    // the changes above and so provide a consistent view to other threads.
+    bool success =
+        ChangeType(ref, T::kPersistentTypeId, kReferenceTransitioning);
+    DCHECK(success);
+    return obj;
+  }
+
   // 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);
 
+  // Allocate and construct an object in persistent memory. The type must have
+  // both (size_t) kExpectedInstanceSize and (uint32_t) kPersistentTypeId
+  // static constexpr fields that are used to ensure compatibility between
+  // software versions. An optional size parameter can be specified to force
+  // the allocation to be bigger than the size of the object; this is useful
+  // when the last field is actually variable length.
+  template <typename T>
+  T* AllocateObject(size_t size) {
+    if (size < sizeof(T))
+      size = sizeof(T);
+    Reference ref = Allocate(size, T::kPersistentTypeId);
+    void* mem =
+        const_cast<void*>(GetBlockData(ref, T::kPersistentTypeId, size));
+    if (!mem)
+      return nullptr;
+    DCHECK_EQ(0U, reinterpret_cast<uintptr_t>(mem) & (ALIGNOF(T) - 1));
+    return new (mem) T();
+  }
+  template <typename T>
+  T* AllocateObject() {
+    return AllocateObject<T>(sizeof(T));
+  }
+
+  // Deletes an object by destructing it and then changing the type to a
+  // different value (default 0).
+  template <typename T>
+  void DeleteObject(T* obj, uint32_t new_type) {
+    // Get the reference for the object.
+    Reference ref = GetAsReference<T>(obj);
+    // First change the type to "transitioning" so there is no race condition
+    // where another thread could find the object through iteration while it
+    // is been destructed. This will "acquire" the memory so no changes get
+    // reordered before it. It will fail if |ref| is invalid.
+    if (!ChangeType(ref, kReferenceTransitioning, T::kPersistentTypeId))
+      return;
+    // Destruct the object.
+    obj->~T();
+    // Finally change the type to the desired value. This will "release" all
+    // the changes above.
+    bool success = ChangeType(ref, new_type, kReferenceTransitioning);
+    DCHECK(success);
+  }
+  template <typename T>
+  void DeleteObject(T* obj) {
+    DeleteObject<T>(obj, 0);
+  }
+
   // 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.
+  // Changing the type does not alter its "iterable" status.
   void MakeIterable(Reference ref);
 
+  // As above but works with an object allocated from persistent memory.
+  template <typename T>
+  void MakeIterable(const T* obj) {
+    MakeIterable(GetAsReference<T>(obj));
+  }
+
   // 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;
 
   // 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;
@@ skipping 168 matching lines @@
  private:
   std::unique_ptr<MemoryMappedFile> mapped_file_;
 
   DISALLOW_COPY_AND_ASSIGN(FilePersistentMemoryAllocator);
 };
 #endif  // !defined(OS_NACL)
 
 }  // namespace base
 
 #endif  // BASE_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_