[RFC] __builtin_dynamic_object_size with -D_FORTIFY_SOURCE=3

I tried to incorporate the __builtin_dynamic_object_size[1] builtin
available in clang to enhance _FORTIFY_SOURCE and was looking for some
early feedback so that I can incorporate it into the final patch that
I hope to come up with soon.

__builtin_dynamic_object_size
-----------------------------

__builtin_dynamic_object_size is intended to be a drop-in replacement
for __builtin_object_size (more on why it isn't at the moment, but
later) that goes a little further.  In addition to what
__builtin_object_size does, i.e. replace the builtin call with a
constant object size, __builtin_dynamic_object_size will replace the
call site with an expression that evaluates to the object size, thus
expanding its applicability by a bit.  In practice, it can find these
expressions through malloc/calloc calls earlier in the translation
unit.

A simple motivating example is below; -D_FORTIFY_SOURCE=2 would miss
this and emit memcpy, but -D_FORTIFY_SOURCE=3 with the help of
__builtin_dynamic_object_size is able to emit __memcpy_chk with the
allocation size expression passed into the function:

extern void *getmem (size_t);

void *copy_obj (const void *src, size_t alloc, size_t copysize)
{
  void *obj = malloc (alloc);
  memcpy (obj, src, copysize);

  return obj;
}

Note however that if the object was allocated elsewhere that the
compiler cannot see, or if it was allocated in the function with a
function that the compiler does not recognize as an allocator then
__builtin_dynamic_object_size also returns -1.

-D_FORTIFY_SOURCE=3
-------------------

I restricted usage of __builtin_dynamic_object_size to a new
_FORTIFY_SOURCE level because it has one fundamental difference from
the earlier level, which is that it can pass a variable to the _chk
function instead of constant.  As a result, 1 and 2 are fast with most
overhead being optimized out while 3 may have additional overhead.

For example at the moment the simple case of memcpy, memmove,
etc. where they're implemented with compiler builtins like
__builtin___memcpy_chk, clang is able to generate compact code that
passes the expression to __memcpy_chk or just generates a memcpy when
possible.  In the non-builtin cases though, where the size evaluates
to an expression, one may see patterns like:

	cmpq	$-1, %rbx
	je	.LBB0_2
	callq	fortified_chk
	jmp	.LBB0_3
.LBB0_2:                                # %if.else
	callq	fortified

