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