diff options
author | Jordan Rupprecht <rupprecht@google.com> | 2019-05-14 21:58:59 +0000 |
---|---|---|
committer | Jordan Rupprecht <rupprecht@google.com> | 2019-05-14 21:58:59 +0000 |
commit | b6bc976d7be8ee56d3be4b6dbd2f3ab0a4021c86 (patch) | |
tree | f5ed5db8cb5d237a073ea00c4d4cd63153a16a6c /lib/scudo | |
parent | 05342ccc9cff16425c0a831fddd510879544a0bf (diff) | |
parent | 098ca93185735ec3687106d0967a70fc99a85059 (diff) | |
download | compiler-rt-google/stable.tar.gz |
Creating branches/google/stable and tags/google/stable/2019-05-14 from r360103google/stable
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/branches/google/stable@360714 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/scudo')
72 files changed, 4935 insertions, 109 deletions
diff --git a/lib/scudo/CMakeLists.txt b/lib/scudo/CMakeLists.txt index 79f69e934..bbb8a1a9c 100644 --- a/lib/scudo/CMakeLists.txt +++ b/lib/scudo/CMakeLists.txt @@ -37,7 +37,7 @@ if (FUCHSIA) list(APPEND SCUDO_CFLAGS -nostdinc++) list(APPEND SCUDO_DYNAMIC_LINK_FLAGS -nostdlib++) else() - list(APPEND SCUDO_DYNAMIC_LIBS ${SANITIZER_CXX_ABI_LIBRARY}) + list(APPEND SCUDO_DYNAMIC_LIBS ${SANITIZER_CXX_ABI_LIBRARIES}) list(APPEND SCUDO_OBJECT_LIBS RTSanitizerCommonCoverage RTSanitizerCommonSymbolizer diff --git a/lib/scudo/scudo_allocator.cpp b/lib/scudo/scudo_allocator.cpp index fb04fb281..172975eb9 100644 --- a/lib/scudo/scudo_allocator.cpp +++ b/lib/scudo/scudo_allocator.cpp @@ -1,9 +1,8 @@ //===-- scudo_allocator.cpp -------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// @@ -588,11 +587,11 @@ NOINLINE void Allocator::performSanityChecks() { } // Opportunistic RSS limit check. This will update the RSS limit status, if -// it can, every 100ms, otherwise it will just return the current one. +// it can, every 250ms, otherwise it will just return the current one. NOINLINE bool Allocator::isRssLimitExceeded() { u64 LastCheck = atomic_load_relaxed(&RssLastCheckedAtNS); const u64 CurrentCheck = MonotonicNanoTime(); - if (LIKELY(CurrentCheck < LastCheck + (100ULL * 1000000ULL))) + if (LIKELY(CurrentCheck < LastCheck + (250ULL * 1000000ULL))) return atomic_load_relaxed(&RssLimitExceeded); if (!atomic_compare_exchange_weak(&RssLastCheckedAtNS, &LastCheck, CurrentCheck, memory_order_relaxed)) diff --git a/lib/scudo/scudo_allocator.h b/lib/scudo/scudo_allocator.h index 814bb08ab..0efa5c520 100644 --- a/lib/scudo/scudo_allocator.h +++ b/lib/scudo/scudo_allocator.h @@ -1,9 +1,8 @@ //===-- scudo_allocator.h ---------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// @@ -85,12 +84,6 @@ struct AP64 { }; typedef SizeClassAllocator64<AP64> PrimaryT; #else -static const uptr NumRegions = SANITIZER_MMAP_RANGE_SIZE >> RegionSizeLog; -# if SANITIZER_WORDSIZE == 32 -typedef FlatByteMap<NumRegions> ByteMap; -# elif SANITIZER_WORDSIZE == 64 -typedef TwoLevelByteMap<(NumRegions >> 12), 1 << 12> ByteMap; -# endif // SANITIZER_WORDSIZE struct AP32 { static const uptr kSpaceBeg = 0; static const u64 kSpaceSize = SANITIZER_MMAP_RANGE_SIZE; @@ -98,7 +91,6 @@ struct AP32 { typedef __scudo::SizeClassMap SizeClassMap; static const uptr kRegionSizeLog = RegionSizeLog; using AddressSpaceView = LocalAddressSpaceView; - using ByteMap = __scudo::ByteMap; typedef NoOpMapUnmapCallback MapUnmapCallback; static const uptr kFlags = SizeClassAllocator32FlagMasks::kRandomShuffleChunks | @@ -108,11 +100,13 @@ typedef SizeClassAllocator32<AP32> PrimaryT; #endif // SANITIZER_CAN_USE_ALLOCATOR64 #include "scudo_allocator_secondary.h" -#include "scudo_allocator_combined.h" -typedef SizeClassAllocatorLocalCache<PrimaryT> AllocatorCacheT; typedef LargeMmapAllocator SecondaryT; -typedef CombinedAllocator<PrimaryT, AllocatorCacheT, SecondaryT> BackendT; + +#include "scudo_allocator_combined.h" + +typedef CombinedAllocator BackendT; +typedef CombinedAllocator::AllocatorCache AllocatorCacheT; void initScudo(); diff --git a/lib/scudo/scudo_allocator_combined.h b/lib/scudo/scudo_allocator_combined.h index 6e40660ba..d61cc9ec1 100644 --- a/lib/scudo/scudo_allocator_combined.h +++ b/lib/scudo/scudo_allocator_combined.h @@ -1,9 +1,8 @@ //===-- scudo_allocator_combined.h ------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// @@ -19,10 +18,11 @@ # error "This file must be included inside scudo_allocator.h." #endif -template <class PrimaryAllocator, class AllocatorCache, - class SecondaryAllocator> class CombinedAllocator { public: + using PrimaryAllocator = PrimaryT; + using SecondaryAllocator = SecondaryT; + using AllocatorCache = typename PrimaryAllocator::AllocatorCache; void init(s32 ReleaseToOSIntervalMs) { Primary.Init(ReleaseToOSIntervalMs); Secondary.Init(); diff --git a/lib/scudo/scudo_allocator_secondary.h b/lib/scudo/scudo_allocator_secondary.h index ff6246e25..151ff9931 100644 --- a/lib/scudo/scudo_allocator_secondary.h +++ b/lib/scudo/scudo_allocator_secondary.h @@ -1,9 +1,8 @@ //===-- scudo_allocator_secondary.h -----------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_crc32.cpp b/lib/scudo/scudo_crc32.cpp index a267dc4e3..87473505f 100644 --- a/lib/scudo/scudo_crc32.cpp +++ b/lib/scudo/scudo_crc32.cpp @@ -1,9 +1,8 @@ //===-- scudo_crc32.cpp -----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_crc32.h b/lib/scudo/scudo_crc32.h index e89e430f4..bad15a929 100644 --- a/lib/scudo/scudo_crc32.h +++ b/lib/scudo/scudo_crc32.h @@ -1,9 +1,8 @@ //===-- scudo_crc32.h -------------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_errors.cpp b/lib/scudo/scudo_errors.cpp index d11e03cf9..34e57bf71 100644 --- a/lib/scudo/scudo_errors.cpp +++ b/lib/scudo/scudo_errors.cpp @@ -1,9 +1,8 @@ //===-- scudo_errors.cpp ----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_errors.h b/lib/scudo/scudo_errors.h index 8b1af996b..258695c2c 100644 --- a/lib/scudo/scudo_errors.h +++ b/lib/scudo/scudo_errors.h @@ -1,9 +1,8 @@ //===-- scudo_errors.h ------------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_flags.cpp b/lib/scudo/scudo_flags.cpp index c012471a8..af8ae5b4c 100644 --- a/lib/scudo/scudo_flags.cpp +++ b/lib/scudo/scudo_flags.cpp @@ -1,9 +1,8 @@ //===-- scudo_flags.cpp -----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_flags.h b/lib/scudo/scudo_flags.h index d4ae31031..483c79621 100644 --- a/lib/scudo/scudo_flags.h +++ b/lib/scudo/scudo_flags.h @@ -1,9 +1,8 @@ //===-- scudo_flags.h -------------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_flags.inc b/lib/scudo/scudo_flags.inc index f180478fd..c124738c1 100644 --- a/lib/scudo/scudo_flags.inc +++ b/lib/scudo/scudo_flags.inc @@ -1,9 +1,8 @@ //===-- scudo_flags.inc -----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// @@ -37,7 +36,9 @@ SCUDO_FLAG(int, QuarantineChunksUpToSize, -1, "Size in bytes up to which chunks will be quarantined (if lower than" "or equal to). Defaults to 256 (32-bit) or 2048 (64-bit)") -SCUDO_FLAG(bool, DeallocationTypeMismatch, true, +// Disable the deallocation type check by default on Android, it causes too many +// issues with third party libraries. +SCUDO_FLAG(bool, DeallocationTypeMismatch, !SANITIZER_ANDROID, "Report errors on malloc/delete, new/free, new/delete[], etc.") SCUDO_FLAG(bool, DeleteSizeMismatch, true, diff --git a/lib/scudo/scudo_interface_internal.h b/lib/scudo/scudo_interface_internal.h index 3e520a50c..75c63aa6d 100644 --- a/lib/scudo/scudo_interface_internal.h +++ b/lib/scudo/scudo_interface_internal.h @@ -1,9 +1,8 @@ //===-- scudo_interface_internal.h ------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_malloc.cpp b/lib/scudo/scudo_malloc.cpp index eef776809..a72b861e2 100644 --- a/lib/scudo/scudo_malloc.cpp +++ b/lib/scudo/scudo_malloc.cpp @@ -1,9 +1,8 @@ //===-- scudo_malloc.cpp ----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_new_delete.cpp b/lib/scudo/scudo_new_delete.cpp index daa3b47dc..03eef7f28 100644 --- a/lib/scudo/scudo_new_delete.cpp +++ b/lib/scudo/scudo_new_delete.cpp @@ -1,9 +1,8 @@ //===-- scudo_new_delete.cpp ------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_platform.h b/lib/scudo/scudo_platform.h index 3a6f4be69..07d4b70fc 100644 --- a/lib/scudo/scudo_platform.h +++ b/lib/scudo/scudo_platform.h @@ -1,9 +1,8 @@ //===-- scudo_platform.h ----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// @@ -80,7 +79,7 @@ const uptr RegionSizeLog = SANITIZER_ANDROID ? 19 : 20; #endif // SANITIZER_CAN_USE_ALLOCATOR64 #if !defined(SCUDO_SIZE_CLASS_MAP) -# define SCUDO_SIZE_CLASS_MAP Default +# define SCUDO_SIZE_CLASS_MAP Dense #endif #define SIZE_CLASS_MAP_TYPE SIZE_CLASS_MAP_TYPE_(SCUDO_SIZE_CLASS_MAP) diff --git a/lib/scudo/scudo_termination.cpp b/lib/scudo/scudo_termination.cpp index 4237d3bc1..6c7c0abc6 100644 --- a/lib/scudo/scudo_termination.cpp +++ b/lib/scudo/scudo_termination.cpp @@ -1,9 +1,8 @@ //===-- scudo_termination.cpp -----------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_tsd.h b/lib/scudo/scudo_tsd.h index 2bd78716a..1d4e4e6f1 100644 --- a/lib/scudo/scudo_tsd.h +++ b/lib/scudo/scudo_tsd.h @@ -1,9 +1,8 @@ //===-- scudo_tsd.h ---------------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_tsd_exclusive.cpp b/lib/scudo/scudo_tsd_exclusive.cpp index 74e797580..a203a74bb 100644 --- a/lib/scudo/scudo_tsd_exclusive.cpp +++ b/lib/scudo/scudo_tsd_exclusive.cpp @@ -1,9 +1,8 @@ //===-- scudo_tsd_exclusive.cpp ---------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_tsd_exclusive.inc b/lib/scudo/scudo_tsd_exclusive.inc index 1fa9dcdfd..08e4d3af7 100644 --- a/lib/scudo/scudo_tsd_exclusive.inc +++ b/lib/scudo/scudo_tsd_exclusive.inc @@ -1,9 +1,8 @@ //===-- scudo_tsd_exclusive.inc ---------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_tsd_shared.cpp b/lib/scudo/scudo_tsd_shared.cpp index 8853894c0..9918a08be 100644 --- a/lib/scudo/scudo_tsd_shared.cpp +++ b/lib/scudo/scudo_tsd_shared.cpp @@ -1,9 +1,8 @@ //===-- scudo_tsd_shared.cpp ------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_tsd_shared.inc b/lib/scudo/scudo_tsd_shared.inc index 9dad756b5..8f3362dd3 100644 --- a/lib/scudo/scudo_tsd_shared.inc +++ b/lib/scudo/scudo_tsd_shared.inc @@ -1,9 +1,8 @@ //===-- scudo_tsd_shared.inc ------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_utils.cpp b/lib/scudo/scudo_utils.cpp index d5788d20c..5e76a4a30 100644 --- a/lib/scudo/scudo_utils.cpp +++ b/lib/scudo/scudo_utils.cpp @@ -1,9 +1,8 @@ //===-- scudo_utils.cpp -----------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/scudo_utils.h b/lib/scudo/scudo_utils.h index 43448e083..a8dfbdeb3 100644 --- a/lib/scudo/scudo_utils.h +++ b/lib/scudo/scudo_utils.h @@ -1,9 +1,8 @@ //===-- scudo_utils.h -------------------------------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// diff --git a/lib/scudo/standalone/CMakeLists.txt b/lib/scudo/standalone/CMakeLists.txt new file mode 100644 index 000000000..922f98692 --- /dev/null +++ b/lib/scudo/standalone/CMakeLists.txt @@ -0,0 +1,98 @@ +add_compiler_rt_component(scudo_standalone) + +include_directories(../..) + +set(SCUDO_CFLAGS) + +list(APPEND SCUDO_CFLAGS + -Wall + -nostdinc++) + +# Remove -stdlib= which is unused when passing -nostdinc++. +string(REGEX REPLACE "-stdlib=[a-zA-Z+]*" "" CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS}) + +append_list_if(COMPILER_RT_HAS_FFREESTANDING_FLAG -ffreestanding SCUDO_CFLAGS) + +append_list_if(COMPILER_RT_HAS_FVISIBILITY_HIDDEN_FLAG -fvisibility=hidden SCUDO_CFLAGS) + +if(COMPILER_RT_DEBUG) + list(APPEND SCUDO_CFLAGS -O0) +else() + list(APPEND SCUDO_CFLAGS -O3) +endif() + +set(SCUDO_LINK_FLAGS) + +list(APPEND SCUDO_LINK_FLAGS -Wl,-z,defs,-z,now,-z,relro) + +append_list_if(COMPILER_RT_HAS_NODEFAULTLIBS_FLAG -nodefaultlibs SCUDO_LINK_FLAGS) + +if(ANDROID) +# Put the shared library in the global group. For more details, see +# android-changes-for-ndk-developers.md#changes-to-library-search-order + append_list_if(COMPILER_RT_HAS_Z_GLOBAL -Wl,-z,global SCUDO_LINK_FLAGS) +endif() + +set(SCUDO_SOURCES + checksum.cc + crc32_hw.cc + common.cc + flags.cc + flags_parser.cc + fuchsia.cc + linux.cc + report.cc + secondary.cc + string_utils.cc) + +# Enable the SSE 4.2 instruction set for crc32_hw.cc, if available. +if (COMPILER_RT_HAS_MSSE4_2_FLAG) + set_source_files_properties(crc32_hw.cc PROPERTIES COMPILE_FLAGS -msse4.2) +endif() + +# Enable the AArch64 CRC32 feature for crc32_hw.cc, if available. +# Note that it is enabled by default starting with armv8.1-a. +if (COMPILER_RT_HAS_MCRC_FLAG) + set_source_files_properties(crc32_hw.cc PROPERTIES COMPILE_FLAGS -mcrc) +endif() + +set(SCUDO_HEADERS + atomic_helpers.h + bytemap.h + checksum.h + flags.h + flags_parser.h + fuchsia.h + interface.h + internal_defs.h + linux.h + list.h + mutex.h + platform.h + release.h + report.h + secondary.h + size_class_map.h + stats.h + string_utils.h + vector.h) + +if(COMPILER_RT_HAS_SCUDO_STANDALONE) + add_compiler_rt_object_libraries(RTScudoStandalone + ARCHS ${SCUDO_STANDALONE_SUPPORTED_ARCH} + SOURCES ${SCUDO_SOURCES} + ADDITIONAL_HEADERS ${SCUDO_HEADERS} + CFLAGS ${SCUDO_CFLAGS}) + + add_compiler_rt_runtime(clang_rt.scudo_standalone + STATIC + ARCHS ${SCUDO_STANDALONE_SUPPORTED_ARCH} + SOURCES ${SCUDO_SOURCES} + ADDITIONAL_HEADERS ${SCUDO_HEADERS} + CFLAGS ${SCUDO_CFLAGS} + PARENT_TARGET scudo_standalone) + + if(COMPILER_RT_INCLUDE_TESTS) + add_subdirectory(tests) + endif() +endif() diff --git a/lib/scudo/standalone/atomic_helpers.h b/lib/scudo/standalone/atomic_helpers.h new file mode 100644 index 000000000..35d7369c1 --- /dev/null +++ b/lib/scudo/standalone/atomic_helpers.h @@ -0,0 +1,131 @@ +//===-- atomic_helpers.h ----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_ATOMIC_H_ +#define SCUDO_ATOMIC_H_ + +#include "internal_defs.h" + +namespace scudo { + +enum memory_order { + memory_order_relaxed = 0, + memory_order_consume = 1, + memory_order_acquire = 2, + memory_order_release = 3, + memory_order_acq_rel = 4, + memory_order_seq_cst = 5 +}; +COMPILER_CHECK(memory_order_relaxed == __ATOMIC_RELAXED); +COMPILER_CHECK(memory_order_consume == __ATOMIC_CONSUME); +COMPILER_CHECK(memory_order_acquire == __ATOMIC_ACQUIRE); +COMPILER_CHECK(memory_order_release == __ATOMIC_RELEASE); +COMPILER_CHECK(memory_order_acq_rel == __ATOMIC_ACQ_REL); +COMPILER_CHECK(memory_order_seq_cst == __ATOMIC_SEQ_CST); + +struct atomic_u8 { + typedef u8 Type; + volatile Type ValDoNotUse; +}; + +struct atomic_u16 { + typedef u16 Type; + volatile Type ValDoNotUse; +}; + +struct atomic_s32 { + typedef s32 Type; + volatile Type ValDoNotUse; +}; + +struct atomic_u32 { + typedef u32 Type; + volatile Type ValDoNotUse; +}; + +struct atomic_u64 { + typedef u64 Type; + // On 32-bit platforms u64 is not necessarily aligned on 8 bytes. + ALIGNED(8) volatile Type ValDoNotUse; +}; + +struct atomic_uptr { + typedef uptr Type; + volatile Type ValDoNotUse; +}; + +template <typename T> +INLINE typename T::Type atomic_load(const volatile T *A, memory_order MO) { + DCHECK(!(reinterpret_cast<uptr>(A) % sizeof(*A))); + typename T::Type V; + __atomic_load(&A->ValDoNotUse, &V, MO); + return V; +} + +template <typename T> +INLINE void atomic_store(volatile T *A, typename T::Type V, memory_order MO) { + DCHECK(!(reinterpret_cast<uptr>(A) % sizeof(*A))); + __atomic_store(&A->ValDoNotUse, &V, MO); +} + +INLINE void atomic_thread_fence(memory_order) { __sync_synchronize(); } + +template <typename T> +INLINE typename T::Type atomic_fetch_add(volatile T *A, typename T::Type V, + memory_order MO) { + DCHECK(!(reinterpret_cast<uptr>(A) % sizeof(*A))); + return __atomic_fetch_add(&A->ValDoNotUse, V, MO); +} + +template <typename T> +INLINE typename T::Type atomic_fetch_sub(volatile T *A, typename T::Type V, + memory_order MO) { + DCHECK(!(reinterpret_cast<uptr>(A) % sizeof(*A))); + return __atomic_fetch_sub(&A->ValDoNotUse, V, MO); +} + +template <typename T> +INLINE typename T::Type atomic_exchange(volatile T *A, typename T::Type V, + memory_order MO) { + DCHECK(!(reinterpret_cast<uptr>(A) % sizeof(*A))); + typename T::Type R; + __atomic_exchange(&A->ValDoNotUse, &V, &R, MO); + return R; +} + +template <typename T> +INLINE bool atomic_compare_exchange_strong(volatile T *A, typename T::Type *Cmp, + typename T::Type Xchg, + memory_order MO) { + return __atomic_compare_exchange(&A->ValDoNotUse, Cmp, &Xchg, false, MO, + __ATOMIC_RELAXED); +} + +template <typename T> +INLINE bool atomic_compare_exchange_weak(volatile T *A, typename T::Type *Cmp, + typename T::Type Xchg, + memory_order MO) { + return __atomic_compare_exchange(&A->ValDoNotUse, Cmp, &Xchg, true, MO, + __ATOMIC_RELAXED); +} + +// Clutter-reducing helpers. + +template <typename T> +INLINE typename T::Type atomic_load_relaxed(const volatile T *A) { + return atomic_load(A, memory_order_relaxed); +} + +template <typename T> +INLINE void atomic_store_relaxed(volatile T *A, typename T::Type V) { + atomic_store(A, V, memory_order_relaxed); +} + +} // namespace scudo + +#endif // SCUDO_ATOMIC_H_ diff --git a/lib/scudo/standalone/bytemap.h b/lib/scudo/standalone/bytemap.h new file mode 100644 index 000000000..2c8ba1fd0 --- /dev/null +++ b/lib/scudo/standalone/bytemap.h @@ -0,0 +1,103 @@ +//===-- bytemap.h -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_BYTEMAP_H_ +#define SCUDO_BYTEMAP_H_ + +#include "atomic_helpers.h" +#include "common.h" +#include "mutex.h" + +namespace scudo { + +template <uptr Size> class FlatByteMap { +public: + void initLinkerInitialized() { + Map = reinterpret_cast<u8 *>(map(nullptr, Size, "scudo:bytemap")); + } + void init() { initLinkerInitialized(); } + + void set(uptr Index, u8 Value) { + DCHECK_LT(Index, Size); + DCHECK_EQ(0U, Map[Index]); + Map[Index] = Value; + } + u8 operator[](uptr Index) { + DCHECK_LT(Index, Size); + return Map[Index]; + } + +private: + u8 *Map; +}; + +template <uptr Level1Size, uptr Level2Size> class TwoLevelByteMap { +public: + void initLinkerInitialized() { + Level1Map = reinterpret_cast<atomic_uptr *>( + map(nullptr, sizeof(atomic_uptr) * Level1Size, "scudo:bytemap")); + } + void init() { + initLinkerInitialized(); + Mutex.init(); + } + + void reset() { + for (uptr I = 0; I < Level1Size; I++) { + u8 *P = get(I); + if (!P) + continue; + unmap(P, Level2Size); + } + memset(Level1Map, 0, sizeof(atomic_uptr) * Level1Size); + } + + uptr size() const { return Level1Size * Level2Size; } + + void set(uptr Index, u8 Value) { + DCHECK_LT(Index, Level1Size * Level2Size); + u8 *Level2Map = getOrCreate(Index / Level2Size); + DCHECK_EQ(0U, Level2Map[Index % Level2Size]); + Level2Map[Index % Level2Size] = Value; + } + + u8 operator[](uptr Index) const { + DCHECK_LT(Index, Level1Size * Level2Size); + u8 *Level2Map = get(Index / Level2Size); + if (!Level2Map) + return 0; + return Level2Map[Index % Level2Size]; + } + +private: + u8 *get(uptr Index) const { + DCHECK_LT(Index, Level1Size); + return reinterpret_cast<u8 *>( + atomic_load(&Level1Map[Index], memory_order_acquire)); + } + + u8 *getOrCreate(uptr Index) { + u8 *Res = get(Index); + if (!Res) { + SpinMutexLock L(&Mutex); + if (!(Res = get(Index))) { + Res = reinterpret_cast<u8 *>(map(nullptr, Level2Size, "scudo:bytemap")); + atomic_store(&Level1Map[Index], reinterpret_cast<uptr>(Res), + memory_order_release); + } + } + return Res; + } + + atomic_uptr *Level1Map; + StaticSpinMutex Mutex; +}; + +} // namespace scudo + +#endif // SCUDO_BYTEMAP_H_ diff --git a/lib/scudo/standalone/checksum.cc b/lib/scudo/standalone/checksum.cc new file mode 100644 index 000000000..ff6462bcd --- /dev/null +++ b/lib/scudo/standalone/checksum.cc @@ -0,0 +1,70 @@ +//===-- checksum.cc ---------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "checksum.h" +#include "atomic_helpers.h" + +#if defined(__x86_64__) || defined(__i386__) +#include <cpuid.h> +#elif defined(__arm__) || defined(__aarch64__) +#if SCUDO_FUCHSIA +#include <zircon/features.h> +#include <zircon/syscalls.h> +#else +#include <sys/auxv.h> +#endif +#endif + +namespace scudo { + +atomic_u8 HashAlgorithm = {BSDChecksum}; + +#if defined(__x86_64__) || defined(__i386__) +// i386 and x86_64 specific code to detect CRC32 hardware support via CPUID. +// CRC32 requires the SSE 4.2 instruction set. +#ifndef bit_SSE4_2 +#define bit_SSE4_2 bit_SSE42 // clang and gcc have different defines. +#endif + +bool hasHardwareCRC32() { + u32 Eax, Ebx = 0, Ecx = 0, Edx = 0; + __get_cpuid(0, &Eax, &Ebx, &Ecx, &Edx); + const bool IsIntel = (Ebx == signature_INTEL_ebx) && + (Edx == signature_INTEL_edx) && + (Ecx == signature_INTEL_ecx); + const bool IsAMD = (Ebx == signature_AMD_ebx) && (Edx == signature_AMD_edx) && + (Ecx == signature_AMD_ecx); + if (!IsIntel && !IsAMD) + return false; + __get_cpuid(1, &Eax, &Ebx, &Ecx, &Edx); + return !!(Ecx & bit_SSE4_2); +} + +#elif defined(__arm__) || defined(__aarch64__) +#ifndef AT_HWCAP +#define AT_HWCAP 16 +#endif +#ifndef HWCAP_CRC32 +#define HWCAP_CRC32 (1U << 7) // HWCAP_CRC32 is missing on older platforms. +#endif + +bool hasHardwareCRC32() { +#if SCUDO_FUCHSIA + u32 HWCap; + const zx_status_t Status = + zx_system_get_features(ZX_FEATURE_KIND_CPU, &HWCap); + if (Status != ZX_OK) + return false; + return !!(HWCap & ZX_ARM64_FEATURE_ISA_CRC32); +#else + return !!(getauxval(AT_HWCAP) & HWCAP_CRC32); +#endif // SCUDO_FUCHSIA +} +#endif // defined(__x86_64__) || defined(__i386__) + +} // namespace scudo diff --git a/lib/scudo/standalone/checksum.h b/lib/scudo/standalone/checksum.h new file mode 100644 index 000000000..7c4afcd96 --- /dev/null +++ b/lib/scudo/standalone/checksum.h @@ -0,0 +1,54 @@ +//===-- checksum.h ----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_CHECKSUM_H_ +#define SCUDO_CHECKSUM_H_ + +#include "internal_defs.h" + +// Hardware CRC32 is supported at compilation via the following: +// - for i386 & x86_64: -msse4.2 +// - for ARM & AArch64: -march=armv8-a+crc or -mcrc +// An additional check must be performed at runtime as well to make sure the +// emitted instructions are valid on the target host. + +#ifdef __SSE4_2__ +#include <smmintrin.h> +#define CRC32_INTRINSIC FIRST_32_SECOND_64(_mm_crc32_u32, _mm_crc32_u64) +#endif +#ifdef __ARM_FEATURE_CRC32 +#include <arm_acle.h> +#define CRC32_INTRINSIC FIRST_32_SECOND_64(__crc32cw, __crc32cd) +#endif + +namespace scudo { + +enum ChecksumType : u8 { + BSDChecksum = 0, + HardwareCRC32 = 1, +}; + +// BSD checksum, unlike a software CRC32, doesn't use any array lookup. We save +// significantly on memory accesses, as well as 1K of CRC32 table, on platforms +// that do no support hardware CRC32. The checksum itself is 16-bit, which is at +// odds with CRC32, but enough for our needs. +INLINE u16 computeBSDChecksum(u16 Sum, uptr Data) { + for (u8 I = 0; I < sizeof(Data); I++) { + Sum = static_cast<u16>((Sum >> 1) | ((Sum & 1) << 15)); + Sum = static_cast<u16>(Sum + (Data & 0xff)); + Data >>= 8; + } + return Sum; +} + +bool hasHardwareCRC32(); +WEAK u32 computeHardwareCRC32(u32 Crc, uptr Data); + +} // namespace scudo + +#endif // SCUDO_CHECKSUM_H_ diff --git a/lib/scudo/standalone/common.cc b/lib/scudo/standalone/common.cc new file mode 100644 index 000000000..2a26efbb9 --- /dev/null +++ b/lib/scudo/standalone/common.cc @@ -0,0 +1,32 @@ +//===-- common.cc -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "common.h" +#include "atomic_helpers.h" + +namespace scudo { + +uptr PageSizeCached; +uptr getPageSize(); + +uptr getPageSizeSlow() { + PageSizeCached = getPageSize(); + CHECK_NE(PageSizeCached, 0); + return PageSizeCached; +} + +// Fatal internal map() or unmap() error (potentially OOM related). +void NORETURN dieOnMapUnmapError(bool OutOfMemory) { + outputRaw("Scudo ERROR: internal map or unmap failure"); + if (OutOfMemory) + outputRaw(" (OOM)"); + outputRaw("\n"); + die(); +} + +} // namespace scudo diff --git a/lib/scudo/standalone/common.h b/lib/scudo/standalone/common.h new file mode 100644 index 000000000..313f89c9c --- /dev/null +++ b/lib/scudo/standalone/common.h @@ -0,0 +1,175 @@ +//===-- common.h ------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_COMMON_H_ +#define SCUDO_COMMON_H_ + +#include "internal_defs.h" + +#include "fuchsia.h" +#include "linux.h" + +#include <stddef.h> +#include <string.h> + +namespace scudo { + +template <class Dest, class Source> INLINE Dest bit_cast(const Source &S) { + COMPILER_CHECK(sizeof(Dest) == sizeof(Source)); + Dest D; + memcpy(&D, &S, sizeof(D)); + return D; +} + +INLINE constexpr uptr roundUpTo(uptr X, uptr Boundary) { + return (X + Boundary - 1) & ~(Boundary - 1); +} + +INLINE constexpr uptr roundDownTo(uptr X, uptr Boundary) { + return X & ~(Boundary - 1); +} + +INLINE constexpr bool isAligned(uptr X, uptr Alignment) { + return (X & (Alignment - 1)) == 0; +} + +template <class T> constexpr T Min(T A, T B) { return A < B ? A : B; } + +template <class T> constexpr T Max(T A, T B) { return A > B ? A : B; } + +template <class T> void Swap(T &A, T &B) { + T Tmp = A; + A = B; + B = Tmp; +} + +INLINE bool isPowerOfTwo(uptr X) { return (X & (X - 1)) == 0; } + +INLINE uptr getMostSignificantSetBitIndex(uptr X) { + DCHECK_NE(X, 0U); + return SCUDO_WORDSIZE - 1U - static_cast<uptr>(__builtin_clzl(X)); +} + +INLINE uptr roundUpToPowerOfTwo(uptr Size) { + DCHECK(Size); + if (isPowerOfTwo(Size)) + return Size; + const uptr Up = getMostSignificantSetBitIndex(Size); + DCHECK_LT(Size, (1UL << (Up + 1))); + DCHECK_GT(Size, (1UL << Up)); + return 1UL << (Up + 1); +} + +INLINE uptr getLeastSignificantSetBitIndex(uptr X) { + DCHECK_NE(X, 0U); + return static_cast<uptr>(__builtin_ctzl(X)); +} + +INLINE uptr getLog2(uptr X) { + DCHECK(isPowerOfTwo(X)); + return getLeastSignificantSetBitIndex(X); +} + +INLINE u32 getRandomU32(u32 *State) { + // ANSI C linear congruential PRNG (16-bit output). + // return (*State = *State * 1103515245 + 12345) >> 16; + // XorShift (32-bit output). + *State ^= *State << 13; + *State ^= *State >> 17; + *State ^= *State << 5; + return *State; +} + +INLINE u32 getRandomModN(u32 *State, u32 N) { + return getRandomU32(State) % N; // [0, N) +} + +template <typename T> INLINE void shuffle(T *A, u32 N, u32 *RandState) { + if (N <= 1) + return; + u32 State = *RandState; + for (u32 I = N - 1; I > 0; I--) + Swap(A[I], A[getRandomModN(&State, I + 1)]); + *RandState = State; +} + +// Hardware specific inlinable functions. + +INLINE void yieldProcessor(u8 Count) { +#if defined(__i386__) || defined(__x86_64__) + __asm__ __volatile__("" ::: "memory"); + for (u8 I = 0; I < Count; I++) + __asm__ __volatile__("pause"); +#elif defined(__aarch64__) || defined(__arm__) + __asm__ __volatile__("" ::: "memory"); + for (u8 I = 0; I < Count; I++) + __asm__ __volatile__("yield"); +#endif + __asm__ __volatile__("" ::: "memory"); +} + +// Platform specific functions. + +void yieldPlatform(); + +extern uptr PageSizeCached; +uptr getPageSizeSlow(); +INLINE uptr getPageSizeCached() { + if (LIKELY(PageSizeCached)) + return PageSizeCached; + return getPageSizeSlow(); +} + +u32 getNumberOfCPUs(); + +const char *getEnv(const char *Name); + +u64 getMonotonicTime(); + +// Our randomness gathering function is limited to 256 bytes to ensure we get +// as many bytes as requested, and avoid interruptions (on Linux). +constexpr uptr MaxRandomLength = 256U; +bool getRandom(void *Buffer, uptr Length, bool Blocking = false); + +// Platform memory mapping functions. + +#define MAP_ALLOWNOMEM (1U << 0) +#define MAP_NOACCESS (1U << 1) +#define MAP_RESIZABLE (1U << 2) + +// Our platform memory mapping use is restricted to 3 scenarios: +// - reserve memory at a random address (MAP_NOACCESS); +// - commit memory in a previously reserved space; +// - commit memory at a random address. +// As such, only a subset of parameters combinations is valid, which is checked +// by the function implementation. The Data parameter allows to pass opaque +// platform specific data to the function. +// Returns nullptr on error or dies if MAP_ALLOWNOMEM is not specified. +void *map(void *Addr, uptr Size, const char *Name, uptr Flags = 0, + MapPlatformData *Data = nullptr); + +// Indicates that we are getting rid of the whole mapping, which might have +// further consequences on Data, depending on the platform. +#define UNMAP_ALL (1U << 0) + +void unmap(void *Addr, uptr Size, uptr Flags = 0, + MapPlatformData *Data = nullptr); + +void releasePagesToOS(uptr BaseAddress, uptr Offset, uptr Size, + MapPlatformData *Data = nullptr); + +// Internal map & unmap fatal error. This must not call map(). +void NORETURN dieOnMapUnmapError(bool OutOfMemory = false); + +// Logging related functions. + +void setAbortMessage(const char *Message); + +} // namespace scudo + +#endif // SCUDO_COMMON_H_ diff --git a/lib/scudo/standalone/crc32_hw.cc b/lib/scudo/standalone/crc32_hw.cc new file mode 100644 index 000000000..f4dae7b5f --- /dev/null +++ b/lib/scudo/standalone/crc32_hw.cc @@ -0,0 +1,19 @@ +//===-- crc32_hw.h ----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "checksum.h" + +namespace scudo { + +#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32) +u32 computeHardwareCRC32(u32 Crc, uptr Data) { + return static_cast<u32>(CRC32_INTRINSIC(Crc, Data)); +} +#endif // defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32) + +} // namespace scudo diff --git a/lib/scudo/standalone/flags.cc b/lib/scudo/standalone/flags.cc new file mode 100644 index 000000000..21144f211 --- /dev/null +++ b/lib/scudo/standalone/flags.cc @@ -0,0 +1,57 @@ +//===-- flags.cc ------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "flags.h" +#include "common.h" +#include "flags_parser.h" +#include "interface.h" + +namespace scudo { + +Flags *getFlags() { + static Flags F; + return &F; +} + +void Flags::setDefaults() { +#define SCUDO_FLAG(Type, Name, DefaultValue, Description) Name = DefaultValue; +#include "flags.inc" +#undef SCUDO_FLAG +} + +void registerFlags(FlagParser *Parser, Flags *F) { +#define SCUDO_FLAG(Type, Name, DefaultValue, Description) \ + Parser->registerFlag(#Name, Description, FlagType::FT_##Type, \ + reinterpret_cast<void *>(&F->Name)); +#include "flags.inc" +#undef SCUDO_FLAG +} + +static const char *getCompileDefinitionScudoDefaultOptions() { +#ifdef SCUDO_DEFAULT_OPTIONS + return STRINGIFY(SCUDO_DEFAULT_OPTIONS); +#else + return ""; +#endif +} + +static const char *getScudoDefaultOptions() { + return (&__scudo_default_options) ? __scudo_default_options() : ""; +} + +void initFlags() { + Flags *F = getFlags(); + F->setDefaults(); + FlagParser Parser; + registerFlags(&Parser, F); + Parser.parseString(getCompileDefinitionScudoDefaultOptions()); + Parser.parseString(getScudoDefaultOptions()); + Parser.parseString(getEnv("SCUDO_OPTIONS")); +} + +} // namespace scudo diff --git a/lib/scudo/standalone/flags.h b/lib/scudo/standalone/flags.h new file mode 100644 index 000000000..edd39a1b8 --- /dev/null +++ b/lib/scudo/standalone/flags.h @@ -0,0 +1,30 @@ +//===-- flags.h -------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_FLAGS_H_ +#define SCUDO_FLAGS_H_ + +#include "internal_defs.h" + +namespace scudo { + +struct Flags { +#define SCUDO_FLAG(Type, Name, DefaultValue, Description) Type Name; +#include "flags.inc" +#undef SCUDO_FLAG + void setDefaults(); +}; + +Flags *getFlags(); +void initFlags(); +class FlagParser; +void registerFlags(FlagParser *Parser, Flags *F); + +} // namespace scudo + +#endif // SCUDO_FLAGS_H_ diff --git a/lib/scudo/standalone/flags.inc b/lib/scudo/standalone/flags.inc new file mode 100644 index 000000000..25b86e14f --- /dev/null +++ b/lib/scudo/standalone/flags.inc @@ -0,0 +1,50 @@ +//===-- flags.inc -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_FLAG +#error "Define SCUDO_FLAG prior to including this file!" +#endif + +SCUDO_FLAG(int, quarantine_size_kb, 0, + "Size (in kilobytes) of quarantine used to delay the actual " + "deallocation of chunks. Lower value may reduce memory usage but " + "decrease the effectiveness of the mitigation.") + +SCUDO_FLAG(int, thread_local_quarantine_size_kb, 0, + "Size (in kilobytes) of per-thread cache used to offload the global " + "quarantine. Lower value may reduce memory usage but might increase " + "the contention on the global quarantine.") + +SCUDO_FLAG(int, quarantine_max_chunk_size, 0, + "Size (in bytes) up to which chunks will be quarantined (if lower " + "than or equal to).") + +SCUDO_FLAG(bool, dealloc_type_mismatch, false, + "Terminate on a type mismatch in allocation-deallocation functions, " + "eg: malloc/delete, new/free, new/delete[], etc.") + +SCUDO_FLAG(bool, delete_size_mismatch, true, + "Terminate on a size mismatch between a sized-delete and the actual " + "size of a chunk (as provided to new/new[]).") + +SCUDO_FLAG(bool, zero_contents, false, "Zero chunk contents on allocation.") + +SCUDO_FLAG(int, rss_limit_mb, -1, + "Enforce an upper limit (in megabytes) to the process RSS. The " + "allocator will terminate or return NULL when allocations are " + "attempted past that limit (depending on may_return_null). Negative " + "values disable the feature.") + +SCUDO_FLAG(bool, may_return_null, true, + "Indicate whether the allocator should terminate instead of " + "returning NULL in otherwise non-fatal error scenarios, eg: OOM, " + "invalid allocation alignments, etc.") + +SCUDO_FLAG(int, release_to_os_interval_ms, 5000, + "Interval (in milliseconds) at which to attempt release of unused " + "memory to the OS. Negative values disable the feature.") diff --git a/lib/scudo/standalone/flags_parser.cc b/lib/scudo/standalone/flags_parser.cc new file mode 100644 index 000000000..918304f49 --- /dev/null +++ b/lib/scudo/standalone/flags_parser.cc @@ -0,0 +1,163 @@ +//===-- flags_parser.cc -----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "flags_parser.h" +#include "common.h" +#include "report.h" + +#include <string.h> + +namespace scudo { + +class UnknownFlagsRegistry { + static const u32 MaxUnknownFlags = 16; + const char *UnknownFlagsNames[MaxUnknownFlags]; + u32 NumberOfUnknownFlags; + +public: + void add(const char *Name) { + CHECK_LT(NumberOfUnknownFlags, MaxUnknownFlags); + UnknownFlagsNames[NumberOfUnknownFlags++] = Name; + } + + void report() { + if (!NumberOfUnknownFlags) + return; + Printf("Scudo WARNING: found %d unrecognized flag(s):\n", + NumberOfUnknownFlags); + for (u32 I = 0; I < NumberOfUnknownFlags; ++I) + Printf(" %s\n", UnknownFlagsNames[I]); + NumberOfUnknownFlags = 0; + } +}; +static UnknownFlagsRegistry UnknownFlags; + +void reportUnrecognizedFlags() { UnknownFlags.report(); } + +void FlagParser::printFlagDescriptions() { + Printf("Available flags for Scudo:\n"); + for (u32 I = 0; I < NumberOfFlags; ++I) + Printf("\t%s\n\t\t- %s\n", Flags[I].Name, Flags[I].Desc); +} + +static bool isSeparator(char C) { + return C == ' ' || C == ',' || C == ':' || C == '\n' || C == '\t' || + C == '\r'; +} + +static bool isSeparatorOrNull(char C) { return !C || isSeparator(C); } + +void FlagParser::skipWhitespace() { + while (isSeparator(Buffer[Pos])) + ++Pos; +} + +void FlagParser::parseFlag() { + const uptr NameStart = Pos; + while (Buffer[Pos] != '=' && !isSeparatorOrNull(Buffer[Pos])) + ++Pos; + if (Buffer[Pos] != '=') + reportError("expected '='"); + const char *Name = Buffer + NameStart; + const uptr ValueStart = ++Pos; + const char *Value; + if (Buffer[Pos] == '\'' || Buffer[Pos] == '"') { + const char Quote = Buffer[Pos++]; + while (Buffer[Pos] != 0 && Buffer[Pos] != Quote) + ++Pos; + if (Buffer[Pos] == 0) + reportError("unterminated string"); + Value = Buffer + ValueStart + 1; + ++Pos; // consume the closing quote + } else { + while (!isSeparatorOrNull(Buffer[Pos])) + ++Pos; + Value = Buffer + ValueStart; + } + if (!runHandler(Name, Value)) + reportError("flag parsing failed."); +} + +void FlagParser::parseFlags() { + while (true) { + skipWhitespace(); + if (Buffer[Pos] == 0) + break; + parseFlag(); + } +} + +void FlagParser::parseString(const char *S) { + if (!S) + return; + // Backup current parser state to allow nested parseString() calls. + const char *OldBuffer = Buffer; + const uptr OldPos = Pos; + Buffer = S; + Pos = 0; + + parseFlags(); + + Buffer = OldBuffer; + Pos = OldPos; +} + +INLINE bool parseBool(const char *Value, bool *b) { + if (strncmp(Value, "0", 1) == 0 || strncmp(Value, "no", 2) == 0 || + strncmp(Value, "false", 5) == 0) { + *b = false; + return true; + } + if (strncmp(Value, "1", 1) == 0 || strncmp(Value, "yes", 3) == 0 || + strncmp(Value, "true", 4) == 0) { + *b = true; + return true; + } + return false; +} + +bool FlagParser::runHandler(const char *Name, const char *Value) { + for (u32 I = 0; I < NumberOfFlags; ++I) { + const uptr Len = strlen(Flags[I].Name); + if (strncmp(Name, Flags[I].Name, Len) != 0 || Name[Len] != '=') + continue; + bool Ok = false; + switch (Flags[I].Type) { + case FlagType::FT_bool: + Ok = parseBool(Value, reinterpret_cast<bool *>(Flags[I].Var)); + if (!Ok) + reportInvalidFlag("bool", Value); + break; + case FlagType::FT_int: + char *ValueEnd; + *reinterpret_cast<int *>(Flags[I].Var) = + static_cast<int>(strtol(Value, &ValueEnd, 10)); + Ok = + *ValueEnd == '"' || *ValueEnd == '\'' || isSeparatorOrNull(*ValueEnd); + if (!Ok) + reportInvalidFlag("int", Value); + break; + } + return Ok; + } + // Unrecognized flag. This is not a fatal error, we may print a warning later. + UnknownFlags.add(Name); + return true; +} + +void FlagParser::registerFlag(const char *Name, const char *Desc, FlagType Type, + void *Var) { + CHECK_LT(NumberOfFlags, MaxFlags); + Flags[NumberOfFlags].Name = Name; + Flags[NumberOfFlags].Desc = Desc; + Flags[NumberOfFlags].Type = Type; + Flags[NumberOfFlags].Var = Var; + ++NumberOfFlags; +} + +} // namespace scudo diff --git a/lib/scudo/standalone/flags_parser.h b/lib/scudo/standalone/flags_parser.h new file mode 100644 index 000000000..d65bff7e7 --- /dev/null +++ b/lib/scudo/standalone/flags_parser.h @@ -0,0 +1,56 @@ +//===-- flags_parser.h ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_FLAGS_PARSER_H_ +#define SCUDO_FLAGS_PARSER_H_ + +#include "report.h" +#include "string_utils.h" + +#include <stddef.h> +#include <stdlib.h> + +namespace scudo { + +enum class FlagType : u8 { + FT_bool, + FT_int, +}; + +class FlagParser { +public: + void registerFlag(const char *Name, const char *Desc, FlagType Type, + void *Var); + void parseString(const char *S); + void printFlagDescriptions(); + +private: + static const u32 MaxFlags = 12; + struct Flag { + const char *Name; + const char *Desc; + FlagType Type; + void *Var; + } Flags[MaxFlags]; + + u32 NumberOfFlags = 0; + const char *Buffer = nullptr; + uptr Pos = 0; + + void reportFatalError(const char *Error); + void skipWhitespace(); + void parseFlags(); + void parseFlag(); + bool runHandler(const char *Name, const char *Value); +}; + +void reportUnrecognizedFlags(); + +} // namespace scudo + +#endif // SCUDO_FLAGS_PARSER_H_ diff --git a/lib/scudo/standalone/fuchsia.cc b/lib/scudo/standalone/fuchsia.cc new file mode 100644 index 000000000..e54563138 --- /dev/null +++ b/lib/scudo/standalone/fuchsia.cc @@ -0,0 +1,186 @@ +//===-- fuchsia.cc ----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "platform.h" + +#if SCUDO_FUCHSIA + +#include "common.h" +#include "mutex.h" +#include "string_utils.h" + +#include <limits.h> // for PAGE_SIZE +#include <stdlib.h> // for getenv() +#include <zircon/sanitizer.h> +#include <zircon/syscalls.h> + +namespace scudo { + +void yieldPlatform() { + const zx_status_t Status = _zx_nanosleep(0); + CHECK_EQ(Status, ZX_OK); +} + +uptr getPageSize() { return PAGE_SIZE; } + +void NORETURN die() { __builtin_trap(); } + +// We zero-initialize the Extra parameter of map(), make sure this is consistent +// with ZX_HANDLE_INVALID. +COMPILER_CHECK(ZX_HANDLE_INVALID == 0); + +static void *allocateVmar(uptr Size, MapPlatformData *Data, bool AllowNoMem) { + // Only scenario so far. + DCHECK(Data); + DCHECK_EQ(Data->Vmar, ZX_HANDLE_INVALID); + + const zx_status_t Status = _zx_vmar_allocate( + _zx_vmar_root_self(), + ZX_VM_CAN_MAP_READ | ZX_VM_CAN_MAP_WRITE | ZX_VM_CAN_MAP_SPECIFIC, 0, + Size, &Data->Vmar, &Data->VmarBase); + if (Status != ZX_OK) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY); + return nullptr; + } + return reinterpret_cast<void *>(Data->VmarBase); +} + +void *map(void *Addr, uptr Size, const char *Name, uptr Flags, + MapPlatformData *Data) { + DCHECK_EQ(Size % PAGE_SIZE, 0); + const bool AllowNoMem = !!(Flags & MAP_ALLOWNOMEM); + + // For MAP_NOACCESS, just allocate a Vmar and return. + if (Flags & MAP_NOACCESS) + return allocateVmar(Size, Data, AllowNoMem); + + const zx_handle_t Vmar = Data ? Data->Vmar : _zx_vmar_root_self(); + CHECK_NE(Vmar, ZX_HANDLE_INVALID); + + zx_status_t Status; + zx_handle_t Vmo; + uint64_t VmoSize = 0; + if (Data && Data->Vmo != ZX_HANDLE_INVALID) { + // If a Vmo was specified, it's a resize operation. + CHECK(Addr); + DCHECK(Flags & MAP_RESIZABLE); + Vmo = Data->Vmo; + VmoSize = Data->VmoSize; + Status = _zx_vmo_set_size(Vmo, VmoSize + Size); + if (Status != ZX_OK) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY); + return nullptr; + } + } else { + // Otherwise, create a Vmo and set its name. + Status = _zx_vmo_create(Size, ZX_VMO_RESIZABLE, &Vmo); + if (Status != ZX_OK) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY); + return nullptr; + } + _zx_object_set_property(Vmo, ZX_PROP_NAME, Name, strlen(Name)); + } + + uintptr_t P; + zx_vm_option_t MapFlags = ZX_VM_PERM_READ | ZX_VM_PERM_WRITE; + const uint64_t Offset = + Addr ? reinterpret_cast<uintptr_t>(Addr) - Data->VmarBase : 0; + if (Offset) + MapFlags |= ZX_VM_SPECIFIC; + Status = _zx_vmar_map(Vmar, MapFlags, Offset, Vmo, VmoSize, Size, &P); + // No need to track the Vmo if we don't intend on resizing it. Close it. + if (Flags & MAP_RESIZABLE) { + DCHECK(Data); + DCHECK_EQ(Data->Vmo, ZX_HANDLE_INVALID); + Data->Vmo = Vmo; + } else { + CHECK_EQ(_zx_handle_close(Vmo), ZX_OK); + } + if (Status != ZX_OK) { + if (Status != ZX_ERR_NO_MEMORY || !AllowNoMem) + dieOnMapUnmapError(Status == ZX_ERR_NO_MEMORY); + return nullptr; + } + if (Data) + Data->VmoSize += Size; + + return reinterpret_cast<void *>(P); +} + +void unmap(void *Addr, uptr Size, uptr Flags, MapPlatformData *Data) { + if (Flags & UNMAP_ALL) { + DCHECK_NE(Data, nullptr); + const zx_handle_t Vmar = Data->Vmar; + DCHECK_NE(Vmar, _zx_vmar_root_self()); + // Destroying the vmar effectively unmaps the whole mapping. + CHECK_EQ(_zx_vmar_destroy(Vmar), ZX_OK); + CHECK_EQ(_zx_handle_close(Vmar), ZX_OK); + } else { + const zx_handle_t Vmar = Data ? Data->Vmar : _zx_vmar_root_self(); + const zx_status_t Status = + _zx_vmar_unmap(Vmar, reinterpret_cast<uintptr_t>(Addr), Size); + if (Status != ZX_OK) + dieOnMapUnmapError(); + } + if (Data) { + if (Data->Vmo != ZX_HANDLE_INVALID) + CHECK_EQ(_zx_handle_close(Data->Vmo), ZX_OK); + memset(Data, 0, sizeof(*Data)); + } +} + +void releasePagesToOS(UNUSED uptr BaseAddress, uptr Offset, uptr Size, + MapPlatformData *Data) { + DCHECK(Data); + DCHECK_NE(Data->Vmar, ZX_HANDLE_INVALID); + DCHECK_NE(Data->Vmo, ZX_HANDLE_INVALID); + const zx_status_t Status = + _zx_vmo_op_range(Data->Vmo, ZX_VMO_OP_DECOMMIT, Offset, Size, NULL, 0); + CHECK_EQ(Status, ZX_OK); +} + +const char *getEnv(const char *Name) { return getenv(Name); } + +void BlockingMutex::wait() { + const zx_status_t Status = + _zx_futex_wait(reinterpret_cast<zx_futex_t *>(OpaqueStorage), MtxSleeping, + ZX_HANDLE_INVALID, ZX_TIME_INFINITE); + if (Status != ZX_ERR_BAD_STATE) + CHECK_EQ(Status, ZX_OK); // Normal race +} + +void BlockingMutex::wake() { + const zx_status_t Status = + _zx_futex_wake(reinterpret_cast<zx_futex_t *>(OpaqueStorage), 1); + CHECK_EQ(Status, ZX_OK); +} + +u64 getMonotonicTime() { return _zx_clock_get_monotonic(); } + +u32 getNumberOfCPUs() { return _zx_system_get_num_cpus(); } + +bool getRandom(void *Buffer, uptr Length, bool Blocking) { + COMPILER_CHECK(MaxRandomLength <= ZX_CPRNG_DRAW_MAX_LEN); + if (!Buffer || !Length || Length > MaxRandomLength) + return false; + _zx_cprng_draw(Buffer, Length); + return true; +} + +void outputRaw(const char *Buffer) { + __sanitizer_log_write(Buffer, strlen(Buffer)); +} + +void setAbortMessage(const char *Message) {} + +} // namespace scudo + +#endif // SCUDO_FUCHSIA diff --git a/lib/scudo/standalone/fuchsia.h b/lib/scudo/standalone/fuchsia.h new file mode 100644 index 000000000..d6993f892 --- /dev/null +++ b/lib/scudo/standalone/fuchsia.h @@ -0,0 +1,31 @@ +//===-- fuchsia.h -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_FUCHSIA_H_ +#define SCUDO_FUCHSIA_H_ + +#include "platform.h" + +#if SCUDO_FUCHSIA + +#include <zircon/process.h> + +namespace scudo { + +struct MapPlatformData { + zx_handle_t Vmar; + zx_handle_t Vmo; + uintptr_t VmarBase; + uint64_t VmoSize; +}; + +} // namespace scudo + +#endif // SCUDO_FUCHSIA + +#endif // SCUDO_FUCHSIA_H_ diff --git a/lib/scudo/standalone/interface.h b/lib/scudo/standalone/interface.h new file mode 100644 index 000000000..e2639823f --- /dev/null +++ b/lib/scudo/standalone/interface.h @@ -0,0 +1,29 @@ +//===-- interface.h ---------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_INTERFACE_H_ +#define SCUDO_INTERFACE_H_ + +#include "internal_defs.h" + +extern "C" { + +WEAK INTERFACE const char *__scudo_default_options(); + +// Post-allocation & pre-deallocation hooks. +// They must be thread-safe and not use heap related functions. +WEAK INTERFACE void __scudo_allocate_hook(void *ptr, size_t size); +WEAK INTERFACE void __scudo_deallocate_hook(void *ptr); + +WEAK INTERFACE void __scudo_print_stats(void); + +typedef void (*iterate_callback)(uintptr_t base, size_t size, void *arg); + +} // extern "C" + +#endif // SCUDO_INTERFACE_H_ diff --git a/lib/scudo/standalone/internal_defs.h b/lib/scudo/standalone/internal_defs.h new file mode 100644 index 000000000..cca9c42af --- /dev/null +++ b/lib/scudo/standalone/internal_defs.h @@ -0,0 +1,135 @@ +//===-- internal_defs.h -----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_INTERNAL_DEFS_H_ +#define SCUDO_INTERNAL_DEFS_H_ + +#include "platform.h" + +#include <stdint.h> + +#ifndef SCUDO_DEBUG +#define SCUDO_DEBUG 0 +#endif + +#define ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0])) + +// String related macros. + +#define STRINGIFY_(S) #S +#define STRINGIFY(S) STRINGIFY_(S) +#define CONCATENATE_(S, C) S##C +#define CONCATENATE(S, C) CONCATENATE_(S, C) + +// Attributes & builtins related macros. + +#define INTERFACE __attribute__((visibility("default"))) +#define WEAK __attribute__((weak)) +#define INLINE inline +#define ALWAYS_INLINE inline __attribute__((always_inline)) +#define ALIAS(X) __attribute__((alias(X))) +// Please only use the ALIGNED macro before the type. Using ALIGNED after the +// variable declaration is not portable. +#define ALIGNED(X) __attribute__((aligned(X))) +#define FORMAT(F, A) __attribute__((format(printf, F, A))) +#define NOINLINE __attribute__((noinline)) +#define NORETURN __attribute__((noreturn)) +#define THREADLOCAL __thread +#define LIKELY(X) __builtin_expect(!!(X), 1) +#define UNLIKELY(X) __builtin_expect(!!(X), 0) +#if defined(__i386__) || defined(__x86_64__) +// __builtin_prefetch(X) generates prefetchnt0 on x86 +#define PREFETCH(X) __asm__("prefetchnta (%0)" : : "r"(X)) +#else +#define PREFETCH(X) __builtin_prefetch(X) +#endif +#define UNUSED __attribute__((unused)) +#define USED __attribute__((used)) +#define NOEXCEPT noexcept + +namespace scudo { + +typedef unsigned long uptr; +typedef signed long sptr; +typedef unsigned char u8; +typedef unsigned short u16; +typedef unsigned int u32; +typedef unsigned long long u64; +typedef signed char s8; +typedef signed short s16; +typedef signed int s32; +typedef signed long long s64; + +// The following two functions have platform specific implementations. +void outputRaw(const char *Buffer); +void NORETURN die(); + +#define RAW_CHECK_MSG(Expr, Msg) \ + do { \ + if (UNLIKELY(!(Expr))) { \ + outputRaw(Msg); \ + die(); \ + } \ + } while (false) + +#define RAW_CHECK(Expr) RAW_CHECK_MSG(Expr, #Expr) + +void NORETURN reportCheckFailed(const char *File, int Line, + const char *Condition, u64 Value1, u64 Value2); + +#define CHECK_IMPL(C1, Op, C2) \ + do { \ + u64 V1 = (u64)(C1); \ + u64 V2 = (u64)(C2); \ + if (UNLIKELY(!(V1 Op V2))) { \ + reportCheckFailed(__FILE__, __LINE__, "(" #C1 ") " #Op " (" #C2 ")", V1, \ + V2); \ + die(); \ + } \ + } while (false) + +#define CHECK(A) CHECK_IMPL((A), !=, 0) +#define CHECK_EQ(A, B) CHECK_IMPL((A), ==, (B)) +#define CHECK_NE(A, B) CHECK_IMPL((A), !=, (B)) +#define CHECK_LT(A, B) CHECK_IMPL((A), <, (B)) +#define CHECK_LE(A, B) CHECK_IMPL((A), <=, (B)) +#define CHECK_GT(A, B) CHECK_IMPL((A), >, (B)) +#define CHECK_GE(A, B) CHECK_IMPL((A), >=, (B)) + +#if SCUDO_DEBUG +#define DCHECK(A) CHECK(A) +#define DCHECK_EQ(A, B) CHECK_EQ(A, B) +#define DCHECK_NE(A, B) CHECK_NE(A, B) +#define DCHECK_LT(A, B) CHECK_LT(A, B) +#define DCHECK_LE(A, B) CHECK_LE(A, B) +#define DCHECK_GT(A, B) CHECK_GT(A, B) +#define DCHECK_GE(A, B) CHECK_GE(A, B) +#else +#define DCHECK(A) +#define DCHECK_EQ(A, B) +#define DCHECK_NE(A, B) +#define DCHECK_LT(A, B) +#define DCHECK_LE(A, B) +#define DCHECK_GT(A, B) +#define DCHECK_GE(A, B) +#endif + +// The superfluous die() call effectively makes this macro NORETURN. +#define UNREACHABLE(Msg) \ + do { \ + CHECK(0 && Msg); \ + die(); \ + } while (0) + +#define COMPILER_CHECK(Pred) static_assert(Pred, "") + +enum LinkerInitialized { LINKER_INITIALIZED = 0 }; + +} // namespace scudo + +#endif // SCUDO_INTERNAL_DEFS_H_ diff --git a/lib/scudo/standalone/linux.cc b/lib/scudo/standalone/linux.cc new file mode 100644 index 000000000..5e695d72f --- /dev/null +++ b/lib/scudo/standalone/linux.cc @@ -0,0 +1,150 @@ +//===-- linux.cc ------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "platform.h" + +#if SCUDO_LINUX + +#include "common.h" +#include "linux.h" +#include "mutex.h" +#include "string_utils.h" + +#include <errno.h> +#include <fcntl.h> +#include <linux/futex.h> +#include <sched.h> +#include <stdlib.h> +#include <string.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <time.h> +#include <unistd.h> + +#if SCUDO_ANDROID +#include <sys/prctl.h> +// Definitions of prctl arguments to set a vma name in Android kernels. +#define ANDROID_PR_SET_VMA 0x53564d41 +#define ANDROID_PR_SET_VMA_ANON_NAME 0 +#endif + +namespace scudo { + +void yieldPlatform() { sched_yield(); } + +uptr getPageSize() { return static_cast<uptr>(sysconf(_SC_PAGESIZE)); } + +void NORETURN die() { abort(); } + +void *map(void *Addr, uptr Size, UNUSED const char *Name, uptr Flags, + UNUSED MapPlatformData *Data) { + int MmapFlags = MAP_PRIVATE | MAP_ANON; + if (Flags & MAP_NOACCESS) + MmapFlags |= MAP_NORESERVE; + if (Addr) { + // Currently no scenario for a noaccess mapping with a fixed address. + DCHECK_EQ(Flags & MAP_NOACCESS, 0); + MmapFlags |= MAP_FIXED; + } + const int MmapProt = + (Flags & MAP_NOACCESS) ? PROT_NONE : PROT_READ | PROT_WRITE; + void *P = mmap(Addr, Size, MmapProt, MmapFlags, -1, 0); + if (P == MAP_FAILED) { + if (!(Flags & MAP_ALLOWNOMEM) || errno != ENOMEM) + dieOnMapUnmapError(errno == ENOMEM); + return nullptr; + } +#if SCUDO_ANDROID + if (!(Flags & MAP_NOACCESS)) + prctl(ANDROID_PR_SET_VMA, ANDROID_PR_SET_VMA_ANON_NAME, P, Size, Name); +#endif + return P; +} + +void unmap(void *Addr, uptr Size, UNUSED uptr Flags, + UNUSED MapPlatformData *Data) { + if (munmap(Addr, Size) != 0) + dieOnMapUnmapError(); +} + +void releasePagesToOS(uptr BaseAddress, uptr Offset, uptr Size, + UNUSED MapPlatformData *Data) { + void *Addr = reinterpret_cast<void *>(BaseAddress + Offset); + while (madvise(Addr, Size, MADV_DONTNEED) == -1 && errno == EAGAIN) { + } +} + +// Calling getenv should be fine (c)(tm) at any time. +const char *getEnv(const char *Name) { return getenv(Name); } + +void BlockingMutex::wait() { + syscall(SYS_futex, reinterpret_cast<uptr>(OpaqueStorage), FUTEX_WAIT_PRIVATE, + MtxSleeping, nullptr, nullptr, 0); +} + +void BlockingMutex::wake() { + syscall(SYS_futex, reinterpret_cast<uptr>(OpaqueStorage), FUTEX_WAKE_PRIVATE, + 1, nullptr, nullptr, 0); +} + +u64 getMonotonicTime() { + timespec TS; + clock_gettime(CLOCK_MONOTONIC, &TS); + return static_cast<u64>(TS.tv_sec) * (1000ULL * 1000 * 1000) + + static_cast<u64>(TS.tv_nsec); +} + +u32 getNumberOfCPUs() { + cpu_set_t CPUs; + CHECK_EQ(sched_getaffinity(0, sizeof(cpu_set_t), &CPUs), 0); + return static_cast<u32>(CPU_COUNT(&CPUs)); +} + +// Blocking is possibly unused if the getrandom block is not compiled in. +bool getRandom(void *Buffer, uptr Length, UNUSED bool Blocking) { + if (!Buffer || !Length || Length > MaxRandomLength) + return false; + ssize_t ReadBytes; +#if defined(SYS_getrandom) +#if !defined(GRND_NONBLOCK) +#define GRND_NONBLOCK 1 +#endif + // Up to 256 bytes, getrandom will not be interrupted. + ReadBytes = + syscall(SYS_getrandom, Buffer, Length, Blocking ? 0 : GRND_NONBLOCK); + if (ReadBytes == static_cast<ssize_t>(Length)) + return true; +#endif // defined(SYS_getrandom) + // Up to 256 bytes, a read off /dev/urandom will not be interrupted. + // Blocking is moot here, O_NONBLOCK has no effect when opening /dev/urandom. + const int FileDesc = open("/dev/urandom", O_RDONLY); + if (FileDesc == -1) + return false; + ReadBytes = read(FileDesc, Buffer, Length); + close(FileDesc); + return (ReadBytes == static_cast<ssize_t>(Length)); +} + +void outputRaw(const char *Buffer) { + static StaticSpinMutex Mutex; + SpinMutexLock L(&Mutex); + write(2, Buffer, strlen(Buffer)); +} + +extern "C" WEAK void android_set_abort_message(const char *); + +void setAbortMessage(const char *Message) { + if (&android_set_abort_message) + android_set_abort_message(Message); +} + +} // namespace scudo + +#endif // SCUDO_LINUX diff --git a/lib/scudo/standalone/linux.h b/lib/scudo/standalone/linux.h new file mode 100644 index 000000000..92c9eb5e9 --- /dev/null +++ b/lib/scudo/standalone/linux.h @@ -0,0 +1,70 @@ +//===-- linux.h -------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_LINUX_H_ +#define SCUDO_LINUX_H_ + +#include "platform.h" + +#if SCUDO_LINUX + +namespace scudo { + +// MapPlatformData is unused on Linux, define it as a minimally sized structure. +struct MapPlatformData {}; + +#if SCUDO_ANDROID + +#if defined(__aarch64__) +#define __get_tls() \ + ({ \ + void **__v; \ + __asm__("mrs %0, tpidr_el0" : "=r"(__v)); \ + __v; \ + }) +#elif defined(__arm__) +#define __get_tls() \ + ({ \ + void **__v; \ + __asm__("mrc p15, 0, %0, c13, c0, 3" : "=r"(__v)); \ + __v; \ + }) +#elif defined(__i386__) +#define __get_tls() \ + ({ \ + void **__v; \ + __asm__("movl %%gs:0, %0" : "=r"(__v)); \ + __v; \ + }) +#elif defined(__x86_64__) +#define __get_tls() \ + ({ \ + void **__v; \ + __asm__("mov %%fs:0, %0" : "=r"(__v)); \ + __v; \ + }) +#else +#error "Unsupported architecture." +#endif + +// The Android Bionic team has allocated a TLS slot for sanitizers starting +// with Q, given that Android currently doesn't support ELF TLS. It is used to +// store sanitizer thread specific data. +static const int TLS_SLOT_SANITIZER = 8; // TODO(kostyak): 6 for Q!! + +ALWAYS_INLINE uptr *getAndroidTlsPtr() { + return reinterpret_cast<uptr *>(&__get_tls()[TLS_SLOT_SANITIZER]); +} + +#endif // SCUDO_ANDROID + +} // namespace scudo + +#endif // SCUDO_LINUX + +#endif // SCUDO_LINUX_H_ diff --git a/lib/scudo/standalone/list.h b/lib/scudo/standalone/list.h new file mode 100644 index 000000000..139e73eff --- /dev/null +++ b/lib/scudo/standalone/list.h @@ -0,0 +1,156 @@ +//===-- list.h --------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_LIST_H_ +#define SCUDO_LIST_H_ + +#include "internal_defs.h" + +namespace scudo { + +// Intrusive POD singly-linked list. +// An object with all zero fields should represent a valid empty list. clear() +// should be called on all non-zero-initialized objects before using. +template <class Item> struct IntrusiveList { + friend class Iterator; + + void clear() { + First = Last = nullptr; + Size = 0; + } + + bool empty() const { return Size == 0; } + uptr size() const { return Size; } + + void push_back(Item *X) { + if (empty()) { + X->Next = nullptr; + First = Last = X; + Size = 1; + } else { + X->Next = nullptr; + Last->Next = X; + Last = X; + Size++; + } + } + + void push_front(Item *X) { + if (empty()) { + X->Next = nullptr; + First = Last = X; + Size = 1; + } else { + X->Next = First; + First = X; + Size++; + } + } + + void pop_front() { + DCHECK(!empty()); + First = First->Next; + if (!First) + Last = nullptr; + Size--; + } + + void extract(Item *Prev, Item *X) { + DCHECK(!empty()); + DCHECK_NE(Prev, nullptr); + DCHECK_NE(X, nullptr); + DCHECK_EQ(Prev->Next, X); + Prev->Next = X->Next; + if (Last == X) + Last = Prev; + Size--; + } + + Item *front() { return First; } + const Item *front() const { return First; } + Item *back() { return Last; } + const Item *back() const { return Last; } + + void append_front(IntrusiveList<Item> *L) { + DCHECK_NE(this, L); + if (L->empty()) + return; + if (empty()) { + *this = *L; + } else if (!L->empty()) { + L->Last->Next = First; + First = L->First; + Size += L->size(); + } + L->clear(); + } + + void append_back(IntrusiveList<Item> *L) { + DCHECK_NE(this, L); + if (L->empty()) + return; + if (empty()) { + *this = *L; + } else { + Last->Next = L->First; + Last = L->Last; + Size += L->size(); + } + L->clear(); + } + + void checkConsistency() { + if (Size == 0) { + CHECK_EQ(First, 0); + CHECK_EQ(Last, 0); + } else { + uptr count = 0; + for (Item *I = First;; I = I->Next) { + count++; + if (I == Last) + break; + } + CHECK_EQ(size(), count); + CHECK_EQ(Last->Next, 0); + } + } + + template <class ItemT> class IteratorBase { + public: + explicit IteratorBase(ItemT *CurrentItem) : Current(CurrentItem) {} + IteratorBase &operator++() { + Current = Current->Next; + return *this; + } + bool operator!=(IteratorBase Other) const { + return Current != Other.Current; + } + ItemT &operator*() { return *Current; } + + private: + ItemT *Current; + }; + + typedef IteratorBase<Item> Iterator; + typedef IteratorBase<const Item> ConstIterator; + + Iterator begin() { return Iterator(First); } + Iterator end() { return Iterator(nullptr); } + + ConstIterator begin() const { return ConstIterator(First); } + ConstIterator end() const { return ConstIterator(nullptr); } + +private: + uptr Size; + Item *First; + Item *Last; +}; + +} // namespace scudo + +#endif // SCUDO_LIST_H_ diff --git a/lib/scudo/standalone/mutex.h b/lib/scudo/standalone/mutex.h new file mode 100644 index 000000000..6de3810b4 --- /dev/null +++ b/lib/scudo/standalone/mutex.h @@ -0,0 +1,108 @@ +//===-- mutex.h -------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_MUTEX_H_ +#define SCUDO_MUTEX_H_ + +#include "atomic_helpers.h" +#include "common.h" + +namespace scudo { + +class StaticSpinMutex { +public: + void init() { atomic_store_relaxed(&State, 0); } + + void lock() { + if (tryLock()) + return; + lockSlow(); + } + + bool tryLock() { + return atomic_exchange(&State, 1, memory_order_acquire) == 0; + } + + void unlock() { atomic_store(&State, 0, memory_order_release); } + + void checkLocked() { CHECK_EQ(atomic_load_relaxed(&State), 1); } + +private: + atomic_u8 State; + + void NOINLINE lockSlow() { + for (u32 I = 0;; I++) { + if (I < 10) + yieldProcessor(10); + else + yieldPlatform(); + if (atomic_load_relaxed(&State) == 0 && + atomic_exchange(&State, 1, memory_order_acquire) == 0) + return; + } + } +}; + +class SpinMutex : public StaticSpinMutex { +public: + SpinMutex() { init(); } + +private: + SpinMutex(const SpinMutex &) = delete; + void operator=(const SpinMutex &) = delete; +}; + +enum MutexState { MtxUnlocked = 0, MtxLocked = 1, MtxSleeping = 2 }; + +class BlockingMutex { +public: + explicit constexpr BlockingMutex(LinkerInitialized) : OpaqueStorage{0} {} + BlockingMutex() { memset(this, 0, sizeof(*this)); } + void wait(); + void wake(); + void lock() { + atomic_u32 *M = reinterpret_cast<atomic_u32 *>(&OpaqueStorage); + if (atomic_exchange(M, MtxLocked, memory_order_acquire) == MtxUnlocked) + return; + while (atomic_exchange(M, MtxSleeping, memory_order_acquire) != MtxUnlocked) + wait(); + } + void unlock() { + atomic_u32 *M = reinterpret_cast<atomic_u32 *>(&OpaqueStorage); + const u32 V = atomic_exchange(M, MtxUnlocked, memory_order_release); + DCHECK_NE(V, MtxUnlocked); + if (V == MtxSleeping) + wake(); + } + void checkLocked() { + atomic_u32 *M = reinterpret_cast<atomic_u32 *>(&OpaqueStorage); + CHECK_NE(MtxUnlocked, atomic_load_relaxed(M)); + } + +private: + uptr OpaqueStorage[1]; +}; + +template <typename MutexType> class GenericScopedLock { +public: + explicit GenericScopedLock(MutexType *M) : Mutex(M) { Mutex->lock(); } + ~GenericScopedLock() { Mutex->unlock(); } + +private: + MutexType *Mutex; + + GenericScopedLock(const GenericScopedLock &) = delete; + void operator=(const GenericScopedLock &) = delete; +}; + +typedef GenericScopedLock<StaticSpinMutex> SpinMutexLock; +typedef GenericScopedLock<BlockingMutex> BlockingMutexLock; + +} // namespace scudo + +#endif // SCUDO_MUTEX_H_ diff --git a/lib/scudo/standalone/platform.h b/lib/scudo/standalone/platform.h new file mode 100644 index 000000000..a897a566f --- /dev/null +++ b/lib/scudo/standalone/platform.h @@ -0,0 +1,70 @@ +//===-- platform.h ----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_PLATFORM_H_ +#define SCUDO_PLATFORM_H_ + +#if defined(__linux__) +#define SCUDO_LINUX 1 +#else +#define SCUDO_LINUX 0 +#endif + +#if defined(__ANDROID__) +#define SCUDO_ANDROID 1 +#else +#define SCUDO_ANDROID 0 +#endif + +#if defined(__Fuchsia__) +#define SCUDO_FUCHSIA 1 +#else +#define SCUDO_FUCHSIA 0 +#endif + +#if __LP64__ +#define SCUDO_WORDSIZE 64U +#else +#define SCUDO_WORDSIZE 32U +#endif + +#if SCUDO_WORDSIZE == 64U +#define FIRST_32_SECOND_64(a, b) (b) +#else +#define FIRST_32_SECOND_64(a, b) (a) +#endif + +#ifndef SCUDO_CAN_USE_PRIMARY64 +#define SCUDO_CAN_USE_PRIMARY64 (SCUDO_WORDSIZE == 64U) +#endif + +#ifndef SCUDO_MIN_ALIGNMENT_LOG +// We force malloc-type functions to be aligned to std::max_align_t, but there +// is no reason why the minimum alignment for all other functions can't be 8 +// bytes. Except obviously for applications making incorrect assumptions. +// TODO(kostyak): define SCUDO_MIN_ALIGNMENT_LOG 3 +#define SCUDO_MIN_ALIGNMENT_LOG FIRST_32_SECOND_64(3, 4) +#endif + +#if defined(__aarch64__) +#define SCUDO_MMAP_RANGE_SIZE FIRST_32_SECOND_64(1ULL << 32, 1ULL << 48) +#else +#define SCUDO_MMAP_RANGE_SIZE FIRST_32_SECOND_64(1ULL << 32, 1ULL << 47) +#endif + +// Older gcc have issues aligning to a constexpr, and require an integer. +// See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56859 among others. +#if defined(__powerpc__) || defined(__powerpc64__) +#define SCUDO_CACHE_LINE_SIZE 128 +#else +#define SCUDO_CACHE_LINE_SIZE 64 +#endif + +#define SCUDO_POINTER_FORMAT_LENGTH FIRST_32_SECOND_64(8, 12) + +#endif // SCUDO_PLATFORM_H_ diff --git a/lib/scudo/standalone/release.h b/lib/scudo/standalone/release.h new file mode 100644 index 000000000..4fe29fde4 --- /dev/null +++ b/lib/scudo/standalone/release.h @@ -0,0 +1,262 @@ +//===-- release.h -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_RELEASE_H_ +#define SCUDO_RELEASE_H_ + +#include "common.h" +#include "list.h" + +namespace scudo { + +class ReleaseRecorder { +public: + ReleaseRecorder(uptr BaseAddress, MapPlatformData *Data = nullptr) + : BaseAddress(BaseAddress), Data(Data) {} + + uptr getReleasedRangesCount() const { return ReleasedRangesCount; } + + uptr getReleasedBytes() const { return ReleasedBytes; } + + // Releases [From, To) range of pages back to OS. + void releasePageRangeToOS(uptr From, uptr To) { + const uptr Size = To - From; + releasePagesToOS(BaseAddress, From, Size, Data); + ReleasedRangesCount++; + ReleasedBytes += Size; + } + +private: + uptr ReleasedRangesCount = 0; + uptr ReleasedBytes = 0; + uptr BaseAddress = 0; + MapPlatformData *Data = nullptr; +}; + +// A packed array of Counters. Each counter occupies 2^N bits, enough to store +// counter's MaxValue. Ctor will try to allocate the required Buffer via map() +// and the caller is expected to check whether the initialization was successful +// by checking isAllocated() result. For the performance sake, none of the +// accessors check the validity of the arguments, It is assumed that Index is +// always in [0, N) range and the value is not incremented past MaxValue. +class PackedCounterArray { +public: + PackedCounterArray(uptr NumCounters, uptr MaxValue) : N(NumCounters) { + CHECK_GT(NumCounters, 0); + CHECK_GT(MaxValue, 0); + constexpr uptr MaxCounterBits = sizeof(*Buffer) * 8UL; + // Rounding counter storage size up to the power of two allows for using + // bit shifts calculating particular counter's Index and offset. + const uptr CounterSizeBits = + roundUpToPowerOfTwo(getMostSignificantSetBitIndex(MaxValue) + 1); + CHECK_LE(CounterSizeBits, MaxCounterBits); + CounterSizeBitsLog = getLog2(CounterSizeBits); + CounterMask = ~(static_cast<uptr>(0)) >> (MaxCounterBits - CounterSizeBits); + + const uptr PackingRatio = MaxCounterBits >> CounterSizeBitsLog; + CHECK_GT(PackingRatio, 0); + PackingRatioLog = getLog2(PackingRatio); + BitOffsetMask = PackingRatio - 1; + + BufferSize = (roundUpTo(N, static_cast<uptr>(1U) << PackingRatioLog) >> + PackingRatioLog) * + sizeof(*Buffer); + Buffer = reinterpret_cast<uptr *>( + map(nullptr, BufferSize, "scudo:counters", MAP_ALLOWNOMEM)); + } + ~PackedCounterArray() { + if (isAllocated()) + unmap(reinterpret_cast<void *>(Buffer), BufferSize); + } + + bool isAllocated() const { return !!Buffer; } + + uptr getCount() const { return N; } + + uptr get(uptr I) const { + DCHECK_LT(I, N); + const uptr Index = I >> PackingRatioLog; + const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog; + return (Buffer[Index] >> BitOffset) & CounterMask; + } + + void inc(uptr I) const { + DCHECK_LT(get(I), CounterMask); + const uptr Index = I >> PackingRatioLog; + const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog; + DCHECK_LT(BitOffset, SCUDO_WORDSIZE); + Buffer[Index] += static_cast<uptr>(1U) << BitOffset; + } + + void incRange(uptr From, uptr To) const { + DCHECK_LE(From, To); + for (uptr I = From; I <= To; I++) + inc(I); + } + + uptr getBufferSize() const { return BufferSize; } + +private: + const uptr N; + uptr CounterSizeBitsLog; + uptr CounterMask; + uptr PackingRatioLog; + uptr BitOffsetMask; + + uptr BufferSize; + uptr *Buffer; +}; + +template <class ReleaseRecorderT> class FreePagesRangeTracker { +public: + explicit FreePagesRangeTracker(ReleaseRecorderT *Recorder) + : Recorder(Recorder), PageSizeLog(getLog2(getPageSizeCached())) {} + + void processNextPage(bool Freed) { + if (Freed) { + if (!InRange) { + CurrentRangeStatePage = CurrentPage; + InRange = true; + } + } else { + closeOpenedRange(); + } + CurrentPage++; + } + + void finish() { closeOpenedRange(); } + +private: + void closeOpenedRange() { + if (InRange) { + Recorder->releasePageRangeToOS((CurrentRangeStatePage << PageSizeLog), + (CurrentPage << PageSizeLog)); + InRange = false; + } + } + + ReleaseRecorderT *const Recorder; + const uptr PageSizeLog; + bool InRange = false; + uptr CurrentPage = 0; + uptr CurrentRangeStatePage = 0; +}; + +template <class TransferBatchT, class ReleaseRecorderT> +NOINLINE void +releaseFreeMemoryToOS(const IntrusiveList<TransferBatchT> *FreeList, uptr Base, + uptr AllocatedPagesCount, uptr BlockSize, + ReleaseRecorderT *Recorder) { + const uptr PageSize = getPageSizeCached(); + + // Figure out the number of chunks per page and whether we can take a fast + // path (the number of chunks per page is the same for all pages). + uptr FullPagesBlockCountMax; + bool SameBlockCountPerPage; + if (BlockSize <= PageSize) { + if (PageSize % BlockSize == 0) { + // Same number of chunks per page, no cross overs. + FullPagesBlockCountMax = PageSize / BlockSize; + SameBlockCountPerPage = true; + } else if (BlockSize % (PageSize % BlockSize) == 0) { + // Some chunks are crossing page boundaries, which means that the page + // contains one or two partial chunks, but all pages contain the same + // number of chunks. + FullPagesBlockCountMax = PageSize / BlockSize + 1; + SameBlockCountPerPage = true; + } else { + // Some chunks are crossing page boundaries, which means that the page + // contains one or two partial chunks. + FullPagesBlockCountMax = PageSize / BlockSize + 2; + SameBlockCountPerPage = false; + } + } else { + if (BlockSize % PageSize == 0) { + // One chunk covers multiple pages, no cross overs. + FullPagesBlockCountMax = 1; + SameBlockCountPerPage = true; + } else { + // One chunk covers multiple pages, Some chunks are crossing page + // boundaries. Some pages contain one chunk, some contain two. + FullPagesBlockCountMax = 2; + SameBlockCountPerPage = false; + } + } + + PackedCounterArray Counters(AllocatedPagesCount, FullPagesBlockCountMax); + if (!Counters.isAllocated()) + return; + + const uptr PageSizeLog = getLog2(PageSize); + const uptr End = Base + AllocatedPagesCount * PageSize; + + // Iterate over free chunks and count how many free chunks affect each + // allocated page. + if (BlockSize <= PageSize && PageSize % BlockSize == 0) { + // Each chunk affects one page only. + for (auto It = FreeList->begin(); It != FreeList->end(); ++It) { + for (u32 I = 0; I < (*It).getCount(); I++) { + const uptr P = reinterpret_cast<uptr>((*It).get(I)); + if (P >= Base && P < End) + Counters.inc((P - Base) >> PageSizeLog); + } + } + } else { + // In all other cases chunks might affect more than one page. + for (auto It = FreeList->begin(); It != FreeList->end(); ++It) { + for (u32 I = 0; I < (*It).getCount(); I++) { + const uptr P = reinterpret_cast<uptr>((*It).get(I)); + if (P >= Base && P < End) + Counters.incRange((P - Base) >> PageSizeLog, + (P - Base + BlockSize - 1) >> PageSizeLog); + } + } + } + + // Iterate over pages detecting ranges of pages with chunk Counters equal + // to the expected number of chunks for the particular page. + FreePagesRangeTracker<ReleaseRecorderT> RangeTracker(Recorder); + if (SameBlockCountPerPage) { + // Fast path, every page has the same number of chunks affecting it. + for (uptr I = 0; I < Counters.getCount(); I++) + RangeTracker.processNextPage(Counters.get(I) == FullPagesBlockCountMax); + } else { + // Slow path, go through the pages keeping count how many chunks affect + // each page. + const uptr Pn = BlockSize < PageSize ? PageSize / BlockSize : 1; + const uptr Pnc = Pn * BlockSize; + // The idea is to increment the current page pointer by the first chunk + // size, middle portion size (the portion of the page covered by chunks + // except the first and the last one) and then the last chunk size, adding + // up the number of chunks on the current page and checking on every step + // whether the page boundary was crossed. + uptr PrevPageBoundary = 0; + uptr CurrentBoundary = 0; + for (uptr I = 0; I < Counters.getCount(); I++) { + const uptr PageBoundary = PrevPageBoundary + PageSize; + uptr BlocksPerPage = Pn; + if (CurrentBoundary < PageBoundary) { + if (CurrentBoundary > PrevPageBoundary) + BlocksPerPage++; + CurrentBoundary += Pnc; + if (CurrentBoundary < PageBoundary) { + BlocksPerPage++; + CurrentBoundary += BlockSize; + } + } + PrevPageBoundary = PageBoundary; + + RangeTracker.processNextPage(Counters.get(I) == BlocksPerPage); + } + } + RangeTracker.finish(); +} + +} // namespace scudo + +#endif // SCUDO_RELEASE_H_ diff --git a/lib/scudo/standalone/report.cc b/lib/scudo/standalone/report.cc new file mode 100644 index 000000000..2e453a10a --- /dev/null +++ b/lib/scudo/standalone/report.cc @@ -0,0 +1,192 @@ +//===-- report.cc -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "report.h" + +#include "atomic_helpers.h" +#include "string_utils.h" + +#include <stdarg.h> + +namespace scudo { + +class ScopedErrorReport { +public: + ScopedErrorReport() : Message(512) { Message.append("Scudo ERROR: "); } + void append(const char *Format, ...) { + va_list Args; + va_start(Args, Format); + Message.append(Format, Args); + va_end(Args); + } + NORETURN ~ScopedErrorReport() { + outputRaw(Message.data()); + setAbortMessage(Message.data()); + die(); + } + +private: + ScopedString Message; +}; + +INLINE void NORETURN trap() { __builtin_trap(); } + +// This could potentially be called recursively if a CHECK fails in the reports. +void NORETURN reportCheckFailed(const char *File, int Line, + const char *Condition, u64 Value1, u64 Value2) { + static atomic_u32 NumberOfCalls; + if (atomic_fetch_add(&NumberOfCalls, 1, memory_order_relaxed) > 2) { + // TODO(kostyak): maybe sleep here? + trap(); + } + ScopedErrorReport Report; + Report.append("CHECK failed @ %s:%d %s (%llu, %llu)\n", File, Line, Condition, + Value1, Value2); +} + +// Generic string fatal error message. +void NORETURN reportError(const char *Message) { + ScopedErrorReport Report; + Report.append("%s", Message); +} + +void NORETURN reportInvalidFlag(const char *FlagType, const char *Value) { + ScopedErrorReport Report; + Report.append("invalid value for %s option: '%s'\n", FlagType, Value); +} + +// The checksum of a chunk header is invalid. This could be caused by an +// {over,under}write of the header, a pointer that is not an actual chunk. +void NORETURN reportHeaderCorruption(void *Ptr) { + ScopedErrorReport Report; + Report.append("corrupted chunk header at address %p\n", Ptr); +} + +// Two threads have attempted to modify a chunk header at the same time. This is +// symptomatic of a race-condition in the application code, or general lack of +// proper locking. +void NORETURN reportHeaderRace(void *Ptr) { + ScopedErrorReport Report; + Report.append("race on chunk header at address %p\n", Ptr); +} + +// The allocator was compiled with parameters that conflict with field size +// requirements. +void NORETURN reportSanityCheckError(const char *Field) { + ScopedErrorReport Report; + Report.append("maximum possible %s doesn't fit in header\n", Field); +} + +// We enforce a maximum alignment, to keep fields smaller and generally prevent +// integer overflows, or unexpected corner cases. +void NORETURN reportAlignmentTooBig(uptr Alignment, uptr MaxAlignment) { + ScopedErrorReport Report; + Report.append("invalid allocation alignment: %zu exceeds maximum supported " + "alignment of %zu\n", + Alignment, MaxAlignment); +} + +// See above, we also enforce a maximum size. +void NORETURN reportAllocationSizeTooBig(uptr UserSize, uptr TotalSize, + uptr MaxSize) { + ScopedErrorReport Report; + Report.append("requested allocation size %zu (%zu after adjustments) exceeds " + "maximum supported size of %zu\n", + UserSize, TotalSize, MaxSize); +} + +void NORETURN reportOutOfMemory(uptr RequestedSize) { + ScopedErrorReport Report; + Report.append("out of memory trying to allocate %zu bytes\n", RequestedSize); +} + +static const char *stringifyAction(AllocatorAction Action) { + switch (Action) { + case AllocatorAction::Recycling: + return "recycling"; + case AllocatorAction::Deallocating: + return "deallocating"; + case AllocatorAction::Reallocating: + return "reallocating"; + case AllocatorAction::Sizing: + return "sizing"; + } + return "<invalid action>"; +} + +// The chunk is not in a state congruent with the operation we want to perform. +// This is usually the case with a double-free, a realloc of a freed pointer. +void NORETURN reportInvalidChunkState(AllocatorAction Action, void *Ptr) { + ScopedErrorReport Report; + Report.append("invalid chunk state when %s address %p\n", + stringifyAction(Action), Ptr); +} + +void NORETURN reportMisalignedPointer(AllocatorAction Action, void *Ptr) { + ScopedErrorReport Report; + Report.append("misaligned pointer when %s address %p\n", + stringifyAction(Action), Ptr); +} + +// The deallocation function used is at odds with the one used to allocate the +// chunk (eg: new[]/delete or malloc/delete, and so on). +void NORETURN reportDeallocTypeMismatch(AllocatorAction Action, void *Ptr, + u8 TypeA, u8 TypeB) { + ScopedErrorReport Report; + Report.append("allocation type mismatch when %s address %p (%d vs %d)\n", + stringifyAction(Action), Ptr, TypeA, TypeB); +} + +// The size specified to the delete operator does not match the one that was +// passed to new when allocating the chunk. +void NORETURN reportDeleteSizeMismatch(void *Ptr, uptr Size, + uptr ExpectedSize) { + ScopedErrorReport Report; + Report.append( + "invalid sized delete when deallocating address %p (%zu vs %zu)\n", Ptr, + Size, ExpectedSize); +} + +void NORETURN reportAlignmentNotPowerOfTwo(uptr Alignment) { + ScopedErrorReport Report; + Report.append( + "invalid allocation alignment: %zu, alignment must be a power of two\n", + Alignment); +} + +void NORETURN reportCallocOverflow(uptr Count, uptr Size) { + ScopedErrorReport Report; + Report.append("calloc parameters overflow: count * size (%zu * %zu) cannot " + "be represented with type size_t\n", + Count, Size); +} + +void NORETURN reportInvalidPosixMemalignAlignment(uptr Alignment) { + ScopedErrorReport Report; + Report.append( + "invalid alignment requested in posix_memalign: %zu, alignment must be a " + "power of two and a multiple of sizeof(void *) == %zu\n", + Alignment, sizeof(void *)); +} + +void NORETURN reportPvallocOverflow(uptr Size) { + ScopedErrorReport Report; + Report.append("pvalloc parameters overflow: size %zu rounded up to system " + "page size %zu cannot be represented in type size_t\n", + Size, getPageSizeCached()); +} + +void NORETURN reportInvalidAlignedAllocAlignment(uptr Alignment, uptr Size) { + ScopedErrorReport Report; + Report.append("invalid alignment requested in aligned_alloc: %zu, alignment " + "must be a power of two and the requested size %zu must be a " + "multiple of alignment\n", + Alignment, Size); +} + +} // namespace scudo diff --git a/lib/scudo/standalone/report.h b/lib/scudo/standalone/report.h new file mode 100644 index 000000000..14e4e799b --- /dev/null +++ b/lib/scudo/standalone/report.h @@ -0,0 +1,57 @@ +//===-- report.h ------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_REPORT_H_ +#define SCUDO_REPORT_H_ + +#include "internal_defs.h" + +namespace scudo { + +// Reports are *fatal* unless stated otherwise. + +// Generic error. +void NORETURN reportError(const char *Message); + +// Flags related errors. +void NORETURN reportInvalidFlag(const char *FlagType, const char *Value); + +// Chunk header related errors. +void NORETURN reportHeaderCorruption(void *Ptr); +void NORETURN reportHeaderRace(void *Ptr); + +// Sanity checks related error. +void NORETURN reportSanityCheckError(const char *Field); + +// Combined allocator errors. +void NORETURN reportAlignmentTooBig(uptr Alignment, uptr MaxAlignment); +void NORETURN reportAllocationSizeTooBig(uptr UserSize, uptr TotalSize, + uptr MaxSize); +void NORETURN reportOutOfMemory(uptr RequestedSize); +enum class AllocatorAction : u8 { + Recycling, + Deallocating, + Reallocating, + Sizing, +}; +void NORETURN reportInvalidChunkState(AllocatorAction Action, void *Ptr); +void NORETURN reportMisalignedPointer(AllocatorAction Action, void *Ptr); +void NORETURN reportDeallocTypeMismatch(AllocatorAction Action, void *Ptr, + u8 TypeA, u8 TypeB); +void NORETURN reportDeleteSizeMismatch(void *Ptr, uptr Size, uptr ExpectedSize); + +// C wrappers errors. +void NORETURN reportAlignmentNotPowerOfTwo(uptr Alignment); +void NORETURN reportInvalidPosixMemalignAlignment(uptr Alignment); +void NORETURN reportCallocOverflow(uptr Count, uptr Size); +void NORETURN reportPvallocOverflow(uptr Size); +void NORETURN reportInvalidAlignedAllocAlignment(uptr Size, uptr Alignment); + +} // namespace scudo + +#endif // SCUDO_REPORT_H_ diff --git a/lib/scudo/standalone/secondary.cc b/lib/scudo/standalone/secondary.cc new file mode 100644 index 000000000..c0de268be --- /dev/null +++ b/lib/scudo/standalone/secondary.cc @@ -0,0 +1,136 @@ +//===-- secondary.cc --------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "secondary.h" + +#include "string_utils.h" + +namespace scudo { + +// As with the Primary, the size passed to this function includes any desired +// alignment, so that the frontend can align the user allocation. The hint +// parameter allows us to unmap spurious memory when dealing with larger +// (greater than a page) alignments on 32-bit platforms. +// Due to the sparsity of address space available on those platforms, requesting +// an allocation from the Secondary with a large alignment would end up wasting +// VA space (even though we are not committing the whole thing), hence the need +// to trim off some of the reserved space. +// For allocations requested with an alignment greater than or equal to a page, +// the committed memory will amount to something close to Size - AlignmentHint +// (pending rounding and headers). +void *MapAllocator::allocate(uptr Size, uptr AlignmentHint, uptr *BlockEnd) { + DCHECK_GT(Size, AlignmentHint); + const uptr PageSize = getPageSizeCached(); + const uptr MapSize = + roundUpTo(Size + LargeBlock::getHeaderSize(), PageSize) + 2 * PageSize; + MapPlatformData Data = {}; + uptr MapBase = + reinterpret_cast<uptr>(map(nullptr, MapSize, "scudo:secondary", + MAP_NOACCESS | MAP_ALLOWNOMEM, &Data)); + if (!MapBase) + return nullptr; + uptr CommitBase = MapBase + PageSize; + uptr MapEnd = MapBase + MapSize; + + // In the unlikely event of alignments larger than a page, adjust the amount + // of memory we want to commit, and trim the extra memory. + if (AlignmentHint >= PageSize) { + // For alignments greater than or equal to a page, the user pointer (eg: the + // pointer that is returned by the C or C++ allocation APIs) ends up on a + // page boundary , and our headers will live in the preceding page. + CommitBase = roundUpTo(MapBase + PageSize + 1, AlignmentHint) - PageSize; + const uptr NewMapBase = CommitBase - PageSize; + DCHECK_GE(NewMapBase, MapBase); + // We only trim the extra memory on 32-bit platforms: 64-bit platforms + // are less constrained memory wise, and that saves us two syscalls. + if (SCUDO_WORDSIZE == 32U && NewMapBase != MapBase) { + unmap(reinterpret_cast<void *>(MapBase), NewMapBase - MapBase, 0, &Data); + MapBase = NewMapBase; + } + const uptr NewMapEnd = CommitBase + PageSize + + roundUpTo((Size - AlignmentHint), PageSize) + + PageSize; + DCHECK_LE(NewMapEnd, MapEnd); + if (SCUDO_WORDSIZE == 32U && NewMapEnd != MapEnd) { + unmap(reinterpret_cast<void *>(NewMapEnd), MapEnd - NewMapEnd, 0, &Data); + MapEnd = NewMapEnd; + } + } + + const uptr CommitSize = MapEnd - PageSize - CommitBase; + const uptr Ptr = + reinterpret_cast<uptr>(map(reinterpret_cast<void *>(CommitBase), + CommitSize, "scudo:secondary", 0, &Data)); + LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(Ptr); + H->MapBase = MapBase; + H->MapSize = MapEnd - MapBase; + H->BlockEnd = CommitBase + CommitSize; + H->Data = Data; + { + SpinMutexLock L(&Mutex); + if (!Tail) { + Tail = H; + } else { + Tail->Next = H; + H->Prev = Tail; + Tail = H; + } + AllocatedBytes += CommitSize; + if (LargestSize < CommitSize) + LargestSize = CommitSize; + NumberOfAllocs++; + Stats.add(StatAllocated, CommitSize); + Stats.add(StatMapped, H->MapSize); + } + if (BlockEnd) + *BlockEnd = CommitBase + CommitSize; + return reinterpret_cast<void *>(Ptr + LargeBlock::getHeaderSize()); +} + +void MapAllocator::deallocate(void *Ptr) { + LargeBlock::Header *H = LargeBlock::getHeader(Ptr); + { + SpinMutexLock L(&Mutex); + LargeBlock::Header *Prev = H->Prev; + LargeBlock::Header *Next = H->Next; + if (Prev) { + CHECK_EQ(Prev->Next, H); + Prev->Next = Next; + } + if (Next) { + CHECK_EQ(Next->Prev, H); + Next->Prev = Prev; + } + if (Tail == H) { + CHECK(!Next); + Tail = Prev; + } else { + CHECK(Next); + } + const uptr CommitSize = H->BlockEnd - reinterpret_cast<uptr>(H); + FreedBytes += CommitSize; + NumberOfFrees++; + Stats.sub(StatAllocated, CommitSize); + Stats.sub(StatMapped, H->MapSize); + } + void *Addr = reinterpret_cast<void *>(H->MapBase); + const uptr Size = H->MapSize; + MapPlatformData Data; + Data = H->Data; + unmap(Addr, Size, UNMAP_ALL, &Data); +} + +void MapAllocator::printStats() const { + Printf("Stats: MapAllocator: allocated %zd times (%zdK), freed %zd times " + "(%zdK), remains %zd (%zdK) max %zdM\n", + NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees, FreedBytes >> 10, + NumberOfAllocs - NumberOfFrees, (AllocatedBytes - FreedBytes) >> 10, + LargestSize >> 20); +} + +} // namespace scudo diff --git a/lib/scudo/standalone/secondary.h b/lib/scudo/standalone/secondary.h new file mode 100644 index 000000000..016928cc6 --- /dev/null +++ b/lib/scudo/standalone/secondary.h @@ -0,0 +1,97 @@ +//===-- secondary.h ---------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_SECONDARY_H_ +#define SCUDO_SECONDARY_H_ + +#include "common.h" +#include "mutex.h" +#include "stats.h" + +namespace scudo { + +// This allocator wraps the platform allocation primitives, and as such is on +// the slower side and should preferably be used for larger sized allocations. +// Blocks allocated will be preceded and followed by a guard page, and hold +// their own header that is not checksummed: the guard pages and the Combined +// header should be enough for our purpose. + +namespace LargeBlock { + +struct Header { + LargeBlock::Header *Prev; + LargeBlock::Header *Next; + uptr BlockEnd; + uptr MapBase; + uptr MapSize; + MapPlatformData Data; +}; + +constexpr uptr getHeaderSize() { + return roundUpTo(sizeof(Header), 1U << SCUDO_MIN_ALIGNMENT_LOG); +} + +static Header *getHeader(uptr Ptr) { + return reinterpret_cast<Header *>(Ptr - getHeaderSize()); +} + +static Header *getHeader(const void *Ptr) { + return getHeader(reinterpret_cast<uptr>(Ptr)); +} + +} // namespace LargeBlock + +class MapAllocator { +public: + void initLinkerInitialized(GlobalStats *S) { + Stats.initLinkerInitialized(); + if (S) + S->link(&Stats); + } + void init(GlobalStats *S) { + memset(this, 0, sizeof(*this)); + initLinkerInitialized(S); + } + + void *allocate(uptr Size, uptr AlignmentHint = 0, uptr *BlockEnd = nullptr); + + void deallocate(void *Ptr); + + static uptr getBlockEnd(void *Ptr) { + return LargeBlock::getHeader(Ptr)->BlockEnd; + } + + static uptr getBlockSize(void *Ptr) { + return getBlockEnd(Ptr) - reinterpret_cast<uptr>(Ptr); + } + + void printStats() const; + + void disable() { Mutex.lock(); } + + void enable() { Mutex.unlock(); } + + template <typename F> void iterateOverBlocks(F Callback) const { + for (LargeBlock::Header *H = Tail; H != nullptr; H = H->Prev) + Callback(reinterpret_cast<uptr>(H) + LargeBlock::getHeaderSize()); + } + +private: + StaticSpinMutex Mutex; + LargeBlock::Header *Tail; + uptr AllocatedBytes; + uptr FreedBytes; + uptr LargestSize; + u32 NumberOfAllocs; + u32 NumberOfFrees; + LocalStats Stats; +}; + +} // namespace scudo + +#endif // SCUDO_SECONDARY_H_ diff --git a/lib/scudo/standalone/size_class_map.h b/lib/scudo/standalone/size_class_map.h new file mode 100644 index 000000000..b7df54cf8 --- /dev/null +++ b/lib/scudo/standalone/size_class_map.h @@ -0,0 +1,149 @@ +//===-- size_class_map.h ----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_SIZE_CLASS_MAP_H_ +#define SCUDO_SIZE_CLASS_MAP_H_ + +#include "common.h" +#include "string_utils.h" + +namespace scudo { + +// SizeClassMap maps allocation sizes into size classes and back, in an +// efficient table-free manner. +// +// Class 0 is a special class that doesn't abide by the same rules as other +// classes. The allocator uses it to hold batches. +// +// The other sizes are controlled by the template parameters: +// - MinSizeLog: defines the first class as 2^MinSizeLog bytes. +// - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes. +// - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to +// 2^MidSizeLog bytes. +// - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog. +// eg. with NumBits==3 all size classes after 2^MidSizeLog look like +// 0b1xx0..0 (where x is either 0 or 1). +// +// This class also gives a hint to a thread-caching allocator about the amount +// of chunks that can be cached per-thread: +// - MaxNumCachedHint is a hint for the max number of chunks cached per class. +// - 2^MaxBytesCachedLog is the max number of bytes cached per class. + +template <u8 NumBits, u8 MinSizeLog, u8 MidSizeLog, u8 MaxSizeLog, + u32 MaxNumCachedHintT, u8 MaxBytesCachedLog> +class SizeClassMap { + static const uptr MinSize = 1UL << MinSizeLog; + static const uptr MidSize = 1UL << MidSizeLog; + static const uptr MidClass = MidSize / MinSize; + static const u8 S = NumBits - 1; + static const uptr M = (1UL << S) - 1; + +public: + static const u32 MaxNumCachedHint = MaxNumCachedHintT; + + static const uptr MaxSize = 1UL << MaxSizeLog; + static const uptr NumClasses = + MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1; + COMPILER_CHECK(NumClasses <= 256); + static const uptr LargestClassId = NumClasses - 1; + static const uptr BatchClassId = 0; + + static uptr getSizeByClassId(uptr ClassId) { + DCHECK_NE(ClassId, BatchClassId); + if (ClassId <= MidClass) + return ClassId << MinSizeLog; + ClassId -= MidClass; + const uptr T = MidSize << (ClassId >> S); + return T + (T >> S) * (ClassId & M); + } + + static uptr getClassIdBySize(uptr Size) { + DCHECK_LE(Size, MaxSize); + if (Size <= MidSize) + return (Size + MinSize - 1) >> MinSizeLog; + const uptr L = getMostSignificantSetBitIndex(Size); + const uptr HBits = (Size >> (L - S)) & M; + const uptr LBits = Size & ((1UL << (L - S)) - 1); + const uptr L1 = L - MidSizeLog; + return MidClass + (L1 << S) + HBits + (LBits > 0); + } + + static u32 getMaxCachedHint(uptr Size) { + DCHECK_LE(Size, MaxSize); + DCHECK_NE(Size, 0); + u32 N; + // Force a 32-bit division if the template parameters allow for it. + if (MaxBytesCachedLog > 31 || MaxSizeLog > 31) + N = static_cast<u32>((1UL << MaxBytesCachedLog) / Size); + else + N = (1U << MaxBytesCachedLog) / static_cast<u32>(Size); + return Max(1U, Min(MaxNumCachedHint, N)); + } + + static void print() { + uptr PrevS = 0; + uptr TotalCached = 0; + for (uptr I = 0; I < NumClasses; I++) { + if (I == BatchClassId) + continue; + const uptr S = getSizeByClassId(I); + if (S >= MidSize / 2 && (S & (S - 1)) == 0) + Printf("\n"); + const uptr D = S - PrevS; + const uptr P = PrevS ? (D * 100 / PrevS) : 0; + const uptr L = S ? getMostSignificantSetBitIndex(S) : 0; + const uptr Cached = getMaxCachedHint(S) * S; + Printf( + "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n", + I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached, + getClassIdBySize(S)); + TotalCached += Cached; + PrevS = S; + } + Printf("Total Cached: %zu\n", TotalCached); + } + + static void validate() { + for (uptr C = 0; C < NumClasses; C++) { + if (C == BatchClassId) + continue; + const uptr S = getSizeByClassId(C); + CHECK_NE(S, 0U); + CHECK_EQ(getClassIdBySize(S), C); + if (C < LargestClassId) + CHECK_EQ(getClassIdBySize(S + 1), C + 1); + CHECK_EQ(getClassIdBySize(S - 1), C); + CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1)); + } + // Do not perform the loop if the maximum size is too large. + if (MaxSizeLog > 19) + return; + for (uptr S = 1; S <= MaxSize; S++) { + const uptr C = getClassIdBySize(S); + CHECK_LT(C, NumClasses); + CHECK_GE(getSizeByClassId(C), S); + if (C > 0) + CHECK_LT(getSizeByClassId(C - 1), S); + } + } +}; + +typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap; + +// TODO(kostyak): further tune class maps for Android & Fuchsia. +#if SCUDO_WORDSIZE == 64U +typedef SizeClassMap<3, 5, 8, 15, 8, 10> SvelteSizeClassMap; +typedef SizeClassMap<3, 5, 8, 16, 14, 12> AndroidSizeClassMap; +#else +typedef SizeClassMap<3, 4, 7, 15, 8, 10> SvelteSizeClassMap; +typedef SizeClassMap<3, 4, 7, 16, 14, 12> AndroidSizeClassMap; +#endif + +} // namespace scudo + +#endif // SCUDO_SIZE_CLASS_MAP_H_ diff --git a/lib/scudo/standalone/stats.h b/lib/scudo/standalone/stats.h new file mode 100644 index 000000000..7fb9c9ed6 --- /dev/null +++ b/lib/scudo/standalone/stats.h @@ -0,0 +1,105 @@ +//===-- stats.h -------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_STATS_H_ +#define SCUDO_STATS_H_ + +#include "atomic_helpers.h" +#include "mutex.h" + +#include <string.h> + +namespace scudo { + +// Memory allocator statistics +enum StatType { StatAllocated, StatMapped, StatCount }; + +typedef uptr StatCounters[StatCount]; + +// Per-thread stats, live in per-thread cache. We use atomics so that the +// numbers themselves are consistent. But we don't use atomic_{add|sub} or a +// lock, because those are expensive operations , and we only care for the stats +// to be "somewhat" correct: eg. if we call GlobalStats::get while a thread is +// LocalStats::add'ing, this is OK, we will still get a meaningful number. +class LocalStats { +public: + void initLinkerInitialized() {} + void init() { memset(this, 0, sizeof(*this)); } + + void add(StatType I, uptr V) { + V += atomic_load_relaxed(&StatsArray[I]); + atomic_store_relaxed(&StatsArray[I], V); + } + + void sub(StatType I, uptr V) { + V = atomic_load_relaxed(&StatsArray[I]) - V; + atomic_store_relaxed(&StatsArray[I], V); + } + + void set(StatType I, uptr V) { atomic_store_relaxed(&StatsArray[I], V); } + + uptr get(StatType I) const { return atomic_load_relaxed(&StatsArray[I]); } + +private: + friend class GlobalStats; + atomic_uptr StatsArray[StatCount]; + LocalStats *Next; + LocalStats *Prev; +}; + +// Global stats, used for aggregation and querying. +class GlobalStats : public LocalStats { +public: + void initLinkerInitialized() { + Next = this; + Prev = this; + } + void init() { + memset(this, 0, sizeof(*this)); + initLinkerInitialized(); + } + + void link(LocalStats *S) { + SpinMutexLock L(&Mutex); + S->Next = Next; + S->Prev = this; + Next->Prev = S; + Next = S; + } + + void unlink(LocalStats *S) { + SpinMutexLock L(&Mutex); + S->Prev->Next = S->Next; + S->Next->Prev = S->Prev; + for (uptr I = 0; I < StatCount; I++) + add(static_cast<StatType>(I), S->get(static_cast<StatType>(I))); + } + + void get(uptr *S) const { + memset(S, 0, StatCount * sizeof(uptr)); + SpinMutexLock L(&Mutex); + const LocalStats *Stats = this; + for (;;) { + for (uptr I = 0; I < StatCount; I++) + S[I] += Stats->get(static_cast<StatType>(I)); + Stats = Stats->Next; + if (Stats == this) + break; + } + // All stats must be non-negative. + for (uptr I = 0; I < StatCount; I++) + S[I] = static_cast<sptr>(S[I]) >= 0 ? S[I] : 0; + } + +private: + mutable StaticSpinMutex Mutex; +}; + +} // namespace scudo + +#endif // SCUDO_STATS_H_ diff --git a/lib/scudo/standalone/string_utils.cc b/lib/scudo/standalone/string_utils.cc new file mode 100644 index 000000000..f0068afc1 --- /dev/null +++ b/lib/scudo/standalone/string_utils.cc @@ -0,0 +1,236 @@ +//===-- string_utils.cc -----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "string_utils.h" +#include "common.h" + +#include <ctype.h> +#include <stdarg.h> +#include <string.h> + +namespace scudo { + +static int appendChar(char **Buffer, const char *BufferEnd, char C) { + if (*Buffer < BufferEnd) { + **Buffer = C; + (*Buffer)++; + } + return 1; +} + +// Appends number in a given Base to buffer. If its length is less than +// |MinNumberLength|, it is padded with leading zeroes or spaces, depending +// on the value of |PadWithZero|. +static int appendNumber(char **Buffer, const char *BufferEnd, u64 AbsoluteValue, + u8 Base, u8 MinNumberLength, bool PadWithZero, + bool Negative, bool Upper) { + constexpr uptr MaxLen = 30; + RAW_CHECK(Base == 10 || Base == 16); + RAW_CHECK(Base == 10 || !Negative); + RAW_CHECK(AbsoluteValue || !Negative); + RAW_CHECK(MinNumberLength < MaxLen); + int Res = 0; + if (Negative && MinNumberLength) + --MinNumberLength; + if (Negative && PadWithZero) + Res += appendChar(Buffer, BufferEnd, '-'); + uptr NumBuffer[MaxLen]; + int Pos = 0; + do { + RAW_CHECK_MSG(static_cast<uptr>(Pos) < MaxLen, + "appendNumber buffer overflow"); + NumBuffer[Pos++] = AbsoluteValue % Base; + AbsoluteValue /= Base; + } while (AbsoluteValue > 0); + if (Pos < MinNumberLength) { + memset(&NumBuffer[Pos], 0, + sizeof(NumBuffer[0]) * static_cast<uptr>(MinNumberLength - Pos)); + Pos = MinNumberLength; + } + RAW_CHECK(Pos > 0); + Pos--; + for (; Pos >= 0 && NumBuffer[Pos] == 0; Pos--) { + char c = (PadWithZero || Pos == 0) ? '0' : ' '; + Res += appendChar(Buffer, BufferEnd, c); + } + if (Negative && !PadWithZero) + Res += appendChar(Buffer, BufferEnd, '-'); + for (; Pos >= 0; Pos--) { + char Digit = static_cast<char>(NumBuffer[Pos]); + Digit = static_cast<char>((Digit < 10) ? '0' + Digit + : (Upper ? 'A' : 'a') + Digit - 10); + Res += appendChar(Buffer, BufferEnd, Digit); + } + return Res; +} + +static int appendUnsigned(char **Buffer, const char *BufferEnd, u64 Num, + u8 Base, u8 MinNumberLength, bool PadWithZero, + bool Upper) { + return appendNumber(Buffer, BufferEnd, Num, Base, MinNumberLength, + PadWithZero, /*Negative=*/false, Upper); +} + +static int appendSignedDecimal(char **Buffer, const char *BufferEnd, s64 Num, + u8 MinNumberLength, bool PadWithZero) { + const bool Negative = (Num < 0); + return appendNumber(Buffer, BufferEnd, + static_cast<u64>(Negative ? -Num : Num), 10, + MinNumberLength, PadWithZero, Negative, + /*Upper=*/false); +} + +// Use the fact that explicitly requesting 0 Width (%0s) results in UB and +// interpret Width == 0 as "no Width requested": +// Width == 0 - no Width requested +// Width < 0 - left-justify S within and pad it to -Width chars, if necessary +// Width > 0 - right-justify S, not implemented yet +static int appendString(char **Buffer, const char *BufferEnd, int Width, + int MaxChars, const char *S) { + if (!S) + S = "<null>"; + int Res = 0; + for (; *S; S++) { + if (MaxChars >= 0 && Res >= MaxChars) + break; + Res += appendChar(Buffer, BufferEnd, *S); + } + // Only the left justified strings are supported. + while (Width < -Res) + Res += appendChar(Buffer, BufferEnd, ' '); + return Res; +} + +static int appendPointer(char **Buffer, const char *BufferEnd, u64 ptr_value) { + int Res = 0; + Res += appendString(Buffer, BufferEnd, 0, -1, "0x"); + Res += appendUnsigned(Buffer, BufferEnd, ptr_value, 16, + SCUDO_POINTER_FORMAT_LENGTH, /*PadWithZero=*/true, + /*Upper=*/false); + return Res; +} + +int formatString(char *Buffer, uptr BufferLength, const char *Format, + va_list Args) { + UNUSED static const char *PrintfFormatsHelp = + "Supported formatString formats: %([0-9]*)?(z|ll)?{d,u,x,X}; %p; " + "%[-]([0-9]*)?(\\.\\*)?s; %c\n"; + RAW_CHECK(Format); + RAW_CHECK(BufferLength > 0); + const char *BufferEnd = &Buffer[BufferLength - 1]; + const char *Cur = Format; + int Res = 0; + for (; *Cur; Cur++) { + if (*Cur != '%') { + Res += appendChar(&Buffer, BufferEnd, *Cur); + continue; + } + Cur++; + const bool LeftJustified = *Cur == '-'; + if (LeftJustified) + Cur++; + bool HaveWidth = (*Cur >= '0' && *Cur <= '9'); + const bool PadWithZero = (*Cur == '0'); + u8 Width = 0; + if (HaveWidth) { + while (*Cur >= '0' && *Cur <= '9') + Width = static_cast<u8>(Width * 10 + *Cur++ - '0'); + } + const bool HavePrecision = (Cur[0] == '.' && Cur[1] == '*'); + int Precision = -1; + if (HavePrecision) { + Cur += 2; + Precision = va_arg(Args, int); + } + const bool HaveZ = (*Cur == 'z'); + Cur += HaveZ; + const bool HaveLL = !HaveZ && (Cur[0] == 'l' && Cur[1] == 'l'); + Cur += HaveLL * 2; + s64 DVal; + u64 UVal; + const bool HaveLength = HaveZ || HaveLL; + const bool HaveFlags = HaveWidth || HaveLength; + // At the moment only %s supports precision and left-justification. + CHECK(!((Precision >= 0 || LeftJustified) && *Cur != 's')); + switch (*Cur) { + case 'd': { + DVal = HaveLL ? va_arg(Args, s64) + : HaveZ ? va_arg(Args, sptr) : va_arg(Args, int); + Res += appendSignedDecimal(&Buffer, BufferEnd, DVal, Width, PadWithZero); + break; + } + case 'u': + case 'x': + case 'X': { + UVal = HaveLL ? va_arg(Args, u64) + : HaveZ ? va_arg(Args, uptr) : va_arg(Args, unsigned); + const bool Upper = (*Cur == 'X'); + Res += appendUnsigned(&Buffer, BufferEnd, UVal, (*Cur == 'u') ? 10 : 16, + Width, PadWithZero, Upper); + break; + } + case 'p': { + RAW_CHECK_MSG(!HaveFlags, PrintfFormatsHelp); + Res += appendPointer(&Buffer, BufferEnd, va_arg(Args, uptr)); + break; + } + case 's': { + RAW_CHECK_MSG(!HaveLength, PrintfFormatsHelp); + // Only left-justified Width is supported. + CHECK(!HaveWidth || LeftJustified); + Res += appendString(&Buffer, BufferEnd, LeftJustified ? -Width : Width, + Precision, va_arg(Args, char *)); + break; + } + case 'c': { + RAW_CHECK_MSG(!HaveFlags, PrintfFormatsHelp); + Res += + appendChar(&Buffer, BufferEnd, static_cast<char>(va_arg(Args, int))); + break; + } + case '%': { + RAW_CHECK_MSG(!HaveFlags, PrintfFormatsHelp); + Res += appendChar(&Buffer, BufferEnd, '%'); + break; + } + default: { + RAW_CHECK_MSG(false, PrintfFormatsHelp); + } + } + } + RAW_CHECK(Buffer <= BufferEnd); + appendChar(&Buffer, BufferEnd + 1, '\0'); + return Res; +} + +void ScopedString::append(const char *Format, va_list Args) { + CHECK_LT(Length, String.size()); + formatString(String.data() + Length, String.size() - Length, Format, Args); + Length += strlen(String.data() + Length); + CHECK_LT(Length, String.size()); +} + +FORMAT(2, 3) +void ScopedString::append(const char *Format, ...) { + va_list Args; + va_start(Args, Format); + append(Format, Args); + va_end(Args); +} + +FORMAT(1, 2) +void Printf(const char *Format, ...) { + va_list Args; + va_start(Args, Format); + ScopedString Msg(512); + Msg.append(Format, Args); + outputRaw(Msg.data()); + va_end(Args); +} + +} // namespace scudo diff --git a/lib/scudo/standalone/string_utils.h b/lib/scudo/standalone/string_utils.h new file mode 100644 index 000000000..aea7b3ffd --- /dev/null +++ b/lib/scudo/standalone/string_utils.h @@ -0,0 +1,42 @@ +//===-- string_utils.h ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_STRING_UTILS_H_ +#define SCUDO_STRING_UTILS_H_ + +#include "internal_defs.h" +#include "vector.h" + +#include <stdarg.h> + +namespace scudo { + +class ScopedString { +public: + explicit ScopedString(uptr MaxLength) : String(MaxLength), Length(0) { + String[0] = '\0'; + } + uptr length() { return Length; } + const char *data() { return String.data(); } + void clear() { + String[0] = '\0'; + Length = 0; + } + void append(const char *Format, va_list Args); + void append(const char *Format, ...); + +private: + Vector<char> String; + uptr Length; +}; + +void Printf(const char *Format, ...); + +} // namespace scudo + +#endif // SCUDO_STRING_UTILS_H_ diff --git a/lib/scudo/standalone/tests/CMakeLists.txt b/lib/scudo/standalone/tests/CMakeLists.txt new file mode 100644 index 000000000..182d6a26a --- /dev/null +++ b/lib/scudo/standalone/tests/CMakeLists.txt @@ -0,0 +1,69 @@ +include_directories(..) + +add_custom_target(ScudoUnitTests) +set_target_properties(ScudoUnitTests PROPERTIES + FOLDER "Compiler-RT Tests") + +set(SCUDO_UNITTEST_CFLAGS + ${COMPILER_RT_UNITTEST_CFLAGS} + ${COMPILER_RT_GTEST_CFLAGS} + -I${COMPILER_RT_SOURCE_DIR}/include + -I${COMPILER_RT_SOURCE_DIR}/lib + -I${COMPILER_RT_SOURCE_DIR}/lib/scudo/standalone + -DGTEST_HAS_RTTI=0) + +set(SCUDO_TEST_ARCH ${SCUDO_STANDALONE_SUPPORTED_ARCH}) + +# gtests requires c++ +set(LINK_FLAGS ${COMPILER_RT_UNITTEST_LINK_FLAGS}) +foreach(lib ${SANITIZER_TEST_CXX_LIBRARIES}) + list(APPEND LINK_FLAGS -l${lib}) +endforeach() +list(APPEND LINK_FLAGS -pthread) + +set(TEST_HEADERS) +foreach (header ${SCUDO_HEADERS}) + list(APPEND TEST_HEADERS ${CMAKE_CURRENT_SOURCE_DIR}/../${header}) +endforeach() + +# add_scudo_unittest(<name> +# SOURCES <sources list> +# HEADERS <extra headers list>) +macro(add_scudo_unittest testname) + cmake_parse_arguments(TEST "" "" "SOURCES;HEADERS" ${ARGN}) + if(COMPILER_RT_HAS_SCUDO_STANDALONE) + foreach(arch ${SCUDO_TEST_ARCH}) + set(ScudoUnitTestsObjects) + add_library("RTScudoStandalone.test.${arch}" STATIC + $<TARGET_OBJECTS:RTScudoStandalone.${arch}>) + generate_compiler_rt_tests(ScudoUnitTestsObjects ScudoUnitTests + "${testname}-${arch}-Test" ${arch} + SOURCES ${TEST_SOURCES} ${COMPILER_RT_GTEST_SOURCE} + COMPILE_DEPS ${TEST_HEADERS} + DEPS gtest scudo_standalone + RUNTIME RTScudoStandalone.test.${arch} + CFLAGS ${SCUDO_UNITTEST_CFLAGS} + LINK_FLAGS ${LINK_FLAGS}) + endforeach() + endif() +endmacro() + +set(SCUDO_UNIT_TEST_SOURCES + atomic_test.cc + bytemap_test.cc + checksum_test.cc + flags_test.cc + list_test.cc + map_test.cc + mutex_test.cc + release_test.cc + report_test.cc + secondary_test.cc + size_class_map_test.cc + stats_test.cc + strings_test.cc + vector_test.cc + scudo_unit_test_main.cc) + +add_scudo_unittest(ScudoUnitTest + SOURCES ${SCUDO_UNIT_TEST_SOURCES}) diff --git a/lib/scudo/standalone/tests/atomic_test.cc b/lib/scudo/standalone/tests/atomic_test.cc new file mode 100644 index 000000000..3095451b9 --- /dev/null +++ b/lib/scudo/standalone/tests/atomic_test.cc @@ -0,0 +1,112 @@ +//===-- atomic_test.cc ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/atomic_helpers.h" +#include "gtest/gtest.h" + +namespace scudo { + +template <typename T> struct ValAndMagic { + typename T::Type Magic0; + T A; + typename T::Type Magic1; + + static ValAndMagic<T> *Sink; +}; + +template <typename T> ValAndMagic<T> *ValAndMagic<T>::Sink; + +template <typename T, memory_order LoadMO, memory_order StoreMO> +void checkStoreLoad() { + typedef typename T::Type Type; + ValAndMagic<T> Val; + // Prevent the compiler from scalarizing the struct. + ValAndMagic<T>::Sink = &Val; + // Ensure that surrounding memory is not overwritten. + Val.Magic0 = Val.Magic1 = (Type)-3; + for (u64 I = 0; I < 100; I++) { + // Generate A value that occupies all bytes of the variable. + u64 V = I; + V |= V << 8; + V |= V << 16; + V |= V << 32; + Val.A.ValDoNotUse = (Type)V; + EXPECT_EQ(atomic_load(&Val.A, LoadMO), (Type)V); + Val.A.ValDoNotUse = (Type)-1; + atomic_store(&Val.A, (Type)V, StoreMO); + EXPECT_EQ(Val.A.ValDoNotUse, (Type)V); + } + EXPECT_EQ(Val.Magic0, (Type)-3); + EXPECT_EQ(Val.Magic1, (Type)-3); +} + +TEST(ScudoAtomicTest, AtomicStoreLoad) { + checkStoreLoad<atomic_u8, memory_order_relaxed, memory_order_relaxed>(); + checkStoreLoad<atomic_u8, memory_order_consume, memory_order_relaxed>(); + checkStoreLoad<atomic_u8, memory_order_acquire, memory_order_relaxed>(); + checkStoreLoad<atomic_u8, memory_order_relaxed, memory_order_release>(); + checkStoreLoad<atomic_u8, memory_order_seq_cst, memory_order_seq_cst>(); + + checkStoreLoad<atomic_u16, memory_order_relaxed, memory_order_relaxed>(); + checkStoreLoad<atomic_u16, memory_order_consume, memory_order_relaxed>(); + checkStoreLoad<atomic_u16, memory_order_acquire, memory_order_relaxed>(); + checkStoreLoad<atomic_u16, memory_order_relaxed, memory_order_release>(); + checkStoreLoad<atomic_u16, memory_order_seq_cst, memory_order_seq_cst>(); + + checkStoreLoad<atomic_u32, memory_order_relaxed, memory_order_relaxed>(); + checkStoreLoad<atomic_u32, memory_order_consume, memory_order_relaxed>(); + checkStoreLoad<atomic_u32, memory_order_acquire, memory_order_relaxed>(); + checkStoreLoad<atomic_u32, memory_order_relaxed, memory_order_release>(); + checkStoreLoad<atomic_u32, memory_order_seq_cst, memory_order_seq_cst>(); + + checkStoreLoad<atomic_u64, memory_order_relaxed, memory_order_relaxed>(); + checkStoreLoad<atomic_u64, memory_order_consume, memory_order_relaxed>(); + checkStoreLoad<atomic_u64, memory_order_acquire, memory_order_relaxed>(); + checkStoreLoad<atomic_u64, memory_order_relaxed, memory_order_release>(); + checkStoreLoad<atomic_u64, memory_order_seq_cst, memory_order_seq_cst>(); + + checkStoreLoad<atomic_uptr, memory_order_relaxed, memory_order_relaxed>(); + checkStoreLoad<atomic_uptr, memory_order_consume, memory_order_relaxed>(); + checkStoreLoad<atomic_uptr, memory_order_acquire, memory_order_relaxed>(); + checkStoreLoad<atomic_uptr, memory_order_relaxed, memory_order_release>(); + checkStoreLoad<atomic_uptr, memory_order_seq_cst, memory_order_seq_cst>(); +} + +template <typename T> void checkAtomicCompareExchange() { + typedef typename T::Type Type; + { + Type OldVal = 42; + Type NewVal = 24; + Type V = OldVal; + EXPECT_TRUE(atomic_compare_exchange_strong( + reinterpret_cast<T *>(&V), &OldVal, NewVal, memory_order_relaxed)); + EXPECT_FALSE(atomic_compare_exchange_strong( + reinterpret_cast<T *>(&V), &OldVal, NewVal, memory_order_relaxed)); + EXPECT_EQ(NewVal, OldVal); + } + { + Type OldVal = 42; + Type NewVal = 24; + Type V = OldVal; + EXPECT_TRUE(atomic_compare_exchange_weak(reinterpret_cast<T *>(&V), &OldVal, + NewVal, memory_order_relaxed)); + EXPECT_FALSE(atomic_compare_exchange_weak( + reinterpret_cast<T *>(&V), &OldVal, NewVal, memory_order_relaxed)); + EXPECT_EQ(NewVal, OldVal); + } +} + +TEST(ScudoAtomicTest, AtomicCompareExchangeTest) { + checkAtomicCompareExchange<atomic_u8>(); + checkAtomicCompareExchange<atomic_u16>(); + checkAtomicCompareExchange<atomic_u32>(); + checkAtomicCompareExchange<atomic_u64>(); + checkAtomicCompareExchange<atomic_uptr>(); +} + +} // namespace scudo diff --git a/lib/scudo/standalone/tests/bytemap_test.cc b/lib/scudo/standalone/tests/bytemap_test.cc new file mode 100644 index 000000000..615b946c5 --- /dev/null +++ b/lib/scudo/standalone/tests/bytemap_test.cc @@ -0,0 +1,73 @@ +//===-- bytemap_test.cc -----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "bytemap.h" + +#include "gtest/gtest.h" + +#include <string.h> + +template <typename T> void testMap(T &Map, scudo::uptr Size) { + Map.init(); + for (scudo::uptr I = 0; I < Size; I += 7) + Map.set(I, (I % 100) + 1); + for (scudo::uptr J = 0; J < Size; J++) { + if (J % 7) + EXPECT_EQ(Map[J], 0); + else + EXPECT_EQ(Map[J], (J % 100) + 1); + } +} + +TEST(ScudoByteMapTest, FlatByteMap) { + const scudo::uptr Size = 1U << 10; + scudo::FlatByteMap<Size> Map; + testMap(Map, Size); +} + +TEST(ScudoByteMapTest, TwoLevelByteMap) { + const scudo::uptr Size1 = 1U << 6, Size2 = 1U << 12; + scudo::TwoLevelByteMap<Size1, Size2> Map; + testMap(Map, Size1 * Size2); + Map.reset(); +} + +using TestByteMap = scudo::TwoLevelByteMap<1U << 12, 1U << 13>; + +struct TestByteMapParam { + TestByteMap *Map; + scudo::uptr Shard; + scudo::uptr NumberOfShards; +}; + +void *populateByteMap(void *Param) { + TestByteMapParam *P = reinterpret_cast<TestByteMapParam *>(Param); + for (scudo::uptr I = P->Shard; I < P->Map->size(); I += P->NumberOfShards) { + scudo::u8 V = static_cast<scudo::u8>((I % 100) + 1); + P->Map->set(I, V); + EXPECT_EQ((*P->Map)[I], V); + } + return 0; +} + +TEST(ScudoByteMapTest, ThreadedTwoLevelByteMap) { + TestByteMap Map; + Map.init(); + static const scudo::uptr NumberOfThreads = 16U; + pthread_t T[NumberOfThreads]; + TestByteMapParam P[NumberOfThreads]; + for (scudo::uptr I = 0; I < NumberOfThreads; I++) { + P[I].Map = ⤅ + P[I].Shard = I; + P[I].NumberOfShards = NumberOfThreads; + pthread_create(&T[I], 0, populateByteMap, &P[I]); + } + for (scudo::uptr I = 0; I < NumberOfThreads; I++) + pthread_join(T[I], 0); + Map.reset(); +} diff --git a/lib/scudo/standalone/tests/checksum_test.cc b/lib/scudo/standalone/tests/checksum_test.cc new file mode 100644 index 000000000..2e8dc8a7b --- /dev/null +++ b/lib/scudo/standalone/tests/checksum_test.cc @@ -0,0 +1,58 @@ +//===-- checksum_test.cc ----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "checksum.h" + +#include "gtest/gtest.h" + +#include <string.h> + +scudo::u16 computeSoftwareChecksum(scudo::u32 Seed, scudo::uptr *Array, + scudo::uptr ArraySize) { + scudo::u16 Checksum = static_cast<scudo::u16>(Seed & 0xffff); + for (scudo::uptr I = 0; I < ArraySize; I++) + Checksum = scudo::computeBSDChecksum(Checksum, Array[I]); + return Checksum; +} + +scudo::u16 computeHardwareChecksum(scudo::u32 Seed, scudo::uptr *Array, + scudo::uptr ArraySize) { + scudo::u32 Crc = Seed; + for (scudo::uptr I = 0; I < ArraySize; I++) + Crc = scudo::computeHardwareCRC32(Crc, Array[I]); + return static_cast<scudo::u16>((Crc & 0xffff) ^ (Crc >> 16)); +} + +typedef scudo::u16 (*ComputeChecksum)(scudo::u32, scudo::uptr *, scudo::uptr); + +// This verifies that flipping bits in the data being checksummed produces a +// different checksum. We do not use random data to avoid flakyness. +template <ComputeChecksum F> void verifyChecksumFunctionBitFlip() { + scudo::uptr Array[sizeof(scudo::u64) / sizeof(scudo::uptr)]; + const scudo::uptr ArraySize = ARRAY_SIZE(Array); + memset(Array, 0xaa, sizeof(Array)); + const scudo::u32 Seed = 0x41424343U; + const scudo::u16 Reference = F(Seed, Array, ArraySize); + scudo::u8 IdenticalChecksums = 0; + for (scudo::uptr I = 0; I < ArraySize; I++) { + for (scudo::uptr J = 0; J < SCUDO_WORDSIZE; J++) { + Array[I] ^= 1U << J; + if (F(Seed, Array, ArraySize) == Reference) + IdenticalChecksums++; + Array[I] ^= 1U << J; + } + } + // Allow for a couple of identical checksums over the whole set of flips. + EXPECT_LE(IdenticalChecksums, 2); +} + +TEST(ScudoChecksumTest, ChecksumFunctions) { + verifyChecksumFunctionBitFlip<computeSoftwareChecksum>(); + if (&scudo::computeHardwareCRC32 && scudo::hasHardwareCRC32()) + verifyChecksumFunctionBitFlip<computeHardwareChecksum>(); +} diff --git a/lib/scudo/standalone/tests/flags_test.cc b/lib/scudo/standalone/tests/flags_test.cc new file mode 100644 index 000000000..2808a46cd --- /dev/null +++ b/lib/scudo/standalone/tests/flags_test.cc @@ -0,0 +1,119 @@ +//===-- flags_test.cc -------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "flags.h" +#include "flags_parser.h" + +#include "gtest/gtest.h" + +#include <string.h> + +static const char FlagName[] = "flag_name"; +static const char FlagDesc[] = "flag description"; + +template <typename T> +static void testFlag(scudo::FlagType Type, T StartValue, const char *Env, + T FinalValue) { + scudo::FlagParser Parser; + T Flag = StartValue; + Parser.registerFlag(FlagName, FlagDesc, Type, &Flag); + Parser.parseString(Env); + EXPECT_EQ(FinalValue, Flag); + // Reporting unrecognized flags is needed to reset them. + scudo::reportUnrecognizedFlags(); +} + +TEST(ScudoFlagsTest, BooleanFlags) { + testFlag(scudo::FlagType::FT_bool, false, "flag_name=1", true); + testFlag(scudo::FlagType::FT_bool, false, "flag_name=yes", true); + testFlag(scudo::FlagType::FT_bool, false, "flag_name='yes'", true); + testFlag(scudo::FlagType::FT_bool, false, "flag_name=true", true); + testFlag(scudo::FlagType::FT_bool, true, "flag_name=0", false); + testFlag(scudo::FlagType::FT_bool, true, "flag_name=\"0\"", false); + testFlag(scudo::FlagType::FT_bool, true, "flag_name=no", false); + testFlag(scudo::FlagType::FT_bool, true, "flag_name=false", false); + testFlag(scudo::FlagType::FT_bool, true, "flag_name='false'", false); +} + +TEST(ScudoFlagsDeathTest, BooleanFlags) { + EXPECT_DEATH(testFlag(scudo::FlagType::FT_bool, false, "flag_name", true), + "expected '='"); + EXPECT_DEATH(testFlag(scudo::FlagType::FT_bool, false, "flag_name=", true), + "invalid value for bool option: ''"); + EXPECT_DEATH(testFlag(scudo::FlagType::FT_bool, false, "flag_name=2", true), + "invalid value for bool option: '2'"); + EXPECT_DEATH(testFlag(scudo::FlagType::FT_bool, false, "flag_name=-1", true), + "invalid value for bool option: '-1'"); + EXPECT_DEATH(testFlag(scudo::FlagType::FT_bool, false, "flag_name=on", true), + "invalid value for bool option: 'on'"); +} + +TEST(ScudoFlagsTest, IntFlags) { + testFlag(scudo::FlagType::FT_int, -11, nullptr, -11); + testFlag(scudo::FlagType::FT_int, -11, "flag_name=0", 0); + testFlag(scudo::FlagType::FT_int, -11, "flag_name='0'", 0); + testFlag(scudo::FlagType::FT_int, -11, "flag_name=42", 42); + testFlag(scudo::FlagType::FT_int, -11, "flag_name=-42", -42); + testFlag(scudo::FlagType::FT_int, -11, "flag_name=\"-42\"", -42); + + // Unrecognized flags are ignored. + testFlag(scudo::FlagType::FT_int, -11, "--flag_name=42", -11); + testFlag(scudo::FlagType::FT_int, -11, "zzzzzzz=42", -11); +} + +TEST(ScudoFlagsDeathTest, IntFlags) { + EXPECT_DEATH(testFlag(scudo::FlagType::FT_int, -11, "flag_name", 0), + "expected '='"); + EXPECT_DEATH(testFlag(scudo::FlagType::FT_int, -11, "flag_name=42U", 0), + "invalid value for int option"); +} + +static void testTwoFlags(const char *Env, bool ExpectedFlag1, + const int ExpectedFlag2, const char *Name1 = "flag1", + const char *Name2 = "flag2") { + scudo::FlagParser Parser; + bool Flag1 = !ExpectedFlag1; + int Flag2; + Parser.registerFlag(Name1, FlagDesc, scudo::FlagType::FT_bool, &Flag1); + Parser.registerFlag(Name2, FlagDesc, scudo::FlagType::FT_int, &Flag2); + Parser.parseString(Env); + EXPECT_EQ(ExpectedFlag1, Flag1); + EXPECT_EQ(Flag2, ExpectedFlag2); + // Reporting unrecognized flags is needed to reset them. + scudo::reportUnrecognizedFlags(); +} + +TEST(ScudoFlagsTest, MultipleFlags) { + testTwoFlags("flag1=1 flag2=42", true, 42); + testTwoFlags("flag2=-1 flag1=0", false, -1); + testTwoFlags("flag1=false:flag2=1337", false, 1337); + testTwoFlags("flag2=42:flag1=yes", true, 42); + testTwoFlags("flag2=42\nflag1=yes", true, 42); + testTwoFlags("flag2=42\r\nflag1=yes", true, 42); + testTwoFlags("flag2=42\tflag1=yes", true, 42); +} + +TEST(ScudoFlagsTest, CommonSuffixFlags) { + testTwoFlags("flag=1 other_flag=42", true, 42, "flag", "other_flag"); + testTwoFlags("other_flag=42 flag=1", true, 42, "flag", "other_flag"); +} + +TEST(ScudoFlagsTest, AllocatorFlags) { + scudo::FlagParser Parser; + scudo::Flags Flags; + scudo::registerFlags(&Parser, &Flags); + Flags.setDefaults(); + Flags.dealloc_type_mismatch = false; + Flags.delete_size_mismatch = false; + Flags.quarantine_max_chunk_size = 1024; + Parser.parseString("dealloc_type_mismatch=true:delete_size_mismatch=true:" + "quarantine_max_chunk_size=2048"); + EXPECT_TRUE(Flags.dealloc_type_mismatch); + EXPECT_TRUE(Flags.delete_size_mismatch); + EXPECT_EQ(2048, Flags.quarantine_max_chunk_size); +} diff --git a/lib/scudo/standalone/tests/list_test.cc b/lib/scudo/standalone/tests/list_test.cc new file mode 100644 index 000000000..e4053d8b0 --- /dev/null +++ b/lib/scudo/standalone/tests/list_test.cc @@ -0,0 +1,185 @@ +//===-- list_test.cc --------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/list.h" +#include "gtest/gtest.h" + +struct ListItem { + ListItem *Next; +}; + +typedef scudo::IntrusiveList<ListItem> List; + +static List StaticList; + +static void setList(List *L, ListItem *X = nullptr, ListItem *Y = nullptr, + ListItem *Z = nullptr) { + L->clear(); + if (X) + L->push_back(X); + if (Y) + L->push_back(Y); + if (Z) + L->push_back(Z); +} + +static void checkList(List *L, ListItem *I1, ListItem *I2 = nullptr, + ListItem *I3 = nullptr, ListItem *I4 = nullptr, + ListItem *I5 = nullptr, ListItem *I6 = nullptr) { + if (I1) { + EXPECT_EQ(L->front(), I1); + L->pop_front(); + } + if (I2) { + EXPECT_EQ(L->front(), I2); + L->pop_front(); + } + if (I3) { + EXPECT_EQ(L->front(), I3); + L->pop_front(); + } + if (I4) { + EXPECT_EQ(L->front(), I4); + L->pop_front(); + } + if (I5) { + EXPECT_EQ(L->front(), I5); + L->pop_front(); + } + if (I6) { + EXPECT_EQ(L->front(), I6); + L->pop_front(); + } + EXPECT_TRUE(L->empty()); +} + +TEST(ScudoListTest, IntrusiveList) { + ListItem Items[6]; + EXPECT_EQ(StaticList.size(), 0U); + + List L; + L.clear(); + + ListItem *X = &Items[0]; + ListItem *Y = &Items[1]; + ListItem *Z = &Items[2]; + ListItem *A = &Items[3]; + ListItem *B = &Items[4]; + ListItem *C = &Items[5]; + + EXPECT_EQ(L.size(), 0U); + L.push_back(X); + EXPECT_EQ(L.size(), 1U); + EXPECT_EQ(L.back(), X); + EXPECT_EQ(L.front(), X); + L.pop_front(); + EXPECT_TRUE(L.empty()); + L.checkConsistency(); + + L.push_front(X); + EXPECT_EQ(L.size(), 1U); + EXPECT_EQ(L.back(), X); + EXPECT_EQ(L.front(), X); + L.pop_front(); + EXPECT_TRUE(L.empty()); + L.checkConsistency(); + + L.push_front(X); + L.push_front(Y); + L.push_front(Z); + EXPECT_EQ(L.size(), 3U); + EXPECT_EQ(L.front(), Z); + EXPECT_EQ(L.back(), X); + L.checkConsistency(); + + L.pop_front(); + EXPECT_EQ(L.size(), 2U); + EXPECT_EQ(L.front(), Y); + EXPECT_EQ(L.back(), X); + L.pop_front(); + L.pop_front(); + EXPECT_TRUE(L.empty()); + L.checkConsistency(); + + L.push_back(X); + L.push_back(Y); + L.push_back(Z); + EXPECT_EQ(L.size(), 3U); + EXPECT_EQ(L.front(), X); + EXPECT_EQ(L.back(), Z); + L.checkConsistency(); + + L.pop_front(); + EXPECT_EQ(L.size(), 2U); + EXPECT_EQ(L.front(), Y); + EXPECT_EQ(L.back(), Z); + L.pop_front(); + L.pop_front(); + EXPECT_TRUE(L.empty()); + L.checkConsistency(); + + L.push_back(X); + L.push_back(Y); + L.push_back(Z); + L.extract(X, Y); + EXPECT_EQ(L.size(), 2U); + EXPECT_EQ(L.front(), X); + EXPECT_EQ(L.back(), Z); + L.checkConsistency(); + L.extract(X, Z); + EXPECT_EQ(L.size(), 1U); + EXPECT_EQ(L.front(), X); + EXPECT_EQ(L.back(), X); + L.checkConsistency(); + L.pop_front(); + EXPECT_TRUE(L.empty()); + + List L1, L2; + L1.clear(); + L2.clear(); + + L1.append_front(&L2); + EXPECT_TRUE(L1.empty()); + EXPECT_TRUE(L2.empty()); + + L1.append_back(&L2); + EXPECT_TRUE(L1.empty()); + EXPECT_TRUE(L2.empty()); + + setList(&L1, X); + checkList(&L1, X); + + setList(&L1, X, Y, Z); + setList(&L2, A, B, C); + L1.append_back(&L2); + checkList(&L1, X, Y, Z, A, B, C); + EXPECT_TRUE(L2.empty()); + + setList(&L1, X, Y); + setList(&L2); + L1.append_front(&L2); + checkList(&L1, X, Y); + EXPECT_TRUE(L2.empty()); +} + +TEST(ScudoListTest, IntrusiveListAppendEmpty) { + ListItem I; + List L; + L.clear(); + L.push_back(&I); + List L2; + L2.clear(); + L.append_back(&L2); + EXPECT_EQ(L.back(), &I); + EXPECT_EQ(L.front(), &I); + EXPECT_EQ(L.size(), 1U); + L.append_front(&L2); + EXPECT_EQ(L.back(), &I); + EXPECT_EQ(L.front(), &I); + EXPECT_EQ(L.size(), 1U); +} diff --git a/lib/scudo/standalone/tests/map_test.cc b/lib/scudo/standalone/tests/map_test.cc new file mode 100644 index 000000000..7c726e947 --- /dev/null +++ b/lib/scudo/standalone/tests/map_test.cc @@ -0,0 +1,65 @@ +//===-- map_test.cc ---------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "common.h" + +#include "gtest/gtest.h" + +#include <string.h> + +static const char *MappingName = "scudo:test"; + +TEST(ScudoMapTest, MapNoAccessUnmap) { + const scudo::uptr Size = 4 * scudo::getPageSizeCached(); + scudo::MapPlatformData Data = {}; + void *P = scudo::map(nullptr, Size, MappingName, MAP_NOACCESS, &Data); + EXPECT_NE(P, nullptr); + EXPECT_DEATH(memset(P, 0xaa, Size), ""); + scudo::unmap(P, Size, UNMAP_ALL, &Data); +} + +TEST(ScudoMapTest, MapUnmap) { + const scudo::uptr Size = 4 * scudo::getPageSizeCached(); + scudo::MapPlatformData Data = {}; + void *P = scudo::map(nullptr, Size, MappingName, 0, &Data); + EXPECT_NE(P, nullptr); + memset(P, 0xaa, Size); + scudo::unmap(P, Size, 0, &Data); + EXPECT_DEATH(memset(P, 0xbb, Size), ""); +} + +TEST(ScudoMapTest, MapWithGuardUnmap) { + const scudo::uptr PageSize = scudo::getPageSizeCached(); + const scudo::uptr Size = 4 * PageSize; + scudo::MapPlatformData Data = {}; + void *P = scudo::map(nullptr, Size + 2 * PageSize, MappingName, MAP_NOACCESS, + &Data); + EXPECT_NE(P, nullptr); + void *Q = + reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(P) + PageSize); + EXPECT_EQ(scudo::map(Q, Size, MappingName, 0, &Data), Q); + memset(Q, 0xaa, Size); + EXPECT_DEATH(memset(Q, 0xaa, Size + 1), ""); + scudo::unmap(P, Size + 2 * PageSize, UNMAP_ALL, &Data); +} + +TEST(ScudoMapTest, MapGrowUnmap) { + const scudo::uptr PageSize = scudo::getPageSizeCached(); + const scudo::uptr Size = 4 * PageSize; + scudo::MapPlatformData Data = {}; + void *P = scudo::map(nullptr, Size, MappingName, MAP_NOACCESS, &Data); + EXPECT_NE(P, nullptr); + void *Q = + reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(P) + PageSize); + EXPECT_EQ(scudo::map(Q, PageSize, MappingName, 0, &Data), Q); + memset(Q, 0xaa, PageSize); + Q = reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(Q) + PageSize); + EXPECT_EQ(scudo::map(Q, PageSize, MappingName, 0, &Data), Q); + memset(Q, 0xbb, PageSize); + scudo::unmap(P, Size, UNMAP_ALL, &Data); +} diff --git a/lib/scudo/standalone/tests/mutex_test.cc b/lib/scudo/standalone/tests/mutex_test.cc new file mode 100644 index 000000000..ce33db58b --- /dev/null +++ b/lib/scudo/standalone/tests/mutex_test.cc @@ -0,0 +1,121 @@ +//===-- mutex_test.cc -------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "mutex.h" + +#include "gtest/gtest.h" + +#include <string.h> + +template <typename MutexType> class TestData { +public: + explicit TestData(MutexType *M) : Mutex(M) { + for (scudo::u32 I = 0; I < Size; I++) + Data[I] = 0; + } + + void write() { + Lock L(Mutex); + T V0 = Data[0]; + for (scudo::u32 I = 0; I < Size; I++) { + EXPECT_EQ(Data[I], V0); + Data[I]++; + } + } + + void tryWrite() { + if (!Mutex->tryLock()) + return; + T V0 = Data[0]; + for (scudo::u32 I = 0; I < Size; I++) { + EXPECT_EQ(Data[I], V0); + Data[I]++; + } + Mutex->unlock(); + } + + void backoff() { + volatile T LocalData[Size] = {}; + for (scudo::u32 I = 0; I < Size; I++) { + LocalData[I]++; + EXPECT_EQ(LocalData[I], 1U); + } + } + +private: + typedef scudo::GenericScopedLock<MutexType> Lock; + static const scudo::u32 Size = 64U; + typedef scudo::u64 T; + MutexType *Mutex; + ALIGNED(SCUDO_CACHE_LINE_SIZE) T Data[Size]; +}; + +const scudo::u32 NumberOfThreads = 8; +#if SCUDO_DEBUG +const scudo::u32 NumberOfIterations = 4 * 1024; +#else +const scudo::u32 NumberOfIterations = 16 * 1024; +#endif + +template <typename MutexType> static void *lockThread(void *Param) { + TestData<MutexType> *Data = reinterpret_cast<TestData<MutexType> *>(Param); + for (scudo::u32 I = 0; I < NumberOfIterations; I++) { + Data->write(); + Data->backoff(); + } + return 0; +} + +template <typename MutexType> static void *tryThread(void *Param) { + TestData<MutexType> *Data = reinterpret_cast<TestData<MutexType> *>(Param); + for (scudo::u32 I = 0; I < NumberOfIterations; I++) { + Data->tryWrite(); + Data->backoff(); + } + return 0; +} + +template <typename MutexType> static void checkLocked(MutexType *M) { + scudo::GenericScopedLock<MutexType> L(M); + M->checkLocked(); +} + +TEST(ScudoMutexTest, SpinMutex) { + scudo::SpinMutex M; + M.init(); + TestData<scudo::SpinMutex> Data(&M); + pthread_t Threads[NumberOfThreads]; + for (scudo::u32 I = 0; I < NumberOfThreads; I++) + pthread_create(&Threads[I], 0, lockThread<scudo::SpinMutex>, &Data); + for (scudo::u32 I = 0; I < NumberOfThreads; I++) + pthread_join(Threads[I], 0); +} + +TEST(ScudoMutexTest, SpinMutexTry) { + scudo::SpinMutex M; + M.init(); + TestData<scudo::SpinMutex> Data(&M); + pthread_t Threads[NumberOfThreads]; + for (scudo::u32 I = 0; I < NumberOfThreads; I++) + pthread_create(&Threads[I], 0, tryThread<scudo::SpinMutex>, &Data); + for (scudo::u32 I = 0; I < NumberOfThreads; I++) + pthread_join(Threads[I], 0); +} + +TEST(ScudoMutexTest, BlockingMutex) { + scudo::u64 MutexMemory[1024] = {}; + scudo::BlockingMutex *M = + new (MutexMemory) scudo::BlockingMutex(scudo::LINKER_INITIALIZED); + TestData<scudo::BlockingMutex> Data(M); + pthread_t Threads[NumberOfThreads]; + for (scudo::u32 I = 0; I < NumberOfThreads; I++) + pthread_create(&Threads[I], 0, lockThread<scudo::BlockingMutex>, &Data); + for (scudo::u32 I = 0; I < NumberOfThreads; I++) + pthread_join(Threads[I], 0); + checkLocked(M); +} diff --git a/lib/scudo/standalone/tests/release_test.cc b/lib/scudo/standalone/tests/release_test.cc new file mode 100644 index 000000000..2279d5d15 --- /dev/null +++ b/lib/scudo/standalone/tests/release_test.cc @@ -0,0 +1,260 @@ +//===-- release_test.cc -----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "list.h" +#include "release.h" +#include "size_class_map.h" + +#include "gtest/gtest.h" + +#include <string.h> + +#include <algorithm> +#include <random> + +TEST(ScudoReleaseTest, PackedCounterArray) { + for (scudo::uptr I = 0; I < SCUDO_WORDSIZE; I++) { + // Various valid counter's max values packed into one word. + scudo::PackedCounterArray Counters2N(1, 1UL << I); + EXPECT_EQ(sizeof(scudo::uptr), Counters2N.getBufferSize()); + // Check the "all bit set" values too. + scudo::PackedCounterArray Counters2N1_1(1, ~0UL >> I); + EXPECT_EQ(sizeof(scudo::uptr), Counters2N1_1.getBufferSize()); + // Verify the packing ratio, the counter is Expected to be packed into the + // closest power of 2 bits. + scudo::PackedCounterArray Counters(SCUDO_WORDSIZE, 1UL << I); + EXPECT_EQ(sizeof(scudo::uptr) * scudo::roundUpToPowerOfTwo(I + 1), + Counters.getBufferSize()); + } + + // Go through 1, 2, 4, 8, .. {32,64} bits per counter. + for (scudo::uptr I = 0; (SCUDO_WORDSIZE >> I) != 0; I++) { + // Make sure counters request one memory page for the buffer. + const scudo::uptr NumCounters = + (scudo::getPageSizeCached() / 8) * (SCUDO_WORDSIZE >> I); + scudo::PackedCounterArray Counters(NumCounters, 1UL << ((1UL << I) - 1)); + Counters.inc(0); + for (scudo::uptr C = 1; C < NumCounters - 1; C++) { + EXPECT_EQ(0UL, Counters.get(C)); + Counters.inc(C); + EXPECT_EQ(1UL, Counters.get(C - 1)); + } + EXPECT_EQ(0UL, Counters.get(NumCounters - 1)); + Counters.inc(NumCounters - 1); + if (I > 0) { + Counters.incRange(0, NumCounters - 1); + for (scudo::uptr C = 0; C < NumCounters; C++) + EXPECT_EQ(2UL, Counters.get(C)); + } + } +} + +class StringRangeRecorder { +public: + std::string ReportedPages; + + StringRangeRecorder() + : PageSizeScaledLog(scudo::getLog2(scudo::getPageSizeCached())) {} + + void releasePageRangeToOS(scudo::uptr From, scudo::uptr To) { + From >>= PageSizeScaledLog; + To >>= PageSizeScaledLog; + EXPECT_LT(From, To); + if (!ReportedPages.empty()) + EXPECT_LT(LastPageReported, From); + ReportedPages.append(From - LastPageReported, '.'); + ReportedPages.append(To - From, 'x'); + LastPageReported = To; + } + +private: + const scudo::uptr PageSizeScaledLog; + scudo::uptr LastPageReported = 0; +}; + +TEST(ScudoReleaseTest, FreePagesRangeTracker) { + // 'x' denotes a page to be released, '.' denotes a page to be kept around. + const char *TestCases[] = { + "", + ".", + "x", + "........", + "xxxxxxxxxxx", + "..............xxxxx", + "xxxxxxxxxxxxxxxxxx.....", + "......xxxxxxxx........", + "xxx..........xxxxxxxxxxxxxxx", + "......xxxx....xxxx........", + "xxx..........xxxxxxxx....xxxxxxx", + "x.x.x.x.x.x.x.x.x.x.x.x.", + ".x.x.x.x.x.x.x.x.x.x.x.x", + ".x.x.x.x.x.x.x.x.x.x.x.x.", + "x.x.x.x.x.x.x.x.x.x.x.x.x", + }; + typedef scudo::FreePagesRangeTracker<StringRangeRecorder> RangeTracker; + + for (auto TestCase : TestCases) { + StringRangeRecorder Recorder; + RangeTracker Tracker(&Recorder); + for (scudo::uptr I = 0; TestCase[I] != 0; I++) + Tracker.processNextPage(TestCase[I] == 'x'); + Tracker.finish(); + // Strip trailing '.'-pages before comparing the results as they are not + // going to be reported to range_recorder anyway. + const char *LastX = strrchr(TestCase, 'x'); + std::string Expected(TestCase, + LastX == nullptr ? 0 : (LastX - TestCase + 1)); + EXPECT_STREQ(Expected.c_str(), Recorder.ReportedPages.c_str()); + } +} + +class ReleasedPagesRecorder { +public: + std::set<scudo::uptr> ReportedPages; + + void releasePageRangeToOS(scudo::uptr From, scudo::uptr To) { + const scudo::uptr PageSize = scudo::getPageSizeCached(); + for (scudo::uptr I = From; I < To; I += PageSize) + ReportedPages.insert(I); + } +}; + +// Simplified version of a TransferBatch. +template <class SizeClassMap> struct FreeBatch { + static const scudo::u32 MaxCount = SizeClassMap::MaxNumCachedHint; + void clear() { Count = 0; } + void add(scudo::uptr P) { + DCHECK_LT(Count, MaxCount); + Batch[Count++] = P; + } + scudo::u32 getCount() const { return Count; } + scudo::uptr get(scudo::u32 I) const { + DCHECK_LE(I, Count); + return Batch[I]; + } + FreeBatch *Next; + +private: + scudo::u32 Count; + scudo::uptr Batch[MaxCount]; +}; + +template <class SizeClassMap> void testReleaseFreeMemoryToOS() { + typedef FreeBatch<SizeClassMap> Batch; + const scudo::uptr AllocatedPagesCount = 1024; + const scudo::uptr PageSize = scudo::getPageSizeCached(); + std::mt19937 R; + scudo::u32 RandState = 42; + + for (scudo::uptr I = 1; I <= SizeClassMap::LargestClassId; I++) { + const scudo::uptr BlockSize = SizeClassMap::getSizeByClassId(I); + const scudo::uptr MaxBlocks = AllocatedPagesCount * PageSize / BlockSize; + + // Generate the random free list. + std::vector<scudo::uptr> FreeArray; + bool InFreeRange = false; + scudo::uptr CurrentRangeEnd = 0; + for (scudo::uptr I = 0; I < MaxBlocks; I++) { + if (I == CurrentRangeEnd) { + InFreeRange = (scudo::getRandomU32(&RandState) & 1U) == 1; + CurrentRangeEnd += (scudo::getRandomU32(&RandState) & 0x7f) + 1; + } + if (InFreeRange) + FreeArray.push_back(I * BlockSize); + } + if (FreeArray.empty()) + continue; + // Shuffle the array to ensure that the order is irrelevant. + std::shuffle(FreeArray.begin(), FreeArray.end(), R); + + // Build the FreeList from the FreeArray. + scudo::IntrusiveList<Batch> FreeList; + FreeList.clear(); + Batch *CurrentBatch = nullptr; + for (auto const &Block : FreeArray) { + if (!CurrentBatch) { + CurrentBatch = new Batch; + CurrentBatch->clear(); + FreeList.push_back(CurrentBatch); + } + CurrentBatch->add(Block); + if (CurrentBatch->getCount() == Batch::MaxCount) + CurrentBatch = nullptr; + } + + // Release the memory. + ReleasedPagesRecorder Recorder; + releaseFreeMemoryToOS(&FreeList, 0, AllocatedPagesCount, BlockSize, + &Recorder); + + // Verify that there are no released pages touched by used chunks and all + // ranges of free chunks big enough to contain the entire memory pages had + // these pages released. + scudo::uptr VerifiedReleasedPages = 0; + std::set<scudo::uptr> FreeBlocks(FreeArray.begin(), FreeArray.end()); + + scudo::uptr CurrentBlock = 0; + InFreeRange = false; + scudo::uptr CurrentFreeRangeStart = 0; + for (scudo::uptr I = 0; I <= MaxBlocks; I++) { + const bool IsFreeBlock = + FreeBlocks.find(CurrentBlock) != FreeBlocks.end(); + if (IsFreeBlock) { + if (!InFreeRange) { + InFreeRange = true; + CurrentFreeRangeStart = CurrentBlock; + } + } else { + // Verify that this used chunk does not touch any released page. + const scudo::uptr StartPage = CurrentBlock / PageSize; + const scudo::uptr EndPage = (CurrentBlock + BlockSize - 1) / PageSize; + for (scudo::uptr J = StartPage; J <= EndPage; J++) { + const bool PageReleased = Recorder.ReportedPages.find(J * PageSize) != + Recorder.ReportedPages.end(); + EXPECT_EQ(false, PageReleased); + } + + if (InFreeRange) { + InFreeRange = false; + // Verify that all entire memory pages covered by this range of free + // chunks were released. + scudo::uptr P = scudo::roundUpTo(CurrentFreeRangeStart, PageSize); + while (P + PageSize <= CurrentBlock) { + const bool PageReleased = + Recorder.ReportedPages.find(P) != Recorder.ReportedPages.end(); + EXPECT_EQ(true, PageReleased); + VerifiedReleasedPages++; + P += PageSize; + } + } + } + + CurrentBlock += BlockSize; + } + + EXPECT_EQ(Recorder.ReportedPages.size(), VerifiedReleasedPages); + + while (!FreeList.empty()) { + CurrentBatch = FreeList.front(); + FreeList.pop_front(); + delete CurrentBatch; + } + } +} + +TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSDefault) { + testReleaseFreeMemoryToOS<scudo::DefaultSizeClassMap>(); +} + +TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSAndroid) { + testReleaseFreeMemoryToOS<scudo::AndroidSizeClassMap>(); +} + +TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSSvelte) { + testReleaseFreeMemoryToOS<scudo::SvelteSizeClassMap>(); +} diff --git a/lib/scudo/standalone/tests/report_test.cc b/lib/scudo/standalone/tests/report_test.cc new file mode 100644 index 000000000..ce7eda59c --- /dev/null +++ b/lib/scudo/standalone/tests/report_test.cc @@ -0,0 +1,47 @@ +//===-- report_test.cc ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/report.h" +#include "gtest/gtest.h" + +TEST(ScudoReportTest, Generic) { + void *P = reinterpret_cast<void *>(0x42424242U); + EXPECT_DEATH(scudo::reportError("TEST123"), "Scudo ERROR.*TEST123"); + EXPECT_DEATH(scudo::reportInvalidFlag("ABC", "DEF"), "Scudo ERROR.*ABC.*DEF"); + EXPECT_DEATH(scudo::reportHeaderCorruption(P), "Scudo ERROR.*42424242"); + EXPECT_DEATH(scudo::reportHeaderRace(P), "Scudo ERROR.*42424242"); + EXPECT_DEATH(scudo::reportSanityCheckError("XYZ"), "Scudo ERROR.*XYZ"); + EXPECT_DEATH(scudo::reportAlignmentTooBig(123, 456), "Scudo ERROR.*123.*456"); + EXPECT_DEATH(scudo::reportAllocationSizeTooBig(123, 456, 789), + "Scudo ERROR.*123.*456.*789"); + EXPECT_DEATH(scudo::reportOutOfMemory(4242), "Scudo ERROR.*4242"); + EXPECT_DEATH( + scudo::reportInvalidChunkState(scudo::AllocatorAction::Recycling, P), + "Scudo ERROR.*recycling.*42424242"); + EXPECT_DEATH( + scudo::reportInvalidChunkState(scudo::AllocatorAction::Sizing, P), + "Scudo ERROR.*sizing.*42424242"); + EXPECT_DEATH( + scudo::reportMisalignedPointer(scudo::AllocatorAction::Deallocating, P), + "Scudo ERROR.*deallocating.*42424242"); + EXPECT_DEATH(scudo::reportDeallocTypeMismatch( + scudo::AllocatorAction::Reallocating, P, 0, 1), + "Scudo ERROR.*reallocating.*42424242"); + EXPECT_DEATH(scudo::reportDeleteSizeMismatch(P, 123, 456), + "Scudo ERROR.*42424242.*123.*456"); +} + +TEST(ScudoReportTest, CSpecific) { + EXPECT_DEATH(scudo::reportAlignmentNotPowerOfTwo(123), "Scudo ERROR.*123"); + EXPECT_DEATH(scudo::reportCallocOverflow(123, 456), "Scudo ERROR.*123.*456"); + EXPECT_DEATH(scudo::reportInvalidPosixMemalignAlignment(789), + "Scudo ERROR.*789"); + EXPECT_DEATH(scudo::reportPvallocOverflow(123), "Scudo ERROR.*123"); + EXPECT_DEATH(scudo::reportInvalidAlignedAllocAlignment(123, 456), + "Scudo ERROR.*123.*456"); +} diff --git a/lib/scudo/standalone/tests/scudo_unit_test_main.cc b/lib/scudo/standalone/tests/scudo_unit_test_main.cc new file mode 100644 index 000000000..16398e5da --- /dev/null +++ b/lib/scudo/standalone/tests/scudo_unit_test_main.cc @@ -0,0 +1,14 @@ +//===-- scudo_unit_test_main.cc ---------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" + +int main(int argc, char **argv) { + testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/lib/scudo/standalone/tests/secondary_test.cc b/lib/scudo/standalone/tests/secondary_test.cc new file mode 100644 index 000000000..8eed16e0e --- /dev/null +++ b/lib/scudo/standalone/tests/secondary_test.cc @@ -0,0 +1,137 @@ +//===-- secondary_test.cc ---------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "secondary.h" + +#include "gtest/gtest.h" + +#include <stdio.h> + +#include <condition_variable> +#include <mutex> +#include <thread> + +TEST(ScudoSecondaryTest, SecondaryBasic) { + scudo::GlobalStats S; + S.init(); + scudo::MapAllocator *L = new scudo::MapAllocator; + L->init(&S); + const scudo::uptr Size = 1U << 16; + void *P = L->allocate(Size); + EXPECT_NE(P, nullptr); + memset(P, 'A', Size); + EXPECT_GE(scudo::MapAllocator::getBlockSize(P), Size); + L->deallocate(P); + EXPECT_DEATH(memset(P, 'A', Size), ""); + + const scudo::uptr Align = 1U << 16; + P = L->allocate(Size + Align, Align); + EXPECT_NE(P, nullptr); + void *AlignedP = reinterpret_cast<void *>( + scudo::roundUpTo(reinterpret_cast<scudo::uptr>(P), Align)); + memset(AlignedP, 'A', Size); + L->deallocate(P); + + std::vector<void *> V; + for (scudo::u8 I = 0; I < 32; I++) + V.push_back(L->allocate(Size)); + std::random_shuffle(V.begin(), V.end()); + while (!V.empty()) { + L->deallocate(V.back()); + V.pop_back(); + } + L->printStats(); +} + +// This exercises a variety of combinations of size and alignment for the +// MapAllocator. The size computation done here mimic the ones done by the +// combined allocator. +TEST(ScudoSecondaryTest, SecondaryCombinations) { + constexpr scudo::uptr MinAlign = FIRST_32_SECOND_64(8, 16); + constexpr scudo::uptr HeaderSize = scudo::roundUpTo(8, MinAlign); + scudo::MapAllocator *L = new scudo::MapAllocator; + L->init(nullptr); + for (scudo::uptr SizeLog = 0; SizeLog <= 20; SizeLog++) { + for (scudo::uptr AlignLog = FIRST_32_SECOND_64(3, 4); AlignLog <= 16; + AlignLog++) { + const scudo::uptr Align = 1U << AlignLog; + for (scudo::sptr Delta = -128; Delta <= 128; Delta += 8) { + if (static_cast<scudo::sptr>(1U << SizeLog) + Delta <= 0) + continue; + const scudo::uptr UserSize = + scudo::roundUpTo((1U << SizeLog) + Delta, MinAlign); + const scudo::uptr Size = + HeaderSize + UserSize + (Align > MinAlign ? Align - HeaderSize : 0); + void *P = L->allocate(Size, Align); + EXPECT_NE(P, nullptr); + void *AlignedP = reinterpret_cast<void *>( + scudo::roundUpTo(reinterpret_cast<scudo::uptr>(P), Align)); + memset(AlignedP, 0xff, UserSize); + L->deallocate(P); + } + } + } + L->printStats(); +} + +TEST(ScudoSecondaryTest, SecondaryIterate) { + scudo::MapAllocator *L = new scudo::MapAllocator; + L->init(nullptr); + std::vector<void *> V; + const scudo::uptr PageSize = scudo::getPageSizeCached(); + for (scudo::u8 I = 0; I < 32; I++) + V.push_back(L->allocate((std::rand() % 16) * PageSize)); + auto Lambda = [V](scudo::uptr Block) { + EXPECT_NE(std::find(V.begin(), V.end(), reinterpret_cast<void *>(Block)), + V.end()); + }; + L->disable(); + L->iterateOverBlocks(Lambda); + L->enable(); + while (!V.empty()) { + L->deallocate(V.back()); + V.pop_back(); + } + L->printStats(); +} + +std::mutex Mutex; +std::condition_variable Cv; +bool Ready = false; + +static void performAllocations(scudo::MapAllocator *L) { + { + std::unique_lock<std::mutex> Lock(Mutex); + while (!Ready) + Cv.wait(Lock); + } + std::vector<void *> V; + const scudo::uptr PageSize = scudo::getPageSizeCached(); + for (scudo::u8 I = 0; I < 32; I++) + V.push_back(L->allocate((std::rand() % 16) * PageSize)); + while (!V.empty()) { + L->deallocate(V.back()); + V.pop_back(); + } +} + +TEST(ScudoSecondaryTest, SecondaryThreadsRace) { + scudo::MapAllocator *L = new scudo::MapAllocator; + L->init(nullptr); + std::thread Threads[10]; + for (scudo::uptr I = 0; I < 10; I++) + Threads[I] = std::thread(performAllocations, L); + { + std::unique_lock<std::mutex> Lock(Mutex); + Ready = true; + Cv.notify_all(); + } + for (auto &T : Threads) + T.join(); + L->printStats(); +} diff --git a/lib/scudo/standalone/tests/size_class_map_test.cc b/lib/scudo/standalone/tests/size_class_map_test.cc new file mode 100644 index 000000000..d857aa4b2 --- /dev/null +++ b/lib/scudo/standalone/tests/size_class_map_test.cc @@ -0,0 +1,38 @@ +//===-- size_class_map_test.cc ----------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/size_class_map.h" +#include "gtest/gtest.h" + +template <class SizeClassMap> void testSizeClassMap() { + typedef SizeClassMap SCMap; + SCMap::print(); + SCMap::validate(); +} + +TEST(ScudoSizeClassMapTest, DefaultSizeClassMap) { + testSizeClassMap<scudo::DefaultSizeClassMap>(); +} + +TEST(ScudoSizeClassMapTest, SvelteSizeClassMap) { + testSizeClassMap<scudo::SvelteSizeClassMap>(); +} + +TEST(ScudoSizeClassMapTest, AndroidSizeClassMap) { + testSizeClassMap<scudo::AndroidSizeClassMap>(); +} + +TEST(ScudoSizeClassMapTest, OneClassSizeClassMap) { + testSizeClassMap<scudo::SizeClassMap<1, 5, 5, 5, 0, 0>>(); +} + +#if SCUDO_CAN_USE_PRIMARY64 +TEST(ScudoSizeClassMapTest, LargeMaxSizeClassMap) { + testSizeClassMap<scudo::SizeClassMap<3, 4, 8, 63, 128, 16>>(); +} +#endif diff --git a/lib/scudo/standalone/tests/stats_test.cc b/lib/scudo/standalone/tests/stats_test.cc new file mode 100644 index 000000000..9ed105d3d --- /dev/null +++ b/lib/scudo/standalone/tests/stats_test.cc @@ -0,0 +1,45 @@ +//===-- stats_test.cc -------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/stats.h" +#include "gtest/gtest.h" + +TEST(ScudoStatsTest, LocalStats) { + scudo::LocalStats LStats; + LStats.init(); + for (scudo::uptr I = 0; I < scudo::StatCount; I++) + EXPECT_EQ(LStats.get(static_cast<scudo::StatType>(I)), 0U); + LStats.add(scudo::StatAllocated, 4096U); + EXPECT_EQ(LStats.get(scudo::StatAllocated), 4096U); + LStats.sub(scudo::StatAllocated, 4096U); + EXPECT_EQ(LStats.get(scudo::StatAllocated), 0U); + LStats.set(scudo::StatAllocated, 4096U); + EXPECT_EQ(LStats.get(scudo::StatAllocated), 4096U); +} + +TEST(ScudoStatsTest, GlobalStats) { + scudo::GlobalStats GStats; + GStats.init(); + scudo::uptr Counters[scudo::StatCount] = {}; + GStats.get(Counters); + for (scudo::uptr I = 0; I < scudo::StatCount; I++) + EXPECT_EQ(Counters[I], 0U); + scudo::LocalStats LStats; + LStats.init(); + GStats.link(&LStats); + for (scudo::uptr I = 0; I < scudo::StatCount; I++) + LStats.add(static_cast<scudo::StatType>(I), 4096U); + GStats.get(Counters); + for (scudo::uptr I = 0; I < scudo::StatCount; I++) + EXPECT_EQ(Counters[I], 4096U); + // Unlinking the local stats move numbers to the global stats. + GStats.unlink(&LStats); + GStats.get(Counters); + for (scudo::uptr I = 0; I < scudo::StatCount; I++) + EXPECT_EQ(Counters[I], 4096U); +} diff --git a/lib/scudo/standalone/tests/strings_test.cc b/lib/scudo/standalone/tests/strings_test.cc new file mode 100644 index 000000000..31e59c403 --- /dev/null +++ b/lib/scudo/standalone/tests/strings_test.cc @@ -0,0 +1,98 @@ +//===-- strings_test.cc -----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/string_utils.h" +#include "gtest/gtest.h" + +#include <limits.h> + +TEST(ScudoStringsTest, Basic) { + scudo::ScopedString Str(128); + Str.append("a%db%zdc%ue%zuf%xh%zxq%pe%sr", static_cast<int>(-1), + static_cast<scudo::uptr>(-2), static_cast<unsigned>(-4), + static_cast<scudo::uptr>(5), static_cast<unsigned>(10), + static_cast<scudo::uptr>(11), reinterpret_cast<void *>(0x123), + "_string_"); + EXPECT_EQ(Str.length(), strlen(Str.data())); + + std::string expectedString = "a-1b-2c4294967292e5fahbq0x"; + expectedString += std::string(SCUDO_POINTER_FORMAT_LENGTH - 3, '0'); + expectedString += "123e_string_r"; + EXPECT_EQ(Str.length(), strlen(Str.data())); + EXPECT_STREQ(expectedString.c_str(), Str.data()); +} + +TEST(ScudoStringsTest, Precision) { + scudo::ScopedString Str(128); + Str.append("%.*s", 3, "12345"); + EXPECT_EQ(Str.length(), strlen(Str.data())); + EXPECT_STREQ("123", Str.data()); + Str.clear(); + Str.append("%.*s", 6, "12345"); + EXPECT_EQ(Str.length(), strlen(Str.data())); + EXPECT_STREQ("12345", Str.data()); + Str.clear(); + Str.append("%-6s", "12345"); + EXPECT_EQ(Str.length(), strlen(Str.data())); + EXPECT_STREQ("12345 ", Str.data()); +} + +static void fillString(scudo::ScopedString &Str, scudo::uptr Size) { + for (scudo::uptr I = 0; I < Size; I++) + Str.append("A"); +} + +TEST(ScudoStringTest, PotentialOverflows) { + // Use a ScopedString that spans a page, and attempt to write past the end + // of it with variations of append. The expectation is for nothing to crash. + const scudo::uptr PageSize = scudo::getPageSizeCached(); + scudo::ScopedString Str(PageSize); + Str.clear(); + fillString(Str, 2 * PageSize); + Str.clear(); + fillString(Str, PageSize - 64); + Str.append("%-128s", "12345"); + Str.clear(); + fillString(Str, PageSize - 16); + Str.append("%024x", 12345); + Str.clear(); + fillString(Str, PageSize - 16); + Str.append("EEEEEEEEEEEEEEEEEEEEEEEE"); +} + +template <typename T> +static void testAgainstLibc(const char *Format, T Arg1, T Arg2) { + scudo::ScopedString Str(128); + Str.append(Format, Arg1, Arg2); + char Buffer[128]; + snprintf(Buffer, sizeof(Buffer), Format, Arg1, Arg2); + EXPECT_EQ(Str.length(), strlen(Str.data())); + EXPECT_STREQ(Buffer, Str.data()); +} + +TEST(ScudoStringsTest, MinMax) { + testAgainstLibc<int>("%d-%d", INT_MIN, INT_MAX); + testAgainstLibc<unsigned>("%u-%u", 0, UINT_MAX); + testAgainstLibc<unsigned>("%x-%x", 0, UINT_MAX); + testAgainstLibc<long>("%zd-%zd", LONG_MIN, LONG_MAX); + testAgainstLibc<unsigned long>("%zu-%zu", 0, ULONG_MAX); + testAgainstLibc<unsigned long>("%zx-%zx", 0, ULONG_MAX); +} + +TEST(ScudoStringsTest, Padding) { + testAgainstLibc<int>("%3d - %3d", 1, 0); + testAgainstLibc<int>("%3d - %3d", -1, 123); + testAgainstLibc<int>("%3d - %3d", -1, -123); + testAgainstLibc<int>("%3d - %3d", 12, 1234); + testAgainstLibc<int>("%3d - %3d", -12, -1234); + testAgainstLibc<int>("%03d - %03d", 1, 0); + testAgainstLibc<int>("%03d - %03d", -1, 123); + testAgainstLibc<int>("%03d - %03d", -1, -123); + testAgainstLibc<int>("%03d - %03d", 12, 1234); + testAgainstLibc<int>("%03d - %03d", -12, -1234); +} diff --git a/lib/scudo/standalone/tests/vector_test.cc b/lib/scudo/standalone/tests/vector_test.cc new file mode 100644 index 000000000..ebfcc43cc --- /dev/null +++ b/lib/scudo/standalone/tests/vector_test.cc @@ -0,0 +1,43 @@ +//===-- vector_test.cc ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "vector.h" + +#include "gtest/gtest.h" + +TEST(ScudoVectorTest, Basic) { + scudo::Vector<int> V; + EXPECT_EQ(V.size(), 0U); + V.push_back(42); + EXPECT_EQ(V.size(), 1U); + EXPECT_EQ(V[0], 42); + V.push_back(43); + EXPECT_EQ(V.size(), 2U); + EXPECT_EQ(V[0], 42); + EXPECT_EQ(V[1], 43); +} + +TEST(ScudoVectorTest, Stride) { + scudo::Vector<int> V; + for (int i = 0; i < 1000; i++) { + V.push_back(i); + EXPECT_EQ(V.size(), i + 1U); + EXPECT_EQ(V[i], i); + } + for (int i = 0; i < 1000; i++) + EXPECT_EQ(V[i], i); +} + +TEST(ScudoVectorTest, ResizeReduction) { + scudo::Vector<int> V; + V.push_back(0); + V.push_back(0); + EXPECT_EQ(V.size(), 2U); + V.resize(1); + EXPECT_EQ(V.size(), 1U); +} diff --git a/lib/scudo/standalone/vector.h b/lib/scudo/standalone/vector.h new file mode 100644 index 000000000..3cb4005ed --- /dev/null +++ b/lib/scudo/standalone/vector.h @@ -0,0 +1,118 @@ +//===-- vector.h ------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_VECTOR_H_ +#define SCUDO_VECTOR_H_ + +#include "common.h" + +#include <string.h> + +namespace scudo { + +// A low-level vector based on map. May incur a significant memory overhead for +// small vectors. The current implementation supports only POD types. +template <typename T> class VectorNoCtor { +public: + void init(uptr InitialCapacity) { + CapacityBytes = 0; + Size = 0; + Data = nullptr; + reserve(InitialCapacity); + } + void destroy() { + if (Data) + unmap(Data, CapacityBytes); + } + T &operator[](uptr I) { + DCHECK_LT(I, Size); + return Data[I]; + } + const T &operator[](uptr I) const { + DCHECK_LT(I, Size); + return Data[I]; + } + void push_back(const T &Element) { + DCHECK_LE(Size, capacity()); + if (Size == capacity()) { + const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1); + reallocate(NewCapacity); + } + memcpy(&Data[Size++], &Element, sizeof(T)); + } + T &back() { + DCHECK_GT(Size, 0); + return Data[Size - 1]; + } + void pop_back() { + DCHECK_GT(Size, 0); + Size--; + } + uptr size() const { return Size; } + const T *data() const { return Data; } + T *data() { return Data; } + uptr capacity() const { return CapacityBytes / sizeof(T); } + void reserve(uptr NewSize) { + // Never downsize internal buffer. + if (NewSize > capacity()) + reallocate(NewSize); + } + void resize(uptr NewSize) { + if (NewSize > Size) { + reserve(NewSize); + memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); + } + Size = NewSize; + } + + void clear() { Size = 0; } + bool empty() const { return size() == 0; } + + const T *begin() const { return data(); } + T *begin() { return data(); } + const T *end() const { return data() + size(); } + T *end() { return data() + size(); } + +private: + void reallocate(uptr NewCapacity) { + DCHECK_GT(NewCapacity, 0); + DCHECK_LE(Size, NewCapacity); + const uptr NewCapacityBytes = + roundUpTo(NewCapacity * sizeof(T), getPageSizeCached()); + T *NewData = (T *)map(nullptr, NewCapacityBytes, "scudo:vector"); + if (Data) { + memcpy(NewData, Data, Size * sizeof(T)); + unmap(Data, CapacityBytes); + } + Data = NewData; + CapacityBytes = NewCapacityBytes; + } + + T *Data; + uptr CapacityBytes; + uptr Size; +}; + +template <typename T> class Vector : public VectorNoCtor<T> { +public: + Vector() { VectorNoCtor<T>::init(1); } + explicit Vector(uptr Count) { + VectorNoCtor<T>::init(Count); + this->resize(Count); + } + ~Vector() { VectorNoCtor<T>::destroy(); } + // Disallow copies and moves. + Vector(const Vector &) = delete; + Vector &operator=(const Vector &) = delete; + Vector(Vector &&) = delete; + Vector &operator=(Vector &&) = delete; +}; + +} // namespace scudo + +#endif // SCUDO_VECTOR_H_ |