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