This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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.

Thanks,
Pedro Alves


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]