blob: 50bc10748c05f75bc5f638024f49cecc1bf0fb5d [file] [log] [blame]
// Copyright (c) 2005, 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.
// ---
// Unittest for the TCMalloc implementation.
//
// * The test consists of a set of threads.
// * Each thread maintains a set of allocated objects, with
// a bound on the total amount of data in the set.
// * Each allocated object's contents are generated by
// hashing the object pointer, and a generation count
// in the object. This allows us to easily check for
// data corruption.
// * At any given step, the thread can do any of the following:
// a. Allocate an object
// b. Increment an object's generation count and update
// its contents.
// c. Pass the object to another thread
// d. Free an object
// Also, at the end of every step, object(s) are freed to maintain
// the memory upper-bound.
//
// If this test is compiled with -DDEBUGALLOCATION, then we don't
// run some tests that test the inner workings of tcmalloc and
// break on debugallocation: that certain allocations are aligned
// in a certain way (even though no standard requires it), and that
// realloc() tries to minimize copying (which debug allocators don't
// care about).
#include "config_for_unittests.h"
// Complicated ordering requirements. tcmalloc.h defines (indirectly)
// _POSIX_C_SOURCE, which it needs so stdlib.h defines posix_memalign.
// unistd.h, on the other hand, requires _POSIX_C_SOURCE to be unset,
// at least on FreeBSD, in order to define sbrk. The solution
// is to #include unistd.h first. This is safe because unistd.h
// doesn't sub-include stdlib.h, so we'll still get posix_memalign
// when we #include stdlib.h. Blah.
#ifdef HAVE_UNISTD_H
#include <unistd.h> // for testing sbrk hooks
#endif
#include "tcmalloc.h" // must come early, to pick up posix_memalign
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#if defined HAVE_STDINT_H
#include <stdint.h> // for intptr_t
#endif
#include <sys/types.h> // for size_t
#ifdef HAVE_FCNTL_H
#include <fcntl.h> // for open; used with mmap-hook test
#endif
#ifdef HAVE_MMAP
#include <sys/mman.h> // for testing mmap hooks
#endif
#ifdef HAVE_MALLOC_H
#include <malloc.h> // defines pvalloc/etc on cygwin
#endif
#include <assert.h>
#include <vector>
#include <algorithm>
#include <string>
#include <new>
#include "base/logging.h"
#include "base/simple_mutex.h"
#include "gperftools/malloc_hook.h"
#include "gperftools/malloc_extension.h"
#include "gperftools/tcmalloc.h"
#include "thread_cache.h"
#include "system-alloc.h"
#include "tests/testutil.h"
// Windows doesn't define pvalloc and a few other obsolete unix
// functions; nor does it define posix_memalign (which is not obsolete).
#if defined(_WIN32)
# define cfree free // don't bother to try to test these obsolete fns
# define valloc malloc
# define pvalloc malloc
// I'd like to map posix_memalign to _aligned_malloc, but _aligned_malloc
// must be paired with _aligned_free (not normal free), which is too
// invasive a change to how we allocate memory here. So just bail
static bool kOSSupportsMemalign = false;
static inline void* Memalign(size_t align, size_t size) {
//LOG(FATAL) << "memalign not supported on windows";
exit(1);
return NULL;
}
static inline int PosixMemalign(void** ptr, size_t align, size_t size) {
//LOG(FATAL) << "posix_memalign not supported on windows";
exit(1);
return -1;
}
// OS X defines posix_memalign in some OS versions but not others;
// it's confusing enough to check that it's easiest to just not to test.
#elif defined(__APPLE__)
static bool kOSSupportsMemalign = false;
static inline void* Memalign(size_t align, size_t size) {
//LOG(FATAL) << "memalign not supported on OS X";
exit(1);
return NULL;
}
static inline int PosixMemalign(void** ptr, size_t align, size_t size) {
//LOG(FATAL) << "posix_memalign not supported on OS X";
exit(1);
return -1;
}
#else
static bool kOSSupportsMemalign = true;
static inline void* Memalign(size_t align, size_t size) {
return memalign(align, size);
}
static inline int PosixMemalign(void** ptr, size_t align, size_t size) {
return posix_memalign(ptr, align, size);
}
#endif
// On systems (like freebsd) that don't define MAP_ANONYMOUS, use the old
// form of the name instead.
#ifndef MAP_ANONYMOUS
# define MAP_ANONYMOUS MAP_ANON
#endif
#define LOGSTREAM stdout
using std::vector;
using std::string;
DECLARE_double(tcmalloc_release_rate);
DECLARE_int32(max_free_queue_size); // in debugallocation.cc
DECLARE_int64(tcmalloc_sample_parameter);
namespace testing {
static const int FLAGS_numtests = 50000;
static const int FLAGS_log_every_n_tests = 50000; // log exactly once
// Testing parameters
static const int FLAGS_lgmaxsize = 16; // lg() of the max size object to alloc
static const int FLAGS_numthreads = 10; // Number of threads
static const int FLAGS_threadmb = 4; // Max memory size allocated by thread
static const int FLAGS_lg_max_memalign = 18; // lg of max alignment for memalign
static const double FLAGS_memalign_min_fraction = 0; // min expected%
static const double FLAGS_memalign_max_fraction = 0.4; // max expected%
static const double FLAGS_memalign_max_alignment_ratio = 6; // alignment/size
// Weights of different operations
static const int FLAGS_allocweight = 50; // Weight for picking allocation
static const int FLAGS_freeweight = 50; // Weight for picking free
static const int FLAGS_updateweight = 10; // Weight for picking update
static const int FLAGS_passweight = 1; // Weight for passing object
static const int kSizeBits = 8 * sizeof(size_t);
static const size_t kMaxSize = ~static_cast<size_t>(0);
static const size_t kMaxSignedSize = ((size_t(1) << (kSizeBits-1)) - 1);
static const size_t kNotTooBig = 100000;
// We want an allocation that is definitely more than main memory. OS
// X has special logic to discard very big allocs before even passing
// the request along to the user-defined memory allocator; we're not
// interested in testing their logic, so we have to make sure we're
// not *too* big.
static const size_t kTooBig = kMaxSize - 100000;
static int news_handled = 0;
// Global array of threads
class TesterThread;
static TesterThread** threads;
// To help with generating random numbers
class TestHarness {
private:
// Information kept per type
struct Type {
string name;
int type;
int weight;
};
public:
TestHarness(int seed)
: types_(new vector<Type>), total_weight_(0), num_tests_(0) {
srandom(seed);
}
~TestHarness() {
delete types_;
}
// Add operation type with specified weight. When starting a new
// iteration, an operation type is picked with probability
// proportional to its weight.
//
// "type" must be non-negative.
// "weight" must be non-negative.
void AddType(int type, int weight, const char* name);
// Call this to get the type of operation for the next iteration.
// It returns a random operation type from the set of registered
// operations. Returns -1 if tests should finish.
int PickType();
// If n == 0, returns the next pseudo-random number in the range [0 .. 0]
// If n != 0, returns the next pseudo-random number in the range [0 .. n)
int Uniform(int n) {
if (n == 0) {
return random() * 0;
} else {
return random() % n;
}
}
// Pick "base" uniformly from range [0,max_log] and then return
// "base" random bits. The effect is to pick a number in the range
// [0,2^max_log-1] with bias towards smaller numbers.
int Skewed(int max_log) {
const int base = random() % (max_log+1);
return random() % (1 << base);
}
private:
vector<Type>* types_; // Registered types
int total_weight_; // Total weight of all types
int num_tests_; // Num tests run so far
};
void TestHarness::AddType(int type, int weight, const char* name) {
Type t;
t.name = name;
t.type = type;
t.weight = weight;
types_->push_back(t);
total_weight_ += weight;
}
int TestHarness::PickType() {
if (num_tests_ >= FLAGS_numtests) return -1;
num_tests_++;
assert(total_weight_ > 0);
// This is a little skewed if total_weight_ doesn't divide 2^31, but it's close
int v = Uniform(total_weight_);
int i;
for (i = 0; i < types_->size(); i++) {
v -= (*types_)[i].weight;
if (v < 0) {
break;
}
}
assert(i < types_->size());
if ((num_tests_ % FLAGS_log_every_n_tests) == 0) {
fprintf(LOGSTREAM, " Test %d out of %d: %s\n",
num_tests_, FLAGS_numtests, (*types_)[i].name.c_str());
}
return (*types_)[i].type;
}
class AllocatorState : public TestHarness {
public:
explicit AllocatorState(int seed) : TestHarness(seed), memalign_fraction_(0) {
if (kOSSupportsMemalign) {
CHECK_GE(FLAGS_memalign_max_fraction, 0);
CHECK_LE(FLAGS_memalign_max_fraction, 1);
CHECK_GE(FLAGS_memalign_min_fraction, 0);
CHECK_LE(FLAGS_memalign_min_fraction, 1);
double delta = FLAGS_memalign_max_fraction - FLAGS_memalign_min_fraction;
CHECK_GE(delta, 0);
memalign_fraction_ = (Uniform(10000)/10000.0 * delta +
FLAGS_memalign_min_fraction);
//fprintf(LOGSTREAM, "memalign fraction: %f\n", memalign_fraction_);
}
}
virtual ~AllocatorState() {}
// Allocate memory. Randomly choose between malloc() or posix_memalign().
void* alloc(size_t size) {
if (Uniform(100) < memalign_fraction_ * 100) {
// Try a few times to find a reasonable alignment, or fall back on malloc.
for (int i = 0; i < 5; i++) {
size_t alignment = 1 << Uniform(FLAGS_lg_max_memalign);
if (alignment >= sizeof(intptr_t) &&
(size < sizeof(intptr_t) ||
alignment < FLAGS_memalign_max_alignment_ratio * size)) {
void *result = reinterpret_cast<void*>(static_cast<intptr_t>(0x1234));
int err = PosixMemalign(&result, alignment, size);
if (err != 0) {
CHECK_EQ(err, ENOMEM);
}
return err == 0 ? result : NULL;
}
}
}
return malloc(size);
}
private:
double memalign_fraction_;
};
// Info kept per thread
class TesterThread {
private:
// Info kept per allocated object
struct Object {
char* ptr; // Allocated pointer
int size; // Allocated size
int generation; // Generation counter of object contents
};
Mutex lock_; // For passing in another thread's obj
int id_; // My thread id
AllocatorState rnd_; // For generating random numbers
vector<Object> heap_; // This thread's heap
vector<Object> passed_; // Pending objects passed from others
size_t heap_size_; // Current heap size
int locks_ok_; // Number of OK TryLock() ops
int locks_failed_; // Number of failed TryLock() ops
// Type of operations
enum Type { ALLOC, FREE, UPDATE, PASS };
// ACM minimal standard random number generator. (re-entrant.)
class ACMRandom {
int32 seed_;
public:
explicit ACMRandom(int32 seed) { seed_ = seed; }
int32 Next() {
const int32 M = 2147483647L; // 2^31-1
const int32 A = 16807;
// In effect, we are computing seed_ = (seed_ * A) % M, where M = 2^31-1
uint32 lo = A * (int32)(seed_ & 0xFFFF);
uint32 hi = A * (int32)((uint32)seed_ >> 16);
lo += (hi & 0x7FFF) << 16;
if (lo > M) {
lo &= M;
++lo;
}
lo += hi >> 15;
if (lo > M) {
lo &= M;
++lo;
}
return (seed_ = (int32) lo);
}
};
public:
TesterThread(int id)
: id_(id),
rnd_(id+1),
heap_size_(0),
locks_ok_(0),
locks_failed_(0) {
}
virtual ~TesterThread() {
if (FLAGS_verbose)
fprintf(LOGSTREAM, "Thread %2d: locks %6d ok; %6d trylocks failed\n",
id_, locks_ok_, locks_failed_);
if (locks_ok_ + locks_failed_ >= 1000) {
CHECK_LE(locks_failed_, locks_ok_ / 2);
}
}
virtual void Run() {
rnd_.AddType(ALLOC, FLAGS_allocweight, "allocate");
rnd_.AddType(FREE, FLAGS_freeweight, "free");
rnd_.AddType(UPDATE, FLAGS_updateweight, "update");
rnd_.AddType(PASS, FLAGS_passweight, "pass");
while (true) {
AcquirePassedObjects();
switch (rnd_.PickType()) {
case ALLOC: AllocateObject(); break;
case FREE: FreeObject(); break;
case UPDATE: UpdateObject(); break;
case PASS: PassObject(); break;
case -1: goto done;
default: assert(NULL == "Unknown type");
}
ShrinkHeap();
}
done:
DeleteHeap();
}
// Allocate a new object
void AllocateObject() {
Object object;
object.size = rnd_.Skewed(FLAGS_lgmaxsize);
object.ptr = static_cast<char*>(rnd_.alloc(object.size));
CHECK(object.ptr);
object.generation = 0;
FillContents(&object);
heap_.push_back(object);
heap_size_ += object.size;
}
// Mutate a random object
void UpdateObject() {
if (heap_.empty()) return;
const int index = rnd_.Uniform(heap_.size());
CheckContents(heap_[index]);
heap_[index].generation++;
FillContents(&heap_[index]);
}
// Free a random object
void FreeObject() {
if (heap_.empty()) return;
const int index = rnd_.Uniform(heap_.size());
Object object = heap_[index];
CheckContents(object);
free(object.ptr);
heap_size_ -= object.size;
heap_[index] = heap_[heap_.size()-1];
heap_.pop_back();
}
// Delete all objects in the heap
void DeleteHeap() {
while (!heap_.empty()) {
FreeObject();
}
}
// Free objects until our heap is small enough
void ShrinkHeap() {
while (heap_size_ > FLAGS_threadmb << 20) {
assert(!heap_.empty());
FreeObject();
}
}
// Pass a random object to another thread
void PassObject() {
// Pick object to pass
if (heap_.empty()) return;
const int index = rnd_.Uniform(heap_.size());
Object object = heap_[index];
CheckContents(object);
// Pick thread to pass
const int tid = rnd_.Uniform(FLAGS_numthreads);
TesterThread* thread = threads[tid];
if (thread->lock_.TryLock()) {
// Pass the object
locks_ok_++;
thread->passed_.push_back(object);
thread->lock_.Unlock();
heap_size_ -= object.size;
heap_[index] = heap_[heap_.size()-1];
heap_.pop_back();
} else {
locks_failed_++;
}
}
// Grab any objects passed to this thread by another thread
void AcquirePassedObjects() {
// We do not create unnecessary contention by always using
// TryLock(). Plus we unlock immediately after swapping passed
// objects into a local vector.
vector<Object> copy;
{ // Locking scope
if (!lock_.TryLock()) {
locks_failed_++;
return;
}
locks_ok_++;
swap(copy, passed_);
lock_.Unlock();
}
for (int i = 0; i < copy.size(); ++i) {
const Object& object = copy[i];
CheckContents(object);
heap_.push_back(object);
heap_size_ += object.size;
}
}
// Fill object contents according to ptr/generation
void FillContents(Object* object) {
ACMRandom r(reinterpret_cast<intptr_t>(object->ptr) & 0x7fffffff);
for (int i = 0; i < object->generation; ++i) {
r.Next();
}
const char c = static_cast<char>(r.Next());
memset(object->ptr, c, object->size);
}
// Check object contents
void CheckContents(const Object& object) {
ACMRandom r(reinterpret_cast<intptr_t>(object.ptr) & 0x7fffffff);
for (int i = 0; i < object.generation; ++i) {
r.Next();
}
// For large objects, we just check a prefix/suffix
const char expected = static_cast<char>(r.Next());
const int limit1 = object.size < 32 ? object.size : 32;
const int start2 = limit1 > object.size - 32 ? limit1 : object.size - 32;
for (int i = 0; i < limit1; ++i) {
CHECK_EQ(object.ptr[i], expected);
}
for (int i = start2; i < object.size; ++i) {
CHECK_EQ(object.ptr[i], expected);
}
}
};
static void RunThread(int thread_id) {
threads[thread_id]->Run();
}
static void TryHugeAllocation(size_t s, AllocatorState* rnd) {
void* p = rnd->alloc(s);
CHECK(p == NULL); // huge allocation s should fail!
}
static void TestHugeAllocations(AllocatorState* rnd) {
// Check that asking for stuff tiny bit smaller than largest possible
// size returns NULL.
for (size_t i = 0; i < 70000; i += rnd->Uniform(20)) {
TryHugeAllocation(kMaxSize - i, rnd);
}
// Asking for memory sizes near signed/unsigned boundary (kMaxSignedSize)
// might work or not, depending on the amount of virtual memory.
#ifndef DEBUGALLOCATION // debug allocation takes forever for huge allocs
for (size_t i = 0; i < 100; i++) {
void* p = NULL;
p = rnd->alloc(kMaxSignedSize + i);
if (p) free(p); // if: free(NULL) is not necessarily defined
p = rnd->alloc(kMaxSignedSize - i);
if (p) free(p);
}
#endif
// Check that ReleaseFreeMemory has no visible effect (aka, does not
// crash the test):
MallocExtension* inst = MallocExtension::instance();
CHECK(inst);
inst->ReleaseFreeMemory();
}
static void TestCalloc(size_t n, size_t s, bool ok) {
char* p = reinterpret_cast<char*>(calloc(n, s));
if (FLAGS_verbose)
fprintf(LOGSTREAM, "calloc(%" PRIxS ", %" PRIxS "): %p\n", n, s, p);
if (!ok) {
CHECK(p == NULL); // calloc(n, s) should not succeed
} else {
CHECK(p != NULL); // calloc(n, s) should succeed
for (int i = 0; i < n*s; i++) {
CHECK(p[i] == '\0');
}
free(p);
}
}
// This makes sure that reallocing a small number of bytes in either
// direction doesn't cause us to allocate new memory.
static void TestRealloc() {
#ifndef DEBUGALLOCATION // debug alloc doesn't try to minimize reallocs
// When sampling, we always allocate in units of page-size, which
// makes reallocs of small sizes do extra work (thus, failing these
// checks). Since sampling is random, we turn off sampling to make
// sure that doesn't happen to us here.
const int64 old_sample_parameter = FLAGS_tcmalloc_sample_parameter;
FLAGS_tcmalloc_sample_parameter = 0; // turn off sampling
int start_sizes[] = { 100, 1000, 10000, 100000 };
int deltas[] = { 1, -2, 4, -8, 16, -32, 64, -128 };
for (int s = 0; s < sizeof(start_sizes)/sizeof(*start_sizes); ++s) {
void* p = malloc(start_sizes[s]);
CHECK(p);
// The larger the start-size, the larger the non-reallocing delta.
for (int d = 0; d < (s+1) * 2; ++d) {
void* new_p = realloc(p, start_sizes[s] + deltas[d]);
CHECK(p == new_p); // realloc should not allocate new memory
}
// Test again, but this time reallocing smaller first.
for (int d = 0; d < s*2; ++d) {
void* new_p = realloc(p, start_sizes[s] - deltas[d]);
CHECK(p == new_p); // realloc should not allocate new memory
}
free(p);
}
FLAGS_tcmalloc_sample_parameter = old_sample_parameter;
#endif
}
static void TestNewHandler() throw (std::bad_alloc) {
++news_handled;
throw std::bad_alloc();
}
static void TestOneNew(void* (*func)(size_t)) {
// success test
try {
void* ptr = (*func)(kNotTooBig);
if (0 == ptr) {
fprintf(LOGSTREAM, "allocation should not have failed.\n");
abort();
}
} catch (...) {
fprintf(LOGSTREAM, "allocation threw unexpected exception.\n");
abort();
}
// failure test
// we should always receive a bad_alloc exception
try {
(*func)(kTooBig);
fprintf(LOGSTREAM, "allocation should have failed.\n");
abort();
} catch (const std::bad_alloc&) {
// correct
} catch (...) {
fprintf(LOGSTREAM, "allocation threw unexpected exception.\n");
abort();
}
}
static void TestNew(void* (*func)(size_t)) {
news_handled = 0;
// test without new_handler:
std::new_handler saved_handler = std::set_new_handler(0);
TestOneNew(func);
// test with new_handler:
std::set_new_handler(TestNewHandler);
TestOneNew(func);
if (news_handled != 1) {
fprintf(LOGSTREAM, "new_handler was not called.\n");
abort();
}
std::set_new_handler(saved_handler);
}
static void TestOneNothrowNew(void* (*func)(size_t, const std::nothrow_t&)) {
// success test
try {
void* ptr = (*func)(kNotTooBig, std::nothrow);
if (0 == ptr) {
fprintf(LOGSTREAM, "allocation should not have failed.\n");
abort();
}
} catch (...) {
fprintf(LOGSTREAM, "allocation threw unexpected exception.\n");
abort();
}
// failure test
// we should always receive a bad_alloc exception
try {
if ((*func)(kTooBig, std::nothrow) != 0) {
fprintf(LOGSTREAM, "allocation should have failed.\n");
abort();
}
} catch (...) {
fprintf(LOGSTREAM, "nothrow allocation threw unexpected exception.\n");
abort();
}
}
static void TestNothrowNew(void* (*func)(size_t, const std::nothrow_t&)) {
news_handled = 0;
// test without new_handler:
std::new_handler saved_handler = std::set_new_handler(0);
TestOneNothrowNew(func);
// test with new_handler:
std::set_new_handler(TestNewHandler);
TestOneNothrowNew(func);
if (news_handled != 1) {
fprintf(LOGSTREAM, "nothrow new_handler was not called.\n");
abort();
}
std::set_new_handler(saved_handler);
}
// These are used as callbacks by the sanity-check. Set* and Reset*
// register the hook that counts how many times the associated memory
// function is called. After each such call, call Verify* to verify
// that we used the tcmalloc version of the call, and not the libc.
// Note the ... in the hook signature: we don't care what arguments
// the hook takes.
#define MAKE_HOOK_CALLBACK(hook_type) \
static int g_##hook_type##_calls = 0; \
static void IncrementCallsTo##hook_type(...) { \
g_##hook_type##_calls++; \
} \
static void Verify##hook_type##WasCalled() { \
CHECK_GT(g_##hook_type##_calls, 0); \
g_##hook_type##_calls = 0; /* reset for next call */ \
} \
static void Set##hook_type() { \
CHECK(MallocHook::Add##hook_type( \
(MallocHook::hook_type)&IncrementCallsTo##hook_type)); \
} \
static void Reset##hook_type() { \
CHECK(MallocHook::Remove##hook_type( \
(MallocHook::hook_type)&IncrementCallsTo##hook_type)); \
}
// We do one for each hook typedef in malloc_hook.h
MAKE_HOOK_CALLBACK(NewHook);
MAKE_HOOK_CALLBACK(DeleteHook);
MAKE_HOOK_CALLBACK(MmapHook);
MAKE_HOOK_CALLBACK(MremapHook);
MAKE_HOOK_CALLBACK(MunmapHook);
MAKE_HOOK_CALLBACK(SbrkHook);
static void TestAlignmentForSize(int size) {
fprintf(LOGSTREAM, "Testing alignment of malloc(%d)\n", size);
static const int kNum = 100;
void* ptrs[kNum];
for (int i = 0; i < kNum; i++) {
ptrs[i] = malloc(size);
uintptr_t p = reinterpret_cast<uintptr_t>(ptrs[i]);
CHECK((p % sizeof(void*)) == 0);
CHECK((p % sizeof(double)) == 0);
// Must have 16-byte (or 8-byte in case of -DTCMALLOC_ALIGN_8BYTES)
// alignment for large enough objects
if (size >= kMinAlign) {
CHECK((p % kMinAlign) == 0);
}
}
for (int i = 0; i < kNum; i++) {
free(ptrs[i]);
}
}
static void TestMallocAlignment() {
for (int lg = 0; lg < 16; lg++) {
TestAlignmentForSize((1<<lg) - 1);
TestAlignmentForSize((1<<lg) + 0);
TestAlignmentForSize((1<<lg) + 1);
}
}
static void TestHugeThreadCache() {
fprintf(LOGSTREAM, "==== Testing huge thread cache\n");
// More than 2^16 to cause integer overflow of 16 bit counters.
static const int kNum = 70000;
char** array = new char*[kNum];
for (int i = 0; i < kNum; ++i) {
array[i] = new char[10];
}
for (int i = 0; i < kNum; ++i) {
delete[] array[i];
}
delete[] array;
}
namespace {
struct RangeCallbackState {
uintptr_t ptr;
base::MallocRange::Type expected_type;
size_t min_size;
bool matched;
};
static void RangeCallback(void* arg, const base::MallocRange* r) {
RangeCallbackState* state = reinterpret_cast<RangeCallbackState*>(arg);
if (state->ptr >= r->address &&
state->ptr < r->address + r->length) {
if (state->expected_type == base::MallocRange::FREE) {
// We are expecting r->type == FREE, but ReleaseMemory
// may have already moved us to UNMAPPED state instead (this happens in
// approximately 0.1% of executions). Accept either state.
CHECK(r->type == base::MallocRange::FREE ||
r->type == base::MallocRange::UNMAPPED);
} else {
CHECK_EQ(r->type, state->expected_type);
}
CHECK_GE(r->length, state->min_size);
state->matched = true;
}
}
// Check that at least one of the callbacks from Ranges() contains
// the specified address with the specified type, and has size
// >= min_size.
static void CheckRangeCallback(void* ptr, base::MallocRange::Type type,
size_t min_size) {
RangeCallbackState state;
state.ptr = reinterpret_cast<uintptr_t>(ptr);
state.expected_type = type;
state.min_size = min_size;
state.matched = false;
MallocExtension::instance()->Ranges(&state, RangeCallback);
CHECK(state.matched);
}
}
static bool HaveSystemRelease =
TCMalloc_SystemRelease(TCMalloc_SystemAlloc(kPageSize, NULL, 0), kPageSize);
static void TestRanges() {
static const int MB = 1048576;
void* a = malloc(MB);
void* b = malloc(MB);
base::MallocRange::Type releasedType =
HaveSystemRelease ? base::MallocRange::UNMAPPED : base::MallocRange::FREE;
CheckRangeCallback(a, base::MallocRange::INUSE, MB);
CheckRangeCallback(b, base::MallocRange::INUSE, MB);
free(a);
CheckRangeCallback(a, base::MallocRange::FREE, MB);
CheckRangeCallback(b, base::MallocRange::INUSE, MB);
MallocExtension::instance()->ReleaseFreeMemory();
CheckRangeCallback(a, releasedType, MB);
CheckRangeCallback(b, base::MallocRange::INUSE, MB);
free(b);
CheckRangeCallback(a, releasedType, MB);
CheckRangeCallback(b, base::MallocRange::FREE, MB);
}
#ifndef DEBUGALLOCATION
static size_t GetUnmappedBytes() {
size_t bytes;
CHECK(MallocExtension::instance()->GetNumericProperty(
"tcmalloc.pageheap_unmapped_bytes", &bytes));
return bytes;
}
#endif
static void TestReleaseToSystem() {
// Debug allocation mode adds overhead to each allocation which
// messes up all the equality tests here. I just disable the
// teset in this mode. TODO(csilvers): get it to work for debugalloc?
#ifndef DEBUGALLOCATION
if(!HaveSystemRelease) return;
const double old_tcmalloc_release_rate = FLAGS_tcmalloc_release_rate;
FLAGS_tcmalloc_release_rate = 0;
static const int MB = 1048576;
void* a = malloc(MB);
void* b = malloc(MB);
MallocExtension::instance()->ReleaseFreeMemory();
size_t starting_bytes = GetUnmappedBytes();
// Calling ReleaseFreeMemory() a second time shouldn't do anything.
MallocExtension::instance()->ReleaseFreeMemory();
EXPECT_EQ(starting_bytes, GetUnmappedBytes());
// ReleaseToSystem shouldn't do anything either.
MallocExtension::instance()->ReleaseToSystem(MB);
EXPECT_EQ(starting_bytes, GetUnmappedBytes());
free(a);
// The span to release should be 1MB.
MallocExtension::instance()->ReleaseToSystem(MB/2);
EXPECT_EQ(starting_bytes + MB, GetUnmappedBytes());
// Should do nothing since the previous call released too much.
MallocExtension::instance()->ReleaseToSystem(MB/4);
EXPECT_EQ(starting_bytes + MB, GetUnmappedBytes());
free(b);
// Use up the extra MB/4 bytes from 'a' and also release 'b'.
MallocExtension::instance()->ReleaseToSystem(MB/2);
EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
// Should do nothing since the previous call released too much.
MallocExtension::instance()->ReleaseToSystem(MB/2);
EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
// Nothing else to release.
MallocExtension::instance()->ReleaseFreeMemory();
EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
a = malloc(MB);
free(a);
EXPECT_EQ(starting_bytes + MB, GetUnmappedBytes());
// Releasing less than a page should still trigger a release.
MallocExtension::instance()->ReleaseToSystem(1);
EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
FLAGS_tcmalloc_release_rate = old_tcmalloc_release_rate;
#endif // #ifndef DEBUGALLOCATION
}
// On MSVC10, in release mode, the optimizer convinces itself
// g_no_memory is never changed (I guess it doesn't realize OnNoMemory
// might be called). Work around this by setting the var volatile.
volatile bool g_no_memory = false;
std::new_handler g_old_handler = NULL;
static void OnNoMemory() {
g_no_memory = true;
std::set_new_handler(g_old_handler);
}
static void TestSetNewMode() {
int old_mode = tc_set_new_mode(1);
g_old_handler = std::set_new_handler(&OnNoMemory);
g_no_memory = false;
void* ret = malloc(kTooBig);
EXPECT_EQ(NULL, ret);
EXPECT_TRUE(g_no_memory);
g_old_handler = std::set_new_handler(&OnNoMemory);
g_no_memory = false;
ret = calloc(1, kTooBig);
EXPECT_EQ(NULL, ret);
EXPECT_TRUE(g_no_memory);
g_old_handler = std::set_new_handler(&OnNoMemory);
g_no_memory = false;
ret = realloc(NULL, kTooBig);
EXPECT_EQ(NULL, ret);
EXPECT_TRUE(g_no_memory);
if (kOSSupportsMemalign) {
// Not really important, but must be small enough such that
// kAlignment + kTooBig does not overflow.
const int kAlignment = 1 << 5;
g_old_handler = std::set_new_handler(&OnNoMemory);
g_no_memory = false;
ret = Memalign(kAlignment, kTooBig);
EXPECT_EQ(NULL, ret);
EXPECT_TRUE(g_no_memory);
g_old_handler = std::set_new_handler(&OnNoMemory);
g_no_memory = false;
EXPECT_EQ(ENOMEM,
PosixMemalign(&ret, kAlignment, kTooBig));
EXPECT_EQ(NULL, ret);
EXPECT_TRUE(g_no_memory);
}
tc_set_new_mode(old_mode);
}
static int RunAllTests(int argc, char** argv) {
// Optional argv[1] is the seed
AllocatorState rnd(argc > 1 ? atoi(argv[1]) : 100);
SetTestResourceLimit();
// TODO(odo): This test has been disabled because it is only by luck that it
// does not result in fragmentation. When tcmalloc makes an allocation which
// spans previously unused leaves of the pagemap it will allocate and fill in
// the leaves to cover the new allocation. The leaves happen to be 256MiB in
// the 64-bit build, and with the sbrk allocator these allocations just
// happen to fit in one leaf by luck. With other allocators (mmap,
// memfs_malloc when used with small pages) the allocations generally span
// two leaves and this results in a very bad fragmentation pattern with this
// code. The same failure can be forced with the sbrk allocator just by
// allocating something on the order of 128MiB prior to starting this test so
// that the test allocations straddle a 256MiB boundary.
// TODO(csilvers): port MemoryUsage() over so the test can use that
#if 0
# include <unistd.h> // for getpid()
// Allocate and deallocate blocks of increasing sizes to check if the alloc
// metadata fragments the memory. (Do not put other allocations/deallocations
// before this test, it may break).
{
size_t memory_usage = MemoryUsage(getpid());
fprintf(LOGSTREAM, "Testing fragmentation\n");
for ( int i = 200; i < 240; ++i ) {
int size = i << 20;
void *test1 = rnd.alloc(size);
CHECK(test1);
for ( int j = 0; j < size; j += (1 << 12) ) {
static_cast<char*>(test1)[j] = 1;
}
free(test1);
}
// There may still be a bit of fragmentation at the beginning, until we
// reach kPageMapBigAllocationThreshold bytes so we check for
// 200 + 240 + margin.
CHECK_LT(MemoryUsage(getpid()), memory_usage + (450 << 20) );
}
#endif
// Check that empty allocation works
fprintf(LOGSTREAM, "Testing empty allocation\n");
{
void* p1 = rnd.alloc(0);
CHECK(p1 != NULL);
void* p2 = rnd.alloc(0);
CHECK(p2 != NULL);
CHECK(p1 != p2);
free(p1);
free(p2);
}
// This code stresses some of the memory allocation via STL.
// It may call operator delete(void*, nothrow_t).
fprintf(LOGSTREAM, "Testing STL use\n");
{
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(0);
std::stable_sort(v.begin(), v.end());
}
// Test each of the memory-allocation functions once, just as a sanity-check
fprintf(LOGSTREAM, "Sanity-testing all the memory allocation functions\n");
{
// We use new-hook and delete-hook to verify we actually called the
// tcmalloc version of these routines, and not the libc version.
SetNewHook(); // defined as part of MAKE_HOOK_CALLBACK, above
SetDeleteHook(); // ditto
void* p1 = malloc(10);
CHECK(p1 != NULL); // force use of this variable
VerifyNewHookWasCalled();
// Also test the non-standard tc_malloc_size
size_t actual_p1_size = tc_malloc_size(p1);
CHECK_GE(actual_p1_size, 10);
CHECK_LT(actual_p1_size, 100000); // a reasonable upper-bound, I think
free(p1);
VerifyDeleteHookWasCalled();
p1 = calloc(10, 2);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
// We make sure we realloc to a big size, since some systems (OS
// X) will notice if the realloced size continues to fit into the
// malloc-block and make this a noop if so.
p1 = realloc(p1, 30000);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
VerifyDeleteHookWasCalled();
cfree(p1); // synonym for free
VerifyDeleteHookWasCalled();
if (kOSSupportsMemalign) {
CHECK_EQ(PosixMemalign(&p1, sizeof(p1), 40), 0);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
free(p1);
VerifyDeleteHookWasCalled();
p1 = Memalign(sizeof(p1) * 2, 50);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
free(p1);
VerifyDeleteHookWasCalled();
}
// Windows has _aligned_malloc. Let's test that that's captured too.
#if (defined(_MSC_VER) || defined(__MINGW32__)) && !defined(PERFTOOLS_NO_ALIGNED_MALLOC)
p1 = _aligned_malloc(sizeof(p1) * 2, 64);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
_aligned_free(p1);
VerifyDeleteHookWasCalled();
#endif
p1 = valloc(60);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
free(p1);
VerifyDeleteHookWasCalled();
p1 = pvalloc(70);
CHECK(p1 != NULL);
VerifyNewHookWasCalled();
free(p1);
VerifyDeleteHookWasCalled();
char* p2 = new char;
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
delete p2;
VerifyDeleteHookWasCalled();
p2 = new char[100];
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
delete[] p2;
VerifyDeleteHookWasCalled();
p2 = new(std::nothrow) char;
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
delete p2;
VerifyDeleteHookWasCalled();
p2 = new(std::nothrow) char[100];
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
delete[] p2;
VerifyDeleteHookWasCalled();
// Another way of calling operator new
p2 = static_cast<char*>(::operator new(100));
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
::operator delete(p2);
VerifyDeleteHookWasCalled();
// Try to call nothrow's delete too. Compilers use this.
p2 = static_cast<char*>(::operator new(100, std::nothrow));
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
::operator delete(p2, std::nothrow);
VerifyDeleteHookWasCalled();
// Try strdup(), which the system allocates but we must free. If
// all goes well, libc will use our malloc!
p2 = strdup("test");
CHECK(p2 != NULL);
VerifyNewHookWasCalled();
free(p2);
VerifyDeleteHookWasCalled();
// Test mmap too: both anonymous mmap and mmap of a file
// Note that for right now we only override mmap on linux
// systems, so those are the only ones for which we check.
SetMmapHook();
SetMremapHook();
SetMunmapHook();
#if defined(HAVE_MMAP) && defined(__linux) && \
(defined(__i386__) || defined(__x86_64__))
int size = 8192*2;
p1 = mmap(NULL, size, PROT_WRITE|PROT_READ, MAP_ANONYMOUS|MAP_PRIVATE,
-1, 0);
CHECK(p1 != NULL);
VerifyMmapHookWasCalled();
p1 = mremap(p1, size, size/2, 0);
CHECK(p1 != NULL);
VerifyMremapHookWasCalled();
size /= 2;
munmap(p1, size);
VerifyMunmapHookWasCalled();
int fd = open("/dev/zero", O_RDONLY);
CHECK_GE(fd, 0); // make sure the open succeeded
p1 = mmap(NULL, 8192, PROT_READ, MAP_SHARED, fd, 0);
CHECK(p1 != NULL);
VerifyMmapHookWasCalled();
munmap(p1, 8192);
VerifyMunmapHookWasCalled();
close(fd);
#else // this is just to quiet the compiler: make sure all fns are called
IncrementCallsToMmapHook();
IncrementCallsToMunmapHook();
IncrementCallsToMremapHook();
VerifyMmapHookWasCalled();
VerifyMremapHookWasCalled();
VerifyMunmapHookWasCalled();
#endif
// Test sbrk
SetSbrkHook();
#if defined(HAVE_SBRK) && defined(__linux) && \
(defined(__i386__) || defined(__x86_64__))
p1 = sbrk(8192);
CHECK(p1 != NULL);
VerifySbrkHookWasCalled();
p1 = sbrk(-8192);
CHECK(p1 != NULL);
VerifySbrkHookWasCalled();
// However, sbrk hook should *not* be called with sbrk(0)
p1 = sbrk(0);
CHECK(p1 != NULL);
CHECK_EQ(g_SbrkHook_calls, 0);
#else // this is just to quiet the compiler: make sure all fns are called
IncrementCallsToSbrkHook();
VerifySbrkHookWasCalled();
#endif
// Reset the hooks to what they used to be. These are all
// defined as part of MAKE_HOOK_CALLBACK, above.
ResetNewHook();
ResetDeleteHook();
ResetMmapHook();
ResetMremapHook();
ResetMunmapHook();
ResetSbrkHook();
}
// Check that "lots" of memory can be allocated
fprintf(LOGSTREAM, "Testing large allocation\n");
{
const int mb_to_allocate = 100;
void* p = rnd.alloc(mb_to_allocate << 20);
CHECK(p != NULL); // could not allocate
free(p);
}
TestMallocAlignment();
// Check calloc() with various arguments
fprintf(LOGSTREAM, "Testing calloc\n");
TestCalloc(0, 0, true);
TestCalloc(0, 1, true);
TestCalloc(1, 1, true);
TestCalloc(1<<10, 0, true);
TestCalloc(1<<20, 0, true);
TestCalloc(0, 1<<10, true);
TestCalloc(0, 1<<20, true);
TestCalloc(1<<20, 2, true);
TestCalloc(2, 1<<20, true);
TestCalloc(1000, 1000, true);
TestCalloc(kMaxSize, 2, false);
TestCalloc(2, kMaxSize, false);
TestCalloc(kMaxSize, kMaxSize, false);
TestCalloc(kMaxSignedSize, 3, false);
TestCalloc(3, kMaxSignedSize, false);
TestCalloc(kMaxSignedSize, kMaxSignedSize, false);
// Test that realloc doesn't always reallocate and copy memory.
fprintf(LOGSTREAM, "Testing realloc\n");
TestRealloc();
fprintf(LOGSTREAM, "Testing operator new(nothrow).\n");
TestNothrowNew(&::operator new);
fprintf(LOGSTREAM, "Testing operator new[](nothrow).\n");
TestNothrowNew(&::operator new[]);
fprintf(LOGSTREAM, "Testing operator new.\n");
TestNew(&::operator new);
fprintf(LOGSTREAM, "Testing operator new[].\n");
TestNew(&::operator new[]);
// Create threads
fprintf(LOGSTREAM, "Testing threaded allocation/deallocation (%d threads)\n",
FLAGS_numthreads);
threads = new TesterThread*[FLAGS_numthreads];
for (int i = 0; i < FLAGS_numthreads; ++i) {
threads[i] = new TesterThread(i);
}
// This runs all the tests at the same time, with a 1M stack size each
RunManyThreadsWithId(RunThread, FLAGS_numthreads, 1<<20);
for (int i = 0; i < FLAGS_numthreads; ++i) delete threads[i]; // Cleanup
// Do the memory intensive tests after threads are done, since exhausting
// the available address space can make pthread_create to fail.
// Check that huge allocations fail with NULL instead of crashing
fprintf(LOGSTREAM, "Testing huge allocations\n");
TestHugeAllocations(&rnd);
// Check that large allocations fail with NULL instead of crashing
#ifndef DEBUGALLOCATION // debug allocation takes forever for huge allocs
fprintf(LOGSTREAM, "Testing out of memory\n");
for (int s = 0; ; s += (10<<20)) {
void* large_object = rnd.alloc(s);
if (large_object == NULL) break;
free(large_object);
}
#endif
TestHugeThreadCache();
TestRanges();
TestReleaseToSystem();
TestSetNewMode();
return 0;
}
}
using testing::RunAllTests;
int main(int argc, char** argv) {
#ifdef DEBUGALLOCATION // debug allocation takes forever for huge allocs
FLAGS_max_free_queue_size = 0; // return freed blocks to tcmalloc immediately
#endif
RunAllTests(argc, argv);
// Test tc_version()
fprintf(LOGSTREAM, "Testing tc_version()\n");
int major;
int minor;
const char* patch;
char mmp[64];
const char* human_version = tc_version(&major, &minor, &patch);
snprintf(mmp, sizeof(mmp), "%d.%d%s", major, minor, patch);
CHECK(!strcmp(PACKAGE_STRING, human_version));
CHECK(!strcmp(PACKAGE_VERSION, mmp));
fprintf(LOGSTREAM, "PASS\n");
}