1//===-- sanitizer_allocator_test.cc ---------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of ThreadSanitizer/AddressSanitizer runtime.
11// Tests for sanitizer_allocator.h.
12//
13//===----------------------------------------------------------------------===//
14#include "sanitizer_common/sanitizer_allocator.h"
15#include "sanitizer_common/sanitizer_allocator_internal.h"
16#include "sanitizer_common/sanitizer_common.h"
17
18#include "sanitizer_test_utils.h"
19#include "sanitizer_pthread_wrappers.h"
20
21#include "gtest/gtest.h"
22
23#include <stdlib.h>
24#include <algorithm>
25#include <vector>
26#include <set>
27
28// Too slow for debug build
29#if !SANITIZER_DEBUG
30
31#if SANITIZER_CAN_USE_ALLOCATOR64
32static const uptr kAllocatorSpace = 0x700000000000ULL;
33static const uptr kAllocatorSize  = 0x010000000000ULL;  // 1T.
34static const u64 kAddressSpaceSize = 1ULL << 47;
35
36typedef SizeClassAllocator64<
37  kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap> Allocator64;
38
39typedef SizeClassAllocator64<
40  kAllocatorSpace, kAllocatorSize, 16, CompactSizeClassMap> Allocator64Compact;
41#elif defined(__mips64)
42static const u64 kAddressSpaceSize = 1ULL << 40;
43#elif defined(__aarch64__)
44static const u64 kAddressSpaceSize = 1ULL << 39;
45#else
46static const u64 kAddressSpaceSize = 1ULL << 32;
47#endif
48
49static const uptr kRegionSizeLog = FIRST_32_SECOND_64(20, 24);
50static const uptr kFlatByteMapSize = kAddressSpaceSize >> kRegionSizeLog;
51
52typedef SizeClassAllocator32<
53  0, kAddressSpaceSize,
54  /*kMetadataSize*/16,
55  CompactSizeClassMap,
56  kRegionSizeLog,
57  FlatByteMap<kFlatByteMapSize> >
58  Allocator32Compact;
59
60template <class SizeClassMap>
61void TestSizeClassMap() {
62  typedef SizeClassMap SCMap;
63  // SCMap::Print();
64  SCMap::Validate();
65}
66
67TEST(SanitizerCommon, DefaultSizeClassMap) {
68  TestSizeClassMap<DefaultSizeClassMap>();
69}
70
71TEST(SanitizerCommon, CompactSizeClassMap) {
72  TestSizeClassMap<CompactSizeClassMap>();
73}
74
75TEST(SanitizerCommon, InternalSizeClassMap) {
76  TestSizeClassMap<InternalSizeClassMap>();
77}
78
79template <class Allocator>
80void TestSizeClassAllocator() {
81  Allocator *a = new Allocator;
82  a->Init();
83  SizeClassAllocatorLocalCache<Allocator> cache;
84  memset(&cache, 0, sizeof(cache));
85  cache.Init(0);
86
87  static const uptr sizes[] = {1, 16, 30, 40, 100, 1000, 10000,
88    50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000};
89
90  std::vector<void *> allocated;
91
92  uptr last_total_allocated = 0;
93  for (int i = 0; i < 3; i++) {
94    // Allocate a bunch of chunks.
95    for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) {
96      uptr size = sizes[s];
97      if (!a->CanAllocate(size, 1)) continue;
98      // printf("s = %ld\n", size);
99      uptr n_iter = std::max((uptr)6, 4000000 / size);
100      // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter);
101      for (uptr i = 0; i < n_iter; i++) {
102        uptr class_id0 = Allocator::SizeClassMapT::ClassID(size);
103        char *x = (char*)cache.Allocate(a, class_id0);
104        x[0] = 0;
105        x[size - 1] = 0;
106        x[size / 2] = 0;
107        allocated.push_back(x);
108        CHECK_EQ(x, a->GetBlockBegin(x));
109        CHECK_EQ(x, a->GetBlockBegin(x + size - 1));
110        CHECK(a->PointerIsMine(x));
111        CHECK(a->PointerIsMine(x + size - 1));
112        CHECK(a->PointerIsMine(x + size / 2));
113        CHECK_GE(a->GetActuallyAllocatedSize(x), size);
114        uptr class_id = a->GetSizeClass(x);
115        CHECK_EQ(class_id, Allocator::SizeClassMapT::ClassID(size));
116        uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x));
117        metadata[0] = reinterpret_cast<uptr>(x) + 1;
118        metadata[1] = 0xABCD;
119      }
120    }
121    // Deallocate all.
122    for (uptr i = 0; i < allocated.size(); i++) {
123      void *x = allocated[i];
124      uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x));
125      CHECK_EQ(metadata[0], reinterpret_cast<uptr>(x) + 1);
126      CHECK_EQ(metadata[1], 0xABCD);
127      cache.Deallocate(a, a->GetSizeClass(x), x);
128    }
129    allocated.clear();
130    uptr total_allocated = a->TotalMemoryUsed();
131    if (last_total_allocated == 0)
132      last_total_allocated = total_allocated;
133    CHECK_EQ(last_total_allocated, total_allocated);
134  }
135
136  // Check that GetBlockBegin never crashes.
137  for (uptr x = 0, step = kAddressSpaceSize / 100000;
138       x < kAddressSpaceSize - step; x += step)
139    if (a->PointerIsMine(reinterpret_cast<void *>(x)))
140      Ident(a->GetBlockBegin(reinterpret_cast<void *>(x)));
141
142  a->TestOnlyUnmap();
143  delete a;
144}
145
146#if SANITIZER_CAN_USE_ALLOCATOR64
147TEST(SanitizerCommon, SizeClassAllocator64) {
148  TestSizeClassAllocator<Allocator64>();
149}
150
151TEST(SanitizerCommon, SizeClassAllocator64Compact) {
152  TestSizeClassAllocator<Allocator64Compact>();
153}
154#endif
155
156TEST(SanitizerCommon, SizeClassAllocator32Compact) {
157  TestSizeClassAllocator<Allocator32Compact>();
158}
159
160template <class Allocator>
161void SizeClassAllocatorMetadataStress() {
162  Allocator *a = new Allocator;
163  a->Init();
164  SizeClassAllocatorLocalCache<Allocator> cache;
165  memset(&cache, 0, sizeof(cache));
166  cache.Init(0);
167
168  const uptr kNumAllocs = 1 << 13;
169  void *allocated[kNumAllocs];
170  void *meta[kNumAllocs];
171  for (uptr i = 0; i < kNumAllocs; i++) {
172    void *x = cache.Allocate(a, 1 + i % 50);
173    allocated[i] = x;
174    meta[i] = a->GetMetaData(x);
175  }
176  // Get Metadata kNumAllocs^2 times.
177  for (uptr i = 0; i < kNumAllocs * kNumAllocs; i++) {
178    uptr idx = i % kNumAllocs;
179    void *m = a->GetMetaData(allocated[idx]);
180    EXPECT_EQ(m, meta[idx]);
181  }
182  for (uptr i = 0; i < kNumAllocs; i++) {
183    cache.Deallocate(a, 1 + i % 50, allocated[i]);
184  }
185
186  a->TestOnlyUnmap();
187  delete a;
188}
189
190#if SANITIZER_CAN_USE_ALLOCATOR64
191TEST(SanitizerCommon, SizeClassAllocator64MetadataStress) {
192  SizeClassAllocatorMetadataStress<Allocator64>();
193}
194
195TEST(SanitizerCommon, SizeClassAllocator64CompactMetadataStress) {
196  SizeClassAllocatorMetadataStress<Allocator64Compact>();
197}
198#endif  // SANITIZER_CAN_USE_ALLOCATOR64
199TEST(SanitizerCommon, SizeClassAllocator32CompactMetadataStress) {
200  SizeClassAllocatorMetadataStress<Allocator32Compact>();
201}
202
203template <class Allocator>
204void SizeClassAllocatorGetBlockBeginStress() {
205  Allocator *a = new Allocator;
206  a->Init();
207  SizeClassAllocatorLocalCache<Allocator> cache;
208  memset(&cache, 0, sizeof(cache));
209  cache.Init(0);
210
211  uptr max_size_class = Allocator::kNumClasses - 1;
212  uptr size = Allocator::SizeClassMapT::Size(max_size_class);
213  u64 G8 = 1ULL << 33;
214  // Make sure we correctly compute GetBlockBegin() w/o overflow.
215  for (size_t i = 0; i <= G8 / size; i++) {
216    void *x = cache.Allocate(a, max_size_class);
217    void *beg = a->GetBlockBegin(x);
218    // if ((i & (i - 1)) == 0)
219    //   fprintf(stderr, "[%zd] %p %p\n", i, x, beg);
220    EXPECT_EQ(x, beg);
221  }
222
223  a->TestOnlyUnmap();
224  delete a;
225}
226
227#if SANITIZER_CAN_USE_ALLOCATOR64
228TEST(SanitizerCommon, SizeClassAllocator64GetBlockBegin) {
229  SizeClassAllocatorGetBlockBeginStress<Allocator64>();
230}
231TEST(SanitizerCommon, SizeClassAllocator64CompactGetBlockBegin) {
232  SizeClassAllocatorGetBlockBeginStress<Allocator64Compact>();
233}
234TEST(SanitizerCommon, SizeClassAllocator32CompactGetBlockBegin) {
235  SizeClassAllocatorGetBlockBeginStress<Allocator32Compact>();
236}
237#endif  // SANITIZER_CAN_USE_ALLOCATOR64
238
239struct TestMapUnmapCallback {
240  static int map_count, unmap_count;
241  void OnMap(uptr p, uptr size) const { map_count++; }
242  void OnUnmap(uptr p, uptr size) const { unmap_count++; }
243};
244int TestMapUnmapCallback::map_count;
245int TestMapUnmapCallback::unmap_count;
246
247#if SANITIZER_CAN_USE_ALLOCATOR64
248TEST(SanitizerCommon, SizeClassAllocator64MapUnmapCallback) {
249  TestMapUnmapCallback::map_count = 0;
250  TestMapUnmapCallback::unmap_count = 0;
251  typedef SizeClassAllocator64<
252      kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap,
253      TestMapUnmapCallback> Allocator64WithCallBack;
254  Allocator64WithCallBack *a = new Allocator64WithCallBack;
255  a->Init();
256  EXPECT_EQ(TestMapUnmapCallback::map_count, 1);  // Allocator state.
257  SizeClassAllocatorLocalCache<Allocator64WithCallBack> cache;
258  memset(&cache, 0, sizeof(cache));
259  cache.Init(0);
260  AllocatorStats stats;
261  stats.Init();
262  a->AllocateBatch(&stats, &cache, 32);
263  EXPECT_EQ(TestMapUnmapCallback::map_count, 3);  // State + alloc + metadata.
264  a->TestOnlyUnmap();
265  EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1);  // The whole thing.
266  delete a;
267}
268#endif
269
270TEST(SanitizerCommon, SizeClassAllocator32MapUnmapCallback) {
271  TestMapUnmapCallback::map_count = 0;
272  TestMapUnmapCallback::unmap_count = 0;
273  typedef SizeClassAllocator32<
274      0, kAddressSpaceSize,
275      /*kMetadataSize*/16,
276      CompactSizeClassMap,
277      kRegionSizeLog,
278      FlatByteMap<kFlatByteMapSize>,
279      TestMapUnmapCallback>
280    Allocator32WithCallBack;
281  Allocator32WithCallBack *a = new Allocator32WithCallBack;
282  a->Init();
283  EXPECT_EQ(TestMapUnmapCallback::map_count, 0);
284  SizeClassAllocatorLocalCache<Allocator32WithCallBack>  cache;
285  memset(&cache, 0, sizeof(cache));
286  cache.Init(0);
287  AllocatorStats stats;
288  stats.Init();
289  a->AllocateBatch(&stats, &cache, 32);
290  EXPECT_EQ(TestMapUnmapCallback::map_count, 1);
291  a->TestOnlyUnmap();
292  EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1);
293  delete a;
294  // fprintf(stderr, "Map: %d Unmap: %d\n",
295  //         TestMapUnmapCallback::map_count,
296  //         TestMapUnmapCallback::unmap_count);
297}
298
299TEST(SanitizerCommon, LargeMmapAllocatorMapUnmapCallback) {
300  TestMapUnmapCallback::map_count = 0;
301  TestMapUnmapCallback::unmap_count = 0;
302  LargeMmapAllocator<TestMapUnmapCallback> a;
303  a.Init(/* may_return_null */ false);
304  AllocatorStats stats;
305  stats.Init();
306  void *x = a.Allocate(&stats, 1 << 20, 1);
307  EXPECT_EQ(TestMapUnmapCallback::map_count, 1);
308  a.Deallocate(&stats, x);
309  EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1);
310}
311
312template<class Allocator>
313void FailInAssertionOnOOM() {
314  Allocator a;
315  a.Init();
316  SizeClassAllocatorLocalCache<Allocator> cache;
317  memset(&cache, 0, sizeof(cache));
318  cache.Init(0);
319  AllocatorStats stats;
320  stats.Init();
321  for (int i = 0; i < 1000000; i++) {
322    a.AllocateBatch(&stats, &cache, 52);
323  }
324
325  a.TestOnlyUnmap();
326}
327
328#if SANITIZER_CAN_USE_ALLOCATOR64
329TEST(SanitizerCommon, SizeClassAllocator64Overflow) {
330  EXPECT_DEATH(FailInAssertionOnOOM<Allocator64>(), "Out of memory");
331}
332#endif
333
334#if !defined(_WIN32)  // FIXME: This currently fails on Windows.
335TEST(SanitizerCommon, LargeMmapAllocator) {
336  LargeMmapAllocator<> a;
337  a.Init(/* may_return_null */ false);
338  AllocatorStats stats;
339  stats.Init();
340
341  static const int kNumAllocs = 1000;
342  char *allocated[kNumAllocs];
343  static const uptr size = 4000;
344  // Allocate some.
345  for (int i = 0; i < kNumAllocs; i++) {
346    allocated[i] = (char *)a.Allocate(&stats, size, 1);
347    CHECK(a.PointerIsMine(allocated[i]));
348  }
349  // Deallocate all.
350  CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs);
351  for (int i = 0; i < kNumAllocs; i++) {
352    char *p = allocated[i];
353    CHECK(a.PointerIsMine(p));
354    a.Deallocate(&stats, p);
355  }
356  // Check that non left.
357  CHECK_EQ(a.TotalMemoryUsed(), 0);
358
359  // Allocate some more, also add metadata.
360  for (int i = 0; i < kNumAllocs; i++) {
361    char *x = (char *)a.Allocate(&stats, size, 1);
362    CHECK_GE(a.GetActuallyAllocatedSize(x), size);
363    uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(x));
364    *meta = i;
365    allocated[i] = x;
366  }
367  for (int i = 0; i < kNumAllocs * kNumAllocs; i++) {
368    char *p = allocated[i % kNumAllocs];
369    CHECK(a.PointerIsMine(p));
370    CHECK(a.PointerIsMine(p + 2000));
371  }
372  CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs);
373  // Deallocate all in reverse order.
374  for (int i = 0; i < kNumAllocs; i++) {
375    int idx = kNumAllocs - i - 1;
376    char *p = allocated[idx];
377    uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(p));
378    CHECK_EQ(*meta, idx);
379    CHECK(a.PointerIsMine(p));
380    a.Deallocate(&stats, p);
381  }
382  CHECK_EQ(a.TotalMemoryUsed(), 0);
383
384  // Test alignments.
385  uptr max_alignment = SANITIZER_WORDSIZE == 64 ? (1 << 28) : (1 << 24);
386  for (uptr alignment = 8; alignment <= max_alignment; alignment *= 2) {
387    const uptr kNumAlignedAllocs = 100;
388    for (uptr i = 0; i < kNumAlignedAllocs; i++) {
389      uptr size = ((i % 10) + 1) * 4096;
390      char *p = allocated[i] = (char *)a.Allocate(&stats, size, alignment);
391      CHECK_EQ(p, a.GetBlockBegin(p));
392      CHECK_EQ(p, a.GetBlockBegin(p + size - 1));
393      CHECK_EQ(p, a.GetBlockBegin(p + size / 2));
394      CHECK_EQ(0, (uptr)allocated[i] % alignment);
395      p[0] = p[size - 1] = 0;
396    }
397    for (uptr i = 0; i < kNumAlignedAllocs; i++) {
398      a.Deallocate(&stats, allocated[i]);
399    }
400  }
401
402  // Regression test for boundary condition in GetBlockBegin().
403  uptr page_size = GetPageSizeCached();
404  char *p = (char *)a.Allocate(&stats, page_size, 1);
405  CHECK_EQ(p, a.GetBlockBegin(p));
406  CHECK_EQ(p, (char *)a.GetBlockBegin(p + page_size - 1));
407  CHECK_NE(p, (char *)a.GetBlockBegin(p + page_size));
408  a.Deallocate(&stats, p);
409}
410#endif
411
412template
413<class PrimaryAllocator, class SecondaryAllocator, class AllocatorCache>
414void TestCombinedAllocator() {
415  typedef
416      CombinedAllocator<PrimaryAllocator, AllocatorCache, SecondaryAllocator>
417      Allocator;
418  Allocator *a = new Allocator;
419  a->Init(/* may_return_null */ true);
420
421  AllocatorCache cache;
422  memset(&cache, 0, sizeof(cache));
423  a->InitCache(&cache);
424
425  EXPECT_EQ(a->Allocate(&cache, -1, 1), (void*)0);
426  EXPECT_EQ(a->Allocate(&cache, -1, 1024), (void*)0);
427  EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1), (void*)0);
428  EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1024), (void*)0);
429  EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1023, 1024), (void*)0);
430
431  // Set to false
432  a->SetMayReturnNull(false);
433  EXPECT_DEATH(a->Allocate(&cache, -1, 1),
434               "allocator is terminating the process");
435
436  const uptr kNumAllocs = 100000;
437  const uptr kNumIter = 10;
438  for (uptr iter = 0; iter < kNumIter; iter++) {
439    std::vector<void*> allocated;
440    for (uptr i = 0; i < kNumAllocs; i++) {
441      uptr size = (i % (1 << 14)) + 1;
442      if ((i % 1024) == 0)
443        size = 1 << (10 + (i % 14));
444      void *x = a->Allocate(&cache, size, 1);
445      uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x));
446      CHECK_EQ(*meta, 0);
447      *meta = size;
448      allocated.push_back(x);
449    }
450
451    random_shuffle(allocated.begin(), allocated.end());
452
453    for (uptr i = 0; i < kNumAllocs; i++) {
454      void *x = allocated[i];
455      uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x));
456      CHECK_NE(*meta, 0);
457      CHECK(a->PointerIsMine(x));
458      *meta = 0;
459      a->Deallocate(&cache, x);
460    }
461    allocated.clear();
462    a->SwallowCache(&cache);
463  }
464  a->DestroyCache(&cache);
465  a->TestOnlyUnmap();
466}
467
468#if SANITIZER_CAN_USE_ALLOCATOR64
469TEST(SanitizerCommon, CombinedAllocator64) {
470  TestCombinedAllocator<Allocator64,
471      LargeMmapAllocator<>,
472      SizeClassAllocatorLocalCache<Allocator64> > ();
473}
474
475TEST(SanitizerCommon, CombinedAllocator64Compact) {
476  TestCombinedAllocator<Allocator64Compact,
477      LargeMmapAllocator<>,
478      SizeClassAllocatorLocalCache<Allocator64Compact> > ();
479}
480#endif
481
482#if !defined(_WIN32)  // FIXME: This currently fails on Windows.
483TEST(SanitizerCommon, CombinedAllocator32Compact) {
484  TestCombinedAllocator<Allocator32Compact,
485      LargeMmapAllocator<>,
486      SizeClassAllocatorLocalCache<Allocator32Compact> > ();
487}
488#endif
489
490template <class AllocatorCache>
491void TestSizeClassAllocatorLocalCache() {
492  AllocatorCache cache;
493  typedef typename AllocatorCache::Allocator Allocator;
494  Allocator *a = new Allocator();
495
496  a->Init();
497  memset(&cache, 0, sizeof(cache));
498  cache.Init(0);
499
500  const uptr kNumAllocs = 10000;
501  const int kNumIter = 100;
502  uptr saved_total = 0;
503  for (int class_id = 1; class_id <= 5; class_id++) {
504    for (int it = 0; it < kNumIter; it++) {
505      void *allocated[kNumAllocs];
506      for (uptr i = 0; i < kNumAllocs; i++) {
507        allocated[i] = cache.Allocate(a, class_id);
508      }
509      for (uptr i = 0; i < kNumAllocs; i++) {
510        cache.Deallocate(a, class_id, allocated[i]);
511      }
512      cache.Drain(a);
513      uptr total_allocated = a->TotalMemoryUsed();
514      if (it)
515        CHECK_EQ(saved_total, total_allocated);
516      saved_total = total_allocated;
517    }
518  }
519
520  a->TestOnlyUnmap();
521  delete a;
522}
523
524#if SANITIZER_CAN_USE_ALLOCATOR64
525TEST(SanitizerCommon, SizeClassAllocator64LocalCache) {
526  TestSizeClassAllocatorLocalCache<
527      SizeClassAllocatorLocalCache<Allocator64> >();
528}
529
530TEST(SanitizerCommon, SizeClassAllocator64CompactLocalCache) {
531  TestSizeClassAllocatorLocalCache<
532      SizeClassAllocatorLocalCache<Allocator64Compact> >();
533}
534#endif
535
536TEST(SanitizerCommon, SizeClassAllocator32CompactLocalCache) {
537  TestSizeClassAllocatorLocalCache<
538      SizeClassAllocatorLocalCache<Allocator32Compact> >();
539}
540
541#if SANITIZER_CAN_USE_ALLOCATOR64
542typedef SizeClassAllocatorLocalCache<Allocator64> AllocatorCache;
543static AllocatorCache static_allocator_cache;
544
545void *AllocatorLeakTestWorker(void *arg) {
546  typedef AllocatorCache::Allocator Allocator;
547  Allocator *a = (Allocator*)(arg);
548  static_allocator_cache.Allocate(a, 10);
549  static_allocator_cache.Drain(a);
550  return 0;
551}
552
553TEST(SanitizerCommon, AllocatorLeakTest) {
554  typedef AllocatorCache::Allocator Allocator;
555  Allocator a;
556  a.Init();
557  uptr total_used_memory = 0;
558  for (int i = 0; i < 100; i++) {
559    pthread_t t;
560    PTHREAD_CREATE(&t, 0, AllocatorLeakTestWorker, &a);
561    PTHREAD_JOIN(t, 0);
562    if (i == 0)
563      total_used_memory = a.TotalMemoryUsed();
564    EXPECT_EQ(a.TotalMemoryUsed(), total_used_memory);
565  }
566
567  a.TestOnlyUnmap();
568}
569
570// Struct which is allocated to pass info to new threads.  The new thread frees
571// it.
572struct NewThreadParams {
573  AllocatorCache *thread_cache;
574  AllocatorCache::Allocator *allocator;
575  uptr class_id;
576};
577
578// Called in a new thread.  Just frees its argument.
579static void *DeallocNewThreadWorker(void *arg) {
580  NewThreadParams *params = reinterpret_cast<NewThreadParams*>(arg);
581  params->thread_cache->Deallocate(params->allocator, params->class_id, params);
582  return NULL;
583}
584
585// The allocator cache is supposed to be POD and zero initialized.  We should be
586// able to call Deallocate on a zeroed cache, and it will self-initialize.
587TEST(Allocator, AllocatorCacheDeallocNewThread) {
588  AllocatorCache::Allocator allocator;
589  allocator.Init();
590  AllocatorCache main_cache;
591  AllocatorCache child_cache;
592  memset(&main_cache, 0, sizeof(main_cache));
593  memset(&child_cache, 0, sizeof(child_cache));
594
595  uptr class_id = DefaultSizeClassMap::ClassID(sizeof(NewThreadParams));
596  NewThreadParams *params = reinterpret_cast<NewThreadParams*>(
597      main_cache.Allocate(&allocator, class_id));
598  params->thread_cache = &child_cache;
599  params->allocator = &allocator;
600  params->class_id = class_id;
601  pthread_t t;
602  PTHREAD_CREATE(&t, 0, DeallocNewThreadWorker, params);
603  PTHREAD_JOIN(t, 0);
604}
605#endif
606
607TEST(Allocator, Basic) {
608  char *p = (char*)InternalAlloc(10);
609  EXPECT_NE(p, (char*)0);
610  char *p2 = (char*)InternalAlloc(20);
611  EXPECT_NE(p2, (char*)0);
612  EXPECT_NE(p2, p);
613  InternalFree(p);
614  InternalFree(p2);
615}
616
617TEST(Allocator, Stress) {
618  const int kCount = 1000;
619  char *ptrs[kCount];
620  unsigned rnd = 42;
621  for (int i = 0; i < kCount; i++) {
622    uptr sz = my_rand_r(&rnd) % 1000;
623    char *p = (char*)InternalAlloc(sz);
624    EXPECT_NE(p, (char*)0);
625    ptrs[i] = p;
626  }
627  for (int i = 0; i < kCount; i++) {
628    InternalFree(ptrs[i]);
629  }
630}
631
632TEST(Allocator, LargeAlloc) {
633  void *p = InternalAlloc(10 << 20);
634  InternalFree(p);
635}
636
637TEST(Allocator, ScopedBuffer) {
638  const int kSize = 512;
639  {
640    InternalScopedBuffer<int> int_buf(kSize);
641    EXPECT_EQ(sizeof(int) * kSize, int_buf.size());  // NOLINT
642  }
643  InternalScopedBuffer<char> char_buf(kSize);
644  EXPECT_EQ(sizeof(char) * kSize, char_buf.size());  // NOLINT
645  internal_memset(char_buf.data(), 'c', kSize);
646  for (int i = 0; i < kSize; i++) {
647    EXPECT_EQ('c', char_buf[i]);
648  }
649}
650
651void IterationTestCallback(uptr chunk, void *arg) {
652  reinterpret_cast<std::set<uptr> *>(arg)->insert(chunk);
653}
654
655template <class Allocator>
656void TestSizeClassAllocatorIteration() {
657  Allocator *a = new Allocator;
658  a->Init();
659  SizeClassAllocatorLocalCache<Allocator> cache;
660  memset(&cache, 0, sizeof(cache));
661  cache.Init(0);
662
663  static const uptr sizes[] = {1, 16, 30, 40, 100, 1000, 10000,
664    50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000};
665
666  std::vector<void *> allocated;
667
668  // Allocate a bunch of chunks.
669  for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) {
670    uptr size = sizes[s];
671    if (!a->CanAllocate(size, 1)) continue;
672    // printf("s = %ld\n", size);
673    uptr n_iter = std::max((uptr)6, 80000 / size);
674    // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter);
675    for (uptr j = 0; j < n_iter; j++) {
676      uptr class_id0 = Allocator::SizeClassMapT::ClassID(size);
677      void *x = cache.Allocate(a, class_id0);
678      allocated.push_back(x);
679    }
680  }
681
682  std::set<uptr> reported_chunks;
683  a->ForceLock();
684  a->ForEachChunk(IterationTestCallback, &reported_chunks);
685  a->ForceUnlock();
686
687  for (uptr i = 0; i < allocated.size(); i++) {
688    // Don't use EXPECT_NE. Reporting the first mismatch is enough.
689    ASSERT_NE(reported_chunks.find(reinterpret_cast<uptr>(allocated[i])),
690              reported_chunks.end());
691  }
692
693  a->TestOnlyUnmap();
694  delete a;
695}
696
697#if SANITIZER_CAN_USE_ALLOCATOR64
698TEST(SanitizerCommon, SizeClassAllocator64Iteration) {
699  TestSizeClassAllocatorIteration<Allocator64>();
700}
701#endif
702
703TEST(SanitizerCommon, SizeClassAllocator32Iteration) {
704  TestSizeClassAllocatorIteration<Allocator32Compact>();
705}
706
707TEST(SanitizerCommon, LargeMmapAllocatorIteration) {
708  LargeMmapAllocator<> a;
709  a.Init(/* may_return_null */ false);
710  AllocatorStats stats;
711  stats.Init();
712
713  static const uptr kNumAllocs = 1000;
714  char *allocated[kNumAllocs];
715  static const uptr size = 40;
716  // Allocate some.
717  for (uptr i = 0; i < kNumAllocs; i++)
718    allocated[i] = (char *)a.Allocate(&stats, size, 1);
719
720  std::set<uptr> reported_chunks;
721  a.ForceLock();
722  a.ForEachChunk(IterationTestCallback, &reported_chunks);
723  a.ForceUnlock();
724
725  for (uptr i = 0; i < kNumAllocs; i++) {
726    // Don't use EXPECT_NE. Reporting the first mismatch is enough.
727    ASSERT_NE(reported_chunks.find(reinterpret_cast<uptr>(allocated[i])),
728              reported_chunks.end());
729  }
730  for (uptr i = 0; i < kNumAllocs; i++)
731    a.Deallocate(&stats, allocated[i]);
732}
733
734TEST(SanitizerCommon, LargeMmapAllocatorBlockBegin) {
735  LargeMmapAllocator<> a;
736  a.Init(/* may_return_null */ false);
737  AllocatorStats stats;
738  stats.Init();
739
740  static const uptr kNumAllocs = 1024;
741  static const uptr kNumExpectedFalseLookups = 10000000;
742  char *allocated[kNumAllocs];
743  static const uptr size = 4096;
744  // Allocate some.
745  for (uptr i = 0; i < kNumAllocs; i++) {
746    allocated[i] = (char *)a.Allocate(&stats, size, 1);
747  }
748
749  a.ForceLock();
750  for (uptr i = 0; i < kNumAllocs  * kNumAllocs; i++) {
751    // if ((i & (i - 1)) == 0) fprintf(stderr, "[%zd]\n", i);
752    char *p1 = allocated[i % kNumAllocs];
753    EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1));
754    EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 + size / 2));
755    EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 + size - 1));
756    EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 - 100));
757  }
758
759  for (uptr i = 0; i < kNumExpectedFalseLookups; i++) {
760    void *p = reinterpret_cast<void *>(i % 1024);
761    EXPECT_EQ((void *)0, a.GetBlockBeginFastLocked(p));
762    p = reinterpret_cast<void *>(~0L - (i % 1024));
763    EXPECT_EQ((void *)0, a.GetBlockBeginFastLocked(p));
764  }
765  a.ForceUnlock();
766
767  for (uptr i = 0; i < kNumAllocs; i++)
768    a.Deallocate(&stats, allocated[i]);
769}
770
771
772#if SANITIZER_CAN_USE_ALLOCATOR64
773// Regression test for out-of-memory condition in PopulateFreeList().
774TEST(SanitizerCommon, SizeClassAllocator64PopulateFreeListOOM) {
775  // In a world where regions are small and chunks are huge...
776  typedef SizeClassMap<63, 128, 16> SpecialSizeClassMap;
777  typedef SizeClassAllocator64<kAllocatorSpace, kAllocatorSize, 0,
778                               SpecialSizeClassMap> SpecialAllocator64;
779  const uptr kRegionSize =
780      kAllocatorSize / SpecialSizeClassMap::kNumClassesRounded;
781  SpecialAllocator64 *a = new SpecialAllocator64;
782  a->Init();
783  SizeClassAllocatorLocalCache<SpecialAllocator64> cache;
784  memset(&cache, 0, sizeof(cache));
785  cache.Init(0);
786
787  // ...one man is on a mission to overflow a region with a series of
788  // successive allocations.
789  const uptr kClassID = 107;
790  const uptr kAllocationSize = DefaultSizeClassMap::Size(kClassID);
791  ASSERT_LT(2 * kAllocationSize, kRegionSize);
792  ASSERT_GT(3 * kAllocationSize, kRegionSize);
793  cache.Allocate(a, kClassID);
794  EXPECT_DEATH(cache.Allocate(a, kClassID) && cache.Allocate(a, kClassID),
795               "The process has exhausted");
796  a->TestOnlyUnmap();
797  delete a;
798}
799#endif
800
801TEST(SanitizerCommon, TwoLevelByteMap) {
802  const u64 kSize1 = 1 << 6, kSize2 = 1 << 12;
803  const u64 n = kSize1 * kSize2;
804  TwoLevelByteMap<kSize1, kSize2> m;
805  m.TestOnlyInit();
806  for (u64 i = 0; i < n; i += 7) {
807    m.set(i, (i % 100) + 1);
808  }
809  for (u64 j = 0; j < n; j++) {
810    if (j % 7)
811      EXPECT_EQ(m[j], 0);
812    else
813      EXPECT_EQ(m[j], (j % 100) + 1);
814  }
815
816  m.TestOnlyUnmap();
817}
818
819
820typedef TwoLevelByteMap<1 << 12, 1 << 13, TestMapUnmapCallback> TestByteMap;
821
822struct TestByteMapParam {
823  TestByteMap *m;
824  size_t shard;
825  size_t num_shards;
826};
827
828void *TwoLevelByteMapUserThread(void *param) {
829  TestByteMapParam *p = (TestByteMapParam*)param;
830  for (size_t i = p->shard; i < p->m->size(); i += p->num_shards) {
831    size_t val = (i % 100) + 1;
832    p->m->set(i, val);
833    EXPECT_EQ((*p->m)[i], val);
834  }
835  return 0;
836}
837
838TEST(SanitizerCommon, ThreadedTwoLevelByteMap) {
839  TestByteMap m;
840  m.TestOnlyInit();
841  TestMapUnmapCallback::map_count = 0;
842  TestMapUnmapCallback::unmap_count = 0;
843  static const int kNumThreads = 4;
844  pthread_t t[kNumThreads];
845  TestByteMapParam p[kNumThreads];
846  for (int i = 0; i < kNumThreads; i++) {
847    p[i].m = &m;
848    p[i].shard = i;
849    p[i].num_shards = kNumThreads;
850    PTHREAD_CREATE(&t[i], 0, TwoLevelByteMapUserThread, &p[i]);
851  }
852  for (int i = 0; i < kNumThreads; i++) {
853    PTHREAD_JOIN(t[i], 0);
854  }
855  EXPECT_EQ((uptr)TestMapUnmapCallback::map_count, m.size1());
856  EXPECT_EQ((uptr)TestMapUnmapCallback::unmap_count, 0UL);
857  m.TestOnlyUnmap();
858  EXPECT_EQ((uptr)TestMapUnmapCallback::map_count, m.size1());
859  EXPECT_EQ((uptr)TestMapUnmapCallback::unmap_count, m.size1());
860}
861
862#endif  // #if !SANITIZER_DEBUG
863