From patchwork Thu Jun 29 01:58:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Samuel Mendoza-Jonas X-Patchwork-Id: 114127 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp9339089vqr; Wed, 28 Jun 2023 19:10:56 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6yD7YlfVAvvEHJStY3NxLTn8cbSZraX3ggXOVJk1otGnkSMJzrZVmnJ0W9tT0utikouRlz X-Received: by 2002:a05:6a20:4418:b0:125:213e:8b68 with SMTP id ce24-20020a056a20441800b00125213e8b68mr27069261pzb.0.1688004655983; Wed, 28 Jun 2023 19:10:55 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1688004655; cv=none; d=google.com; s=arc-20160816; b=VPFh3ZtyuXtqtj1s6udBBVbmu7vFXUU+D3plJtDKDshM/wwQtEvIdwiH7yrpRh37NM qdaCzw2FOLO0nMRHM+RDFWksZqVXtcsZs+uvAP+3AlGTkj6zZWE92Xp3XEvm3AWKuR0u WtSievPtxH3efevss6hzWLgRDkRM/gf32ZRxsz0vQJM59onuyhiQ8IhRu+OIuJ/1OukD jY/TltlVm85TYDVSO/dRIiHXSi6kvdX4mO9SiWuqDng9t7bfwR744fyvxVBFwSl4OXpT 0nJ4BMvN8rb2l7TVCUFkNoyBe3Yvi/UqUk5QWwYNW0aiP85QVG03j0bjYyznE0+GdQF9 liWw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :message-id:date:subject:cc:to:from:dkim-signature; bh=Z5ADgpgRcm7ildcG3JRpr/Zcwf95I9lu4+eIDLt2QIQ=; fh=bVw2K4h921l+ufOzzQ/KgPDLVSnuB+Qf4xosHlmo9/8=; b=KeNDzHmD99N/WY0jjw9X7t0Gu33rP/SbBqTDqCmAto5g3jjKDVBagV/M4odFxyGmmU Mmjby6ItoR8e/Mp99GnX3CvvfBxanyk+sCAynOoOD9B1SKwiGeVnFQHHpGjAi5Z2H0kh /rH+Pg/e7EMhrH/MKJj97IJR+nwcIrQj/Nn9WxyFeHHeabqOu4j7op2k664aCXg9a8zI nd75wR68c/y1Sq63sFVs7xYp1UcvDz5ay3JMc1Jn9D35dl50fRNKeAFvAmgXKLqZVzEv xmtHS9p79ekEn4DaxWg25yUlqDeWPbQeea1UWnveCDlqEfl9i/pdzo2Rk6IIJY6Auyww SriQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@amazon.com header.s=amazon201209 header.b=hikrSbtC; 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=QUARANTINE sp=QUARANTINE dis=NONE) header.from=amazon.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id t64-20020a638143000000b0053fee168aabsi9711112pgd.742.2023.06.28.19.10.42; Wed, 28 Jun 2023 19:10:55 -0700 (PDT) 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=@amazon.com header.s=amazon201209 header.b=hikrSbtC; 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=QUARANTINE sp=QUARANTINE dis=NONE) header.from=amazon.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231784AbjF2B7Q (ORCPT + 99 others); Wed, 28 Jun 2023 21:59:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46416 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231494AbjF2B7K (ORCPT ); Wed, 28 Jun 2023 21:59:10 -0400 Received: from smtp-fw-9102.amazon.com (smtp-fw-9102.amazon.com [207.171.184.29]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C08982681; Wed, 28 Jun 2023 18:59:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1688003949; x=1719539949; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=Z5ADgpgRcm7ildcG3JRpr/Zcwf95I9lu4+eIDLt2QIQ=; b=hikrSbtCH2THGVDVNMfIqYzS9KMdkZyiZeAZi4CmawK2tsOoglkgKkmu +rG3RFSzU2z0j0nTjY8aIyZ1bMcjClPUwfnxXOnw84XJxPV8XH/XC2NFs uGHf0PSHvShuz/cQ/N6T8eNnEVdOTT3REL6JCNYxUrd1QK841dvZIlQtd E=; X-IronPort-AV: E=Sophos;i="6.01,167,1684800000"; d="scan'208";a="348439320" Received: from pdx4-co-svc-p1-lb2-vlan2.amazon.com (HELO email-inbound-relay-pdx-2a-m6i4x-1cca8d67.us-west-2.amazon.com) ([10.25.36.210]) by smtp-border-fw-9102.sea19.amazon.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 29 Jun 2023 01:59:09 +0000 Received: from EX19MTAUWA002.ant.amazon.com (pdx1-ws-svc-p6-lb9-vlan2.pdx.amazon.com [10.236.137.194]) by email-inbound-relay-pdx-2a-m6i4x-1cca8d67.us-west-2.amazon.com (Postfix) with ESMTPS id 24CC08064F; Thu, 29 Jun 2023 01:59:08 +0000 (UTC) Received: from EX19D001UWA002.ant.amazon.com (10.13.138.236) by EX19MTAUWA002.ant.amazon.com (10.250.64.202) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1118.26; Thu, 29 Jun 2023 01:59:07 +0000 Received: from u46989501580c5c.ant.amazon.com (10.88.130.162) by EX19D001UWA002.ant.amazon.com (10.13.138.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1118.30; Thu, 29 Jun 2023 01:59:06 +0000 From: Samuel Mendoza-Jonas To: CC: Stewart Smith , "David S . Miller" , David Ahern , Eric Dumazet , Jakub Kicinski , Paolo Abeni , , , , Samuel Mendoza-Jonas Subject: [PATCH net] net/ipv6: Reduce chance of collisions in inet6_hashfn() Date: Wed, 28 Jun 2023 18:58:44 -0700 Message-ID: <20230629015844.800280-1-samjonas@amazon.com> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 X-Originating-IP: [10.88.130.162] X-ClientProxiedBy: EX19D041UWA002.ant.amazon.com (10.13.139.121) To EX19D001UWA002.ant.amazon.com (10.13.138.236) X-Spam-Status: No, score=-4.4 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_MED, RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE, T_SCC_BODY_TEXT_LINE 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?1770001169976484695?= X-GMAIL-MSGID: =?utf-8?q?1770001169976484695?= From: Stewart Smith For both IPv4 and IPv6 incoming TCP connections are tracked in a hash table with a hash over the source & destination addresses and ports. However, the IPv6 hash is insufficient and can lead to a high rate of collisions. The IPv6 hash used an XOR to fit everything into the 96 bits for the fast jenkins hash, meaning it is possible for an external entity to ensure the hash collides, thus falling back to a linear search in the bucket, which is slow. We take the approach of hash half the data; hash the other half; and then hash them together. We do this with 3x jenkins hashes rather than 2x to calculate the hashing value for the connection covering the full length of the addresses and ports. While this may look like it adds overhead, the reality of modern CPUs means that this is unmeasurable in real world scenarios. In simulating with llvm-mca, the increase in cycles for the hashing code was ~5 cycles on Skylake (from a base of ~50), and an extra ~9 on Nehalem (base of ~62). In commit dd6d2910c5e0 ("netfilter: conntrack: switch to siphash") netfilter switched from a jenkins hash to a siphash, but even the faster hsiphash is a more significant overhead (~20-30%) in some preliminary testing. So, in this patch, we keep to the more conservative approach to ensure we don't add much overhead per SYN. In testing, this results in a consistently even spread across the connection buckets. In both testing and real-world scenarios, we have not found any measurable performance impact. Cc: stable@vger.kernel.org Fixes: 08dcdbf6a7b9 ("ipv6: use a stronger hash for tcp") Fixes: b3da2cf37c5c ("[INET]: Use jhash + random secret for ehash.") Signed-off-by: Stewart Smith Signed-off-by: Samuel Mendoza-Jonas --- include/net/ipv6.h | 4 +--- net/ipv6/inet6_hashtables.c | 5 ++++- 2 files changed, 5 insertions(+), 4 deletions(-) diff --git a/include/net/ipv6.h b/include/net/ipv6.h index 7332296eca44..f9bb54869d82 100644 --- a/include/net/ipv6.h +++ b/include/net/ipv6.h @@ -752,9 +752,7 @@ static inline u32 ipv6_addr_hash(const struct in6_addr *a) /* more secured version of ipv6_addr_hash() */ static inline u32 __ipv6_addr_jhash(const struct in6_addr *a, const u32 initval) { - u32 v = (__force u32)a->s6_addr32[0] ^ (__force u32)a->s6_addr32[1]; - - return jhash_3words(v, + return jhash_3words((__force u32)a->s6_addr32[1], (__force u32)a->s6_addr32[2], (__force u32)a->s6_addr32[3], initval); diff --git a/net/ipv6/inet6_hashtables.c b/net/ipv6/inet6_hashtables.c index b64b49012655..bb7198081974 100644 --- a/net/ipv6/inet6_hashtables.c +++ b/net/ipv6/inet6_hashtables.c @@ -33,7 +33,10 @@ u32 inet6_ehashfn(const struct net *net, net_get_random_once(&inet6_ehash_secret, sizeof(inet6_ehash_secret)); net_get_random_once(&ipv6_hash_secret, sizeof(ipv6_hash_secret)); - lhash = (__force u32)laddr->s6_addr32[3]; + lhash = jhash_3words((__force u32)laddr->s6_addr32[3], + (((u32)lport) << 16) | (__force u32)fport, + (__force u32)faddr->s6_addr32[0], + ipv6_hash_secret); fhash = __ipv6_addr_jhash(faddr, ipv6_hash_secret); return __inet6_ehashfn(lhash, lport, fhash, fport,