1d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross/* 2d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * Copyright (C) 2016 The Android Open Source Project 3d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * 4d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * Licensed under the Apache License, Version 2.0 (the "License"); 5d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * you may not use this file except in compliance with the License. 6d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * You may obtain a copy of the License at 7d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * 8d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * http://www.apache.org/licenses/LICENSE-2.0 9d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * 10d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * Unless required by applicable law or agreed to in writing, software 11d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * distributed under the License is distributed on an "AS IS" BASIS, 12d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * See the License for the specific language governing permissions and 14d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross * limitations under the License. 15d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross */ 16d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 17d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross#ifndef LIBMEMUNREACHABLE_LEAK_FOLDING_H_ 18d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross#define LIBMEMUNREACHABLE_LEAK_FOLDING_H_ 19d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 20d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross#include "HeapWalker.h" 21d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 22d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Crossclass LeakFolding { 23d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross public: 24d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross LeakFolding(Allocator<void> allocator, HeapWalker& heap_walker) 25d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross : allocator_(allocator), heap_walker_(heap_walker), 26d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross leak_map_(allocator), leak_graph_(allocator), leak_scc_(allocator) {} 27d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 28d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross bool FoldLeaks(); 29d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 30d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross struct Leak { 31d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross const Range range; 32d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t referenced_count; 33d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t referenced_size; 34d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross }; 35d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 36c1228c7f2b21c3a21e462a48eb49e3ccfd2290d9Colin Cross bool Leaked(allocator::vector<Leak>& leaked, 37d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t* num_leaks_out, size_t* leak_bytes_out); 38d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 39d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross private: 40d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross DISALLOW_COPY_AND_ASSIGN(LeakFolding); 41d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross Allocator<void> allocator_; 42d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross HeapWalker& heap_walker_; 43d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 44d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross struct SCCInfo { 45d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross public: 46d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross Node<SCCInfo> node; 47d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 48d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t count; 49d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t size; 50d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 51d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t cuumulative_count; 52d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross size_t cuumulative_size; 53d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 54d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross bool dominator; 55d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross SCCInfo* accumulator; 56d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 57034c475931e8e4da54b499c0056121490f029865Chih-Hung Hsieh explicit SCCInfo(Allocator<SCCInfo> allocator) : node(this, allocator), 58d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross count(0), size(0), cuumulative_count(0), cuumulative_size(0), 59d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross dominator(false), accumulator(nullptr) {} 60d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross private: 61d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross SCCInfo(SCCInfo&&) = delete; 62d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross DISALLOW_COPY_AND_ASSIGN(SCCInfo); 63d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross }; 64d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 65d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross struct LeakInfo { 66d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross public: 67d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross Node<LeakInfo> node; 68d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 69d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross const Range range; 70d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 71d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross SCCInfo* scc; 72d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 73d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross LeakInfo(const Range& range, Allocator<LeakInfo> allocator) 74d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross : node(this, allocator), range(range), 75d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross scc(nullptr) {} 76d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 77d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross private: 78d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross DISALLOW_COPY_AND_ASSIGN(LeakInfo); 79d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross }; 80d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 81d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross void ComputeDAG(); 82d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross void AccumulateLeaks(SCCInfo* dominator); 83d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 84e4cbe0ec9a4c0389409024c54c9413082954d0eeColin Cross allocator::map<Range, LeakInfo, compare_range> leak_map_; 85d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross Graph<LeakInfo> leak_graph_; 86d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross allocator::vector<Allocator<SCCInfo>::unique_ptr> leak_scc_; 87d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross}; 88d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross 89d6b3a2a0a36bf37f9c9d6ffc5fd8eaa43c214c71Colin Cross#endif // LIBMEMUNREACHABLE_LEAK_FOLDING_H_ 90