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

base/memory/shared_memory_allocator.cc

+// 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.
+
+#include "base/memory/shared_memory_allocator.h"
+
+#include <assert.h>
+#include <algorithm>
+
+#include "base/logging.h"
+
+// All integer constants in this file are signed because Atomic32 is signed
+// and keeping all others consistent with this avoids a lot of unnecessary
+// casting to avoid signed/unsigned operations just to avoid compiler errors.
+// This means an occasonal cast of a constant from sizeof() to "int" but
+// is far simpler than the alternative.

[mdempsky, 2015/11/10 19:47:55]

I notice that 1) there's no checks to ensure the size_t values still fit into
int32_t, and 2) lots of C style casts.  How about adding an "int32_t
SizeToInt(size_t)" function so we can consistently D?CHECK, and SizeToInt(x) is
a little more concise than static_cast<int32_t>(x) everywhere.  Also lets you
put this comment on SizeToInt to explain why it's necessary.

[bcwhite, 2015/11/10 21:17:34]

There are size_t checks where it's used (which is only as part of the external
interface), for example on line #196:
usize > (size_t)std::numeric_limits<int32_t>::max()

I used c-style casts for constants like "(int32_t)sizeof(BlockHeader)" because
it's just so much clearer and, well, it's an immediate constant.

[mdempsky, 2015/11/10 22:45:52]

Style guide says "Do not use C-style casts."

