1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
// -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
// Copyright (c) 2008, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
// * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
// ---
// All Rights Reserved.
//
// Author: Daniel Ford
#ifndef TCMALLOC_SAMPLER_H_
#define TCMALLOC_SAMPLER_H_
#include "config.h"
#include <stddef.h> // for size_t
#ifdef HAVE_STDINT_H
#include <stdint.h> // for uint64_t, uint32_t, int32_t
#endif
#include <string.h> // for memcpy
#include "base/basictypes.h" // for ASSERT
#include "internal_logging.h" // for ASSERT
namespace tcmalloc {
//-------------------------------------------------------------------
// Sampler to decide when to create a sample trace for an allocation
// Not thread safe: Each thread should have it's own sampler object.
// Caller must use external synchronization if used
// from multiple threads.
//
// With 512K average sample step (the default):
// the probability of sampling a 4K allocation is about 0.00778
// the probability of sampling a 1MB allocation is about 0.865
// the probability of sampling a 1GB allocation is about 1.00000
// In general, the probablity of sampling is an allocation of size X
// given a flag value of Y (default 1M) is:
// 1 - e^(-X/Y)
//
// With 128K average sample step:
// the probability of sampling a 1MB allocation is about 0.99966
// the probability of sampling a 1GB allocation is about 1.0
// (about 1 - 2**(-26))
// With 1M average sample step:
// the probability of sampling a 4K allocation is about 0.00390
// the probability of sampling a 1MB allocation is about 0.632
// the probability of sampling a 1GB allocation is about 1.0
//
// The sampler works by representing memory as a long stream from
// which allocations are taken. Some of the bytes in this stream are
// marked and if an allocation includes a marked byte then it is
// sampled. Bytes are marked according to a Poisson point process
// with each byte being marked independently with probability
// p = 1/tcmalloc_sample_parameter. This makes the probability
// of sampling an allocation of X bytes equal to the CDF of
// a geometric with mean tcmalloc_sample_parameter. (ie. the
// probability that at least one byte in the range is marked). This
// is accurately given by the CDF of the corresponding exponential
// distribution : 1 - e^(X/tcmalloc_sample_parameter_)
// Independence of the byte marking ensures independence of
// the sampling of each allocation.
//
// This scheme is implemented by noting that, starting from any
// fixed place, the number of bytes until the next marked byte
// is geometrically distributed. This number is recorded as
// bytes_until_sample_. Every allocation subtracts from this
// number until it is less than 0. When this happens the current
// allocation is sampled.
//
// When an allocation occurs, bytes_until_sample_ is reset to
// a new independtly sampled geometric number of bytes. The
// memoryless property of the point process means that this may
// be taken as the number of bytes after the end of the current
// allocation until the next marked byte. This ensures that
// very large allocations which would intersect many marked bytes
// only result in a single call to PickNextSamplingPoint.
//-------------------------------------------------------------------
class PERFTOOLS_DLL_DECL Sampler {
public:
// Initialize this sampler.
// Passing a seed of 0 gives a non-deterministic
// seed value given by casting the object ("this")
void Init(uint32_t seed);
void Cleanup();
// Record allocation of "k" bytes. Return true iff allocation
// should be sampled
bool SampleAllocation(size_t k);
// Generate a geometric with mean 512K (or FLAG_tcmalloc_sample_parameter)
size_t PickNextSamplingPoint();
// Initialize the statics for the Sampler class
static void InitStatics();
// Returns the current sample period
int GetSamplePeriod();
// The following are public for the purposes of testing
static uint64_t NextRandom(uint64_t rnd_); // Returns the next prng value
static double FastLog2(const double & d); // Computes Log2(x) quickly
static void PopulateFastLog2Table(); // Populate the lookup table
private:
size_t bytes_until_sample_; // Bytes until we sample next
uint64_t rnd_; // Cheap random number generator
// Statics for the fast log
// Note that this code may not depend on anything in //util
// hence the duplication of functionality here
static const int kFastlogNumBits = 10;
static const int kFastlogMask = (1 << kFastlogNumBits) - 1;
static double log_table_[1<<kFastlogNumBits]; // Constant
};
inline bool Sampler::SampleAllocation(size_t k) {
if (bytes_until_sample_ < k) {
bytes_until_sample_ = PickNextSamplingPoint();
return true;
} else {
bytes_until_sample_ -= k;
return false;
}
}
// Inline functions which are public for testing purposes
// Returns the next prng value.
// pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48
// This is the lrand64 generator.
inline uint64_t Sampler::NextRandom(uint64_t rnd) {
const uint64_t prng_mult = 0x5DEECE66DLL;
const uint64_t prng_add = 0xB;
const uint64_t prng_mod_power = 48;
const uint64_t prng_mod_mask =
~((~static_cast<uint64_t>(0)) << prng_mod_power);
return (prng_mult * rnd + prng_add) & prng_mod_mask;
}
// Adapted from //util/math/fastmath.[h|cc] by Noam Shazeer
// This mimics the VeryFastLog2 code in those files
inline double Sampler::FastLog2(const double & d) {
ASSERT(d>0);
COMPILE_ASSERT(sizeof(d) == sizeof(uint64_t), DoubleMustBe64Bits);
uint64_t x;
memcpy(&x, &d, sizeof(x)); // we depend on the compiler inlining this
const uint32_t x_high = x >> 32;
const uint32_t y = x_high >> (20 - kFastlogNumBits) & kFastlogMask;
const int32_t exponent = ((x_high >> 20) & 0x7FF) - 1023;
return exponent + log_table_[y];
}
} // namespace tcmalloc
#endif // TCMALLOC_SAMPLER_H_
|
