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/base/utils.h"
26 
27 namespace perfetto {
28 namespace profiling {
29 
30 constexpr uint64_t kSamplerSeed = 1;
31 
32 // Poisson sampler for memory allocations. We apply sampling individually to
33 // each byte. The whole allocation gets accounted as often as the number of
34 // sampled bytes it contains.
35 //
36 // The algorithm is inspired by the Chromium sampling algorithm at
37 // https://cs.chromium.org/search/?q=f:cc+symbol:AllocatorShimLogAlloc+package:%5Echromium$&type=cs
38 // Googlers: see go/chrome-shp for more details.
39 //
40 // NB: not thread-safe, requires external synchronization.
41 class Sampler {
42  public:
Sampler(uint64_t sampling_interval)43   Sampler(uint64_t sampling_interval)
44       : sampling_interval_(sampling_interval),
45         sampling_rate_(1.0 / static_cast<double>(sampling_interval)),
46         random_engine_(kSamplerSeed),
47         interval_to_next_sample_(NextSampleInterval()) {}
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 >= sampling_interval_))
56       return alloc_sz;
57     return sampling_interval_ * NumberOfSamples(alloc_sz);
58   }
59 
60  private:
NextSampleInterval()61   int64_t NextSampleInterval() {
62     std::exponential_distribution<double> dist(sampling_rate_);
63     int64_t next = static_cast<int64_t>(dist(random_engine_));
64     // The +1 corrects the distribution of the first value in the interval.
65     // TODO(fmayer): Figure out why.
66     return next + 1;
67   }
68 
69   // Returns number of times a sample should be accounted. Due to how the
70   // poission sampling works, some samples should be accounted multiple times.
NumberOfSamples(size_t alloc_sz)71   size_t NumberOfSamples(size_t alloc_sz) {
72     interval_to_next_sample_ -= alloc_sz;
73     size_t num_samples = 0;
74     while (PERFETTO_UNLIKELY(interval_to_next_sample_ <= 0)) {
75       interval_to_next_sample_ += NextSampleInterval();
76       ++num_samples;
77     }
78     return num_samples;
79   }
80 
81   uint64_t sampling_interval_;
82   double sampling_rate_;
83   std::default_random_engine random_engine_;
84   int64_t interval_to_next_sample_;
85 };
86 
87 }  // namespace profiling
88 }  // namespace perfetto
89 
90 #endif  // SRC_PROFILING_MEMORY_SAMPLER_H_
91