1 /*
2  * Copyright (C) 2018 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 SRC_PROFILING_MEMORY_SAMPLER_H_
18 #define SRC_PROFILING_MEMORY_SAMPLER_H_
19 
20 #include <stdint.h>
21 
22 #include <atomic>
23 #include <random>
24 
25 #include "perfetto/ext/base/utils.h"
26 
27 namespace perfetto {
28 namespace profiling {
29 
30 constexpr uint64_t kSamplerSeed = 1;
31 
32 uint64_t GetPassthroughThreshold(uint64_t interval);
33 
34 std::default_random_engine& GetGlobalRandomEngineLocked();
35 
36 // Poisson sampler for memory allocations. We apply sampling individually to
37 // each byte. The whole allocation gets accounted as often as the number of
38 // sampled bytes it contains.
39 //
40 // The algorithm is inspired by the Chromium sampling algorithm at
41 // https://cs.chromium.org/search/?q=f:cc+symbol:AllocatorShimLogAlloc+package:%5Echromium$&type=cs
42 // Googlers: see go/chrome-shp for more details.
43 //
44 // NB: not thread-safe, requires external synchronization.
45 class Sampler {
46  public:
47   void SetSamplingInterval(uint64_t sampling_interval);
48 
49   // Returns number of bytes that should be be attributed to the sample.
50   // If returned size is 0, the allocation should not be sampled.
51   //
52   // Due to how the poission sampling works, some samples should be accounted
53   // multiple times.
SampleSize(size_t alloc_sz)54   size_t SampleSize(size_t alloc_sz) {
55     if (PERFETTO_UNLIKELY(alloc_sz >= passthrough_threshold_))
56       return alloc_sz;
57     return static_cast<size_t>(sampling_interval_ * NumberOfSamples(alloc_sz));
58   }
59 
sampling_interval()60   uint64_t sampling_interval() const { return sampling_interval_; }
61 
62  private:
NextSampleInterval()63   int64_t NextSampleInterval() {
64     std::exponential_distribution<double> dist(sampling_rate_);
65     int64_t next = static_cast<int64_t>(dist(GetGlobalRandomEngineLocked()));
66     // We approximate the geometric distribution using an exponential
67     // distribution.
68     // We need to add 1 because that gives us the number of failures before
69     // the next success, while our interval includes the next success.
70     return next + 1;
71   }
72 
73   // Returns number of times a sample should be accounted. Due to how the
74   // poission sampling works, some samples should be accounted multiple times.
NumberOfSamples(size_t alloc_sz)75   size_t NumberOfSamples(size_t alloc_sz) {
76     interval_to_next_sample_ -= alloc_sz;
77     size_t num_samples = 0;
78     while (PERFETTO_UNLIKELY(interval_to_next_sample_ <= 0)) {
79       interval_to_next_sample_ += NextSampleInterval();
80       ++num_samples;
81     }
82     return num_samples;
83   }
84 
85   uint64_t sampling_interval_;
86   uint64_t passthrough_threshold_;
87   double sampling_rate_;
88   int64_t interval_to_next_sample_;
89 };
90 
91 }  // namespace profiling
92 }  // namespace perfetto
93 
94 #endif  // SRC_PROFILING_MEMORY_SAMPLER_H_
95