From patchwork Tue Feb 28 14:33:25 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Thomas Gleixner X-Patchwork-Id: 5943 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp3048688wrd; Tue, 28 Feb 2023 06:35:27 -0800 (PST) X-Google-Smtp-Source: AK7set9PL25QAlx2a34i9n3aoY66+WWudJt5QDxwF/dhFtSm31ac7fMMWH+G3SSqxNo79kaXAyCb X-Received: by 2002:a17:906:4f86:b0:8b1:788f:2198 with SMTP id o6-20020a1709064f8600b008b1788f2198mr2551208eju.19.1677594927560; Tue, 28 Feb 2023 06:35:27 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1677594927; cv=none; d=google.com; s=arc-20160816; b=NgnE5ZeL6Or0+2ytFFga7BWNr3weXSVOdtFypFP5wxge5PH8x8rKZGqx7XYO1robTa /6yKuWbJgbpm7rHI3LinFX9ypJcyuED2pKnxsqgWkN8l8SxvAINkEnYYuNUUesJ5Ru5n zpPOk+5gaEkVYoyeVhiGMAsgjZH5VJWy07O/Y1r9g7ZtmykwbOLqnfQPnvkCCBCH5Ko9 q4H26PhJtpirCMpsRsg35QsMe5GOpuBloEhEWFgW7Kv/B2ns4BWbONdZhMzkP/koqrQJ fgBaMm3pedlRzftVvJsXdCh+dmQaaNBnBkXbJTnzl0hwYmm4w5BN2+tgwZ2Hta2YrGC4 s8pA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:date:subject:cc:to:from:dkim-signature :dkim-signature:message-id; bh=Lb565lna/s6U3kiSF2MXBRiVLZf5H76cCRuDZ64GJmo=; b=kZpz7CZ8yOMvvqxOsz41+/Wiczxsycxv7w4FNb3HML3IShP7Vuy7dmVWiFoEikorFo DJBi/wrpKjVf1sFVMTuCPX/R06C/J9hjtFoUQcsIlak0PLJRUlOlvzKJDbIkRQqwDFWi X3oyPS2avNkDjY2pzbYtby6h1bgjswH50qOioaA93i819INHFtwQM0hq4HAjuqVo5PEZ KmTzlW5PJNBqO8iEvS+xP0GMEJwUF2Ralo93NaDEJVs94OmAQupqDrZ3MhCxyv4dp9K1 norSHN3SwADPcC0Avm9WNOwJ73wmtMURXgcDC3+GtSPcK6h3dO//KUVA167w/LNe7RCJ ohLQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=AHu1QN44; dkim=neutral (no key) header.i=@linutronix.de header.s=2020e header.b="HFL4ArZ/"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id x3-20020a170906148300b008b270fe3363si3526114ejc.679.2023.02.28.06.35.04; Tue, 28 Feb 2023 06:35:27 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=AHu1QN44; dkim=neutral (no key) header.i=@linutronix.de header.s=2020e header.b="HFL4ArZ/"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229847AbjB1Odc (ORCPT + 99 others); Tue, 28 Feb 2023 09:33:32 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56928 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229486AbjB1Oda (ORCPT ); Tue, 28 Feb 2023 09:33:30 -0500 Received: from galois.linutronix.de (Galois.linutronix.de [IPv6:2a0a:51c0:0:12e:550::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 70B32113D9; Tue, 28 Feb 2023 06:33:28 -0800 (PST) Message-ID: <20230228132118.978145284@linutronix.de> DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1677594805; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc; bh=Lb565lna/s6U3kiSF2MXBRiVLZf5H76cCRuDZ64GJmo=; b=AHu1QN44yS5yiMIIaQM/bhF9U6AEh/nZRBJVWFyICDSqk3P0vJLcJDVAqaIrnTaJgdCWjv Y4+p5PPsAH7FaBwIH95r2h8pR56X62fQMKvyEXrR5ZTA7zSxWBGzsPXjEPpnQKApgNBBJ/ +cR1qpOtrN+9RPUgHX4u8WlQz0LMbNQwwCT1XipIjsnpR8YVQ6xQf7p/7GwDhNhrXbDhNr nShFyqLoWwUq6zqjT+ug3ayEttdG/J+PJ0YwXbz34e7bExIFUQYp99B8X/As+tXx2t4Ejh ISJ07CvLK0rqWHkRFYLBv/13EcEEf6iA5Q8Ax0Wp0x169xPifESeqtcy6QNcrw== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1677594805; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc; bh=Lb565lna/s6U3kiSF2MXBRiVLZf5H76cCRuDZ64GJmo=; b=HFL4ArZ/QfvP9NVXbDuUui8LOdP2ihpwMWNvYqIGqxzGFQv32BRTNGxI4i04zfbG64mPWf bj7WStzSy3LAjKAw== From: Thomas Gleixner To: LKML Cc: Linus Torvalds , x86@kernel.org, Wangyang Guo , Arjan van De Ven , "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , netdev@vger.kernel.org, Will Deacon , Peter Zijlstra , Boqun Feng , Mark Rutland , Marc Zyngier Subject: [patch 0/3] net, refcount: Address dst_entry reference count scalability issues Date: Tue, 28 Feb 2023 15:33:25 +0100 (CET) X-Spam-Status: No, score=-4.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_MED,SPF_HELO_NONE, SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759085778591256145?= X-GMAIL-MSGID: =?utf-8?q?1759085778591256145?= Hi! Wangyang and Arjan reported a bottleneck in the networking code related to struct dst_entry::__refcnt. Performance tanks massively when concurrency on a dst_entry increases. This happens when there are a large amount of connections to or from the same IP address. The memtier benchmark when run on the same host as memcached amplifies this massively. But even over real network connections this issue can be observed at an obviously smaller scale (due to the network bandwith limitations in my setup, i.e. 1Gb). There are two factors which make this reference count a scalability issue: 1) False sharing dst_entry:__refcnt is located at offset 64 of dst_entry, which puts it into a seperate cacheline vs. the read mostly members located at the beginning of the struct. That prevents false sharing vs. the struct members in the first 64 bytes of the structure, but there is also dst_entry::lwtstate which is located after the reference count and in the same cache line. This member is read after a reference count has been acquired. The other problem is struct rtable, which embeds a struct dst_entry at offset 0. struct dst_entry has a size of 112 bytes, which means that the struct members of rtable which follow the dst member share the same cache line as dst_entry::__refcnt. Especially rtable::rt_genid is also read by the contexts which have a reference count acquired already. When dst_entry:__refcnt is incremented or decremented via an atomic operation these read accesses stall and contribute to the performance problem. 2) atomic_inc_not_zero() A reference on dst_entry:__refcnt is acquired via atomic_inc_not_zero() and released via atomic_dec_return(). atomic_inc_not_zero() is implemted via a atomic_try_cmpxchg() loop, which exposes O(N^2) behaviour under contention with N concurrent operations. Lightweight instrumentation exposed an average of 8!! retry loops per atomic_inc_not_zero() invocation in a userspace inc()/dec() loop running concurrently on 112 CPUs. There is nothing which can be done to make atomic_inc_not_zero() more scalable. The following series addresses these issues: 1) Reorder and pad struct dst_entry to prevent the false sharing. 2) Implement and use a reference count implementation which avoids the atomic_inc_not_zero() problem. It is slightly less performant in the case of the final 1 -> 0 transition, but the deconstruction of these objects is a low frequency event. get()/put() pairs are in the hotpath and that's what this implementation optimizes for. The algorithm of this reference count is only suitable for RCU managed objects. Therefore it cannot replace the refcount_t algorithm, which is also based on atomic_inc_not_zero(), due to a subtle race condition related to the 1 -> 0 transition and the final verdict to mark the reference count dead. See details in patch 2/3. It might be just my lack of imagination which declares this to be impossible and I'd be happy to be proven wrong. As a bonus the new rcuref implementation provides underflow/overflow detection and mitigation while being performance wise on par with open coded atomic_inc_not_zero() / atomic_dec_return() pairs even in the non-contended case. The combination of these two changes results in performance gains in micro benchmarks and also localhost and networked memtier benchmarks talking to memcached. It's hard to quantify the benchmark results as they depend heavily on the micro-architecture and the number of concurrent operations. The overall gain of both changes for localhost memtier ranges from 1.2X to 3.2X and from +2% to %5% range for networked operations on a 1Gb connection. A micro benchmark which enforces maximized concurrency shows a gain between 1.2X and 4.7X!!! Obviously this is focussed on a particular problem and therefore needs to be discussed in detail. It also requires wider testing outside of the cases which this is focussed on. Though the false sharing issue is obvious and should be addressed independent of the more focussed reference count changes. The series is also available from git: git://git.kernel.org/pub/scm/linux/kernel/git/tglx/devel.git I want to say thanks to Wangyang who analyzed the issue and provided the initial fix for the false sharing problem. Further thanks go to Arjan Peter, Marc, Will and Borislav for valuable input and providing test results on machines which I do not have access to. Thoughts? Thanks, tglx --- include/linux/rcuref.h | 89 +++++++++++ include/linux/types.h | 6 include/net/dst.h | 21 ++ include/net/sock.h | 2 lib/Makefile | 2 lib/rcuref.c | 311 ++++++++++++++++++++++++++++++++++++++++ net/bridge/br_nf_core.c | 2 net/core/dst.c | 26 --- net/core/rtnetlink.c | 2 net/ipv6/route.c | 6 net/netfilter/ipvs/ip_vs_xmit.c | 4 11 files changed, 436 insertions(+), 35 deletions(-)