+
+namespace {
+
+// Required range of memory segment sizes. It has to fit in a signed 32-bit
+// number and should be a power of 2 in order to accomodate almost any page
+// size.
+const int32_t kSegmentMinSize = 1 << 10;  // 1 KiB
+const int32_t kSegmentMaxSize = 1 << 30;  // 1 GiB
+
+// All allocations and data-structures must be aligned to this byte boundary.
+// Alignment as large as the physical bus between CPU and RAM is _required_
+// for some architectures, is simply more efficient on other CPUs, and
+// generally a Good Idea(tm) for all platforms as it reduces/eliminates the
+// chance that a type will span cache lines. Alignment mustn't be less
+// than 8 to ensure proper alignment for all types. The rest is a balance
+// between reducing spans across multiple cache lines and wasted space spent
+// padding out allocations. An alignment of 16 would ensure that the block
+// header structure always sits in a single cache line. An average of about
+// 1/2 this value will be wasted with every allocation.
+const int32_t kAllocAlignment = 8;
+
+// A constant (random) value placed in the shared metadata to identify
+// an already initialized memory segment.
+const int32_t kGlobalCookie = 0x408305DC;
+
+// The current version of the metadata. If updates are made that change
+// the metadata, the version number can be queried to operate in a backward-
+// compatible manner until the memory segment is completely re-initalized.
+const int32_t kGlobalVersion = 1;
+
+// Constant values placed in the block headers to indicate its state.
+const int32_t kBlockCookieFree = 0;
+const int32_t kBlockCookieQueue = 1;
+const int32_t kBlockCookieWasted = -1;
+const int32_t kBlockCookieAllocated = 0xC8799269;
+
+// TODO(bcwhite): When acceptable, consider moving flags to std::atomic<char>
+// types rather than combined bitfield.
+
+// Flags stored in the flags_ field of the SharedMetaData structure below.
+enum : int32_t {
+  kFlagCorrupt = 1 << 0,
+  kFlagFull    = 1 << 1
+};
+
+bool CheckFlag(base::subtle::Atomic32* flags, int flag) {
+  base::subtle::Atomic32 loaded_flags = base::subtle::Acquire_Load(flags);
+  return (loaded_flags & flag) != 0;
+}
+
+void SetFlag(base::subtle::Atomic32* flags, int flag) {
+  for (;;) {
+    base::subtle::Atomic32 loaded_flags = base::subtle::Acquire_Load(flags);
+    base::subtle::Atomic32 new_flags =
+        (loaded_flags & ~flag) | flag;
+    if (base::subtle::Release_CompareAndSwap(
+            flags, loaded_flags, new_flags) == loaded_flags) {
+      break;
+    }
+  }
+}
+
+}  // namespace
+
+namespace base {
+
+// The block-header is placed at the top of every allocation within the
+// segment to describe the data that follows it.
+struct SharedMemoryAllocator::BlockHeader {
+  int32_t size;           // Number of bytes in this block, including header.
+  int32_t cookie;         // Constant value indicating completed allocation.
+  uint32_t type_id;       // A number provided by caller indicating data type.
+  subtle::Atomic32 next;  // Pointer to the next block when iterating.
+};
+
+// The shared metadata exists once at the top of the memory segment to
+// describe the state of the allocator to all processes.
+struct SharedMemoryAllocator::SharedMetadata {
+  int32_t cookie;     // Some value that indicates complete initialization.
+  int32_t size;       // Total size of memory segment.
+  int32_t page_size;  // Paging size within memory segment.
+  int32_t version;    // Version code so upgrades don't break.
+  subtle::Atomic32 freeptr;  // Offset/ref to first free space in the segment.
+  subtle::Atomic32 flags;    // Bitfield of information flags.
+  int32_t reserved;   // Padding to ensure size is multiple of alignment.
+
+  // The "iterable" queue is an M&S Queue as described here, append-only:
+  // https://www.research.ibm.com/people/m/michael/podc-1996.pdf
+  subtle::Atomic32 tailptr;  // Last block available for iteration.
+  BlockHeader queue;  // Empty block for linked-list head/tail. (must be last)
+};
+
+// The "queue" block header is used to detect "last node" so that zero/null
+// can be used to indicate that it hasn't been added at all. It is part of
+// the SharedMetadata structure which itself is always located at offset zero.
+// This can't be a constant because SharedMetadata is a private definition.

[mdempsky, 2015/11/10 19:47:55]

FWIW, this is valid C++:

  class Foo {
    struct Bar;
    static const size_t kBarOff;
  };

  struct Foo::Bar {
    int x;
  };
  const size_t Foo::kBarOff = offsetof(Foo::Bar, x);

[bcwhite, 2015/11/10 21:17:34]

That would require the constant to be declared in the header file, no?

[mdempsky, 2015/11/10 22:45:52]

Declared, yes.  Is that problematic somehow?

[bcwhite, 2015/11/11 13:25:14]

Nope.  Just making sure I understood.

+#define REF_QUEUE offsetof(SharedMetadata, queue)
+#define REF_NULL 0  // the equivalest NULL value for a reference

[mdempsky, 2015/11/10 19:47:55]

typo: equivalent

[bcwhite, 2015/11/10 21:17:34]

Done.

+
+SharedMemoryAllocator::SharedMemoryAllocator(void* base,
+                                             size_t size,
+                                             size_t page_size)
+    : mem_base_(static_cast<char*>(base)),
+      mem_size_((int32_t)size),
+      mem_page_((int32_t)(page_size ? page_size : size)),
+      corrupted_(0) {
+  static_assert(sizeof(BlockHeader) % kAllocAlignment == 0,
+                "BlockHeader is not a multiple of kAllocAlignment");
+  static_assert(sizeof(SharedMetadata) % kAllocAlignment == 0,
+                "SharedMetadata is not a multiple of kAllocAlignment");
+
+  CHECK(base && reinterpret_cast<uintptr_t>(base) % kAllocAlignment == 0);
+  CHECK(size >= kSegmentMinSize && size <= kSegmentMaxSize &&
+        size % kAllocAlignment == 0);
+  CHECK(page_size == 0 || size % page_size == 0);
+
+  if (shared_meta()->cookie != kGlobalCookie) {
+    // This block is only executed when a completely new memory segment is
+    // being initialized. It's unshared and single-threaded...
+    const BlockHeader* first_block = reinterpret_cast<BlockHeader*>(
+        mem_base_ + sizeof(SharedMetadata));
+    if (shared_meta()->cookie != 0 ||
+        shared_meta()->size != 0 ||
+        shared_meta()->version != 0 ||
+        subtle::NoBarrier_Load(&shared_meta()->freeptr) != 0 ||
+        subtle::NoBarrier_Load(&shared_meta()->flags) != 0 ||
+        shared_meta()->tailptr != 0 ||
+        shared_meta()->queue.cookie != 0 ||
+        subtle::NoBarrier_Load(&shared_meta()->queue.next) != 0 ||
+        first_block->size != 0 ||
+        first_block->cookie != 0 ||
+        first_block->type_id != 0 ||
+        first_block->next != 0) {
+      // ...or something malicious has been playing with the metadata.
+      NOTREACHED();
+      SetCorrupt();
+    }
+
+    // This is still safe to do even if corruption has been detected.
+    shared_meta()->cookie = kGlobalCookie;
+    shared_meta()->size = mem_size_;
+    shared_meta()->page_size = mem_page_;
+    shared_meta()->version = kGlobalVersion;
+    subtle::NoBarrier_Store(&shared_meta()->freeptr, sizeof(SharedMetadata));
+
+    // Set up the queue of iterable allocations.
+    shared_meta()->queue.size = sizeof(BlockHeader);
+    shared_meta()->queue.cookie = kBlockCookieQueue;
+    subtle::NoBarrier_Store(&shared_meta()->queue.next, REF_QUEUE);
+    subtle::NoBarrier_Store(&shared_meta()->tailptr, REF_QUEUE);
+  } else {
+    // The allocator is attaching to a previously initialized segment of
+    // memory. Make sure the embedded data matches what has been passed.
+    if (shared_meta()->size != mem_size_ ||
+        shared_meta()->page_size != mem_page_) {
+      NOTREACHED();
+      SetCorrupt();
+    }
+  }
+}
+
+SharedMemoryAllocator::~SharedMemoryAllocator() {}
+
+size_t SharedMemoryAllocator::GetAllocSize(Reference ref) {
+  BlockHeader* block = GetBlock(ref, 0, 0, false, false);
+  if (!block)
+    return 0;
+  int32_t size = block->size;
+  // Header was verified by GetBlock() but a malicious actor could change
+  // the value between there and here.  Check it again.
+  if (size <= (int)sizeof(BlockHeader) || ref + size >= mem_size_)
+    return 0;
+  return (size_t)size - sizeof(BlockHeader);
+}
+
+int32_t SharedMemoryAllocator::Allocate(size_t usize, uint32_t type_id) {
+  // Round up the requested size, plus header, to the next allocation alignment.
+  int32_t size = (int)usize + sizeof(BlockHeader);
+  size = (size + (kAllocAlignment - 1)) & ~(kAllocAlignment - 1);
+  if (usize > (size_t)std::numeric_limits<int32_t>::max() ||
+      size <= (int)sizeof(BlockHeader) || size > mem_page_) {
+    NOTREACHED();
+    return REF_NULL;
+  }
+
+  // Allocation is lockless so we do all our caculation and then, if saving
+  // indicates a change has occurred since we started, scrap everything and
+  // start over.
+  for (;;) {
+    if (IsCorrupt())
+      return REF_NULL;
+
+    // Get the current start of unallocated memory. Other threads may
+    // update this at any time and cause us to retry these operations.
+    int32_t freeptr = subtle::NoBarrier_Load(&shared_meta()->freeptr);
+    if (freeptr + size > mem_size_) {
+      SetFlag(&shared_meta()->flags, kFlagFull);
+      return REF_NULL;
+    }
+
+    // Get pointer to the "free" block. It doesn't even have a header; pass
+    // -sizeof(header) so accouting for that will yield an expected size of
+    // zero which is what will be stored at that location. If something
+    // has been allocated since the load of freeptr above, it is still safe
+    // as nothing will be written to that location until after the CAS below.
+    BlockHeader* block = GetBlock(freeptr, 0, 0, false, true);
+    if (!block) {
+      SetCorrupt();
+      return REF_NULL;
+    }
+
+    // An allocation cannot cross page boundaries. If it would, create a
+    // "wasted" block and begin again at the top of the next page. This
+    // area could just be left empty but we fill in the block header just
+    // for completeness sake.
+    int32_t page_free = mem_page_ - freeptr % mem_page_;
+    if (size > page_free) {
+      if (page_free <= sizeof(BlockHeader)) {
+        SetCorrupt();
+        return REF_NULL;
+      }
+      int32_t new_freeptr = freeptr + page_free;
+      if (subtle::NoBarrier_CompareAndSwap(
+              &shared_meta()->freeptr, freeptr, new_freeptr) == freeptr) {
+        block->size = page_free;
+        block->cookie = kBlockCookieWasted;
+      }
+      continue;
+    }
+
+    // Don't leave a slice at the end of a page too small for anything. This
+    // can result in an allocation up to two alignment-sizes greater than the
+    // minimum required by requested-size + header + alignment.
+    if (page_free - size < (int)(sizeof(BlockHeader) + kAllocAlignment))
+      size = page_free;
+
+    int32_t new_freeptr = freeptr + size;
+    if (new_freeptr > mem_size_) {
+      SetCorrupt();
+      return REF_NULL;
+    }
+
+    if (subtle::NoBarrier_CompareAndSwap(
+            &shared_meta()->freeptr, freeptr, new_freeptr) != freeptr) {
+      // Another thread must have completed an allocation while we were working.
+      // Try again.
+      continue;
+    }
+
+    // Given that all memory was zeroed before ever being given to an instance
+    // of this class and given that we only allocate in a monotomic fashion
+    // going forward, it must be that the newly allocated block is completely
+    // full of zeros. If we find anything in the block header that is NOT a
+    // zero then something must have previously run amuck through memory,
+    // writing beyond the allocated space and into unallocated space.
+    if (block->size != 0 ||
+        block->cookie != kBlockCookieFree ||
+        block->type_id != 0 ||
+        subtle::NoBarrier_Load(&block->next) != 0) {
+      SetCorrupt();
+      return REF_NULL;
+    }
+
+    block->size = size;
+    block->cookie = kBlockCookieAllocated;
+    block->type_id = type_id;
+    return freeptr;
+  }
+}
+
+void SharedMemoryAllocator::GetMemoryInfo(MemoryInfo* meminfo) {
+  int32_t remaining =
+      mem_size_ - subtle::NoBarrier_Load(&shared_meta()->freeptr);
+  meminfo->total = mem_size_;
+  meminfo->free = IsCorrupt() ? 0 : remaining - sizeof(BlockHeader);
+}
+
+void SharedMemoryAllocator::MakeIterable(Reference ref) {
+  if (IsCorrupt())
+    return;
+  BlockHeader* block = GetBlock(ref, 0, 0, false, false);
+  if (!block)  // invalid reference
+    return;
+  if (subtle::Acquire_Load(&block->next) != 0)  // previously set iterable
+    return;
+  subtle::Release_Store(&block->next, REF_QUEUE);  // will be tail block
+
+  // Try to add this block to the tail of the queue. May take multiple tries.
+  int32_t tail;
+  for (;;) {
+    // Acquire the current tail-pointer released by previous call to this
+    // method and validate it.
+    tail = subtle::Acquire_Load(&shared_meta()->tailptr);
+    block = GetBlock(tail, 0, 0, true, false);
+    if (!block) {
+      SetCorrupt();
+      return;
+    }
+
+    // Try to insert the block at the tail of the queue. The tail node always
+    // has an existing value of REF_QUEUE; if that is not the value returned,
+    // another thread has acted in the meantime.
+    int32_t next = subtle::Release_CompareAndSwap(&block->next, REF_QUEUE, ref);
+    if (next == REF_QUEUE) {
+      // Update the tail pointer to the new offset. If the "else" clause did
+      // not exist, then this could be a simple Release_Store to set the new
+      // value but because it does, it's possible that other threads could add
+      // one or more nodes at the tail before reaching this point. We don't
+      // have to check the return value because it either operates correctly
+      // or the exact same operation has already been done (by the "else"
+      // clause).
+      subtle::Release_CompareAndSwap(&shared_meta()->tailptr, tail, ref);
+      return;
+    } else {
+      // In the unlikely case that a thread crashed or was killed between the
+      // update of "next" and the update of "tailptr", it is necessary to
+      // perform the operation that would have been done. There's no explicit
+      // check for crash/kill which means that this operation may also happen
+      // even when the other thread is in perfect working order which is what
+      // necessitates the CompareAndSwap above.
+      subtle::Release_CompareAndSwap(&shared_meta()->tailptr, tail, next);
+    }
+  }
+}
+
+void SharedMemoryAllocator::CreateIterator(Iterator* state) {
+  state->last = REF_QUEUE;
+  state->niter = 0;
+}
+
+int32_t SharedMemoryAllocator::GetNextIterable(Iterator* state,
+                                               uint32_t* type_id) {
+  const BlockHeader* block = GetBlock(state->last, 0, 0, true, false);
+  if (!block)  // invalid iterator state
+    return REF_NULL;
+
+  // The compiler and CPU can freely reorder all memory accesses on which
+  // there are no dependencies. It could, for example, move the load of
+  // "freeptr" above this point because there are no explicit dependencies
+  // between it and "next". If it did, however, then another block could
+  // be queued after that but before the following load meaning there is
+  // one more queued block than the future "detect loop by having more
+  // blocks that could fit before freeptr" will allow.
+  //
+  // By "acquiring" the "next" value here, it's synchronized to the enqueue
+  // of the node which in turn is synchronized to the allocation (which sets
+  // freeptr). Thus, the scenario above cannot happen.
+  int32_t next = subtle::Acquire_Load(&block->next);
+  block = GetBlock(next, 0, 0, false, false);
+  if (!block)  // no next allocation in queue
+    return REF_NULL;
+
+  // Memory corruption could cause a loop in the list. We need to detect
+  // that so as to not cause an infinite loop in the caller. We do this
+  // simply by making sure we don't iterate more than the absolute maximum
+  // number of allocations that could have been made. Callers are likely
+  // to loop multiple times before it is detected but at least it stops.
+  int32_t freeptr = std::min(subtle::Acquire_Load(&shared_meta()->freeptr),
+                             mem_size_);
+  if (state->niter > freeptr / (sizeof(BlockHeader) + kAllocAlignment)) {
+    SetCorrupt();
+    return REF_NULL;
+  }
+
+  state->last = next;
+  state->niter++;
+  *type_id = block->type_id;
+
+  return next;
+}
+
+// The "corrupted" state is held both locally and globally (shared). The
+// shared flag can't be trusted since a malicious actor could overwrite it.
+// The local version is immune to foreign actors. Thus, if seen shared,
+// copy it locally and, once known, always restore it globally.
+void SharedMemoryAllocator::SetCorrupt() {
+  LOG(ERROR) << "Corruption detected in shared-memory segment.";
+  subtle::NoBarrier_Store(&corrupted_, 1);

[mdempsky, 2015/11/10 19:47:55]

(I take individual SharedMemoryAllocator objects meant to be safe for concurrent
use within a process?)

[bcwhite, 2015/11/10 21:17:34]

Yes.

+  SetFlag(&shared_meta()->flags, kFlagCorrupt);
+}
+
+bool SharedMemoryAllocator::IsCorrupt() {
+  if (subtle::NoBarrier_Load(&corrupted_) ||
+      CheckFlag(&shared_meta()->flags, kFlagCorrupt)) {
+    SetCorrupt();  // Make sure all indicators are set.
+    return true;
+  }
+  return false;
+}
+
+bool SharedMemoryAllocator::IsFull() {
+  return CheckFlag(&shared_meta()->flags, kFlagFull);
+}
+
+// Dereference a block |ref| and ensure that it's valid for the desired
+// |type_id| and |size|. |special| indicates that we may try to access block
+// headers not available to callers but still accessed by this module. By
+// having internal dereferences go through this same function, the allocator
+// is hardened against corruption.
+SharedMemoryAllocator::BlockHeader* SharedMemoryAllocator::GetBlock(
+    Reference ref,
+    uint32_t type_id,
+    int32_t size,
+    bool queue_ok,
+    bool free_ok) {
+  // Validation of parameters.
+  if (ref % kAllocAlignment != 0)
+    return nullptr;
+  if (ref < (int)(queue_ok ? REF_QUEUE : sizeof(SharedMetadata)))
+    return nullptr;
+  size += sizeof(BlockHeader);
+  if (ref + size > mem_size_)
+    return nullptr;
+
+  // Validation of referenced block-header.
+  if (!free_ok) {
+    int32_t freeptr = subtle::NoBarrier_Load(&shared_meta()->freeptr);
+    if (ref + size > freeptr)
+      return nullptr;
+    const BlockHeader* block =
+        reinterpret_cast<BlockHeader*>(mem_base_ + ref);
+    if (block->size < size)

[mdempsky, 2015/11/10 19:47:55]

Like JF and I mentioned, for C++ correctness, block should be a pointer to a
volatile BlockHeader and *all* accesses to its member variables need to be
atomic to guard against malicious processes.  (Probably GetAsObject, etc. should
return pointers-to-volatile too to help enforce this.)

[Alexander Potapenko, 2015/11/10 20:47:10]

By "volatile" did you mean "atomic"?
(this is basically the same with base/atomicops.h, but I don't think C++11
atomics have volatile semantics)

[bcwhite, 2015/11/10 21:17:35]

You mean "volatile T* GetAsObject(...) {...}"?  I think any objects being
fetched and expecting continued shared access would have to use Atomic data
values so wouldn't this be redundant?

Near as I can tell, volatile would only help with reads.  Writes to volatile
data won't necessary be immediately visible to other cores and so volatile isn't
sufficient.

To be honest, I don't understand what use "volatile" has in these days of
multi-core processing.

[mdempsky, 2015/11/10 22:45:52]

JF said they need to both volatile and atomic (and I trust that he understand
C++ memory model correctness requirements better than I do).  I'll have to defer
to him for elaborations on why volatile is necessary.

[mdempsky, 2015/11/10 22:45:52]

Yes.
(Again, have to defer to JF.)

+      return nullptr;
+    if (ref != REF_QUEUE && block->cookie != kBlockCookieAllocated)
+      return nullptr;
+    if (type_id != 0 && block->type_id != type_id)
+      return nullptr;
+  }
+
+  // Return pointer to block data.
+  return reinterpret_cast<BlockHeader*>(mem_base_ + ref);
+}
+
+void* SharedMemoryAllocator::GetBlockData(Reference ref,
+                                          uint32_t type_id,
+                                          int32_t size) {
+  DCHECK(size > 0);
+  BlockHeader* block = GetBlock(ref, type_id, size, false, false);
+  if (!block)
+    return nullptr;
+  return reinterpret_cast<char*>(block) + sizeof(BlockHeader);
+}
+
+}  // namespace base