since the compiler isn't smart enough yet to reduce that condition.
This can be fixed (I'm working on that right now) in the simple case
of a direct comparison and thus work for _FORTIFY_SOURCE=3, but it may
be harder to evaluate for __builtin_dynamic_object_size in general
where the comparison happens indirectly.  This is also why
__builtin_dynamic_object_size isn't exactly a drop-in replacement for
__builtin_object_size in all cases.

Outstanding Issues/RFC:
------------------

- As mentioned above, I'm trying to get clang to eliminate that
  conditional so that it can be applied more widely beyond to
  __builtin___func_chk like functions.  That hopefully won't be too
  hard.  However there is a risk that the llvm project rejects such a
  peephole optimisation; in that case would the additional overhead of
  the conditional be acceptable?  It is a separate fortify level, so
  it may be easier to justify.

- gcc does not support __builtin_dynamic_object_size yet.  Based on
  previous discussions[2] ISTM that the idea hasn't bee rejected
  outright, just that the gcc community would like to see a more
  detailed specification before committing to add it.  I think the
  glibc implementation will help us arrive at that, although there are
  issues beyond glibc usage of __builtin_dynamic_object_size or
  __builtin_object_size.  I hope to start discussions on this next
  year, nearer to the next gcc stage 1 open.

- The idea of -D_FORTIFY_SOURCE=3 is a beginning of a shift in design.
  This introduces hardening that could potentially have noticeable
  additional overhead at runtime.  It does expand coverage of
  fortification and there's potential for additional coverage on
  similar lines.  Is it enough to simply increment the fortify level
  or should this be a different feature macro altogether?  Maybe
  incrementing the fortify level is sufficient but we need some
  additional space to grow static checks, i.e. start dynamic checks
  from -D_FORTIFY_SOURCE=9?  Or any other concerns regarding where
  such checks ought to fit in?

[1] https://reviews.llvm.org/D56760
[2] https://gcc.gnu.org/legacy-ml/gcc/2019-01/msg00188.html
---
 include/features.h              |  6 +++---
 misc/sys/cdefs.h                |  9 +++++++++
 string/bits/string_fortified.h  | 24 ++++++++++++------------
 string/bits/strings_fortified.h |  4 ++--
 4 files changed, 26 insertions(+), 17 deletions(-)

* Siddhesh Poyarekar:

> -D_FORTIFY_SOURCE=3
> -------------------
>
> I restricted usage of __builtin_dynamic_object_size to a new
> _FORTIFY_SOURCE level because it has one fundamental difference from
> the earlier level, which is that it can pass a variable to the _chk
> function instead of constant.  As a result, 1 and 2 are fast with most
> overhead being optimized out while 3 may have additional overhead.
>
> For example at the moment the simple case of memcpy, memmove,
> etc. where they're implemented with compiler builtins like
> __builtin___memcpy_chk, clang is able to generate compact code that
> passes the expression to __memcpy_chk or just generates a memcpy when
> possible.  In the non-builtin cases though, where the size evaluates
> to an expression, one may see patterns like:
>
> 	cmpq	$-1, %rbx
> 	je	.LBB0_2
> 	callq	fortified_chk
> 	jmp	.LBB0_3
> .LBB0_2:                                # %if.else
> 	callq	fortified
>
> since the compiler isn't smart enough yet to reduce that condition.
> This can be fixed (I'm working on that right now) in the simple case
> of a direct comparison and thus work for _FORTIFY_SOURCE=3, but it may
> be harder to evaluate for __builtin_dynamic_object_size in general
> where the comparison happens indirectly.  This is also why
> __builtin_dynamic_object_size isn't exactly a drop-in replacement for
> __builtin_object_size in all cases.

I think this should be fixed in the compiler, and the level 3 should be
dropped.  A compiler bug is not a good reason to change the external
interface, especially if it is just a performance bug.  The 2 vs 3
choice isn't something that's useful to developers.

Thanks,
Florian

On Mon, Nov 30, 2020 at 10:11:51AM +0100, Florian Weimer wrote:
> > For example at the moment the simple case of memcpy, memmove,
> > etc. where they're implemented with compiler builtins like
> > __builtin___memcpy_chk, clang is able to generate compact code that
> > passes the expression to __memcpy_chk or just generates a memcpy when
> > possible.  In the non-builtin cases though, where the size evaluates
> > to an expression, one may see patterns like:
> >
> > 	cmpq	$-1, %rbx
> > 	je	.LBB0_2
> > 	callq	fortified_chk
> > 	jmp	.LBB0_3
> > .LBB0_2:                                # %if.else
> > 	callq	fortified
> >
> > since the compiler isn't smart enough yet to reduce that condition.
> > This can be fixed (I'm working on that right now) in the simple case
> > of a direct comparison and thus work for _FORTIFY_SOURCE=3, but it may
> > be harder to evaluate for __builtin_dynamic_object_size in general
> > where the comparison happens indirectly.  This is also why
> > __builtin_dynamic_object_size isn't exactly a drop-in replacement for
> > __builtin_object_size in all cases.
> 
> I think this should be fixed in the compiler, and the level 3 should be
> dropped.  A compiler bug is not a good reason to change the external
> interface, especially if it is just a performance bug.  The 2 vs 3
> choice isn't something that's useful to developers.

What bug do you mean?  The fact that __builtin_object_size is required to be
a constant has been a fundamental requirement of the whole _FORTIFY_SOURCE
design.  Without that, it adds completely unbounded runtime overhead,
turning the program ultimately into yet another bounded pointers
implementation.  In the worst case, every pointer arithmetic will need to be
accomodated by tracking of its runtime length, using maximum/minimum,
saturated arithmetics etc.

Consider just for a start e.g.

#include <stdlib.h>
void foo (void *, void *, void *);

size_t
bar (size_t x, size_t y, size_t z, size_t w, size_t v)
{
  char *p = malloc (x + 15);
  char *q = calloc (y + 12, z + 31);
  char *r = w ? p : q;
  if (v > 23)
    r += v;
  foo (r, p, q);
  size_t ret = __builtin_dynamic_object_size (r, 0);
  free (p);
  free (q);
  return ret;
}

LLVM seems to handle this as adding
  size_t len1 = x + 15;
  size_t len2 = (y + 12) * (z + 31);
/* Note, no overflow checking here, though as calloc would return NULL
   perhaps it is not needed.  */
  size_t len3 = w ? len1 : len2;
  size_t len4 = v > 23 ? (len3 - 23 /* saturating */) : len3;
Now consider the involved pointer to be conditionally incremented in some
loop...

__builtin_object_size is only exact if 0 mode returns the same value as
2 mode (or 1 vs. 3), otherwise it is an upper bound,
__builtin_dynamic_object_size is bounded pointer implementation (for
selected pointers).

I think users should have a choice whether they want up to 2x slowdown in
their code or not.

	Jakub

On 11/30/20 2:41 PM, Florian Weimer via Libc-alpha wrote:
> * Siddhesh Poyarekar:
> 
>> -D_FORTIFY_SOURCE=3
>> -------------------
>>
>> I restricted usage of __builtin_dynamic_object_size to a new
>> _FORTIFY_SOURCE level because it has one fundamental difference from
>> the earlier level, which is that it can pass a variable to the _chk
>> function instead of constant.  As a result, 1 and 2 are fast with most
>> overhead being optimized out while 3 may have additional overhead.
>>
>> For example at the moment the simple case of memcpy, memmove,
>> etc. where they're implemented with compiler builtins like
>> __builtin___memcpy_chk, clang is able to generate compact code that
>> passes the expression to __memcpy_chk or just generates a memcpy when
>> possible.  In the non-builtin cases though, where the size evaluates
>> to an expression, one may see patterns like:
>>
>> 	cmpq	$-1, %rbx
>> 	je	.LBB0_2
>> 	callq	fortified_chk
>> 	jmp	.LBB0_3
>> .LBB0_2:                                # %if.else
>> 	callq	fortified
>>
>> since the compiler isn't smart enough yet to reduce that condition.
>> This can be fixed (I'm working on that right now) in the simple case
>> of a direct comparison and thus work for _FORTIFY_SOURCE=3, but it may
>> be harder to evaluate for __builtin_dynamic_object_size in general
>> where the comparison happens indirectly.  This is also why
>> __builtin_dynamic_object_size isn't exactly a drop-in replacement for
>> __builtin_object_size in all cases.
> 
> I think this should be fixed in the compiler, and the level 3 should be
> dropped.  A compiler bug is not a good reason to change the external
> interface, especially if it is just a performance bug.  The 2 vs 3
> choice isn't something that's useful to developers.

Besides the bug, do you think a performance tradeoff should result in us 
having this 2 vs 3 differentiation?  I didn't make the 2 vs 3 proposal 
specifically to work around this bug although though it does make it 
easier for us to add support into glibc without blocking on llvm fixing 
it.  In general, dynamic object size checks may end up having an 
additional performance tradeoff (even __bdos without this bug will have 
additional instructions emitted, perhaps even spills, making them a wee 
bit slower) and it may be desirable to have a separate fortification 
level to allow developers to choose.

Siddhesh

* Siddhesh Poyarekar:

> Besides the bug, do you think a performance tradeoff should result in
> us having this 2 vs 3 differentiation?  I didn't make the 2 vs 3
> proposal specifically to work around this bug although though it does
> make it easier for us to add support into glibc without blocking on
> llvm fixing it.  In general, dynamic object size checks may end up
> having an additional performance tradeoff (even __bdos without this
> bug will have additional instructions emitted, perhaps even spills,
> making them a wee bit slower) and it may be desirable to have a
> separate fortification level to allow developers to choose.

I really dislike more developer choices.  I think we should experiment
with this with a fixed Clang, and see what the generated code looks like
in practice.

Thanks,
Florian

* Jakub Jelinek:

> On Mon, Nov 30, 2020 at 10:11:51AM +0100, Florian Weimer wrote:
>> > For example at the moment the simple case of memcpy, memmove,
>> > etc. where they're implemented with compiler builtins like
>> > __builtin___memcpy_chk, clang is able to generate compact code that
>> > passes the expression to __memcpy_chk or just generates a memcpy when
>> > possible.  In the non-builtin cases though, where the size evaluates
>> > to an expression, one may see patterns like:
>> >
>> > 	cmpq	$-1, %rbx
>> > 	je	.LBB0_2
>> > 	callq	fortified_chk
>> > 	jmp	.LBB0_3
>> > .LBB0_2:                                # %if.else
>> > 	callq	fortified
>> >
>> > since the compiler isn't smart enough yet to reduce that condition.
>> > This can be fixed (I'm working on that right now) in the simple case
>> > of a direct comparison and thus work for _FORTIFY_SOURCE=3, but it may
>> > be harder to evaluate for __builtin_dynamic_object_size in general
>> > where the comparison happens indirectly.  This is also why
>> > __builtin_dynamic_object_size isn't exactly a drop-in replacement for
>> > __builtin_object_size in all cases.
>> 
>> I think this should be fixed in the compiler, and the level 3 should be
>> dropped.  A compiler bug is not a good reason to change the external
>> interface, especially if it is just a performance bug.  The 2 vs 3
>> choice isn't something that's useful to developers.
>
> What bug do you mean?

The pointless run-time check to choose between the _chk and non-_chk
variants.

> The fact that __builtin_object_size is required to be a constant has
> been a fundamental requirement of the whole _FORTIFY_SOURCE design.
> Without that, it adds completely unbounded runtime overhead, turning
> the program ultimately into yet another bounded pointers
> implementation.  In the worst case, every pointer arithmetic will need
> to be accomodated by tracking of its runtime length, using
> maximum/minimum, saturated arithmetics etc.

Let's see if there is an actual performance impact for Clang.

I think it's wrong to view this in isolation.  Of course there will be
regressions for certain code sequences.  But glibc will use this in
conjunction with string functions, which already trigger heavy
optimization from GCC with lots of code duplication.

The Clang implementation, once fixed, will give us a way to experiment
with this.

Maybe some trade-offs are possible: Track just the end of the allocated
buffer, at the cost of some accuracy.  Then intermediate pointer
arithmetic does not have to be instrumented.

Thanks,
Florian

On Mon, Nov 30, 2020 at 11:10:56AM +0100, Florian Weimer wrote:
> I think it's wrong to view this in isolation.  Of course there will be
> regressions for certain code sequences.  But glibc will use this in
> conjunction with string functions, which already trigger heavy
> optimization from GCC with lots of code duplication.
> 
> The Clang implementation, once fixed, will give us a way to experiment
> with this.
> 
> Maybe some trade-offs are possible: Track just the end of the allocated
> buffer, at the cost of some accuracy.  Then intermediate pointer
> arithmetic does not have to be instrumented.

There is no "the allocated buffer", a pointer may point to many different
ones and which ones depends on the control flow etc. and for each of the
allocations there could be different pointer arithmetics involved, in both
directions.  As can be seen e.g. on following example, LLVM really does
implement it as bounded pointers, the sizes are then precise, but the
runtime cost is high.  There is no limit it to simple most common cases.

typedef __SIZE_TYPE__ size_t;
void *malloc (size_t);
void free (void *);

int
foo (int p[128], int q)
{
  char *r = malloc (q);
  for (int i = 0; i < 64; i++)
    {
      if (p[i])
        r += p[64 + i];
    }
  size_t ret = __builtin_dynamic_object_size (r, 0);
  free (r);
  return ret;
}

Actually, trying:

typedef __SIZE_TYPE__ size_t;
void *malloc (size_t);
void free (void *);

int
bar (int p[192], int q, char *s)
{
  char *r = malloc (q);
  for (int i = 0; i < 64; i++)
    {
      if (p[i])
        r += p[64 + i];
      if (p[128 + i])
	r = s;
    }
  size_t ret = __builtin_dynamic_object_size (r, 0);
  free (r);
  return ret;
}

in that case LLVM gives up, so maybe it does the tracking only
if all the possible values have some known object size.
Even with the above foo test where r can have (expensively computed)
precise value, if one e.g. add char *s argument and uses
s ? s : r in __builtin_dynamic_object_size, it just returns -1.

	Jakub

On Mon, Nov 30, 2020 at 11:06:47AM +0100, Florian Weimer wrote:
> * Siddhesh Poyarekar:
> 
> > Besides the bug, do you think a performance tradeoff should result in
> > us having this 2 vs 3 differentiation?  I didn't make the 2 vs 3
> > proposal specifically to work around this bug although though it does
> > make it easier for us to add support into glibc without blocking on
> > llvm fixing it.  In general, dynamic object size checks may end up
> > having an additional performance tradeoff (even __bdos without this
> > bug will have additional instructions emitted, perhaps even spills,
> > making them a wee bit slower) and it may be desirable to have a
> > separate fortification level to allow developers to choose.
> 
> I really dislike more developer choices.  I think we should experiment
> with this with a fixed Clang, and see what the generated code looks like
> in practice.

I think it is very important to give developers a choice.  Because,
otherwise if the dynamic bounded pointers tracking is too costly for them,
they will disable all fortification, even the cheap ones, which will in the
end be worse for security.

	Jakub