third_party/tcmalloc/chromium/src/tests/tcmalloc

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
Memalign
PosixMemalign
Memalign
PosixMemalign
Memalign
PosixMemalign
num_tests_
Uniform
Skewed
AddType
PickType
memalign_fraction_
alloc
Next
locks_failed_
Run
AllocateObject
UpdateObject
FreeObject
DeleteHeap
ShrinkHeap
PassObject
AcquirePassedObjects
FillContents
CheckContents
RunThread
TryHugeAllocation
TestHugeAllocations
TestCalloc
TestRealloc
TestNewHandler
TestOneNew
TestNew
TestOneNothrowNew
TestNothrowNew
TestAlignmentForSize
TestMallocAlignment
TestHugeThreadCache
RangeCallback
CheckRangeCallback
TestRanges
GetUnmappedBytes
TestReleaseToSystem
OnNoMemory
TestSetNewMode
RunAllTests
main
// 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 "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 alignment for large enough objects
    if (size >= 16) {
      CHECK((p % 16) == 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 void TestRanges() {
  static const int MB = 1048576;
  void* a = malloc(MB);
  void* b = malloc(MB);
  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, base::MallocRange::UNMAPPED, MB);
  CheckRangeCallback(b, base::MallocRange::INUSE, MB);
  free(b);
  CheckRangeCallback(a, base::MallocRange::UNMAPPED, 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
  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");
}
/* [<][>][^][v][top][bottom][index][help] */
root/third_party/tcmalloc/chromium/src/tests/tcmalloc_unittest.cc

DEFINITIONS
