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

base/memory/shared_memory_allocator.h

Index: base/memory/shared_memory_allocator.h
diff --git a/base/memory/shared_memory_allocator.h b/base/memory/shared_memory_allocator.h
new file mode 100644
index 0000000000000000000000000000000000000000..74ad9eb742d7f37634634479acb1f5a188d8434d
--- /dev/null
+++ b/base/memory/shared_memory_allocator.h
@@ -0,0 +1,101 @@
+// 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_MEMORY_SHARED_MEMORY_ALLOCATOR_H_
+#define BASE_MEMORY_SHARED_MEMORY_ALLOCATOR_H_
+
+#include "base/base_export.h"
+#include "base/basictypes.h"
+
+namespace base {
+
+// Simple allocator for pieces of a memory block that may be shared across
+// multiple processes.

[chrisha, 2015/10/29 21:05:14]

More detailed comments about the thread safety guarantees this achieves, and the
fact that this is monotonic (ie: no frees...)

[bcwhite, 2015/10/29 23:40:58]

Done.

+class BASE_EXPORT SharedMemoryAllocator {
+ public:
+  struct Iterator {
+    int32 last;
+  };
+
+  struct MemoryInfo {
+    int32 total;
+    int32 free;
+  };
+
+  // The allocator operates on any arbitrary block of memory.  Creation and
+  // 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

[chrisha, 2015/10/29 21:05:14]

micronit: The more common pattern in Chrome is a single space after a period
when starting a new sentence. (Roughly 5:1 usage of single space versus double
space, from a few quick greps.)

[bcwhite, 2015/10/29 23:40:58]

I can't.  I'm sorry.  <hanging head in shame>  Blame it on my 7th grade typing
teacher.  Always 2 spaces after a period.

[chrisha, 2015/10/30 14:36:46]

http://www.slate.com/articles/technology/technology/2011/01/space_invaders.html

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

Heh!  Yeah, I've read that.  It even makes sense.  But when I say "I can't", I
mean I physically can't.  Double spacing after periods is such a ingrained habit
that I can't break.  And I have tried.  I'm pedantic enough that I had to try. 
It doesn't help that it now simply looks completely "wrong" to me for a single
space to be there.

I'll do a global search/replace when this is nearing completion.  If I do it
sooner, more will sneak in.  In the mean time, please suffer my personal failing
in this regard.  :-)

+  // total |size| of the block, and any internal |page| size (zero if not
+  // paged) across which allocations should not span.
+  //
+  // SharedMemoryAllocator does NOT take ownership of this memory block.  The
+  // caller must manage it and ensure it stays available throughout the lifetime
+  // of this object.
+  SharedMemoryAllocator(void* base, int32 size, int32 page);

[chrisha, 2015/10/29 21:05:14]

(We now use int32_t instead of int32.)

Shouldn't these all be uint32_t, or size_t? Given that they are strictly
non-negative quantities. (Here and most everywhere in the API.)

[bcwhite, 2015/10/29 23:40:57]

Awww.... shoot.
I tried going that way early on.  However, Atomic32 is always a signed value and
the mixing of signed and unsigned values causes either excessive compiler errors
or excessive casting.  Since we're talking small values (kilobytes at most),
there isn't any danger of overflowing even a signed integer.  It's much simpler
this way.

[chrisha, 2015/10/30 14:36:46]

Okay, sounds like a reasonable reason to me. Worth a comment somewhere?

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

Done.

+  ~SharedMemoryAllocator();
+
+  // Get an object referenced by an |offset|.  For safety reasons, the |type|
+  // code and size-of |unused| are compared to ensure the reference is valid
+  // and cannot return an object outside of the memory segment.  A |type| of
+  // zero will match any though the size is still checked.  NULL is returned
+  // 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
+  // is safe to reuse forever.
+  template<typename T> T* GetObject(int32 offset, int32 type, T* unused) {

[chrisha, 2015/10/29 21:05:14]

Why pass a T* unused instead of just getting having the caller specify the type
via GetObject<T>(...)? Syntactic sugar?

Also, I'm curious what this is needed for. Presumably users are going to make an
allocation and remember the returned pointer, and won't need to go try and look
up the object again by offset? Why should users be aware of the concept of
offsets at all?

And finally, why do we need the notion of types? This makes this non-standard
from most allocators, which only care about ranges of memory of a fixed size. If
the thing you need to build on *top* of the allocator needs to be explicitly
type aware, then provide the type info at that layer?

[bcwhite, 2015/10/29 23:40:58]

That works.  Done.
Callers need to be returned an offset from an allocation in case they want to
store that reference inside another object.  A Histogram, for example, has a
name.  That name needs to be stored in the shared memory and the object needs to
reference it.  References can be only offsets since pointers would be invalid in
another process should it map the segment at a different address.

 
It could certainly be done that way.  I did it this way to force some basic
checking based on type.  By passing knowledge of the object to the allocator, it
can ensure that the memory it is returning is capable of at least holding that
object.  If that was not done, it would be possible to craft a malicious memory
segment that could cause a segmentation fault in another process.

[chrisha, 2015/10/30 14:36:46]

The offset isn't sufficient in this case, because things may live in multiple
independent memory segments, so you'll need both some kind of segment ID and an
offset.

Why not just abstract this away entirely and have the UMA allocator tie things
together with IDs? (ie: hashes of the name, the bucket metadata, etc). The
actual renderer using this allocator will keep direct pointers to things, and
can store sufficient metadata into the individual allocations (representing
various parts of the histograms) so that they can subsequently be tied together
when read. No need for pointers or offsets at all.
I feel like you're mixing things that are specific to the UMA storage layer and
things that are specific to the allocator.

The allocator need only be able to return chunks of memory with a given size.
Anybody with access to the memory can screw up the allocator and the data stored
within it, regardless of any security measures you put in place. I agree that a
simple 'consistency' check (checksum of block headers? constant cookie?) are
useful because they quickly provide information about derails. However, the type
means nothing to somebody parsing a range of allocations... it means something
to the *user* of the segment, but not to the segment itself. I strongly feel it
should be in the storage layer, not the allocator layer.

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

Acknowledged.

+    return static_cast<T*>(GetBlockData(offset, type, sizeof(T), false));
+  }
+
+  // Reserve space in the memory segment of the desired |size| and |type|.
+  // A return value of zero indicates the allocation failed, otherwise the
+  // returned offset can be used by any process to get a real pointer via
+  // the GetObject() call.
+  int32 Allocate(int32 size, int32 type);
+
+  // 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 meta-data, but will never return less than could actually
+  // be allocated.
+  void GetMemoryInfo(MemoryInfo* meminfo);
+
+  // Allocated objects can be added to an internal list that can then be
+  // iterated over by other processes.
+  void MakeIterable(int32 offset);

[chrisha, 2015/10/29 21:05:14]

Why do you need this? The implementation already has all the information
required to perform iteration...

[bcwhite, 2015/10/29 23:40:58]

Unfortunately, it doesn't.  If you try to make it iterable during the
allocation, you get a race condition between the filling in of the iteration
information (the block header) and the update of the "global_freeptr".  It's
possible for a process to iterate into the newly allocated block before size and
other things get set.  See comments on my design document for details.

As a bonus, not all allocations need to be made iterable.  The histogram names,
for example, can be omitted.

[chrisha, 2015/10/30 14:36:46]

Still implementation details. This should be entirely internal:

- carve out space by incrementing the cursor
  (Any other allocations will strictly go to the end, no conflict. The
   allocation is still not iterable, but that's fine.)
- initialize the block header, the memory, etc.
  (The allocation is still not iterable, but that's fine.)
- weave the allocation into the link list using atomics.

Thus, the 'MakeIterable' (weave into the link list) could be entirely private
and an implementation detail.

If something doesn't need to be iterable (ie: the reader doesn't care about),
then I wouldn't store it in the shared memory segment. I'd store it in the
regular heap and let it die with the process. I'd only use the shared memory for
things that must be communicated, in which case all of the allocations need to
be iterable.

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

Acknowledged.

+
+  // Iterating uses a |state| structure (initialized by GetFirstIterable) and
+  // returns both the offset reference to the object as well as the |type| 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".
+  int32 GetFirstIterable(Iterator* state, int32* type);
+  int32 GetNextIterable(Iterator* state, int32* type);
+
+  // If there is some indication that the shared memory has become corrupted,
+  // calling this will attempt to prevent further damage by indicating to
+  // all processes that something is not as expected.
+  void SetCorrupted();
+  bool IsCorrupted();
+
+  // Flag set if an allocation has failed because memory was full.
+  bool IsFull();
+
+ private:
+  struct SharedMetaData;

[chrisha, 2015/10/29 21:05:14]

Metadata is a single word, no need to capitalize Data.

[bcwhite, 2015/10/29 23:40:58]

Done.

+  struct BlockHeader;
+
+  BlockHeader* GetBlock(int32 offset, int32 type, int32 size, bool special);
+  void* GetBlockData(int32 offset, int32 type, int32 size, bool special);
+
+  SharedMetaData* shared_meta_;
+  char* mem_base_;  // char because sizeof guaranteed 1 -- easy offset calc
+  int32 mem_size_;
+  int32 mem_page_;

[chrisha, 2015/10/29 21:05:14]

Do we really care about page sizes? What's the harm in allowing allocations to
cross a page boundary? (This happens all the time with most any allocator. I'd
be more worried about crossing cache lines for small allocations.)

And if we do, isn't this an implementation detail? (ie: platform specific, but
knowable from the system and doesn't need to be provided) Maybe you only need to
inform the allocator whether or not you care about crossing page boundaries, but
not what the page size is?

[bcwhite, 2015/10/29 23:40:58]

Probably not.  However, if this were to be used against a memory-mapped file,
then an allocation that crossed page boundaries could cause two pages to be
dirtied and written to disk.

If pages aren't a concern on whatever memory is being assigned, just set it to
zero and it'll be ignored.
Possibly but since the management of the memory segment is external, I think it
best to get the page size knowledge from that external source rather than make
assumptions here.

[chrisha, 2015/10/30 14:36:46]

Okay, I'm fine with that.

+  int32 last_seen_;
+  bool corrupted_;
+
+  DISALLOW_COPY_AND_ASSIGN(SharedMemoryAllocator);
+};
+}  // namespace base
+
+#endif  // BASE_MEMORY_SHARED_MEMORY_ALLOCATOR_H_