1// Copyright (c) 2008, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// --- 31// All Rights Reserved. 32// 33// Author: Daniel Ford 34// 35// Checks basic properties of the sampler 36 37#include "config_for_unittests.h" 38#include <stdlib.h> // defines posix_memalign 39#include <stdio.h> // for the printf at the end 40#if defined HAVE_STDINT_H 41#include <stdint.h> // to get uintptr_t 42#elif defined HAVE_INTTYPES_H 43#include <inttypes.h> // another place uintptr_t might be defined 44#endif 45#include <sys/types.h> 46#include <iostream> 47#include <algorithm> 48#include <vector> 49#include <string> 50#include <cmath> 51#include "base/logging.h" 52#include "base/commandlineflags.h" 53#include "sampler.h" // The Sampler class being tested 54 55using std::sort; 56using std::min; 57using std::max; 58using std::vector; 59using std::abs; 60 61vector<void (*)()> g_testlist; // the tests to run 62 63#define TEST(a, b) \ 64 struct Test_##a##_##b { \ 65 Test_##a##_##b() { g_testlist.push_back(&Run); } \ 66 static void Run(); \ 67 }; \ 68 static Test_##a##_##b g_test_##a##_##b; \ 69 void Test_##a##_##b::Run() 70 71 72static int RUN_ALL_TESTS() { 73 vector<void (*)()>::const_iterator it; 74 for (it = g_testlist.begin(); it != g_testlist.end(); ++it) { 75 (*it)(); // The test will error-exit if there's a problem. 76 } 77 fprintf(stderr, "\nPassed %d tests\n\nPASS\n", (int)g_testlist.size()); 78 return 0; 79} 80 81#undef LOG // defined in base/logging.h 82// Ideally, we'd put the newline at the end, but this hack puts the 83// newline at the end of the previous log message, which is good enough :-) 84#define LOG(level) std::cerr << "\n" 85 86static std::string StringPrintf(const char* format, ...) { 87 char buf[256]; // should be big enough for all logging 88 va_list ap; 89 va_start(ap, format); 90 perftools_vsnprintf(buf, sizeof(buf), format, ap); 91 va_end(ap); 92 return buf; 93} 94 95namespace { 96template<typename T> class scoped_array { 97 public: 98 scoped_array(T* p) : p_(p) { } 99 ~scoped_array() { delete[] p_; } 100 const T* get() const { return p_; } 101 T* get() { return p_; } 102 T& operator[](int i) { return p_[i]; } 103 private: 104 T* p_; 105}; 106} 107 108// Note that these tests are stochastic. 109// This mean that the chance of correct code passing the test is, 110// in the case of 5 standard deviations: 111// kSigmas=5: ~99.99994267% 112// in the case of 4 standard deviations: 113// kSigmas=4: ~99.993666% 114static const double kSigmas = 4; 115static const size_t kSamplingInterval = 512*1024; 116 117// Tests that GetSamplePeriod returns the expected value 118// which is 1<<19 119TEST(Sampler, TestGetSamplePeriod) { 120 tcmalloc::Sampler sampler; 121 sampler.Init(1); 122 uint64_t sample_period; 123 sample_period = sampler.GetSamplePeriod(); 124 CHECK_GT(sample_period, 0); 125} 126 127// Tests of the quality of the random numbers generated 128// This uses the Anderson Darling test for uniformity. 129// See "Evaluating the Anderson-Darling Distribution" by Marsaglia 130// for details. 131 132// Short cut version of ADinf(z), z>0 (from Marsaglia) 133// This returns the p-value for Anderson Darling statistic in 134// the limit as n-> infinity. For finite n, apply the error fix below. 135double AndersonDarlingInf(double z) { 136 if (z < 2) { 137 return exp(-1.2337141 / z) / sqrt(z) * (2.00012 + (0.247105 - 138 (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 139 * z) * z) * z) * z) * z); 140 } 141 return exp( - exp(1.0776 - (2.30695 - (0.43424 - (0.082433 - 142 (0.008056 - 0.0003146 * z) * z) * z) * z) * z)); 143} 144 145// Corrects the approximation error in AndersonDarlingInf for small values of n 146// Add this to AndersonDarlingInf to get a better approximation 147// (from Marsaglia) 148double AndersonDarlingErrFix(int n, double x) { 149 if (x > 0.8) { 150 return (-130.2137 + (745.2337 - (1705.091 - (1950.646 - 151 (1116.360 - 255.7844 * x) * x) * x) * x) * x) / n; 152 } 153 double cutoff = 0.01265 + 0.1757 / n; 154 double t; 155 if (x < cutoff) { 156 t = x / cutoff; 157 t = sqrt(t) * (1 - t) * (49 * t - 102); 158 return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n; 159 } else { 160 t = (x - cutoff) / (0.8 - cutoff); 161 t = -0.00022633 + (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 162 * t) * t) * t) * t) * t; 163 return t * (0.04213 + 0.01365 / n) / n; 164 } 165} 166 167// Returns the AndersonDarling p-value given n and the value of the statistic 168double AndersonDarlingPValue(int n, double z) { 169 double ad = AndersonDarlingInf(z); 170 double errfix = AndersonDarlingErrFix(n, ad); 171 return ad + errfix; 172} 173 174double AndersonDarlingStatistic(int n, double* random_sample) { 175 double ad_sum = 0; 176 for (int i = 0; i < n; i++) { 177 ad_sum += (2*i + 1) * log(random_sample[i] * (1 - random_sample[n-1-i])); 178 } 179 double ad_statistic = - n - 1/static_cast<double>(n) * ad_sum; 180 return ad_statistic; 181} 182 183// Tests if the array of doubles is uniformly distributed. 184// Returns the p-value of the Anderson Darling Statistic 185// for the given set of sorted random doubles 186// See "Evaluating the Anderson-Darling Distribution" by 187// Marsaglia and Marsaglia for details. 188double AndersonDarlingTest(int n, double* random_sample) { 189 double ad_statistic = AndersonDarlingStatistic(n, random_sample); 190 LOG(INFO) << StringPrintf("AD stat = %f, n=%d\n", ad_statistic, n); 191 double p = AndersonDarlingPValue(n, ad_statistic); 192 return p; 193} 194 195// Test the AD Test. The value of the statistic should go to zero as n->infty 196// Not run as part of regular tests 197void ADTestTest(int n) { 198 scoped_array<double> random_sample(new double[n]); 199 for (int i = 0; i < n; i++) { 200 random_sample[i] = (i+0.01)/n; 201 } 202 sort(random_sample.get(), random_sample.get() + n); 203 double ad_stat = AndersonDarlingStatistic(n, random_sample.get()); 204 LOG(INFO) << StringPrintf("Testing the AD test. n=%d, ad_stat = %f", 205 n, ad_stat); 206} 207 208// Print the CDF of the distribution of the Anderson-Darling Statistic 209// Used for checking the Anderson-Darling Test 210// Not run as part of regular tests 211void ADCDF() { 212 for (int i = 1; i < 40; i++) { 213 double x = i/10.0; 214 LOG(INFO) << "x= " << x << " adpv= " 215 << AndersonDarlingPValue(100, x) << ", " 216 << AndersonDarlingPValue(1000, x); 217 } 218} 219 220// Testing that NextRandom generates uniform 221// random numbers. 222// Applies the Anderson-Darling test for uniformity 223void TestNextRandom(int n) { 224 tcmalloc::Sampler sampler; 225 sampler.Init(1); 226 uint64_t x = 1; 227 // This assumes that the prng returns 48 bit numbers 228 uint64_t max_prng_value = static_cast<uint64_t>(1)<<48; 229 // Initialize 230 for (int i = 1; i <= 20; i++) { // 20 mimics sampler.Init() 231 x = sampler.NextRandom(x); 232 } 233 scoped_array<uint64_t> int_random_sample(new uint64_t[n]); 234 // Collect samples 235 for (int i = 0; i < n; i++) { 236 int_random_sample[i] = x; 237 x = sampler.NextRandom(x); 238 } 239 // First sort them... 240 sort(int_random_sample.get(), int_random_sample.get() + n); 241 scoped_array<double> random_sample(new double[n]); 242 // Convert them to uniform randoms (in the range [0,1]) 243 for (int i = 0; i < n; i++) { 244 random_sample[i] = static_cast<double>(int_random_sample[i])/max_prng_value; 245 } 246 // Now compute the Anderson-Darling statistic 247 double ad_pvalue = AndersonDarlingTest(n, random_sample.get()); 248 LOG(INFO) << StringPrintf("pvalue for AndersonDarlingTest " 249 "with n= %d is p= %f\n", n, ad_pvalue); 250 CHECK_GT(min(ad_pvalue, 1 - ad_pvalue), 0.0001); 251 // << StringPrintf("prng is not uniform, %d\n", n); 252} 253 254 255TEST(Sampler, TestNextRandom_MultipleValues) { 256 TestNextRandom(10); // Check short-range correlation 257 TestNextRandom(100); 258 TestNextRandom(1000); 259 TestNextRandom(10000); // Make sure there's no systematic error 260} 261 262// Tests that PickNextSamplePeriod generates 263// geometrically distributed random numbers. 264// First converts to uniforms then applied the 265// Anderson-Darling test for uniformity. 266void TestPickNextSample(int n) { 267 tcmalloc::Sampler sampler; 268 sampler.Init(1); 269 scoped_array<uint64_t> int_random_sample(new uint64_t[n]); 270 int sample_period = sampler.GetSamplePeriod(); 271 int ones_count = 0; 272 for (int i = 0; i < n; i++) { 273 int_random_sample[i] = sampler.PickNextSamplingPoint(); 274 CHECK_GE(int_random_sample[i], 1); 275 if (int_random_sample[i] == 1) { 276 ones_count += 1; 277 } 278 CHECK_LT(ones_count, 4); // << " out of " << i << " samples."; 279 } 280 // First sort them... 281 sort(int_random_sample.get(), int_random_sample.get() + n); 282 scoped_array<double> random_sample(new double[n]); 283 // Convert them to uniform random numbers 284 // by applying the geometric CDF 285 for (int i = 0; i < n; i++) { 286 random_sample[i] = 1 - exp(-static_cast<double>(int_random_sample[i]) 287 / sample_period); 288 } 289 // Now compute the Anderson-Darling statistic 290 double geom_ad_pvalue = AndersonDarlingTest(n, random_sample.get()); 291 LOG(INFO) << StringPrintf("pvalue for geometric AndersonDarlingTest " 292 "with n= %d is p= %f\n", n, geom_ad_pvalue); 293 CHECK_GT(min(geom_ad_pvalue, 1 - geom_ad_pvalue), 0.0001); 294 // << "PickNextSamplingPoint does not produce good " 295 // "geometric/exponential random numbers\n"; 296} 297 298TEST(Sampler, TestPickNextSample_MultipleValues) { 299 TestPickNextSample(10); // Make sure the first few are good (enough) 300 TestPickNextSample(100); 301 TestPickNextSample(1000); 302 TestPickNextSample(10000); // Make sure there's no systematic error 303} 304 305 306// This is superceeded by the Anderson-Darling Test 307// and it not run now. 308// Tests how fast nearby values are spread out with LRand64 309// The purpose of this code is to determine how many 310// steps to apply to the seed during initialization 311void TestLRand64Spread() { 312 tcmalloc::Sampler sampler; 313 sampler.Init(1); 314 uint64_t current_value; 315 printf("Testing LRand64 Spread\n"); 316 for (int i = 1; i < 10; i++) { 317 printf("%d ", i); 318 current_value = i; 319 for (int j = 1; j < 100; j++) { 320 current_value = sampler.NextRandom(current_value); 321 } 322 LOG(INFO) << current_value; 323 } 324} 325 326 327// Test for Fastlog2 code 328// We care about the percentage error because we're using this 329// for choosing step sizes, so "close" is relative to the size of 330// the step we would get if we used the built-in log function 331TEST(Sampler, FastLog2) { 332 tcmalloc::Sampler sampler; 333 sampler.Init(1); 334 double max_ratio_error = 0; 335 for (double d = -1021.9; d < 1; d+= 0.13124235) { 336 double e = pow(2.0, d); 337 double truelog = log(e) / log(2.0); // log_2(e) 338 double fastlog = sampler.FastLog2(e); 339 max_ratio_error = max(max_ratio_error, 340 max(truelog/fastlog-1, fastlog/truelog-1)); 341 CHECK_LE(max_ratio_error, 0.01); 342 // << StringPrintf("d = %f, e=%f, truelog = %f, fastlog= %f\n", 343 // d, e, truelog, fastlog); 344 } 345 LOG(INFO) << StringPrintf("Fastlog2: max_ratio_error = %f\n", 346 max_ratio_error); 347} 348 349// Futher tests 350 351bool CheckMean(size_t mean, int num_samples) { 352 tcmalloc::Sampler sampler; 353 sampler.Init(1); 354 size_t total = 0; 355 for (int i = 0; i < num_samples; i++) { 356 total += sampler.PickNextSamplingPoint(); 357 } 358 double empirical_mean = total / static_cast<double>(num_samples); 359 double expected_sd = mean / pow(num_samples * 1.0, 0.5); 360 return(fabs(mean-empirical_mean) < expected_sd * kSigmas); 361} 362 363// Prints a sequence so you can look at the distribution 364void OutputSequence(int sequence_length) { 365 tcmalloc::Sampler sampler; 366 sampler.Init(1); 367 size_t next_step; 368 for (int i = 0; i< sequence_length; i++) { 369 next_step = sampler.PickNextSamplingPoint(); 370 LOG(INFO) << next_step; 371 } 372} 373 374 375double StandardDeviationsErrorInSample( 376 int total_samples, int picked_samples, 377 int alloc_size, int sampling_interval) { 378 double p = 1 - exp(-(static_cast<double>(alloc_size) / sampling_interval)); 379 double expected_samples = total_samples * p; 380 double sd = pow(p*(1-p)*total_samples, 0.5); 381 return((picked_samples - expected_samples) / sd); 382} 383 384TEST(Sampler, LargeAndSmallAllocs_CombinedTest) { 385 tcmalloc::Sampler sampler; 386 sampler.Init(1); 387 int counter_big = 0; 388 int counter_small = 0; 389 int size_big = 129*8*1024+1; 390 int size_small = 1024*8; 391 int num_iters = 128*4*8; 392 // Allocate in mixed chunks 393 for (int i = 0; i < num_iters; i++) { 394 if (sampler.SampleAllocation(size_big)) { 395 counter_big += 1; 396 } 397 for (int i = 0; i < 129; i++) { 398 if (sampler.SampleAllocation(size_small)) { 399 counter_small += 1; 400 } 401 } 402 } 403 // Now test that there are the right number of each 404 double large_allocs_sds = 405 StandardDeviationsErrorInSample(num_iters, counter_big, 406 size_big, kSamplingInterval); 407 double small_allocs_sds = 408 StandardDeviationsErrorInSample(num_iters*129, counter_small, 409 size_small, kSamplingInterval); 410 LOG(INFO) << StringPrintf("large_allocs_sds = %f\n", large_allocs_sds); 411 LOG(INFO) << StringPrintf("small_allocs_sds = %f\n", small_allocs_sds); 412 CHECK_LE(fabs(large_allocs_sds), kSigmas); 413 CHECK_LE(fabs(small_allocs_sds), kSigmas); 414} 415 416// Tests whether the mean is about right over 1000 samples 417TEST(Sampler, IsMeanRight) { 418 CHECK(CheckMean(kSamplingInterval, 1000)); 419} 420 421// This flag is for the OldSampler class to use 422const int64 FLAGS_mock_tcmalloc_sample_parameter = 1<<19; 423 424// A cut down and slightly refactored version of the old Sampler 425class OldSampler { 426 public: 427 void Init(uint32_t seed); 428 void Cleanup() {} 429 430 // Record allocation of "k" bytes. Return true iff allocation 431 // should be sampled 432 bool SampleAllocation(size_t k); 433 434 // Generate a geometric with mean 1M (or FLAG value) 435 void PickNextSample(size_t k); 436 437 // Initialize the statics for the Sample class 438 static void InitStatics() { 439 sample_period = 1048583; 440 } 441 size_t bytes_until_sample_; 442 443 private: 444 uint32_t rnd_; // Cheap random number generator 445 static uint64_t sample_period; 446 // Should be a prime just above a power of 2: 447 // 2, 5, 11, 17, 37, 67, 131, 257, 448 // 521, 1031, 2053, 4099, 8209, 16411, 449 // 32771, 65537, 131101, 262147, 524309, 1048583, 450 // 2097169, 4194319, 8388617, 16777259, 33554467 451}; 452 453// Statics for OldSampler 454uint64_t OldSampler::sample_period; 455 456void OldSampler::Init(uint32_t seed) { 457 // Initialize PRNG -- run it for a bit to get to good values 458 if (seed != 0) { 459 rnd_ = seed; 460 } else { 461 rnd_ = 12345; 462 } 463 bytes_until_sample_ = 0; 464 for (int i = 0; i < 100; i++) { 465 PickNextSample(sample_period * 2); 466 } 467}; 468 469// A cut-down version of the old PickNextSampleRoutine 470void OldSampler::PickNextSample(size_t k) { 471 // Make next "random" number 472 // x^32+x^22+x^2+x^1+1 is a primitive polynomial for random numbers 473 static const uint32_t kPoly = (1 << 22) | (1 << 2) | (1 << 1) | (1 << 0); 474 uint32_t r = rnd_; 475 rnd_ = (r << 1) ^ ((static_cast<int32_t>(r) >> 31) & kPoly); 476 477 // Next point is "rnd_ % (sample_period)". I.e., average 478 // increment is "sample_period/2". 479 const int flag_value = FLAGS_mock_tcmalloc_sample_parameter; 480 static int last_flag_value = -1; 481 482 if (flag_value != last_flag_value) { 483 // There should be a spinlock here, but this code is 484 // for benchmarking only. 485 sample_period = 1048583; 486 last_flag_value = flag_value; 487 } 488 489 bytes_until_sample_ += rnd_ % sample_period; 490 491 if (k > (static_cast<size_t>(-1) >> 2)) { 492 // If the user has asked for a huge allocation then it is possible 493 // for the code below to loop infinitely. Just return (note that 494 // this throws off the sampling accuracy somewhat, but a user who 495 // is allocating more than 1G of memory at a time can live with a 496 // minor inaccuracy in profiling of small allocations, and also 497 // would rather not wait for the loop below to terminate). 498 return; 499 } 500 501 while (bytes_until_sample_ < k) { 502 // Increase bytes_until_sample_ by enough average sampling periods 503 // (sample_period >> 1) to allow us to sample past the current 504 // allocation. 505 bytes_until_sample_ += (sample_period >> 1); 506 } 507 508 bytes_until_sample_ -= k; 509} 510 511inline bool OldSampler::SampleAllocation(size_t k) { 512 if (bytes_until_sample_ < k) { 513 PickNextSample(k); 514 return true; 515 } else { 516 bytes_until_sample_ -= k; 517 return false; 518 } 519} 520 521// This checks that the stated maximum value for the 522// tcmalloc_sample_parameter flag never overflows bytes_until_sample_ 523TEST(Sampler, bytes_until_sample_Overflow_Underflow) { 524 tcmalloc::Sampler sampler; 525 sampler.Init(1); 526 uint64_t one = 1; 527 // sample_parameter = 0; // To test the edge case 528 uint64_t sample_parameter_array[4] = {0, 1, one<<19, one<<58}; 529 for (int i = 0; i < 4; i++) { 530 uint64_t sample_parameter = sample_parameter_array[i]; 531 LOG(INFO) << "sample_parameter = " << sample_parameter; 532 double sample_scaling = - log(2.0) * sample_parameter; 533 // Take the top 26 bits as the random number 534 // (This plus the 1<<26 sampling bound give a max step possible of 535 // 1209424308 bytes.) 536 const uint64_t prng_mod_power = 48; // Number of bits in prng 537 538 // First, check the largest_prng value 539 uint64_t largest_prng_value = (static_cast<uint64_t>(1)<<48) - 1; 540 double q = (largest_prng_value >> (prng_mod_power - 26)) + 1.0; 541 LOG(INFO) << StringPrintf("q = %f\n", q); 542 LOG(INFO) << StringPrintf("FastLog2(q) = %f\n", sampler.FastLog2(q)); 543 LOG(INFO) << StringPrintf("log2(q) = %f\n", log(q)/log(2.0)); 544 // Replace min(sampler.FastLog2(q) - 26, 0.0) with 545 // (sampler.FastLog2(q) - 26.000705) when using that optimization 546 uint64_t smallest_sample_step 547 = static_cast<uint64_t>(min(sampler.FastLog2(q) - 26, 0.0) 548 * sample_scaling + 1); 549 LOG(INFO) << "Smallest sample step is " << smallest_sample_step; 550 uint64_t cutoff = static_cast<uint64_t>(10) 551 * (sample_parameter/(one<<24) + 1); 552 LOG(INFO) << "Acceptable value is < " << cutoff; 553 // This checks that the answer is "small" and positive 554 CHECK_LE(smallest_sample_step, cutoff); 555 556 // Next, check with the smallest prng value 557 uint64_t smallest_prng_value = 0; 558 q = (smallest_prng_value >> (prng_mod_power - 26)) + 1.0; 559 LOG(INFO) << StringPrintf("q = %f\n", q); 560 // Replace min(sampler.FastLog2(q) - 26, 0.0) with 561 // (sampler.FastLog2(q) - 26.000705) when using that optimization 562 uint64_t largest_sample_step 563 = static_cast<uint64_t>(min(sampler.FastLog2(q) - 26, 0.0) 564 * sample_scaling + 1); 565 LOG(INFO) << "Largest sample step is " << largest_sample_step; 566 CHECK_LE(largest_sample_step, one<<63); 567 CHECK_GE(largest_sample_step, smallest_sample_step); 568 } 569} 570 571 572// Test that NextRand is in the right range. Unfortunately, this is a 573// stochastic test which could miss problems. 574TEST(Sampler, NextRand_range) { 575 tcmalloc::Sampler sampler; 576 sampler.Init(1); 577 uint64_t one = 1; 578 // The next number should be (one << 48) - 1 579 uint64_t max_value = (one << 48) - 1; 580 uint64_t x = (one << 55); 581 int n = 22; // 27; 582 LOG(INFO) << "Running sampler.NextRandom 1<<" << n << " times"; 583 for (int i = 1; i <= (1<<n); i++) { // 20 mimics sampler.Init() 584 x = sampler.NextRandom(x); 585 CHECK_LE(x, max_value); 586 } 587} 588 589// Tests certain arithmetic operations to make sure they compute what we 590// expect them too (for testing across different platforms) 591TEST(Sampler, arithmetic_1) { 592 tcmalloc::Sampler sampler; 593 sampler.Init(1); 594 uint64_t rnd; // our 48 bit random number, which we don't trust 595 const uint64_t prng_mod_power = 48; 596 uint64_t one = 1; 597 rnd = one; 598 uint64_t max_value = (one << 48) - 1; 599 for (int i = 1; i <= (1>>27); i++) { // 20 mimics sampler.Init() 600 rnd = sampler.NextRandom(rnd); 601 CHECK_LE(rnd, max_value); 602 double q = (rnd >> (prng_mod_power - 26)) + 1.0; 603 CHECK_GE(q, 0); // << rnd << " " << prng_mod_power; 604 } 605 // Test some potentially out of bounds value for rnd 606 for (int i = 1; i <= 66; i++) { 607 rnd = one << i; 608 double q = (rnd >> (prng_mod_power - 26)) + 1.0; 609 LOG(INFO) << "rnd = " << rnd << " i=" << i << " q=" << q; 610 CHECK_GE(q, 0); 611 // << " rnd=" << rnd << " i=" << i << " prng_mod_power" << prng_mod_power; 612 } 613} 614 615void test_arithmetic(uint64_t rnd) { 616 const uint64_t prng_mod_power = 48; // Number of bits in prng 617 uint64_t shifted_rnd = rnd >> (prng_mod_power - 26); 618 CHECK_GE(shifted_rnd, 0); 619 CHECK_LT(shifted_rnd, (1<<26)); 620 LOG(INFO) << shifted_rnd; 621 LOG(INFO) << static_cast<double>(shifted_rnd); 622 CHECK_GE(static_cast<double>(static_cast<uint32_t>(shifted_rnd)), 0); 623 // << " rnd=" << rnd << " srnd=" << shifted_rnd; 624 CHECK_GE(static_cast<double>(shifted_rnd), 0); 625 // << " rnd=" << rnd << " srnd=" << shifted_rnd; 626 double q = static_cast<double>(shifted_rnd) + 1.0; 627 CHECK_GT(q, 0); 628} 629 630// Tests certain arithmetic operations to make sure they compute what we 631// expect them too (for testing across different platforms) 632// know bad values under with -c dbg --cpu piii for _some_ binaries: 633// rnd=227453640600554 634// shifted_rnd=54229173 635// (hard to reproduce) 636TEST(Sampler, arithmetic_2) { 637 uint64_t rnd = 227453640600554LL; 638 test_arithmetic(rnd); 639} 640 641 642// It's not really a test, but it's good to know 643TEST(Sample, size_of_class) { 644 tcmalloc::Sampler sampler; 645 sampler.Init(1); 646 LOG(INFO) << "Size of Sampler class is: " << sizeof(tcmalloc::Sampler); 647 LOG(INFO) << "Size of Sampler object is: " << sizeof(sampler); 648} 649 650// Make sure sampling is enabled, or the tests won't work right. 651DECLARE_int64(tcmalloc_sample_parameter); 652 653int main(int argc, char **argv) { 654 if (FLAGS_tcmalloc_sample_parameter == 0) 655 FLAGS_tcmalloc_sample_parameter = 524288; 656 return RUN_ALL_TESTS(); 657} 658