1 // Copyright 2020 the V8 project 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 #ifndef V8_HEAP_CPPGC_FREE_LIST_H_ 6 #define V8_HEAP_CPPGC_FREE_LIST_H_ 7 8 #include <array> 9 10 #include "include/cppgc/heap-statistics.h" 11 #include "src/base/macros.h" 12 #include "src/base/sanitizer/asan.h" 13 #include "src/heap/cppgc/globals.h" 14 #include "src/heap/cppgc/heap-object-header.h" 15 16 namespace cppgc { 17 namespace internal { 18 19 class Filler : public HeapObjectHeader { 20 public: 21 inline static Filler& CreateAt(void* memory, size_t size); 22 23 protected: Filler(size_t size)24 explicit Filler(size_t size) : HeapObjectHeader(size, kFreeListGCInfoIndex) {} 25 }; 26 27 class V8_EXPORT_PRIVATE FreeList { 28 public: 29 struct Block { 30 void* address; 31 size_t size; 32 }; 33 34 FreeList(); 35 36 FreeList(const FreeList&) = delete; 37 FreeList& operator=(const FreeList&) = delete; 38 39 FreeList(FreeList&& freelist) V8_NOEXCEPT; 40 FreeList& operator=(FreeList&& freelist) V8_NOEXCEPT; 41 42 // Allocates entries which are at least of the provided size. 43 Block Allocate(size_t); 44 45 // Adds block to the freelist. The minimal block size is a words. Regular 46 // entries have two words and unusable filler entries have a single word. 47 void Add(Block); 48 // Same as `Add()` but also returns the bounds of memory that is not required 49 // for free list management. 50 std::pair<Address, Address> AddReturningUnusedBounds(Block); 51 52 // Append other freelist into this. 53 void Append(FreeList&&); 54 55 void Clear(); 56 57 size_t Size() const; 58 bool IsEmpty() const; 59 60 void CollectStatistics(HeapStatistics::FreeListStatistics&); 61 62 bool ContainsForTesting(Block) const; 63 64 private: 65 class Entry; 66 67 bool IsConsistent(size_t) const; 68 69 // All |Entry|s in the nth list have size >= 2^n. 70 std::array<Entry*, kPageSizeLog2> free_list_heads_; 71 std::array<Entry*, kPageSizeLog2> free_list_tails_; 72 size_t biggest_free_list_index_ = 0; 73 }; 74 75 // static CreateAt(void * memory,size_t size)76Filler& Filler::CreateAt(void* memory, size_t size) { 77 // The memory area only needs to unpoisoned when running with ASAN. Zapped 78 // values (DEBUG) or uninitialized values (MSAN) are overwritten below. 79 ASAN_UNPOISON_MEMORY_REGION(memory, sizeof(Filler)); 80 return *new (memory) Filler(size); 81 } 82 83 } // namespace internal 84 } // namespace cppgc 85 86 #endif // V8_HEAP_CPPGC_FREE_LIST_H_ 87