From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 593 invoked by alias); 30 Dec 2015 20:18:33 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 579 invoked by uid 89); 30 Dec 2015 20:18:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.0 required=5.0 tests=AWL,BAYES_40,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 spammy=leaders, H*Ad:U*ppluzhnikov, mandated, D*samsung.com X-HELO: mail-lb0-f174.google.com Received: from mail-lb0-f174.google.com (HELO mail-lb0-f174.google.com) (209.85.217.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 30 Dec 2015 20:18:31 +0000 Received: by mail-lb0-f174.google.com with SMTP id pv2so134864500lbb.1 for ; Wed, 30 Dec 2015 12:18:31 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.112.148.131 with SMTP id ts3mr19602412lbb.102.1451506708134; Wed, 30 Dec 2015 12:18:28 -0800 (PST) Received: by 10.25.21.220 with HTTP; Wed, 30 Dec 2015 12:18:28 -0800 (PST) In-Reply-To: <5682CC66.70608@samsung.com> References: <566FFEE2.4010300@samsung.com> <56823702.6020804@samsung.com> <5682C264.3030109@redhat.com> <5682CC66.70608@samsung.com> Date: Wed, 30 Dec 2015 20:18:00 -0000 Message-ID: Subject: Re: [PATCH][PING][PR gdb/19361] Fix invalid comparison functions From: Yuri Gribov To: Yury Gribov Cc: Pedro Alves , gdb-patches@sourceware.org, Stan Shebs , Paul Pluzhnikov Content-Type: text/plain; charset=UTF-8 X-SW-Source: 2015-12/txt/msg00538.txt.bz2 On Tue, Dec 29, 2015 at 9:09 PM, Yury Gribov 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