1/*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_RUNTIME_PROFILER_H_
18#define ART_RUNTIME_PROFILER_H_
19
20#include <memory>
21#include <ostream>
22#include <set>
23#include <string>
24#include <vector>
25
26#include "barrier.h"
27#include "base/macros.h"
28#include "base/mutex.h"
29#include "globals.h"
30#include "instrumentation.h"
31#include "profiler_options.h"
32#include "os.h"
33#include "safe_map.h"
34#include "method_reference.h"
35
36namespace art {
37
38namespace mirror {
39  class ArtMethod;
40  class Class;
41}  // namespace mirror
42class Thread;
43
44typedef std::pair<mirror::ArtMethod*, uint32_t> InstructionLocation;
45
46// This class stores the sampled bounded stacks in a trie structure. A path of the trie represents
47// a particular context with the method on top of the stack being a leaf or an internal node of the
48// trie rather than the root.
49class StackTrieNode {
50 public:
51  StackTrieNode(MethodReference method, uint32_t dex_pc, uint32_t method_size,
52      StackTrieNode* parent) :
53      parent_(parent), method_(method), dex_pc_(dex_pc),
54      count_(0), method_size_(method_size) {
55  }
56  StackTrieNode() : parent_(nullptr), method_(nullptr, 0),
57      dex_pc_(0), count_(0), method_size_(0) {
58  }
59  StackTrieNode* GetParent() { return parent_; }
60  MethodReference GetMethod() { return method_; }
61  uint32_t GetCount() { return count_; }
62  uint32_t GetDexPC() { return dex_pc_; }
63  uint32_t GetMethodSize() { return method_size_; }
64  void AppendChild(StackTrieNode* child) { children_.insert(child); }
65  StackTrieNode* FindChild(MethodReference method, uint32_t dex_pc);
66  void DeleteChildren();
67  void IncreaseCount() { ++count_; }
68
69 private:
70  // Comparator for stack trie node.
71  struct StackTrieNodeComparator {
72    bool operator()(StackTrieNode* node1, StackTrieNode* node2) const {
73      MethodReference mr1 = node1->GetMethod();
74      MethodReference mr2 = node2->GetMethod();
75      if (mr1.dex_file == mr2.dex_file) {
76        if (mr1.dex_method_index == mr2.dex_method_index) {
77          return node1->GetDexPC() < node2->GetDexPC();
78        } else {
79          return mr1.dex_method_index < mr2.dex_method_index;
80        }
81      } else {
82        return mr1.dex_file < mr2.dex_file;
83      }
84    }
85  };
86
87  std::set<StackTrieNode*, StackTrieNodeComparator> children_;
88  StackTrieNode* parent_;
89  MethodReference method_;
90  uint32_t dex_pc_;
91  uint32_t count_;
92  uint32_t method_size_;
93};
94
95//
96// This class holds all the results for all runs of the profiler.  It also
97// counts the number of null methods (where we can't determine the method) and
98// the number of methods in the boot path (where we have already compiled the method).
99//
100// This object is an internal profiler object and uses the same locking as the profiler
101// itself.
102class ProfileSampleResults {
103 public:
104  explicit ProfileSampleResults(Mutex& lock);
105  ~ProfileSampleResults();
106
107  void Put(mirror::ArtMethod* method);
108  void PutStack(const std::vector<InstructionLocation>& stack_dump);
109  uint32_t Write(std::ostream &os, ProfileDataType type);
110  void ReadPrevious(int fd, ProfileDataType type);
111  void Clear();
112  uint32_t GetNumSamples() { return num_samples_; }
113  void NullMethod() { ++num_null_methods_; }
114  void BootMethod() { ++num_boot_methods_; }
115
116 private:
117  uint32_t Hash(mirror::ArtMethod* method);
118  static constexpr int kHashSize = 17;
119  Mutex& lock_;                  // Reference to the main profiler lock - we don't need two of them.
120  uint32_t num_samples_;         // Total number of samples taken.
121  uint32_t num_null_methods_;    // Number of samples where can don't know the method.
122  uint32_t num_boot_methods_;    // Number of samples in the boot path.
123
124  typedef std::map<mirror::ArtMethod*, uint32_t> Map;  // Map of method vs its count.
125  Map *table[kHashSize];
126
127  typedef std::set<StackTrieNode*> TrieNodeSet;
128  // Map of method hit by profiler vs the set of stack trie nodes for this method.
129  typedef std::map<MethodReference, TrieNodeSet*, MethodReferenceComparator> MethodContextMap;
130  MethodContextMap *method_context_table;
131  StackTrieNode* stack_trie_root_;  // Root of the trie that stores sampled stack information.
132
133  // Map from <pc, context> to counts.
134  typedef std::map<std::pair<uint32_t, std::string>, uint32_t> PreviousContextMap;
135  struct PreviousValue {
136    PreviousValue() : count_(0), method_size_(0), context_map_(nullptr) {}
137    PreviousValue(uint32_t count, uint32_t method_size, PreviousContextMap* context_map)
138      : count_(count), method_size_(method_size), context_map_(context_map) {}
139    uint32_t count_;
140    uint32_t method_size_;
141    PreviousContextMap* context_map_;
142  };
143
144  typedef std::map<std::string, PreviousValue> PreviousProfile;
145  PreviousProfile previous_;
146  uint32_t previous_num_samples_;
147  uint32_t previous_num_null_methods_;     // Number of samples where can don't know the method.
148  uint32_t previous_num_boot_methods_;     // Number of samples in the boot path.
149};
150
151//
152// The BackgroundMethodSamplingProfiler runs in a thread.  Most of the time it is sleeping but
153// occasionally wakes up and counts the number of times a method is called.  Each time
154// it ticks, it looks at the current method and records it in the ProfileSampleResults
155// table.
156//
157// The timing is controlled by a number of variables:
158// 1.  Period: the time between sampling runs.
159// 2.  Interval: the time between each sample in a run.
160// 3.  Duration: the duration of a run.
161//
162// So the profiler thread is sleeping for the 'period' time.  It wakes up and runs for the
163// 'duration'.  The run consists of a series of samples, each of which is 'interval' microseconds
164// apart.  At the end of a run, it writes the results table to a file and goes back to sleep.
165
166class BackgroundMethodSamplingProfiler {
167 public:
168  // Start a profile thread with the user-supplied arguments.
169  // Returns true if the profile was started or if it was already running. Returns false otherwise.
170  static bool Start(const std::string& output_filename, const ProfilerOptions& options)
171  LOCKS_EXCLUDED(Locks::mutator_lock_,
172                 Locks::thread_list_lock_,
173                 Locks::thread_suspend_count_lock_,
174                 Locks::profiler_lock_);
175
176  static void Stop() LOCKS_EXCLUDED(Locks::profiler_lock_, wait_lock_);
177  static void Shutdown() LOCKS_EXCLUDED(Locks::profiler_lock_);
178
179  void RecordMethod(mirror::ArtMethod *method) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
180  void RecordStack(const std::vector<InstructionLocation>& stack) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
181  bool ProcessMethod(mirror::ArtMethod* method) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
182  const ProfilerOptions& GetProfilerOptions() const { return options_; }
183
184  Barrier& GetBarrier() {
185    return *profiler_barrier_;
186  }
187
188 private:
189  explicit BackgroundMethodSamplingProfiler(
190    const std::string& output_filename, const ProfilerOptions& options);
191
192  // The sampling interval in microseconds is passed as an argument.
193  static void* RunProfilerThread(void* arg) LOCKS_EXCLUDED(Locks::profiler_lock_);
194
195  uint32_t WriteProfile() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
196
197  void CleanProfile();
198  uint32_t DumpProfile(std::ostream& os) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
199  static bool ShuttingDown(Thread* self) LOCKS_EXCLUDED(Locks::profiler_lock_);
200
201  static BackgroundMethodSamplingProfiler* profiler_ GUARDED_BY(Locks::profiler_lock_);
202
203  // We need to shut the sample thread down at exit.  Setting this to true will do that.
204  static volatile bool shutting_down_ GUARDED_BY(Locks::profiler_lock_);
205
206  // Sampling thread, non-zero when sampling.
207  static pthread_t profiler_pthread_;
208
209  // Some measure of the number of samples that are significant.
210  static constexpr uint32_t kSignificantSamples = 10;
211
212  // The name of the file where profile data will be written.
213  std::string output_filename_;
214  // The options used to start the profiler.
215  const ProfilerOptions& options_;
216
217
218  // Profile condition support.
219  Mutex wait_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
220  ConditionVariable period_condition_ GUARDED_BY(wait_lock_);
221
222  ProfileSampleResults profile_table_;
223
224  std::unique_ptr<Barrier> profiler_barrier_;
225
226  // Set of methods to be filtered out.  This will probably be rare because
227  // most of the methods we want to be filtered reside in the boot path and
228  // are automatically filtered.
229  typedef std::set<std::string> FilteredMethods;
230  FilteredMethods filtered_methods_;
231
232  DISALLOW_COPY_AND_ASSIGN(BackgroundMethodSamplingProfiler);
233};
234
235//
236// Contains profile data generated from previous runs of the program and stored
237// in a file.  It is used to determine whether to compile a particular method or not.
238class ProfileFile {
239 public:
240  class ProfileData {
241   public:
242    ProfileData() : count_(0), method_size_(0), used_percent_(0) {}
243    ProfileData(const std::string& method_name, uint32_t count, uint32_t method_size,
244      double used_percent, double top_k_used_percentage) :
245      method_name_(method_name), count_(count), method_size_(method_size),
246      used_percent_(used_percent), top_k_used_percentage_(top_k_used_percentage) {
247      // TODO: currently method_size_ is unused
248      UNUSED(method_size_);
249    }
250
251    double GetUsedPercent() const { return used_percent_; }
252    uint32_t GetCount() const { return count_; }
253    double GetTopKUsedPercentage() const { return top_k_used_percentage_; }
254
255   private:
256    std::string method_name_;       // Method name.
257    uint32_t count_;                // Number of times it has been called.
258    uint32_t method_size_;          // Size of the method on dex instructions.
259    double used_percent_;           // Percentage of how many times this method was called.
260    double top_k_used_percentage_;  // The percentage of the group that comprise K% of the total
261                                    // used methods this methods belongs to.
262  };
263
264 public:
265  // Loads profile data from the given file. The new data are merged with any existing data.
266  // Returns true if the file was loaded successfully and false otherwise.
267  bool LoadFile(const std::string& filename);
268
269  // Computes the group that comprise top_k_percentage of the total used methods.
270  bool GetTopKSamples(std::set<std::string>& top_k_methods, double top_k_percentage);
271
272  // If the given method has an entry in the profile table it updates the data
273  // and returns true. Otherwise returns false and leaves the data unchanged.
274  bool GetProfileData(ProfileData* data, const std::string& method_name);
275
276 private:
277  // Profile data is stored in a map, indexed by the full method name.
278  typedef std::map<std::string, ProfileData> ProfileMap;
279  ProfileMap profile_map_;
280};
281
282}  // namespace art
283
284#endif  // ART_RUNTIME_PROFILER_H_
285