clang/docs/BoundsSafetyImplPlans.rst

   1 ============================================
   2 Implementation plans for ``-fbounds-safety``
   3 ============================================
   4
   5 .. contents::
   6    :local:
   7
   8 Gradual updates with experimental flag
   9 ======================================
  10
  11 The feature will be implemented as a series of smaller PRs and we will guard our
  12 implementation with an experimental flag ``-fexperimental-bounds-safety`` until
  13 the usable model is fully available. Once the model is ready for use, we will
  14 expose the flag ``-fbounds-safety``.
  15
  16 Possible patch sets
  17 -------------------
  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 divided
  23   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 also
  26   be divided into multiple sub-PRs).
  27
  28 Proposed implementation
  29 =======================
  30
  31 External bounds annotations
  32 ---------------------------
  33
  34 The bounds annotations are C type attributes appertaining to pointer types. If
  35 an attribute is added to the position of a declaration attribute, e.g., ``int
  36 *ptr __counted_by(size)``, the attribute appertains to the outermost pointer
  37 type of the declaration (``int *``).
  38
  39 New sugar types
  40 ---------------
  41
  42 An external bounds annotation creates a type sugar of the underlying pointer
  43 types. We will introduce a new sugar type, ``DynamicBoundsPointerType`` to
  44 represent ``__counted_by`` or ``__sized_by``. Using ``AttributedType`` would not
  45 be sufficient because the type needs to hold the count or size expression as
  46 well as some metadata necessary for analysis, while this type may be implemented
  47 through inheritance from ``AttributedType``. Treating the annotations as type
  48 sugars means two types with incompatible external bounds annotations may be
  49 considered canonically the same types. This is sometimes necessary, for example,
  50 to make the ``__counted_by`` and friends not participate in function
  51 overloading. However, this design requires a separate logic to walk through the
  52 entire type hierarchy to check type compatibility of bounds annotations.
  53
  54 Late parsing for C
  55 ------------------
  56
  57 A bounds annotation such as ``__counted_by(count)`` can be added to type of a
  58 struct field declaration where count is another field of the same struct
  59 declared later. Similarly, the annotation may apply to type of a function
  60 parameter declaration which precedes the parameter count in the same function.
  61 This means parsing the argument of bounds annotations must be done after the
  62 parser has the whole context of a struct or a function declaration. Clang has
  63 late parsing logic for C++ declaration attributes that require late parsing,
  64 while the C declaration attributes and C/C++ type attributes do not have the
  65 same logic. This requires introducing late parsing logic for C/C++ type
  66 attributes.
  67
  68 Internal bounds annotations
  69 ---------------------------
  70
  71 ``__indexable`` and ``__bidi_indexable`` alter pointer representations to be
  72 equivalent to a struct with the pointer and the corresponding bounds fields.
  73 Despite this difference in their representations, they are still pointers in
  74 terms of types of operations that are allowed and their semantics. For instance,
  75 a pointer dereference on a ``__bidi_indexable`` pointer will return the
  76 dereferenced value same as plain C pointers, modulo the extra bounds checks
  77 being performed before dereferencing the wide pointer. This means mapping the
  78 wide pointers to struct types with equivalent layout won’t be sufficient. To
  79 represent the wide pointers in Clang AST, we add an extra field in the
  80 PointerType class to indicate the internal bounds of the pointer. This ensures
  81 pointers of different representations are mapped to different canonical types
  82 while they are still treated as pointers.
  83
  84 In LLVM IR, wide pointers will be emitted as structs of equivalent
  85 representations. Clang CodeGen will handle them as Aggregate in
  86 ``TypeEvaluationKind (TEK)``. ``AggExprEmitter`` was extended to handle pointer
  87 operations returning wide pointers. Alternatively, a new ``TEK`` and an
  88 expression emitter dedicated to wide pointers could be introduced.
  89
  90 Default bounds annotations
  91 --------------------------
  92
  93 The model may implicitly add ``__bidi_indexable`` or ``__single`` depending on
  94 the context of the declaration that has the pointer type. ``__bidi_indexable``
  95 implicitly adds to local variables, while ``__single`` implicitly adds to
  96 pointer types specifying struct fields, function parameters, or global
  97 variables. This means the parser may first create the pointer type without any
  98 default pointer attribute and then recreate the type once the parser has the
  99 declaration context and determined the default attribute accordingly.
 100
 101 This also requires the parser to reset the type of the declaration with the
 102 newly created type with the right default attribute.
 103
 104 Promotion expression
 105 --------------------
 106
 107 A new expression will be introduced to represent the conversion from a pointer
 108 with an external bounds annotation, such as ``__counted_by``, to
 109 ``__bidi_indexable``. This type of conversion cannot be handled by normal
 110 CastExprs because it requires an extra subexpression(s) to provide the bounds
 111 information necessary to create a wide pointer.
 112
 113 Bounds check expression
 114 -----------------------
 115
 116 Bounds checks are part of semantics defined in the ``-fbounds-safety`` language
 117 model. Hence, exposing the bounds checks and other semantic actions in the AST
 118 is desirable. A new expression for bounds checks has been added to the AST. The
 119 bounds check expression has a ``BoundsCheckKind`` to indicate the kind of checks
 120 and has the additional sub-expressions that are necessary to perform the check
 121 according to the kind.
 122
 123 Paired assignment check
 124 -----------------------
 125
 126 ``-fbounds-safety`` enforces that variables or fields related with the same
 127 external bounds annotation (e.g., ``buf`` and ``count`` related with
 128 ``__counted_by`` in the example below) must be updated side by side within the
 129 same basic block and without side effect in between.
 130
 131 .. code-block:: c
 132
 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, sized_t nelems) {
 138       sbuf->buf = (int *)malloc(sizeof(int) * nelems);
 139       sbuf->count = nelems;
 140    }
 141
 142 To implement this rule, the compiler requires a linear representation of
 143 statements to understand the ordering and the adjacency between the two or more
 144 assignments. The Clang CFG is used to implement this analysis as Clang CFG
 145 provides a linear view of statements within each ``CFGBlock`` (Clang
 146 ``CFGBlock`` represents a single basic block in a source-level CFG).
 147
 148 Bounds check optimizations
 149 --------------------------
 150
 151 In ``-fbounds-safety``, the Clang frontend emits run-time checks for every
 152 memory dereference if the type system or analyses in the frontend couldn’t
 153 verify its bounds safety. The implementation relies on LLVM optimizations to
 154 remove redundant run-time checks. Using this optimization strategy, if the
 155 original source code already has bounds checks, the fewer additional checks
 156 ``-fbounds-safety`` will introduce. The LLVM ``ConstraintElimination`` pass is
 157 design to remove provable redundant checks (please check Florian Hahn’s
 158 presentation in 2021 LLVM Dev Meeting and the implementation to learn more). In
 159 the following example, ``-fbounds-safety`` implicitly adds the redundant bounds
 160 checks that the optimizer can remove:
 161
 162 .. code-block:: c
 163
 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 the
 173 bounds 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 deterministically
 178   two’s complement computation, not an undefined behavior. Therefore,
 179   getelementptr does not typically have inbounds keyword. However, the compiler
 180   does emit inbounds for ``p + count`` in this case because
 181   ``__counted_by(count)`` has the invariant that p has at least as many as
 182   elements as count. Using this information, ``ConstraintElimination`` is able
 183   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 subsequent
 187   optimization passes can remove.
 188
 189 ``OptRemarks`` can be utilized to provide insights into performance tuning. It
 190 has the capability to report on checks that it cannot eliminate, possibly with
 191 reasons, allowing programmers to adjust their code to unlock further
 192 optimizations.
 193
 194 Debugging
 195 =========
 196
 197 Internal bounds annotations
 198 ---------------------------
 199
 200 Internal bounds annotations change a pointer into a wide pointer. The debugger
 201 needs to understand that wide pointers are essentially pointers with a struct
 202 layout. To handle this, a wide pointer is described as a record type in the
 203 debug info. The type name has a special name prefix (e.g.,
 204 ``__bounds_safety$bidi_indexable``) which can be recognized by a debug info
 205 consumer to provide support that goes beyond showing the internal structure of
 206 the wide pointer. There are no DWARF extensions needed to support wide pointers.
 207 In our implementation, LLDB recognizes wide pointer types by name and
 208 reconstructs them as wide pointer Clang AST types for use in the expression
 209 evaluator.
 210
 211 External bounds annotations
 212 ---------------------------
 213
 214 Similar to internal bounds annotations, external bound annotations are described
 215 as a typedef to their underlying pointer type in the debug info, and the bounds
 216 are encoded as strings in the typedef’s name (e.g.,
 217 ``__bounds_safety$counted_by:N``).
 218
 219 Recognizing ``-fbounds-safety`` traps
 220 -------------------------------------
 221
 222 Clang emits debug info for ``-fbounds-safety`` traps as inlined functions, where
 223 the function name encodes the error message. LLDB implements a frame recognizer
 224 to surface a human-readable error cause to the end user. A debug info consumer
 225 that is unaware of this sees an inlined function whose name encodes an error
 226 message (e.g., : ``__bounds_safety$Bounds check failed``).
 227
 228 Expression Parsing
 229 ------------------
 230
 231 In our implementation, LLDB’s expression evaluator does not enable the
 232 ``-fbounds-safety`` language option because it’s currently unable to fully
 233 reconstruct the pointers with external bounds annotations, and also because the
 234 evaluator operates in C++ mode, utilizing C++ reference types, while
 235 ``-fbounds-safety`` does not currently support C++. This means LLDB’s expression
 236 evaluator can only evaluate a subset of the ``-fbounds-safety`` language model.
 237 Specifically, it’s capable of evaluating the wide pointers that already exist in
 238 the source code. All other expressions are evaluated according to C/C++
 239 semantics.
 240
 241 C++ support
 242 ===========
 243
 244 C++ has multiple options to write code in a bounds-safe manner, such as
 245 following the bounds-safety core guidelines and/or using hardened libc++ along
 246 with the `C++ Safe Buffer model
 247 <https://discourse.llvm.org/t/rfc-c-buffer-hardening/65734>`_. However, these
 248 techniques may require ABI changes and may not be applicable to code
 249 interoperating with C. When the ABI of an existing program needs to be preserved
 250 and for headers shared between C and C++, ``-fbounds-safety`` offers a potential
 251 solution.
 252
 253 ``-fbounds-safety`` is not currently supported in C++, but we believe the
 254 general approach would be applicable for future efforts.