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: 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. 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: 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. 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
