From patchwork Thu Jul 8 13:50:01 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pierre-Marie de Rodat X-Patchwork-Id: 1502267 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=adacore-com.20150623.gappssmtp.com header.i=@adacore-com.20150623.gappssmtp.com header.a=rsa-sha256 header.s=20150623 header.b=twK3+fWT; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GLHlw3sQFz9sRf for ; Thu, 8 Jul 2021 23:52:12 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4EA6639960E4 for ; Thu, 8 Jul 2021 13:52:10 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com [IPv6:2a00:1450:4864:20::12d]) by sourceware.org (Postfix) with ESMTPS id BBF92398B8B6 for ; Thu, 8 Jul 2021 13:50:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BBF92398B8B6 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com Received: by mail-lf1-x12d.google.com with SMTP id 8so4110902lfp.9 for ; Thu, 08 Jul 2021 06:50:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:mime-version:content-disposition; bh=kdyeNHBqAAqazTAH++LTC1GL76S5TuczhhSqeBAbKeM=; b=twK3+fWTHcSxEX8yJLoC6KZXeIVH6dUOm01Jvsjc05Dz7Hvey3gK3GjVnspJi4a6QA 3pGhbxpGJtMjpKFEI86OVi034VX1MFn3AuybAKV0suYFdrnRecuLFS6u74W9ZpT9bLl6 LPypEZ07HJ4Y/t6HGhZxOw1KwpEwwGj9NXAmvUWVLLcUn/2bwPsQ+mZr1BSc8AAImWY0 rIQZMGSAtLbchf/7HDDlL/m9Yd8LoYJ/0ih47/mBuKoDkuUQHkFy0fwbxFjeYND691d6 fcJs+GTYQaQCn4/mCjjK0T9eARMf4xXLkk5993/U08mDSBFZVr2sBQqA5FfSOZ5jyVAd rpqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:mime-version :content-disposition; bh=kdyeNHBqAAqazTAH++LTC1GL76S5TuczhhSqeBAbKeM=; b=sSJVFZ0EeEyMvt4A5QNd71BL2xZr/8KRf+OGGsXld+ZpFP9FpydFH8q6d8TJmkYU4m rgrJRoweC52JCIBWU1Q6xdU8cDf+QP8a1eueVDGa4c2MRTjfp/qjrGBF3b0C0nDWNsvQ hhplxVcZJlmAnHqRoxqSFa58061FXIx/bzwPJH/jBpIaSPCeXp8TZ/xrCMyZAuKIdoFj 9Qg9E7HFm1X6n5Y3AkVcIvdmmrhQzU/pZA0/JcgkUlSUe8EJEHUti9PA3Z9wbSt8GGW3 JGYhFnXK2eyWNsNZZ4JjfQBVXfnfYPZkuEbgfSChP7gmY9IYhABYvurlS7EZPwEdscLL dR4Q== X-Gm-Message-State: AOAM530+ueSiL2aZBt1kgIt1HfITBNV9DVxQpoMUPsmwrxnEqMhDE7q4 qDeV2sDM0T95rIk88Wn4ANpif7ZnhuvjvQ== X-Google-Smtp-Source: ABdhPJxv30hzXjPzHULrEsh+hm64C+KRjJO2tfqoHiWXBRmjg2vQK4cAsYFQ02d9o+3X8AQzrC+9TQ== X-Received: by 2002:a05:651c:150a:: with SMTP id e10mr25031933ljf.215.1625752202609; Thu, 08 Jul 2021 06:50:02 -0700 (PDT) Received: from adacore.com ([2a02:2ab8:224:2ce:72b5:e8ff:feef:ee60]) by smtp.gmail.com with ESMTPSA id i130sm201471lfd.304.2021.07.08.06.50.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Jul 2021 06:50:02 -0700 (PDT) Date: Thu, 8 Jul 2021 13:50:01 +0000 From: Pierre-Marie de Rodat To: gcc-patches@gcc.gnu.org Subject: [Ada] Incorrect iteration over hashed containers after multiple Inserts Message-ID: <20210708135001.GA2465563@adacore.com> MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-12.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ed Schonberg Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Cursors for Hashed maps and hashed sets include a component that speeds up iteration over these containers. However, in the presence of multiple insertions into the corresponding hash-tables, this component may become unreliable when a cursor obtained before an iteration is compared with a cursor denoting the same element but obtained during a loop over the container. To prevent these anomalies, we introduce an explicit equality operator for the corresponding Cursor types, which ignores the additional component. This patch assumes that the mention of "predefined" equality in the sections of the RM that discuss these cursors is in fact an over specification. Tested on x86_64-pc-linux-gnu, committed on trunk gcc/ada/ * libgnat/a-cohama.ads: Introduce an equality operator over cursors. * libgnat/a-cohase.ads: Ditto. * libgnat/a-cohama.adb: Add body for "=" over cursors. (Insert): Do not set the Position component of the cursor that denotes the inserted element. * libgnat/a-cohase.adb: Ditto. diff --git a/gcc/ada/libgnat/a-cohama.adb b/gcc/ada/libgnat/a-cohama.adb --- a/gcc/ada/libgnat/a-cohama.adb +++ b/gcc/ada/libgnat/a-cohama.adb @@ -116,6 +116,13 @@ is -- "=" -- --------- + function "=" (Left, Right : Cursor) return Boolean is + begin + return + Left.Container = Right.Container + and then Left.Node = Right.Node; + end "="; + function "=" (Left, Right : Map) return Boolean is begin return Is_Equal (Left.HT, Right.HT); @@ -636,7 +643,11 @@ is end if; Position.Container := Container'Unrestricted_Access; - Position.Position := HT_Ops.Index (HT, Position.Node); + + -- Note that we do not set the Position component of the cursor, + -- because it may become incorrect on subsequent insertions/deletions + -- from the container. This will lose some optimizations but prevents + -- anomalies when the underlying hash-table is expanded or shrunk. end Insert; procedure Insert @@ -679,7 +690,6 @@ is end if; Position.Container := Container'Unrestricted_Access; - Position.Position := HT_Ops.Index (HT, Position.Node); end Insert; procedure Insert diff --git a/gcc/ada/libgnat/a-cohama.ads b/gcc/ada/libgnat/a-cohama.ads --- a/gcc/ada/libgnat/a-cohama.ads +++ b/gcc/ada/libgnat/a-cohama.ads @@ -110,6 +110,14 @@ is type Cursor is private; pragma Preelaborable_Initialization (Cursor); + function "=" (Left, Right : Cursor) return Boolean; + -- The representation of cursors includes a component used to optimize + -- iteration over maps. This component may become unreliable after + -- multiple map insertions, and must be excluded from cursor equality, + -- so we need to provide an explicit definition for it, instead of + -- using predefined equality (as implied by a questionable comment + -- in the RM). + Empty_Map : constant Map; -- Map objects declared without an initialization expression are -- initialized to the value Empty_Map. diff --git a/gcc/ada/libgnat/a-cohase.adb b/gcc/ada/libgnat/a-cohase.adb --- a/gcc/ada/libgnat/a-cohase.adb +++ b/gcc/ada/libgnat/a-cohase.adb @@ -145,6 +145,13 @@ is -- "=" -- --------- + function "=" (Left, Right : Cursor) return Boolean is + begin + return + Left.Container = Right.Container + and then Left.Node = Right.Node; + end "="; + function "=" (Left, Right : Set) return Boolean is begin return Is_Equal (Left.HT, Right.HT); @@ -763,11 +770,14 @@ is Position : out Cursor; Inserted : out Boolean) is - HT : Hash_Table_Type renames Container'Unrestricted_Access.HT; begin Insert (Container.HT, New_Item, Position.Node, Inserted); Position.Container := Container'Unchecked_Access; - Position.Position := HT_Ops.Index (HT, Position.Node); + + -- Note that we do not set the Position component of the cursor, + -- because it may become incorrect on subsequent insertions/deletions + -- from the container. This will lose some optimizations but prevents + -- anomalies when the underlying hash-table is expanded or shrunk. end Insert; procedure Insert diff --git a/gcc/ada/libgnat/a-cohase.ads b/gcc/ada/libgnat/a-cohase.ads --- a/gcc/ada/libgnat/a-cohase.ads +++ b/gcc/ada/libgnat/a-cohase.ads @@ -69,6 +69,15 @@ is type Cursor is private; pragma Preelaborable_Initialization (Cursor); + function "=" (Left, Right : Cursor) return Boolean; + -- The representation of cursors includes a component used to optimize + -- iteration over sets. This component may become unreliable after + -- multiple set insertions, and must be excluded from cursor equality, + -- so we need to provide an explicit definition for it, instead of + -- using predefined equality (as implied by a questionable comment + -- in the RM). This is also the case for hashed maps, and affects the + -- use of Insert primitives in hashed structures. + Empty_Set : constant Set; -- Set objects declared without an initialization expression are -- initialized to the value Empty_Set.