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