[google,4.6] Bug fix to function reordering linker plugin (issue5623048)

Fix a bug in the function reordering linker plugin where the number of nodes
to be reordered is incremented in the wrong place. This caused a heap buffer
to overflow under certain conditions.  

The linker plugin itself is only available in the google 4_6 branch and I will
port it to other branches and make it available for review for trunk soon.

	* callgraph.c (parse_callgraph_section_contents): Remove increment
	to num_real_nodes.
	(set_node_type): Increment num_real_nodes.


--
This patch is available for review at http://codereview.appspot.com/5623048

This code before the change seems to over-estimate the number of real
nodes which should be safe -- can you explain why it causes problem?

David

On Thu, Feb 2, 2012 at 6:13 PM, Sriraman Tallam <tmsriram@google.com> wrote:
> Fix a bug in the function reordering linker plugin where the number of nodes
> to be reordered is incremented in the wrong place. This caused a heap buffer
> to overflow under certain conditions.
>
> The linker plugin itself is only available in the google 4_6 branch and I will
> port it to other branches and make it available for review for trunk soon.
>
>        * callgraph.c (parse_callgraph_section_contents): Remove increment
>        to num_real_nodes.
>        (set_node_type): Increment num_real_nodes.
>
> Index: function_reordering_plugin/callgraph.c
> ===================================================================
> --- function_reordering_plugin/callgraph.c      (revision 183860)
> +++ function_reordering_plugin/callgraph.c      (working copy)
> @@ -304,7 +304,6 @@ parse_callgraph_section_contents (unsigned char *s
>   caller = caller + HEADER_LEN;
>   curr_length = read_length;
>   caller_node = get_function_node (caller);
> -  num_real_nodes++;
>
>   while (curr_length < length)
>     {
> @@ -422,7 +421,10 @@ static void set_node_type (Node *n)
>   char *name = n->name;
>   slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
>   if (slot != NULL)
> -    set_as_real_node (n);
> +    {
> +      set_as_real_node (n);
> +      num_real_nodes++;
> +    }
>  }
>
>  void
>
> --
> This patch is available for review at http://codereview.appspot.com/5623048

Hi David,

A .gnu.callgraph.text section for function foo will only contain edges
where foo is the caller. Also, in my code real nodes correspond to
functions whose text section is available and hence reorderable.

Originally, when I was counting the number of real function nodes, I
was only treating those functions with a .gnu.callgraph.text section.
This is correct but there can be other real function nodes too so this
is an under-estimate. For instance, there can be leaf functions which
would have no callgraph sections since they dont call anything but can
be reordered. I was not counting these as real function nodes but I
was marking them later as real.  So, the count and the actual can
differ. I use the count to malloc a buffer which gets underallocated
and overflows.

Now, I have changed the code now to increment the number of real
function nodes at the point where I mark a node as real and there is
only one place where I mark it. Hence, this is safe.

Thanks,
-Sri.



On Thu, Feb 2, 2012 at 8:23 PM, Xinliang David Li <davidxl@google.com> wrote:
> This code before the change seems to over-estimate the number of real
> nodes which should be safe -- can you explain why it causes problem?
>
> David
>
> On Thu, Feb 2, 2012 at 6:13 PM, Sriraman Tallam <tmsriram@google.com> wrote:
>> Fix a bug in the function reordering linker plugin where the number of nodes
>> to be reordered is incremented in the wrong place. This caused a heap buffer
>> to overflow under certain conditions.
>>
>> The linker plugin itself is only available in the google 4_6 branch and I will
>> port it to other branches and make it available for review for trunk soon.
>>
>>        * callgraph.c (parse_callgraph_section_contents): Remove increment
>>        to num_real_nodes.
>>        (set_node_type): Increment num_real_nodes.
>>
>> Index: function_reordering_plugin/callgraph.c
>> ===================================================================
>> --- function_reordering_plugin/callgraph.c      (revision 183860)
>> +++ function_reordering_plugin/callgraph.c      (working copy)
>> @@ -304,7 +304,6 @@ parse_callgraph_section_contents (unsigned char *s
>>   caller = caller + HEADER_LEN;
>>   curr_length = read_length;
>>   caller_node = get_function_node (caller);
>> -  num_real_nodes++;
>>
>>   while (curr_length < length)
>>     {
>> @@ -422,7 +421,10 @@ static void set_node_type (Node *n)
>>   char *name = n->name;
>>   slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
>>   if (slot != NULL)
>> -    set_as_real_node (n);
>> +    {
>> +      set_as_real_node (n);
>> +      num_real_nodes++;
>> +    }
>>  }
>>
>>  void
>>
>> --
>> This patch is available for review at http://codereview.appspot.com/5623048

Right -- I examined how the arrays are used. The fix looks safe.

Ok for google branches.

David

On Thu, Feb 2, 2012 at 9:23 PM, Sriraman Tallam <tmsriram@google.com> wrote:
> Hi David,
>
> A .gnu.callgraph.text section for function foo will only contain edges
> where foo is the caller. Also, in my code real nodes correspond to
> functions whose text section is available and hence reorderable.
>
> Originally, when I was counting the number of real function nodes, I
> was only treating those functions with a .gnu.callgraph.text section.
> This is correct but there can be other real function nodes too so this
> is an under-estimate. For instance, there can be leaf functions which
> would have no callgraph sections since they dont call anything but can
> be reordered. I was not counting these as real function nodes but I
> was marking them later as real.  So, the count and the actual can
> differ. I use the count to malloc a buffer which gets underallocated
> and overflows.
>
> Now, I have changed the code now to increment the number of real
> function nodes at the point where I mark a node as real and there is
> only one place where I mark it. Hence, this is safe.
>
> Thanks,
> -Sri.
>
>
>
> On Thu, Feb 2, 2012 at 8:23 PM, Xinliang David Li <davidxl@google.com> wrote:
>> This code before the change seems to over-estimate the number of real
>> nodes which should be safe -- can you explain why it causes problem?
>>
>> David
>>
>> On Thu, Feb 2, 2012 at 6:13 PM, Sriraman Tallam <tmsriram@google.com> wrote:
>>> Fix a bug in the function reordering linker plugin where the number of nodes
>>> to be reordered is incremented in the wrong place. This caused a heap buffer
>>> to overflow under certain conditions.
>>>
>>> The linker plugin itself is only available in the google 4_6 branch and I will
>>> port it to other branches and make it available for review for trunk soon.
>>>
>>>        * callgraph.c (parse_callgraph_section_contents): Remove increment
>>>        to num_real_nodes.
>>>        (set_node_type): Increment num_real_nodes.
>>>
>>> Index: function_reordering_plugin/callgraph.c
>>> ===================================================================
>>> --- function_reordering_plugin/callgraph.c      (revision 183860)
>>> +++ function_reordering_plugin/callgraph.c      (working copy)
>>> @@ -304,7 +304,6 @@ parse_callgraph_section_contents (unsigned char *s
>>>   caller = caller + HEADER_LEN;
>>>   curr_length = read_length;
>>>   caller_node = get_function_node (caller);
>>> -  num_real_nodes++;
>>>
>>>   while (curr_length < length)
>>>     {
>>> @@ -422,7 +421,10 @@ static void set_node_type (Node *n)
>>>   char *name = n->name;
>>>   slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
>>>   if (slot != NULL)
>>> -    set_as_real_node (n);
>>> +    {
>>> +      set_as_real_node (n);
>>> +      num_real_nodes++;
>>> +    }
>>>  }
>>>
>>>  void
>>>
>>> --
>>> This patch is available for review at http://codereview.appspot.com/5623048