1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 // PHC is a probabilistic heap checker. A tiny fraction of randomly chosen heap
8 // allocations are subject to some expensive checking via the use of OS page
9 // access protection. A failed check triggers a crash, whereupon useful
10 // information about the failure is put into the crash report. The cost and
11 // coverage for each user is minimal, but spread over the entire user base the
12 // coverage becomes significant.
13 //
14 // The idea comes from Chromium, where it is called GWP-ASAN. (Firefox uses PHC
15 // as the name because GWP-ASAN is long, awkward, and doesn't have any
16 // particular meaning.)
17 //
18 // In the current implementation up to 64 allocations per process can become
19 // PHC allocations. These allocations must be page-sized or smaller. Each PHC
20 // allocation gets its own page, and when the allocation is freed its page is
21 // marked inaccessible until the page is reused for another allocation. This
22 // means that a use-after-free defect (which includes double-frees) will be
23 // caught if the use occurs before the page is reused for another allocation.
24 // The crash report will contain stack traces for the allocation site, the free
25 // site, and the use-after-free site, which is often enough to diagnose the
26 // defect.
27 //
28 // Also, each PHC allocation is followed by a guard page. The PHC allocation is
29 // positioned so that its end abuts the guard page (or as close as possible,
30 // given alignment constraints). This means that a bounds violation at the end
31 // of the allocation (overflow) will be caught. The crash report will contain
32 // stack traces for the allocation site and the bounds violation use site,
33 // which is often enough to diagnose the defect.
34 //
35 // (A bounds violation at the start of the allocation (underflow) will not be
36 // caught, unless it is sufficiently large to hit the preceding allocation's
37 // guard page, which is not that likely. It would be possible to look more
38 // assiduously for underflow by randomly placing some allocations at the end of
39 // the page and some at the start of the page, and GWP-ASAN does this. PHC does
40 // not, however, because overflow is likely to be much more common than
41 // underflow in practice.)
42 //
43 // We use a simple heuristic to categorize a guard page access as overflow or
44 // underflow: if the address falls in the lower half of the guard page, we
45 // assume it is overflow, otherwise we assume it is underflow. More
46 // sophisticated heuristics are possible, but this one is very simple, and it is
47 // likely that most overflows/underflows in practice are very close to the page
48 // boundary.
49 //
50 // The design space for the randomization strategy is large. The current
51 // implementation has a large random delay before it starts operating, and a
52 // small random delay between each PHC allocation attempt. Each freed PHC
53 // allocation is quarantined for a medium random delay before being reused, in
54 // order to increase the chance of catching UAFs.
55 //
56 // The basic cost of PHC's operation is as follows.
57 //
58 // - The physical memory cost is 64 * 4 KiB = 256 KiB per process (assuming 4
59 // KiB pages) plus some metadata (including stack traces) for each page.
60 //
61 // - The virtual memory cost is the physical memory cost plus the guard pages:
62 // another 64 * 4 KiB = 256 KiB per process. PHC is currently only enabled on
63 // 64-bit platforms so the impact of the virtual memory usage is negligible.
64 //
65 // - Every allocation requires a size check and a decrement-and-check of an
66 // atomic counter. When the counter reaches zero a PHC allocation can occur,
67 // which involves marking a page as accessible and getting a stack trace for
68 // the allocation site. Otherwise, mozjemalloc performs the allocation.
69 //
70 // - Every deallocation requires a range check on the pointer to see if it
71 // involves a PHC allocation. (The choice to only do PHC allocations that are
72 // a page or smaller enables this range check, because the 64 pages are
73 // contiguous. Allowing larger allocations would make this more complicated,
74 // and we definitely don't want something as slow as a hash table lookup on
75 // every deallocation.) PHC deallocations involve marking a page as
76 // inaccessible and getting a stack trace for the deallocation site.
77 //
78 // Note that calls to realloc(), free(), and malloc_usable_size() will
79 // immediately crash if the given pointer falls within a page allocation's
80 // page, but does not point to the start of the allocation itself.
81 //
82 // void* p = malloc(64);
83 // free(p + 1); // p+1 doesn't point to the allocation start; crash
84 //
85 // Such crashes will not have the PHC fields in the crash report.
86 //
87 // PHC-specific tests can be run with the following commands:
88 // - gtests: `./mach gtest '*PHC*'`
89 // - xpcshell-tests: `./mach test toolkit/crashreporter/test/unit`
90 // - This runs some non-PHC tests as well.
91
92 #include "PHC.h"
93
94 #include <stdlib.h>
95 #include <time.h>
96
97 #include <algorithm>
98
99 #ifdef XP_WIN
100 # include <process.h>
101 #else
102 # include <sys/mman.h>
103 # include <sys/types.h>
104 # include <pthread.h>
105 # include <unistd.h>
106 #endif
107
108 #include "replace_malloc.h"
109 #include "FdPrintf.h"
110 #include "Mutex.h"
111 #include "mozilla/Assertions.h"
112 #include "mozilla/Atomics.h"
113 #include "mozilla/Attributes.h"
114 #include "mozilla/CheckedInt.h"
115 #include "mozilla/Maybe.h"
116 #include "mozilla/StackWalk.h"
117 #include "mozilla/ThreadLocal.h"
118 #include "mozilla/XorShift128PlusRNG.h"
119
120 using namespace mozilla;
121
122 //---------------------------------------------------------------------------
123 // Utilities
124 //---------------------------------------------------------------------------
125
126 #ifdef ANDROID
127 // Android doesn't have pthread_atfork defined in pthread.h.
128 extern "C" MOZ_EXPORT int pthread_atfork(void (*)(void), void (*)(void),
129 void (*)(void));
130 #endif
131
132 #ifndef DISALLOW_COPY_AND_ASSIGN
133 # define DISALLOW_COPY_AND_ASSIGN(T) \
134 T(const T&); \
135 void operator=(const T&)
136 #endif
137
138 static malloc_table_t sMallocTable;
139
140 // This class provides infallible operations for the small number of heap
141 // allocations that PHC does for itself. It would be nice if we could use the
142 // InfallibleAllocPolicy from mozalloc, but PHC cannot use mozalloc.
143 class InfallibleAllocPolicy {
144 public:
AbortOnFailure(const void * aP)145 static void AbortOnFailure(const void* aP) {
146 if (!aP) {
147 MOZ_CRASH("PHC failed to allocate");
148 }
149 }
150
151 template <class T>
new_()152 static T* new_() {
153 void* p = sMallocTable.malloc(sizeof(T));
154 AbortOnFailure(p);
155 return new (p) T;
156 }
157 };
158
159 //---------------------------------------------------------------------------
160 // Stack traces
161 //---------------------------------------------------------------------------
162
163 // This code is similar to the equivalent code within DMD.
164
165 class StackTrace : public phc::StackTrace {
166 public:
StackTrace()167 StackTrace() : phc::StackTrace() {}
168
Clear()169 void Clear() { mLength = 0; }
170
171 void Fill();
172
173 private:
StackWalkCallback(uint32_t aFrameNumber,void * aPc,void * aSp,void * aClosure)174 static void StackWalkCallback(uint32_t aFrameNumber, void* aPc, void* aSp,
175 void* aClosure) {
176 StackTrace* st = (StackTrace*)aClosure;
177 MOZ_ASSERT(st->mLength < kMaxFrames);
178 st->mPcs[st->mLength] = aPc;
179 st->mLength++;
180 MOZ_ASSERT(st->mLength == aFrameNumber);
181 }
182 };
183
184 // WARNING WARNING WARNING: this function must only be called when GMut::sMutex
185 // is *not* locked, otherwise we might get deadlocks.
186 //
187 // How? On Windows, MozStackWalk() can lock a mutex, M, from the shared library
188 // loader. Another thread might call malloc() while holding M locked (when
189 // loading a shared library) and try to lock GMut::sMutex, causing a deadlock.
190 // So GMut::sMutex can't be locked during the call to MozStackWalk(). (For
191 // details, see https://bugzilla.mozilla.org/show_bug.cgi?id=374829#c8. On
192 // Linux, something similar can happen; see bug 824340. So we just disallow it
193 // on all platforms.)
194 //
195 // In DMD, to avoid this problem we temporarily unlock the equivalent mutex for
196 // the MozStackWalk() call. But that's grotty, and things are a bit different
197 // here, so we just require that stack traces be obtained before locking
198 // GMut::sMutex.
199 //
200 // Unfortunately, there is no reliable way at compile-time or run-time to ensure
201 // this pre-condition. Hence this large comment.
202 //
Fill()203 void StackTrace::Fill() {
204 mLength = 0;
205
206 #if defined(XP_WIN) && defined(_M_IX86)
207 // This avoids MozStackWalk(), which causes unusably slow startup on Win32
208 // when it is called during static initialization (see bug 1241684).
209 //
210 // This code is cribbed from the Gecko Profiler, which also uses
211 // FramePointerStackWalk() on Win32: Registers::SyncPopulate() for the
212 // frame pointer, and GetStackTop() for the stack end.
213 CONTEXT context;
214 RtlCaptureContext(&context);
215 void** fp = reinterpret_cast<void**>(context.Ebp);
216
217 PNT_TIB pTib = reinterpret_cast<PNT_TIB>(NtCurrentTeb());
218 void* stackEnd = static_cast<void*>(pTib->StackBase);
219 FramePointerStackWalk(StackWalkCallback, kMaxFrames, this, fp, stackEnd);
220 #elif defined(XP_MACOSX)
221 // This avoids MozStackWalk(), which has become unusably slow on Mac due to
222 // changes in libunwind.
223 //
224 // This code is cribbed from the Gecko Profiler, which also uses
225 // FramePointerStackWalk() on Mac: Registers::SyncPopulate() for the frame
226 // pointer, and GetStackTop() for the stack end.
227 void** fp;
228 asm(
229 // Dereference %rbp to get previous %rbp
230 "movq (%%rbp), %0\n\t"
231 : "=r"(fp));
232 void* stackEnd = pthread_get_stackaddr_np(pthread_self());
233 FramePointerStackWalk(StackWalkCallback, kMaxFrames, this, fp, stackEnd);
234 #else
235 MozStackWalk(StackWalkCallback, nullptr, kMaxFrames, this);
236 #endif
237 }
238
239 //---------------------------------------------------------------------------
240 // Logging
241 //---------------------------------------------------------------------------
242
243 // Change this to 1 to enable some PHC logging. Useful for debugging.
244 #define PHC_LOGGING 0
245
246 #if PHC_LOGGING
247
GetPid()248 static size_t GetPid() { return size_t(getpid()); }
249
GetTid()250 static size_t GetTid() {
251 # if defined(XP_WIN)
252 return size_t(GetCurrentThreadId());
253 # else
254 return size_t(pthread_self());
255 # endif
256 }
257
258 # if defined(XP_WIN)
259 # define LOG_STDERR \
260 reinterpret_cast<intptr_t>(GetStdHandle(STD_ERROR_HANDLE))
261 # else
262 # define LOG_STDERR 2
263 # endif
264 # define LOG(fmt, ...) \
265 FdPrintf(LOG_STDERR, "PHC[%zu,%zu,~%zu] " fmt, GetPid(), GetTid(), \
266 size_t(GAtomic::Now()), __VA_ARGS__)
267
268 #else
269
270 # define LOG(fmt, ...)
271
272 #endif // PHC_LOGGING
273
274 //---------------------------------------------------------------------------
275 // Global state
276 //---------------------------------------------------------------------------
277
278 // Throughout this entire file time is measured as the number of sub-page
279 // allocations performed (by PHC and mozjemalloc combined). `Time` is 64-bit
280 // because we could have more than 2**32 allocations in a long-running session.
281 // `Delay` is 32-bit because the delays used within PHC are always much smaller
282 // than 2**32.
283 using Time = uint64_t; // A moment in time.
284 using Delay = uint32_t; // A time duration.
285
286 // PHC only runs if the page size is 4 KiB; anything more is uncommon and would
287 // use too much memory. So we hardwire this size.
288 static const size_t kPageSize = 4096;
289
290 // There are two kinds of page.
291 // - Allocation pages, from which allocations are made.
292 // - Guard pages, which are never touched by PHC.
293 //
294 // These page kinds are interleaved; each allocation page has a guard page on
295 // either side.
296 static const size_t kNumAllocPages = 64;
297 static const size_t kNumAllPages = kNumAllocPages * 2 + 1;
298
299 // The total size of the allocation pages and guard pages.
300 static const size_t kAllPagesSize = kNumAllPages * kPageSize;
301
302 // The junk value used to fill new allocation in debug builds. It's same value
303 // as the one used by mozjemalloc. PHC applies it unconditionally in debug
304 // builds. Unlike mozjemalloc, PHC doesn't consult the MALLOC_OPTIONS
305 // environment variable to possibly change that behaviour.
306 //
307 // Also note that, unlike mozjemalloc, PHC doesn't have a poison value for freed
308 // allocations because freed allocations are protected by OS page protection.
309 const uint8_t kAllocJunk = 0xe4;
310
311 // The maximum time.
312 static const Time kMaxTime = ~(Time(0));
313
314 // The average delay before doing any page allocations at the start of a
315 // process. Note that roughly 1 million allocations occur in the main process
316 // while starting the browser. The delay range is 1..kAvgFirstAllocDelay*2.
317 static const Delay kAvgFirstAllocDelay = 512 * 1024;
318
319 // The average delay until the next attempted page allocation, once we get past
320 // the first delay. The delay range is 1..kAvgAllocDelay*2.
321 static const Delay kAvgAllocDelay = 16 * 1024;
322
323 // The average delay before reusing a freed page. Should be significantly larger
324 // than kAvgAllocDelay, otherwise there's not much point in having it. The delay
325 // range is (kAvgAllocDelay / 2)..(kAvgAllocDelay / 2 * 3). This is different to
326 // the other delay ranges in not having a minimum of 1, because that's such a
327 // short delay that there is a high likelihood of bad stacks in any crash
328 // report.
329 static const Delay kAvgPageReuseDelay = 256 * 1024;
330
331 // Truncate aRnd to the range (1 .. AvgDelay*2). If aRnd is random, this
332 // results in an average value of aAvgDelay + 0.5, which is close enough to
333 // aAvgDelay. aAvgDelay must be a power-of-two (otherwise it will crash) for
334 // speed.
335 template <Delay AvgDelay>
Rnd64ToDelay(uint64_t aRnd)336 constexpr Delay Rnd64ToDelay(uint64_t aRnd) {
337 static_assert(IsPowerOfTwo(AvgDelay), "must be a power of two");
338
339 return aRnd % (AvgDelay * 2) + 1;
340 }
341
342 // Maps a pointer to a PHC-specific structure:
343 // - Nothing
344 // - A guard page (it is unspecified which one)
345 // - An allocation page (with an index < kNumAllocPages)
346 //
347 // The standard way of handling a PtrKind is to check IsNothing(), and if that
348 // fails, to check IsGuardPage(), and if that fails, to call AllocPage().
349 class PtrKind {
350 private:
351 enum class Tag : uint8_t {
352 Nothing,
353 GuardPage,
354 AllocPage,
355 };
356
357 Tag mTag;
358 uintptr_t mIndex; // Only used if mTag == Tag::AllocPage.
359
360 public:
361 // Detect what a pointer points to. This constructor must be fast because it
362 // is called for every call to free(), realloc(), malloc_usable_size(), and
363 // jemalloc_ptr_info().
PtrKind(const void * aPtr,const uint8_t * aPagesStart,const uint8_t * aPagesLimit)364 PtrKind(const void* aPtr, const uint8_t* aPagesStart,
365 const uint8_t* aPagesLimit) {
366 if (!(aPagesStart <= aPtr && aPtr < aPagesLimit)) {
367 mTag = Tag::Nothing;
368 } else {
369 uintptr_t offset = static_cast<const uint8_t*>(aPtr) - aPagesStart;
370 uintptr_t allPageIndex = offset / kPageSize;
371 MOZ_ASSERT(allPageIndex < kNumAllPages);
372 if (allPageIndex & 1) {
373 // Odd-indexed pages are allocation pages.
374 uintptr_t allocPageIndex = allPageIndex / 2;
375 MOZ_ASSERT(allocPageIndex < kNumAllocPages);
376 mTag = Tag::AllocPage;
377 mIndex = allocPageIndex;
378 } else {
379 // Even-numbered pages are guard pages.
380 mTag = Tag::GuardPage;
381 }
382 }
383 }
384
IsNothing() const385 bool IsNothing() const { return mTag == Tag::Nothing; }
IsGuardPage() const386 bool IsGuardPage() const { return mTag == Tag::GuardPage; }
387
388 // This should only be called after IsNothing() and IsGuardPage() have been
389 // checked and failed.
AllocPageIndex() const390 uintptr_t AllocPageIndex() const {
391 MOZ_RELEASE_ASSERT(mTag == Tag::AllocPage);
392 return mIndex;
393 }
394 };
395
396 // Shared, atomic, mutable global state.
397 class GAtomic {
398 public:
Init(Delay aFirstDelay)399 static void Init(Delay aFirstDelay) {
400 sAllocDelay = aFirstDelay;
401
402 LOG("Initial sAllocDelay <- %zu\n", size_t(aFirstDelay));
403 }
404
Now()405 static Time Now() { return sNow; }
406
IncrementNow()407 static void IncrementNow() { sNow++; }
408
409 // Decrements the delay and returns the decremented value.
DecrementDelay()410 static int32_t DecrementDelay() { return --sAllocDelay; }
411
SetAllocDelay(Delay aAllocDelay)412 static void SetAllocDelay(Delay aAllocDelay) { sAllocDelay = aAllocDelay; }
413
414 private:
415 // The current time. Relaxed semantics because it's primarily used for
416 // determining if an allocation can be recycled yet and therefore it doesn't
417 // need to be exact.
418 static Atomic<Time, Relaxed> sNow;
419
420 // Delay until the next attempt at a page allocation. See the comment in
421 // MaybePageAlloc() for an explanation of why it is a signed integer, and why
422 // it uses ReleaseAcquire semantics.
423 static Atomic<Delay, ReleaseAcquire> sAllocDelay;
424 };
425
426 Atomic<Time, Relaxed> GAtomic::sNow;
427 Atomic<Delay, ReleaseAcquire> GAtomic::sAllocDelay;
428
429 // Shared, immutable global state. Initialized by replace_init() and never
430 // changed after that. replace_init() runs early enough that no synchronization
431 // is needed.
432 class GConst {
433 private:
434 // The bounds of the allocated pages.
435 uint8_t* const mPagesStart;
436 uint8_t* const mPagesLimit;
437
438 // Allocates the allocation pages and the guard pages, contiguously.
AllocAllPages()439 uint8_t* AllocAllPages() {
440 // Allocate the pages so that they are inaccessible. They are never freed,
441 // because it would happen at process termination when it would be of little
442 // use.
443 void* pages =
444 #ifdef XP_WIN
445 VirtualAlloc(nullptr, kAllPagesSize, MEM_RESERVE, PAGE_NOACCESS);
446 #else
447 mmap(nullptr, kAllPagesSize, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1,
448 0);
449 #endif
450 if (!pages) {
451 MOZ_CRASH();
452 }
453
454 return static_cast<uint8_t*>(pages);
455 }
456
457 public:
GConst()458 GConst()
459 : mPagesStart(AllocAllPages()), mPagesLimit(mPagesStart + kAllPagesSize) {
460 LOG("AllocAllPages at %p..%p\n", mPagesStart, mPagesLimit);
461 }
462
PtrKind(const void * aPtr)463 class PtrKind PtrKind(const void* aPtr) {
464 class PtrKind pk(aPtr, mPagesStart, mPagesLimit);
465 return pk;
466 }
467
IsInFirstGuardPage(const void * aPtr)468 bool IsInFirstGuardPage(const void* aPtr) {
469 return mPagesStart <= aPtr && aPtr < mPagesStart + kPageSize;
470 }
471
472 // Get the address of the allocation page referred to via an index. Used when
473 // marking the page as accessible/inaccessible.
AllocPagePtr(uintptr_t aIndex)474 uint8_t* AllocPagePtr(uintptr_t aIndex) {
475 MOZ_ASSERT(aIndex < kNumAllocPages);
476 // Multiply by two and add one to account for allocation pages *and* guard
477 // pages.
478 return mPagesStart + (2 * aIndex + 1) * kPageSize;
479 }
480 };
481
482 static GConst* gConst;
483
484 // On MacOS, the first __thread/thread_local access calls malloc, which leads
485 // to an infinite loop. So we use pthread-based TLS instead, which somehow
486 // doesn't have this problem.
487 #if !defined(XP_DARWIN)
488 # define PHC_THREAD_LOCAL(T) MOZ_THREAD_LOCAL(T)
489 #else
490 # define PHC_THREAD_LOCAL(T) \
491 detail::ThreadLocal<T, detail::ThreadLocalKeyStorage>
492 #endif
493
494 // Thread-local state.
495 class GTls {
496 GTls(const GTls&) = delete;
497
498 const GTls& operator=(const GTls&) = delete;
499
500 // When true, PHC does as little as possible.
501 //
502 // (a) It does not allocate any new page allocations.
503 //
504 // (b) It avoids doing any operations that might call malloc/free/etc., which
505 // would cause re-entry into PHC. (In practice, MozStackWalk() is the
506 // only such operation.) Note that calls to the functions in sMallocTable
507 // are ok.
508 //
509 // For example, replace_malloc() will just fall back to mozjemalloc. However,
510 // operations involving existing allocations are more complex, because those
511 // existing allocations may be page allocations. For example, if
512 // replace_free() is passed a page allocation on a PHC-disabled thread, it
513 // will free the page allocation in the usual way, but it will get a dummy
514 // freeStack in order to avoid calling MozStackWalk(), as per (b) above.
515 //
516 // This single disabling mechanism has two distinct uses.
517 //
518 // - It's used to prevent re-entry into PHC, which can cause correctness
519 // problems. For example, consider this sequence.
520 //
521 // 1. enter replace_free()
522 // 2. which calls PageFree()
523 // 3. which calls MozStackWalk()
524 // 4. which locks a mutex M, and then calls malloc
525 // 5. enter replace_malloc()
526 // 6. which calls MaybePageAlloc()
527 // 7. which calls MozStackWalk()
528 // 8. which (re)locks a mutex M --> deadlock
529 //
530 // We avoid this sequence by "disabling" the thread in PageFree() (at step
531 // 2), which causes MaybePageAlloc() to fail, avoiding the call to
532 // MozStackWalk() (at step 7).
533 //
534 // In practice, realloc or free of a PHC allocation is unlikely on a thread
535 // that is disabled because of this use: MozStackWalk() will probably only
536 // realloc/free allocations that it allocated itself, but those won't be
537 // page allocations because PHC is disabled before calling MozStackWalk().
538 //
539 // (Note that MaybePageAlloc() could safely do a page allocation so long as
540 // it avoided calling MozStackWalk() by getting a dummy allocStack. But it
541 // wouldn't be useful, and it would prevent the second use below.)
542 //
543 // - It's used to prevent PHC allocations in some tests that rely on
544 // mozjemalloc's exact allocation behaviour, which PHC does not replicate
545 // exactly. (Note that (b) isn't necessary for this use -- MozStackWalk()
546 // could be safely called -- but it is necessary for the first use above.)
547 //
548 static PHC_THREAD_LOCAL(bool) tlsIsDisabled;
549
550 public:
Init()551 static void Init() {
552 if (!tlsIsDisabled.init()) {
553 MOZ_CRASH();
554 }
555 }
556
DisableOnCurrentThread()557 static void DisableOnCurrentThread() {
558 MOZ_ASSERT(!GTls::tlsIsDisabled.get());
559 tlsIsDisabled.set(true);
560 }
561
EnableOnCurrentThread()562 static void EnableOnCurrentThread() {
563 MOZ_ASSERT(GTls::tlsIsDisabled.get());
564 tlsIsDisabled.set(false);
565 }
566
IsDisabledOnCurrentThread()567 static bool IsDisabledOnCurrentThread() { return tlsIsDisabled.get(); }
568 };
569
570 PHC_THREAD_LOCAL(bool) GTls::tlsIsDisabled;
571
572 class AutoDisableOnCurrentThread {
573 AutoDisableOnCurrentThread(const AutoDisableOnCurrentThread&) = delete;
574
575 const AutoDisableOnCurrentThread& operator=(
576 const AutoDisableOnCurrentThread&) = delete;
577
578 public:
AutoDisableOnCurrentThread()579 explicit AutoDisableOnCurrentThread() { GTls::DisableOnCurrentThread(); }
~AutoDisableOnCurrentThread()580 ~AutoDisableOnCurrentThread() { GTls::EnableOnCurrentThread(); }
581 };
582
583 // This type is used as a proof-of-lock token, to make it clear which functions
584 // require sMutex to be locked.
585 using GMutLock = const MutexAutoLock&;
586
587 // Shared, mutable global state. Protected by sMutex; all accessing functions
588 // take a GMutLock as proof that sMutex is held.
589 class GMut {
590 enum class AllocPageState {
591 NeverAllocated = 0,
592 InUse = 1,
593 Freed = 2,
594 };
595
596 // Metadata for each allocation page.
597 class AllocPageInfo {
598 public:
AllocPageInfo()599 AllocPageInfo()
600 : mState(AllocPageState::NeverAllocated),
601 mArenaId(),
602 mBaseAddr(nullptr),
603 mAllocStack(),
604 mFreeStack(),
605 mReuseTime(0) {}
606
607 // The current allocation page state.
608 AllocPageState mState;
609
610 // The arena that the allocation is nominally from. This isn't meaningful
611 // within PHC, which has no arenas. But it is necessary for reallocation of
612 // page allocations as normal allocations, such as in this code:
613 //
614 // p = moz_arena_malloc(arenaId, 4096);
615 // realloc(p, 8192);
616 //
617 // The realloc is more than one page, and thus too large for PHC to handle.
618 // Therefore, if PHC handles the first allocation, it must ask mozjemalloc
619 // to allocate the 8192 bytes in the correct arena, and to do that, it must
620 // call sMallocTable.moz_arena_malloc with the correct arenaId under the
621 // covers. Therefore it must record that arenaId.
622 //
623 // This field is also needed for jemalloc_ptr_info() to work, because it
624 // also returns the arena ID (but only in debug builds).
625 //
626 // - NeverAllocated: must be 0.
627 // - InUse | Freed: can be any valid arena ID value.
628 Maybe<arena_id_t> mArenaId;
629
630 // The starting address of the allocation. Will not be the same as the page
631 // address unless the allocation is a full page.
632 // - NeverAllocated: must be 0.
633 // - InUse | Freed: must be within the allocation page.
634 uint8_t* mBaseAddr;
635
636 // Usable size is computed as the number of bytes between the pointer and
637 // the end of the allocation page. This might be bigger than the requested
638 // size, especially if an outsized alignment is requested.
UsableSize() const639 size_t UsableSize() const {
640 return mState == AllocPageState::NeverAllocated
641 ? 0
642 : kPageSize - (reinterpret_cast<uintptr_t>(mBaseAddr) &
643 (kPageSize - 1));
644 }
645
646 // The allocation stack.
647 // - NeverAllocated: Nothing.
648 // - InUse | Freed: Some.
649 Maybe<StackTrace> mAllocStack;
650
651 // The free stack.
652 // - NeverAllocated | InUse: Nothing.
653 // - Freed: Some.
654 Maybe<StackTrace> mFreeStack;
655
656 // The time at which the page is available for reuse, as measured against
657 // GAtomic::sNow. When the page is in use this value will be kMaxTime.
658 // - NeverAllocated: must be 0.
659 // - InUse: must be kMaxTime.
660 // - Freed: must be > 0 and < kMaxTime.
661 Time mReuseTime;
662 };
663
664 public:
665 // The mutex that protects the other members.
666 static Mutex sMutex;
667
GMut()668 GMut()
669 : mRNG(RandomSeed<0>(), RandomSeed<1>()),
670 mAllocPages(),
671 mNumPageAllocs(0),
672 mPageAllocHits(0),
673 mPageAllocMisses(0) {
674 sMutex.Init();
675 }
676
Random64(GMutLock)677 uint64_t Random64(GMutLock) { return mRNG.next(); }
678
IsPageInUse(GMutLock,uintptr_t aIndex)679 bool IsPageInUse(GMutLock, uintptr_t aIndex) {
680 return mAllocPages[aIndex].mState == AllocPageState::InUse;
681 }
682
683 // Is the page free? And if so, has enough time passed that we can use it?
IsPageAllocatable(GMutLock,uintptr_t aIndex,Time aNow)684 bool IsPageAllocatable(GMutLock, uintptr_t aIndex, Time aNow) {
685 const AllocPageInfo& page = mAllocPages[aIndex];
686 return page.mState != AllocPageState::InUse && aNow >= page.mReuseTime;
687 }
688
PageArena(GMutLock aLock,uintptr_t aIndex)689 Maybe<arena_id_t> PageArena(GMutLock aLock, uintptr_t aIndex) {
690 const AllocPageInfo& page = mAllocPages[aIndex];
691 AssertAllocPageInUse(aLock, page);
692
693 return page.mArenaId;
694 }
695
PageUsableSize(GMutLock aLock,uintptr_t aIndex)696 size_t PageUsableSize(GMutLock aLock, uintptr_t aIndex) {
697 const AllocPageInfo& page = mAllocPages[aIndex];
698 AssertAllocPageInUse(aLock, page);
699
700 return page.UsableSize();
701 }
702
SetPageInUse(GMutLock aLock,uintptr_t aIndex,const Maybe<arena_id_t> & aArenaId,uint8_t * aBaseAddr,const StackTrace & aAllocStack)703 void SetPageInUse(GMutLock aLock, uintptr_t aIndex,
704 const Maybe<arena_id_t>& aArenaId, uint8_t* aBaseAddr,
705 const StackTrace& aAllocStack) {
706 AllocPageInfo& page = mAllocPages[aIndex];
707 AssertAllocPageNotInUse(aLock, page);
708
709 page.mState = AllocPageState::InUse;
710 page.mArenaId = aArenaId;
711 page.mBaseAddr = aBaseAddr;
712 page.mAllocStack = Some(aAllocStack);
713 page.mFreeStack = Nothing();
714 page.mReuseTime = kMaxTime;
715
716 mNumPageAllocs++;
717 MOZ_RELEASE_ASSERT(mNumPageAllocs <= kNumAllocPages);
718 }
719
ResizePageInUse(GMutLock aLock,uintptr_t aIndex,const Maybe<arena_id_t> & aArenaId,uint8_t * aNewBaseAddr,const StackTrace & aAllocStack)720 void ResizePageInUse(GMutLock aLock, uintptr_t aIndex,
721 const Maybe<arena_id_t>& aArenaId, uint8_t* aNewBaseAddr,
722 const StackTrace& aAllocStack) {
723 AllocPageInfo& page = mAllocPages[aIndex];
724 AssertAllocPageInUse(aLock, page);
725
726 // page.mState is not changed.
727 if (aArenaId.isSome()) {
728 // Crash if the arenas don't match.
729 MOZ_RELEASE_ASSERT(page.mArenaId == aArenaId);
730 }
731 page.mBaseAddr = aNewBaseAddr;
732 // We could just keep the original alloc stack, but the realloc stack is
733 // more recent and therefore seems more useful.
734 page.mAllocStack = Some(aAllocStack);
735 // page.mFreeStack is not changed.
736 // page.mReuseTime is not changed.
737 };
738
SetPageFreed(GMutLock aLock,uintptr_t aIndex,const Maybe<arena_id_t> & aArenaId,const StackTrace & aFreeStack,Delay aReuseDelay)739 void SetPageFreed(GMutLock aLock, uintptr_t aIndex,
740 const Maybe<arena_id_t>& aArenaId,
741 const StackTrace& aFreeStack, Delay aReuseDelay) {
742 AllocPageInfo& page = mAllocPages[aIndex];
743 AssertAllocPageInUse(aLock, page);
744
745 page.mState = AllocPageState::Freed;
746
747 // page.mArenaId is left unchanged, for jemalloc_ptr_info() calls that
748 // occur after freeing (e.g. in the PtrInfo test in TestJemalloc.cpp).
749 if (aArenaId.isSome()) {
750 // Crash if the arenas don't match.
751 MOZ_RELEASE_ASSERT(page.mArenaId == aArenaId);
752 }
753
754 // page.musableSize is left unchanged, for reporting on UAF, and for
755 // jemalloc_ptr_info() calls that occur after freeing (e.g. in the PtrInfo
756 // test in TestJemalloc.cpp).
757
758 // page.mAllocStack is left unchanged, for reporting on UAF.
759
760 page.mFreeStack = Some(aFreeStack);
761 page.mReuseTime = GAtomic::Now() + aReuseDelay;
762
763 MOZ_RELEASE_ASSERT(mNumPageAllocs > 0);
764 mNumPageAllocs--;
765 }
766
CrashOnGuardPage(void * aPtr)767 static void CrashOnGuardPage(void* aPtr) {
768 // An operation on a guard page? This is a bounds violation. Deliberately
769 // touch the page in question, to cause a crash that triggers the usual PHC
770 // machinery.
771 LOG("CrashOnGuardPage(%p), bounds violation\n", aPtr);
772 *static_cast<uint8_t*>(aPtr) = 0;
773 MOZ_CRASH("unreachable");
774 }
775
EnsureValidAndInUse(GMutLock,void * aPtr,uintptr_t aIndex)776 void EnsureValidAndInUse(GMutLock, void* aPtr, uintptr_t aIndex) {
777 const AllocPageInfo& page = mAllocPages[aIndex];
778
779 // The pointer must point to the start of the allocation.
780 MOZ_RELEASE_ASSERT(page.mBaseAddr == aPtr);
781
782 if (page.mState == AllocPageState::Freed) {
783 // An operation on a freed page? This is a particular kind of
784 // use-after-free. Deliberately touch the page in question, in order to
785 // cause a crash that triggers the usual PHC machinery. But unlock sMutex
786 // first, because that self-same PHC machinery needs to re-lock it, and
787 // the crash causes non-local control flow so sMutex won't be unlocked
788 // the normal way in the caller.
789 LOG("EnsureValidAndInUse(%p), use-after-free\n", aPtr);
790 sMutex.Unlock();
791 *static_cast<uint8_t*>(aPtr) = 0;
792 MOZ_CRASH("unreachable");
793 }
794 }
795
FillAddrInfo(GMutLock,uintptr_t aIndex,const void * aBaseAddr,bool isGuardPage,phc::AddrInfo & aOut)796 void FillAddrInfo(GMutLock, uintptr_t aIndex, const void* aBaseAddr,
797 bool isGuardPage, phc::AddrInfo& aOut) {
798 const AllocPageInfo& page = mAllocPages[aIndex];
799 if (isGuardPage) {
800 aOut.mKind = phc::AddrInfo::Kind::GuardPage;
801 } else {
802 switch (page.mState) {
803 case AllocPageState::NeverAllocated:
804 aOut.mKind = phc::AddrInfo::Kind::NeverAllocatedPage;
805 break;
806
807 case AllocPageState::InUse:
808 aOut.mKind = phc::AddrInfo::Kind::InUsePage;
809 break;
810
811 case AllocPageState::Freed:
812 aOut.mKind = phc::AddrInfo::Kind::FreedPage;
813 break;
814
815 default:
816 MOZ_CRASH();
817 }
818 }
819 aOut.mBaseAddr = page.mBaseAddr;
820 aOut.mUsableSize = page.UsableSize();
821 aOut.mAllocStack = page.mAllocStack;
822 aOut.mFreeStack = page.mFreeStack;
823 }
824
FillJemallocPtrInfo(GMutLock,const void * aPtr,uintptr_t aIndex,jemalloc_ptr_info_t * aInfo)825 void FillJemallocPtrInfo(GMutLock, const void* aPtr, uintptr_t aIndex,
826 jemalloc_ptr_info_t* aInfo) {
827 const AllocPageInfo& page = mAllocPages[aIndex];
828 switch (page.mState) {
829 case AllocPageState::NeverAllocated:
830 break;
831
832 case AllocPageState::InUse: {
833 // Only return TagLiveAlloc if the pointer is within the bounds of the
834 // allocation's usable size.
835 uint8_t* base = page.mBaseAddr;
836 uint8_t* limit = base + page.UsableSize();
837 if (base <= aPtr && aPtr < limit) {
838 *aInfo = {TagLiveAlloc, page.mBaseAddr, page.UsableSize(),
839 page.mArenaId.valueOr(0)};
840 return;
841 }
842 break;
843 }
844
845 case AllocPageState::Freed: {
846 // Only return TagFreedAlloc if the pointer is within the bounds of the
847 // former allocation's usable size.
848 uint8_t* base = page.mBaseAddr;
849 uint8_t* limit = base + page.UsableSize();
850 if (base <= aPtr && aPtr < limit) {
851 *aInfo = {TagFreedAlloc, page.mBaseAddr, page.UsableSize(),
852 page.mArenaId.valueOr(0)};
853 return;
854 }
855 break;
856 }
857
858 default:
859 MOZ_CRASH();
860 }
861
862 // Pointers into guard pages will end up here, as will pointers into
863 // allocation pages that aren't within the allocation's bounds.
864 *aInfo = {TagUnknown, nullptr, 0, 0};
865 }
866
prefork()867 static void prefork() { sMutex.Lock(); }
postfork()868 static void postfork() { sMutex.Unlock(); }
869
IncPageAllocHits(GMutLock)870 void IncPageAllocHits(GMutLock) { mPageAllocHits++; }
IncPageAllocMisses(GMutLock)871 void IncPageAllocMisses(GMutLock) { mPageAllocMisses++; }
872
NumPageAllocs(GMutLock)873 size_t NumPageAllocs(GMutLock) { return mNumPageAllocs; }
874
PageAllocHits(GMutLock)875 size_t PageAllocHits(GMutLock) { return mPageAllocHits; }
PageAllocAttempts(GMutLock)876 size_t PageAllocAttempts(GMutLock) {
877 return mPageAllocHits + mPageAllocMisses;
878 }
879
880 // This is an integer because FdPrintf only supports integer printing.
PageAllocHitRate(GMutLock)881 size_t PageAllocHitRate(GMutLock) {
882 return mPageAllocHits * 100 / (mPageAllocHits + mPageAllocMisses);
883 }
884
885 private:
886 template <int N>
RandomSeed()887 uint64_t RandomSeed() {
888 // An older version of this code used RandomUint64() here, but on Mac that
889 // function uses arc4random(), which can allocate, which would cause
890 // re-entry, which would be bad. So we just use time() and a local variable
891 // address. These are mediocre sources of entropy, but good enough for PHC.
892 static_assert(N == 0 || N == 1, "must be 0 or 1");
893 uint64_t seed;
894 if (N == 0) {
895 time_t t = time(nullptr);
896 seed = t ^ (t << 32);
897 } else {
898 seed = uintptr_t(&seed) ^ (uintptr_t(&seed) << 32);
899 }
900 return seed;
901 }
902
AssertAllocPageInUse(GMutLock,const AllocPageInfo & aPage)903 void AssertAllocPageInUse(GMutLock, const AllocPageInfo& aPage) {
904 MOZ_ASSERT(aPage.mState == AllocPageState::InUse);
905 // There is nothing to assert about aPage.mArenaId.
906 MOZ_ASSERT(aPage.mBaseAddr);
907 MOZ_ASSERT(aPage.UsableSize() > 0);
908 MOZ_ASSERT(aPage.mAllocStack.isSome());
909 MOZ_ASSERT(aPage.mFreeStack.isNothing());
910 MOZ_ASSERT(aPage.mReuseTime == kMaxTime);
911 }
912
AssertAllocPageNotInUse(GMutLock,const AllocPageInfo & aPage)913 void AssertAllocPageNotInUse(GMutLock, const AllocPageInfo& aPage) {
914 // We can assert a lot about `NeverAllocated` pages, but not much about
915 // `Freed` pages.
916 #ifdef DEBUG
917 bool isFresh = aPage.mState == AllocPageState::NeverAllocated;
918 MOZ_ASSERT(isFresh || aPage.mState == AllocPageState::Freed);
919 MOZ_ASSERT_IF(isFresh, aPage.mArenaId == Nothing());
920 MOZ_ASSERT(isFresh == (aPage.mBaseAddr == nullptr));
921 MOZ_ASSERT(isFresh == (aPage.mAllocStack.isNothing()));
922 MOZ_ASSERT(isFresh == (aPage.mFreeStack.isNothing()));
923 MOZ_ASSERT(aPage.mReuseTime != kMaxTime);
924 #endif
925 }
926
927 // RNG for deciding which allocations to treat specially. It doesn't need to
928 // be high quality.
929 //
930 // This is a raw pointer for the reason explained in the comment above
931 // GMut's constructor. Don't change it to UniquePtr or anything like that.
932 non_crypto::XorShift128PlusRNG mRNG;
933
934 AllocPageInfo mAllocPages[kNumAllocPages];
935
936 // How many page allocs are currently in use (the max is kNumAllocPages).
937 size_t mNumPageAllocs;
938
939 // How many allocations that could have been page allocs actually were? As
940 // constrained kNumAllocPages. If the hit ratio isn't close to 100% it's
941 // likely that the global constants are poorly chosen.
942 size_t mPageAllocHits;
943 size_t mPageAllocMisses;
944 };
945
946 Mutex GMut::sMutex;
947
948 static GMut* gMut;
949
950 //---------------------------------------------------------------------------
951 // Page allocation operations
952 //---------------------------------------------------------------------------
953
954 // Attempt a page allocation if the time and the size are right. Allocated
955 // memory is zeroed if aZero is true. On failure, the caller should attempt a
956 // normal allocation via sMallocTable. Can be called in a context where
957 // GMut::sMutex is locked.
MaybePageAlloc(const Maybe<arena_id_t> & aArenaId,size_t aReqSize,size_t aAlignment,bool aZero)958 static void* MaybePageAlloc(const Maybe<arena_id_t>& aArenaId, size_t aReqSize,
959 size_t aAlignment, bool aZero) {
960 MOZ_ASSERT(IsPowerOfTwo(aAlignment));
961
962 if (aReqSize > kPageSize) {
963 return nullptr;
964 }
965
966 GAtomic::IncrementNow();
967
968 // Decrement the delay. If it's zero, we do a page allocation and reset the
969 // delay to a random number. Because the assignment to the random number isn't
970 // atomic w.r.t. the decrement, we might have a sequence like this:
971 //
972 // Thread 1 Thread 2 Thread 3
973 // -------- -------- --------
974 // (a) newDelay = --sAllocDelay (-> 0)
975 // (b) --sAllocDelay (-> -1)
976 // (c) (newDelay != 0) fails
977 // (d) --sAllocDelay (-> -2)
978 // (e) sAllocDelay = new_random_number()
979 //
980 // It's critical that sAllocDelay has ReleaseAcquire semantics, because that
981 // guarantees that exactly one thread will see sAllocDelay have the value 0.
982 // (Relaxed semantics wouldn't guarantee that.)
983 //
984 // It's also nice that sAllocDelay is signed, given that we can decrement to
985 // below zero. (Strictly speaking, an unsigned integer would also work due
986 // to wrapping, but a signed integer is conceptually cleaner.)
987 //
988 // Finally, note that the decrements that occur between (a) and (e) above are
989 // effectively ignored, because (e) clobbers them. This shouldn't be a
990 // problem; it effectively just adds a little more randomness to
991 // new_random_number(). An early version of this code tried to account for
992 // these decrements by doing `sAllocDelay += new_random_number()`. However, if
993 // new_random_value() is small, the number of decrements between (a) and (e)
994 // can easily exceed it, whereupon sAllocDelay ends up negative after
995 // `sAllocDelay += new_random_number()`, and the zero-check never succeeds
996 // again. (At least, not until sAllocDelay wraps around on overflow, which
997 // would take a very long time indeed.)
998 //
999 int32_t newDelay = GAtomic::DecrementDelay();
1000 if (newDelay != 0) {
1001 return nullptr;
1002 }
1003
1004 if (GTls::IsDisabledOnCurrentThread()) {
1005 return nullptr;
1006 }
1007
1008 // Disable on this thread *before* getting the stack trace.
1009 AutoDisableOnCurrentThread disable;
1010
1011 // Get the stack trace *before* locking the mutex. If we return nullptr then
1012 // it was a waste, but it's not so frequent, and doing a stack walk while
1013 // the mutex is locked is problematic (see the big comment on
1014 // StackTrace::Fill() for details).
1015 StackTrace allocStack;
1016 allocStack.Fill();
1017
1018 MutexAutoLock lock(GMut::sMutex);
1019
1020 Time now = GAtomic::Now();
1021 Delay newAllocDelay = Rnd64ToDelay<kAvgAllocDelay>(gMut->Random64(lock));
1022
1023 // We start at a random page alloc and wrap around, to ensure pages get even
1024 // amounts of use.
1025 uint8_t* ptr = nullptr;
1026 uint8_t* pagePtr = nullptr;
1027 for (uintptr_t n = 0, i = size_t(gMut->Random64(lock)) % kNumAllocPages;
1028 n < kNumAllocPages; n++, i = (i + 1) % kNumAllocPages) {
1029 if (!gMut->IsPageAllocatable(lock, i, now)) {
1030 continue;
1031 }
1032
1033 pagePtr = gConst->AllocPagePtr(i);
1034 MOZ_ASSERT(pagePtr);
1035 bool ok =
1036 #ifdef XP_WIN
1037 !!VirtualAlloc(pagePtr, kPageSize, MEM_COMMIT, PAGE_READWRITE);
1038 #else
1039 mprotect(pagePtr, kPageSize, PROT_READ | PROT_WRITE) == 0;
1040 #endif
1041 size_t usableSize = sMallocTable.malloc_good_size(aReqSize);
1042 if (ok) {
1043 MOZ_ASSERT(usableSize > 0);
1044
1045 // Put the allocation as close to the end of the page as possible,
1046 // allowing for alignment requirements.
1047 ptr = pagePtr + kPageSize - usableSize;
1048 if (aAlignment != 1) {
1049 ptr = reinterpret_cast<uint8_t*>(
1050 (reinterpret_cast<uintptr_t>(ptr) & ~(aAlignment - 1)));
1051 }
1052
1053 gMut->SetPageInUse(lock, i, aArenaId, ptr, allocStack);
1054
1055 if (aZero) {
1056 memset(ptr, 0, usableSize);
1057 } else {
1058 #ifdef DEBUG
1059 memset(ptr, kAllocJunk, usableSize);
1060 #endif
1061 }
1062 }
1063
1064 gMut->IncPageAllocHits(lock);
1065 LOG("PageAlloc(%zu, %zu) -> %p[%zu]/%p (%zu) (z%zu), sAllocDelay <- %zu, "
1066 "fullness %zu/%zu, hits %zu/%zu (%zu%%)\n",
1067 aReqSize, aAlignment, pagePtr, i, ptr, usableSize, size_t(aZero),
1068 size_t(newAllocDelay), gMut->NumPageAllocs(lock), kNumAllocPages,
1069 gMut->PageAllocHits(lock), gMut->PageAllocAttempts(lock),
1070 gMut->PageAllocHitRate(lock));
1071 break;
1072 }
1073
1074 if (!pagePtr) {
1075 // No pages are available, or VirtualAlloc/mprotect failed.
1076 gMut->IncPageAllocMisses(lock);
1077 LOG("No PageAlloc(%zu, %zu), sAllocDelay <- %zu, fullness %zu/%zu, hits "
1078 "%zu/%zu "
1079 "(%zu%%)\n",
1080 aReqSize, aAlignment, size_t(newAllocDelay), gMut->NumPageAllocs(lock),
1081 kNumAllocPages, gMut->PageAllocHits(lock),
1082 gMut->PageAllocAttempts(lock), gMut->PageAllocHitRate(lock));
1083 }
1084
1085 // Set the new alloc delay.
1086 GAtomic::SetAllocDelay(newAllocDelay);
1087
1088 return ptr;
1089 }
1090
FreePage(GMutLock aLock,uintptr_t aIndex,const Maybe<arena_id_t> & aArenaId,const StackTrace & aFreeStack,Delay aReuseDelay)1091 static void FreePage(GMutLock aLock, uintptr_t aIndex,
1092 const Maybe<arena_id_t>& aArenaId,
1093 const StackTrace& aFreeStack, Delay aReuseDelay) {
1094 void* pagePtr = gConst->AllocPagePtr(aIndex);
1095 #ifdef XP_WIN
1096 if (!VirtualFree(pagePtr, kPageSize, MEM_DECOMMIT)) {
1097 return;
1098 }
1099 #else
1100 if (!mmap(pagePtr, kPageSize, PROT_NONE, MAP_FIXED | MAP_PRIVATE | MAP_ANON,
1101 -1, 0)) {
1102 return;
1103 }
1104 #endif
1105
1106 gMut->SetPageFreed(aLock, aIndex, aArenaId, aFreeStack, aReuseDelay);
1107 }
1108
1109 //---------------------------------------------------------------------------
1110 // replace-malloc machinery
1111 //---------------------------------------------------------------------------
1112
1113 // This handles malloc, moz_arena_malloc, and realloc-with-a-nullptr.
PageMalloc(const Maybe<arena_id_t> & aArenaId,size_t aReqSize)1114 MOZ_ALWAYS_INLINE static void* PageMalloc(const Maybe<arena_id_t>& aArenaId,
1115 size_t aReqSize) {
1116 void* ptr = MaybePageAlloc(aArenaId, aReqSize, /* aAlignment */ 1,
1117 /* aZero */ false);
1118 return ptr ? ptr
1119 : (aArenaId.isSome()
1120 ? sMallocTable.moz_arena_malloc(*aArenaId, aReqSize)
1121 : sMallocTable.malloc(aReqSize));
1122 }
1123
replace_malloc(size_t aReqSize)1124 static void* replace_malloc(size_t aReqSize) {
1125 return PageMalloc(Nothing(), aReqSize);
1126 }
1127
ReuseDelay(GMutLock aLock)1128 static Delay ReuseDelay(GMutLock aLock) {
1129 return (kAvgPageReuseDelay / 2) +
1130 Rnd64ToDelay<kAvgPageReuseDelay / 2>(gMut->Random64(aLock));
1131 }
1132
1133 // This handles both calloc and moz_arena_calloc.
PageCalloc(const Maybe<arena_id_t> & aArenaId,size_t aNum,size_t aReqSize)1134 MOZ_ALWAYS_INLINE static void* PageCalloc(const Maybe<arena_id_t>& aArenaId,
1135 size_t aNum, size_t aReqSize) {
1136 CheckedInt<size_t> checkedSize = CheckedInt<size_t>(aNum) * aReqSize;
1137 if (!checkedSize.isValid()) {
1138 return nullptr;
1139 }
1140
1141 void* ptr = MaybePageAlloc(aArenaId, checkedSize.value(), /* aAlignment */ 1,
1142 /* aZero */ true);
1143 return ptr ? ptr
1144 : (aArenaId.isSome()
1145 ? sMallocTable.moz_arena_calloc(*aArenaId, aNum, aReqSize)
1146 : sMallocTable.calloc(aNum, aReqSize));
1147 }
1148
replace_calloc(size_t aNum,size_t aReqSize)1149 static void* replace_calloc(size_t aNum, size_t aReqSize) {
1150 return PageCalloc(Nothing(), aNum, aReqSize);
1151 }
1152
1153 // This function handles both realloc and moz_arena_realloc.
1154 //
1155 // As always, realloc is complicated, and doubly so when there are two
1156 // different kinds of allocations in play. Here are the possible transitions,
1157 // and what we do in practice.
1158 //
1159 // - normal-to-normal: This is straightforward and obviously necessary.
1160 //
1161 // - normal-to-page: This is disallowed because it would require getting the
1162 // arenaId of the normal allocation, which isn't possible in non-DEBUG builds
1163 // for security reasons.
1164 //
1165 // - page-to-page: This is done whenever possible, i.e. whenever the new size
1166 // is less than or equal to 4 KiB. This choice counterbalances the
1167 // disallowing of normal-to-page allocations, in order to avoid biasing
1168 // towards or away from page allocations. It always occurs in-place.
1169 //
1170 // - page-to-normal: this is done only when necessary, i.e. only when the new
1171 // size is greater than 4 KiB. This choice naturally flows from the
1172 // prior choice on page-to-page transitions.
1173 //
1174 // In summary: realloc doesn't change the allocation kind unless it must.
1175 //
PageRealloc(const Maybe<arena_id_t> & aArenaId,void * aOldPtr,size_t aNewSize)1176 MOZ_ALWAYS_INLINE static void* PageRealloc(const Maybe<arena_id_t>& aArenaId,
1177 void* aOldPtr, size_t aNewSize) {
1178 if (!aOldPtr) {
1179 // Null pointer. Treat like malloc(aNewSize).
1180 return PageMalloc(aArenaId, aNewSize);
1181 }
1182
1183 PtrKind pk = gConst->PtrKind(aOldPtr);
1184 if (pk.IsNothing()) {
1185 // A normal-to-normal transition.
1186 return aArenaId.isSome()
1187 ? sMallocTable.moz_arena_realloc(*aArenaId, aOldPtr, aNewSize)
1188 : sMallocTable.realloc(aOldPtr, aNewSize);
1189 }
1190
1191 if (pk.IsGuardPage()) {
1192 GMut::CrashOnGuardPage(aOldPtr);
1193 }
1194
1195 // At this point we know we have an allocation page.
1196 uintptr_t index = pk.AllocPageIndex();
1197
1198 // A page-to-something transition.
1199
1200 // Note that `disable` has no effect unless it is emplaced below.
1201 Maybe<AutoDisableOnCurrentThread> disable;
1202 // Get the stack trace *before* locking the mutex.
1203 StackTrace stack;
1204 if (GTls::IsDisabledOnCurrentThread()) {
1205 // PHC is disabled on this thread. Leave the stack empty.
1206 } else {
1207 // Disable on this thread *before* getting the stack trace.
1208 disable.emplace();
1209 stack.Fill();
1210 }
1211
1212 MutexAutoLock lock(GMut::sMutex);
1213
1214 // Check for realloc() of a freed block.
1215 gMut->EnsureValidAndInUse(lock, aOldPtr, index);
1216
1217 if (aNewSize <= kPageSize) {
1218 // A page-to-page transition. Just keep using the page allocation. We do
1219 // this even if the thread is disabled, because it doesn't create a new
1220 // page allocation. Note that ResizePageInUse() checks aArenaId.
1221 //
1222 // Move the bytes with memmove(), because the old allocation and the new
1223 // allocation overlap. Move the usable size rather than the requested size,
1224 // because the user might have used malloc_usable_size() and filled up the
1225 // usable size.
1226 size_t oldUsableSize = gMut->PageUsableSize(lock, index);
1227 size_t newUsableSize = sMallocTable.malloc_good_size(aNewSize);
1228 uint8_t* pagePtr = gConst->AllocPagePtr(index);
1229 uint8_t* newPtr = pagePtr + kPageSize - newUsableSize;
1230 memmove(newPtr, aOldPtr, std::min(oldUsableSize, aNewSize));
1231 gMut->ResizePageInUse(lock, index, aArenaId, newPtr, stack);
1232 LOG("PageRealloc-Reuse(%p, %zu) -> %p\n", aOldPtr, aNewSize, newPtr);
1233 return newPtr;
1234 }
1235
1236 // A page-to-normal transition (with the new size greater than page-sized).
1237 // (Note that aArenaId is checked below.)
1238 void* newPtr;
1239 if (aArenaId.isSome()) {
1240 newPtr = sMallocTable.moz_arena_malloc(*aArenaId, aNewSize);
1241 } else {
1242 Maybe<arena_id_t> oldArenaId = gMut->PageArena(lock, index);
1243 newPtr = (oldArenaId.isSome()
1244 ? sMallocTable.moz_arena_malloc(*oldArenaId, aNewSize)
1245 : sMallocTable.malloc(aNewSize));
1246 }
1247 if (!newPtr) {
1248 return nullptr;
1249 }
1250
1251 MOZ_ASSERT(aNewSize > kPageSize);
1252
1253 Delay reuseDelay = ReuseDelay(lock);
1254
1255 // Copy the usable size rather than the requested size, because the user
1256 // might have used malloc_usable_size() and filled up the usable size. Note
1257 // that FreePage() checks aArenaId (via SetPageFreed()).
1258 size_t oldUsableSize = gMut->PageUsableSize(lock, index);
1259 memcpy(newPtr, aOldPtr, std::min(oldUsableSize, aNewSize));
1260 FreePage(lock, index, aArenaId, stack, reuseDelay);
1261 LOG("PageRealloc-Free(%p[%zu], %zu) -> %p, %zu delay, reuse at ~%zu\n",
1262 aOldPtr, index, aNewSize, newPtr, size_t(reuseDelay),
1263 size_t(GAtomic::Now()) + reuseDelay);
1264
1265 return newPtr;
1266 }
1267
replace_realloc(void * aOldPtr,size_t aNewSize)1268 static void* replace_realloc(void* aOldPtr, size_t aNewSize) {
1269 return PageRealloc(Nothing(), aOldPtr, aNewSize);
1270 }
1271
1272 // This handles both free and moz_arena_free.
PageFree(const Maybe<arena_id_t> & aArenaId,void * aPtr)1273 MOZ_ALWAYS_INLINE static void PageFree(const Maybe<arena_id_t>& aArenaId,
1274 void* aPtr) {
1275 PtrKind pk = gConst->PtrKind(aPtr);
1276 if (pk.IsNothing()) {
1277 // Not a page allocation.
1278 return aArenaId.isSome() ? sMallocTable.moz_arena_free(*aArenaId, aPtr)
1279 : sMallocTable.free(aPtr);
1280 }
1281
1282 if (pk.IsGuardPage()) {
1283 GMut::CrashOnGuardPage(aPtr);
1284 }
1285
1286 // At this point we know we have an allocation page.
1287 uintptr_t index = pk.AllocPageIndex();
1288
1289 // Note that `disable` has no effect unless it is emplaced below.
1290 Maybe<AutoDisableOnCurrentThread> disable;
1291 // Get the stack trace *before* locking the mutex.
1292 StackTrace freeStack;
1293 if (GTls::IsDisabledOnCurrentThread()) {
1294 // PHC is disabled on this thread. Leave the stack empty.
1295 } else {
1296 // Disable on this thread *before* getting the stack trace.
1297 disable.emplace();
1298 freeStack.Fill();
1299 }
1300
1301 MutexAutoLock lock(GMut::sMutex);
1302
1303 // Check for a double-free.
1304 gMut->EnsureValidAndInUse(lock, aPtr, index);
1305
1306 // Note that FreePage() checks aArenaId (via SetPageFreed()).
1307 Delay reuseDelay = ReuseDelay(lock);
1308 FreePage(lock, index, aArenaId, freeStack, reuseDelay);
1309
1310 LOG("PageFree(%p[%zu]), %zu delay, reuse at ~%zu, fullness %zu/%zu\n", aPtr,
1311 index, size_t(reuseDelay), size_t(GAtomic::Now()) + reuseDelay,
1312 gMut->NumPageAllocs(lock), kNumAllocPages);
1313 }
1314
replace_free(void * aPtr)1315 static void replace_free(void* aPtr) { return PageFree(Nothing(), aPtr); }
1316
1317 // This handles memalign and moz_arena_memalign.
PageMemalign(const Maybe<arena_id_t> & aArenaId,size_t aAlignment,size_t aReqSize)1318 MOZ_ALWAYS_INLINE static void* PageMemalign(const Maybe<arena_id_t>& aArenaId,
1319 size_t aAlignment,
1320 size_t aReqSize) {
1321 MOZ_RELEASE_ASSERT(IsPowerOfTwo(aAlignment));
1322
1323 // PHC can't satisfy an alignment greater than a page size, so fall back to
1324 // mozjemalloc in that case.
1325 void* ptr = nullptr;
1326 if (aAlignment <= kPageSize) {
1327 ptr = MaybePageAlloc(aArenaId, aReqSize, aAlignment, /* aZero */ false);
1328 }
1329 return ptr ? ptr
1330 : (aArenaId.isSome()
1331 ? sMallocTable.moz_arena_memalign(*aArenaId, aAlignment,
1332 aReqSize)
1333 : sMallocTable.memalign(aAlignment, aReqSize));
1334 }
1335
replace_memalign(size_t aAlignment,size_t aReqSize)1336 static void* replace_memalign(size_t aAlignment, size_t aReqSize) {
1337 return PageMemalign(Nothing(), aAlignment, aReqSize);
1338 }
1339
replace_malloc_usable_size(usable_ptr_t aPtr)1340 static size_t replace_malloc_usable_size(usable_ptr_t aPtr) {
1341 PtrKind pk = gConst->PtrKind(aPtr);
1342 if (pk.IsNothing()) {
1343 // Not a page allocation. Measure it normally.
1344 return sMallocTable.malloc_usable_size(aPtr);
1345 }
1346
1347 if (pk.IsGuardPage()) {
1348 GMut::CrashOnGuardPage(const_cast<void*>(aPtr));
1349 }
1350
1351 // At this point we know we have an allocation page.
1352 uintptr_t index = pk.AllocPageIndex();
1353
1354 MutexAutoLock lock(GMut::sMutex);
1355
1356 // Check for malloc_usable_size() of a freed block.
1357 gMut->EnsureValidAndInUse(lock, const_cast<void*>(aPtr), index);
1358
1359 return gMut->PageUsableSize(lock, index);
1360 }
1361
replace_jemalloc_stats(jemalloc_stats_t * aStats,jemalloc_bin_stats_t * aBinStats)1362 void replace_jemalloc_stats(jemalloc_stats_t* aStats,
1363 jemalloc_bin_stats_t* aBinStats) {
1364 sMallocTable.jemalloc_stats_internal(aStats, aBinStats);
1365
1366 // Add all the pages to `mapped`.
1367 size_t mapped = kAllPagesSize;
1368 aStats->mapped += mapped;
1369
1370 size_t allocated = 0;
1371 {
1372 MutexAutoLock lock(GMut::sMutex);
1373
1374 // Add usable space of in-use allocations to `allocated`.
1375 for (size_t i = 0; i < kNumAllocPages; i++) {
1376 if (gMut->IsPageInUse(lock, i)) {
1377 allocated += gMut->PageUsableSize(lock, i);
1378 }
1379 }
1380 }
1381 aStats->allocated += allocated;
1382
1383 // Waste is the gap between `allocated` and `mapped`.
1384 size_t waste = mapped - allocated;
1385 aStats->waste += waste;
1386
1387 // aStats.page_cache and aStats.bin_unused are left unchanged because PHC
1388 // doesn't have anything corresponding to those.
1389
1390 // gConst and gMut are normal heap allocations, so they're measured by
1391 // mozjemalloc as `allocated`. Move them into `bookkeeping`.
1392 size_t bookkeeping = sMallocTable.malloc_usable_size(gConst) +
1393 sMallocTable.malloc_usable_size(gMut);
1394 aStats->allocated -= bookkeeping;
1395 aStats->bookkeeping += bookkeeping;
1396 }
1397
replace_jemalloc_ptr_info(const void * aPtr,jemalloc_ptr_info_t * aInfo)1398 void replace_jemalloc_ptr_info(const void* aPtr, jemalloc_ptr_info_t* aInfo) {
1399 // We need to implement this properly, because various code locations do
1400 // things like checking that allocations are in the expected arena.
1401 PtrKind pk = gConst->PtrKind(aPtr);
1402 if (pk.IsNothing()) {
1403 // Not a page allocation.
1404 return sMallocTable.jemalloc_ptr_info(aPtr, aInfo);
1405 }
1406
1407 if (pk.IsGuardPage()) {
1408 // Treat a guard page as unknown because there's no better alternative.
1409 *aInfo = {TagUnknown, nullptr, 0, 0};
1410 return;
1411 }
1412
1413 // At this point we know we have an allocation page.
1414 uintptr_t index = pk.AllocPageIndex();
1415
1416 MutexAutoLock lock(GMut::sMutex);
1417
1418 gMut->FillJemallocPtrInfo(lock, aPtr, index, aInfo);
1419 #if DEBUG
1420 LOG("JemallocPtrInfo(%p[%zu]) -> {%zu, %p, %zu, %zu}\n", aPtr, index,
1421 size_t(aInfo->tag), aInfo->addr, aInfo->size, aInfo->arenaId);
1422 #else
1423 LOG("JemallocPtrInfo(%p[%zu]) -> {%zu, %p, %zu}\n", aPtr, index,
1424 size_t(aInfo->tag), aInfo->addr, aInfo->size);
1425 #endif
1426 }
1427
replace_moz_create_arena_with_params(arena_params_t * aParams)1428 arena_id_t replace_moz_create_arena_with_params(arena_params_t* aParams) {
1429 // No need to do anything special here.
1430 return sMallocTable.moz_create_arena_with_params(aParams);
1431 }
1432
replace_moz_dispose_arena(arena_id_t aArenaId)1433 void replace_moz_dispose_arena(arena_id_t aArenaId) {
1434 // No need to do anything special here.
1435 return sMallocTable.moz_dispose_arena(aArenaId);
1436 }
1437
replace_moz_arena_malloc(arena_id_t aArenaId,size_t aReqSize)1438 void* replace_moz_arena_malloc(arena_id_t aArenaId, size_t aReqSize) {
1439 return PageMalloc(Some(aArenaId), aReqSize);
1440 }
1441
replace_moz_arena_calloc(arena_id_t aArenaId,size_t aNum,size_t aReqSize)1442 void* replace_moz_arena_calloc(arena_id_t aArenaId, size_t aNum,
1443 size_t aReqSize) {
1444 return PageCalloc(Some(aArenaId), aNum, aReqSize);
1445 }
1446
replace_moz_arena_realloc(arena_id_t aArenaId,void * aOldPtr,size_t aNewSize)1447 void* replace_moz_arena_realloc(arena_id_t aArenaId, void* aOldPtr,
1448 size_t aNewSize) {
1449 return PageRealloc(Some(aArenaId), aOldPtr, aNewSize);
1450 }
1451
replace_moz_arena_free(arena_id_t aArenaId,void * aPtr)1452 void replace_moz_arena_free(arena_id_t aArenaId, void* aPtr) {
1453 return PageFree(Some(aArenaId), aPtr);
1454 }
1455
replace_moz_arena_memalign(arena_id_t aArenaId,size_t aAlignment,size_t aReqSize)1456 void* replace_moz_arena_memalign(arena_id_t aArenaId, size_t aAlignment,
1457 size_t aReqSize) {
1458 return PageMemalign(Some(aArenaId), aAlignment, aReqSize);
1459 }
1460
1461 class PHCBridge : public ReplaceMallocBridge {
IsPHCAllocation(const void * aPtr,phc::AddrInfo * aOut)1462 virtual bool IsPHCAllocation(const void* aPtr, phc::AddrInfo* aOut) override {
1463 PtrKind pk = gConst->PtrKind(aPtr);
1464 if (pk.IsNothing()) {
1465 return false;
1466 }
1467
1468 bool isGuardPage = false;
1469 if (pk.IsGuardPage()) {
1470 if ((uintptr_t(aPtr) % kPageSize) < (kPageSize / 2)) {
1471 // The address is in the lower half of a guard page, so it's probably an
1472 // overflow. But first check that it is not on the very first guard
1473 // page, in which case it cannot be an overflow, and we ignore it.
1474 if (gConst->IsInFirstGuardPage(aPtr)) {
1475 return false;
1476 }
1477
1478 // Get the allocation page preceding this guard page.
1479 pk = gConst->PtrKind(static_cast<const uint8_t*>(aPtr) - kPageSize);
1480
1481 } else {
1482 // The address is in the upper half of a guard page, so it's probably an
1483 // underflow. Get the allocation page following this guard page.
1484 pk = gConst->PtrKind(static_cast<const uint8_t*>(aPtr) + kPageSize);
1485 }
1486
1487 // Make a note of the fact that we hit a guard page.
1488 isGuardPage = true;
1489 }
1490
1491 // At this point we know we have an allocation page.
1492 uintptr_t index = pk.AllocPageIndex();
1493
1494 if (aOut) {
1495 MutexAutoLock lock(GMut::sMutex);
1496 gMut->FillAddrInfo(lock, index, aPtr, isGuardPage, *aOut);
1497 LOG("IsPHCAllocation: %zu, %p, %zu, %zu, %zu\n", size_t(aOut->mKind),
1498 aOut->mBaseAddr, aOut->mUsableSize,
1499 aOut->mAllocStack.isSome() ? aOut->mAllocStack->mLength : 0,
1500 aOut->mFreeStack.isSome() ? aOut->mFreeStack->mLength : 0);
1501 }
1502 return true;
1503 }
1504
DisablePHCOnCurrentThread()1505 virtual void DisablePHCOnCurrentThread() override {
1506 GTls::DisableOnCurrentThread();
1507 LOG("DisablePHCOnCurrentThread: %zu\n", 0ul);
1508 }
1509
ReenablePHCOnCurrentThread()1510 virtual void ReenablePHCOnCurrentThread() override {
1511 GTls::EnableOnCurrentThread();
1512 LOG("ReenablePHCOnCurrentThread: %zu\n", 0ul);
1513 }
1514
IsPHCEnabledOnCurrentThread()1515 virtual bool IsPHCEnabledOnCurrentThread() override {
1516 bool enabled = !GTls::IsDisabledOnCurrentThread();
1517 LOG("IsPHCEnabledOnCurrentThread: %zu\n", size_t(enabled));
1518 return enabled;
1519 }
1520 };
1521
1522 // WARNING: this function runs *very* early -- before all static initializers
1523 // have run. For this reason, non-scalar globals (gConst, gMut) are allocated
1524 // dynamically (so we can guarantee their construction in this function) rather
1525 // than statically. GAtomic and GTls contain simple static data that doesn't
1526 // involve static initializers so they don't need to be allocated dynamically.
replace_init(malloc_table_t * aMallocTable,ReplaceMallocBridge ** aBridge)1527 void replace_init(malloc_table_t* aMallocTable, ReplaceMallocBridge** aBridge) {
1528 // Don't run PHC if the page size isn't 4 KiB.
1529 jemalloc_stats_t stats;
1530 aMallocTable->jemalloc_stats_internal(&stats, nullptr);
1531 if (stats.page_size != kPageSize) {
1532 return;
1533 }
1534
1535 sMallocTable = *aMallocTable;
1536
1537 // The choices of which functions to replace are complex enough that we set
1538 // them individually instead of using MALLOC_FUNCS/malloc_decls.h.
1539
1540 aMallocTable->malloc = replace_malloc;
1541 aMallocTable->calloc = replace_calloc;
1542 aMallocTable->realloc = replace_realloc;
1543 aMallocTable->free = replace_free;
1544 aMallocTable->memalign = replace_memalign;
1545
1546 // posix_memalign, aligned_alloc & valloc: unset, which means they fall back
1547 // to replace_memalign.
1548 aMallocTable->malloc_usable_size = replace_malloc_usable_size;
1549 // default malloc_good_size: the default suffices.
1550
1551 aMallocTable->jemalloc_stats_internal = replace_jemalloc_stats;
1552 // jemalloc_purge_freed_pages: the default suffices.
1553 // jemalloc_free_dirty_pages: the default suffices.
1554 // jemalloc_thread_local_arena: the default suffices.
1555 aMallocTable->jemalloc_ptr_info = replace_jemalloc_ptr_info;
1556
1557 aMallocTable->moz_create_arena_with_params =
1558 replace_moz_create_arena_with_params;
1559 aMallocTable->moz_dispose_arena = replace_moz_dispose_arena;
1560 aMallocTable->moz_arena_malloc = replace_moz_arena_malloc;
1561 aMallocTable->moz_arena_calloc = replace_moz_arena_calloc;
1562 aMallocTable->moz_arena_realloc = replace_moz_arena_realloc;
1563 aMallocTable->moz_arena_free = replace_moz_arena_free;
1564 aMallocTable->moz_arena_memalign = replace_moz_arena_memalign;
1565
1566 static PHCBridge bridge;
1567 *aBridge = &bridge;
1568
1569 #ifndef XP_WIN
1570 // Avoid deadlocks when forking by acquiring our state lock prior to forking
1571 // and releasing it after forking. See |LogAlloc|'s |replace_init| for
1572 // in-depth details.
1573 //
1574 // Note: This must run after attempting an allocation so as to give the
1575 // system malloc a chance to insert its own atfork handler.
1576 sMallocTable.malloc(-1);
1577 pthread_atfork(GMut::prefork, GMut::postfork, GMut::postfork);
1578 #endif
1579
1580 // gConst and gMut are never freed. They live for the life of the process.
1581 gConst = InfallibleAllocPolicy::new_<GConst>();
1582 GTls::Init();
1583 gMut = InfallibleAllocPolicy::new_<GMut>();
1584 {
1585 MutexAutoLock lock(GMut::sMutex);
1586 Delay firstAllocDelay =
1587 Rnd64ToDelay<kAvgFirstAllocDelay>(gMut->Random64(lock));
1588 GAtomic::Init(firstAllocDelay);
1589 }
1590 }
1591