[libc++][hardening] Categorize assertions related to strict weak ordering (#77405) If a user passes a comparator that doesn't satisfy strict weak ordering (see https://eel.is/c++draft/algorithms#alg.sorting.general) to a sorting algorithm, the algorithm can produce an incorrect result or even lead to an out-of-bounds access. Unfortunately, comprehensively validating that a given comparator indeed satisfies the strict weak ordering requirement is prohibitively expensive (see [the related RFC](https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217)). As a result, we have three independent sets of checks: - assertions that catch out-of-bounds accesses within the algorithms' implementation. These are relatively cheap; however, they cannot catch the underlying cause and cannot prevent the case where an invalid comparator would result in an incorrectly-sorted sequence without actually triggering an OOB access; - debug comparators that wrap a given comparator and on each comparison check that if `(a < b)`, then `!(b < a)`, where `<` stands for the user-provided comparator. This performs up to 2x number of comparisons but doesn't affect the algorithmic complexity. While this approach can find more issues, it is still a heuristic; - a comprehensive check of the comparator that validates up to 100 elements in the resulting sorted sequence (see the RFC above for details). The check is expensive but the 100 element limit can somewhat compensate for that, especially for large values of `N`. The first set of checks is enabled in the fast hardening mode while the other two are only enabled in the debug mode. This patch also removes the `_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK` macro that previously was used to selectively enable the 100-element check. Now this check is enabled unconditionally in the debug mode. Also, introduce a new category `_LIBCPP_ASSERT_SEMANTIC_REQUIREMENT`. This category is intended for checking the semantic requirements from the Standard. Typically, these are hard or impossible to completely validate, so these checks are expected to be heuristic in nature and potentially quite expensive. See https://reviews.llvm.org/D150264 for additional background. Fixes #71496
Welcome to the LLVM project!
This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.
C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.
Other components include: the libc++ C++ standard library, the LLD linker, and more.
Consult the Getting Started with LLVM page for information on building and running LLVM.
For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.
Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.
The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.