• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2015 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "base/metrics/persistent_memory_allocator.h"
6 
7 #include <assert.h>
8 #include <algorithm>
9 
10 #if defined(OS_WIN)
11 #include <windows.h>
12 #include "winbase.h"
13 #elif defined(OS_POSIX) || defined(OS_FUCHSIA)
14 #include <sys/mman.h>
15 #endif
16 
17 #include "base/files/memory_mapped_file.h"
18 #include "base/logging.h"
19 #include "base/memory/shared_memory.h"
20 #include "base/metrics/histogram_functions.h"
21 #include "base/metrics/sparse_histogram.h"
22 #include "base/numerics/safe_conversions.h"
23 #include "base/sys_info.h"
24 #include "base/threading/thread_restrictions.h"
25 #include "build/build_config.h"
26 
27 namespace {
28 
29 // Limit of memory segment size. It has to fit in an unsigned 32-bit number
30 // and should be a power of 2 in order to accomodate almost any page size.
31 const uint32_t kSegmentMaxSize = 1 << 30;  // 1 GiB
32 
33 // A constant (random) value placed in the shared metadata to identify
34 // an already initialized memory segment.
35 const uint32_t kGlobalCookie = 0x408305DC;
36 
37 // The current version of the metadata. If updates are made that change
38 // the metadata, the version number can be queried to operate in a backward-
39 // compatible manner until the memory segment is completely re-initalized.
40 const uint32_t kGlobalVersion = 2;
41 
42 // Constant values placed in the block headers to indicate its state.
43 const uint32_t kBlockCookieFree = 0;
44 const uint32_t kBlockCookieQueue = 1;
45 const uint32_t kBlockCookieWasted = (uint32_t)-1;
46 const uint32_t kBlockCookieAllocated = 0xC8799269;
47 
48 // TODO(bcwhite): When acceptable, consider moving flags to std::atomic<char>
49 // types rather than combined bitfield.
50 
51 // Flags stored in the flags_ field of the SharedMetadata structure below.
52 enum : int {
53   kFlagCorrupt = 1 << 0,
54   kFlagFull    = 1 << 1
55 };
56 
57 // Errors that are logged in "errors" histogram.
58 enum AllocatorError : int {
59   kMemoryIsCorrupt = 1,
60 };
61 
CheckFlag(const volatile std::atomic<uint32_t> * flags,int flag)62 bool CheckFlag(const volatile std::atomic<uint32_t>* flags, int flag) {
63   uint32_t loaded_flags = flags->load(std::memory_order_relaxed);
64   return (loaded_flags & flag) != 0;
65 }
66 
SetFlag(volatile std::atomic<uint32_t> * flags,int flag)67 void SetFlag(volatile std::atomic<uint32_t>* flags, int flag) {
68   uint32_t loaded_flags = flags->load(std::memory_order_relaxed);
69   for (;;) {
70     uint32_t new_flags = (loaded_flags & ~flag) | flag;
71     // In the failue case, actual "flags" value stored in loaded_flags.
72     // These access are "relaxed" because they are completely independent
73     // of all other values.
74     if (flags->compare_exchange_weak(loaded_flags, new_flags,
75                                      std::memory_order_relaxed,
76                                      std::memory_order_relaxed)) {
77       break;
78     }
79   }
80 }
81 
82 }  // namespace
83 
84 namespace base {
85 
86 // All allocations and data-structures must be aligned to this byte boundary.
87 // Alignment as large as the physical bus between CPU and RAM is _required_
88 // for some architectures, is simply more efficient on other CPUs, and
89 // generally a Good Idea(tm) for all platforms as it reduces/eliminates the
90 // chance that a type will span cache lines. Alignment mustn't be less
91 // than 8 to ensure proper alignment for all types. The rest is a balance
92 // between reducing spans across multiple cache lines and wasted space spent
93 // padding out allocations. An alignment of 16 would ensure that the block
94 // header structure always sits in a single cache line. An average of about
95 // 1/2 this value will be wasted with every allocation.
96 const uint32_t PersistentMemoryAllocator::kAllocAlignment = 8;
97 
98 // The block-header is placed at the top of every allocation within the
99 // segment to describe the data that follows it.
100 struct PersistentMemoryAllocator::BlockHeader {
101   uint32_t size;       // Number of bytes in this block, including header.
102   uint32_t cookie;     // Constant value indicating completed allocation.
103   std::atomic<uint32_t> type_id;  // Arbitrary number indicating data type.
104   std::atomic<uint32_t> next;     // Pointer to the next block when iterating.
105 };
106 
107 // The shared metadata exists once at the top of the memory segment to
108 // describe the state of the allocator to all processes. The size of this
109 // structure must be a multiple of 64-bits to ensure compatibility between
110 // architectures.
111 struct PersistentMemoryAllocator::SharedMetadata {
112   uint32_t cookie;     // Some value that indicates complete initialization.
113   uint32_t size;       // Total size of memory segment.
114   uint32_t page_size;  // Paging size within memory segment.
115   uint32_t version;    // Version code so upgrades don't break.
116   uint64_t id;         // Arbitrary ID number given by creator.
117   uint32_t name;       // Reference to stored name string.
118   uint32_t padding1;   // Pad-out read-only data to 64-bit alignment.
119 
120   // Above is read-only after first construction. Below may be changed and
121   // so must be marked "volatile" to provide correct inter-process behavior.
122 
123   // State of the memory, plus some padding to keep alignment.
124   volatile std::atomic<uint8_t> memory_state;  // MemoryState enum values.
125   uint8_t padding2[3];
126 
127   // Bitfield of information flags. Access to this should be done through
128   // the CheckFlag() and SetFlag() methods defined above.
129   volatile std::atomic<uint32_t> flags;
130 
131   // Offset/reference to first free space in segment.
132   volatile std::atomic<uint32_t> freeptr;
133 
134   // The "iterable" queue is an M&S Queue as described here, append-only:
135   // https://www.research.ibm.com/people/m/michael/podc-1996.pdf
136   // |queue| needs to be 64-bit aligned and is itself a multiple of 64 bits.
137   volatile std::atomic<uint32_t> tailptr;  // Last block of iteration queue.
138   volatile BlockHeader queue;   // Empty block for linked-list head/tail.
139 };
140 
141 // The "queue" block header is used to detect "last node" so that zero/null
142 // can be used to indicate that it hasn't been added at all. It is part of
143 // the SharedMetadata structure which itself is always located at offset zero.
144 const PersistentMemoryAllocator::Reference
145     PersistentMemoryAllocator::kReferenceQueue =
146         offsetof(SharedMetadata, queue);
147 
148 const base::FilePath::CharType PersistentMemoryAllocator::kFileExtension[] =
149     FILE_PATH_LITERAL(".pma");
150 
151 
Iterator(const PersistentMemoryAllocator * allocator)152 PersistentMemoryAllocator::Iterator::Iterator(
153     const PersistentMemoryAllocator* allocator)
154     : allocator_(allocator), last_record_(kReferenceQueue), record_count_(0) {}
155 
Iterator(const PersistentMemoryAllocator * allocator,Reference starting_after)156 PersistentMemoryAllocator::Iterator::Iterator(
157     const PersistentMemoryAllocator* allocator,
158     Reference starting_after)
159     : allocator_(allocator), last_record_(0), record_count_(0) {
160   Reset(starting_after);
161 }
162 
Reset()163 void PersistentMemoryAllocator::Iterator::Reset() {
164   last_record_.store(kReferenceQueue, std::memory_order_relaxed);
165   record_count_.store(0, std::memory_order_relaxed);
166 }
167 
Reset(Reference starting_after)168 void PersistentMemoryAllocator::Iterator::Reset(Reference starting_after) {
169   if (starting_after == 0) {
170     Reset();
171     return;
172   }
173 
174   last_record_.store(starting_after, std::memory_order_relaxed);
175   record_count_.store(0, std::memory_order_relaxed);
176 
177   // Ensure that the starting point is a valid, iterable block (meaning it can
178   // be read and has a non-zero "next" pointer).
179   const volatile BlockHeader* block =
180       allocator_->GetBlock(starting_after, 0, 0, false, false);
181   if (!block || block->next.load(std::memory_order_relaxed) == 0) {
182     NOTREACHED();
183     last_record_.store(kReferenceQueue, std::memory_order_release);
184   }
185 }
186 
187 PersistentMemoryAllocator::Reference
GetLast()188 PersistentMemoryAllocator::Iterator::GetLast() {
189   Reference last = last_record_.load(std::memory_order_relaxed);
190   if (last == kReferenceQueue)
191     return kReferenceNull;
192   return last;
193 }
194 
195 PersistentMemoryAllocator::Reference
GetNext(uint32_t * type_return)196 PersistentMemoryAllocator::Iterator::GetNext(uint32_t* type_return) {
197   // Make a copy of the existing count of found-records, acquiring all changes
198   // made to the allocator, notably "freeptr" (see comment in loop for why
199   // the load of that value cannot be moved above here) that occurred during
200   // any previous runs of this method, including those by parallel threads
201   // that interrupted it. It pairs with the Release at the end of this method.
202   //
203   // Otherwise, if the compiler were to arrange the two loads such that
204   // "count" was fetched _after_ "freeptr" then it would be possible for
205   // this thread to be interrupted between them and other threads perform
206   // multiple allocations, make-iterables, and iterations (with the included
207   // increment of |record_count_|) culminating in the check at the bottom
208   // mistakenly determining that a loop exists. Isn't this stuff fun?
209   uint32_t count = record_count_.load(std::memory_order_acquire);
210 
211   Reference last = last_record_.load(std::memory_order_acquire);
212   Reference next;
213   while (true) {
214     const volatile BlockHeader* block =
215         allocator_->GetBlock(last, 0, 0, true, false);
216     if (!block)  // Invalid iterator state.
217       return kReferenceNull;
218 
219     // The compiler and CPU can freely reorder all memory accesses on which
220     // there are no dependencies. It could, for example, move the load of
221     // "freeptr" to above this point because there are no explicit dependencies
222     // between it and "next". If it did, however, then another block could
223     // be queued after that but before the following load meaning there is
224     // one more queued block than the future "detect loop by having more
225     // blocks that could fit before freeptr" will allow.
226     //
227     // By "acquiring" the "next" value here, it's synchronized to the enqueue
228     // of the node which in turn is synchronized to the allocation (which sets
229     // freeptr). Thus, the scenario above cannot happen.
230     next = block->next.load(std::memory_order_acquire);
231     if (next == kReferenceQueue)  // No next allocation in queue.
232       return kReferenceNull;
233     block = allocator_->GetBlock(next, 0, 0, false, false);
234     if (!block) {  // Memory is corrupt.
235       allocator_->SetCorrupt();
236       return kReferenceNull;
237     }
238 
239     // Update the "last_record" pointer to be the reference being returned.
240     // If it fails then another thread has already iterated past it so loop
241     // again. Failing will also load the existing value into "last" so there
242     // is no need to do another such load when the while-loop restarts. A
243     // "strong" compare-exchange is used because failing unnecessarily would
244     // mean repeating some fairly costly validations above.
245     if (last_record_.compare_exchange_strong(
246             last, next, std::memory_order_acq_rel, std::memory_order_acquire)) {
247       *type_return = block->type_id.load(std::memory_order_relaxed);
248       break;
249     }
250   }
251 
252   // Memory corruption could cause a loop in the list. Such must be detected
253   // so as to not cause an infinite loop in the caller. This is done by simply
254   // making sure it doesn't iterate more times than the absolute maximum
255   // number of allocations that could have been made. Callers are likely
256   // to loop multiple times before it is detected but at least it stops.
257   const uint32_t freeptr = std::min(
258       allocator_->shared_meta()->freeptr.load(std::memory_order_relaxed),
259       allocator_->mem_size_);
260   const uint32_t max_records =
261       freeptr / (sizeof(BlockHeader) + kAllocAlignment);
262   if (count > max_records) {
263     allocator_->SetCorrupt();
264     return kReferenceNull;
265   }
266 
267   // Increment the count and release the changes made above. It pairs with
268   // the Acquire at the top of this method. Note that this operation is not
269   // strictly synchonized with fetching of the object to return, which would
270   // have to be done inside the loop and is somewhat complicated to achieve.
271   // It does not matter if it falls behind temporarily so long as it never
272   // gets ahead.
273   record_count_.fetch_add(1, std::memory_order_release);
274   return next;
275 }
276 
277 PersistentMemoryAllocator::Reference
GetNextOfType(uint32_t type_match)278 PersistentMemoryAllocator::Iterator::GetNextOfType(uint32_t type_match) {
279   Reference ref;
280   uint32_t type_found;
281   while ((ref = GetNext(&type_found)) != 0) {
282     if (type_found == type_match)
283       return ref;
284   }
285   return kReferenceNull;
286 }
287 
288 
289 // static
IsMemoryAcceptable(const void * base,size_t size,size_t page_size,bool readonly)290 bool PersistentMemoryAllocator::IsMemoryAcceptable(const void* base,
291                                                    size_t size,
292                                                    size_t page_size,
293                                                    bool readonly) {
294   return ((base && reinterpret_cast<uintptr_t>(base) % kAllocAlignment == 0) &&
295           (size >= sizeof(SharedMetadata) && size <= kSegmentMaxSize) &&
296           (size % kAllocAlignment == 0 || readonly) &&
297           (page_size == 0 || size % page_size == 0 || readonly));
298 }
299 
PersistentMemoryAllocator(void * base,size_t size,size_t page_size,uint64_t id,base::StringPiece name,bool readonly)300 PersistentMemoryAllocator::PersistentMemoryAllocator(void* base,
301                                                      size_t size,
302                                                      size_t page_size,
303                                                      uint64_t id,
304                                                      base::StringPiece name,
305                                                      bool readonly)
306     : PersistentMemoryAllocator(Memory(base, MEM_EXTERNAL),
307                                 size,
308                                 page_size,
309                                 id,
310                                 name,
311                                 readonly) {}
312 
PersistentMemoryAllocator(Memory memory,size_t size,size_t page_size,uint64_t id,base::StringPiece name,bool readonly)313 PersistentMemoryAllocator::PersistentMemoryAllocator(Memory memory,
314                                                      size_t size,
315                                                      size_t page_size,
316                                                      uint64_t id,
317                                                      base::StringPiece name,
318                                                      bool readonly)
319     : mem_base_(static_cast<char*>(memory.base)),
320       mem_type_(memory.type),
321       mem_size_(static_cast<uint32_t>(size)),
322       mem_page_(static_cast<uint32_t>((page_size ? page_size : size))),
323 #if defined(OS_NACL)
324       vm_page_size_(4096U),  // SysInfo is not built for NACL.
325 #else
326       vm_page_size_(SysInfo::VMAllocationGranularity()),
327 #endif
328       readonly_(readonly),
329       corrupt_(0),
330       allocs_histogram_(nullptr),
331       used_histogram_(nullptr),
332       errors_histogram_(nullptr) {
333   // These asserts ensure that the structures are 32/64-bit agnostic and meet
334   // all the requirements of use within the allocator. They access private
335   // definitions and so cannot be moved to the global scope.
336   static_assert(sizeof(PersistentMemoryAllocator::BlockHeader) == 16,
337                 "struct is not portable across different natural word widths");
338   static_assert(sizeof(PersistentMemoryAllocator::SharedMetadata) == 64,
339                 "struct is not portable across different natural word widths");
340 
341   static_assert(sizeof(BlockHeader) % kAllocAlignment == 0,
342                 "BlockHeader is not a multiple of kAllocAlignment");
343   static_assert(sizeof(SharedMetadata) % kAllocAlignment == 0,
344                 "SharedMetadata is not a multiple of kAllocAlignment");
345   static_assert(kReferenceQueue % kAllocAlignment == 0,
346                 "\"queue\" is not aligned properly; must be at end of struct");
347 
348   // Ensure that memory segment is of acceptable size.
349   CHECK(IsMemoryAcceptable(memory.base, size, page_size, readonly));
350 
351   // These atomics operate inter-process and so must be lock-free. The local
352   // casts are to make sure it can be evaluated at compile time to a constant.
353   CHECK(((SharedMetadata*)nullptr)->freeptr.is_lock_free());
354   CHECK(((SharedMetadata*)nullptr)->flags.is_lock_free());
355   CHECK(((BlockHeader*)nullptr)->next.is_lock_free());
356   CHECK(corrupt_.is_lock_free());
357 
358   if (shared_meta()->cookie != kGlobalCookie) {
359     if (readonly) {
360       SetCorrupt();
361       return;
362     }
363 
364     // This block is only executed when a completely new memory segment is
365     // being initialized. It's unshared and single-threaded...
366     volatile BlockHeader* const first_block =
367         reinterpret_cast<volatile BlockHeader*>(mem_base_ +
368                                                 sizeof(SharedMetadata));
369     if (shared_meta()->cookie != 0 ||
370         shared_meta()->size != 0 ||
371         shared_meta()->version != 0 ||
372         shared_meta()->freeptr.load(std::memory_order_relaxed) != 0 ||
373         shared_meta()->flags.load(std::memory_order_relaxed) != 0 ||
374         shared_meta()->id != 0 ||
375         shared_meta()->name != 0 ||
376         shared_meta()->tailptr != 0 ||
377         shared_meta()->queue.cookie != 0 ||
378         shared_meta()->queue.next.load(std::memory_order_relaxed) != 0 ||
379         first_block->size != 0 ||
380         first_block->cookie != 0 ||
381         first_block->type_id.load(std::memory_order_relaxed) != 0 ||
382         first_block->next != 0) {
383       // ...or something malicious has been playing with the metadata.
384       SetCorrupt();
385     }
386 
387     // This is still safe to do even if corruption has been detected.
388     shared_meta()->cookie = kGlobalCookie;
389     shared_meta()->size = mem_size_;
390     shared_meta()->page_size = mem_page_;
391     shared_meta()->version = kGlobalVersion;
392     shared_meta()->id = id;
393     shared_meta()->freeptr.store(sizeof(SharedMetadata),
394                                  std::memory_order_release);
395 
396     // Set up the queue of iterable allocations.
397     shared_meta()->queue.size = sizeof(BlockHeader);
398     shared_meta()->queue.cookie = kBlockCookieQueue;
399     shared_meta()->queue.next.store(kReferenceQueue, std::memory_order_release);
400     shared_meta()->tailptr.store(kReferenceQueue, std::memory_order_release);
401 
402     // Allocate space for the name so other processes can learn it.
403     if (!name.empty()) {
404       const size_t name_length = name.length() + 1;
405       shared_meta()->name = Allocate(name_length, 0);
406       char* name_cstr = GetAsArray<char>(shared_meta()->name, 0, name_length);
407       if (name_cstr)
408         memcpy(name_cstr, name.data(), name.length());
409     }
410 
411     shared_meta()->memory_state.store(MEMORY_INITIALIZED,
412                                       std::memory_order_release);
413   } else {
414     if (shared_meta()->size == 0 || shared_meta()->version != kGlobalVersion ||
415         shared_meta()->freeptr.load(std::memory_order_relaxed) == 0 ||
416         shared_meta()->tailptr == 0 || shared_meta()->queue.cookie == 0 ||
417         shared_meta()->queue.next.load(std::memory_order_relaxed) == 0) {
418       SetCorrupt();
419     }
420     if (!readonly) {
421       // The allocator is attaching to a previously initialized segment of
422       // memory. If the initialization parameters differ, make the best of it
423       // by reducing the local construction parameters to match those of
424       // the actual memory area. This ensures that the local object never
425       // tries to write outside of the original bounds.
426       // Because the fields are const to ensure that no code other than the
427       // constructor makes changes to them as well as to give optimization
428       // hints to the compiler, it's necessary to const-cast them for changes
429       // here.
430       if (shared_meta()->size < mem_size_)
431         *const_cast<uint32_t*>(&mem_size_) = shared_meta()->size;
432       if (shared_meta()->page_size < mem_page_)
433         *const_cast<uint32_t*>(&mem_page_) = shared_meta()->page_size;
434 
435       // Ensure that settings are still valid after the above adjustments.
436       if (!IsMemoryAcceptable(memory.base, mem_size_, mem_page_, readonly))
437         SetCorrupt();
438     }
439   }
440 }
441 
~PersistentMemoryAllocator()442 PersistentMemoryAllocator::~PersistentMemoryAllocator() {
443   // It's strictly forbidden to do any memory access here in case there is
444   // some issue with the underlying memory segment. The "Local" allocator
445   // makes use of this to allow deletion of the segment on the heap from
446   // within its destructor.
447 }
448 
Id() const449 uint64_t PersistentMemoryAllocator::Id() const {
450   return shared_meta()->id;
451 }
452 
Name() const453 const char* PersistentMemoryAllocator::Name() const {
454   Reference name_ref = shared_meta()->name;
455   const char* name_cstr =
456       GetAsArray<char>(name_ref, 0, PersistentMemoryAllocator::kSizeAny);
457   if (!name_cstr)
458     return "";
459 
460   size_t name_length = GetAllocSize(name_ref);
461   if (name_cstr[name_length - 1] != '\0') {
462     NOTREACHED();
463     SetCorrupt();
464     return "";
465   }
466 
467   return name_cstr;
468 }
469 
CreateTrackingHistograms(base::StringPiece name)470 void PersistentMemoryAllocator::CreateTrackingHistograms(
471     base::StringPiece name) {
472   if (name.empty() || readonly_)
473     return;
474   std::string name_string = name.as_string();
475 
476 #if 0
477   // This histogram wasn't being used so has been disabled. It is left here
478   // in case development of a new use of the allocator could benefit from
479   // recording (temporarily and locally) the allocation sizes.
480   DCHECK(!allocs_histogram_);
481   allocs_histogram_ = Histogram::FactoryGet(
482       "UMA.PersistentAllocator." + name_string + ".Allocs", 1, 10000, 50,
483       HistogramBase::kUmaTargetedHistogramFlag);
484 #endif
485 
486   DCHECK(!used_histogram_);
487   used_histogram_ = LinearHistogram::FactoryGet(
488       "UMA.PersistentAllocator." + name_string + ".UsedPct", 1, 101, 21,
489       HistogramBase::kUmaTargetedHistogramFlag);
490 
491   DCHECK(!errors_histogram_);
492   errors_histogram_ = SparseHistogram::FactoryGet(
493       "UMA.PersistentAllocator." + name_string + ".Errors",
494       HistogramBase::kUmaTargetedHistogramFlag);
495 }
496 
Flush(bool sync)497 void PersistentMemoryAllocator::Flush(bool sync) {
498   FlushPartial(used(), sync);
499 }
500 
SetMemoryState(uint8_t memory_state)501 void PersistentMemoryAllocator::SetMemoryState(uint8_t memory_state) {
502   shared_meta()->memory_state.store(memory_state, std::memory_order_relaxed);
503   FlushPartial(sizeof(SharedMetadata), false);
504 }
505 
GetMemoryState() const506 uint8_t PersistentMemoryAllocator::GetMemoryState() const {
507   return shared_meta()->memory_state.load(std::memory_order_relaxed);
508 }
509 
used() const510 size_t PersistentMemoryAllocator::used() const {
511   return std::min(shared_meta()->freeptr.load(std::memory_order_relaxed),
512                   mem_size_);
513 }
514 
GetAsReference(const void * memory,uint32_t type_id) const515 PersistentMemoryAllocator::Reference PersistentMemoryAllocator::GetAsReference(
516     const void* memory,
517     uint32_t type_id) const {
518   uintptr_t address = reinterpret_cast<uintptr_t>(memory);
519   if (address < reinterpret_cast<uintptr_t>(mem_base_))
520     return kReferenceNull;
521 
522   uintptr_t offset = address - reinterpret_cast<uintptr_t>(mem_base_);
523   if (offset >= mem_size_ || offset < sizeof(BlockHeader))
524     return kReferenceNull;
525 
526   Reference ref = static_cast<Reference>(offset) - sizeof(BlockHeader);
527   if (!GetBlockData(ref, type_id, kSizeAny))
528     return kReferenceNull;
529 
530   return ref;
531 }
532 
GetAllocSize(Reference ref) const533 size_t PersistentMemoryAllocator::GetAllocSize(Reference ref) const {
534   const volatile BlockHeader* const block = GetBlock(ref, 0, 0, false, false);
535   if (!block)
536     return 0;
537   uint32_t size = block->size;
538   // Header was verified by GetBlock() but a malicious actor could change
539   // the value between there and here. Check it again.
540   if (size <= sizeof(BlockHeader) || ref + size > mem_size_) {
541     SetCorrupt();
542     return 0;
543   }
544   return size - sizeof(BlockHeader);
545 }
546 
GetType(Reference ref) const547 uint32_t PersistentMemoryAllocator::GetType(Reference ref) const {
548   const volatile BlockHeader* const block = GetBlock(ref, 0, 0, false, false);
549   if (!block)
550     return 0;
551   return block->type_id.load(std::memory_order_relaxed);
552 }
553 
ChangeType(Reference ref,uint32_t to_type_id,uint32_t from_type_id,bool clear)554 bool PersistentMemoryAllocator::ChangeType(Reference ref,
555                                            uint32_t to_type_id,
556                                            uint32_t from_type_id,
557                                            bool clear) {
558   DCHECK(!readonly_);
559   volatile BlockHeader* const block = GetBlock(ref, 0, 0, false, false);
560   if (!block)
561     return false;
562 
563   // "Strong" exchanges are used below because there is no loop that can retry
564   // in the wake of spurious failures possible with "weak" exchanges. It is,
565   // in aggregate, an "acquire-release" operation so no memory accesses can be
566   // reordered either before or after this method (since changes based on type
567   // could happen on either side).
568 
569   if (clear) {
570     // If clearing the memory, first change it to the "transitioning" type so
571     // there can be no confusion by other threads. After the memory is cleared,
572     // it can be changed to its final type.
573     if (!block->type_id.compare_exchange_strong(
574             from_type_id, kTypeIdTransitioning, std::memory_order_acquire,
575             std::memory_order_acquire)) {
576       // Existing type wasn't what was expected: fail (with no changes)
577       return false;
578     }
579 
580     // Clear the memory in an atomic manner. Using "release" stores force
581     // every write to be done after the ones before it. This is better than
582     // using memset because (a) it supports "volatile" and (b) it creates a
583     // reliable pattern upon which other threads may rely.
584     volatile std::atomic<int>* data =
585         reinterpret_cast<volatile std::atomic<int>*>(
586             reinterpret_cast<volatile char*>(block) + sizeof(BlockHeader));
587     const uint32_t words = (block->size - sizeof(BlockHeader)) / sizeof(int);
588     DCHECK_EQ(0U, (block->size - sizeof(BlockHeader)) % sizeof(int));
589     for (uint32_t i = 0; i < words; ++i) {
590       data->store(0, std::memory_order_release);
591       ++data;
592     }
593 
594     // If the destination type is "transitioning" then skip the final exchange.
595     if (to_type_id == kTypeIdTransitioning)
596       return true;
597 
598     // Finish the change to the desired type.
599     from_type_id = kTypeIdTransitioning;  // Exchange needs modifiable original.
600     bool success = block->type_id.compare_exchange_strong(
601         from_type_id, to_type_id, std::memory_order_release,
602         std::memory_order_relaxed);
603     DCHECK(success);  // Should never fail.
604     return success;
605   }
606 
607   // One step change to the new type. Will return false if the existing value
608   // doesn't match what is expected.
609   return block->type_id.compare_exchange_strong(from_type_id, to_type_id,
610                                                 std::memory_order_acq_rel,
611                                                 std::memory_order_acquire);
612 }
613 
Allocate(size_t req_size,uint32_t type_id)614 PersistentMemoryAllocator::Reference PersistentMemoryAllocator::Allocate(
615     size_t req_size,
616     uint32_t type_id) {
617   Reference ref = AllocateImpl(req_size, type_id);
618   if (ref) {
619     // Success: Record this allocation in usage stats (if active).
620     if (allocs_histogram_)
621       allocs_histogram_->Add(static_cast<HistogramBase::Sample>(req_size));
622   } else {
623     // Failure: Record an allocation of zero for tracking.
624     if (allocs_histogram_)
625       allocs_histogram_->Add(0);
626   }
627   return ref;
628 }
629 
AllocateImpl(size_t req_size,uint32_t type_id)630 PersistentMemoryAllocator::Reference PersistentMemoryAllocator::AllocateImpl(
631     size_t req_size,
632     uint32_t type_id) {
633   DCHECK(!readonly_);
634 
635   // Validate req_size to ensure it won't overflow when used as 32-bit value.
636   if (req_size > kSegmentMaxSize - sizeof(BlockHeader)) {
637     NOTREACHED();
638     return kReferenceNull;
639   }
640 
641   // Round up the requested size, plus header, to the next allocation alignment.
642   uint32_t size = static_cast<uint32_t>(req_size + sizeof(BlockHeader));
643   size = (size + (kAllocAlignment - 1)) & ~(kAllocAlignment - 1);
644   if (size <= sizeof(BlockHeader) || size > mem_page_) {
645     NOTREACHED();
646     return kReferenceNull;
647   }
648 
649   // Get the current start of unallocated memory. Other threads may
650   // update this at any time and cause us to retry these operations.
651   // This value should be treated as "const" to avoid confusion through
652   // the code below but recognize that any failed compare-exchange operation
653   // involving it will cause it to be loaded with a more recent value. The
654   // code should either exit or restart the loop in that case.
655   /* const */ uint32_t freeptr =
656       shared_meta()->freeptr.load(std::memory_order_acquire);
657 
658   // Allocation is lockless so we do all our caculation and then, if saving
659   // indicates a change has occurred since we started, scrap everything and
660   // start over.
661   for (;;) {
662     if (IsCorrupt())
663       return kReferenceNull;
664 
665     if (freeptr + size > mem_size_) {
666       SetFlag(&shared_meta()->flags, kFlagFull);
667       return kReferenceNull;
668     }
669 
670     // Get pointer to the "free" block. If something has been allocated since
671     // the load of freeptr above, it is still safe as nothing will be written
672     // to that location until after the compare-exchange below.
673     volatile BlockHeader* const block = GetBlock(freeptr, 0, 0, false, true);
674     if (!block) {
675       SetCorrupt();
676       return kReferenceNull;
677     }
678 
679     // An allocation cannot cross page boundaries. If it would, create a
680     // "wasted" block and begin again at the top of the next page. This
681     // area could just be left empty but we fill in the block header just
682     // for completeness sake.
683     const uint32_t page_free = mem_page_ - freeptr % mem_page_;
684     if (size > page_free) {
685       if (page_free <= sizeof(BlockHeader)) {
686         SetCorrupt();
687         return kReferenceNull;
688       }
689       const uint32_t new_freeptr = freeptr + page_free;
690       if (shared_meta()->freeptr.compare_exchange_strong(
691               freeptr, new_freeptr, std::memory_order_acq_rel,
692               std::memory_order_acquire)) {
693         block->size = page_free;
694         block->cookie = kBlockCookieWasted;
695       }
696       continue;
697     }
698 
699     // Don't leave a slice at the end of a page too small for anything. This
700     // can result in an allocation up to two alignment-sizes greater than the
701     // minimum required by requested-size + header + alignment.
702     if (page_free - size < sizeof(BlockHeader) + kAllocAlignment)
703       size = page_free;
704 
705     const uint32_t new_freeptr = freeptr + size;
706     if (new_freeptr > mem_size_) {
707       SetCorrupt();
708       return kReferenceNull;
709     }
710 
711     // Save our work. Try again if another thread has completed an allocation
712     // while we were processing. A "weak" exchange would be permissable here
713     // because the code will just loop and try again but the above processing
714     // is significant so make the extra effort of a "strong" exchange.
715     if (!shared_meta()->freeptr.compare_exchange_strong(
716             freeptr, new_freeptr, std::memory_order_acq_rel,
717             std::memory_order_acquire)) {
718       continue;
719     }
720 
721     // Given that all memory was zeroed before ever being given to an instance
722     // of this class and given that we only allocate in a monotomic fashion
723     // going forward, it must be that the newly allocated block is completely
724     // full of zeros. If we find anything in the block header that is NOT a
725     // zero then something must have previously run amuck through memory,
726     // writing beyond the allocated space and into unallocated space.
727     if (block->size != 0 ||
728         block->cookie != kBlockCookieFree ||
729         block->type_id.load(std::memory_order_relaxed) != 0 ||
730         block->next.load(std::memory_order_relaxed) != 0) {
731       SetCorrupt();
732       return kReferenceNull;
733     }
734 
735     // Make sure the memory exists by writing to the first byte of every memory
736     // page it touches beyond the one containing the block header itself.
737     // As the underlying storage is often memory mapped from disk or shared
738     // space, sometimes things go wrong and those address don't actually exist
739     // leading to a SIGBUS (or Windows equivalent) at some arbitrary location
740     // in the code. This should concentrate all those failures into this
741     // location for easy tracking and, eventually, proper handling.
742     volatile char* mem_end = reinterpret_cast<volatile char*>(block) + size;
743     volatile char* mem_begin = reinterpret_cast<volatile char*>(
744         (reinterpret_cast<uintptr_t>(block) + sizeof(BlockHeader) +
745          (vm_page_size_ - 1)) &
746         ~static_cast<uintptr_t>(vm_page_size_ - 1));
747     for (volatile char* memory = mem_begin; memory < mem_end;
748          memory += vm_page_size_) {
749       // It's required that a memory segment start as all zeros and thus the
750       // newly allocated block is all zeros at this point. Thus, writing a
751       // zero to it allows testing that the memory exists without actually
752       // changing its contents. The compiler doesn't know about the requirement
753       // and so cannot optimize-away these writes.
754       *memory = 0;
755     }
756 
757     // Load information into the block header. There is no "release" of the
758     // data here because this memory can, currently, be seen only by the thread
759     // performing the allocation. When it comes time to share this, the thread
760     // will call MakeIterable() which does the release operation.
761     block->size = size;
762     block->cookie = kBlockCookieAllocated;
763     block->type_id.store(type_id, std::memory_order_relaxed);
764     return freeptr;
765   }
766 }
767 
GetMemoryInfo(MemoryInfo * meminfo) const768 void PersistentMemoryAllocator::GetMemoryInfo(MemoryInfo* meminfo) const {
769   uint32_t remaining = std::max(
770       mem_size_ - shared_meta()->freeptr.load(std::memory_order_relaxed),
771       (uint32_t)sizeof(BlockHeader));
772   meminfo->total = mem_size_;
773   meminfo->free = remaining - sizeof(BlockHeader);
774 }
775 
MakeIterable(Reference ref)776 void PersistentMemoryAllocator::MakeIterable(Reference ref) {
777   DCHECK(!readonly_);
778   if (IsCorrupt())
779     return;
780   volatile BlockHeader* block = GetBlock(ref, 0, 0, false, false);
781   if (!block)  // invalid reference
782     return;
783   if (block->next.load(std::memory_order_acquire) != 0)  // Already iterable.
784     return;
785   block->next.store(kReferenceQueue, std::memory_order_release);  // New tail.
786 
787   // Try to add this block to the tail of the queue. May take multiple tries.
788   // If so, tail will be automatically updated with a more recent value during
789   // compare-exchange operations.
790   uint32_t tail = shared_meta()->tailptr.load(std::memory_order_acquire);
791   for (;;) {
792     // Acquire the current tail-pointer released by previous call to this
793     // method and validate it.
794     block = GetBlock(tail, 0, 0, true, false);
795     if (!block) {
796       SetCorrupt();
797       return;
798     }
799 
800     // Try to insert the block at the tail of the queue. The tail node always
801     // has an existing value of kReferenceQueue; if that is somehow not the
802     // existing value then another thread has acted in the meantime. A "strong"
803     // exchange is necessary so the "else" block does not get executed when
804     // that is not actually the case (which can happen with a "weak" exchange).
805     uint32_t next = kReferenceQueue;  // Will get replaced with existing value.
806     if (block->next.compare_exchange_strong(next, ref,
807                                             std::memory_order_acq_rel,
808                                             std::memory_order_acquire)) {
809       // Update the tail pointer to the new offset. If the "else" clause did
810       // not exist, then this could be a simple Release_Store to set the new
811       // value but because it does, it's possible that other threads could add
812       // one or more nodes at the tail before reaching this point. We don't
813       // have to check the return value because it either operates correctly
814       // or the exact same operation has already been done (by the "else"
815       // clause) on some other thread.
816       shared_meta()->tailptr.compare_exchange_strong(tail, ref,
817                                                      std::memory_order_release,
818                                                      std::memory_order_relaxed);
819       return;
820     } else {
821       // In the unlikely case that a thread crashed or was killed between the
822       // update of "next" and the update of "tailptr", it is necessary to
823       // perform the operation that would have been done. There's no explicit
824       // check for crash/kill which means that this operation may also happen
825       // even when the other thread is in perfect working order which is what
826       // necessitates the CompareAndSwap above.
827       shared_meta()->tailptr.compare_exchange_strong(tail, next,
828                                                      std::memory_order_acq_rel,
829                                                      std::memory_order_acquire);
830     }
831   }
832 }
833 
834 // The "corrupted" state is held both locally and globally (shared). The
835 // shared flag can't be trusted since a malicious actor could overwrite it.
836 // Because corruption can be detected during read-only operations such as
837 // iteration, this method may be called by other "const" methods. In this
838 // case, it's safe to discard the constness and modify the local flag and
839 // maybe even the shared flag if the underlying data isn't actually read-only.
SetCorrupt() const840 void PersistentMemoryAllocator::SetCorrupt() const {
841   if (!corrupt_.load(std::memory_order_relaxed) &&
842       !CheckFlag(
843           const_cast<volatile std::atomic<uint32_t>*>(&shared_meta()->flags),
844           kFlagCorrupt)) {
845     LOG(ERROR) << "Corruption detected in shared-memory segment.";
846     RecordError(kMemoryIsCorrupt);
847   }
848 
849   corrupt_.store(true, std::memory_order_relaxed);
850   if (!readonly_) {
851     SetFlag(const_cast<volatile std::atomic<uint32_t>*>(&shared_meta()->flags),
852             kFlagCorrupt);
853   }
854 }
855 
IsCorrupt() const856 bool PersistentMemoryAllocator::IsCorrupt() const {
857   if (corrupt_.load(std::memory_order_relaxed) ||
858       CheckFlag(&shared_meta()->flags, kFlagCorrupt)) {
859     SetCorrupt();  // Make sure all indicators are set.
860     return true;
861   }
862   return false;
863 }
864 
IsFull() const865 bool PersistentMemoryAllocator::IsFull() const {
866   return CheckFlag(&shared_meta()->flags, kFlagFull);
867 }
868 
869 // Dereference a block |ref| and ensure that it's valid for the desired
870 // |type_id| and |size|. |special| indicates that we may try to access block
871 // headers not available to callers but still accessed by this module. By
872 // having internal dereferences go through this same function, the allocator
873 // is hardened against corruption.
874 const volatile PersistentMemoryAllocator::BlockHeader*
GetBlock(Reference ref,uint32_t type_id,uint32_t size,bool queue_ok,bool free_ok) const875 PersistentMemoryAllocator::GetBlock(Reference ref, uint32_t type_id,
876                                     uint32_t size, bool queue_ok,
877                                     bool free_ok) const {
878   // Handle special cases.
879   if (ref == kReferenceQueue && queue_ok)
880     return reinterpret_cast<const volatile BlockHeader*>(mem_base_ + ref);
881 
882   // Validation of parameters.
883   if (ref < sizeof(SharedMetadata))
884     return nullptr;
885   if (ref % kAllocAlignment != 0)
886     return nullptr;
887   size += sizeof(BlockHeader);
888   if (ref + size > mem_size_)
889     return nullptr;
890 
891   // Validation of referenced block-header.
892   if (!free_ok) {
893     const volatile BlockHeader* const block =
894         reinterpret_cast<volatile BlockHeader*>(mem_base_ + ref);
895     if (block->cookie != kBlockCookieAllocated)
896       return nullptr;
897     if (block->size < size)
898       return nullptr;
899     if (ref + block->size > mem_size_)
900       return nullptr;
901     if (type_id != 0 &&
902         block->type_id.load(std::memory_order_relaxed) != type_id) {
903       return nullptr;
904     }
905   }
906 
907   // Return pointer to block data.
908   return reinterpret_cast<const volatile BlockHeader*>(mem_base_ + ref);
909 }
910 
FlushPartial(size_t length,bool sync)911 void PersistentMemoryAllocator::FlushPartial(size_t length, bool sync) {
912   // Generally there is nothing to do as every write is done through volatile
913   // memory with atomic instructions to guarantee consistency. This (virtual)
914   // method exists so that derivced classes can do special things, such as
915   // tell the OS to write changes to disk now rather than when convenient.
916 }
917 
RecordError(int error) const918 void PersistentMemoryAllocator::RecordError(int error) const {
919   if (errors_histogram_)
920     errors_histogram_->Add(error);
921 }
922 
GetBlockData(Reference ref,uint32_t type_id,uint32_t size) const923 const volatile void* PersistentMemoryAllocator::GetBlockData(
924     Reference ref,
925     uint32_t type_id,
926     uint32_t size) const {
927   DCHECK(size > 0);
928   const volatile BlockHeader* block =
929       GetBlock(ref, type_id, size, false, false);
930   if (!block)
931     return nullptr;
932   return reinterpret_cast<const volatile char*>(block) + sizeof(BlockHeader);
933 }
934 
UpdateTrackingHistograms()935 void PersistentMemoryAllocator::UpdateTrackingHistograms() {
936   DCHECK(!readonly_);
937   if (used_histogram_) {
938     MemoryInfo meminfo;
939     GetMemoryInfo(&meminfo);
940     HistogramBase::Sample used_percent = static_cast<HistogramBase::Sample>(
941         ((meminfo.total - meminfo.free) * 100ULL / meminfo.total));
942     used_histogram_->Add(used_percent);
943   }
944 }
945 
946 
947 //----- LocalPersistentMemoryAllocator -----------------------------------------
948 
LocalPersistentMemoryAllocator(size_t size,uint64_t id,base::StringPiece name)949 LocalPersistentMemoryAllocator::LocalPersistentMemoryAllocator(
950     size_t size,
951     uint64_t id,
952     base::StringPiece name)
953     : PersistentMemoryAllocator(AllocateLocalMemory(size),
954                                 size, 0, id, name, false) {}
955 
~LocalPersistentMemoryAllocator()956 LocalPersistentMemoryAllocator::~LocalPersistentMemoryAllocator() {
957   DeallocateLocalMemory(const_cast<char*>(mem_base_), mem_size_, mem_type_);
958 }
959 
960 // static
961 PersistentMemoryAllocator::Memory
AllocateLocalMemory(size_t size)962 LocalPersistentMemoryAllocator::AllocateLocalMemory(size_t size) {
963   void* address;
964 
965 #if defined(OS_WIN)
966   address =
967       ::VirtualAlloc(nullptr, size, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
968   if (address)
969     return Memory(address, MEM_VIRTUAL);
970   UmaHistogramSparse("UMA.LocalPersistentMemoryAllocator.Failures.Win",
971                      ::GetLastError());
972 #elif defined(OS_POSIX) || defined(OS_FUCHSIA)
973   // MAP_ANON is deprecated on Linux but MAP_ANONYMOUS is not universal on Mac.
974   // MAP_SHARED is not available on Linux <2.4 but required on Mac.
975   address = ::mmap(nullptr, size, PROT_READ | PROT_WRITE,
976                    MAP_ANON | MAP_SHARED, -1, 0);
977   if (address != MAP_FAILED)
978     return Memory(address, MEM_VIRTUAL);
979   UmaHistogramSparse("UMA.LocalPersistentMemoryAllocator.Failures.Posix",
980                      errno);
981 #else
982 #error This architecture is not (yet) supported.
983 #endif
984 
985   // As a last resort, just allocate the memory from the heap. This will
986   // achieve the same basic result but the acquired memory has to be
987   // explicitly zeroed and thus realized immediately (i.e. all pages are
988   // added to the process now istead of only when first accessed).
989   address = malloc(size);
990   DPCHECK(address);
991   memset(address, 0, size);
992   return Memory(address, MEM_MALLOC);
993 }
994 
995 // static
DeallocateLocalMemory(void * memory,size_t size,MemoryType type)996 void LocalPersistentMemoryAllocator::DeallocateLocalMemory(void* memory,
997                                                            size_t size,
998                                                            MemoryType type) {
999   if (type == MEM_MALLOC) {
1000     free(memory);
1001     return;
1002   }
1003 
1004   DCHECK_EQ(MEM_VIRTUAL, type);
1005 #if defined(OS_WIN)
1006   BOOL success = ::VirtualFree(memory, 0, MEM_DECOMMIT);
1007   DCHECK(success);
1008 #elif defined(OS_POSIX) || defined(OS_FUCHSIA)
1009   int result = ::munmap(memory, size);
1010   DCHECK_EQ(0, result);
1011 #else
1012 #error This architecture is not (yet) supported.
1013 #endif
1014 }
1015 
1016 
1017 //----- SharedPersistentMemoryAllocator ----------------------------------------
1018 
SharedPersistentMemoryAllocator(std::unique_ptr<SharedMemory> memory,uint64_t id,base::StringPiece name,bool read_only)1019 SharedPersistentMemoryAllocator::SharedPersistentMemoryAllocator(
1020     std::unique_ptr<SharedMemory> memory,
1021     uint64_t id,
1022     base::StringPiece name,
1023     bool read_only)
1024     : PersistentMemoryAllocator(
1025           Memory(static_cast<uint8_t*>(memory->memory()), MEM_SHARED),
1026           memory->mapped_size(),
1027           0,
1028           id,
1029           name,
1030           read_only),
1031       shared_memory_(std::move(memory)) {}
1032 
1033 SharedPersistentMemoryAllocator::~SharedPersistentMemoryAllocator() = default;
1034 
1035 // static
IsSharedMemoryAcceptable(const SharedMemory & memory)1036 bool SharedPersistentMemoryAllocator::IsSharedMemoryAcceptable(
1037     const SharedMemory& memory) {
1038   return IsMemoryAcceptable(memory.memory(), memory.mapped_size(), 0, false);
1039 }
1040 
1041 
1042 #if !defined(OS_NACL)
1043 //----- FilePersistentMemoryAllocator ------------------------------------------
1044 
FilePersistentMemoryAllocator(std::unique_ptr<MemoryMappedFile> file,size_t max_size,uint64_t id,base::StringPiece name,bool read_only)1045 FilePersistentMemoryAllocator::FilePersistentMemoryAllocator(
1046     std::unique_ptr<MemoryMappedFile> file,
1047     size_t max_size,
1048     uint64_t id,
1049     base::StringPiece name,
1050     bool read_only)
1051     : PersistentMemoryAllocator(
1052           Memory(const_cast<uint8_t*>(file->data()), MEM_FILE),
1053           max_size != 0 ? max_size : file->length(),
1054           0,
1055           id,
1056           name,
1057           read_only),
1058       mapped_file_(std::move(file)) {}
1059 
1060 FilePersistentMemoryAllocator::~FilePersistentMemoryAllocator() = default;
1061 
1062 // static
IsFileAcceptable(const MemoryMappedFile & file,bool read_only)1063 bool FilePersistentMemoryAllocator::IsFileAcceptable(
1064     const MemoryMappedFile& file,
1065     bool read_only) {
1066   return IsMemoryAcceptable(file.data(), file.length(), 0, read_only);
1067 }
1068 
FlushPartial(size_t length,bool sync)1069 void FilePersistentMemoryAllocator::FlushPartial(size_t length, bool sync) {
1070   if (sync)
1071     AssertBlockingAllowed();
1072   if (IsReadonly())
1073     return;
1074 
1075 #if defined(OS_WIN)
1076   // Windows doesn't support asynchronous flush.
1077   AssertBlockingAllowed();
1078   BOOL success = ::FlushViewOfFile(data(), length);
1079   DPCHECK(success);
1080 #elif defined(OS_MACOSX)
1081   // On OSX, "invalidate" removes all cached pages, forcing a re-read from
1082   // disk. That's not applicable to "flush" so omit it.
1083   int result =
1084       ::msync(const_cast<void*>(data()), length, sync ? MS_SYNC : MS_ASYNC);
1085   DCHECK_NE(EINVAL, result);
1086 #elif defined(OS_POSIX) || defined(OS_FUCHSIA)
1087   // On POSIX, "invalidate" forces _other_ processes to recognize what has
1088   // been written to disk and so is applicable to "flush".
1089   int result = ::msync(const_cast<void*>(data()), length,
1090                        MS_INVALIDATE | (sync ? MS_SYNC : MS_ASYNC));
1091   DCHECK_NE(EINVAL, result);
1092 #else
1093 #error Unsupported OS.
1094 #endif
1095 }
1096 #endif  // !defined(OS_NACL)
1097 
1098 //----- DelayedPersistentAllocation --------------------------------------------
1099 
1100 // Forwarding constructors.
DelayedPersistentAllocation(PersistentMemoryAllocator * allocator,subtle::Atomic32 * ref,uint32_t type,size_t size,bool make_iterable)1101 DelayedPersistentAllocation::DelayedPersistentAllocation(
1102     PersistentMemoryAllocator* allocator,
1103     subtle::Atomic32* ref,
1104     uint32_t type,
1105     size_t size,
1106     bool make_iterable)
1107     : DelayedPersistentAllocation(
1108           allocator,
1109           reinterpret_cast<std::atomic<Reference>*>(ref),
1110           type,
1111           size,
1112           0,
1113           make_iterable) {}
1114 
DelayedPersistentAllocation(PersistentMemoryAllocator * allocator,subtle::Atomic32 * ref,uint32_t type,size_t size,size_t offset,bool make_iterable)1115 DelayedPersistentAllocation::DelayedPersistentAllocation(
1116     PersistentMemoryAllocator* allocator,
1117     subtle::Atomic32* ref,
1118     uint32_t type,
1119     size_t size,
1120     size_t offset,
1121     bool make_iterable)
1122     : DelayedPersistentAllocation(
1123           allocator,
1124           reinterpret_cast<std::atomic<Reference>*>(ref),
1125           type,
1126           size,
1127           offset,
1128           make_iterable) {}
1129 
DelayedPersistentAllocation(PersistentMemoryAllocator * allocator,std::atomic<Reference> * ref,uint32_t type,size_t size,bool make_iterable)1130 DelayedPersistentAllocation::DelayedPersistentAllocation(
1131     PersistentMemoryAllocator* allocator,
1132     std::atomic<Reference>* ref,
1133     uint32_t type,
1134     size_t size,
1135     bool make_iterable)
1136     : DelayedPersistentAllocation(allocator,
1137                                   ref,
1138                                   type,
1139                                   size,
1140                                   0,
1141                                   make_iterable) {}
1142 
1143 // Real constructor.
DelayedPersistentAllocation(PersistentMemoryAllocator * allocator,std::atomic<Reference> * ref,uint32_t type,size_t size,size_t offset,bool make_iterable)1144 DelayedPersistentAllocation::DelayedPersistentAllocation(
1145     PersistentMemoryAllocator* allocator,
1146     std::atomic<Reference>* ref,
1147     uint32_t type,
1148     size_t size,
1149     size_t offset,
1150     bool make_iterable)
1151     : allocator_(allocator),
1152       type_(type),
1153       size_(checked_cast<uint32_t>(size)),
1154       offset_(checked_cast<uint32_t>(offset)),
1155       make_iterable_(make_iterable),
1156       reference_(ref) {
1157   DCHECK(allocator_);
1158   DCHECK_NE(0U, type_);
1159   DCHECK_LT(0U, size_);
1160   DCHECK(reference_);
1161 }
1162 
1163 DelayedPersistentAllocation::~DelayedPersistentAllocation() = default;
1164 
Get() const1165 void* DelayedPersistentAllocation::Get() const {
1166   // Relaxed operations are acceptable here because it's not protecting the
1167   // contents of the allocation in any way.
1168   Reference ref = reference_->load(std::memory_order_acquire);
1169   if (!ref) {
1170     ref = allocator_->Allocate(size_, type_);
1171     if (!ref)
1172       return nullptr;
1173 
1174     // Store the new reference in its proper location using compare-and-swap.
1175     // Use a "strong" exchange to ensure no false-negatives since the operation
1176     // cannot be retried.
1177     Reference existing = 0;  // Must be mutable; receives actual value.
1178     if (reference_->compare_exchange_strong(existing, ref,
1179                                             std::memory_order_release,
1180                                             std::memory_order_relaxed)) {
1181       if (make_iterable_)
1182         allocator_->MakeIterable(ref);
1183     } else {
1184       // Failure indicates that something else has raced ahead, performed the
1185       // allocation, and stored its reference. Purge the allocation that was
1186       // just done and use the other one instead.
1187       DCHECK_EQ(type_, allocator_->GetType(existing));
1188       DCHECK_LE(size_, allocator_->GetAllocSize(existing));
1189       allocator_->ChangeType(ref, 0, type_, /*clear=*/false);
1190       ref = existing;
1191     }
1192   }
1193 
1194   char* mem = allocator_->GetAsArray<char>(ref, type_, size_);
1195   if (!mem) {
1196     // This should never happen but be tolerant if it does as corruption from
1197     // the outside is something to guard against.
1198     NOTREACHED();
1199     return nullptr;
1200   }
1201   return mem + offset_;
1202 }
1203 
1204 }  // namespace base
1205