Re: [PATCH][PING][PR gdb/19361] Fix invalid comparison functions

[Yury Gribov <y.gribov@samsung.com>]

On 12/29/2015 08:27 PM, Pedro Alves wrote:
> On 12/29/2015 07:32 AM, Yury Gribov wrote:
>> Hi all,
>>
>> The attached patch fixes bugs in comparison functions qsort_cmp and
>> compare_processes.
>>
>> I've tested the patch on x86_64-pc-linux-gnu (no regressions in
>> testsuite except for flakiness in gdb.threads and bigcore.exp).
>>
>> These functions are passed to qsort(3) but do not obey standard symmetry
>> requirements mandated by the standard (grep for "total ordering" in
>> http://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.html).
>> This causes undefined behavior at runtime which can e.g. cause qsort to
>> produce invalid results.
>>
>> Compare_processes fails to properly compare process group leaders which
>> is probably a serious problem (e.g. resulting in invalid sort).
>
> I'm not sure whether it's possible that you end up with equivalent
> elements in the list.  That is, two entries with the same pgid and pid.
> I suppose it could, if the kernel doesn't build the /proc/ directory in one
> go under a lock (or rcu), and a process that has been added to the directory
> already just exited and the kernel reuses the pid for another process of
> the same progress group while we're calling readdir...  Did you check?
> I was under the impression the whole /proc subdir was built atomically
> at open time.
>
>> diff --git a/gdb/nat/linux-osdata.c b/gdb/nat/linux-osdata.c
>> index 56a8fe6..25a310f 100644
>> --- a/gdb/nat/linux-osdata.c
>> +++ b/gdb/nat/linux-osdata.c
>> @@ -420,9 +420,9 @@ compare_processes (const void *process1, const void *process2)
>>     else
>>       {
>>         /* Process group leaders always come first, else sort by PID.  */
>> -      if (pid1 == pgid1)
>> +      if (pid1 == pgid1 && pid2 != pgid2)
>>   	return -1;
>> -      else if (pid2 == pgid2)
>> +      else if (pid1 != pgid1 && pid2 == pgid2)
>>   	return 1;
>>         else if (pid1 < pid2)
>>   	return -1;
>
> In any case, seems to me that it'd result in simpler-to-read-code if
> you rewrote it like this:
>
>        /* Process group leaders always come first, else sort by PID.  */
>
>        /* Easier to check for equivalent element first.  */
>        if (pid1 == pid2)
>          return 0;
>
>        if (pid1 == pgid1)
> 	return -1;
>        else if (pid2 == pgid2)
> 	return 1;
>        else if (pid1 < pid2)
> 	return -1;
>        else if (pid1 > pid2)
> 	return 1;
>
>>
>> Qsort_cmp fails to produce proper result when comparing same element.
>> Sane qsort implementation probably don't call comparison callback on
>> same element
>
> One would hope...  AFAIK, the only real reason to compare same
> object, is if you're sorting an array of pointers, and you can have
> the same pointer included twice in the array being sorted.  It's still
> not the same as comparing same element (the pointers are the elements), but
> it's close.  But in this case, if that ever happened, surely something
> else would have blown up already.
>
> So how about we make that:
>
>    if (sect1_addr < sect2_addr)
>      return -1;
>    else if (sect1_addr > sect2_addr)
>      return 1;
> -  else
> +  if (sect1 != sect2)
>      {
>
> So that the assertion at the bottom is reached in that case? :
>
>    /* Unreachable.  */
>    gdb_assert_not_reached ("unexpected code path");
>    return 0;
> }
>
>> so this may not be a big problem in practice but I think it
>> should still be fixed.

Added my home address (to be able to answer on vacation).

-Y