From patchwork Mon Nov 21 16:09:05 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 60930 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A0B673851892 for ; Mon, 21 Nov 2022 16:09:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A0B673851892 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1669046981; bh=C3Wtx8VoQK/1sWbb+WaV2w/NkG/Qlk0JSmQxl8i15ws=; h=To:CC:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=YqaGZiRdE871DBb6Fn18/QLNA2u/V4SMuiVFR2nc4z/bbviWprpBBkK1jQ88P1jOI znT9hFjHQParaqJpMBKcXwmjghmMhl8u4x8q92HyeChlVuDT7V7QXMGiHHqUwhTv3e 6/pSN2e6IcR0W3gnxLZ9SOcSF59AMStkD/IJP718= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from EUR03-VI1-obe.outbound.protection.outlook.com (mail-vi1eur03on2063.outbound.protection.outlook.com [40.107.103.63]) by sourceware.org (Postfix) with ESMTPS id 65ECC3851885 for ; Mon, 21 Nov 2022 16:09:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 65ECC3851885 Received: from DBBPR09CA0018.eurprd09.prod.outlook.com (2603:10a6:10:c0::30) by PA4PR08MB6015.eurprd08.prod.outlook.com (2603:10a6:102:e6::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5857.17; Mon, 21 Nov 2022 16:09:15 +0000 Received: from DBAEUR03FT007.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:c0:cafe::f1) by DBBPR09CA0018.outlook.office365.com (2603:10a6:10:c0::30) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5834.15 via Frontend Transport; Mon, 21 Nov 2022 16:09:15 +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; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DBAEUR03FT007.mail.protection.outlook.com (100.127.142.161) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5834.8 via Frontend Transport; Mon, 21 Nov 2022 16:09:15 +0000 Received: ("Tessian outbound aeae1c7b66fd:v130"); Mon, 21 Nov 2022 16:09:15 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: f747540ed2334902 X-CR-MTA-TID: 64aa7808 Received: from c52d8e13112c.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id E64E3B03-179F-4E23-801A-F230CD5C6F4E.1; Mon, 21 Nov 2022 16:09:08 +0000 Received: from EUR05-VI1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id c52d8e13112c.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Mon, 21 Nov 2022 16:09:08 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=QJzmoPOMMlx+7FJ98lGRV+ssErdJidoxacu1AVCWuHhLubN1v2WZ63zd3XjkKDnSCasR13iootnC+thrCdwQR7q95xWfR/0XI3/YhOHuJb8wnHc4+qGQJPqs+t8XUjUOpGYTVEKF4jlFlwy4MkU3dmOwkuCVJpxmL9HlSOCm0YAqT1biclYyyaF0izo3su4uNxX4xahrhgVgBd4vGeWzpknIhvGlvqJXoTMdCK54leqaBAvYROAK89yD2JDHSGSZmCwNMHOZedoH5aSAG6dbHsqqiwDk7L3Z06mNoPpN59UuQaYREhG0RsiUDYCp5EVjmTnY/wGdOCBEtcbIKfn6aw== 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=C3Wtx8VoQK/1sWbb+WaV2w/NkG/Qlk0JSmQxl8i15ws=; b=a4hsF47w94pyaPWfoww/8HEjj5SyrX8cO/1WoNsvuOO7nrUsRCwmvCFXSQA0B9xMkfoPiMjOnBblhLtoEGsRD+R/CArFzR/GxZu3pt/MbMEGo3Qy0NLqJYnH/pt5fggQ+amKuvtiVBmQ4K/9TLCdlhzY80PY/gBY+DnUVkohU1XIdINI/ihVUc9Y0NiUXf0Dat7f8er8Z/ohBGtZ9PWHMSmNE5xKxy15UCtmQGy+Xdet/jmBbE+L5kSTVg7IjnWsTnt+u4xbkMKxJtWHQvdz0yOt/aqgJz+V1Nx+PV5sMoRiSIu+QVIuQCLdxIEhaTMuJESowOFaTcVS1SsSNkkUFw== 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 Received: from PAWPR08MB8982.eurprd08.prod.outlook.com (2603:10a6:102:33f::20) by DB9PR08MB7469.eurprd08.prod.outlook.com (2603:10a6:10:36f::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5857.17; Mon, 21 Nov 2022 16:09:06 +0000 Received: from PAWPR08MB8982.eurprd08.prod.outlook.com ([fe80::4c73:7d14:fc39:a3cb]) by PAWPR08MB8982.eurprd08.prod.outlook.com ([fe80::4c73:7d14:fc39:a3cb%3]) with mapi id 15.20.5857.017; Mon, 21 Nov 2022 16:09:06 +0000 To: 'GNU C Library' CC: Florian Weimer Subject: [PATCH] malloc: Use correct C11 atomics for fastbin Thread-Topic: [PATCH] malloc: Use correct C11 atomics for fastbin Thread-Index: AQHY/cJS/cK/f0PorUWetLVbA8LI1g== Date: Mon, 21 Nov 2022 16:09:05 +0000 Message-ID: Accept-Language: en-GB, en-US Content-Language: en-GB X-MS-Has-Attach: X-MS-TNEF-Correlator: msip_labels: Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; x-ms-traffictypediagnostic: PAWPR08MB8982:EE_|DB9PR08MB7469:EE_|DBAEUR03FT007:EE_|PA4PR08MB6015:EE_ X-MS-Office365-Filtering-Correlation-Id: a96dd25f-4072-4893-251e-08dacbdabc9b x-checkrecipientrouted: true nodisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: 1+Anjpv0FkPbOnPCsgHJH9t3Ir5x7xXFC9/mIjx6Bcf0WIleV2YVHSAkjMKMzheyMIAw5zn6G++hIhGnT3iQ7NUoFI4UqPfdjuEv+v2Hoib+3DJdTk7rqnKFS7APlqAqWIiI5ZUMJzk6LVjKlmAbURkZI2sQnEBj7EZb+AUi+WaY17NHML9V4tJVmvpA2yML5AzxKwqSMURH8dH6aTLwYI4AIJfwASRJXaIPLNdTien4H8QiVmIIi9jkMbc9u4MZX8nQRH2QDo5MTkBhLftzqxkTrKTjbM8vGITLEHUuHfEfU5vIxcZJ1j6hsA8HD8pTJxf78u6CdHNMpjmgkSrGf1Oq1QinDcA2bYXKB2gAHOhQZdkFkXOPfjt/KeikJ7+XzwwedZsA7PmSwARhk4Ww6JeQ+LNCfKktsbkzPQhiOpCErkEDmDF0zR8ChjbisbKc+RSrRAwjUrYqncnA3KRmzimaTZh5i+fqSIQG4Bmh7HgTl0EtiYvo+59HgiKT+HB55J6ttzVozKv0MJ6xezQjvu4RcPQTNJ0RZKDGK9N9txtdr1+BEb5/mYPUe5Mbh90DFJ19Moj07849HTyOBLdDDnrAUbJIjn1J1+Q6WmEw/dDbrDS12AKQIvY5lo62SVvjq/INTFfgJ+eVtvUEa5SmfvYM9z3xgM4++N37plenDr4aHxsatVVsf1vf3qD3K386s1HxtvmKHksGUA90JYJzOQ== X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:PAWPR08MB8982.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(4636009)(366004)(376002)(396003)(39860400002)(136003)(346002)(451199015)(83380400001)(52536014)(5660300002)(8936002)(41300700001)(38070700005)(6506007)(7696005)(9686003)(26005)(478600001)(71200400001)(33656002)(186003)(91956017)(66946007)(66446008)(66476007)(76116006)(66556008)(64756008)(8676002)(316002)(4326008)(6916009)(86362001)(122000001)(38100700002)(2906002)(55016003); DIR:OUT; SFP:1101; MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB9PR08MB7469 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: DBAEUR03FT007.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: a29a224d-3649-42f4-c175-08dacbdab705 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: TPXHRKCqQqRMHoFCNg+ayzuE0q/xBdDW1RtecD5O7inmd2VWjmjEzVmHNnWVDg7cfNzkHkSc82ID5YUIM14G+TA4V0bMu76bT6zovxlAGnNgdA8g2bDlGZX4LS4UA/jiokT67zm04D+81/4Cz+cleuLvyw8wduCCm7JPJJYK//laXrCee8cDm7px66pLkJJCYd9Z6wewP+oWeAFT6aC0/dPMhQNzULrvBwIbG1vLuQBr9ymN8tbOCGNku2WvY9wZ7gp/AYFUXjX7FIjOXdidxaNTJgGLvDwJADD7jlk7stCPU/f/6josPe5HOt7ldGjAPYvC1ccd4gQQ7QjJSXGihHnz0uyiY/Nb+9at6DEoRTRj6rr3hqG+ygb9xxKei1ofzBAOmOfZsjvs7i2iY5qYbp7tyTfPdUmGUPPpG35ByR1JI0fdo7IMvJfrWgjZ4Yy1tsejpBb9KnRVbv8jbXK9an90CBRx8KQrokd4o1BCI1kb9N+ctQnjZ+97Y6M+O4f0ZSZQyfXewxVwC1HVuyTqd60wljS3q2e6C/bFKRrOyW5nzOF2Mc0EDCkbn0yHecI8J0j5pgHplaewd2NWWf1n8N2FB0YJTiKNCW4k8kF2+1Trbx4Qb1BzNa6cBfShB5Ry0Lydw4AafqBllbMLLZy2shtKBluZrcP3WZmUKqiK44sZYeIfVwncevJT39y2ctMOP0H7u2CU5onxFk3Pu+fyVw== 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:(13230022)(4636009)(39860400002)(376002)(346002)(396003)(136003)(451199015)(46966006)(40470700004)(36840700001)(82740400003)(86362001)(36860700001)(83380400001)(47076005)(41300700001)(81166007)(2906002)(52536014)(40460700003)(8936002)(82310400005)(40480700001)(5660300002)(478600001)(107886003)(55016003)(6506007)(7696005)(26005)(336012)(4326008)(8676002)(70206006)(316002)(9686003)(186003)(356005)(6916009)(70586007)(33656002); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 21 Nov 2022 16:09:15.3939 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: a96dd25f-4072-4893-251e-08dacbdabc9b 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: DBAEUR03FT007.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: PA4PR08MB6015 X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, KAM_DMARC_NONE, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP, UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Wilco Dijkstra via Libc-alpha From: Wilco Dijkstra Reply-To: Wilco Dijkstra Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Fix memory ordering issues in the fastbin implementation: in REMOVE_FB the next pointer is read before any MO synchronization, however in the C11 atomic model this is only correct after a load acquire. Refactor the fastbin code and add a dedicated fastbin_push/pop implementation. The number of acquire or release atomics remains the same, and the new functions are inlined, so performance is unaffected. Passes regress, OK for commit? diff --git a/malloc/malloc.c b/malloc/malloc.c index 2a61c8b5ee38f33c42c72f3c5ad441e26ed0e701..a3e7053d2db81cce211dd8c3cff43af0f59a1b71 100644 --- a/malloc/malloc.c +++ b/malloc/malloc.c @@ -1786,6 +1786,73 @@ get_max_fast (void) return global_max_fast; } + +/* Atomically push onto the fastbin list. Return the previous head of the + list, however it can only be referenced if the arena lock is acquired. */ +static __always_inline mchunkptr +fastbin_push_chunk (mchunkptr *fastbin, mchunkptr p) +{ + mchunkptr head = atomic_load_relaxed (fastbin); + + /* Check that the top of the bin is not the record we are going to + add (i.e., double free). */ + if (__builtin_expect (head == p, 0)) + malloc_printerr ("double free or corruption (fasttop)"); + + if (SINGLE_THREAD_P) + { + p->fd = PROTECT_PTR (&p->fd, head); + *fastbin = p; + return head; + } + + /* Atomically update the fastbin head. Use release MO to synchronize + with acquire reads in fastbin_pop_chunk and malloc_consolidate (this + ensures the next pointer update is valid). */ + do + { + p->fd = PROTECT_PTR (&p->fd, head); + } + while (!atomic_compare_exchange_weak_release (fastbin, &head, p)); + + return head; +} + + +/* Atomically pop from the fastbin list. The arena lock must be held to + block other threads removing entries, avoiding the ABA issue. */ +static __always_inline mchunkptr +fastbin_pop_chunk (mchunkptr *fastbin) +{ + mchunkptr head, tail; + + if (SINGLE_THREAD_P) + { + head = *fastbin; + if (head == NULL) + return head; + if (__glibc_unlikely (misaligned_chunk (head))) + malloc_printerr ("malloc(): unaligned fastbin chunk detected"); + *fastbin = REVEAL_PTR (head->fd); + return head; + } + + do + { + /* Synchronize with release MO CAS in fastbin_pop_chunk - this ensures + the next pointer is valid. */ + head = atomic_load_acquire (fastbin); + if (head == NULL) + return head; + if (__glibc_unlikely (head != NULL && misaligned_chunk (head))) + malloc_printerr ("malloc(): unaligned fastbin chunk detected"); + tail = REVEAL_PTR (head->fd); + } + while (!atomic_compare_exchange_weak_relaxed (fastbin, &head, tail)); + + return head; +} + /* ----------- Internal state representation and initialization ----------- */ @@ -3798,71 +3865,37 @@ _int_malloc (mstate av, size_t bytes) can try it without checking, which saves some time on this fast path. */ -#define REMOVE_FB(fb, victim, pp) \ - do \ - { \ - victim = pp; \ - if (victim == NULL) \ - break; \ - pp = REVEAL_PTR (victim->fd); \ - if (__glibc_unlikely (pp != NULL && misaligned_chunk (pp))) \ - malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \ - } \ - while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \ - != victim); \ - if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ())) { idx = fastbin_index (nb); mfastbinptr *fb = &fastbin (av, idx); - mchunkptr pp; - victim = *fb; + victim = fastbin_pop_chunk (fb); if (victim != NULL) { - if (__glibc_unlikely (misaligned_chunk (victim))) - malloc_printerr ("malloc(): unaligned fastbin chunk detected 2"); - - if (SINGLE_THREAD_P) - *fb = REVEAL_PTR (victim->fd); - else - REMOVE_FB (fb, pp, victim); - if (__glibc_likely (victim != NULL)) - { - size_t victim_idx = fastbin_index (chunksize (victim)); - if (__builtin_expect (victim_idx != idx, 0)) - malloc_printerr ("malloc(): memory corruption (fast)"); - check_remalloced_chunk (av, victim, nb); + size_t victim_idx = fastbin_index (chunksize (victim)); + if (__builtin_expect (victim_idx != idx, 0)) + malloc_printerr ("malloc(): memory corruption (fast)"); + check_remalloced_chunk (av, victim, nb); #if USE_TCACHE - /* While we're here, if we see other chunks of the same size, - stash them in the tcache. */ - size_t tc_idx = csize2tidx (nb); - if (tcache && tc_idx < mp_.tcache_bins) + /* While we're here, if we see other chunks of the same size, + stash them in the tcache. */ + size_t tc_idx = csize2tidx (nb); + if (tcache && tc_idx < mp_.tcache_bins) + { + /* While bin not empty and tcache not full, copy chunks. */ + while (tcache->counts[tc_idx] < mp_.tcache_count) { - mchunkptr tc_victim; - - /* While bin not empty and tcache not full, copy chunks. */ - while (tcache->counts[tc_idx] < mp_.tcache_count - && (tc_victim = *fb) != NULL) - { - if (__glibc_unlikely (misaligned_chunk (tc_victim))) - malloc_printerr ("malloc(): unaligned fastbin chunk detected 3"); - if (SINGLE_THREAD_P) - *fb = REVEAL_PTR (tc_victim->fd); - else - { - REMOVE_FB (fb, pp, tc_victim); - if (__glibc_unlikely (tc_victim == NULL)) - break; - } - tcache_put (tc_victim, tc_idx); - } + mchunkptr tc_victim = fastbin_pop_chunk (fb); + if (tc_victim == NULL) + break; + tcache_put (tc_victim, tc_idx); } -#endif - void *p = chunk2mem (victim); - alloc_perturb (p, bytes); - return p; } +#endif + void *p = chunk2mem (victim); + alloc_perturb (p, bytes); + return p; } } @@ -4505,29 +4538,7 @@ _int_free (mstate av, mchunkptr p, int have_lock) fb = &fastbin (av, idx); /* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */ - mchunkptr old = *fb, old2; - - if (SINGLE_THREAD_P) - { - /* Check that the top of the bin is not the record we are going to - add (i.e., double free). */ - if (__builtin_expect (old == p, 0)) - malloc_printerr ("double free or corruption (fasttop)"); - p->fd = PROTECT_PTR (&p->fd, old); - *fb = p; - } - else - do - { - /* Check that the top of the bin is not the record we are going to - add (i.e., double free). */ - if (__builtin_expect (old == p, 0)) - malloc_printerr ("double free or corruption (fasttop)"); - old2 = old; - p->fd = PROTECT_PTR (&p->fd, old); - } - while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) - != old2); + mchunkptr old = fastbin_push_chunk (fb, p); /* Check that size of fastbin chunk at the top is the same as size of the chunk that we are adding. We can dereference OLD @@ -4718,6 +4729,7 @@ static void malloc_consolidate(mstate av) maxfb = &fastbin (av, NFASTBINS - 1); fb = &fastbin (av, 0); do { + /* Synchronize with relase MO CAS in fastbin_push_chunk. */ p = atomic_exchange_acquire (fb, NULL); if (p != 0) { do {