Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1 | //===-- sanitizer_allocator.h -----------------------------------*- C++ -*-===// |
| 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 | // Specialized memory allocator for ThreadSanitizer, MemorySanitizer, etc. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef SANITIZER_ALLOCATOR_H |
| 15 | #define SANITIZER_ALLOCATOR_H |
| 16 | |
| 17 | #include "sanitizer_internal_defs.h" |
| 18 | #include "sanitizer_common.h" |
| 19 | #include "sanitizer_libc.h" |
| 20 | #include "sanitizer_list.h" |
| 21 | #include "sanitizer_mutex.h" |
Dmitry Vyukov | b48224c | 2013-01-14 08:23:34 +0000 | [diff] [blame] | 22 | #include "sanitizer_lfstack.h" |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 23 | |
| 24 | namespace __sanitizer { |
| 25 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 26 | // Prints error message and kills the program. |
| 27 | void NORETURN ReportAllocatorCannotReturnNull(); |
Kostya Serebryany | 9150f39 | 2013-09-06 09:25:11 +0000 | [diff] [blame] | 28 | |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 29 | // SizeClassMap maps allocation sizes into size classes and back. |
| 30 | // Class 0 corresponds to size 0. |
Kostya Serebryany | 3661bae | 2013-02-07 15:04:06 +0000 | [diff] [blame] | 31 | // Classes 1 - 16 correspond to sizes 16 to 256 (size = class_id * 16). |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 32 | // Next 4 classes: 256 + i * 64 (i = 1 to 4). |
| 33 | // Next 4 classes: 512 + i * 128 (i = 1 to 4). |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 34 | // ... |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 35 | // Next 4 classes: 2^k + i * 2^(k-2) (i = 1 to 4). |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 36 | // Last class corresponds to kMaxSize = 1 << kMaxSizeLog. |
| 37 | // |
| 38 | // This structure of the size class map gives us: |
| 39 | // - Efficient table-free class-to-size and size-to-class functions. |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 40 | // - Difference between two consequent size classes is betweed 14% and 25% |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 41 | // |
| 42 | // This class also gives a hint to a thread-caching allocator about the amount |
| 43 | // of chunks that need to be cached per-thread: |
| 44 | // - kMaxNumCached is the maximal number of chunks per size class. |
| 45 | // - (1 << kMaxBytesCachedLog) is the maximal number of bytes per size class. |
| 46 | // |
| 47 | // Part of output of SizeClassMap::Print(): |
Kostya Serebryany | 3661bae | 2013-02-07 15:04:06 +0000 | [diff] [blame] | 48 | // c00 => s: 0 diff: +0 00% l 0 cached: 0 0; id 0 |
| 49 | // c01 => s: 16 diff: +16 00% l 4 cached: 256 4096; id 1 |
| 50 | // c02 => s: 32 diff: +16 100% l 5 cached: 256 8192; id 2 |
| 51 | // c03 => s: 48 diff: +16 50% l 5 cached: 256 12288; id 3 |
| 52 | // c04 => s: 64 diff: +16 33% l 6 cached: 256 16384; id 4 |
| 53 | // c05 => s: 80 diff: +16 25% l 6 cached: 256 20480; id 5 |
| 54 | // c06 => s: 96 diff: +16 20% l 6 cached: 256 24576; id 6 |
| 55 | // c07 => s: 112 diff: +16 16% l 6 cached: 256 28672; id 7 |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 56 | // |
Kostya Serebryany | 3661bae | 2013-02-07 15:04:06 +0000 | [diff] [blame] | 57 | // c08 => s: 128 diff: +16 14% l 7 cached: 256 32768; id 8 |
| 58 | // c09 => s: 144 diff: +16 12% l 7 cached: 256 36864; id 9 |
| 59 | // c10 => s: 160 diff: +16 11% l 7 cached: 256 40960; id 10 |
| 60 | // c11 => s: 176 diff: +16 10% l 7 cached: 256 45056; id 11 |
| 61 | // c12 => s: 192 diff: +16 09% l 7 cached: 256 49152; id 12 |
| 62 | // c13 => s: 208 diff: +16 08% l 7 cached: 256 53248; id 13 |
| 63 | // c14 => s: 224 diff: +16 07% l 7 cached: 256 57344; id 14 |
| 64 | // c15 => s: 240 diff: +16 07% l 7 cached: 256 61440; id 15 |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 65 | // |
Kostya Serebryany | 3661bae | 2013-02-07 15:04:06 +0000 | [diff] [blame] | 66 | // c16 => s: 256 diff: +16 06% l 8 cached: 256 65536; id 16 |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 67 | // c17 => s: 320 diff: +64 25% l 8 cached: 204 65280; id 17 |
| 68 | // c18 => s: 384 diff: +64 20% l 8 cached: 170 65280; id 18 |
| 69 | // c19 => s: 448 diff: +64 16% l 8 cached: 146 65408; id 19 |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 70 | // |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 71 | // c20 => s: 512 diff: +64 14% l 9 cached: 128 65536; id 20 |
| 72 | // c21 => s: 640 diff: +128 25% l 9 cached: 102 65280; id 21 |
| 73 | // c22 => s: 768 diff: +128 20% l 9 cached: 85 65280; id 22 |
| 74 | // c23 => s: 896 diff: +128 16% l 9 cached: 73 65408; id 23 |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 75 | // |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 76 | // c24 => s: 1024 diff: +128 14% l 10 cached: 64 65536; id 24 |
| 77 | // c25 => s: 1280 diff: +256 25% l 10 cached: 51 65280; id 25 |
| 78 | // c26 => s: 1536 diff: +256 20% l 10 cached: 42 64512; id 26 |
| 79 | // c27 => s: 1792 diff: +256 16% l 10 cached: 36 64512; id 27 |
| 80 | // |
| 81 | // ... |
| 82 | // |
| 83 | // c48 => s: 65536 diff: +8192 14% l 16 cached: 1 65536; id 48 |
| 84 | // c49 => s: 81920 diff: +16384 25% l 16 cached: 1 81920; id 49 |
| 85 | // c50 => s: 98304 diff: +16384 20% l 16 cached: 1 98304; id 50 |
| 86 | // c51 => s: 114688 diff: +16384 16% l 16 cached: 1 114688; id 51 |
| 87 | // |
| 88 | // c52 => s: 131072 diff: +16384 14% l 17 cached: 1 131072; id 52 |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 89 | |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 90 | template <uptr kMaxSizeLog, uptr kMaxNumCachedT, uptr kMaxBytesCachedLog> |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 91 | class SizeClassMap { |
Kostya Serebryany | 3661bae | 2013-02-07 15:04:06 +0000 | [diff] [blame] | 92 | static const uptr kMinSizeLog = 4; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 93 | static const uptr kMidSizeLog = kMinSizeLog + 4; |
| 94 | static const uptr kMinSize = 1 << kMinSizeLog; |
| 95 | static const uptr kMidSize = 1 << kMidSizeLog; |
| 96 | static const uptr kMidClass = kMidSize / kMinSize; |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 97 | static const uptr S = 2; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 98 | static const uptr M = (1 << S) - 1; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 99 | |
| 100 | public: |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 101 | static const uptr kMaxNumCached = kMaxNumCachedT; |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 102 | // We transfer chunks between central and thread-local free lists in batches. |
| 103 | // For small size classes we allocate batches separately. |
| 104 | // For large size classes we use one of the chunks to store the batch. |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 105 | struct TransferBatch { |
| 106 | TransferBatch *next; |
| 107 | uptr count; |
| 108 | void *batch[kMaxNumCached]; |
| 109 | }; |
| 110 | |
Kostya Serebryany | 8d6854a | 2013-05-16 13:24:31 +0000 | [diff] [blame] | 111 | static const uptr kMaxSize = 1UL << kMaxSizeLog; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 112 | static const uptr kNumClasses = |
| 113 | kMidClass + ((kMaxSizeLog - kMidSizeLog) << S) + 1; |
| 114 | COMPILER_CHECK(kNumClasses >= 32 && kNumClasses <= 256); |
| 115 | static const uptr kNumClassesRounded = |
| 116 | kNumClasses == 32 ? 32 : |
| 117 | kNumClasses <= 64 ? 64 : |
| 118 | kNumClasses <= 128 ? 128 : 256; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 119 | |
| 120 | static uptr Size(uptr class_id) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 121 | if (class_id <= kMidClass) |
| 122 | return kMinSize * class_id; |
| 123 | class_id -= kMidClass; |
| 124 | uptr t = kMidSize << (class_id >> S); |
| 125 | return t + (t >> S) * (class_id & M); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 126 | } |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 127 | |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 128 | static uptr ClassID(uptr size) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 129 | if (size <= kMidSize) |
| 130 | return (size + kMinSize - 1) >> kMinSizeLog; |
| 131 | if (size > kMaxSize) return 0; |
Timur Iskhodzhanov | 2b10d39 | 2013-02-08 12:02:00 +0000 | [diff] [blame] | 132 | uptr l = MostSignificantSetBitIndex(size); |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 133 | uptr hbits = (size >> (l - S)) & M; |
| 134 | uptr lbits = size & ((1 << (l - S)) - 1); |
| 135 | uptr l1 = l - kMidSizeLog; |
| 136 | return kMidClass + (l1 << S) + hbits + (lbits > 0); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 137 | } |
| 138 | |
| 139 | static uptr MaxCached(uptr class_id) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 140 | if (class_id == 0) return 0; |
| 141 | uptr n = (1UL << kMaxBytesCachedLog) / Size(class_id); |
Dmitry Vyukov | 8ceeec4 | 2013-02-04 08:07:45 +0000 | [diff] [blame] | 142 | return Max<uptr>(1, Min(kMaxNumCached, n)); |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 143 | } |
| 144 | |
| 145 | static void Print() { |
| 146 | uptr prev_s = 0; |
| 147 | uptr total_cached = 0; |
| 148 | for (uptr i = 0; i < kNumClasses; i++) { |
| 149 | uptr s = Size(i); |
| 150 | if (s >= kMidSize / 2 && (s & (s - 1)) == 0) |
| 151 | Printf("\n"); |
| 152 | uptr d = s - prev_s; |
| 153 | uptr p = prev_s ? (d * 100 / prev_s) : 0; |
Evgeniy Stepanov | cf80871 | 2013-03-01 08:49:14 +0000 | [diff] [blame] | 154 | uptr l = s ? MostSignificantSetBitIndex(s) : 0; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 155 | uptr cached = MaxCached(i) * s; |
| 156 | Printf("c%02zd => s: %zd diff: +%zd %02zd%% l %zd " |
| 157 | "cached: %zd %zd; id %zd\n", |
| 158 | i, Size(i), d, p, l, MaxCached(i), cached, ClassID(s)); |
| 159 | total_cached += cached; |
| 160 | prev_s = s; |
| 161 | } |
| 162 | Printf("Total cached: %zd\n", total_cached); |
| 163 | } |
| 164 | |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 165 | static bool SizeClassRequiresSeparateTransferBatch(uptr class_id) { |
| 166 | return Size(class_id) < sizeof(TransferBatch) - |
| 167 | sizeof(uptr) * (kMaxNumCached - MaxCached(class_id)); |
| 168 | } |
| 169 | |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 170 | static void Validate() { |
| 171 | for (uptr c = 1; c < kNumClasses; c++) { |
| 172 | // Printf("Validate: c%zd\n", c); |
| 173 | uptr s = Size(c); |
Kostya Serebryany | f155fcc | 2013-02-26 12:59:06 +0000 | [diff] [blame] | 174 | CHECK_NE(s, 0U); |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 175 | CHECK_EQ(ClassID(s), c); |
| 176 | if (c != kNumClasses - 1) |
| 177 | CHECK_EQ(ClassID(s + 1), c + 1); |
| 178 | CHECK_EQ(ClassID(s - 1), c); |
| 179 | if (c) |
| 180 | CHECK_GT(Size(c), Size(c-1)); |
| 181 | } |
| 182 | CHECK_EQ(ClassID(kMaxSize + 1), 0); |
| 183 | |
| 184 | for (uptr s = 1; s <= kMaxSize; s++) { |
| 185 | uptr c = ClassID(s); |
| 186 | // Printf("s%zd => c%zd\n", s, c); |
| 187 | CHECK_LT(c, kNumClasses); |
| 188 | CHECK_GE(Size(c), s); |
| 189 | if (c > 0) |
| 190 | CHECK_LT(Size(c-1), s); |
| 191 | } |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 192 | } |
| 193 | }; |
| 194 | |
Dmitry Vyukov | 4b450f4 | 2013-03-20 09:26:46 +0000 | [diff] [blame] | 195 | typedef SizeClassMap<17, 128, 16> DefaultSizeClassMap; |
Kostya Serebryany | f2c417c | 2013-03-12 08:44:40 +0000 | [diff] [blame] | 196 | typedef SizeClassMap<17, 64, 14> CompactSizeClassMap; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 197 | template<class SizeClassAllocator> struct SizeClassAllocatorLocalCache; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 198 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 199 | // Memory allocator statistics |
| 200 | enum AllocatorStat { |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 201 | AllocatorStatAllocated, |
| 202 | AllocatorStatMapped, |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 203 | AllocatorStatCount |
| 204 | }; |
| 205 | |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 206 | typedef uptr AllocatorStatCounters[AllocatorStatCount]; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 207 | |
| 208 | // Per-thread stats, live in per-thread cache. |
| 209 | class AllocatorStats { |
| 210 | public: |
| 211 | void Init() { |
| 212 | internal_memset(this, 0, sizeof(*this)); |
| 213 | } |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 214 | void InitLinkerInitialized() {} |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 215 | |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 216 | void Add(AllocatorStat i, uptr v) { |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 217 | v += atomic_load(&stats_[i], memory_order_relaxed); |
| 218 | atomic_store(&stats_[i], v, memory_order_relaxed); |
| 219 | } |
| 220 | |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 221 | void Sub(AllocatorStat i, uptr v) { |
| 222 | v = atomic_load(&stats_[i], memory_order_relaxed) - v; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 223 | atomic_store(&stats_[i], v, memory_order_relaxed); |
| 224 | } |
| 225 | |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 226 | void Set(AllocatorStat i, uptr v) { |
| 227 | atomic_store(&stats_[i], v, memory_order_relaxed); |
| 228 | } |
| 229 | |
| 230 | uptr Get(AllocatorStat i) const { |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 231 | return atomic_load(&stats_[i], memory_order_relaxed); |
| 232 | } |
| 233 | |
| 234 | private: |
| 235 | friend class AllocatorGlobalStats; |
| 236 | AllocatorStats *next_; |
| 237 | AllocatorStats *prev_; |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 238 | atomic_uintptr_t stats_[AllocatorStatCount]; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 239 | }; |
| 240 | |
| 241 | // Global stats, used for aggregation and querying. |
| 242 | class AllocatorGlobalStats : public AllocatorStats { |
| 243 | public: |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 244 | void InitLinkerInitialized() { |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 245 | next_ = this; |
| 246 | prev_ = this; |
| 247 | } |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 248 | void Init() { |
| 249 | internal_memset(this, 0, sizeof(*this)); |
| 250 | InitLinkerInitialized(); |
| 251 | } |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 252 | |
| 253 | void Register(AllocatorStats *s) { |
| 254 | SpinMutexLock l(&mu_); |
| 255 | s->next_ = next_; |
| 256 | s->prev_ = this; |
| 257 | next_->prev_ = s; |
| 258 | next_ = s; |
| 259 | } |
| 260 | |
| 261 | void Unregister(AllocatorStats *s) { |
| 262 | SpinMutexLock l(&mu_); |
| 263 | s->prev_->next_ = s->next_; |
| 264 | s->next_->prev_ = s->prev_; |
| 265 | for (int i = 0; i < AllocatorStatCount; i++) |
| 266 | Add(AllocatorStat(i), s->Get(AllocatorStat(i))); |
| 267 | } |
| 268 | |
| 269 | void Get(AllocatorStatCounters s) const { |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 270 | internal_memset(s, 0, AllocatorStatCount * sizeof(uptr)); |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 271 | SpinMutexLock l(&mu_); |
| 272 | const AllocatorStats *stats = this; |
| 273 | for (;;) { |
| 274 | for (int i = 0; i < AllocatorStatCount; i++) |
| 275 | s[i] += stats->Get(AllocatorStat(i)); |
| 276 | stats = stats->next_; |
| 277 | if (stats == this) |
| 278 | break; |
| 279 | } |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 280 | // All stats must be non-negative. |
| 281 | for (int i = 0; i < AllocatorStatCount; i++) |
| 282 | s[i] = ((sptr)s[i]) >= 0 ? s[i] : 0; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 283 | } |
| 284 | |
| 285 | private: |
| 286 | mutable SpinMutex mu_; |
| 287 | }; |
| 288 | |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 289 | // Allocators call these callbacks on mmap/munmap. |
| 290 | struct NoOpMapUnmapCallback { |
| 291 | void OnMap(uptr p, uptr size) const { } |
| 292 | void OnUnmap(uptr p, uptr size) const { } |
| 293 | }; |
| 294 | |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 295 | // Callback type for iterating over chunks. |
| 296 | typedef void (*ForEachChunkCallback)(uptr chunk, void *arg); |
| 297 | |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 298 | // SizeClassAllocator64 -- allocator for 64-bit address space. |
| 299 | // |
| 300 | // Space: a portion of address space of kSpaceSize bytes starting at |
| 301 | // a fixed address (kSpaceBeg). Both constants are powers of two and |
| 302 | // kSpaceBeg is kSpaceSize-aligned. |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 303 | // At the beginning the entire space is mprotect-ed, then small parts of it |
| 304 | // are mapped on demand. |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 305 | // |
| 306 | // Region: a part of Space dedicated to a single size class. |
| 307 | // There are kNumClasses Regions of equal size. |
| 308 | // |
| 309 | // UserChunk: a piece of memory returned to user. |
| 310 | // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk. |
| 311 | // |
| 312 | // A Region looks like this: |
| 313 | // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 |
| 314 | template <const uptr kSpaceBeg, const uptr kSpaceSize, |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 315 | const uptr kMetadataSize, class SizeClassMap, |
| 316 | class MapUnmapCallback = NoOpMapUnmapCallback> |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 317 | class SizeClassAllocator64 { |
| 318 | public: |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 319 | typedef typename SizeClassMap::TransferBatch Batch; |
| 320 | typedef SizeClassAllocator64<kSpaceBeg, kSpaceSize, kMetadataSize, |
| 321 | SizeClassMap, MapUnmapCallback> ThisT; |
| 322 | typedef SizeClassAllocatorLocalCache<ThisT> AllocatorCache; |
| 323 | |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 324 | void Init() { |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 325 | CHECK_EQ(kSpaceBeg, |
Pirama Arumuga Nainar | 259f706 | 2015-05-06 11:49:53 -0700 | [diff] [blame] | 326 | reinterpret_cast<uptr>(MmapNoAccess(kSpaceBeg, kSpaceSize))); |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 327 | MapWithCallback(kSpaceEnd, AdditionalSize()); |
| 328 | } |
| 329 | |
| 330 | void MapWithCallback(uptr beg, uptr size) { |
Kostya Serebryany | 9bfe78f | 2012-12-13 05:36:00 +0000 | [diff] [blame] | 331 | CHECK_EQ(beg, reinterpret_cast<uptr>(MmapFixedOrDie(beg, size))); |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 332 | MapUnmapCallback().OnMap(beg, size); |
| 333 | } |
| 334 | |
| 335 | void UnmapWithCallback(uptr beg, uptr size) { |
| 336 | MapUnmapCallback().OnUnmap(beg, size); |
| 337 | UnmapOrDie(reinterpret_cast<void *>(beg), size); |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 338 | } |
| 339 | |
Kostya Serebryany | f1877cf | 2012-12-25 09:40:20 +0000 | [diff] [blame] | 340 | static bool CanAllocate(uptr size, uptr alignment) { |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 341 | return size <= SizeClassMap::kMaxSize && |
| 342 | alignment <= SizeClassMap::kMaxSize; |
| 343 | } |
| 344 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 345 | NOINLINE Batch* AllocateBatch(AllocatorStats *stat, AllocatorCache *c, |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 346 | uptr class_id) { |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 347 | CHECK_LT(class_id, kNumClasses); |
| 348 | RegionInfo *region = GetRegionInfo(class_id); |
Dmitry Vyukov | b48224c | 2013-01-14 08:23:34 +0000 | [diff] [blame] | 349 | Batch *b = region->free_list.Pop(); |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 350 | if (!b) |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 351 | b = PopulateFreeList(stat, c, class_id, region); |
Dmitry Vyukov | d618867 | 2013-01-14 08:51:08 +0000 | [diff] [blame] | 352 | region->n_allocated += b->count; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 353 | return b; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 354 | } |
| 355 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 356 | NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id, Batch *b) { |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 357 | RegionInfo *region = GetRegionInfo(class_id); |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 358 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | b48224c | 2013-01-14 08:23:34 +0000 | [diff] [blame] | 359 | region->free_list.Push(b); |
Dmitry Vyukov | d618867 | 2013-01-14 08:51:08 +0000 | [diff] [blame] | 360 | region->n_freed += b->count; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 361 | } |
| 362 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 363 | static bool PointerIsMine(const void *p) { |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 364 | return reinterpret_cast<uptr>(p) / kSpaceSize == kSpaceBeg / kSpaceSize; |
| 365 | } |
| 366 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 367 | static uptr GetSizeClass(const void *p) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 368 | return (reinterpret_cast<uptr>(p) / kRegionSize) % kNumClassesRounded; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 369 | } |
| 370 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 371 | void *GetBlockBegin(const void *p) { |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 372 | uptr class_id = GetSizeClass(p); |
| 373 | uptr size = SizeClassMap::Size(class_id); |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 374 | if (!size) return nullptr; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 375 | uptr chunk_idx = GetChunkIdx((uptr)p, size); |
| 376 | uptr reg_beg = (uptr)p & ~(kRegionSize - 1); |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 377 | uptr beg = chunk_idx * size; |
| 378 | uptr next_beg = beg + size; |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 379 | if (class_id >= kNumClasses) return nullptr; |
Kostya Serebryany | 2592d76 | 2012-12-19 08:32:50 +0000 | [diff] [blame] | 380 | RegionInfo *region = GetRegionInfo(class_id); |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 381 | if (region->mapped_user >= next_beg) |
| 382 | return reinterpret_cast<void*>(reg_beg + beg); |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 383 | return nullptr; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 384 | } |
| 385 | |
| 386 | static uptr GetActuallyAllocatedSize(void *p) { |
| 387 | CHECK(PointerIsMine(p)); |
| 388 | return SizeClassMap::Size(GetSizeClass(p)); |
| 389 | } |
| 390 | |
| 391 | uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } |
| 392 | |
Evgeniy Stepanov | 5c48a8c | 2013-08-02 14:26:58 +0000 | [diff] [blame] | 393 | void *GetMetaData(const void *p) { |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 394 | uptr class_id = GetSizeClass(p); |
| 395 | uptr size = SizeClassMap::Size(class_id); |
| 396 | uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size); |
| 397 | return reinterpret_cast<void*>(kSpaceBeg + (kRegionSize * (class_id + 1)) - |
| 398 | (1 + chunk_idx) * kMetadataSize); |
| 399 | } |
| 400 | |
| 401 | uptr TotalMemoryUsed() { |
| 402 | uptr res = 0; |
| 403 | for (uptr i = 0; i < kNumClasses; i++) |
| 404 | res += GetRegionInfo(i)->allocated_user; |
| 405 | return res; |
| 406 | } |
| 407 | |
| 408 | // Test-only. |
| 409 | void TestOnlyUnmap() { |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 410 | UnmapWithCallback(kSpaceBeg, kSpaceSize + AdditionalSize()); |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 411 | } |
| 412 | |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 413 | void PrintStats() { |
| 414 | uptr total_mapped = 0; |
| 415 | uptr n_allocated = 0; |
| 416 | uptr n_freed = 0; |
| 417 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) { |
| 418 | RegionInfo *region = GetRegionInfo(class_id); |
| 419 | total_mapped += region->mapped_user; |
| 420 | n_allocated += region->n_allocated; |
| 421 | n_freed += region->n_freed; |
| 422 | } |
| 423 | Printf("Stats: SizeClassAllocator64: %zdM mapped in %zd allocations; " |
| 424 | "remains %zd\n", |
| 425 | total_mapped >> 20, n_allocated, n_allocated - n_freed); |
| 426 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) { |
| 427 | RegionInfo *region = GetRegionInfo(class_id); |
| 428 | if (region->mapped_user == 0) continue; |
| 429 | Printf(" %02zd (%zd): total: %zd K allocs: %zd remains: %zd\n", |
| 430 | class_id, |
| 431 | SizeClassMap::Size(class_id), |
| 432 | region->mapped_user >> 10, |
| 433 | region->n_allocated, |
| 434 | region->n_allocated - region->n_freed); |
| 435 | } |
| 436 | } |
| 437 | |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 438 | // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone |
| 439 | // introspection API. |
| 440 | void ForceLock() { |
| 441 | for (uptr i = 0; i < kNumClasses; i++) { |
| 442 | GetRegionInfo(i)->mutex.Lock(); |
Alexander Potapenko | 3c5ebf6 | 2013-02-07 14:58:04 +0000 | [diff] [blame] | 443 | } |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 444 | } |
| 445 | |
| 446 | void ForceUnlock() { |
| 447 | for (int i = (int)kNumClasses - 1; i >= 0; i--) { |
| 448 | GetRegionInfo(i)->mutex.Unlock(); |
Alexander Potapenko | 3c5ebf6 | 2013-02-07 14:58:04 +0000 | [diff] [blame] | 449 | } |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 450 | } |
| 451 | |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 452 | // Iterate over all existing chunks. |
| 453 | // The allocator must be locked when calling this function. |
| 454 | void ForEachChunk(ForEachChunkCallback callback, void *arg) { |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 455 | for (uptr class_id = 1; class_id < kNumClasses; class_id++) { |
| 456 | RegionInfo *region = GetRegionInfo(class_id); |
| 457 | uptr chunk_size = SizeClassMap::Size(class_id); |
| 458 | uptr region_beg = kSpaceBeg + class_id * kRegionSize; |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 459 | for (uptr chunk = region_beg; |
| 460 | chunk < region_beg + region->allocated_user; |
| 461 | chunk += chunk_size) { |
| 462 | // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); |
| 463 | callback(chunk, arg); |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 464 | } |
| 465 | } |
| 466 | } |
| 467 | |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 468 | static uptr AdditionalSize() { |
| 469 | return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded, |
| 470 | GetPageSizeCached()); |
| 471 | } |
| 472 | |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 473 | typedef SizeClassMap SizeClassMapT; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 474 | static const uptr kNumClasses = SizeClassMap::kNumClasses; |
| 475 | static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 476 | |
| 477 | private: |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 478 | static const uptr kRegionSize = kSpaceSize / kNumClassesRounded; |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 479 | static const uptr kSpaceEnd = kSpaceBeg + kSpaceSize; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 480 | COMPILER_CHECK(kSpaceBeg % kSpaceSize == 0); |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 481 | // kRegionSize must be >= 2^32. |
| 482 | COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); |
| 483 | // Populate the free list with at most this number of bytes at once |
| 484 | // or with one element if its size is greater. |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 485 | static const uptr kPopulateSize = 1 << 14; |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 486 | // Call mmap for user memory with at least this size. |
Kostya Serebryany | ed847e3 | 2013-01-23 14:07:17 +0000 | [diff] [blame] | 487 | static const uptr kUserMapSize = 1 << 16; |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 488 | // Call mmap for metadata memory with at least this size. |
| 489 | static const uptr kMetaMapSize = 1 << 16; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 490 | |
| 491 | struct RegionInfo { |
Dmitry Vyukov | f4f51f2 | 2013-01-14 07:51:39 +0000 | [diff] [blame] | 492 | BlockingMutex mutex; |
Dmitry Vyukov | b48224c | 2013-01-14 08:23:34 +0000 | [diff] [blame] | 493 | LFStack<Batch> free_list; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 494 | uptr allocated_user; // Bytes allocated for user memory. |
| 495 | uptr allocated_meta; // Bytes allocated for metadata. |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 496 | uptr mapped_user; // Bytes mapped for user memory. |
| 497 | uptr mapped_meta; // Bytes mapped for metadata. |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 498 | uptr n_allocated, n_freed; // Just stats. |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 499 | }; |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 500 | COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize); |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 501 | |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 502 | RegionInfo *GetRegionInfo(uptr class_id) { |
| 503 | CHECK_LT(class_id, kNumClasses); |
| 504 | RegionInfo *regions = reinterpret_cast<RegionInfo*>(kSpaceBeg + kSpaceSize); |
| 505 | return ®ions[class_id]; |
| 506 | } |
| 507 | |
| 508 | static uptr GetChunkIdx(uptr chunk, uptr size) { |
Kostya Serebryany | 871b7fd | 2013-05-16 07:11:16 +0000 | [diff] [blame] | 509 | uptr offset = chunk % kRegionSize; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 510 | // Here we divide by a non-constant. This is costly. |
Kostya Serebryany | 871b7fd | 2013-05-16 07:11:16 +0000 | [diff] [blame] | 511 | // size always fits into 32-bits. If the offset fits too, use 32-bit div. |
Kostya Serebryany | c7014ed | 2013-05-16 08:03:26 +0000 | [diff] [blame] | 512 | if (offset >> (SANITIZER_WORDSIZE / 2)) |
Kostya Serebryany | 871b7fd | 2013-05-16 07:11:16 +0000 | [diff] [blame] | 513 | return offset / size; |
| 514 | return (u32)offset / (u32)size; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 515 | } |
| 516 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 517 | NOINLINE Batch* PopulateFreeList(AllocatorStats *stat, AllocatorCache *c, |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 518 | uptr class_id, RegionInfo *region) { |
Dmitry Vyukov | b48224c | 2013-01-14 08:23:34 +0000 | [diff] [blame] | 519 | BlockingMutexLock l(®ion->mutex); |
| 520 | Batch *b = region->free_list.Pop(); |
| 521 | if (b) |
| 522 | return b; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 523 | uptr size = SizeClassMap::Size(class_id); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 524 | uptr count = size < kPopulateSize ? SizeClassMap::MaxCached(class_id) : 1; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 525 | uptr beg_idx = region->allocated_user; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 526 | uptr end_idx = beg_idx + count * size; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 527 | uptr region_beg = kSpaceBeg + kRegionSize * class_id; |
Kostya Serebryany | b1f21c6 | 2012-12-19 06:51:45 +0000 | [diff] [blame] | 528 | if (end_idx + size > region->mapped_user) { |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 529 | // Do the mmap for the user memory. |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 530 | uptr map_size = kUserMapSize; |
| 531 | while (end_idx + size > region->mapped_user + map_size) |
| 532 | map_size += kUserMapSize; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 533 | CHECK_GE(region->mapped_user + map_size, end_idx); |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 534 | MapWithCallback(region_beg + region->mapped_user, map_size); |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 535 | stat->Add(AllocatorStatMapped, map_size); |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 536 | region->mapped_user += map_size; |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 537 | } |
Dmitry Vyukov | 8ef9ac9 | 2013-01-14 10:49:11 +0000 | [diff] [blame] | 538 | uptr total_count = (region->mapped_user - beg_idx - size) |
| 539 | / size / count * count; |
| 540 | region->allocated_meta += total_count * kMetadataSize; |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 541 | if (region->allocated_meta > region->mapped_meta) { |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 542 | uptr map_size = kMetaMapSize; |
| 543 | while (region->allocated_meta > region->mapped_meta + map_size) |
| 544 | map_size += kMetaMapSize; |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 545 | // Do the mmap for the metadata. |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 546 | CHECK_GE(region->mapped_meta + map_size, region->allocated_meta); |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 547 | MapWithCallback(region_beg + kRegionSize - |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 548 | region->mapped_meta - map_size, map_size); |
| 549 | region->mapped_meta += map_size; |
Kostya Serebryany | 567ad07 | 2012-12-13 05:05:11 +0000 | [diff] [blame] | 550 | } |
Kostya Serebryany | aaf7210 | 2012-12-21 13:38:05 +0000 | [diff] [blame] | 551 | CHECK_LE(region->allocated_meta, region->mapped_meta); |
Sergey Matveev | f14ef72 | 2013-05-16 12:58:34 +0000 | [diff] [blame] | 552 | if (region->mapped_user + region->mapped_meta > kRegionSize) { |
Kostya Serebryany | d39a34e | 2013-03-14 13:16:09 +0000 | [diff] [blame] | 553 | Printf("%s: Out of memory. Dying. ", SanitizerToolName); |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 554 | Printf("The process has exhausted %zuMB for size class %zu.\n", |
| 555 | kRegionSize / 1024 / 1024, size); |
| 556 | Die(); |
| 557 | } |
Dmitry Vyukov | 8ef9ac9 | 2013-01-14 10:49:11 +0000 | [diff] [blame] | 558 | for (;;) { |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 559 | if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) |
Dmitry Vyukov | 8ef9ac9 | 2013-01-14 10:49:11 +0000 | [diff] [blame] | 560 | b = (Batch*)c->Allocate(this, SizeClassMap::ClassID(sizeof(Batch))); |
| 561 | else |
| 562 | b = (Batch*)(region_beg + beg_idx); |
| 563 | b->count = count; |
| 564 | for (uptr i = 0; i < count; i++) |
| 565 | b->batch[i] = (void*)(region_beg + beg_idx + i * size); |
| 566 | region->allocated_user += count * size; |
| 567 | CHECK_LE(region->allocated_user, region->mapped_user); |
| 568 | beg_idx += count * size; |
| 569 | if (beg_idx + count * size + size > region->mapped_user) |
| 570 | break; |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 571 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | 8ef9ac9 | 2013-01-14 10:49:11 +0000 | [diff] [blame] | 572 | region->free_list.Push(b); |
| 573 | } |
Dmitry Vyukov | b48224c | 2013-01-14 08:23:34 +0000 | [diff] [blame] | 574 | return b; |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 575 | } |
Kostya Serebryany | 72166ca | 2012-12-05 10:09:15 +0000 | [diff] [blame] | 576 | }; |
| 577 | |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 578 | // Maps integers in rage [0, kSize) to u8 values. |
| 579 | template<u64 kSize> |
| 580 | class FlatByteMap { |
| 581 | public: |
| 582 | void TestOnlyInit() { |
| 583 | internal_memset(map_, 0, sizeof(map_)); |
| 584 | } |
| 585 | |
| 586 | void set(uptr idx, u8 val) { |
| 587 | CHECK_LT(idx, kSize); |
| 588 | CHECK_EQ(0U, map_[idx]); |
| 589 | map_[idx] = val; |
| 590 | } |
| 591 | u8 operator[] (uptr idx) { |
| 592 | CHECK_LT(idx, kSize); |
| 593 | // FIXME: CHECK may be too expensive here. |
| 594 | return map_[idx]; |
| 595 | } |
| 596 | private: |
| 597 | u8 map_[kSize]; |
| 598 | }; |
| 599 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 600 | // TwoLevelByteMap maps integers in range [0, kSize1*kSize2) to u8 values. |
| 601 | // It is implemented as a two-dimensional array: array of kSize1 pointers |
| 602 | // to kSize2-byte arrays. The secondary arrays are mmaped on demand. |
| 603 | // Each value is initially zero and can be set to something else only once. |
| 604 | // Setting and getting values from multiple threads is safe w/o extra locking. |
| 605 | template <u64 kSize1, u64 kSize2, class MapUnmapCallback = NoOpMapUnmapCallback> |
| 606 | class TwoLevelByteMap { |
| 607 | public: |
| 608 | void TestOnlyInit() { |
| 609 | internal_memset(map1_, 0, sizeof(map1_)); |
| 610 | mu_.Init(); |
| 611 | } |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 612 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 613 | void TestOnlyUnmap() { |
| 614 | for (uptr i = 0; i < kSize1; i++) { |
| 615 | u8 *p = Get(i); |
| 616 | if (!p) continue; |
| 617 | MapUnmapCallback().OnUnmap(reinterpret_cast<uptr>(p), kSize2); |
| 618 | UnmapOrDie(p, kSize2); |
| 619 | } |
| 620 | } |
| 621 | |
| 622 | uptr size() const { return kSize1 * kSize2; } |
| 623 | uptr size1() const { return kSize1; } |
| 624 | uptr size2() const { return kSize2; } |
| 625 | |
| 626 | void set(uptr idx, u8 val) { |
| 627 | CHECK_LT(idx, kSize1 * kSize2); |
| 628 | u8 *map2 = GetOrCreate(idx / kSize2); |
| 629 | CHECK_EQ(0U, map2[idx % kSize2]); |
| 630 | map2[idx % kSize2] = val; |
| 631 | } |
| 632 | |
| 633 | u8 operator[] (uptr idx) const { |
| 634 | CHECK_LT(idx, kSize1 * kSize2); |
| 635 | u8 *map2 = Get(idx / kSize2); |
| 636 | if (!map2) return 0; |
| 637 | return map2[idx % kSize2]; |
| 638 | } |
| 639 | |
| 640 | private: |
| 641 | u8 *Get(uptr idx) const { |
| 642 | CHECK_LT(idx, kSize1); |
| 643 | return reinterpret_cast<u8 *>( |
| 644 | atomic_load(&map1_[idx], memory_order_acquire)); |
| 645 | } |
| 646 | |
| 647 | u8 *GetOrCreate(uptr idx) { |
| 648 | u8 *res = Get(idx); |
| 649 | if (!res) { |
| 650 | SpinMutexLock l(&mu_); |
| 651 | if (!(res = Get(idx))) { |
| 652 | res = (u8*)MmapOrDie(kSize2, "TwoLevelByteMap"); |
| 653 | MapUnmapCallback().OnMap(reinterpret_cast<uptr>(res), kSize2); |
| 654 | atomic_store(&map1_[idx], reinterpret_cast<uptr>(res), |
| 655 | memory_order_release); |
| 656 | } |
| 657 | } |
| 658 | return res; |
| 659 | } |
| 660 | |
| 661 | atomic_uintptr_t map1_[kSize1]; |
| 662 | StaticSpinMutex mu_; |
| 663 | }; |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 664 | |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 665 | // SizeClassAllocator32 -- allocator for 32-bit address space. |
| 666 | // This allocator can theoretically be used on 64-bit arch, but there it is less |
| 667 | // efficient than SizeClassAllocator64. |
| 668 | // |
| 669 | // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can |
| 670 | // be returned by MmapOrDie(). |
| 671 | // |
| 672 | // Region: |
| 673 | // a result of a single call to MmapAlignedOrDie(kRegionSize, kRegionSize). |
| 674 | // Since the regions are aligned by kRegionSize, there are exactly |
| 675 | // kNumPossibleRegions possible regions in the address space and so we keep |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 676 | // a ByteMap possible_regions to store the size classes of each Region. |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 677 | // 0 size class means the region is not used by the allocator. |
| 678 | // |
| 679 | // One Region is used to allocate chunks of a single size class. |
| 680 | // A Region looks like this: |
| 681 | // UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1 |
| 682 | // |
| 683 | // In order to avoid false sharing the objects of this class should be |
| 684 | // chache-line aligned. |
| 685 | template <const uptr kSpaceBeg, const u64 kSpaceSize, |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 686 | const uptr kMetadataSize, class SizeClassMap, |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 687 | const uptr kRegionSizeLog, |
| 688 | class ByteMap, |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 689 | class MapUnmapCallback = NoOpMapUnmapCallback> |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 690 | class SizeClassAllocator32 { |
| 691 | public: |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 692 | typedef typename SizeClassMap::TransferBatch Batch; |
| 693 | typedef SizeClassAllocator32<kSpaceBeg, kSpaceSize, kMetadataSize, |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 694 | SizeClassMap, kRegionSizeLog, ByteMap, MapUnmapCallback> ThisT; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 695 | typedef SizeClassAllocatorLocalCache<ThisT> AllocatorCache; |
| 696 | |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 697 | void Init() { |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 698 | possible_regions.TestOnlyInit(); |
| 699 | internal_memset(size_class_info_array, 0, sizeof(size_class_info_array)); |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 700 | } |
| 701 | |
| 702 | void *MapWithCallback(uptr size) { |
| 703 | size = RoundUpTo(size, GetPageSizeCached()); |
| 704 | void *res = MmapOrDie(size, "SizeClassAllocator32"); |
| 705 | MapUnmapCallback().OnMap((uptr)res, size); |
| 706 | return res; |
| 707 | } |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 708 | |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 709 | void UnmapWithCallback(uptr beg, uptr size) { |
| 710 | MapUnmapCallback().OnUnmap(beg, size); |
| 711 | UnmapOrDie(reinterpret_cast<void *>(beg), size); |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 712 | } |
| 713 | |
Kostya Serebryany | f1877cf | 2012-12-25 09:40:20 +0000 | [diff] [blame] | 714 | static bool CanAllocate(uptr size, uptr alignment) { |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 715 | return size <= SizeClassMap::kMaxSize && |
| 716 | alignment <= SizeClassMap::kMaxSize; |
| 717 | } |
| 718 | |
Evgeniy Stepanov | 5c48a8c | 2013-08-02 14:26:58 +0000 | [diff] [blame] | 719 | void *GetMetaData(const void *p) { |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 720 | CHECK(PointerIsMine(p)); |
| 721 | uptr mem = reinterpret_cast<uptr>(p); |
| 722 | uptr beg = ComputeRegionBeg(mem); |
| 723 | uptr size = SizeClassMap::Size(GetSizeClass(p)); |
| 724 | u32 offset = mem - beg; |
| 725 | uptr n = offset / (u32)size; // 32-bit division |
| 726 | uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize; |
Kostya Serebryany | 8a41bdc | 2012-12-06 13:13:58 +0000 | [diff] [blame] | 727 | return reinterpret_cast<void*>(meta); |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 728 | } |
| 729 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 730 | NOINLINE Batch* AllocateBatch(AllocatorStats *stat, AllocatorCache *c, |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 731 | uptr class_id) { |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 732 | CHECK_LT(class_id, kNumClasses); |
Kostya Serebryany | 674d05c | 2012-12-06 14:27:32 +0000 | [diff] [blame] | 733 | SizeClassInfo *sci = GetSizeClassInfo(class_id); |
| 734 | SpinMutexLock l(&sci->mutex); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 735 | if (sci->free_list.empty()) |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 736 | PopulateFreeList(stat, c, sci, class_id); |
Kostya Serebryany | 674d05c | 2012-12-06 14:27:32 +0000 | [diff] [blame] | 737 | CHECK(!sci->free_list.empty()); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 738 | Batch *b = sci->free_list.front(); |
| 739 | sci->free_list.pop_front(); |
| 740 | return b; |
Kostya Serebryany | 674d05c | 2012-12-06 14:27:32 +0000 | [diff] [blame] | 741 | } |
| 742 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 743 | NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id, Batch *b) { |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 744 | CHECK_LT(class_id, kNumClasses); |
Kostya Serebryany | 674d05c | 2012-12-06 14:27:32 +0000 | [diff] [blame] | 745 | SizeClassInfo *sci = GetSizeClassInfo(class_id); |
| 746 | SpinMutexLock l(&sci->mutex); |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 747 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 748 | sci->free_list.push_front(b); |
Kostya Serebryany | 674d05c | 2012-12-06 14:27:32 +0000 | [diff] [blame] | 749 | } |
| 750 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 751 | bool PointerIsMine(const void *p) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 752 | return GetSizeClass(p) != 0; |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 753 | } |
| 754 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 755 | uptr GetSizeClass(const void *p) { |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 756 | return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))]; |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 757 | } |
| 758 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 759 | void *GetBlockBegin(const void *p) { |
Kostya Serebryany | 8a41bdc | 2012-12-06 13:13:58 +0000 | [diff] [blame] | 760 | CHECK(PointerIsMine(p)); |
| 761 | uptr mem = reinterpret_cast<uptr>(p); |
| 762 | uptr beg = ComputeRegionBeg(mem); |
| 763 | uptr size = SizeClassMap::Size(GetSizeClass(p)); |
| 764 | u32 offset = mem - beg; |
| 765 | u32 n = offset / (u32)size; // 32-bit division |
| 766 | uptr res = beg + (n * (u32)size); |
| 767 | return reinterpret_cast<void*>(res); |
| 768 | } |
| 769 | |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 770 | uptr GetActuallyAllocatedSize(void *p) { |
| 771 | CHECK(PointerIsMine(p)); |
| 772 | return SizeClassMap::Size(GetSizeClass(p)); |
| 773 | } |
| 774 | |
Kostya Serebryany | 674d05c | 2012-12-06 14:27:32 +0000 | [diff] [blame] | 775 | uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } |
| 776 | |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 777 | uptr TotalMemoryUsed() { |
| 778 | // No need to lock here. |
| 779 | uptr res = 0; |
| 780 | for (uptr i = 0; i < kNumPossibleRegions; i++) |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 781 | if (possible_regions[i]) |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 782 | res += kRegionSize; |
| 783 | return res; |
| 784 | } |
| 785 | |
| 786 | void TestOnlyUnmap() { |
| 787 | for (uptr i = 0; i < kNumPossibleRegions; i++) |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 788 | if (possible_regions[i]) |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 789 | UnmapWithCallback((i * kRegionSize), kRegionSize); |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 790 | } |
| 791 | |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 792 | // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone |
| 793 | // introspection API. |
| 794 | void ForceLock() { |
Alexander Potapenko | aeedfd6 | 2013-02-07 12:00:40 +0000 | [diff] [blame] | 795 | for (uptr i = 0; i < kNumClasses; i++) { |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 796 | GetSizeClassInfo(i)->mutex.Lock(); |
Alexander Potapenko | 3c5ebf6 | 2013-02-07 14:58:04 +0000 | [diff] [blame] | 797 | } |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 798 | } |
| 799 | |
| 800 | void ForceUnlock() { |
| 801 | for (int i = kNumClasses - 1; i >= 0; i--) { |
| 802 | GetSizeClassInfo(i)->mutex.Unlock(); |
Alexander Potapenko | 3c5ebf6 | 2013-02-07 14:58:04 +0000 | [diff] [blame] | 803 | } |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 804 | } |
| 805 | |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 806 | // Iterate over all existing chunks. |
| 807 | // The allocator must be locked when calling this function. |
| 808 | void ForEachChunk(ForEachChunkCallback callback, void *arg) { |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 809 | for (uptr region = 0; region < kNumPossibleRegions; region++) |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 810 | if (possible_regions[region]) { |
| 811 | uptr chunk_size = SizeClassMap::Size(possible_regions[region]); |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 812 | uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize); |
| 813 | uptr region_beg = region * kRegionSize; |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 814 | for (uptr chunk = region_beg; |
| 815 | chunk < region_beg + max_chunks_in_region * chunk_size; |
| 816 | chunk += chunk_size) { |
| 817 | // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); |
| 818 | callback(chunk, arg); |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 819 | } |
| 820 | } |
| 821 | } |
| 822 | |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 823 | void PrintStats() { |
| 824 | } |
| 825 | |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 826 | static uptr AdditionalSize() { |
| 827 | return 0; |
| 828 | } |
| 829 | |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 830 | typedef SizeClassMap SizeClassMapT; |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 831 | static const uptr kNumClasses = SizeClassMap::kNumClasses; |
Kostya Serebryany | 19313d9 | 2012-12-07 09:40:17 +0000 | [diff] [blame] | 832 | |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 833 | private: |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 834 | static const uptr kRegionSize = 1 << kRegionSizeLog; |
| 835 | static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize; |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 836 | |
| 837 | struct SizeClassInfo { |
| 838 | SpinMutex mutex; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 839 | IntrusiveList<Batch> free_list; |
| 840 | char padding[kCacheLineSize - sizeof(uptr) - sizeof(IntrusiveList<Batch>)]; |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 841 | }; |
| 842 | COMPILER_CHECK(sizeof(SizeClassInfo) == kCacheLineSize); |
| 843 | |
| 844 | uptr ComputeRegionId(uptr mem) { |
| 845 | uptr res = mem >> kRegionSizeLog; |
| 846 | CHECK_LT(res, kNumPossibleRegions); |
| 847 | return res; |
| 848 | } |
| 849 | |
| 850 | uptr ComputeRegionBeg(uptr mem) { |
| 851 | return mem & ~(kRegionSize - 1); |
| 852 | } |
| 853 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 854 | uptr AllocateRegion(AllocatorStats *stat, uptr class_id) { |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 855 | CHECK_LT(class_id, kNumClasses); |
| 856 | uptr res = reinterpret_cast<uptr>(MmapAlignedOrDie(kRegionSize, kRegionSize, |
| 857 | "SizeClassAllocator32")); |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 858 | MapUnmapCallback().OnMap(res, kRegionSize); |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 859 | stat->Add(AllocatorStatMapped, kRegionSize); |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 860 | CHECK_EQ(0U, (res & (kRegionSize - 1))); |
Timur Iskhodzhanov | 5e97ba3 | 2013-05-29 14:11:44 +0000 | [diff] [blame] | 861 | possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id)); |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 862 | return res; |
| 863 | } |
| 864 | |
| 865 | SizeClassInfo *GetSizeClassInfo(uptr class_id) { |
| 866 | CHECK_LT(class_id, kNumClasses); |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 867 | return &size_class_info_array[class_id]; |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 868 | } |
| 869 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 870 | void PopulateFreeList(AllocatorStats *stat, AllocatorCache *c, |
| 871 | SizeClassInfo *sci, uptr class_id) { |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 872 | uptr size = SizeClassMap::Size(class_id); |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 873 | uptr reg = AllocateRegion(stat, class_id); |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 874 | uptr n_chunks = kRegionSize / (size + kMetadataSize); |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 875 | uptr max_count = SizeClassMap::MaxCached(class_id); |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 876 | Batch *b = nullptr; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 877 | for (uptr i = reg; i < reg + n_chunks * size; i += size) { |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 878 | if (!b) { |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 879 | if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 880 | b = (Batch*)c->Allocate(this, SizeClassMap::ClassID(sizeof(Batch))); |
| 881 | else |
| 882 | b = (Batch*)i; |
| 883 | b->count = 0; |
| 884 | } |
| 885 | b->batch[b->count++] = (void*)i; |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 886 | if (b->count == max_count) { |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 887 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 888 | sci->free_list.push_back(b); |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 889 | b = nullptr; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 890 | } |
| 891 | } |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 892 | if (b) { |
| 893 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 894 | sci->free_list.push_back(b); |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 895 | } |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 896 | } |
| 897 | |
Kostya Serebryany | 1b54cbf | 2013-05-20 07:29:21 +0000 | [diff] [blame] | 898 | ByteMap possible_regions; |
| 899 | SizeClassInfo size_class_info_array[kNumClasses]; |
Kostya Serebryany | 45595ba | 2012-12-06 12:49:28 +0000 | [diff] [blame] | 900 | }; |
| 901 | |
Dmitry Vyukov | 3bf34d6 | 2013-01-10 13:06:35 +0000 | [diff] [blame] | 902 | // Objects of this type should be used as local caches for SizeClassAllocator64 |
| 903 | // or SizeClassAllocator32. Since the typical use of this class is to have one |
| 904 | // object per thread in TLS, is has to be POD. |
Kostya Serebryany | 82de942 | 2012-12-04 14:15:17 +0000 | [diff] [blame] | 905 | template<class SizeClassAllocator> |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 906 | struct SizeClassAllocatorLocalCache { |
Kostya Serebryany | cd815ad | 2012-12-04 13:59:22 +0000 | [diff] [blame] | 907 | typedef SizeClassAllocator Allocator; |
Kostya Serebryany | 82de942 | 2012-12-04 14:15:17 +0000 | [diff] [blame] | 908 | static const uptr kNumClasses = SizeClassAllocator::kNumClasses; |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 909 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 910 | void Init(AllocatorGlobalStats *s) { |
| 911 | stats_.Init(); |
| 912 | if (s) |
| 913 | s->Register(&stats_); |
| 914 | } |
| 915 | |
| 916 | void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) { |
| 917 | Drain(allocator); |
| 918 | if (s) |
| 919 | s->Unregister(&stats_); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 920 | } |
| 921 | |
| 922 | void *Allocate(SizeClassAllocator *allocator, uptr class_id) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 923 | CHECK_NE(class_id, 0UL); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 924 | CHECK_LT(class_id, kNumClasses); |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 925 | stats_.Add(AllocatorStatAllocated, SizeClassMap::Size(class_id)); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 926 | PerClass *c = &per_class_[class_id]; |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 927 | if (UNLIKELY(c->count == 0)) |
| 928 | Refill(allocator, class_id); |
| 929 | void *res = c->batch[--c->count]; |
| 930 | PREFETCH(c->batch[c->count - 1]); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 931 | return res; |
| 932 | } |
| 933 | |
| 934 | void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) { |
Kostya Serebryany | 038820f | 2012-12-24 13:41:07 +0000 | [diff] [blame] | 935 | CHECK_NE(class_id, 0UL); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 936 | CHECK_LT(class_id, kNumClasses); |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 937 | // If the first allocator call on a new thread is a deallocation, then |
| 938 | // max_count will be zero, leading to check failure. |
| 939 | InitCache(); |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 940 | stats_.Sub(AllocatorStatAllocated, SizeClassMap::Size(class_id)); |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 941 | PerClass *c = &per_class_[class_id]; |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 942 | CHECK_NE(c->max_count, 0UL); |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 943 | if (UNLIKELY(c->count == c->max_count)) |
| 944 | Drain(allocator, class_id); |
| 945 | c->batch[c->count++] = p; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 946 | } |
| 947 | |
| 948 | void Drain(SizeClassAllocator *allocator) { |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 949 | for (uptr class_id = 0; class_id < kNumClasses; class_id++) { |
| 950 | PerClass *c = &per_class_[class_id]; |
| 951 | while (c->count > 0) |
| 952 | Drain(allocator, class_id); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 953 | } |
| 954 | } |
| 955 | |
| 956 | // private: |
| 957 | typedef typename SizeClassAllocator::SizeClassMapT SizeClassMap; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 958 | typedef typename SizeClassMap::TransferBatch Batch; |
| 959 | struct PerClass { |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 960 | uptr count; |
| 961 | uptr max_count; |
| 962 | void *batch[2 * SizeClassMap::kMaxNumCached]; |
Dmitry Vyukov | a343ca0 | 2013-01-11 16:41:19 +0000 | [diff] [blame] | 963 | }; |
| 964 | PerClass per_class_[kNumClasses]; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 965 | AllocatorStats stats_; |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 966 | |
| 967 | void InitCache() { |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 968 | if (per_class_[1].max_count) |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 969 | return; |
| 970 | for (uptr i = 0; i < kNumClasses; i++) { |
| 971 | PerClass *c = &per_class_[i]; |
| 972 | c->max_count = 2 * SizeClassMap::MaxCached(i); |
| 973 | } |
| 974 | } |
| 975 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 976 | NOINLINE void Refill(SizeClassAllocator *allocator, uptr class_id) { |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 977 | InitCache(); |
| 978 | PerClass *c = &per_class_[class_id]; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 979 | Batch *b = allocator->AllocateBatch(&stats_, this, class_id); |
| 980 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 981 | for (uptr i = 0; i < b->count; i++) |
| 982 | c->batch[i] = b->batch[i]; |
| 983 | c->count = b->count; |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 984 | if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 985 | Deallocate(allocator, SizeClassMap::ClassID(sizeof(Batch)), b); |
| 986 | } |
| 987 | |
Timur Iskhodzhanov | 53becd8 | 2013-01-28 17:29:50 +0000 | [diff] [blame] | 988 | NOINLINE void Drain(SizeClassAllocator *allocator, uptr class_id) { |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 989 | InitCache(); |
| 990 | PerClass *c = &per_class_[class_id]; |
| 991 | Batch *b; |
Kostya Serebryany | 7811b4a | 2013-03-12 07:01:27 +0000 | [diff] [blame] | 992 | if (SizeClassMap::SizeClassRequiresSeparateTransferBatch(class_id)) |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 993 | b = (Batch*)Allocate(allocator, SizeClassMap::ClassID(sizeof(Batch))); |
| 994 | else |
| 995 | b = (Batch*)c->batch[0]; |
| 996 | uptr cnt = Min(c->max_count / 2, c->count); |
| 997 | for (uptr i = 0; i < cnt; i++) { |
| 998 | b->batch[i] = c->batch[i]; |
| 999 | c->batch[i] = c->batch[i + c->max_count / 2]; |
| 1000 | } |
| 1001 | b->count = cnt; |
| 1002 | c->count -= cnt; |
Reid Kleckner | 5d3dcb8 | 2013-03-06 14:54:08 +0000 | [diff] [blame] | 1003 | CHECK_GT(b->count, 0); |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1004 | allocator->DeallocateBatch(&stats_, class_id, b); |
Dmitry Vyukov | ce8674f | 2013-01-15 09:02:20 +0000 | [diff] [blame] | 1005 | } |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1006 | }; |
| 1007 | |
| 1008 | // This class can (de)allocate only large chunks of memory using mmap/unmap. |
| 1009 | // The main purpose of this allocator is to cover large and rare allocation |
| 1010 | // sizes not covered by more efficient allocators (e.g. SizeClassAllocator64). |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 1011 | template <class MapUnmapCallback = NoOpMapUnmapCallback> |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1012 | class LargeMmapAllocator { |
| 1013 | public: |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1014 | void InitLinkerInitialized(bool may_return_null) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1015 | page_size_ = GetPageSizeCached(); |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1016 | atomic_store(&may_return_null_, may_return_null, memory_order_relaxed); |
| 1017 | } |
| 1018 | |
| 1019 | void Init(bool may_return_null) { |
| 1020 | internal_memset(this, 0, sizeof(*this)); |
| 1021 | InitLinkerInitialized(may_return_null); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1022 | } |
Dmitry Vyukov | ce17384 | 2013-01-11 11:15:48 +0000 | [diff] [blame] | 1023 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1024 | void *Allocate(AllocatorStats *stat, uptr size, uptr alignment) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1025 | CHECK(IsPowerOfTwo(alignment)); |
| 1026 | uptr map_size = RoundUpMapSize(size); |
| 1027 | if (alignment > page_size_) |
| 1028 | map_size += alignment; |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1029 | // Overflow. |
| 1030 | if (map_size < size) |
| 1031 | return ReturnNullOrDie(); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1032 | uptr map_beg = reinterpret_cast<uptr>( |
| 1033 | MmapOrDie(map_size, "LargeMmapAllocator")); |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 1034 | CHECK(IsAligned(map_beg, page_size_)); |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 1035 | MapUnmapCallback().OnMap(map_beg, map_size); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1036 | uptr map_end = map_beg + map_size; |
| 1037 | uptr res = map_beg + page_size_; |
| 1038 | if (res & (alignment - 1)) // Align. |
| 1039 | res += alignment - (res & (alignment - 1)); |
Stephen Hines | 6d18623 | 2014-11-26 17:56:19 -0800 | [diff] [blame] | 1040 | CHECK(IsAligned(res, alignment)); |
| 1041 | CHECK(IsAligned(res, page_size_)); |
| 1042 | CHECK_GE(res + size, map_beg); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1043 | CHECK_LE(res + size, map_end); |
| 1044 | Header *h = GetHeader(res); |
| 1045 | h->size = size; |
| 1046 | h->map_beg = map_beg; |
| 1047 | h->map_size = map_size; |
Timur Iskhodzhanov | 2b10d39 | 2013-02-08 12:02:00 +0000 | [diff] [blame] | 1048 | uptr size_log = MostSignificantSetBitIndex(map_size); |
Kostya Serebryany | 800344c | 2013-01-10 13:38:38 +0000 | [diff] [blame] | 1049 | CHECK_LT(size_log, ARRAY_SIZE(stats.by_size_log)); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1050 | { |
| 1051 | SpinMutexLock l(&mutex_); |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1052 | uptr idx = n_chunks_++; |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1053 | chunks_sorted_ = false; |
Kostya Serebryany | bb5d057 | 2012-12-25 07:50:35 +0000 | [diff] [blame] | 1054 | CHECK_LT(idx, kMaxNumChunks); |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1055 | h->chunk_idx = idx; |
| 1056 | chunks_[idx] = h; |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1057 | stats.n_allocs++; |
| 1058 | stats.currently_allocated += map_size; |
| 1059 | stats.max_allocated = Max(stats.max_allocated, stats.currently_allocated); |
Kostya Serebryany | 800344c | 2013-01-10 13:38:38 +0000 | [diff] [blame] | 1060 | stats.by_size_log[size_log]++; |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 1061 | stat->Add(AllocatorStatAllocated, map_size); |
| 1062 | stat->Add(AllocatorStatMapped, map_size); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1063 | } |
| 1064 | return reinterpret_cast<void*>(res); |
| 1065 | } |
| 1066 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1067 | void *ReturnNullOrDie() { |
| 1068 | if (atomic_load(&may_return_null_, memory_order_acquire)) |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1069 | return nullptr; |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1070 | ReportAllocatorCannotReturnNull(); |
| 1071 | } |
| 1072 | |
| 1073 | void SetMayReturnNull(bool may_return_null) { |
| 1074 | atomic_store(&may_return_null_, may_return_null, memory_order_release); |
| 1075 | } |
| 1076 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1077 | void Deallocate(AllocatorStats *stat, void *p) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1078 | Header *h = GetHeader(p); |
| 1079 | { |
| 1080 | SpinMutexLock l(&mutex_); |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1081 | uptr idx = h->chunk_idx; |
| 1082 | CHECK_EQ(chunks_[idx], h); |
| 1083 | CHECK_LT(idx, n_chunks_); |
| 1084 | chunks_[idx] = chunks_[n_chunks_ - 1]; |
| 1085 | chunks_[idx]->chunk_idx = idx; |
| 1086 | n_chunks_--; |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1087 | chunks_sorted_ = false; |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1088 | stats.n_frees++; |
| 1089 | stats.currently_allocated -= h->map_size; |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 1090 | stat->Sub(AllocatorStatAllocated, h->map_size); |
| 1091 | stat->Sub(AllocatorStatMapped, h->map_size); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1092 | } |
Kostya Serebryany | 214621f | 2012-12-12 14:32:18 +0000 | [diff] [blame] | 1093 | MapUnmapCallback().OnUnmap(h->map_beg, h->map_size); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1094 | UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size); |
| 1095 | } |
| 1096 | |
| 1097 | uptr TotalMemoryUsed() { |
| 1098 | SpinMutexLock l(&mutex_); |
| 1099 | uptr res = 0; |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1100 | for (uptr i = 0; i < n_chunks_; i++) { |
| 1101 | Header *h = chunks_[i]; |
| 1102 | CHECK_EQ(h->chunk_idx, i); |
| 1103 | res += RoundUpMapSize(h->size); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1104 | } |
| 1105 | return res; |
| 1106 | } |
| 1107 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 1108 | bool PointerIsMine(const void *p) { |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1109 | return GetBlockBegin(p) != nullptr; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1110 | } |
| 1111 | |
| 1112 | uptr GetActuallyAllocatedSize(void *p) { |
Kostya Serebryany | da1f82b | 2012-12-18 14:56:38 +0000 | [diff] [blame] | 1113 | return RoundUpTo(GetHeader(p)->size, page_size_); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1114 | } |
| 1115 | |
| 1116 | // At least page_size_/2 metadata bytes is available. |
Evgeniy Stepanov | 5c48a8c | 2013-08-02 14:26:58 +0000 | [diff] [blame] | 1117 | void *GetMetaData(const void *p) { |
Kostya Serebryany | bb5d057 | 2012-12-25 07:50:35 +0000 | [diff] [blame] | 1118 | // Too slow: CHECK_EQ(p, GetBlockBegin(p)); |
Dmitry Vyukov | cde3bae | 2013-08-08 13:47:50 +0000 | [diff] [blame] | 1119 | if (!IsAligned(reinterpret_cast<uptr>(p), page_size_)) { |
| 1120 | Printf("%s: bad pointer %p\n", SanitizerToolName, p); |
| 1121 | CHECK(IsAligned(reinterpret_cast<uptr>(p), page_size_)); |
| 1122 | } |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1123 | return GetHeader(p) + 1; |
| 1124 | } |
| 1125 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 1126 | void *GetBlockBegin(const void *ptr) { |
Kostya Serebryany | da1f82b | 2012-12-18 14:56:38 +0000 | [diff] [blame] | 1127 | uptr p = reinterpret_cast<uptr>(ptr); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1128 | SpinMutexLock l(&mutex_); |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1129 | uptr nearest_chunk = 0; |
| 1130 | // Cache-friendly linear search. |
| 1131 | for (uptr i = 0; i < n_chunks_; i++) { |
| 1132 | uptr ch = reinterpret_cast<uptr>(chunks_[i]); |
| 1133 | if (p < ch) continue; // p is at left to this chunk, skip it. |
| 1134 | if (p - ch < p - nearest_chunk) |
| 1135 | nearest_chunk = ch; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1136 | } |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1137 | if (!nearest_chunk) |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1138 | return nullptr; |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1139 | Header *h = reinterpret_cast<Header *>(nearest_chunk); |
| 1140 | CHECK_GE(nearest_chunk, h->map_beg); |
| 1141 | CHECK_LT(nearest_chunk, h->map_beg + h->map_size); |
| 1142 | CHECK_LE(nearest_chunk, p); |
Kostya Serebryany | a2c1d98 | 2013-04-08 08:43:22 +0000 | [diff] [blame] | 1143 | if (h->map_beg + h->map_size <= p) |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1144 | return nullptr; |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1145 | return GetUser(h); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1146 | } |
| 1147 | |
Sergey Matveev | ba2169a | 2013-05-31 11:13:45 +0000 | [diff] [blame] | 1148 | // This function does the same as GetBlockBegin, but is much faster. |
| 1149 | // Must be called with the allocator locked. |
| 1150 | void *GetBlockBeginFastLocked(void *ptr) { |
Peter Collingbourne | 8f0c5bd | 2013-10-25 23:03:21 +0000 | [diff] [blame] | 1151 | mutex_.CheckLocked(); |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1152 | uptr p = reinterpret_cast<uptr>(ptr); |
| 1153 | uptr n = n_chunks_; |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1154 | if (!n) return nullptr; |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1155 | if (!chunks_sorted_) { |
| 1156 | // Do one-time sort. chunks_sorted_ is reset in Allocate/Deallocate. |
| 1157 | SortArray(reinterpret_cast<uptr*>(chunks_), n); |
| 1158 | for (uptr i = 0; i < n; i++) |
| 1159 | chunks_[i]->chunk_idx = i; |
| 1160 | chunks_sorted_ = true; |
| 1161 | min_mmap_ = reinterpret_cast<uptr>(chunks_[0]); |
| 1162 | max_mmap_ = reinterpret_cast<uptr>(chunks_[n - 1]) + |
| 1163 | chunks_[n - 1]->map_size; |
| 1164 | } |
| 1165 | if (p < min_mmap_ || p >= max_mmap_) |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1166 | return nullptr; |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1167 | uptr beg = 0, end = n - 1; |
| 1168 | // This loop is a log(n) lower_bound. It does not check for the exact match |
| 1169 | // to avoid expensive cache-thrashing loads. |
| 1170 | while (end - beg >= 2) { |
| 1171 | uptr mid = (beg + end) / 2; // Invariant: mid >= beg + 1 |
| 1172 | if (p < reinterpret_cast<uptr>(chunks_[mid])) |
| 1173 | end = mid - 1; // We are not interested in chunks_[mid]. |
| 1174 | else |
| 1175 | beg = mid; // chunks_[mid] may still be what we want. |
| 1176 | } |
| 1177 | |
| 1178 | if (beg < end) { |
| 1179 | CHECK_EQ(beg + 1, end); |
| 1180 | // There are 2 chunks left, choose one. |
| 1181 | if (p >= reinterpret_cast<uptr>(chunks_[end])) |
| 1182 | beg = end; |
| 1183 | } |
| 1184 | |
| 1185 | Header *h = chunks_[beg]; |
| 1186 | if (h->map_beg + h->map_size <= p || p < h->map_beg) |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1187 | return nullptr; |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1188 | return GetUser(h); |
| 1189 | } |
| 1190 | |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1191 | void PrintStats() { |
| 1192 | Printf("Stats: LargeMmapAllocator: allocated %zd times, " |
Kostya Serebryany | 800344c | 2013-01-10 13:38:38 +0000 | [diff] [blame] | 1193 | "remains %zd (%zd K) max %zd M; by size logs: ", |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1194 | stats.n_allocs, stats.n_allocs - stats.n_frees, |
| 1195 | stats.currently_allocated >> 10, stats.max_allocated >> 20); |
Kostya Serebryany | 800344c | 2013-01-10 13:38:38 +0000 | [diff] [blame] | 1196 | for (uptr i = 0; i < ARRAY_SIZE(stats.by_size_log); i++) { |
| 1197 | uptr c = stats.by_size_log[i]; |
| 1198 | if (!c) continue; |
| 1199 | Printf("%zd:%zd; ", i, c); |
| 1200 | } |
| 1201 | Printf("\n"); |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1202 | } |
| 1203 | |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 1204 | // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone |
| 1205 | // introspection API. |
| 1206 | void ForceLock() { |
| 1207 | mutex_.Lock(); |
| 1208 | } |
| 1209 | |
| 1210 | void ForceUnlock() { |
| 1211 | mutex_.Unlock(); |
| 1212 | } |
| 1213 | |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 1214 | // Iterate over all existing chunks. |
| 1215 | // The allocator must be locked when calling this function. |
| 1216 | void ForEachChunk(ForEachChunkCallback callback, void *arg) { |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 1217 | for (uptr i = 0; i < n_chunks_; i++) |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 1218 | callback(reinterpret_cast<uptr>(GetUser(chunks_[i])), arg); |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 1219 | } |
| 1220 | |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1221 | private: |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1222 | static const int kMaxNumChunks = 1 << FIRST_32_SECOND_64(15, 18); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1223 | struct Header { |
| 1224 | uptr map_beg; |
| 1225 | uptr map_size; |
| 1226 | uptr size; |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1227 | uptr chunk_idx; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1228 | }; |
| 1229 | |
| 1230 | Header *GetHeader(uptr p) { |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1231 | CHECK(IsAligned(p, page_size_)); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1232 | return reinterpret_cast<Header*>(p - page_size_); |
| 1233 | } |
Alexey Samsonov | 53fbbf4 | 2013-08-05 13:20:39 +0000 | [diff] [blame] | 1234 | Header *GetHeader(const void *p) { |
| 1235 | return GetHeader(reinterpret_cast<uptr>(p)); |
| 1236 | } |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1237 | |
| 1238 | void *GetUser(Header *h) { |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1239 | CHECK(IsAligned((uptr)h, page_size_)); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1240 | return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_); |
| 1241 | } |
| 1242 | |
| 1243 | uptr RoundUpMapSize(uptr size) { |
| 1244 | return RoundUpTo(size, page_size_) + page_size_; |
| 1245 | } |
| 1246 | |
| 1247 | uptr page_size_; |
Kostya Serebryany | b8c363d | 2012-12-24 14:35:14 +0000 | [diff] [blame] | 1248 | Header *chunks_[kMaxNumChunks]; |
| 1249 | uptr n_chunks_; |
Kostya Serebryany | f8c3f3d | 2013-05-30 08:43:30 +0000 | [diff] [blame] | 1250 | uptr min_mmap_, max_mmap_; |
| 1251 | bool chunks_sorted_; |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1252 | struct Stats { |
Kostya Serebryany | 800344c | 2013-01-10 13:38:38 +0000 | [diff] [blame] | 1253 | uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64]; |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1254 | } stats; |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1255 | atomic_uint8_t may_return_null_; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1256 | SpinMutex mutex_; |
| 1257 | }; |
| 1258 | |
| 1259 | // This class implements a complete memory allocator by using two |
| 1260 | // internal allocators: |
| 1261 | // PrimaryAllocator is efficient, but may not allocate some sizes (alignments). |
| 1262 | // When allocating 2^x bytes it should return 2^x aligned chunk. |
| 1263 | // PrimaryAllocator is used via a local AllocatorCache. |
| 1264 | // SecondaryAllocator can allocate anything, but is not efficient. |
| 1265 | template <class PrimaryAllocator, class AllocatorCache, |
| 1266 | class SecondaryAllocator> // NOLINT |
| 1267 | class CombinedAllocator { |
| 1268 | public: |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1269 | void InitCommon(bool may_return_null) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1270 | primary_.Init(); |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1271 | atomic_store(&may_return_null_, may_return_null, memory_order_relaxed); |
| 1272 | } |
| 1273 | |
| 1274 | void InitLinkerInitialized(bool may_return_null) { |
| 1275 | secondary_.InitLinkerInitialized(may_return_null); |
| 1276 | stats_.InitLinkerInitialized(); |
| 1277 | InitCommon(may_return_null); |
| 1278 | } |
| 1279 | |
| 1280 | void Init(bool may_return_null) { |
| 1281 | secondary_.Init(may_return_null); |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1282 | stats_.Init(); |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1283 | InitCommon(may_return_null); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1284 | } |
| 1285 | |
| 1286 | void *Allocate(AllocatorCache *cache, uptr size, uptr alignment, |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1287 | bool cleared = false, bool check_rss_limit = false) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1288 | // Returning 0 on malloc(0) may break a lot of code. |
| 1289 | if (size == 0) |
| 1290 | size = 1; |
| 1291 | if (size + alignment < size) |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1292 | return ReturnNullOrDie(); |
| 1293 | if (check_rss_limit && RssLimitIsExceeded()) |
| 1294 | return ReturnNullOrDie(); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1295 | if (alignment > 8) |
| 1296 | size = RoundUpTo(size, alignment); |
| 1297 | void *res; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 1298 | bool from_primary = primary_.CanAllocate(size, alignment); |
| 1299 | if (from_primary) |
Dmitry Vyukov | ce17384 | 2013-01-11 11:15:48 +0000 | [diff] [blame] | 1300 | res = cache->Allocate(&primary_, primary_.ClassID(size)); |
| 1301 | else |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1302 | res = secondary_.Allocate(&stats_, size, alignment); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1303 | if (alignment > 8) |
| 1304 | CHECK_EQ(reinterpret_cast<uptr>(res) & (alignment - 1), 0); |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 1305 | if (cleared && res && from_primary) |
| 1306 | internal_bzero_aligned16(res, RoundUpTo(size, 16)); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1307 | return res; |
| 1308 | } |
| 1309 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1310 | bool MayReturnNull() const { |
| 1311 | return atomic_load(&may_return_null_, memory_order_acquire); |
| 1312 | } |
| 1313 | |
| 1314 | void *ReturnNullOrDie() { |
| 1315 | if (MayReturnNull()) |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1316 | return nullptr; |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1317 | ReportAllocatorCannotReturnNull(); |
| 1318 | } |
| 1319 | |
| 1320 | void SetMayReturnNull(bool may_return_null) { |
| 1321 | secondary_.SetMayReturnNull(may_return_null); |
| 1322 | atomic_store(&may_return_null_, may_return_null, memory_order_release); |
| 1323 | } |
| 1324 | |
| 1325 | bool RssLimitIsExceeded() { |
| 1326 | return atomic_load(&rss_limit_is_exceeded_, memory_order_acquire); |
| 1327 | } |
| 1328 | |
| 1329 | void SetRssLimitIsExceeded(bool rss_limit_is_exceeded) { |
| 1330 | atomic_store(&rss_limit_is_exceeded_, rss_limit_is_exceeded, |
| 1331 | memory_order_release); |
| 1332 | } |
| 1333 | |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1334 | void Deallocate(AllocatorCache *cache, void *p) { |
| 1335 | if (!p) return; |
| 1336 | if (primary_.PointerIsMine(p)) |
| 1337 | cache->Deallocate(&primary_, primary_.GetSizeClass(p), p); |
| 1338 | else |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1339 | secondary_.Deallocate(&stats_, p); |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1340 | } |
| 1341 | |
| 1342 | void *Reallocate(AllocatorCache *cache, void *p, uptr new_size, |
| 1343 | uptr alignment) { |
| 1344 | if (!p) |
| 1345 | return Allocate(cache, new_size, alignment); |
| 1346 | if (!new_size) { |
| 1347 | Deallocate(cache, p); |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1348 | return nullptr; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1349 | } |
| 1350 | CHECK(PointerIsMine(p)); |
| 1351 | uptr old_size = GetActuallyAllocatedSize(p); |
| 1352 | uptr memcpy_size = Min(new_size, old_size); |
| 1353 | void *new_p = Allocate(cache, new_size, alignment); |
| 1354 | if (new_p) |
| 1355 | internal_memcpy(new_p, p, memcpy_size); |
| 1356 | Deallocate(cache, p); |
| 1357 | return new_p; |
| 1358 | } |
| 1359 | |
| 1360 | bool PointerIsMine(void *p) { |
| 1361 | if (primary_.PointerIsMine(p)) |
| 1362 | return true; |
| 1363 | return secondary_.PointerIsMine(p); |
| 1364 | } |
| 1365 | |
Kostya Serebryany | 111a071 | 2012-12-26 04:52:07 +0000 | [diff] [blame] | 1366 | bool FromPrimary(void *p) { |
| 1367 | return primary_.PointerIsMine(p); |
| 1368 | } |
| 1369 | |
Evgeniy Stepanov | 5c48a8c | 2013-08-02 14:26:58 +0000 | [diff] [blame] | 1370 | void *GetMetaData(const void *p) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1371 | if (primary_.PointerIsMine(p)) |
| 1372 | return primary_.GetMetaData(p); |
| 1373 | return secondary_.GetMetaData(p); |
| 1374 | } |
| 1375 | |
Sergey Matveev | cd571e0 | 2013-06-06 14:17:56 +0000 | [diff] [blame] | 1376 | void *GetBlockBegin(const void *p) { |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1377 | if (primary_.PointerIsMine(p)) |
| 1378 | return primary_.GetBlockBegin(p); |
| 1379 | return secondary_.GetBlockBegin(p); |
| 1380 | } |
| 1381 | |
Sergey Matveev | ba2169a | 2013-05-31 11:13:45 +0000 | [diff] [blame] | 1382 | // This function does the same as GetBlockBegin, but is much faster. |
| 1383 | // Must be called with the allocator locked. |
| 1384 | void *GetBlockBeginFastLocked(void *p) { |
| 1385 | if (primary_.PointerIsMine(p)) |
| 1386 | return primary_.GetBlockBegin(p); |
| 1387 | return secondary_.GetBlockBeginFastLocked(p); |
| 1388 | } |
| 1389 | |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1390 | uptr GetActuallyAllocatedSize(void *p) { |
| 1391 | if (primary_.PointerIsMine(p)) |
| 1392 | return primary_.GetActuallyAllocatedSize(p); |
| 1393 | return secondary_.GetActuallyAllocatedSize(p); |
| 1394 | } |
| 1395 | |
| 1396 | uptr TotalMemoryUsed() { |
| 1397 | return primary_.TotalMemoryUsed() + secondary_.TotalMemoryUsed(); |
| 1398 | } |
| 1399 | |
| 1400 | void TestOnlyUnmap() { primary_.TestOnlyUnmap(); } |
| 1401 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1402 | void InitCache(AllocatorCache *cache) { |
| 1403 | cache->Init(&stats_); |
| 1404 | } |
| 1405 | |
| 1406 | void DestroyCache(AllocatorCache *cache) { |
| 1407 | cache->Destroy(&primary_, &stats_); |
| 1408 | } |
| 1409 | |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1410 | void SwallowCache(AllocatorCache *cache) { |
| 1411 | cache->Drain(&primary_); |
| 1412 | } |
| 1413 | |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1414 | void GetStats(AllocatorStatCounters s) const { |
| 1415 | stats_.Get(s); |
| 1416 | } |
| 1417 | |
Kostya Serebryany | 4b48f45 | 2012-12-27 14:09:19 +0000 | [diff] [blame] | 1418 | void PrintStats() { |
| 1419 | primary_.PrintStats(); |
| 1420 | secondary_.PrintStats(); |
| 1421 | } |
| 1422 | |
Alexander Potapenko | 6a11cc1 | 2013-02-07 11:40:03 +0000 | [diff] [blame] | 1423 | // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone |
| 1424 | // introspection API. |
| 1425 | void ForceLock() { |
| 1426 | primary_.ForceLock(); |
| 1427 | secondary_.ForceLock(); |
| 1428 | } |
| 1429 | |
| 1430 | void ForceUnlock() { |
| 1431 | secondary_.ForceUnlock(); |
| 1432 | primary_.ForceUnlock(); |
| 1433 | } |
| 1434 | |
Sergey Matveev | ac78d00 | 2013-06-24 08:34:50 +0000 | [diff] [blame] | 1435 | // Iterate over all existing chunks. |
| 1436 | // The allocator must be locked when calling this function. |
| 1437 | void ForEachChunk(ForEachChunkCallback callback, void *arg) { |
| 1438 | primary_.ForEachChunk(callback, arg); |
| 1439 | secondary_.ForEachChunk(callback, arg); |
Kostya Serebryany | 300f953 | 2013-03-15 11:39:41 +0000 | [diff] [blame] | 1440 | } |
| 1441 | |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1442 | private: |
| 1443 | PrimaryAllocator primary_; |
| 1444 | SecondaryAllocator secondary_; |
Dmitry Vyukov | bdd844c | 2013-01-24 09:08:03 +0000 | [diff] [blame] | 1445 | AllocatorGlobalStats stats_; |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 1446 | atomic_uint8_t may_return_null_; |
| 1447 | atomic_uint8_t rss_limit_is_exceeded_; |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1448 | }; |
| 1449 | |
Kostya Serebryany | 65199f1 | 2013-01-25 11:46:22 +0000 | [diff] [blame] | 1450 | // Returns true if calloc(size, n) should return 0 due to overflow in size*n. |
| 1451 | bool CallocShouldReturnNullDueToOverflow(uptr size, uptr n); |
| 1452 | |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1453 | } // namespace __sanitizer |
Kostya Serebryany | 43811a1 | 2012-12-04 07:54:41 +0000 | [diff] [blame] | 1454 | |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 1455 | #endif // SANITIZER_ALLOCATOR_H |