Index: base/memory/shared_memory_allocator.cc |
diff --git a/base/memory/shared_memory_allocator.cc b/base/memory/shared_memory_allocator.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..05800385e05808c2b2d2c5cc61ac79f14df34736 |
--- /dev/null |
+++ b/base/memory/shared_memory_allocator.cc |
@@ -0,0 +1,336 @@ |
+// 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://googl
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
bcwhite
2015/10/30 14:01:10
*I* prefer it but I've gotten nags in the past tha
chrisha
2015/10/30 15:11:54
How about letting "git cl format" solve this probl
|
+ 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
bcwhite
2015/10/30 14:01:10
The "BlockHeader" entry must be the very last entr
|
+ 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 cons
bcwhite
2015/10/30 14:01:10
I could just use NULL since it is defined as ``0''
|
+ |
+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 co
bcwhite
2015/10/30 14:01:10
I don't think so because (1) it's never constructe
|
+ 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 a
bcwhite
2015/10/30 14:01:10
Right. It doesn't actually affect anything at thi
|
+ 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? Shoul
bcwhite
2015/10/30 14:01:10
It doesn't change anything either way. I opted fo
|
+ 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_->f
bcwhite
2015/10/30 14:01:10
My understanding is that acquire/release affects o
|
+ |
+ // 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
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 poi
bcwhite
2015/10/30 14:01:10
Only the read of the tail pointer is atomic but we
|
+ 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
|
+ // 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
chrisha
2015/10/30 15:11:53
git cl format will take care of these things for y
bcwhite
2015/10/30 15:15:35
I tried that. It made it worse (IMO) by splitting
|
+ // 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 fro
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
bcwhite
2015/10/30 14:01:10
It's just informational to the caller. Data-race
|
+ 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 bloc
|
+ 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 |