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 "base/atomicops.h"
+#include "base/logging.h"
+
+namespace {
+
+// All allocations and data-structures must be aligned to this byte boundary.
+// It shouldn't be less than 8 so that 64-bit values can be read in a single
+// RAM bus access.  16 was chosen so that the block header would always fall

[Alexander Potapenko, 2015/10/30 06:53:13]

Nit: please 's/.  /. ' here and below.

+// within a single cache line.
+const int32_t kAllocAlignment = 16;
+
+// 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;
+
+}  // 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

[Alexander Potapenko, 2015/10/30 06:53:13]

Please fix the comments according to
https://google.github.io/styleguide/cppguide.html#Punctuation,_Spelling_and_G...

[bcwhite, 2015/10/30 14:01:10]

Done.

+  int32_t cookie;  // constant value indicating completed allocation

[Alexander Potapenko, 2015/10/30 06:53:13]

I think it's better to align the comments to this struct's fields, but YMMV.
Ditto for the struct below.

[bcwhite, 2015/10/30 14:01:10]

*I* prefer it but I've gotten nags in the past that I shouldn't do it.  Let me
see if presumbit complains about too many spaces before the double-slash if I
do...

[chrisha, 2015/10/30 15:11:54]

How about letting "git cl format" solve this problem?

+  int32_t type;  // 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 version;  // version code so upgrades don't break
+  subtle::Atomic32 freeptr;  // offset to first free space in the segment
+  int32_t reserved[2];  // padding to ensure size is multiple of alignment

[Alexander Potapenko, 2015/10/30 06:53:13]

I think it's more common to put the padding at the end of the structure, not in
the middle.

[bcwhite, 2015/10/30 14:01:10]

The "BlockHeader" entry must be the very last entry so that it starts on a
proper alignment boundary.

+  char corrupted;  // flag indicating that corruption has been detected
+  char full;  // flag indicating that alloc failed because segment is full
+  char flags[2];  // align to next int (not strictly needed but avoid confusion)
+
+  // 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.
+#define OFFSET_QUEUE offsetof(SharedMetadata, queue)
+#define OFFSET_NULL 0  // the equivalest NULL value for an offset

[Alexander Potapenko, 2015/10/30 06:53:13]

I think '0' is good enough to not introduce a constant effectively meaning zero.

[bcwhite, 2015/10/30 14:01:10]

I could just use NULL since it is defined as ``0''.  I was trying to be
descriptive (self-documenting code) without adding confusion since everybody
associates NULL with pointers.

Thoughts?

+
+SharedMemoryAllocator::SharedMemoryAllocator(void* base, int32_t size,
+                                             int32_t page)

[Alexander Potapenko, 2015/10/30 06:53:13]

s/page/page_size/

[bcwhite, 2015/10/30 14:01:10]

Done.

+  : shared_meta_(static_cast<SharedMetadata*>(base)),
+    mem_base_(static_cast<char*>(base)),
+    mem_size_(size),
+    mem_page_(page ? page : size),
+    last_seen_(0),
+    corrupted_(false) {
+  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");
+
+  DCHECK(base && reinterpret_cast<uintptr_t>(base) % kAllocAlignment == 0);
+  DCHECK(size >= 1 << 10 && size <= 1 << 20 &&  // 1 KiB <= size <= 1 MiB
+         size % kAllocAlignment == 0);
+  DCHECK(page >= 0 && (page == 0 || size % page == 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 ||

[Alexander Potapenko, 2015/10/30 06:53:13]

Can these checks be moved to the SharedMetadata constructor?
Also, you seem to be just asserting the whole memory buffer is zeroed.
Instead of writing this if-statement you can:
a) scan the memory to make sure all the bytes are zeroes
b) zero-fill this memory

[bcwhite, 2015/10/30 14:01:10]

I don't think so because (1) it's never constructed and (2) it would have to be
called only for newly created allocations.
It must be zero but only when first attached.  If other processes attach it, the
global-cookie will be set indicating that it is already initialized.

Also, it's not allowed to zero the memory here because (1) it doesn't know if
it's the first or later attachment and (2) accessing all memory would "realize"
that memory -- in the case of memory-mapped files, the file size could start at
zero and auto-grow as needed; we don't want to "need" it before we really need
it.

+        shared_meta_->size != 0 ||
+        shared_meta_->version != 0 ||
+        shared_meta_->freeptr != 0 ||

[Alexander Potapenko, 2015/10/30 06:53:13]

shared_meta_->freeptr is an atomic and should be accessed as such.

[bcwhite, 2015/10/30 14:01:10]

Right.  It doesn't actually affect anything at this point but I think TSAN or
similar checks these things.

+        shared_meta_->corrupted != 0 ||
+        shared_meta_->full != 0 ||
+        shared_meta_->tailptr != 0 ||
+        shared_meta_->queue.cookie != 0 ||
+        shared_meta_->queue.next != 0 ||
+        first_block->size != 0 ||
+        first_block->cookie != 0 ||
+        first_block->type != 0 ||
+        first_block->next != 0) {
+      // ...or something malicious has been playing with the metadata.
+      SetCorrupted();
+    }
+
+    // This is still safe to do even if corruption has been detected.

