255 lines · plain
1============================================2Implementation plans for ``-fbounds-safety``3============================================4 5.. contents::6 :local:7 8Gradual updates with experimental flag9======================================10 11The feature will be implemented as a series of smaller PRs and we will guard our12implementation with an experimental flag ``-fexperimental-bounds-safety`` until13the usable model is fully available. Once the model is ready for use, we will14expose the flag ``-fbounds-safety``.15 16Possible patch sets17-------------------18 19* External bounds annotations and the (late) parsing logic.20* Internal bounds annotations (wide pointers) and their parsing logic.21* Clang code generation for wide pointers with debug information.22* Pointer cast semantics involving bounds annotations (this could be divided23 into multiple sub-PRs).24* CFG analysis for pairs of related pointer and count assignments and the likes.25* Bounds check expressions in AST and the Clang code generation (this could also26 be divided into multiple sub-PRs).27 28Proposed implementation29=======================30 31External bounds annotations32---------------------------33 34The bounds annotations are C type attributes appertaining to pointer types. If35an attribute is added to the position of a declaration attribute, e.g., ``int36*ptr __counted_by(size)``, the attribute appertains to the outermost pointer37type of the declaration (``int *``).38 39New sugar types40---------------41 42An external bounds annotation creates a type sugar of the underlying pointer43types. We will introduce a new sugar type, ``DynamicBoundsPointerType`` to44represent ``__counted_by`` or ``__sized_by``. Using ``AttributedType`` would not45be sufficient because the type needs to hold the count or size expression as46well as some metadata necessary for analysis, while this type may be implemented47through inheritance from ``AttributedType``. Treating the annotations as type48sugars means two types with incompatible external bounds annotations may be49considered canonically the same types. This is sometimes necessary, for example,50to make the ``__counted_by`` and friends not participate in function51overloading. However, this design requires a separate logic to walk through the52entire type hierarchy to check type compatibility of bounds annotations.53 54Late parsing for C55------------------56 57A bounds annotation such as ``__counted_by(count)`` can be added to type of a58struct field declaration where count is another field of the same struct59declared later. Similarly, the annotation may apply to type of a function60parameter declaration which precedes the parameter count in the same function.61This means parsing the argument of bounds annotations must be done after the62parser has the whole context of a struct or a function declaration. Clang has63late parsing logic for C++ declaration attributes that require late parsing,64while the C declaration attributes and C/C++ type attributes do not have the65same logic. This requires introducing late parsing logic for C/C++ type66attributes.67 68Internal bounds annotations69---------------------------70 71``__indexable`` and ``__bidi_indexable`` alter pointer representations to be72equivalent to a struct with the pointer and the corresponding bounds fields.73Despite this difference in their representations, they are still pointers in74terms of types of operations that are allowed and their semantics. For instance,75a pointer dereference on a ``__bidi_indexable`` pointer will return the76dereferenced value same as plain C pointers, modulo the extra bounds checks77being performed before dereferencing the wide pointer. This means mapping the78wide pointers to struct types with equivalent layout won’t be sufficient. To79represent the wide pointers in Clang AST, we add an extra field in the80PointerType class to indicate the internal bounds of the pointer. This ensures81pointers of different representations are mapped to different canonical types82while they are still treated as pointers.83 84In LLVM IR, wide pointers will be emitted as structs of equivalent85representations. Clang CodeGen will handle them as Aggregate in86``TypeEvaluationKind (TEK)``. ``AggExprEmitter`` was extended to handle pointer87operations returning wide pointers. Alternatively, a new ``TEK`` and an88expression emitter dedicated to wide pointers could be introduced.89 90Default bounds annotations91--------------------------92 93The model may implicitly add ``__bidi_indexable`` or ``__single`` depending on94the context of the declaration that has the pointer type. ``__bidi_indexable``95implicitly adds to local variables, while ``__single`` implicitly adds to96pointer types specifying struct fields, function parameters, or global97variables. This means the parser may first create the pointer type without any98default pointer attribute and then recreate the type once the parser has the99declaration context and determined the default attribute accordingly.100 101This also requires the parser to reset the type of the declaration with the102newly created type with the right default attribute.103 104Promotion expression105--------------------106 107A new expression will be introduced to represent the conversion from a pointer108with an external bounds annotation, such as ``__counted_by``, to109``__bidi_indexable``. This type of conversion cannot be handled by normal110CastExprs because it requires an extra subexpression(s) to provide the bounds111information necessary to create a wide pointer.112 113Bounds check expression114-----------------------115 116Bounds checks are part of semantics defined in the ``-fbounds-safety`` language117model. Hence, exposing the bounds checks and other semantic actions in the AST118is desirable. A new expression for bounds checks has been added to the AST. The119bounds check expression has a ``BoundsCheckKind`` to indicate the kind of checks120and has the additional sub-expressions that are necessary to perform the check121according to the kind.122 123Paired assignment check124-----------------------125 126``-fbounds-safety`` enforces that variables or fields related with the same127external bounds annotation (e.g., ``buf`` and ``count`` related with128``__counted_by`` in the example below) must be updated side by side within the129same basic block and without side effect in between.130 131.. code-block:: c132 133 typedef struct {134 int *__counted_by(count) buf; size_t count;135 } sized_buf_t;136 137 void alloc_buf(sized_buf_t *sbuf, size_t nelems) {138 sbuf->buf = (int *)malloc(sizeof(int) * nelems);139 sbuf->count = nelems;140 }141 142To implement this rule, the compiler requires a linear representation of143statements to understand the ordering and the adjacency between the two or more144assignments. The Clang CFG is used to implement this analysis as Clang CFG145provides a linear view of statements within each ``CFGBlock`` (Clang146``CFGBlock`` represents a single basic block in a source-level CFG).147 148Bounds check optimizations149--------------------------150 151In ``-fbounds-safety``, the Clang frontend emits run-time checks for every152memory dereference if the type system or analyses in the frontend couldn’t153verify its bounds safety. The implementation relies on LLVM optimizations to154remove redundant run-time checks. Using this optimization strategy, if the155original source code already has bounds checks, the fewer additional checks156``-fbounds-safety`` will introduce. The LLVM ``ConstraintElimination`` pass is157designed to remove provable redundant checks (please check Florian Hahn’s158presentation in 2021 LLVM Dev Meeting and the implementation to learn more). In159the following example, ``-fbounds-safety`` implicitly adds the redundant bounds160checks that the optimizer can remove:161 162.. code-block:: c163 164 void fill_array_with_indices(int *__counted_by(count) p, size_t count) {165 for (size_t i = 0; i < count; ++i) {166 // implicit bounds checks:167 // if (p + i < p || p + i + 1 > p + count) trap();168 p[i] = i;169 }170 }171 172``ConstraintElimination`` collects the following facts and determines if the173bounds checks can be safely removed:174 175* Inside the for-loop, ``0 <= i < count``, hence ``1 <= i + 1 <= count``.176* Pointer arithmetic ``p + count`` in the if-condition doesn’t wrap.177* ``-fbounds-safety`` treats pointer arithmetic overflow as deterministically178 two’s complement computation, not an undefined behavior. Therefore,179 getelementptr does not typically have inbounds keyword. However, the compiler180 does emit inbounds for ``p + count`` in this case because181 ``__counted_by(count)`` has the invariant that p has at least as many as182 elements as count. Using this information, ``ConstraintElimination`` is able183 to determine ``p + count`` doesn’t wrap.184* Accordingly, ``p + i`` and ``p + i + 1`` also don’t wrap.185* Therefore, ``p <= p + i`` and ``p + i + 1 <= p + count``.186* The if-condition simplifies to false and becomes dead code that the subsequent187 optimization passes can remove.188 189``OptRemarks`` can be utilized to provide insights into performance tuning. It190has the capability to report on checks that it cannot eliminate, possibly with191reasons, allowing programmers to adjust their code to unlock further192optimizations.193 194Debugging195=========196 197Internal bounds annotations198---------------------------199 200Internal bounds annotations change a pointer into a wide pointer. The debugger201needs to understand that wide pointers are essentially pointers with a struct202layout. To handle this, a wide pointer is described as a record type in the203debug info. The type name has a special name prefix (e.g.,204``__bounds_safety$bidi_indexable``) which can be recognized by a debug info205consumer to provide support that goes beyond showing the internal structure of206the wide pointer. There are no DWARF extensions needed to support wide pointers.207In our implementation, LLDB recognizes wide pointer types by name and208reconstructs them as wide pointer Clang AST types for use in the expression209evaluator.210 211External bounds annotations212---------------------------213 214Similar to internal bounds annotations, external bound annotations are described215as a typedef to their underlying pointer type in the debug info, and the bounds216are encoded as strings in the typedef’s name (e.g.,217``__bounds_safety$counted_by:N``).218 219Recognizing ``-fbounds-safety`` traps220-------------------------------------221 222Clang emits debug info for ``-fbounds-safety`` traps as inlined functions, where223the function name encodes the error message. LLDB implements a frame recognizer224to surface a human-readable error cause to the end user. A debug info consumer225that is unaware of this sees an inlined function whose name encodes an error226message (e.g., : ``__bounds_safety$Bounds check failed``).227 228Expression Parsing229------------------230 231In our implementation, LLDB’s expression evaluator does not enable the232``-fbounds-safety`` language option because it’s currently unable to fully233reconstruct the pointers with external bounds annotations, and also because the234evaluator operates in C++ mode, utilizing C++ reference types, while235``-fbounds-safety`` does not currently support C++. This means LLDB’s expression236evaluator can only evaluate a subset of the ``-fbounds-safety`` language model.237Specifically, it’s capable of evaluating the wide pointers that already exist in238the source code. All other expressions are evaluated according to C/C++239semantics.240 241C++ support242===========243 244C++ has multiple options to write code in a bounds-safe manner, such as245following the bounds-safety core guidelines and/or using hardened libc++ along246with the `C++ Safe Buffer model247<https://discourse.llvm.org/t/rfc-c-buffer-hardening/65734>`_. However, these248techniques may require ABI changes and may not be applicable to code249interoperating with C. When the ABI of an existing program needs to be preserved250and for headers shared between C and C++, ``-fbounds-safety`` offers a potential251solution.252 253``-fbounds-safety`` is not currently supported in C++, but we believe the254general approach would be applicable for future efforts.255