[PATCH][PING][PR gdb/19361] Fix invalid comparison functions
Yury Gribov
y.gribov@samsung.com
Tue Dec 29 18:09:00 GMT 2015
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
More information about the Gdb-patches
mailing list