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