summaryrefslogtreecommitdiff
path: root/lib/scudo/scudo_allocator.cpp
AgeCommit message (Collapse)Author
2017-12-14[scudo] Refactor ScudoChunkKostya Kortchinsky
Summary: The initial implementation used an ASan like Chunk class that was deriving from a Header class. Due to potential races, we ended up working with local copies of the Header and never using the parent class fields. ScudoChunk was never constructed but cast, and we were using `this` as the pointer needed for our computations. This was meh. So we refactored ScudoChunk to be now a series of static functions within the namespace `__scudo::Chunk` that take a "user" pointer as first parameter (former `this`). A compiled binary doesn't really change, but the code is more sensible. Clang tends to inline all those small function (in -O2), but GCC left a few not inlined, so we add the `INLINE` keyword to all. Since we don't have `ScudoChunk` pointers anymore, a few variables were renamed here and there to introduce a clearer distinction between a user pointer (usually `Ptr`) and a backend pointer (`BackendPtr`). Reviewers: alekseyshl, flowerhack Reviewed By: alekseyshl Subscribers: #sanitizers, llvm-commits Differential Revision: https://reviews.llvm.org/D41200 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320745 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-13[scudo] Adding a public Scudo interfaceKostya Kortchinsky
Summary: The first and only function to start with allows to set the soft or hard RSS limit at runtime. Add associated tests. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: mgorny, #sanitizers, llvm-commits Differential Revision: https://reviews.llvm.org/D41128 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320611 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-13[sanitizer] Introduce a vDSO aware timing functionKostya Kortchinsky
Summary: See D40657 & D40679 for previous versions of this patch & description. A couple of things were fixed here to have it not break some bots. Weak symbols can't be used with `SANITIZER_GO` so the previous version was breakin TsanGo. I set up some additional local tests and those pass now. I changed the workaround for the glibc vDSO issue: `__progname` is initialized after the vDSO and is actually public and of known type, unlike `__vdso_clock_gettime`. This works better, and with all compilers. The rest is the same. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: srhines, kubamracek, krytarowski, llvm-commits, #sanitizers Differential Revision: https://reviews.llvm.org/D41121 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320594 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-13[scudo] Inline getScudoChunk function.Kostya Kortchinsky
Summary: getScudoChunk function is implicitly inlined for optimized builds on clang, but not on gcc. It's a small enough function that it seems sensible enough to just inline it by default. Reviewers: cryptoad, alekseyshl Reviewed By: cryptoad Differential Revision: https://reviews.llvm.org/D41138 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320592 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-11[sanitizer] Revert rL320409Kostya Kortchinsky
Summary: D40679 broke a couple of builds, reverting while investigating. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: srhines, kubamracek, krytarowski, llvm-commits, #sanitizers Differential Revision: https://reviews.llvm.org/D41088 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320417 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-11[sanitizer] Introduce a vDSO aware time function, and use it in the ↵Kostya Kortchinsky
allocator [redo] Summary: Redo of D40657, which had the initial discussion. The initial code had to move into a libcdep file, and things had to be shuffled accordingly. `NanoTime` is a time sink when checking whether or not to release memory to the OS. While reducing the amount of calls to said function is in the works, another solution that was found to be beneficial was to use a timing function that can leverage the vDSO. We hit a couple of snags along the way, like the fact that the glibc crashes when clock_gettime is called from a preinit_array, or the fact that `__vdso_clock_gettime` is mangled (for security purposes) and can't be used directly, and also that clock_gettime can be intercepted. The proposed solution takes care of all this as far as I can tell, and significantly improve performances and some Scudo load tests with memory reclaiming enabled. @mcgrathr: please feel free to follow up on https://reviews.llvm.org/D40657#940857 here. I posted a reply at https://reviews.llvm.org/D40657#940974. Reviewers: alekseyshl, krytarowski, flowerhack, mcgrathr, kubamracek Reviewed By: alekseyshl, krytarowski Subscribers: #sanitizers, mcgrathr, srhines, llvm-commits, kubamracek Differential Revision: https://reviews.llvm.org/D40679 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320409 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-08[scudo] Minor code generation improvementKostya Kortchinsky
Summary: It looks like clang was generating somewhat weird assembly with the current code. `FromPrimary`, even though `const`, was replaced every time with the code generated for `size <= SizeClassMap::kMaxSize` instead of using a variable or register, and `FromPrimary` didn't induce `ClassId != 0` for the compiler, so a dead branch was generated for `getActuallyAllocatedSize(Ptr, ClassId)` since it's never called for `ClassId = 0` (Secondary backed allocations) [this one was more wishful thinking on my side than anything else]. I rearranged the code bit so that the generated assembly is less clunky. Also changed 2 whitespace inconsistencies that were bothering me. Reviewers: alekseyshl, flowerhack Reviewed By: flowerhack Subscribers: llvm-commits, #sanitizers Differential Revision: https://reviews.llvm.org/D40976 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@320160 91177308-0d34-0410-b5e6-96231b3b80d8
2017-12-05[scudo] Get rid of the thread local PRNG & header saltKostya Kortchinsky
Summary: It was deemed that the salt in the chunk header didn't improve security significantly (and could actually decrease it). The initial idea was that the same chunk would different headers on different allocations, allowing for less predictability. The issue is that gathering the same chunk header with different salts can give information about the other "secrets" (cookie, pointer), and that if an attacker leaks a header, they can reuse it anyway for that same chunk anyway since we don't enforce the salt value. So we get rid of the salt in the header. This means we also get rid of the thread local Prng, and that we don't need a global Prng anymore as well. This makes everything faster. We reuse those 8 bits to store the `ClassId` of a chunk now (0 for a secondary based allocation). This way, we get some additional speed gains: - `ClassId` is computed outside of the locked block; - `getActuallyAllocatedSize` doesn't need the `GetSizeClass` call; - same for `deallocatePrimary`; We add a sanity check at init for this new field (all sanity checks are moved in their own function, `init` was getting crowded). Reviewers: alekseyshl, flowerhack Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40796 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@319791 91177308-0d34-0410-b5e6-96231b3b80d8
2017-11-22[scudo] Overhaul hardware CRC32 feature detectionKostya Kortchinsky
Summary: This patch aims at condensing the hardware CRC32 feature detection and making it slightly more effective on Android. The following changes are included: - remove the `CPUFeature` enum, and get rid of one level of nesting of functions: we only used CRC32, so we just implement and use `hasHardwareCRC32`; - allow for a weak `getauxval`: the Android toolchain is compiled at API level 14 for Android ARM, meaning no `getauxval` at compile time, yet we will run on API level 27+ devices. The `/proc/self/auxv` fallback can work but is worthless for a process like `init` where the proc filesystem doesn't exist yet. If a weak `getauxval` doesn't exist, then fallback. - couple of extra corrections. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: kubamracek, aemerson, srhines, kristof.beyls, llvm-commits Differential Revision: https://reviews.llvm.org/D40322 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@318859 91177308-0d34-0410-b5e6-96231b3b80d8
2017-11-15[scudo] Soft and hard RSS limit checksKostya Kortchinsky
Summary: This implements an opportunistic check for the RSS limit. For ASan, this was implemented thanks to a background thread checking the current RSS vs the set limit every 100ms. This was deemed problematic for Scudo due to potential Android concerns (Zygote as pointed out by Aleksey) as well as the general inconvenience of having a permanent background thread. If a limit (soft or hard) is specified, we will attempt to update the RSS limit status (exceeded or not) every 100ms. This is done in an opportunistic way: if we can update it, we do it, if not we return the current status, mostly because we don't need it to be fully consistent (it's done every 100ms anyway). If the limit is exceeded `allocate` will act as if OOM for a soft limit, or just die for a hard limit. We use the `common_flags()`'s `hard_rss_limit_mb` & `soft_rss_limit_mb` for configuration of the limits. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40038 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@318301 91177308-0d34-0410-b5e6-96231b3b80d8
2017-11-14[scudo] Simplify initialization and flagsKostya Kortchinsky
Summary: This is mostly some cleanup and shouldn't affect functionalities. Reviewing some code for a future addition, I realized that the complexity of the initialization path was unnecessary, and so was maintaining a structure for the allocator options throughout the initialization. So we get rid of that structure, of an extraneous level of nesting for the `init` function, and correct a couple of related code inaccuracies in the flags cpp. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D39974 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@318157 91177308-0d34-0410-b5e6-96231b3b80d8
2017-10-12[scudo] Allow for non-Android Shared TSD platforms, part 1Kostya Kortchinsky
Summary: This first part just prepares the grounds for part 2 and doesn't add any new functionality. It mostly consists of small refactors: - move the `pthread.h` include higher as it will be used in the headers; - use `errno.h` in `scudo_allocator.cpp` instead of the sanitizer one, update the `errno` assignments accordingly (otherwise it creates conflicts on some platforms due to `pthread.h` including `errno.h`); - introduce and use `getCurrentTSD` and `setCurrentTSD` for the shared TSD model code; Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits, srhines Differential Revision: https://reviews.llvm.org/D38826 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@315583 91177308-0d34-0410-b5e6-96231b3b80d8
2017-09-26[scudo] Scudo thread specific data refactor, part 3Kostya Kortchinsky
Summary: Previous parts: D38139, D38183. In this part of the refactor, we abstract the Linux vs Android TSD dissociation in favor of a Exclusive vs Shared one, allowing for easier platform introduction and configuration. Most of this change consist of shuffling the files around to reflect the new organization. We introduce `scudo_platform.h` where platform specific definition lie. This involves the TSD model and the platform specific allocator parameters. In an upcoming CL, those will be configurable via defines, but we currently stick with conservative defaults. Reviewers: alekseyshl, dvyukov Reviewed By: alekseyshl, dvyukov Subscribers: srhines, llvm-commits, mgorny Differential Revision: https://reviews.llvm.org/D38244 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@314224 91177308-0d34-0410-b5e6-96231b3b80d8
2017-09-25[scudo] Scudo thread specific data refactor, part 2Kostya Kortchinsky
Summary: Following D38139, we now consolidate the TSD definition, merging the shared TSD definition with the exclusive TSD definition. We introduce a boolean set at initializaton denoting the need for the TSD to be unlocked or not. This adds some unused members to the exclusive TSD, but increases consistency and reduces the definitions fragmentation. We remove the fallback mechanism from `scudo_allocator.cpp` and add a fallback TSD in the non-shared version. Since the shared version doesn't require one, this makes overall more sense. There are a couple of additional cosmetic changes: removing the header guards from the remaining `.inc` files, added error string to a `CHECK`. Question to reviewers: I thought about friending `getTSDAndLock` in `ScudoTSD` so that the `FallbackTSD` could `Mutex.Lock()` directly instead of `lock()` which involved zeroing out the `Precedence`, which is unused otherwise. Is it worth doing? Reviewers: alekseyshl, dvyukov, kcc Reviewed By: dvyukov Subscribers: srhines, llvm-commits Differential Revision: https://reviews.llvm.org/D38183 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@314110 91177308-0d34-0410-b5e6-96231b3b80d8
2017-09-22[scudo] Scudo thread specific data refactor, part 1Kostya Kortchinsky
Summary: We are going through an overhaul of Scudo's TSD, to allow for new platforms to be integrated more easily, and make the code more sound. This first part is mostly renaming, preferring some shorter names, correcting some comments. I removed `getPrng` and `getAllocatorCache` to directly access the members, there was not really any benefit to them (and it was suggested by Dmitry in D37590). The only functional change is in `scudo_tls_android.cpp`: we enforce bounds to the `NumberOfTSDs` and most of the logic in `getTSDAndLockSlow` is skipped if we only have 1 TSD. Reviewers: alekseyshl, dvyukov, kcc Reviewed By: dvyukov Subscribers: llvm-commits, srhines Differential Revision: https://reviews.llvm.org/D38139 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@313987 91177308-0d34-0410-b5e6-96231b3b80d8
2017-09-14[scudo] Fix bad request handling when allocator has not been initializedKostya Kortchinsky
Summary: In a few functions (`scudoMemalign` and the like), we would call `ScudoAllocator::FailureHandler::OnBadRequest` if the parameters didn't check out. The issue is that if the allocator had not been initialized (eg: if this is the first heap related function called), we would use variables like `allocator_may_return_null` and `exitcode` that still had their default value (as opposed to the one set by the user or the initialization path). To solve this, we introduce `handleBadRequest` that will call `initThreadMaybe`, allowing the options to be correctly initialized. Unfortunately, the tests were passing because `exitcode` was still 0, so the results looked like success. Change those tests to do what they were supposed to. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37853 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@313294 91177308-0d34-0410-b5e6-96231b3b80d8
2017-09-11[scudo] Fix improper TSD init after TLS destructors are calledKostya Kortchinsky
Summary: Some of glibc's own thread local data is destroyed after a user's thread local destructors are called, via __libc_thread_freeres. This might involve calling free, as is the case for strerror_thread_freeres. If there is no prior heap operation in the thread, this free would end up initializing some thread specific data that would never be destroyed properly (as user's pthread destructors have already been called), while still being deallocated when the TLS goes away. As a result, a program could SEGV, usually in __sanitizer::AllocatorGlobalStats::Unregister, where one of the doubly linked list links would refer to a now unmapped memory area. To prevent this from happening, we will not do a full initialization from the deallocation path. This means that the fallback cache & quarantine will be used if no other heap operation has been called, and we effectively prevent the TSD being initialized and never destroyed. The TSD will be fully initialized for all other paths. In the event of a thread doing only frees and nothing else, a TSD would never be initialized for that thread, but this situation is unlikely and we can live with that. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37697 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@312939 91177308-0d34-0410-b5e6-96231b3b80d8
2017-08-16[scudo] Application & platform compatibility changesKostya Kortchinsky
Summary: This patch changes a few (small) things around for compatibility purposes for the current Android & Fuchsia work: - `realloc`'ing some memory that was not allocated with `malloc`, `calloc` or `realloc`, while UB according to http://pubs.opengroup.org/onlinepubs/009695399/functions/realloc.html is more common that one would think. We now only check this if `DeallocationTypeMismatch` is set; change the "mismatch" error messages to be more homogeneous; - some sketchily written but widely used libraries expect a call to `realloc` to copy the usable size of the old chunk to the new one instead of the requested size. We have to begrundingly abide by this de-facto standard. This doesn't seem to impact security either way, unless someone comes up with something we didn't think about; - the CRC32 intrinsics for 64-bit take a 64-bit first argument. This is misleading as the upper 32 bits end up being ignored. This was also raising `-Wconversion` errors. Change things to take a `u32` as first argument. This also means we were (and are) only using 32 bits of the Cookie - not a big thing, but worth mentioning. - Includes-wise: prefer `stddef.h` to `cstddef`, move `scudo_flags.h` where it is actually needed. - Add tests for the memalign-realloc case, and the realloc-usable-size one. (Edited typos) Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D36754 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@311018 91177308-0d34-0410-b5e6-96231b3b80d8
2017-07-25[scudo] Check for pvalloc overflowKostya Kortchinsky
Summary: Previously we were rounding up the size passed to `pvalloc` to the next multiple of page size no matter what. There is an overflow possibility that wasn't accounted for. So now, return null in the event of an overflow. The man page doesn't seem to indicate the errno to set in this particular situation, but the glibc unit tests go for ENOMEM (https://code.woboq.org/userspace/glibc/malloc/tst-pvalloc.c.html#54) so we'll do the same. Update the aligned allocation funtions tests to check for properly aligned returned pointers, and the `pvalloc` corner cases. @alekseyshl: do you want me to do the same in the other Sanitizers? Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: kubamracek, alekseyshl, llvm-commits Differential Revision: https://reviews.llvm.org/D35818 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@309033 91177308-0d34-0410-b5e6-96231b3b80d8
2017-07-24[scudo] Quarantine overhaulKostya Kortchinsky
Summary: First, some context. The main feedback we get about the quarantine is that it's too memory hungry. A single MB of quarantine will have an impact of 3 to 4MB of PSS/RSS, and things quickly get out of hand in terms of memory usage, and the quarantine ends up disabled. The main objective of the quarantine is to protect from use-after-free exploitation by making it harder for an attacker to reallocate a controlled chunk in place of the targeted freed chunk. This is achieved by not making it available to the backend right away for reuse, but holding it a little while. Historically, what has usually been the target of such attacks was objects, where vtable pointers or other function pointers could constitute a valuable targeti to replace. Those are usually on the smaller side. There is barely any advantage in putting the quarantine several megabytes of RGB data or the like. Now for the patch. This patch introduces a new way the Quarantine behaves in Scudo. First of all, the size of the Quarantine will be defined in KB instead of MB, then we introduce a new option: the size up to which (lower than or equal to) a chunk will be quarantined. This way, we only quarantine smaller chunks, and the size of the quarantine remains manageable. It also prevents someone from triggering a recycle by allocating something huge. We default to 512 bytes on 32-bit and 2048 bytes on 64-bit platforms. In details, the patches includes the following: - introduce `QuarantineSizeKb`, but honor `QuarantineSizeMb` if set to fall back to the old behavior (meaning no threshold in that case); `QuarantineSizeMb` is described as deprecated in the options descriptios; documentation update will follow; - introduce `QuarantineChunksUpToSize`, the new threshold value; - update the `quarantine.cpp` test, and other tests using `QuarantineSizeMb`; - remove `AllocatorOptions::copyTo`, it wasn't used; - slightly change the logic around `quarantineOrDeallocateChunk` to accomodate for the new logic; rename a couple of variables there as well; Rewriting the tests, I found a somewhat annoying bug where non-default aligned chunks would account for more than needed when placed in the quarantine due to `<< MinAlignment` instead of `<< MinAlignmentLog`. This is fixed and tested for now. Reviewers: alekseyshl, kcc Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D35694 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@308884 91177308-0d34-0410-b5e6-96231b3b80d8
2017-07-18[Sanitizers] ASan/MSan/LSan allocators set errno on failure.Alex Shlyapnikov
Summary: ASan/MSan/LSan allocators set errno on allocation failures according to malloc/calloc/etc. expected behavior. MSan allocator was refactored a bit to make its structure more similar with other allocators. Also switch Scudo allocator to the internal errno definitions. TSan allocator changes will follow. Reviewers: eugenis Subscribers: llvm-commits, kubamracek Differential Revision: https://reviews.llvm.org/D35275 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@308344 91177308-0d34-0410-b5e6-96231b3b80d8
2017-07-14[Sanitizers] Scudo allocator set errno on failure.Alex Shlyapnikov
Summary: Set proper errno code on alloction failure and change pvalloc and posix_memalign implementation to satisfy their man-specified requirements. Reviewers: cryptoad Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D35429 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@308053 91177308-0d34-0410-b5e6-96231b3b80d8
2017-07-13[scudo] Do not grab a cache for secondary allocation & per related changesKostya Kortchinsky
Summary: Secondary backed allocations do not require a cache. While it's not necessary an issue when each thread has its cache, it becomes one with a shared pool of caches (Android), as a Secondary backed allocation or deallocation holds a cache that could be useful to another thread doing a Primary backed allocation. We introduce an additional PRNG and its mutex (to avoid contention with the Fallback one for Primary allocations) that will provide the `Salt` needed for Secondary backed allocations. I changed some of the code in a way that feels more readable to me (eg: using some values directly rather than going through ternary assigned variables, using directly `true`/`false` rather than `FromPrimary`). I will let reviewers decide if it actually is. An additional change is to mark `CheckForCallocOverflow` as `UNLIKELY`. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D35358 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@307958 91177308-0d34-0410-b5e6-96231b3b80d8
2017-07-12[scudo] PRNG makeoverKostya Kortchinsky
Summary: This follows the addition of `GetRandom` with D34412. We remove our `/dev/urandom` code and use the new function. Additionally, change the PRNG for a slightly faster version. One of the issues with the old code is that we have 64 full bits of randomness per "next", using only 8 of those for the Salt and discarding the rest. So we add a cached u64 in the PRNG that can serve up to 8 u8 before having to call the "next" function again. During some integration work, I also realized that some very early processes (like `init`) do not benefit from `/dev/urandom` yet. So if there is no `getrandom` syscall as well, we have to fallback to some sort of initialization of the PRNG. Now a few words on why XoRoShiRo and not something else. I have played a while with various PRNGs on 32 & 64 bit platforms. Some results are below. LCG 32 & 64 are usually faster but produce respectively 15 & 31 bits of entropy, meaning that to get a full 64-bit, you would need to call them several times. The simple XorShift is fast, produces 32 bits but is mediocre with regard to PRNG test suites, PCG is slower overall, and XoRoShiRo is faster than XorShift128+ and produces full 64 bits. %%% root@tulip-chiphd:/data # ./randtest.arm [+] starting xs32... [?] xs32 duration: 22431833053ns [+] starting lcg32... [?] lcg32 duration: 14941402090ns [+] starting pcg32... [?] pcg32 duration: 44941973771ns [+] starting xs128p... [?] xs128p duration: 48889786981ns [+] starting lcg64... [?] lcg64 duration: 33831042391ns [+] starting xos128p... [?] xos128p duration: 44850878605ns root@tulip-chiphd:/data # ./randtest.aarch64 [+] starting xs32... [?] xs32 duration: 22425151678ns [+] starting lcg32... [?] lcg32 duration: 14954255257ns [+] starting pcg32... [?] pcg32 duration: 37346265726ns [+] starting xs128p... [?] xs128p duration: 22523807219ns [+] starting lcg64... [?] lcg64 duration: 26141304679ns [+] starting xos128p... [?] xos128p duration: 14937033215ns %%% Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: aemerson, kristof.beyls, llvm-commits Differential Revision: https://reviews.llvm.org/D35221 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@307798 91177308-0d34-0410-b5e6-96231b3b80d8
2017-06-29MergeAlex Shlyapnikov
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@306748 91177308-0d34-0410-b5e6-96231b3b80d8
2017-06-29[scudo] Change aligned alloc functions to be more compliant & perf changesKostya Kortchinsky
Summary: We were not following the `man` documented behaviors for invalid arguments to `memalign` and associated functions. Using `CHECK` for those was a bit extreme, so we relax the behavior to return null pointers as expected when this happens. Adapt the associated test. I am using this change also to change a few more minor performance improvements: - mark as `UNLIKELY` a bunch of unlikely conditions; - the current `CHECK` in `__sanitizer::RoundUpTo` is redundant for us in *all* calls. So I am introducing our own version without said `CHECK`. - change our combined allocator `GetActuallyAllocatedSize`. We already know if the pointer is from the Primary or Secondary, so the `PointerIsMine` check is redundant as well, and costly for the 32-bit Primary. So we get the size by directly using the available Primary functions. Finally, change a `int` to `uptr` to avoid a warning/error when compiling on Android. Reviewers: alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34782 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@306698 91177308-0d34-0410-b5e6-96231b3b80d8
2017-06-20[Sanitizers] Move cached allocator_may_return_null flag to sanitizer_allocatorAlex Shlyapnikov
Summary: Move cached allocator_may_return_null flag to sanitizer_allocator.cc and provide API to consolidate and unify the behavior of all specific allocators. Make all sanitizers using CombinedAllocator to follow AllocatorReturnNullOrDieOnOOM() rules to behave the same way when OOM happens. When OOM happens, turn allocator_out_of_memory flag on regardless of allocator_may_return_null flag value (it used to not to be set when allocator_may_return_null == true). release_to_os_interval_ms and rss_limit_exceeded will likely be moved to sanitizer_allocator.cc too (later). Reviewers: eugenis Subscribers: srhines, kubamracek, llvm-commits Differential Revision: https://reviews.llvm.org/D34310 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@305858 91177308-0d34-0410-b5e6-96231b3b80d8
2017-05-11[scudo] Use our own combined allocatorKostya Kortchinsky
Summary: The reasoning behind this change is twofold: - the current combined allocator (sanitizer_allocator_combined.h) implements features that are not relevant for Scudo, making some code redundant, and some restrictions not pertinent (alignments for example). This forced us to do some weird things between the frontend and our secondary to make things work; - we have enough information to be able to know if a chunk will be serviced by the Primary or Secondary, allowing us to avoid extraneous calls to functions such as `PointerIsMine` or `CanAllocate`. As a result, the new scudo-specific combined allocator is very straightforward, and allows us to remove some now unnecessary code both in the frontend and the secondary. Unused functions have been left in as unimplemented for now. It turns out to also be a sizeable performance gain (3% faster in some Android memory_replay benchmarks, doing some more on other platforms). Reviewers: alekseyshl, kcc, dvyukov Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33007 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@302830 91177308-0d34-0410-b5e6-96231b3b80d8
2017-05-09[scudo] CRC32 optimizationsKostya Kortchinsky
Summary: This change optimizes several aspects of the checksum used for chunk headers. First, there is no point in checking the weak symbol `computeHardwareCRC32` everytime, it will either be there or not when we start, so check it once during initialization and set the checksum type accordingly. Then, the loading of `HashAlgorithm` for SSE versions (and ARM equivalent) was not optimized out, while not necessary. So I reshuffled that part of the code, which duplicates a tiny bit of code, but ends up in a much cleaner assembly (and faster as we avoid an extraneous load and some calls). The following code is the checksum at the end of `scudoMalloc` for x86_64 with full SSE 4.2, before: ``` mov rax, 0FFFFFFFFFFFFFFh shl r10, 38h mov edi, dword ptr cs:_ZN7__scudoL6CookieE ; __scudo::Cookie and r14, rax lea rsi, [r13-10h] movzx eax, cs:_ZN7__scudoL13HashAlgorithmE ; __scudo::HashAlgorithm or r14, r10 mov rbx, r14 xor bx, bx call _ZN7__scudo20computeHardwareCRC32Ejm ; __scudo::computeHardwareCRC32(uint,ulong) mov rsi, rbx mov edi, eax call _ZN7__scudo20computeHardwareCRC32Ejm ; __scudo::computeHardwareCRC32(uint,ulong) mov r14w, ax mov rax, r13 mov [r13-10h], r14 ``` After: ``` mov rax, cs:_ZN7__scudoL6CookieE ; __scudo::Cookie lea rcx, [rbx-10h] mov rdx, 0FFFFFFFFFFFFFFh and r14, rdx shl r9, 38h or r14, r9 crc32 eax, rcx mov rdx, r14 xor dx, dx mov eax, eax crc32 eax, rdx mov r14w, ax mov rax, rbx mov [rbx-10h], r14 ``` Reviewers: dvyukov, alekseyshl, kcc Reviewed By: alekseyshl Subscribers: aemerson, rengolin, llvm-commits Differential Revision: https://reviews.llvm.org/D32971 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@302538 91177308-0d34-0410-b5e6-96231b3b80d8
2017-05-05[scudo] Add Android supportKostya Kortchinsky
Summary: This change adds Android support to the allocator (but doesn't yet enable it in the cmake config), and should be the last fragment of the rewritten change D31947. Android has more memory constraints than other platforms, so the idea of a unique context per thread would not have worked. The alternative chosen is to allocate a set of contexts based on the number of cores on the machine, and share those contexts within the threads. Contexts can be dynamically reassigned to threads to prevent contention, based on a scheme suggested by @dvyuokv in the initial review. Additionally, given that Android doesn't support ELF TLS (only emutls for now), we use the TSan TLS slot to make things faster: Scudo is mutually exclusive with other sanitizers so this shouldn't cause any problem. An additional change made here, is replacing `thread_local` by `THREADLOCAL` and using the initial-exec thread model in the non-Android version to prevent extraneous weak definition and checks on the relevant variables. Reviewers: kcc, dvyukov, alekseyshl Reviewed By: alekseyshl Subscribers: srhines, mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D32649 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@302300 91177308-0d34-0410-b5e6-96231b3b80d8
2017-04-27[scudo] Move thread local variables into their own filesKostya Kortchinsky
Summary: This change introduces scudo_tls.h & scudo_tls_linux.cpp, where we move the thread local variables used by the allocator, namely the cache, quarantine cache & prng. `ScudoThreadContext` will hold those. This patch doesn't introduce any new platform support yet, this will be the object of a later patch. This also changes the PRNG so that the structure can be POD. Reviewers: kcc, dvyukov, alekseyshl Reviewed By: dvyukov, alekseyshl Subscribers: llvm-commits, mgorny Differential Revision: https://reviews.llvm.org/D32440 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@301584 91177308-0d34-0410-b5e6-96231b3b80d8
2017-04-21[scudo] Bypass Quarantine if its size is set to 0Kostya Kortchinsky
Summary: In the current state of things, the deallocation path puts a chunk in the Quarantine whether it's enabled or not (size of 0). When the Quarantine is disabled, this results in the header being loaded (and checked) twice, and stored (and checksummed) once, in `deallocate` and `Recycle`. This change introduces a `quarantineOrDeallocateChunk` function that has a fast path to deallocation if the Quarantine is disabled. Even though this is not the preferred configuration security-wise, this change saves a sizeable amount of processing for that particular situation (which could be adopted by low memory devices). Additionally this simplifies a bit `deallocate` and `reallocate`. Reviewers: dvyukov, kcc, alekseyshl Reviewed By: dvyukov Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32310 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@301015 91177308-0d34-0410-b5e6-96231b3b80d8
2017-04-20[scudo] Remove GetActuallyAllocatedSize calls from the fast pathKostya Kortchinsky
Summary: GetActuallyAllocatedSize is actually expensive. In order to avoid calling this function in the malloc/free fast path, we change the Scudo chunk header to store the size of the chunk, if from the Primary, or the amount of unused bytes if from the Secondary. This way, we only have to call the culprit function for Secondary backed allocations (and still in realloc). The performance gain on a singly threaded pure malloc/free benchmark exercising the Primary allocator is above 5%. Reviewers: alekseyshl, kcc, dvyukov Reviewed By: dvyukov Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32299 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@300861 91177308-0d34-0410-b5e6-96231b3b80d8
2017-04-20[scudo] Minor changes and refactoringKostya Kortchinsky
Summary: This is part of D31947 that is being split into several smaller changes. This one deals with all the minor changes, more specifically: - Rename some variables and functions to make their purpose clearer; - Reorder some code; - Mark the hot termination incurring checks as `UNLIKELY`; if they happen, the program will die anyway; - Add a `getScudoChunk` method; - Add an `eraseHeader` method to ScudoChunk that will clear a header with 0s; - Add a parameter to `allocate` to know if the allocated chunk should be filled with zeros. This allows `calloc` to not have to call `GetActuallyAllocatedSize`; more changes to get rid of this function on the hot paths will follow; - reallocate was missing a check to verify that the pointer is properly aligned on `MinAlignment`; - The `Stats` in the secondary have to be protected by a mutex as the `Add` and `Sub` methods are actually not atomic; - The software CRC32 function was moved to the header to allow for inlining. Reviewers: dvyukov, alekseyshl, kcc Reviewed By: dvyukov Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32242 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@300846 91177308-0d34-0410-b5e6-96231b3b80d8
2017-02-03[scudo] 32-bit quarantine sizes adjustments and bug fixesKostya Kortchinsky
Summary: The local and global quarantine sizes were not offering a distinction for 32-bit and 64-bit platforms. This is addressed with lower values for 32-bit. When writing additional tests for the quarantine, it was discovered that when calling some of the allocator interface function prior to any allocation operation having occured, the test would crash due to the allocator not being initialized. This was addressed by making sure the allocator is initialized for those scenarios. Relevant tests were added in interface.cpp and quarantine.cpp. Last change being the removal of the extraneous link dependencies for the tests thanks to rL293220, anf the addition of the gc-sections linker flag. Reviewers: kcc, alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29341 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@294037 91177308-0d34-0410-b5e6-96231b3b80d8
2017-01-20[scudo] Replacing std::atomic with Sanitizer's atomicsKostya Kortchinsky
Summary: In an effort to getting rid of dependencies to external libraries, we are replacing atomic PackedHeader use of std::atomic with Sanitizer's atomic_uint64_t, which allows us to avoid -latomic. Reviewers: kcc, phosek, alekseyshl Reviewed By: alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28864 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@292630 91177308-0d34-0410-b5e6-96231b3b80d8
2017-01-18[scudo] Refactor of CRC32 and ARM runtime CRC32 detectionKostya Kortchinsky
Summary: ARM & AArch64 runtime detection for hardware support of CRC32 has been added via check of the AT_HWVAL auxiliary vector. Following Michal's suggestions in D28417, the CRC32 code has been further changed and looks better now. When compiled with full relro (which is strongly suggested to benefit from additional hardening), the weak symbol for computeHardwareCRC32 is read-only and the assembly generated is fairly clean and straight forward. As suggested, an additional optimization is to skip the runtime check if SSE 4.2 has been enabled globally, as opposed to only for scudo_crc32.cpp. scudo_crc32.h has no purpose anymore and was removed. Reviewers: alekseyshl, kcc, rengolin, mgorny, phosek Reviewed By: rengolin, mgorny Subscribers: aemerson, rengolin, llvm-commits Differential Revision: https://reviews.llvm.org/D28574 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@292409 91177308-0d34-0410-b5e6-96231b3b80d8
2017-01-10[scudo] Separate hardware CRC32 routinesKostya Kortchinsky
Summary: As raised in D28304, enabling SSE 4.2 for the whole Scudo tree leads to the emission of SSE 4.2 instructions everywhere, while the runtime checks only applied to the CRC32 computing function. This patch separates the CRC32 function taking advantage of the hardware into its own file, and only enabled -msse4.2 for that file, if detected to be supported by the compiler. Another consequence of removing SSE4.2 globally is realizing that memcpy were not being optimized, which turned out to be due to the -fno-builtin in SANITIZER_COMMON_CFLAGS. So we now explicitely enable builtins for Scudo. The resulting assembly looks good, with some CALLs are introduced instead of the CRC32 code being inlined. Reviewers: kcc, mgorny, alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28417 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@291570 91177308-0d34-0410-b5e6-96231b3b80d8
2016-12-15[scudo] Use DefaultSizeClassMap for 32-bitKostya Kortchinsky
Summary: With the recent changes to the Secondary, we use less bits for UnusedBytes, which allows us in return to increase the bits used for Offset. That means that we can use a Primary SizeClassMap allowing for a larger maximum size. Reviewers: kcc, alekseyshl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D27816 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@289838 91177308-0d34-0410-b5e6-96231b3b80d8
2016-12-13Corrected D27428: Do not use the alignment-rounded-up size with secondaryKostya Kortchinsky
Summary: I atually had an integer overflow on 32-bit with D27428 that didn't reproduce locally, as the test servers would manage allocate addresses in the 0xffffxxxx range, which led to some issues when rounding addresses. At this point, I feel that Scudo could benefit from having its own combined allocator, as we don't get any benefit from the current one, but have to work around some hurdles (alignment checks, rounding up that is no longer needed, extraneous code). Reviewers: kcc, alekseyshl Subscribers: llvm-commits, kubabrecka Differential Revision: https://reviews.llvm.org/D27681 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@289572 91177308-0d34-0410-b5e6-96231b3b80d8
2016-12-02Don't include system header inside namespaceStephan Bergmann
...causes build failure at least with GCC 6.2.1, as smmintrin.h indirectly includes cstdlib, which then runs into problems. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@288486 91177308-0d34-0410-b5e6-96231b3b80d8
2016-11-30[scudo] 32-bit and hardware agnostic supportKostya Kortchinsky
Summary: This update introduces i386 support for the Scudo Hardened Allocator, and offers software alternatives for functions that used to require hardware specific instruction sets. This should make porting to new architectures easier. Among the changes: - The chunk header has been changed to accomodate the size limitations encountered on 32-bit architectures. We now fit everything in 64-bit. This was achieved by storing the amount of unused bytes in an allocation rather than the size itself, as one can be deduced from the other with the help of the GetActuallyAllocatedSize function. As it turns out, this header can be used for both 64 and 32 bit, and as such we dropped the requirement for the 128-bit compare and exchange instruction support (cmpxchg16b). - Add 32-bit support for the checksum and the PRNG functions: if the SSE 4.2 instruction set is supported, use the 32-bit CRC32 instruction, and in the XorShift128, use a 32-bit based state instead of 64-bit. - Add software support for CRC32: if SSE 4.2 is not supported, fallback on a software implementation. - Modify tests that were not 32-bit compliant, and expand them to cover more allocation and alignment sizes. The random shuffle test has been deactivated for linux-i386 & linux-i686 as the 32-bit sanitizer allocator doesn't currently randomize chunks. Reviewers: alekseyshl, kcc Subscribers: filcab, llvm-commits, tberghammer, danalbert, srhines, mgorny, modocache Differential Revision: https://reviews.llvm.org/D26358 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@288255 91177308-0d34-0410-b5e6-96231b3b80d8
2016-11-29Return memory to OS right after free (not in the async thread).Evgeniy Stepanov
Summary: In order to avoid starting a separate thread to return unused memory to the system (the thread interferes with process startup on Android, Zygota waits for all threads to exit before fork, but this thread never exits), try to return it right after free. Reviewers: eugenis Subscribers: cryptoad, filcab, danalbert, kubabrecka, llvm-commits Patch by Aleksey Shlyapnikov. Differential Revision: https://reviews.llvm.org/D27003 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@288091 91177308-0d34-0410-b5e6-96231b3b80d8
2016-10-26[scudo] Lay the foundation for 32-bit supportKostya Kortchinsky
Summary: In order to support 32-bit platforms, we have to make some adjustments in multiple locations, one of them being the Scudo chunk header. For it to fit on 64 bits (as a reminder, on x64 it's 128 bits), I had to crunch the space taken by some of the fields. In order to keep the offset field small, the secondary allocator was changed to accomodate aligned allocations for larger alignments, hence making the offset constant for chunks serviced by it. The resulting header candidate has been added, and further modifications to allow 32-bit support will follow. Another notable change is the addition of MaybeStartBackgroudThread() to allow release of the memory to the OS. Reviewers: kcc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25688 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@285209 91177308-0d34-0410-b5e6-96231b3b80d8
2016-09-30[scudo] Fix an edge case in the secondary allocatorKostya Kortchinsky
Summary: s/CHECK_LT/CHECK_LE/ in the secondary allocator, as under certain circumstances Ptr + Size can be equal to MapEnd. This edge case was not found by the current tests, so those were extended to be able to catch that. Reviewers: kcc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25101 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@282913 91177308-0d34-0410-b5e6-96231b3b80d8
2016-09-29Don't use internal symbolizer if we are in process of reporting Out-of-Memory.Vitaly Buka
Reviewed by eugenis offline, as reviews.llvm.org is down. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@282805 91177308-0d34-0410-b5e6-96231b3b80d8
2016-09-19[scudo] Modify Scudo to use its own Secondary AllocatorKostya Kortchinsky
Summary: The Sanitizer Secondary Allocator was not entirely ideal was Scudo for several reasons: decent amount of unneeded code, redundant checks already performed by the front end, unneeded data structures, difficulty to properly protect the secondary chunks header. Given that the second allocator is pretty straight forward, Scudo will use its own, trimming all the unneeded code off of the Sanitizer one. A significant difference in terms of security is that now each secondary chunk is preceded and followed by a guard page, thus mitigating overflows into and from the chunk. A test was added as well to illustrate the overflow & underflow situations into the guard pages. Reviewers: kcc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24737 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@281938 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-26[sanitizer] enable random shuffling the memory chunks inside the allocator, ↵Kostya Serebryany
under a flag. Set this flag for the scudo allocator, add a test. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@279793 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-25[sanitizer] change SizeClassAllocator64 to accept just one template ↵Kostya Serebryany
parameter instead of 5. First, this will make the mangled names shorter. Second, this will make adding more parameters simpler. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@279771 91177308-0d34-0410-b5e6-96231b3b80d8
2016-08-02[sanitizer] Implement a __asan_default_options() equivalent for ScudoKostya Serebryany
Summary: Currently, the Scudo Hardened Allocator only gets its flags via the SCUDO_OPTIONS environment variable. With this patch, we offer the opportunity for programs to define their own options via __scudo_default_options() which behaves like __asan_default_options() (weak symbol). A relevant test has been added as well, and the documentation updated accordingly. I also used this patch as an opportunity to rename a few variables to comply with the LLVM naming scheme, and replaced a use of Report with dieWithMessage for consistency (and to avoid a callback). Reviewers: llvm-commits, kcc Differential Revision: https://reviews.llvm.org/D23018 git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@277536 91177308-0d34-0410-b5e6-96231b3b80d8