Heap.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352
  1. /*
  2. * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/Badge.h>
  7. #include <AK/Debug.h>
  8. #include <AK/HashTable.h>
  9. #include <AK/StackInfo.h>
  10. #include <AK/TemporaryChange.h>
  11. #include <LibCore/ElapsedTimer.h>
  12. #include <LibJS/Heap/CellAllocator.h>
  13. #include <LibJS/Heap/Handle.h>
  14. #include <LibJS/Heap/Heap.h>
  15. #include <LibJS/Heap/HeapBlock.h>
  16. #include <LibJS/Interpreter.h>
  17. #include <LibJS/Runtime/Object.h>
  18. #include <LibJS/Runtime/WeakContainer.h>
  19. #include <setjmp.h>
  20. #ifdef __serenity__
  21. # include <serenity.h>
  22. #endif
  23. namespace JS {
  24. #ifdef __serenity__
  25. static int gc_perf_string_id;
  26. #endif
  27. Heap::Heap(VM& vm)
  28. : m_vm(vm)
  29. {
  30. #ifdef __serenity__
  31. auto gc_signpost_string = "Garbage collection"sv;
  32. gc_perf_string_id = perf_register_string(gc_signpost_string.characters_without_null_termination(), gc_signpost_string.length());
  33. #endif
  34. if constexpr (HeapBlock::min_possible_cell_size <= 16) {
  35. m_allocators.append(make<CellAllocator>(16));
  36. }
  37. static_assert(HeapBlock::min_possible_cell_size <= 24, "Heap Cell tracking uses too much data!");
  38. m_allocators.append(make<CellAllocator>(32));
  39. m_allocators.append(make<CellAllocator>(64));
  40. m_allocators.append(make<CellAllocator>(128));
  41. m_allocators.append(make<CellAllocator>(256));
  42. m_allocators.append(make<CellAllocator>(512));
  43. m_allocators.append(make<CellAllocator>(1024));
  44. m_allocators.append(make<CellAllocator>(3072));
  45. }
  46. Heap::~Heap()
  47. {
  48. collect_garbage(CollectionType::CollectEverything);
  49. }
  50. ALWAYS_INLINE CellAllocator& Heap::allocator_for_size(size_t cell_size)
  51. {
  52. for (auto& allocator : m_allocators) {
  53. if (allocator->cell_size() >= cell_size)
  54. return *allocator;
  55. }
  56. dbgln("Cannot get CellAllocator for cell size {}, largest available is {}!", cell_size, m_allocators.last()->cell_size());
  57. VERIFY_NOT_REACHED();
  58. }
  59. Cell* Heap::allocate_cell(size_t size)
  60. {
  61. if (should_collect_on_every_allocation()) {
  62. collect_garbage();
  63. } else if (m_allocations_since_last_gc > m_max_allocations_between_gc) {
  64. m_allocations_since_last_gc = 0;
  65. collect_garbage();
  66. } else {
  67. ++m_allocations_since_last_gc;
  68. }
  69. auto& allocator = allocator_for_size(size);
  70. return allocator.allocate_cell(*this);
  71. }
  72. void Heap::collect_garbage(CollectionType collection_type, bool print_report)
  73. {
  74. VERIFY(!m_collecting_garbage);
  75. TemporaryChange change(m_collecting_garbage, true);
  76. #ifdef __serenity__
  77. static size_t global_gc_counter = 0;
  78. perf_event(PERF_EVENT_SIGNPOST, gc_perf_string_id, global_gc_counter++);
  79. #endif
  80. auto collection_measurement_timer = Core::ElapsedTimer::start_new();
  81. if (collection_type == CollectionType::CollectGarbage) {
  82. if (m_gc_deferrals) {
  83. m_should_gc_when_deferral_ends = true;
  84. return;
  85. }
  86. HashTable<Cell*> roots;
  87. gather_roots(roots);
  88. mark_live_cells(roots);
  89. }
  90. sweep_dead_cells(print_report, collection_measurement_timer);
  91. }
  92. void Heap::gather_roots(HashTable<Cell*>& roots)
  93. {
  94. vm().gather_roots(roots);
  95. gather_conservative_roots(roots);
  96. for (auto& handle : m_handles)
  97. roots.set(handle.cell());
  98. for (auto& list : m_marked_value_lists) {
  99. for (auto& value : list.values()) {
  100. if (value.is_cell())
  101. roots.set(&value.as_cell());
  102. }
  103. }
  104. if constexpr (HEAP_DEBUG) {
  105. dbgln("gather_roots:");
  106. for (auto* root : roots)
  107. dbgln(" + {}", root);
  108. }
  109. }
  110. __attribute__((no_sanitize("address"))) void Heap::gather_conservative_roots(HashTable<Cell*>& roots)
  111. {
  112. FlatPtr dummy;
  113. dbgln_if(HEAP_DEBUG, "gather_conservative_roots:");
  114. jmp_buf buf;
  115. setjmp(buf);
  116. HashTable<FlatPtr> possible_pointers;
  117. auto* raw_jmp_buf = reinterpret_cast<FlatPtr const*>(buf);
  118. for (size_t i = 0; i < ((size_t)sizeof(buf)) / sizeof(FlatPtr); i += sizeof(FlatPtr))
  119. possible_pointers.set(raw_jmp_buf[i]);
  120. auto stack_reference = bit_cast<FlatPtr>(&dummy);
  121. auto& stack_info = m_vm.stack_info();
  122. for (FlatPtr stack_address = stack_reference; stack_address < stack_info.top(); stack_address += sizeof(FlatPtr)) {
  123. auto data = *reinterpret_cast<FlatPtr*>(stack_address);
  124. possible_pointers.set(data);
  125. }
  126. HashTable<HeapBlock*> all_live_heap_blocks;
  127. for_each_block([&](auto& block) {
  128. all_live_heap_blocks.set(&block);
  129. return IterationDecision::Continue;
  130. });
  131. for (auto possible_pointer : possible_pointers) {
  132. if (!possible_pointer)
  133. continue;
  134. dbgln_if(HEAP_DEBUG, " ? {}", (const void*)possible_pointer);
  135. auto* possible_heap_block = HeapBlock::from_cell(reinterpret_cast<const Cell*>(possible_pointer));
  136. if (all_live_heap_blocks.contains(possible_heap_block)) {
  137. if (auto* cell = possible_heap_block->cell_from_possible_pointer(possible_pointer)) {
  138. if (cell->state() == Cell::State::Live) {
  139. dbgln_if(HEAP_DEBUG, " ?-> {}", (const void*)cell);
  140. roots.set(cell);
  141. } else {
  142. dbgln_if(HEAP_DEBUG, " #-> {}", (const void*)cell);
  143. }
  144. }
  145. }
  146. }
  147. }
  148. class MarkingVisitor final : public Cell::Visitor {
  149. public:
  150. MarkingVisitor() { }
  151. virtual void visit_impl(Cell& cell)
  152. {
  153. if (cell.is_marked())
  154. return;
  155. dbgln_if(HEAP_DEBUG, " ! {}", &cell);
  156. if (cell.state() == Cell::State::Zombie) {
  157. dbgln("BUG! Marking a zombie cell, {} @ {:p}", cell.class_name(), &cell);
  158. cell.vm().dump_backtrace();
  159. VERIFY_NOT_REACHED();
  160. }
  161. cell.set_marked(true);
  162. cell.visit_edges(*this);
  163. }
  164. };
  165. void Heap::mark_live_cells(const HashTable<Cell*>& roots)
  166. {
  167. dbgln_if(HEAP_DEBUG, "mark_live_cells:");
  168. MarkingVisitor visitor;
  169. for (auto* root : roots)
  170. visitor.visit(root);
  171. for (auto& inverse_root : m_uprooted_cells)
  172. inverse_root->set_marked(false);
  173. m_uprooted_cells.clear();
  174. }
  175. void Heap::sweep_dead_cells(bool print_report, const Core::ElapsedTimer& measurement_timer)
  176. {
  177. dbgln_if(HEAP_DEBUG, "sweep_dead_cells:");
  178. Vector<HeapBlock*, 32> empty_blocks;
  179. Vector<HeapBlock*, 32> full_blocks_that_became_usable;
  180. Vector<Cell*> swept_cells;
  181. size_t collected_cells = 0;
  182. size_t live_cells = 0;
  183. size_t collected_cell_bytes = 0;
  184. size_t live_cell_bytes = 0;
  185. auto should_store_swept_cells = !m_weak_containers.is_empty();
  186. for_each_block([&](auto& block) {
  187. bool block_has_live_cells = false;
  188. bool block_was_full = block.is_full();
  189. block.template for_each_cell_in_state<Cell::State::Live>([&](Cell* cell) {
  190. if (!cell->is_marked()) {
  191. dbgln_if(HEAP_DEBUG, " ~ {}", cell);
  192. if (should_store_swept_cells)
  193. swept_cells.append(cell);
  194. if (m_zombify_dead_cells) {
  195. cell->set_state(Cell::State::Zombie);
  196. cell->did_become_zombie();
  197. } else {
  198. block.deallocate(cell);
  199. }
  200. ++collected_cells;
  201. collected_cell_bytes += block.cell_size();
  202. } else {
  203. cell->set_marked(false);
  204. block_has_live_cells = true;
  205. ++live_cells;
  206. live_cell_bytes += block.cell_size();
  207. }
  208. });
  209. if (!block_has_live_cells)
  210. empty_blocks.append(&block);
  211. else if (block_was_full != block.is_full())
  212. full_blocks_that_became_usable.append(&block);
  213. return IterationDecision::Continue;
  214. });
  215. for (auto* block : empty_blocks) {
  216. dbgln_if(HEAP_DEBUG, " - HeapBlock empty @ {}: cell_size={}", block, block->cell_size());
  217. allocator_for_size(block->cell_size()).block_did_become_empty({}, *block);
  218. }
  219. for (auto* block : full_blocks_that_became_usable) {
  220. dbgln_if(HEAP_DEBUG, " - HeapBlock usable again @ {}: cell_size={}", block, block->cell_size());
  221. allocator_for_size(block->cell_size()).block_did_become_usable({}, *block);
  222. }
  223. for (auto& weak_container : m_weak_containers)
  224. weak_container.remove_swept_cells({}, swept_cells.span());
  225. if constexpr (HEAP_DEBUG) {
  226. for_each_block([&](auto& block) {
  227. dbgln(" > Live HeapBlock @ {}: cell_size={}", &block, block.cell_size());
  228. return IterationDecision::Continue;
  229. });
  230. }
  231. int time_spent = measurement_timer.elapsed();
  232. if (print_report) {
  233. size_t live_block_count = 0;
  234. for_each_block([&](auto&) {
  235. ++live_block_count;
  236. return IterationDecision::Continue;
  237. });
  238. dbgln("Garbage collection report");
  239. dbgln("=============================================");
  240. dbgln(" Time spent: {} ms", time_spent);
  241. dbgln(" Live cells: {} ({} bytes)", live_cells, live_cell_bytes);
  242. dbgln("Collected cells: {} ({} bytes)", collected_cells, collected_cell_bytes);
  243. dbgln(" Live blocks: {} ({} bytes)", live_block_count, live_block_count * HeapBlock::block_size);
  244. dbgln(" Freed blocks: {} ({} bytes)", empty_blocks.size(), empty_blocks.size() * HeapBlock::block_size);
  245. dbgln("=============================================");
  246. }
  247. }
  248. void Heap::did_create_handle(Badge<HandleImpl>, HandleImpl& impl)
  249. {
  250. VERIFY(!m_handles.contains(impl));
  251. m_handles.append(impl);
  252. }
  253. void Heap::did_destroy_handle(Badge<HandleImpl>, HandleImpl& impl)
  254. {
  255. VERIFY(m_handles.contains(impl));
  256. m_handles.remove(impl);
  257. }
  258. void Heap::did_create_marked_value_list(Badge<MarkedValueList>, MarkedValueList& list)
  259. {
  260. VERIFY(!m_marked_value_lists.contains(list));
  261. m_marked_value_lists.append(list);
  262. }
  263. void Heap::did_destroy_marked_value_list(Badge<MarkedValueList>, MarkedValueList& list)
  264. {
  265. VERIFY(m_marked_value_lists.contains(list));
  266. m_marked_value_lists.remove(list);
  267. }
  268. void Heap::did_create_weak_container(Badge<WeakContainer>, WeakContainer& set)
  269. {
  270. VERIFY(!m_weak_containers.contains(set));
  271. m_weak_containers.append(set);
  272. }
  273. void Heap::did_destroy_weak_container(Badge<WeakContainer>, WeakContainer& set)
  274. {
  275. VERIFY(m_weak_containers.contains(set));
  276. m_weak_containers.remove(set);
  277. }
  278. void Heap::defer_gc(Badge<DeferGC>)
  279. {
  280. ++m_gc_deferrals;
  281. }
  282. void Heap::undefer_gc(Badge<DeferGC>)
  283. {
  284. VERIFY(m_gc_deferrals > 0);
  285. --m_gc_deferrals;
  286. if (!m_gc_deferrals) {
  287. if (m_should_gc_when_deferral_ends)
  288. collect_garbage();
  289. m_should_gc_when_deferral_ends = false;
  290. }
  291. }
  292. void Heap::uproot_cell(Cell* cell)
  293. {
  294. m_uprooted_cells.append(cell);
  295. }
  296. }