Bug 19361

Summary:	Invalid comparison functions
Product:	gdb	Reporter:	Yuri Gribov <tetra2005>
Component:	gdb	Assignee:	Not yet assigned to anyone <unassigned>
Status:	NEW ---
Severity:	normal	CC:	ssbssa, tetra2005, tromey
Priority:	P2
Version:	HEAD
Target Milestone:	---
Host:		Target:
Build:		Last reconfirmed:
Attachments:	Proposed patch

Description Yuri Gribov 2015-12-12 19:25:10 UTC

Created attachment 8846 [details]
Proposed patch

Comparison functions qsort_cmp and compare_processes (used in qsort) do not obey to standard symmetry requirements which causes undefined behavior. The latter may result in strange runtime bugs.

Compare_processes fails to properly compare process group leaders which is probably a serious problem (e.g. resulting in invalid sort).

Qsort_cmp fails to produce proper result when comparing same element. Sane qsort implementation probably don't call comparison callback on same element so this may not be a big problem in practice.

I've attached simple patches which correct both errors.

Bugs were found with SortChecker tool (https://github.com/yugr/sortcheck).

Comment 1 Tom Tromey 2016-05-24 15:37:25 UTC

It seems reasonable to me, but patches should go to the gdb-patches list.
See: https://sourceware.org/gdb/wiki/ContributionChecklist

Comment 2 Hannes Domani 2020-04-07 12:40:44 UTC

Both functions were changed to std::sort, but I'm not sure if the symmetry requirements were fixed with this.

compare_processes:
https://sourceware.org/git/?p=binutils-gdb.git;a=commitdiff;h=b129dcac882da87767cb863ad8b2572f90e9e5bc

qsort_cmp:
https://sourceware.org/git/?p=binutils-gdb.git;a=commitdiff;h=39ef2f6256737db92f5d60fa201fe0b301bb8100

Comment 3 Tom Tromey 2020-04-07 18:28:18 UTC

The linux-osdata.c code looks ok now.

It's hard to say if the objfiles.c code is totally correct or not.
Will std::sort compare an object with itself?
Anyway it would be fine to apply an updated version of that patch.

Comment 4 Yuri Gribov 2020-04-07 20:06:02 UTC

(In reply to Tom Tromey from comment #3)
> The linux-osdata.c code looks ok now.

Yes, looks good except maybe for ...

> Will std::sort compare an object with itself?

... as I've heard rumors that std::sort _can_ compare object to itself (never seen a proof though).

> It's hard to say if the objfiles.c code is totally correct or not.

I think the code in objfiles.c is still violating ordering axioms. E.g. if
  objfile1->separate_debug_objfile == objfile2
then sort_cmp(sect1, sect2) and sort_cmp(sect2, sect1) will both return false which is a contradiction. Some implementations of sort return erratic results in such circumstances.

Sadly I can't rerun my tool on gdb now as it's limited to qsort (std::sort checking requires instrumentation in compiler...).