12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_persistent_allocator.h ------------------------*- C++ -*-===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// A fast memory allocator that does not support free() nor realloc(). 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// All allocations are forever. 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 13799172d60d32feb1acba1a6867f3a9c39a999e5cPirama Arumuga Nainar 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef SANITIZER_PERSISTENT_ALLOCATOR_H 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define SANITIZER_PERSISTENT_ALLOCATOR_H 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_internal_defs.h" 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_mutex.h" 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_atomic.h" 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common.h" 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __sanitizer { 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass PersistentAllocator { 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void *alloc(uptr size); 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void *tryAlloc(uptr size); 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StaticSpinMutex mtx; // Protects alloc of new blocks for region allocator. 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t region_pos; // Region allocator for Node's. 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t region_end; 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesinline void *PersistentAllocator::tryAlloc(uptr size) { 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Optimisic lock-free allocation, essentially try to bump the region ptr. 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (;;) { 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cmp = atomic_load(®ion_pos, memory_order_acquire); 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr end = atomic_load(®ion_end, memory_order_acquire); 40799172d60d32feb1acba1a6867f3a9c39a999e5cPirama Arumuga Nainar if (cmp == 0 || cmp + size > end) return nullptr; 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (atomic_compare_exchange_weak(®ion_pos, &cmp, cmp + size, 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines memory_order_acquire)) 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return (void *)cmp; 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesinline void *PersistentAllocator::alloc(uptr size) { 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // First, try to allocate optimisitically. 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void *s = tryAlloc(size); 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (s) return s; 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // If failed, lock, retry and alloc new superblock. 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SpinMutexLock l(&mtx); 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (;;) { 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s = tryAlloc(size); 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (s) return s; 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(®ion_pos, 0, memory_order_relaxed); 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr allocsz = 64 * 1024; 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (allocsz < size) allocsz = size; 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr mem = (uptr)MmapOrDie(allocsz, "stack depot"); 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(®ion_end, mem + allocsz, memory_order_release); 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(®ion_pos, mem, memory_order_release); 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesextern PersistentAllocator thePersistentAllocator; 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesinline void *PersistentAlloc(uptr sz) { 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return thePersistentAllocator.alloc(sz); 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __sanitizer 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 72799172d60d32feb1acba1a6867f3a9c39a999e5cPirama Arumuga Nainar#endif // SANITIZER_PERSISTENT_ALLOCATOR_H 73