15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2005, Google Inc.
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved.
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met:
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Redistributions of source code must retain the above copyright
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer.
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Redistributions in binary form must reproduce the above
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the
135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution.
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Neither the name of Google Inc. nor the names of its
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission.
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ---
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Unittest for the TCMalloc implementation.
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * The test consists of a set of threads.
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Each thread maintains a set of allocated objects, with
355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   a bound on the total amount of data in the set.
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Each allocated object's contents are generated by
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   hashing the object pointer, and a generation count
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   in the object.  This allows us to easily check for
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   data corruption.
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * At any given step, the thread can do any of the following:
415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     a. Allocate an object
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     b. Increment an object's generation count and update
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//        its contents.
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     c. Pass the object to another thread
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     d. Free an object
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   Also, at the end of every step, object(s) are freed to maintain
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   the memory upper-bound.
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If this test is compiled with -DDEBUGALLOCATION, then we don't
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// run some tests that test the inner workings of tcmalloc and
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// break on debugallocation: that certain allocations are aligned
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in a certain way (even though no standard requires it), and that
535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// realloc() tries to minimize copying (which debug allocators don't
545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// care about).
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config_for_unittests.h"
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Complicated ordering requirements.  tcmalloc.h defines (indirectly)
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// _POSIX_C_SOURCE, which it needs so stdlib.h defines posix_memalign.
595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// unistd.h, on the other hand, requires _POSIX_C_SOURCE to be unset,
605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// at least on FreeBSD, in order to define sbrk.  The solution
615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is to #include unistd.h first.  This is safe because unistd.h
625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// doesn't sub-include stdlib.h, so we'll still get posix_memalign
635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// when we #include stdlib.h.  Blah.
645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_UNISTD_H
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <unistd.h>        // for testing sbrk hooks
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "tcmalloc.h"      // must come early, to pick up posix_memalign
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h>
695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h>
705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h>
715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined HAVE_STDINT_H
725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdint.h>        // for intptr_t
735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <sys/types.h>     // for size_t
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_FCNTL_H
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <fcntl.h>         // for open; used with mmap-hook test
775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_MMAP
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <sys/mman.h>      // for testing mmap hooks
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_MALLOC_H
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <malloc.h>        // defines pvalloc/etc on cygwin
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <assert.h>
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector>
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm>
875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string>
885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <new>
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h"
905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/simple_mutex.h"
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "gperftools/malloc_hook.h"
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "gperftools/malloc_extension.h"
935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "gperftools/tcmalloc.h"
945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "thread_cache.h"
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "tests/testutil.h"
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Windows doesn't define pvalloc and a few other obsolete unix
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// functions; nor does it define posix_memalign (which is not obsolete).
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(_WIN32)
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define cfree free         // don't bother to try to test these obsolete fns
1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define valloc malloc
1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define pvalloc malloc
1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// I'd like to map posix_memalign to _aligned_malloc, but _aligned_malloc
1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// must be paired with _aligned_free (not normal free), which is too
1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// invasive a change to how we allocate memory here.  So just bail
1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool kOSSupportsMemalign = false;
1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static inline void* Memalign(size_t align, size_t size) {
1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //LOG(FATAL) << "memalign not supported on windows";
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  exit(1);
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return NULL;
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static inline int PosixMemalign(void** ptr, size_t align, size_t size) {
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //LOG(FATAL) << "posix_memalign not supported on windows";
1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  exit(1);
1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return -1;
1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OS X defines posix_memalign in some OS versions but not others;
1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// it's confusing enough to check that it's easiest to just not to test.
1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#elif defined(__APPLE__)
1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool kOSSupportsMemalign = false;
1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static inline void* Memalign(size_t align, size_t size) {
1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //LOG(FATAL) << "memalign not supported on OS X";
1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  exit(1);
1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return NULL;
1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static inline int PosixMemalign(void** ptr, size_t align, size_t size) {
1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //LOG(FATAL) << "posix_memalign not supported on OS X";
1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  exit(1);
1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return -1;
1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else
1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool kOSSupportsMemalign = true;
1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static inline void* Memalign(size_t align, size_t size) {
1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return memalign(align, size);
1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static inline int PosixMemalign(void** ptr, size_t align, size_t size) {
1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return posix_memalign(ptr, align, size);
1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// On systems (like freebsd) that don't define MAP_ANONYMOUS, use the old
1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// form of the name instead.
1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef MAP_ANONYMOUS
1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define MAP_ANONYMOUS MAP_ANON
1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LOGSTREAM   stdout
1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::vector;
1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::string;
1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DECLARE_double(tcmalloc_release_rate);
1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DECLARE_int32(max_free_queue_size);     // in debugallocation.cc
1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DECLARE_int64(tcmalloc_sample_parameter);
1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace testing {
1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_numtests = 50000;
1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_log_every_n_tests = 50000; // log exactly once
1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Testing parameters
1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_lgmaxsize = 16;   // lg() of the max size object to alloc
1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_numthreads = 10;  // Number of threads
1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_threadmb = 4;     // Max memory size allocated by thread
1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_lg_max_memalign = 18; // lg of max alignment for memalign
1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const double FLAGS_memalign_min_fraction = 0;    // min expected%
1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const double FLAGS_memalign_max_fraction = 0.4;  // max expected%
1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const double FLAGS_memalign_max_alignment_ratio = 6;  // alignment/size
1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Weights of different operations
1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_allocweight = 50;    // Weight for picking allocation
1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_freeweight = 50;     // Weight for picking free
1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_updateweight = 10;   // Weight for picking update
1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int FLAGS_passweight = 1;      // Weight for passing object
1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int kSizeBits = 8 * sizeof(size_t);
1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const size_t kMaxSize = ~static_cast<size_t>(0);
1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const size_t kMaxSignedSize = ((size_t(1) << (kSizeBits-1)) - 1);
1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const size_t kNotTooBig = 100000;
1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We want an allocation that is definitely more than main memory.  OS
1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// X has special logic to discard very big allocs before even passing
1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the request along to the user-defined memory allocator; we're not
1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// interested in testing their logic, so we have to make sure we're
1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// not *too* big.
1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const size_t kTooBig = kMaxSize - 100000;
1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int news_handled = 0;
1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Global array of threads
1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TesterThread;
1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static TesterThread** threads;
1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// To help with generating random numbers
1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TestHarness {
2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private:
2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Information kept per type
2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  struct Type {
2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    string      name;
2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    int         type;
2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    int         weight;
2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  };
2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TestHarness(int seed)
2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      : types_(new vector<Type>), total_weight_(0), num_tests_(0) {
2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    srandom(seed);
2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ~TestHarness() {
2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete types_;
2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Add operation type with specified weight.  When starting a new
2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // iteration, an operation type is picked with probability
2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // proportional to its weight.
2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //
2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // "type" must be non-negative.
2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // "weight" must be non-negative.
2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AddType(int type, int weight, const char* name);
2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Call this to get the type of operation for the next iteration.
2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // It returns a random operation type from the set of registered
2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // operations.  Returns -1 if tests should finish.
2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int PickType();
2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // If n == 0, returns the next pseudo-random number in the range [0 .. 0]
2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // If n != 0, returns the next pseudo-random number in the range [0 .. n)
2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int Uniform(int n) {
2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (n == 0) {
2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      return random() * 0;
2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    } else {
2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      return random() % n;
2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Pick "base" uniformly from range [0,max_log] and then return
2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // "base" random bits.  The effect is to pick a number in the range
2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // [0,2^max_log-1] with bias towards smaller numbers.
2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int Skewed(int max_log) {
2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int base = random() % (max_log+1);
2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return random() % (1 << base);
2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private:
2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  vector<Type>*         types_;         // Registered types
2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int                   total_weight_;  // Total weight of all types
2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int                   num_tests_;     // Num tests run so far
2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void TestHarness::AddType(int type, int weight, const char* name) {
2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Type t;
2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  t.name = name;
2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  t.type = type;
2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  t.weight = weight;
2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  types_->push_back(t);
2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  total_weight_ += weight;
2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int TestHarness::PickType() {
2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (num_tests_ >= FLAGS_numtests) return -1;
2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  num_tests_++;
2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  assert(total_weight_ > 0);
2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // This is a little skewed if total_weight_ doesn't divide 2^31, but it's close
2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int v = Uniform(total_weight_);
2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int i;
2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (i = 0; i < types_->size(); i++) {
2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    v -= (*types_)[i].weight;
2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (v < 0) {
2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      break;
2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  assert(i < types_->size());
2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if ((num_tests_ % FLAGS_log_every_n_tests) == 0) {
2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "  Test %d out of %d: %s\n",
2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            num_tests_, FLAGS_numtests, (*types_)[i].name.c_str());
2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return (*types_)[i].type;
2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class AllocatorState : public TestHarness {
2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  explicit AllocatorState(int seed) : TestHarness(seed), memalign_fraction_(0) {
2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (kOSSupportsMemalign) {
2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_GE(FLAGS_memalign_max_fraction, 0);
2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_LE(FLAGS_memalign_max_fraction, 1);
2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_GE(FLAGS_memalign_min_fraction, 0);
2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_LE(FLAGS_memalign_min_fraction, 1);
2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      double delta = FLAGS_memalign_max_fraction - FLAGS_memalign_min_fraction;
2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_GE(delta, 0);
2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      memalign_fraction_ = (Uniform(10000)/10000.0 * delta +
2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                            FLAGS_memalign_min_fraction);
2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      //fprintf(LOGSTREAM, "memalign fraction: %f\n", memalign_fraction_);
2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  virtual ~AllocatorState() {}
3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Allocate memory.  Randomly choose between malloc() or posix_memalign().
3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* alloc(size_t size) {
3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (Uniform(100) < memalign_fraction_ * 100) {
3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // Try a few times to find a reasonable alignment, or fall back on malloc.
3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      for (int i = 0; i < 5; i++) {
3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        size_t alignment = 1 << Uniform(FLAGS_lg_max_memalign);
3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        if (alignment >= sizeof(intptr_t) &&
3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            (size < sizeof(intptr_t) ||
3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             alignment < FLAGS_memalign_max_alignment_ratio * size)) {
3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          void *result = reinterpret_cast<void*>(static_cast<intptr_t>(0x1234));
3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          int err = PosixMemalign(&result, alignment, size);
3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          if (err != 0) {
3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            CHECK_EQ(err, ENOMEM);
3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          }
3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          return err == 0 ? result : NULL;
3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        }
3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      }
3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return malloc(size);
3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private:
3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  double memalign_fraction_;
3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Info kept per thread
3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TesterThread {
3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private:
3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Info kept per allocated object
3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  struct Object {
3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    char*       ptr;                    // Allocated pointer
3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    int         size;                   // Allocated size
3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    int         generation;             // Generation counter of object contents
3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  };
3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Mutex                 lock_;          // For passing in another thread's obj
3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int                   id_;            // My thread id
3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  AllocatorState        rnd_;           // For generating random numbers
3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  vector<Object>        heap_;          // This thread's heap
3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  vector<Object>        passed_;        // Pending objects passed from others
3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t                heap_size_;     // Current heap size
3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int                   locks_ok_;      // Number of OK TryLock() ops
3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int                   locks_failed_;  // Number of failed TryLock() ops
3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Type of operations
3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  enum Type { ALLOC, FREE, UPDATE, PASS };
3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // ACM minimal standard random number generator.  (re-entrant.)
3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  class ACMRandom {
3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    int32 seed_;
3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)   public:
3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    explicit ACMRandom(int32 seed) { seed_ = seed; }
3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    int32 Next() {
3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      const int32 M = 2147483647L;   // 2^31-1
3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      const int32 A = 16807;
3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // In effect, we are computing seed_ = (seed_ * A) % M, where M = 2^31-1
3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      uint32 lo = A * (int32)(seed_ & 0xFFFF);
3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      uint32 hi = A * (int32)((uint32)seed_ >> 16);
3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      lo += (hi & 0x7FFF) << 16;
3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      if (lo > M) {
3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        lo &= M;
3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        ++lo;
3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      }
3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      lo += hi >> 15;
3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      if (lo > M) {
3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        lo &= M;
3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        ++lo;
3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      }
3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      return (seed_ = (int32) lo);
3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  };
3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TesterThread(int id)
3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    : id_(id),
3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      rnd_(id+1),
3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      heap_size_(0),
3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      locks_ok_(0),
3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      locks_failed_(0) {
3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  virtual ~TesterThread() {
3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (FLAGS_verbose)
3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      fprintf(LOGSTREAM, "Thread %2d: locks %6d ok; %6d trylocks failed\n",
3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)              id_, locks_ok_, locks_failed_);
3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (locks_ok_ + locks_failed_ >= 1000) {
3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_LE(locks_failed_, locks_ok_ / 2);
3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  virtual void Run() {
3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    rnd_.AddType(ALLOC,  FLAGS_allocweight,   "allocate");
3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    rnd_.AddType(FREE,   FLAGS_freeweight,    "free");
3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    rnd_.AddType(UPDATE, FLAGS_updateweight,  "update");
3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    rnd_.AddType(PASS,   FLAGS_passweight,    "pass");
3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    while (true) {
4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      AcquirePassedObjects();
4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      switch (rnd_.PickType()) {
4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        case ALLOC:   AllocateObject(); break;
4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        case FREE:    FreeObject();     break;
4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        case UPDATE:  UpdateObject();   break;
4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        case PASS:    PassObject();     break;
4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        case -1:      goto done;
4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        default:      assert(NULL == "Unknown type");
4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      }
4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      ShrinkHeap();
4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) done:
4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    DeleteHeap();
4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Allocate a new object
4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AllocateObject() {
4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Object object;
4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    object.size = rnd_.Skewed(FLAGS_lgmaxsize);
4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    object.ptr = static_cast<char*>(rnd_.alloc(object.size));
4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(object.ptr);
4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    object.generation = 0;
4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    FillContents(&object);
4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    heap_.push_back(object);
4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    heap_size_ += object.size;
4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Mutate a random object
4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void UpdateObject() {
4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (heap_.empty()) return;
4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int index = rnd_.Uniform(heap_.size());
4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CheckContents(heap_[index]);
4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    heap_[index].generation++;
4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    FillContents(&heap_[index]);
4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Free a random object
4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void FreeObject() {
4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (heap_.empty()) return;
4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int index = rnd_.Uniform(heap_.size());
4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Object object = heap_[index];
4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CheckContents(object);
4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    free(object.ptr);
4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    heap_size_ -= object.size;
4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    heap_[index] = heap_[heap_.size()-1];
4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    heap_.pop_back();
4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Delete all objects in the heap
4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void DeleteHeap() {
4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    while (!heap_.empty()) {
4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      FreeObject();
4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Free objects until our heap is small enough
4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void ShrinkHeap() {
4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    while (heap_size_ > FLAGS_threadmb << 20) {
4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      assert(!heap_.empty());
4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      FreeObject();
4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Pass a random object to another thread
4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void PassObject() {
4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // Pick object to pass
4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (heap_.empty()) return;
4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int index = rnd_.Uniform(heap_.size());
4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Object object = heap_[index];
4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CheckContents(object);
4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // Pick thread to pass
4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int tid = rnd_.Uniform(FLAGS_numthreads);
4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TesterThread* thread = threads[tid];
4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (thread->lock_.TryLock()) {
4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // Pass the object
4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      locks_ok_++;
4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      thread->passed_.push_back(object);
4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      thread->lock_.Unlock();
4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      heap_size_ -= object.size;
4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      heap_[index] = heap_[heap_.size()-1];
4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      heap_.pop_back();
4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    } else {
4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      locks_failed_++;
4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Grab any objects passed to this thread by another thread
4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AcquirePassedObjects() {
4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // We do not create unnecessary contention by always using
4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // TryLock().  Plus we unlock immediately after swapping passed
4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // objects into a local vector.
4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    vector<Object> copy;
4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    { // Locking scope
4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      if (!lock_.TryLock()) {
4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        locks_failed_++;
5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        return;
5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      }
5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      locks_ok_++;
5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      swap(copy, passed_);
5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      lock_.Unlock();
5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 0; i < copy.size(); ++i) {
5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      const Object& object = copy[i];
5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CheckContents(object);
5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      heap_.push_back(object);
5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      heap_size_ += object.size;
5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Fill object contents according to ptr/generation
5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void FillContents(Object* object) {
5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ACMRandom r(reinterpret_cast<intptr_t>(object->ptr) & 0x7fffffff);
5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 0; i < object->generation; ++i) {
5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      r.Next();
5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const char c = static_cast<char>(r.Next());
5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    memset(object->ptr, c, object->size);
5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Check object contents
5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void CheckContents(const Object& object) {
5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ACMRandom r(reinterpret_cast<intptr_t>(object.ptr) & 0x7fffffff);
5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 0; i < object.generation; ++i) {
5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      r.Next();
5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // For large objects, we just check a prefix/suffix
5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const char expected = static_cast<char>(r.Next());
5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int limit1 = object.size < 32 ? object.size : 32;
5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int start2 = limit1 > object.size - 32 ? limit1 : object.size - 32;
5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 0; i < limit1; ++i) {
5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(object.ptr[i], expected);
5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = start2; i < object.size; ++i) {
5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(object.ptr[i], expected);
5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void RunThread(int thread_id) {
5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  threads[thread_id]->Run();
5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TryHugeAllocation(size_t s, AllocatorState* rnd) {
5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* p = rnd->alloc(s);
5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(p == NULL);   // huge allocation s should fail!
5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestHugeAllocations(AllocatorState* rnd) {
5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Check that asking for stuff tiny bit smaller than largest possible
5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // size returns NULL.
5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (size_t i = 0; i < 70000; i += rnd->Uniform(20)) {
5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TryHugeAllocation(kMaxSize - i, rnd);
5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Asking for memory sizes near signed/unsigned boundary (kMaxSignedSize)
5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // might work or not, depending on the amount of virtual memory.
5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUGALLOCATION    // debug allocation takes forever for huge allocs
5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (size_t i = 0; i < 100; i++) {
5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    void* p = NULL;
5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    p = rnd->alloc(kMaxSignedSize + i);
5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (p) free(p);    // if: free(NULL) is not necessarily defined
5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    p = rnd->alloc(kMaxSignedSize - i);
5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (p) free(p);
5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Check that ReleaseFreeMemory has no visible effect (aka, does not
5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // crash the test):
5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension* inst = MallocExtension::instance();
5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(inst);
5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inst->ReleaseFreeMemory();
5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestCalloc(size_t n, size_t s, bool ok) {
5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  char* p = reinterpret_cast<char*>(calloc(n, s));
5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (FLAGS_verbose)
5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "calloc(%"PRIxS", %"PRIxS"): %p\n", n, s, p);
5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (!ok) {
5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(p == NULL);  // calloc(n, s) should not succeed
5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } else {
5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(p != NULL);  // calloc(n, s) should succeed
5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int i = 0; i < n*s; i++) {
5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK(p[i] == '\0');
5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    free(p);
5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This makes sure that reallocing a small number of bytes in either
5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// direction doesn't cause us to allocate new memory.
5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestRealloc() {
5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUGALLOCATION  // debug alloc doesn't try to minimize reallocs
5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // When sampling, we always allocate in units of page-size, which
5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // makes reallocs of small sizes do extra work (thus, failing these
6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // checks).  Since sampling is random, we turn off sampling to make
6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // sure that doesn't happen to us here.
6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const int64 old_sample_parameter = FLAGS_tcmalloc_sample_parameter;
6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  FLAGS_tcmalloc_sample_parameter = 0;   // turn off sampling
6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int start_sizes[] = { 100, 1000, 10000, 100000 };
6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int deltas[] = { 1, -2, 4, -8, 16, -32, 64, -128 };
6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int s = 0; s < sizeof(start_sizes)/sizeof(*start_sizes); ++s) {
6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    void* p = malloc(start_sizes[s]);
6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(p);
6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // The larger the start-size, the larger the non-reallocing delta.
6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int d = 0; d < (s+1) * 2; ++d) {
6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      void* new_p = realloc(p, start_sizes[s] + deltas[d]);
6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK(p == new_p);  // realloc should not allocate new memory
6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // Test again, but this time reallocing smaller first.
6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (int d = 0; d < s*2; ++d) {
6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      void* new_p = realloc(p, start_sizes[s] - deltas[d]);
6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK(p == new_p);  // realloc should not allocate new memory
6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    free(p);
6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  FLAGS_tcmalloc_sample_parameter = old_sample_parameter;
6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestNewHandler() throw (std::bad_alloc) {
6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++news_handled;
6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  throw std::bad_alloc();
6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestOneNew(void* (*func)(size_t)) {
6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // success test
6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  try {
6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    void* ptr = (*func)(kNotTooBig);
6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (0 == ptr) {
6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      fprintf(LOGSTREAM, "allocation should not have failed.\n");
6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      abort();
6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } catch (...) {
6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "allocation threw unexpected exception.\n");
6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // failure test
6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // we should always receive a bad_alloc exception
6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  try {
6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    (*func)(kTooBig);
6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "allocation should have failed.\n");
6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } catch (const std::bad_alloc&) {
6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // correct
6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } catch (...) {
6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "allocation threw unexpected exception.\n");
6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestNew(void* (*func)(size_t)) {
6605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  news_handled = 0;
6615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // test without new_handler:
6635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::new_handler saved_handler = std::set_new_handler(0);
6645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TestOneNew(func);
6655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // test with new_handler:
6675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::set_new_handler(TestNewHandler);
6685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TestOneNew(func);
6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (news_handled != 1) {
6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "new_handler was not called.\n");
6715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
6725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::set_new_handler(saved_handler);
6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestOneNothrowNew(void* (*func)(size_t, const std::nothrow_t&)) {
6775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // success test
6785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  try {
6795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    void* ptr = (*func)(kNotTooBig, std::nothrow);
6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (0 == ptr) {
6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      fprintf(LOGSTREAM, "allocation should not have failed.\n");
6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      abort();
6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } catch (...) {
6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "allocation threw unexpected exception.\n");
6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // failure test
6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // we should always receive a bad_alloc exception
6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  try {
6925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if ((*func)(kTooBig, std::nothrow) != 0) {
6935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      fprintf(LOGSTREAM, "allocation should have failed.\n");
6945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      abort();
6955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
6965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } catch (...) {
6975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "nothrow allocation threw unexpected exception.\n");
6985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
6995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestNothrowNew(void* (*func)(size_t, const std::nothrow_t&)) {
7035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  news_handled = 0;
7045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // test without new_handler:
7065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::new_handler saved_handler = std::set_new_handler(0);
7075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TestOneNothrowNew(func);
7085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // test with new_handler:
7105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::set_new_handler(TestNewHandler);
7115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TestOneNothrowNew(func);
7125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (news_handled != 1) {
7135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(LOGSTREAM, "nothrow new_handler was not called.\n");
7145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    abort();
7155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::set_new_handler(saved_handler);
7175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// These are used as callbacks by the sanity-check.  Set* and Reset*
7215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// register the hook that counts how many times the associated memory
7225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// function is called.  After each such call, call Verify* to verify
7235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that we used the tcmalloc version of the call, and not the libc.
7245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note the ... in the hook signature: we don't care what arguments
7255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the hook takes.
7265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MAKE_HOOK_CALLBACK(hook_type)                                   \
7275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static int g_##hook_type##_calls = 0;                                 \
7285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void IncrementCallsTo##hook_type(...) {                        \
7295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    g_##hook_type##_calls++;                                            \
7305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }                                                                     \
7315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Verify##hook_type##WasCalled() {                          \
7325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_GT(g_##hook_type##_calls, 0);                                 \
7335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    g_##hook_type##_calls = 0;  /* reset for next call */               \
7345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }                                                                     \
7355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Set##hook_type() {                                        \
7365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(MallocHook::Add##hook_type(                                   \
7375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        (MallocHook::hook_type)&IncrementCallsTo##hook_type));          \
7385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }                                                                     \
7395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Reset##hook_type() {                                      \
7405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(MallocHook::Remove##hook_type(                                \
7415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)        (MallocHook::hook_type)&IncrementCallsTo##hook_type));          \
7425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We do one for each hook typedef in malloc_hook.h
7455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MAKE_HOOK_CALLBACK(NewHook);
7465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MAKE_HOOK_CALLBACK(DeleteHook);
7475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MAKE_HOOK_CALLBACK(MmapHook);
7485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MAKE_HOOK_CALLBACK(MremapHook);
7495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MAKE_HOOK_CALLBACK(MunmapHook);
7505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MAKE_HOOK_CALLBACK(SbrkHook);
7515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestAlignmentForSize(int size) {
7535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  fprintf(LOGSTREAM, "Testing alignment of malloc(%d)\n", size);
7545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const int kNum = 100;
7555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* ptrs[kNum];
7565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < kNum; i++) {
7575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ptrs[i] = malloc(size);
7585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    uintptr_t p = reinterpret_cast<uintptr_t>(ptrs[i]);
7595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK((p % sizeof(void*)) == 0);
7605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK((p % sizeof(double)) == 0);
7615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // Must have 16-byte alignment for large enough objects
7635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (size >= 16) {
7645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK((p % 16) == 0);
7655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
7665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < kNum; i++) {
7685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    free(ptrs[i]);
7695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestMallocAlignment() {
7735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int lg = 0; lg < 16; lg++) {
7745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TestAlignmentForSize((1<<lg) - 1);
7755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TestAlignmentForSize((1<<lg) + 0);
7765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TestAlignmentForSize((1<<lg) + 1);
7775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestHugeThreadCache() {
7815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  fprintf(LOGSTREAM, "==== Testing huge thread cache\n");
7825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // More than 2^16 to cause integer overflow of 16 bit counters.
7835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const int kNum = 70000;
7845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  char** array = new char*[kNum];
7855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < kNum; ++i) {
7865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    array[i] = new char[10];
7875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < kNum; ++i) {
7895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete[] array[i];
7905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete[] array;
7925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace {
7955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct RangeCallbackState {
7975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  uintptr_t ptr;
7985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  base::MallocRange::Type expected_type;
7995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t min_size;
8005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  bool matched;
8015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
8025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void RangeCallback(void* arg, const base::MallocRange* r) {
8045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RangeCallbackState* state = reinterpret_cast<RangeCallbackState*>(arg);
8055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (state->ptr >= r->address &&
8065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      state->ptr < r->address + r->length) {
8075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (state->expected_type == base::MallocRange::FREE) {
8085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // We are expecting r->type == FREE, but ReleaseMemory
8095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // may have already moved us to UNMAPPED state instead (this happens in
8105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      // approximately 0.1% of executions). Accept either state.
8115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK(r->type == base::MallocRange::FREE ||
8125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            r->type == base::MallocRange::UNMAPPED);
8135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    } else {
8145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(r->type, state->expected_type);
8155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
8165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_GE(r->length, state->min_size);
8175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    state->matched = true;
8185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Check that at least one of the callbacks from Ranges() contains
8225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the specified address with the specified type, and has size
8235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// >= min_size.
8245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void CheckRangeCallback(void* ptr, base::MallocRange::Type type,
8255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                               size_t min_size) {
8265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RangeCallbackState state;
8275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  state.ptr = reinterpret_cast<uintptr_t>(ptr);
8285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  state.expected_type = type;
8295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  state.min_size = min_size;
8305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  state.matched = false;
8315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->Ranges(&state, RangeCallback);
8325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(state.matched);
8335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestRanges() {
8385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const int MB = 1048576;
8395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* a = malloc(MB);
8405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* b = malloc(MB);
8415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(a, base::MallocRange::INUSE, MB);
8425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(b, base::MallocRange::INUSE, MB);
8435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  free(a);
8445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(a, base::MallocRange::FREE, MB);
8455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(b, base::MallocRange::INUSE, MB);
8465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseFreeMemory();
8475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(a, base::MallocRange::UNMAPPED, MB);
8485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(b, base::MallocRange::INUSE, MB);
8495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  free(b);
8505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(a, base::MallocRange::UNMAPPED, MB);
8515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CheckRangeCallback(b, base::MallocRange::FREE, MB);
8525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUGALLOCATION
8555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static size_t GetUnmappedBytes() {
8565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t bytes;
8575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(MallocExtension::instance()->GetNumericProperty(
8585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      "tcmalloc.pageheap_unmapped_bytes", &bytes));
8595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return bytes;
8605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
8625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestReleaseToSystem() {
8645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Debug allocation mode adds overhead to each allocation which
8655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // messes up all the equality tests here.  I just disable the
8665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // teset in this mode.  TODO(csilvers): get it to work for debugalloc?
8675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUGALLOCATION
8685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const double old_tcmalloc_release_rate = FLAGS_tcmalloc_release_rate;
8695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  FLAGS_tcmalloc_release_rate = 0;
8705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const int MB = 1048576;
8725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* a = malloc(MB);
8735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* b = malloc(MB);
8745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseFreeMemory();
8755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  size_t starting_bytes = GetUnmappedBytes();
8765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Calling ReleaseFreeMemory() a second time shouldn't do anything.
8785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseFreeMemory();
8795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes, GetUnmappedBytes());
8805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // ReleaseToSystem shouldn't do anything either.
8825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseToSystem(MB);
8835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes, GetUnmappedBytes());
8845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  free(a);
8865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // The span to release should be 1MB.
8885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseToSystem(MB/2);
8895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + MB, GetUnmappedBytes());
8905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Should do nothing since the previous call released too much.
8925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseToSystem(MB/4);
8935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + MB, GetUnmappedBytes());
8945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  free(b);
8965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Use up the extra MB/4 bytes from 'a' and also release 'b'.
8985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseToSystem(MB/2);
8995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
9005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Should do nothing since the previous call released too much.
9025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseToSystem(MB/2);
9035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
9045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Nothing else to release.
9065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseFreeMemory();
9075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
9085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  a = malloc(MB);
9105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  free(a);
9115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + MB, GetUnmappedBytes());
9125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Releasing less than a page should still trigger a release.
9145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MallocExtension::instance()->ReleaseToSystem(1);
9155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(starting_bytes + 2*MB, GetUnmappedBytes());
9165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  FLAGS_tcmalloc_release_rate = old_tcmalloc_release_rate;
9185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif   // #ifndef DEBUGALLOCATION
9195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// On MSVC10, in release mode, the optimizer convinces itself
9225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// g_no_memory is never changed (I guess it doesn't realize OnNoMemory
9235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// might be called).  Work around this by setting the var volatile.
9245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)volatile bool g_no_memory = false;
9255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)std::new_handler g_old_handler = NULL;
9265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void OnNoMemory() {
9275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_no_memory = true;
9285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::set_new_handler(g_old_handler);
9295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void TestSetNewMode() {
9325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int old_mode = tc_set_new_mode(1);
9335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_old_handler = std::set_new_handler(&OnNoMemory);
9355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_no_memory = false;
9365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* ret = malloc(kTooBig);
9375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(NULL, ret);
9385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(g_no_memory);
9395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_old_handler = std::set_new_handler(&OnNoMemory);
9415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_no_memory = false;
9425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ret = calloc(1, kTooBig);
9435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(NULL, ret);
9445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(g_no_memory);
9455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_old_handler = std::set_new_handler(&OnNoMemory);
9475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  g_no_memory = false;
9485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ret = realloc(NULL, kTooBig);
9495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_EQ(NULL, ret);
9505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  EXPECT_TRUE(g_no_memory);
9515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (kOSSupportsMemalign) {
9535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // Not really important, but must be small enough such that
9545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // kAlignment + kTooBig does not overflow.
9555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const int kAlignment = 1 << 5;
9565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    g_old_handler = std::set_new_handler(&OnNoMemory);
9585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    g_no_memory = false;
9595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ret = Memalign(kAlignment, kTooBig);
9605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(NULL, ret);
9615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(g_no_memory);
9625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    g_old_handler = std::set_new_handler(&OnNoMemory);
9645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    g_no_memory = false;
9655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(ENOMEM,
9665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)              PosixMemalign(&ret, kAlignment, kTooBig));
9675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_EQ(NULL, ret);
9685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    EXPECT_TRUE(g_no_memory);
9695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  tc_set_new_mode(old_mode);
9725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int RunAllTests(int argc, char** argv) {
9755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Optional argv[1] is the seed
9765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  AllocatorState rnd(argc > 1 ? atoi(argv[1]) : 100);
9775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetTestResourceLimit();
9795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // TODO(odo):  This test has been disabled because it is only by luck that it
9815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // does not result in fragmentation.  When tcmalloc makes an allocation which
9825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // spans previously unused leaves of the pagemap it will allocate and fill in
9835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // the leaves to cover the new allocation.  The leaves happen to be 256MiB in
9845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // the 64-bit build, and with the sbrk allocator these allocations just
9855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // happen to fit in one leaf by luck.  With other allocators (mmap,
9865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // memfs_malloc when used with small pages) the allocations generally span
9875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // two leaves and this results in a very bad fragmentation pattern with this
9885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // code.  The same failure can be forced with the sbrk allocator just by
9895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // allocating something on the order of 128MiB prior to starting this test so
9905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // that the test allocations straddle a 256MiB boundary.
9915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // TODO(csilvers): port MemoryUsage() over so the test can use that
9935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if 0
9945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# include <unistd.h>      // for getpid()
9955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Allocate and deallocate blocks of increasing sizes to check if the alloc
9965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // metadata fragments the memory. (Do not put other allocations/deallocations
9975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // before this test, it may break).
998