1 /*
2  * Copyright (C) 2017 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_BACKTRACE_HELPER_H_
18 #define ART_RUNTIME_BACKTRACE_HELPER_H_
19 
20 #include <unwind.h>
21 
22 namespace art {
23 
24 // Based on debug malloc logic from libc/bionic/debug_stacktrace.cpp.
25 class BacktraceCollector {
26  public:
BacktraceCollector(uintptr_t * out_frames,size_t max_depth,size_t skip_count)27   BacktraceCollector(uintptr_t* out_frames, size_t max_depth, size_t skip_count)
28       : out_frames_(out_frames), max_depth_(max_depth), skip_count_(skip_count) {}
29 
NumFrames()30   size_t NumFrames() const {
31     return num_frames_;
32   }
33 
34   // Collect the backtrace, do not call more than once.
Collect()35   void Collect() {
36     _Unwind_Backtrace(&Callback, this);
37   }
38 
39  private:
Callback(_Unwind_Context * context,void * arg)40   static _Unwind_Reason_Code Callback(_Unwind_Context* context, void* arg) {
41     auto* const state = reinterpret_cast<BacktraceCollector*>(arg);
42     const uintptr_t ip = _Unwind_GetIP(context);
43     // The first stack frame is get_backtrace itself. Skip it.
44     if (ip != 0 && state->skip_count_ > 0) {
45       --state->skip_count_;
46       return _URC_NO_REASON;
47     }
48     // ip may be off for ARM but it shouldn't matter since we only use it for hashing.
49     state->out_frames_[state->num_frames_] = ip;
50     state->num_frames_++;
51     return state->num_frames_ >= state->max_depth_ ? _URC_END_OF_STACK : _URC_NO_REASON;
52   }
53 
54   uintptr_t* const out_frames_ = nullptr;
55   size_t num_frames_ = 0u;
56   const size_t max_depth_ = 0u;
57   size_t skip_count_ = 0u;
58 };
59 
60 // A bounded sized backtrace.
61 template <size_t kMaxFrames>
62 class FixedSizeBacktrace {
63  public:
Collect(size_t skip_count)64   void Collect(size_t skip_count) {
65     BacktraceCollector collector(frames_, kMaxFrames, skip_count);
66     collector.Collect();
67     num_frames_ = collector.NumFrames();
68   }
69 
Hash()70   uint64_t Hash() const {
71     uint64_t hash = 9314237;
72     for (size_t i = 0; i < num_frames_; ++i) {
73       hash = hash * 2654435761 + frames_[i];
74       hash += (hash >> 13) ^ (hash << 6);
75     }
76     return hash;
77   }
78 
79  private:
80   uintptr_t frames_[kMaxFrames];
81   size_t num_frames_;
82 };
83 
84 }  // namespace art
85 
86 #endif  // ART_RUNTIME_BACKTRACE_HELPER_H_
87