1/*
2 * Copyright (C) 2014 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "Benchmark.h"
27#include "CPUCount.h"
28#include "stress_aligned.h"
29#include <array>
30#include <cassert>
31#include <chrono>
32#include <cmath>
33#include <cstdlib>
34#include <memory>
35#include <stddef.h>
36#include <vector>
37
38#include "mbmalloc.h"
39
40namespace {
41
42static const size_t kB = 1024;
43static const size_t MB = kB * kB;
44
45struct Object {
46 Object(void* pointer, size_t size, long uuid)
47 : pointer(pointer)
48 , size(size)
49 , uuid(uuid)
50 {
51 }
52
53 void* pointer;
54 size_t size;
55 long uuid;
56};
57
58class SizeStream {
59public:
60 SizeStream()
61 : m_state(Small)
62 , m_count(0)
63 {
64 }
65
66 size_t next()
67 {
68 switch (m_state) {
69 case Small: {
70 if (++m_count == smallCount) {
71 m_state = Medium;
72 m_count = 0;
73 }
74 return random() % smallMax;
75 }
76
77 case Medium: {
78 if (++m_count == mediumCount) {
79 m_state = Large;
80 m_count = 0;
81 }
82 return random() % mediumMax;
83 }
84
85 case Large: {
86 if (++m_count == largeCount) {
87 m_state = Small;
88 m_count = 0;
89 }
90 return random() % largeMax;
91 }
92 }
93 assert(0);
94 return 0;
95 }
96
97private:
98 static const size_t smallCount = 1000;
99 static const size_t smallMax = 16 * kB;
100
101 static const size_t mediumCount = 100;
102 static const size_t mediumMax = 512 * kB;
103
104 static const size_t largeCount = 10;
105 static const size_t largeMax = 4 * MB;
106
107 enum { Small, Medium, Large } m_state;
108 size_t m_count;
109};
110
111Object allocate(size_t alignment, size_t size)
112{
113 Object object(mbmemalign(alignment, size), size, random());
114 if ((uintptr_t)object.pointer & (alignment - 1))
115 abort();
116 for (size_t i = 0; i < size / sizeof(long); ++i)
117 (static_cast<long*>(object.pointer))[i] = object.uuid;
118 return object;
119}
120
121void deallocate(const Object& object)
122{
123 for (size_t i = 0; i < object.size / sizeof(long); ++i) {
124 if ((static_cast<long*>(object.pointer))[i] != object.uuid)
125 abort();
126 }
127
128 mbfree(object.pointer, object.size);
129}
130
131size_t randomAlignment()
132{
133 switch (random() % 32) {
134 case 0:
135 return pow(2, random() % 26);
136 default:
137 return pow(2, random() % 14);
138 }
139}
140
141}
142
143void benchmark_stress_aligned(CommandLine&)
144{
145 const size_t heapSize = 100 * MB;
146 const size_t churnSize = .05 * heapSize;
147 const size_t churnCount = 100;
148
149 srandom(1); // For consistency between runs.
150
151 size_t limit = 0x00001ffffffffffful;
152
153 for (size_t size = 0; size < limit; size = std::max(size, sizeof(void*)) * 2) {
154 for (size_t alignment = sizeof(void*); alignment < limit; alignment *= 2) {
155 void* object = mbmemalign(alignment, size);
156 if (reinterpret_cast<uintptr_t>(object) & (alignment - 1))
157 abort();
158 mbfree(object, size);
159 }
160
161 for (size_t alignment = sizeof(void*); alignment < limit; alignment *= 2) {
162 void* object = mbmemalign(alignment, size + 128);
163 if (reinterpret_cast<uintptr_t>(object) & (alignment - 1))
164 abort();
165 mbfree(object, size + 128);
166 }
167 }
168
169 std::vector<Object> objects;
170
171 SizeStream sizeStream;
172
173 size_t size = 0;
174 for (size_t remaining = heapSize; remaining; remaining -= std::min(remaining, size)) {
175 size = sizeStream.next();
176 objects.push_back(allocate(randomAlignment(), size));
177 }
178
179 for (size_t i = 0; i < churnCount; ++i) {
180 std::vector<Object> objectsToFree;
181 for (size_t remaining = churnSize; remaining; remaining -= std::min(remaining, size)) {
182 size = sizeStream.next();
183 Object object = allocate(randomAlignment(), size);
184
185 size_t index = random() % objects.size();
186 objectsToFree.push_back(objects[index]);
187 objects[index] = object;
188 }
189
190 for (auto& object : objectsToFree)
191 deallocate(object);
192
193 mbscavenge();
194 }
195
196 for (auto& object : objects)
197 mbfree(object.pointer, object.size);
198}
199