Re: [PATCH] warn on returning alloca and VLA (PR 71924, 90549)

[Jeff Law <law@redhat.com>]

On 6/3/19 3:37 AM, Richard Biener wrote:
> On Fri, May 31, 2019 at 5:35 PM Jeff Law <law@redhat.com> wrote:>
>> On 5/30/19 4:56 PM, Martin Sebor wrote:
>>> On 5/30/19 10:15 AM, Jeff Law wrote:
>>>> On 5/30/19 9:34 AM, Martin Sebor wrote:
>>>>
>>>>>>> If the alias oracle can be used to give the same results without
>>>>>>> excessive false positives then I think it would be fine to make
>>>>>>> use of it.  Is that something you consider a prerequisite for
>>>>>>> this change or should I look into it as a followup?
>>>>>> I think we should explore it a bit before making a final decision.  It
>>>>>> may guide us for other work in this space (like detecting escaping
>>>>>> locals).   I think a dirty prototype to see if it's even in the right
>>>>>> ballpark would make sense.
>>>>>
>>>>> Okay, let me look into it.
>>>> Sounds good.  Again, go with a quick prototype to see if it's likely
>>>> feasible.  The tests you've added should dramatically help evaluating if
>>>> the oracle is up to the task.
>>>
>>> So to expand on what I said on the phone when we spoke: the problem
>>> I quickly ran into with the prototype is that I wasn't able to find
>>> a way to identify pointers to alloca/VLA storage.
>> Your analysis matches my very quick read of the aliasing code.  It may
>> be the case that the Steensgaard patent got in the way here.
>>
>>>
>>> In the the points-to solution for the pointer being returned they
>>> both have the vars_contains_escaped_heap flag set.  That seems like
>>> an omission that shouldn't be hard to fix, but on its own, I don't
>>> think it would be sufficient.
>> RIght.  In theory the result of an alloca call shouldn't alias anything
>> in the heap -- but there were some implementations of alloca that were
>> built on top of malloc (ugh).  That flag may be catering to that case.
>>
>> But in the case of a __builtin_alloca that shouldn't apply.  Hmm.  That
>> ultimately might be a bug.
>>
>>>
>>> In the IL a VLA is represented as a pointer to an array, but when
>>> returning a pointer into a VLA (at some offset so it's an SSA_NAME),
>>> the pointer's point-to solution doesn't include the VLA pointer or
>>> (AFAICS) make it possible to tell even that it is a VLA.  For example
>>> here:
>>>
>>>   f (int n)
>>>   {
>>>     int * p;
>>>     int[0:D.1912] * a.1;
>>>     sizetype _1;
>>>     void * saved_stack.3_3;
>>>     sizetype _6;
>>>
>>>     <bb 2> [local count: 1073741824]:
>>>     saved_stack.3_3 = __builtin_stack_save ();
>>>     _1 = (sizetype) n_2(D);
>>>     _6 = _1 * 4;
>>>     a.1_8 = __builtin_alloca_with_align (_6, 32);
>>>     p_9 = a.1_8 + _6;
>>>     __builtin_stack_restore (saved_stack.3_3);
>>>     return p_9;
>>>   }
>>>
>>> p_9's solution's is:
>>>
>>>   p_9, points-to vars: { D.1925 } (escaped, escaped heap)
>>>
>>> I couldn't find out how to determine that D.1925 is a VLA (or even
>>> what it is).  It's not among the function's local variables that
>>> FOR_EACH_LOCAL_DECL iterates over.
>> It's possible that decl was created internally as part of the alias
>> oracle's analysis.
> 
> Yes.  Note that only the UID was reserved the fake decl doesn't
> live on.
> 
> Note that for the testcase above the "local" alloca storage escapes
> which means you run into a catch-22 here given points-to computes
> a conservative correct solution and  you want to detect escaping
> locals.  Usually detecting a pointer to local storage can be done
> by using ptr_deref_may_alias_global_p but of course in this
> case the storage was marked global by PTA itself (and our PTA
> is not flow-sensitive and it doesn't distinguish an escape through
> a return stmt from an escape through a call which is relevant
> even for local storage).
Good point.  The inability to tell why something escaped is another
significant hurdle.

> 
> Feature-wise the PTA solver is missing sth like a "filter"
> we could put in front of return stmts that doesn't let
> addresses of locals leak.  The simplest way of implementing
> this might be to not include 'returns' in the constraints at all
> (in non-IPA mode) and handle them by post-processing the
> solver result.  That gets us some additional flow-sensitivity
> and a way to filter locals.  Let me see if I can cook up this.
Another thought would be to somehow flag how the pointer escaped.  ie,
was it as an argument, return value or stored to memory?  Though in the
end that level of detail may not be useful, so collecting it may not be
worth the effort.

> 
> That may ultimatively also help the warning code where you
> then can use ptr_deref_may_alias_global_p.
Another thought would be to use the alias oracle to prune what we look
at.  If we ask the oracle and the value doesn't escape, then it's not
worth walking up the use-def chain to see where it came from.


Jeff