From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-VI1-obe.outbound.protection.outlook.com (mail-eopbgr80080.outbound.protection.outlook.com [40.107.8.80]) by sourceware.org (Postfix) with ESMTPS id 82F473858C2C for ; Tue, 4 Jan 2022 22:14:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 82F473858C2C Received: from AS8PR04CA0034.eurprd04.prod.outlook.com (2603:10a6:20b:312::9) by AM6PR08MB4900.eurprd08.prod.outlook.com (2603:10a6:20b:cc::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4867.7; Tue, 4 Jan 2022 22:14:39 +0000 Received: from VE1EUR03FT037.eop-EUR03.prod.protection.outlook.com (2603:10a6:20b:312:cafe::67) by AS8PR04CA0034.outlook.office365.com (2603:10a6:20b:312::9) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4844.14 via Frontend Transport; Tue, 4 Jan 2022 22:14:39 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by VE1EUR03FT037.mail.protection.outlook.com (10.152.19.70) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4844.14 via Frontend Transport; Tue, 4 Jan 2022 22:14:39 +0000 Received: ("Tessian outbound 157533e214a9:v110"); Tue, 04 Jan 2022 22:14:38 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: fda689c65b6374ee X-CR-MTA-TID: 64aa7808 Received: from 4f548c18c4a3.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 2D6A52F9-11E1-4C03-A47F-41E9BCCE8DC8.1; Tue, 04 Jan 2022 22:14:32 +0000 Received: from EUR05-VI1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 4f548c18c4a3.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Tue, 04 Jan 2022 22:14:32 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=iZkHcCIuK0+IfmswxL5DilpF1y3UL1f4gY2aMAgk0aD6Bv5jrShhgDfwQ+416HoIyopIs3PKBotwatYxV87/29DjIDr4qYVPd7fMX2e1VozGyd2TuPU/U/LsIQfZ0Z6V/scawdt21KQPM1SWzM9XyB7oRq7GRVThth+HzTjzMt2sQKkeepBa/G4N/7w2FTT5+leBj90bZci+Dfiw4IqY803vm9Ss8qiT2S2pkLtkqopr+LKUwRYQUFbQFNzkJpPvMjYdnfUlUz9v100CZq1OqgDRDVwt0+op6h4n3GmRzPozYo3Ol59vNDm2bFwv5ICNBM1cesKbjTiXyYOpU1OI+w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=pYhjPGdY5h0F0Fs0F5ipwORxOT1x9ALn8COH+rIxM6o=; b=Np/8O9P33DYpnNH3IDvCn5/ieJMWhPu8QZ9VJ3TH1lvSsvDfp2Ry0TQDczGI8+/XXOGxEeR2pnsJ7pB2A33y0lZY+NXvhqfXSz8JfkC2Qqa7IB6Uli8tAoNC0Ehg4Po3eiJK2c/Oa9foPY+fZSWFHA67/T4DXh1qzprcaec3WXTrRQtfg9niymqjHX1gxqgsEiOKiRsvWpZKr2YFfe1McYcDQkYaCAx3RsSuGo3GkD0FzPuwPNRWQQjvrdjihGJ+GwjqBhYYQHBXRfqUsGVdP30MKDCJp6RX0eoq0pW+D1TUl0rgSY7zIUJ0P3FJch0SdtJ+e7+rZzlNwPNgiQZ0Kw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from DB9PR08MB7179.eurprd08.prod.outlook.com (2603:10a6:10:2cc::19) by DB9PR08MB7067.eurprd08.prod.outlook.com (2603:10a6:10:2c0::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4867.7; Tue, 4 Jan 2022 22:14:29 +0000 Received: from DB9PR08MB7179.eurprd08.prod.outlook.com ([fe80::25f9:a7e6:422a:da43]) by DB9PR08MB7179.eurprd08.prod.outlook.com ([fe80::25f9:a7e6:422a:da43%7]) with mapi id 15.20.4823.023; Tue, 4 Jan 2022 22:14:29 +0000 Date: Tue, 4 Jan 2022 22:14:27 +0000 From: Szabolcs Nagy To: Florian Weimer Cc: libc-alpha@sourceware.org, gcc-help@gcc.gnu.org, "Paul E. McKenney" , Tulio Magno Quites Machado Filho Subject: Re: Help needed for glibc software transaction memory algorithm Message-ID: <20220104221427.GO3294453@arm.com> References: <87v8yzfv3u.fsf@oldenburg.str.redhat.com> Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <87v8yzfv3u.fsf@oldenburg.str.redhat.com> X-ClientProxiedBy: LO4P123CA0003.GBRP123.PROD.OUTLOOK.COM (2603:10a6:600:150::8) To DB9PR08MB7179.eurprd08.prod.outlook.com (2603:10a6:10:2cc::19) MIME-Version: 1.0 X-MS-Office365-Filtering-Correlation-Id: ae4585b7-e06c-4d66-91f1-08d9cfcf99a8 X-MS-TrafficTypeDiagnostic: DB9PR08MB7067:EE_|VE1EUR03FT037:EE_|AM6PR08MB4900:EE_ X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true NoDisclaimer: true X-MS-Oob-TLC-OOBClassifiers: OLM:9508;OLM:9508; X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: WaHho25QwvqNnVrUiFVSb+kXa49rh3keEXUq4/mX98yI0orQ5eN0K7BvIi3iwfuPn37HBU3k0l4rZAg9g+ZGE3wW6NlQKRcw6HkrJVQLKjHiaU6qblwCwdJV/Ew5qtsSLonP9IePvI4fJTIxdIwTVrFU5Plx8h1ElTaDe36VH5a+wE9a19xGsxBDUAb2rx6TVNcUULJeNDmbvvp2SliFOx0+QM2090QhWB12R2TPshrXcAWGoQHt1L7zvHh7nbeROmZ5fTFfwqgtLcYhuypjR8bAVboL4n/s1N6/hHmh1EtrNmGQTuJt3dJiAyf/WVdZc4gI2MXW2pVLAFPFL/gkt3+1hgbMHaBw1tuoFzVrrL8tmP9zpIuBEAXEAQzMspAL5c85pnjlH0L9GCYmVaXm+wIz3M5fbL5xks/hnZ9zEi89YB78Wnqc4ANzoKfq81NCBKt4yhD9XX7QGHSR9WHFnJNGJlcO1kIrxrfchTeA/HmoxmE0xe9zCSHicOk4nPp4He0MXJ6ugq4QgiKCDmQmmbVkY2ox7HndmYuh6K31AANsy3578dwAenvjSFuMtehSCv+njZhtqDUHHOMhWVKqpmPxB3jQQVtykrI5yfdEbULq7TiGkOK8/goOWrt3rxw/5/3fsKOgc/lTeRrGMkdlipAUiTkN4zjTnok8Mq+/JNqi4DekaJPeHH3WUjsvpBsDn+0RqaWladdUlh3UzD6rdJ938YIBml/pxgLyVQdkZNqVqjo5zz3y9ZNqoWpngdvh189lHO7QZ4JS8fYOZp8UxpD7zqSPC67TPio6PJ3Sy2I= X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:DB9PR08MB7179.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(366004)(6506007)(52116002)(966005)(6916009)(26005)(83380400001)(508600001)(4326008)(2906002)(8936002)(6486002)(186003)(33656002)(316002)(2616005)(6512007)(44832011)(54906003)(8676002)(38100700002)(38350700002)(86362001)(1076003)(5660300002)(66476007)(36756003)(66556008)(66946007); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB9PR08MB7067 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: VE1EUR03FT037.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 880bd9cd-fc9f-427e-422d-08d9cfcf935b X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: JAvV1fkJGmNr4DNviQ20TySJB7aZn6peAiJctbdkxfdllO3vsHZumqcnwGk6s8dZCMrNOH8PcEcJTHytNQKgUdgqyyatsH89Y5O8+25bgzuat4V3BpmAUGTlpqOGVTjx4OVQK5ZaqfF26lj0F5J4Z0IJd3aOE5QPPoQ23x2+68Gqv5XN50ZQN6zstq+Nm2C3DPRAPEdpbqenGhW285N7eJL020bK1oE+EtEDTy2rk8yERQoFeJwxsi7JOq6lGu3an0Ynts3usntYhZONxc0Vfy8sZeQ9KiFWCczpxEyUbOd25zNy4IoEBRBiGqPSEwRQHwW45EQY9l3zLzVL30JsY4tdo0W0ZCGJjxwrpt39EZphst4TN0gRr/tpQK88jUTPrCBlDGmwto7DgiCocJgelKeUoP6p9x4iY8tOe0nriGrlTt5/OytFq2VHBDAB1WsLtOG+vLL4sAIvLXojSLe0C223n8o6M2l0bifeoZYxQ9z1fZ0AvuZzXNt+JBUBARMOBGB8PTyDZkdKi4X7RXhxwZLwMw5kQE/Eas7Cs/Dlml+FYlPvWoH4SUlDLmitBMEGH1b5lp7IvVVWi0hbKGXBtwWgoB36UqlSPkHmKaPWydU4wT5qBlXnexTzQXPAF6c85MWSuiuw7o7jgPOazIsw9gWeEhSL/nEcx4zj0D3rlkpWEburkXL9EDUQLjIipC5jwasKiU2DhR3lpic3NQSRkqNvX3HZz2iCvq/GCEmkbjKWjU+nNicrTkbIp3qX9MW3tSgaBBsc0AZSYNNuNjur8s/MgqfS4M9+6s3ODidn85h4tN85wu4Av4VKbzMO+2zhHlVYbhS6slYWCA1UIi5ar9uNQk+NXAo+Fid0Z/Bnugw= X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFS:(4636009)(40470700002)(46966006)(36840700001)(8676002)(86362001)(6512007)(44832011)(54906003)(2616005)(336012)(70586007)(36860700001)(1076003)(70206006)(36756003)(5660300002)(966005)(356005)(6862004)(81166007)(82310400004)(40460700001)(6506007)(186003)(33656002)(316002)(47076005)(508600001)(83380400001)(6486002)(26005)(4326008)(2906002)(8936002); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Jan 2022 22:14:39.1664 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: ae4585b7-e06c-4d66-91f1-08d9cfcf99a8 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: VE1EUR03FT037.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB4900 X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_PASS, TXREP, UNPARSEABLE_RELAY 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-help@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-help mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 04 Jan 2022 22:14:43 -0000 The 01/04/2022 15:12, Florian Weimer via Libc-alpha wrote: > I've tried to implement a software transactional memory algorithm > > The characteristics are: > > * Single writer, multiple readers. > > * Two copies of the data. > > * A 64-bit version counter tracks modifications. The lowest bit of the > counter tells the reader which copy of the data to read. > > * The writer increments the counter by 2, modifies the STM-protected > data, and increments the counter by 1. > > * The reader loads the counter, reads the STM-protected data, loads the > counter for a second time, and retries if the counter does not match. > > I've attached a model implementation. The glibc implementation has a > wrapper around the counter updates to support 32-bit implementations as > well. In both implementations, the writer uses release MO stores for > the version update, and the reader uses acquire MO loads. The stores > and loads of the STM data itself are unordered (not even volatile). > > It turns out that this does not work: In the reader, loads of the > STM-protected data can be reordered past the final acquire MO load of > the STM version. As a result, the reader can observe incoherent data. > In practice, I only saw this on powerpc64le, where the *compiler* > performed the reordering: > > _dl_find_object miscompilation on powerpc64le > > > Emprically, my stm.c model does not exhibit this behavior. > > To fix this, I think it is sufficient to add a release fence just before > the second version load in the reader. However, from a C memory model > perspective, I don't quite see what this fence would synchronize > with. 8-/ And of course once there is one concurrency bug, there might > be others as well. Do I need to change the writer to use > acquire-release MO for the version updates? > > I think there should be a canned recipe for this scenario (single > writer, two data copies), but I couldn't find one. this reminds me the discussion in section 4 and 5 of https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf there are no 2 data copies here but i think the reasoning about the synchronization may apply.