Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 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 | |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 20 | #include <stdint.h> |
| 21 | |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 22 | #include <atomic> |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 23 | #include <random> |
| 24 | |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 25 | #include "perfetto/base/utils.h" |
| 26 | |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 27 | namespace perfetto { |
Florian Mayer | 8c0d048 | 2018-10-22 14:23:40 +0100 | [diff] [blame] | 28 | namespace profiling { |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 29 | |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 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. |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 35 | // |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 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. |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 39 | // |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 40 | // NB: not thread-safe, requires external synchronization. |
| 41 | class Sampler { |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 42 | public: |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 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), |
Florian Mayer | bb54f5e | 2018-10-22 12:13:03 +0100 | [diff] [blame] | 47 | interval_to_next_sample_(NextSampleInterval()) {} |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 48 | |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 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 | } |
Florian Mayer | bb54f5e | 2018-10-22 12:13:03 +0100 | [diff] [blame] | 59 | |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 60 | private: |
Ryan Savitski | a502bde | 2019-02-26 21:34:03 +0000 | [diff] [blame] | 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_; |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 83 | std::default_random_engine random_engine_; |
Florian Mayer | bb54f5e | 2018-10-22 12:13:03 +0100 | [diff] [blame] | 84 | int64_t interval_to_next_sample_; |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 85 | }; |
| 86 | |
Florian Mayer | 8c0d048 | 2018-10-22 14:23:40 +0100 | [diff] [blame] | 87 | } // namespace profiling |
Florian Mayer | c6be21f | 2018-10-02 11:33:59 +0100 | [diff] [blame] | 88 | } // namespace perfetto |
| 89 | |
| 90 | #endif // SRC_PROFILING_MEMORY_SAMPLER_H_ |