[Alexander Potapenko, 2015/10/30 06:53:13]

Why bother if we've detected the corruption? Shouldn't we just bail out?

[bcwhite, 2015/10/30 14:01:10]

It doesn't change anything either way.  I opted for simpler code but could use
"else" or "return" to skip it.

+    shared_meta_->cookie = kGlobalCookie;
+    shared_meta_->size = size;
+    shared_meta_->version = kGlobalVersion;
+    subtle::NoBarrier_Store(&shared_meta_->freeptr, sizeof(SharedMetadata));

[Alexander Potapenko, 2015/10/30 06:53:13]

Shouldn't this be a Release_Store?
shared_meta_->freeptr is read using an Acquire_Load.

[bcwhite, 2015/10/30 14:01:10]

My understanding is that acquire/release affects only memory ordering of
operations directly around this statement and has no bearing on other parts of
the code or other threads.

From atomicops.h:
"Acquire" operations ensure that no later memory access can be reordered ahead
of the operation.  "Release" operations ensure that no previous memory access
can be reordered after the operation.  "Barrier" operations have both "Acquire"
and "Release" semantics.

+
+    // 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, OFFSET_QUEUE);
+    subtle::NoBarrier_Store(&shared_meta_->tailptr, OFFSET_QUEUE);
+  }
+}
+
+SharedMemoryAllocator::~SharedMemoryAllocator() {
+}
+
+int32_t SharedMemoryAllocator::Allocate(int32_t size, int32_t type) {
+  if (size < 0) {
+    NOTREACHED();
+    return OFFSET_NULL;
+  }
+
+  // Round up the requested size, plus header, to the next allocation alignment.
+  size += sizeof(BlockHeader);
+  size = (size + (kAllocAlignment - 1)) & ~(kAllocAlignment - 1);
+  if (size > mem_page_)
+    return OFFSET_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 (IsCorrupted())
+      return OFFSET_NULL;
+
+    int32_t freeptr = subtle::Acquire_Load(&shared_meta_->freeptr);
+    if (freeptr + size > mem_size_) {
+      shared_meta_->full = true;
+      return OFFSET_NULL;
+    }
+    BlockHeader* block = GetBlock(freeptr, 0, 0, true);
+    if (!block) {
+      SetCorrupted();
+      return OFFSET_NULL;
+    }
+
+    // An allocation cannot cross page boundaries.  If it would, create a
+    // "wasted" block and begin again at the top of the next page.
+    int32_t page_free = mem_page_ - freeptr % mem_page_;
+    if (size > page_free) {
+      int32_t new_freeptr = freeptr + page_free;
+      if (subtle::Release_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.
+    if (page_free - size < (int)(sizeof(BlockHeader) + kAllocAlignment))
+      size = page_free;

[Alexander Potapenko, 2015/10/30 06:53:13]

It may be worth noticing in the comments that the size of the allocated block
may be greater than the requested size + header size + alignment.

[bcwhite, 2015/10/30 14:01:10]

Done.

+
+    int32_t new_freeptr = freeptr + size;
+    if (new_freeptr > mem_size_) {
+      SetCorrupted();
+      return OFFSET_NULL;
+    }
+
+    if (subtle::Release_CompareAndSwap(
+            &shared_meta_->freeptr, freeptr, new_freeptr) != freeptr) {
+      // Another thread must have completed an allocation while we were working.
+      // Try again.
+      continue;
+    }
+
+    // Since allocating a block is atomic and all unallocated memory must be
+    // zeros, any other value indicates that something has run amuck.

[Alexander Potapenko, 2015/10/30 06:53:13]

Can you please elaborate on how's that possible?

[bcwhite, 2015/10/30 14:01:10]

Done.

+    if (block->size != 0 ||
+        block->cookie != kBlockCookieFree ||
+        block->type != 0 ||
+        subtle::NoBarrier_Load(&block->next) != 0) {
+      SetCorrupted();
+      return OFFSET_NULL;
+    }
+
+    block->size = size;
+    block->cookie = kBlockCookieAllocated;
+    block->type = type;
+    return freeptr;
+  }
+}
+
+void SharedMemoryAllocator::GetMemoryInfo(MemoryInfo* meminfo) {
+  int32_t remaining =
+      mem_size_ - subtle::NoBarrier_Load(&shared_meta_->freeptr);
+  meminfo->total = mem_size_;
+  meminfo->free = shared_meta_->corrupted ? 0 : remaining - sizeof(BlockHeader);

[Alexander Potapenko, 2015/10/30 06:53:13]

Shouldn't we use IsCorrupted() here?

[bcwhite, 2015/10/30 14:01:10]

Definitely.

+}
+
+void SharedMemoryAllocator::MakeIterable(int32_t offset) {
+  if (IsCorrupted())
+    return;
+  BlockHeader* block = GetBlock(offset, 0, 0, false);
+  if (!block)  // invalid offset
+    return;
+  if (subtle::NoBarrier_Load(&block->next) != 0)  // previously set iterable
+    return;
+  subtle::NoBarrier_Store(&block->next, OFFSET_QUEUE);  // will be tail block
+
+  // Try to add this block to the tail of the queue.  May take multiple tries.
+  int32_t tail;
+  for (;;) {
+    tail = subtle::Acquire_Load(&shared_meta_->tailptr);
+    block = GetBlock(tail, 0, 0, true);
+    if (!block) {
+      SetCorrupted();
+      return;
+    }
+    int32_t next = subtle::NoBarrier_Load(&block->next);
+
+    // Ensure that the tail pointer didn't change while reading next.

[Alexander Potapenko, 2015/10/30 06:53:13]

Why do you need that?
What happens if the tail pointer changes after you ensure that?

[bcwhite, 2015/10/30 14:01:10]

Only the read of the tail pointer is atomic but we need to read both the tail
pointer and the next pointer from it in an atomic fashion.  The way to do this
is to read both non-atomically and then verify after the last read that the
first read is still valid/unchanged.

I'll add that to the comment.
Then we go about preparing to append the current node in the wrong place but
fail to do so at the CAS down on line 241/242, starting over.

+    if (tail == subtle::Release_Load(&shared_meta_->tailptr)) {

[Alexander Potapenko, 2015/10/30 06:53:13]

Most certainly you do not want to use Release_Load().

[bcwhite, 2015/10/30 14:01:10]

Why?  It ensures no previous memory access in the code above will get reordered
after this.

+      // Check if the found block is truely the last in the queue (i.e. it
+      // points back to the "queue" node).
+      if (next == OFFSET_QUEUE) {
+        // Yes.  Try to append the passed block after the current tail block.
+        if (subtle::Release_CompareAndSwap(
+                &block->next, OFFSET_QUEUE, offset) == OFFSET_QUEUE) {

[Alexander Potapenko, 2015/10/30 06:53:13]

Please mind the indentation.

[bcwhite, 2015/10/30 14:01:10]

Isn't it supposed to be indented 4 spaces from the start of the function call?

[chrisha, 2015/10/30 15:11:53]

git cl format will take care of these things for you

[bcwhite, 2015/10/30 15:15:35]

I tried that.  It made it worse (IMO) by splitting the parameters across the
first and second lines and indenting all the way to the parenthesis.

I'll do a full "git cl format" cleanup at some point.

+          // Success!  The block is enqueued; need to update the tail pointer.
+          break;
+        }
+      } else {
+        // No.  Another thread has stopped between the block-next update
+        // and the tail-pointer update.  Try to update tailptr past the
+        // found block.  That other thread may complete it first or it
+        // may have crashed.  Be fail-safe.
+        subtle::Release_CompareAndSwap(&shared_meta_->tailptr, tail, next);
+      }
+    }
+  }
+
+  // Block has been enqueued.  Now update the tail-pointer past it.  This
+  // could fail if another thread has already completed the operation as
+  // part of being fail-safe.
+  subtle::Release_CompareAndSwap(&shared_meta_->tailptr, tail, offset);
+}
+
+int32_t SharedMemoryAllocator::GetFirstIterable(Iterator* state,
+                                                int32_t* type) {
+  state->last = OFFSET_QUEUE;
+  return GetNextIterable(state, type);
+}
+
+int32_t SharedMemoryAllocator::GetNextIterable(Iterator* state, int32_t* type) {
+  const BlockHeader* block = GetBlock(state->last, 0, 0, true);
+  if (!block)  // invalid iterator state
+    return OFFSET_NULL;
+  int32_t next = subtle::NoBarrier_Load(&block->next);
+  block = GetBlock(next, 0, 0, false);
+  if (!block)  // no next allocation in queue
+    return OFFSET_NULL;
+
+  state->last = next;
+  *type = block->type;
+  return next;
+}
+
+void SharedMemoryAllocator::SetCorrupted() {

[Alexander Potapenko, 2015/10/30 06:53:13]

Can SetCorrupted() and IsCorrupted() be called from different threads?

[bcwhite, 2015/10/30 14:01:10]

Certainly.  See previous comment on this.

+  LOG(ERROR) << "Corruption detected in shared-memory segment.";
+  corrupted_ = true;
+  shared_meta_->corrupted = true;
+}
+
+bool SharedMemoryAllocator::IsCorrupted() {
+  if (corrupted_ || shared_meta_->corrupted) {
+    SetCorrupted();  // Make sure all indicators are set.
+    return true;
+  }
+  return false;
+}
+
+bool SharedMemoryAllocator::IsFull() {

[Alexander Potapenko, 2015/10/30 06:53:13]

How will IsFull() be used?
Looks like a data race between it and Allocate() is possible.

[bcwhite, 2015/10/30 14:01:10]

It's just informational to the caller.  Data-race is not important for the same
reason as IsCorrupted() -- it's safe either way.

+  return shared_meta_->full != 0;
+}
+
+SharedMemoryAllocator::BlockHeader* SharedMemoryAllocator::GetBlock(
+    int32_t offset, int32_t type, int32_t size, bool special) {
+  // Validation of parameters.
+  if (offset % kAllocAlignment != 0)
+    return nullptr;
+  if (offset < (int)(special ? OFFSET_QUEUE : sizeof(SharedMetadata)))

[Alexander Potapenko, 2015/10/30 06:53:13]

It's unclear what 'special' stands for.

[bcwhite, 2015/10/30 14:01:10]

"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.

I'll add a comment.  I could change the name of the parameter to "system" or
"meta_ok" if that would be more clear.

+    return nullptr;
+  size += sizeof(BlockHeader);
+  if (offset + size > mem_size_)
+    return nullptr;
+  int32_t freeptr = subtle::NoBarrier_Load(&shared_meta_->freeptr);
+  if (offset + size > freeptr + (int)(special ? sizeof(BlockHeader) : 0))
+    return nullptr;
+
+  // Validation of referenced block-header.
+  const BlockHeader* block = reinterpret_cast<BlockHeader*>(mem_base_ + offset);
+  if (offset != freeptr && block->size < size)
+    return nullptr;
+  if (!special && block->cookie != kBlockCookieAllocated)
+    return nullptr;
+  if (type != 0 && block->type != type)
+    return nullptr;
+
+  // Return pointer to block data.
+  return reinterpret_cast<BlockHeader*>(mem_base_ + offset);
+}
+
+void* SharedMemoryAllocator::GetBlockData(int32_t offset, int32_t type,
+                                          int32_t size, bool special) {
+  DCHECK(size > 0);
+  BlockHeader* block = GetBlock(offset, type, size, special);
+  if (!block)
+    return nullptr;
+  return reinterpret_cast<char*>(block) + sizeof(BlockHeader);
+}
+
+}  // namespace base