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

[Yuri Gribov <tetra2005@gmail.com>]

On Tue, Dec 29, 2015 at 9:09 PM, Yury Gribov <y.gribov@samsung.com> wrote:
> 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.

Sorry, I should have been more wordy about the actual problem. With
current approach i.e.

  if (pid1 == pgid1)
    return -1;
  else if (pid2 == pgid2)
    return 1;

comparison of two group leaders is not going to be symmetric:

  cmp(lead_1, lead_2) == cmp(lead_2, lead_1) == -1

whereas qsort requires cmp(x, y) == -cmp(y, x) (symmetry requirement).
Such violations of ordering may easily cause sorting algorithm to
misbehave.

>>> 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;
>> }

Makes perfect sense!

And thanks for detailed reply btw.

-Y