183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko/* 283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * Copyright (C) 2014 The Android Open Source Project 383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * 483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * Licensed under the Apache License, Version 2.0 (the "License"); 583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * you may not use this file except in compliance with the License. 683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * You may obtain a copy of the License at 783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * 883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * http://www.apache.org/licenses/LICENSE-2.0 983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * 1083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * Unless required by applicable law or agreed to in writing, software 1183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * distributed under the License is distributed on an "AS IS" BASIS, 1283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * See the License for the specific language governing permissions and 1483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko * limitations under the License. 1583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko */ 1683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 17b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#ifndef ART_RUNTIME_BASE_SCOPED_ARENA_ALLOCATOR_H_ 18b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#define ART_RUNTIME_BASE_SCOPED_ARENA_ALLOCATOR_H_ 1983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 2057943810cfc789da890d73621741729da5feaaf8Andreas Gampe#include <android-base/logging.h> 2157943810cfc789da890d73621741729da5feaaf8Andreas Gampe 22b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#include "arena_allocator.h" 238f4b056427a9d2321e3aa4f21ca8ffb18b3e5ae6David Sehr#include "base/debug_stack.h" 248f4b056427a9d2321e3aa4f21ca8ffb18b3e5ae6David Sehr#include "base/globals.h" 2567bf42e89592c3a1c648f927f2ce3ccb189a1161David Sehr#include "base/macros.h" 2683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 2783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Markonamespace art { 2883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 2983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Markoclass ArenaStack; 3083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Markoclass ScopedArenaAllocator; 3183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 3283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Markotemplate <typename T> 3383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Markoclass ScopedArenaAllocatorAdapter; 3483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 357b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier// Tag associated with each allocation to help prevent double free. 367b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartierenum class ArenaFreeTag : uint8_t { 377b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier // Allocation is used and has not yet been destroyed. 387b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier kUsed, 397b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier // Allocation has been destroyed. 407b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier kFree, 417b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier}; 427b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier 4383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko// Holds a list of Arenas for use by ScopedArenaAllocator stack. 44fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// The memory is returned to the ArenaPool when the ArenaStack is destroyed. 452a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Markoclass ArenaStack : private DebugStackRefCounter, private ArenaAllocatorMemoryTool { 4683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko public: 4783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko explicit ArenaStack(ArenaPool* arena_pool); 4883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ~ArenaStack(); 4983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 502a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko using ArenaAllocatorMemoryTool::IsRunningOnMemoryTool; 512a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko using ArenaAllocatorMemoryTool::MakeDefined; 522a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko using ArenaAllocatorMemoryTool::MakeUndefined; 532a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko using ArenaAllocatorMemoryTool::MakeInaccessible; 542a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko 5553b6afc93d91f9a48660682082dafcd81a652d6cVladimir Marko void Reset(); 5653b6afc93d91f9a48660682082dafcd81a652d6cVladimir Marko 5783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko size_t PeakBytesAllocated() { 58174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko DebugStackRefCounter::CheckNoRefs(); 5983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko return PeakStats()->BytesAllocated(); 6083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 6183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 6283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko MemStats GetPeakStats() const; 6383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 647b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier // Return the arena tag associated with a pointer. 657b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier static ArenaFreeTag& ArenaTagForAllocation(void* ptr) { 667b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier DCHECK(kIsDebugBuild) << "Only debug builds have tags"; 677b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier return *(reinterpret_cast<ArenaFreeTag*>(ptr) - 1); 687b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier } 697b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier 70f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3bVladimir Marko // The alignment guaranteed for individual allocations. 71f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3bVladimir Marko static constexpr size_t kAlignment = 8u; 72f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3bVladimir Marko 7383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko private: 7483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko struct Peak; 7583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko struct Current; 7683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko template <typename Tag> struct TaggedStats : ArenaAllocatorStats { }; 7783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko struct StatsAndPool : TaggedStats<Peak>, TaggedStats<Current> { 7883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko explicit StatsAndPool(ArenaPool* arena_pool) : pool(arena_pool) { } 7983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ArenaPool* const pool; 8083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko }; 8183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 8283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ArenaAllocatorStats* PeakStats() { 8383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko return static_cast<TaggedStats<Peak>*>(&stats_and_pool_); 8483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 8583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 86174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko const ArenaAllocatorStats* PeakStats() const { 87174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko return static_cast<const TaggedStats<Peak>*>(&stats_and_pool_); 88174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko } 89174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko 9083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ArenaAllocatorStats* CurrentStats() { 9183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko return static_cast<TaggedStats<Current>*>(&stats_and_pool_); 9283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 9383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 9483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko // Private - access via ScopedArenaAllocator or ScopedArenaAllocatorAdapter. 9583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko void* Alloc(size_t bytes, ArenaAllocKind kind) ALWAYS_INLINE { 962a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko if (UNLIKELY(IsRunningOnMemoryTool())) { 972a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko return AllocWithMemoryTool(bytes, kind); 9883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 99f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3bVladimir Marko // Add kAlignment for the free or used tag. Required to preserve alignment. 100f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3bVladimir Marko size_t rounded_bytes = RoundUp(bytes + (kIsDebugBuild ? kAlignment : 0u), kAlignment); 10183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko uint8_t* ptr = top_ptr_; 10283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko if (UNLIKELY(static_cast<size_t>(top_end_ - ptr) < rounded_bytes)) { 10383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ptr = AllocateFromNextArena(rounded_bytes); 10483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 10583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko CurrentStats()->RecordAlloc(bytes, kind); 10683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko top_ptr_ = ptr + rounded_bytes; 1077b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier if (kIsDebugBuild) { 108f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3bVladimir Marko ptr += kAlignment; 1097b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier ArenaTagForAllocation(ptr) = ArenaFreeTag::kUsed; 1107b05e17db15879b486f3299a9a41ac17b87700f4Mathieu Chartier } 11183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko return ptr; 11283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 11383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 11483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko uint8_t* AllocateFromNextArena(size_t rounded_bytes); 11583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko void UpdatePeakStatsAndRestore(const ArenaAllocatorStats& restore_stats); 11683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko void UpdateBytesAllocated(); 1172a408a3bef330551818f9cec9a7c5aa7a3f1129eVladimir Marko void* AllocWithMemoryTool(size_t bytes, ArenaAllocKind kind); 11883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 11983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko StatsAndPool stats_and_pool_; 12083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko Arena* bottom_arena_; 12183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko Arena* top_arena_; 12283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko uint8_t* top_ptr_; 12383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko uint8_t* top_end_; 12483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 12583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko friend class ScopedArenaAllocator; 12683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko template <typename T> 12783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko friend class ScopedArenaAllocatorAdapter; 12883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 12983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko DISALLOW_COPY_AND_ASSIGN(ArenaStack); 13083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko}; 13183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 132fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// Fast single-threaded allocator. Allocated chunks are _not_ guaranteed to be zero-initialized. 133fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// 134fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// Unlike the ArenaAllocator, ScopedArenaAllocator is intended for relatively short-lived 135fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// objects and allows nesting multiple allocators. Only the top allocator can be used but 136fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// once it's destroyed, its memory can be reused by the next ScopedArenaAllocator on the 137fda043241caada72fbf1215ac8c6eb5ad1ad44e7Vladimir Marko// stack. This is facilitated by returning the memory to the ArenaStack. 13883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Markoclass ScopedArenaAllocator 13983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko : private DebugStackReference, private DebugStackRefCounter, private ArenaAllocatorStats { 14083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko public: 141174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko ScopedArenaAllocator(ScopedArenaAllocator&& other); 14283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko explicit ScopedArenaAllocator(ArenaStack* arena_stack); 14383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ~ScopedArenaAllocator(); 14483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 145e764d2e50c544c2cb98ee61a15d613161ac6bd17Vladimir Marko ArenaStack* GetArenaStack() const { 146e764d2e50c544c2cb98ee61a15d613161ac6bd17Vladimir Marko return arena_stack_; 147e764d2e50c544c2cb98ee61a15d613161ac6bd17Vladimir Marko } 148e764d2e50c544c2cb98ee61a15d613161ac6bd17Vladimir Marko 14983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko void Reset(); 15083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 151e4fcc5ba2284c201c022b52d27f7a1201d696324Vladimir Marko void* Alloc(size_t bytes, ArenaAllocKind kind = kArenaAllocMisc) ALWAYS_INLINE { 15283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko DebugStackReference::CheckTop(); 15383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko return arena_stack_->Alloc(bytes, kind); 15483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 15583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 156e4fcc5ba2284c201c022b52d27f7a1201d696324Vladimir Marko template <typename T> 157f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko T* Alloc(ArenaAllocKind kind = kArenaAllocMisc) { 158f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko return AllocArray<T>(1, kind); 159f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko } 160f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko 161f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko template <typename T> 162e4fcc5ba2284c201c022b52d27f7a1201d696324Vladimir Marko T* AllocArray(size_t length, ArenaAllocKind kind = kArenaAllocMisc) { 163e4fcc5ba2284c201c022b52d27f7a1201d696324Vladimir Marko return static_cast<T*>(Alloc(length * sizeof(T), kind)); 164e4fcc5ba2284c201c022b52d27f7a1201d696324Vladimir Marko } 165e4fcc5ba2284c201c022b52d27f7a1201d696324Vladimir Marko 1668081d2b8d7a743729557051d0294e040e61c747aVladimir Marko // Get adapter for use in STL containers. See scoped_arena_containers.h . 1678081d2b8d7a743729557051d0294e040e61c747aVladimir Marko ScopedArenaAllocatorAdapter<void> Adapter(ArenaAllocKind kind = kArenaAllocSTL); 16883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 16983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko // Allow a delete-expression to destroy but not deallocate allocators created by Create(). 1704b8f1ecd3aa5a29ec1463ff88fee9db365f257dcRoland Levillain static void operator delete(void* ptr ATTRIBUTE_UNUSED) {} 17183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 17283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko private: 173174b2e27ebf933b80f4e8b64b4b024ab4306aaacVladimir Marko ArenaStack* arena_stack_; 17483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko Arena* mark_arena_; 17583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko uint8_t* mark_ptr_; 17683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko uint8_t* mark_end_; 17783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 1783d2ec35be5aadecc9d2bbd80394929ba3b36a4bfVladimir Marko void DoReset(); 1793d2ec35be5aadecc9d2bbd80394929ba3b36a4bfVladimir Marko 18083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko template <typename T> 18183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko friend class ScopedArenaAllocatorAdapter; 18283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 18383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko DISALLOW_COPY_AND_ASSIGN(ScopedArenaAllocator); 18483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko}; 18583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 18683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko} // namespace art 18783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 188b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#endif // ART_RUNTIME_BASE_SCOPED_ARENA_ALLOCATOR_H_ 189