From patchwork Tue Dec 5 21:28:48 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10093815 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 47ED560348 for ; Tue, 5 Dec 2017 21:29:11 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 39DBA288F4 for ; Tue, 5 Dec 2017 21:29:11 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2D8F928923; Tue, 5 Dec 2017 21:29:11 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D209C288F4 for ; Tue, 5 Dec 2017 21:29:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751473AbdLEV2x (ORCPT ); Tue, 5 Dec 2017 16:28:53 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:55472 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751362AbdLEV2u (ORCPT ); Tue, 5 Dec 2017 16:28:50 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=In-Reply-To:Content-Type:MIME-Version :References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=/E0NkPfzf9MsiWuRiGX+wv7x8lHVsGvvGJb3+JaMWuQ=; b=hO5CAdpnmYTiE5mFtahQoU+hO 9keze0RejFsoMkJUkLz7bvVKlAD6AgniqEDat99kASaR7oibaf3cDsuik+EYyBk4E2NplyRnzjf3d 9R7U9orCovzvm9PUBJ3Sd3Y0USONrdDcaCjXn34Fk5epyG2q7i/8R3FhtzaziBSdtsZdbj9pzfzBl Ec/mrVyMuHyAMjWSDy8GW14qDy6So0ygBiUlhyA5KeOCD3NBaDnp4RUsI5Y5Z+rm796Ye3ENkHkXY C7BiSCKQCt9sY6Tkow2hzz1jVIFgMQtz6kPxowClcRr+jN+JElNjksyYdqlztMBya8RGRhMAUR91H ibpzcaCgQ==; Received: from willy by bombadil.infradead.org with local (Exim 4.87 #1 (Red Hat Linux)) id 1eMKlk-0001AK-1X; Tue, 05 Dec 2017 21:28:48 +0000 Date: Tue, 5 Dec 2017 13:28:48 -0800 From: Matthew Wilcox To: NeilBrown Cc: Thiago Rafael Becker , bfields@fieldses.org, linux-nfs@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH 2/3, V2] kernel: Move groups_sort to the caller of set_groups. Message-ID: <20171205212847.GF26021@bombadil.infradead.org> References: <20171130130457.11429-1-thiago.becker@gmail.com> <20171130130457.11429-3-thiago.becker@gmail.com> <87mv2ztgix.fsf@notabene.neil.brown.name> <87efoatfsb.fsf@notabene.neil.brown.name> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <87efoatfsb.fsf@notabene.neil.brown.name> User-Agent: Mutt/1.9.1 (2017-09-22) Sender: linux-nfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-nfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP On Tue, Dec 05, 2017 at 07:11:00AM +1100, NeilBrown wrote: > As we don't seem to be pursuing this possibility is probably isn't very > important, but I'd like to point out that the original fix isn't a true > fix. > It just sorts a shared group_info early. This does not stop corruption. > Every time a thread calls set_groups() on that group_info it will be > sorted again. > The sort algorithm used is the heap sort, and a heap sort always moves > elements in the array around - it does not leave a sorted array > untouched (unlike e.g. the quick sort which doesn't move anything in a > sorted array). > So it is still possible for two calls to groups_sort() to race. > We *need* to move groups_sort() out of set_groups(). It must be relatively common to sort an already-sorted array. I wonder if something like this patch would be worthwhile? I have deliberately broken this patch so it can't be applied. I haven't tested it, and for all I know, I got the sign of cmp_func wrong. --- To unsubscribe from this list: send the line "unsubscribe linux-nfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/lib/sort.c b/lib/sort.c index d6b7a202b0b6..2b527fde6dad 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -75,7 +75,14 @@ void sort(void *base, size_t num, size_t size, swap_func = generic_swap; } - /* heapify */ + /* Do not sort an already-sorted array */ + for (c = 0; c < (n - size); c += size) { + if (cmp_func(base + c, base + c + size) < 0) + goto heapify; + } + return; + +heapify: for ( ; i >= 0; i -= size) { for (r = i; r * 2 + size < n; r = c) { c = r * 2 + size;