From patchwork Tue Sep 17 14:33:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Boqun Feng X-Patchwork-Id: 13806220 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 901D6EE6426 for ; Tue, 17 Sep 2024 14:34:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9E9BE6B0082; Tue, 17 Sep 2024 10:34:58 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 999F16B0083; Tue, 17 Sep 2024 10:34:58 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 813006B0085; Tue, 17 Sep 2024 10:34:58 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 627BB6B0082 for ; Tue, 17 Sep 2024 10:34:58 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id E9E721C4109 for ; Tue, 17 Sep 2024 14:34:57 +0000 (UTC) X-FDA: 82574477034.20.B929B6B Received: from mail-qt1-f171.google.com (mail-qt1-f171.google.com [209.85.160.171]) by imf08.hostedemail.com (Postfix) with ESMTP id D484A160012 for ; Tue, 17 Sep 2024 14:34:55 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=aWUyo4zk; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.171 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726583686; a=rsa-sha256; cv=none; b=wsNV7xdf961LyFy8vrZGdD7+6GT+G00Ged0UGhpR3Y98Ys3wBsuxWPb3VwsesblBpq08HE 5XgTl3ORGiMpe+UphhgWFXLWFiOjEBxqwUxoUcUa1LW48q5YHiakNQ1+I3a2yBdxkEF5E0 VPFgH4xe6A54i6/14v5p6+w7HNugOtY= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=aWUyo4zk; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.171 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1726583686; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=FifQGheghn0VyIQYWu5CfuZMuqyOUGFJ5hoSCAZAAD4=; b=14LjldJOxLU6jDvqeJZI2MRcnBIrwiX0+2llMq9LedlXmHCJov/oQyC4HVXLh7csEUkyTg KqAGh5EfY5z1H9RWa9ylKX6JdKSOL8N+meAjDnqstQ81ePz/Wq0+Zi6hS6LqKrX0g2vWOa nF0xQ1KGzYQnCm3Aj9hLFSPLHtUepcg= Received: by mail-qt1-f171.google.com with SMTP id d75a77b69052e-4583083d019so31359591cf.3 for ; Tue, 17 Sep 2024 07:34:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1726583695; x=1727188495; darn=kvack.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:feedback-id:from:to:cc:subject:date:message-id:reply-to; bh=FifQGheghn0VyIQYWu5CfuZMuqyOUGFJ5hoSCAZAAD4=; b=aWUyo4zkyTR4A5NCkFrgG0Pse9h6F3luP86RZWWWUrESXPdDGIHscd2951U3buf256 HXPV7+QN+yQG4bpEX1OOAhKkIGKmyOgCENGOv9NfbTgyKxd/rzmqWcLJ0Z2NvfNglMba LDtrxnjvme2LFlVFW0ZQTYyU1BN1mRhUMgi8LkUMWOPV0WZSCRZovpGFj8/ZBdshMQIb CVVgo/cW4Pqdc/xUi3vuIuaTy4qXfdZoYppfV7f6ZtWl71HuDclvbLrOfQ0Keb/EqkHH tAv9Ro9WljIRlWwn23DWinhHeAaETBsgf/65PRPvAV4S3Vz7IM3MK+dCrwaUQ1x+y6Ml 0CAw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726583695; x=1727188495; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:feedback-id:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=FifQGheghn0VyIQYWu5CfuZMuqyOUGFJ5hoSCAZAAD4=; b=ivktkBlemQPnMQfMdijwlugTpoCFrS4wIE8zalmMeWgi1PEQ7DUqPcGMP077e8dpZG 273KkRGLLA5jYYdvdZBrpibesU+Lb1WrgCH3ghhR2SQVxwK07Eal+AZCMLY6wmYUd99h GM9KWXyl4jRTpxDSoDrTJ9RzGI9Lw3DkSlHoo01iHqnbHvbvJApy8Ba8gcJZMrbnR1Rr UEwsiE4uT1mKyJDC4vV4LiiyaZpfL3TyJXLXOeNC9iGGzRDPrAkdTZj70jZzV2ZBkfXU BEHx8cxCZWUPriKCLqLBIAt1iIq4sqCBFtpdPbQjEcQepzqi8yq+ssX1YWrZtVPSyaZZ VDCQ== X-Forwarded-Encrypted: i=1; AJvYcCU4rqwxR4ox/jCu7we/6N82yNwAgaNfqr7ioIFQ5JzRfZRBXC2qEgV7NbsqjbA0+j8U5XjS2Ba1zw==@kvack.org X-Gm-Message-State: AOJu0Ywo+p8rVxPkF06mQwE9Uh9vCO3AWZeriCHoc8oiocR+qn5ZC0pI ts9S5czj66FEYol2muwXpNiXtzvT6AuylZojnsvaJPsAicKfF3F6 X-Google-Smtp-Source: AGHT+IFEDpEW/g8o7DXp1PGDIP+TLu1QDoRIlmZZLelGzkSOBLY6btV0pEJFbxW5KZ7IqqhJdhL2Fw== X-Received: by 2002:ac8:59d3:0:b0:458:34df:1e65 with SMTP id d75a77b69052e-4599d29f812mr221153261cf.44.1726583694695; Tue, 17 Sep 2024 07:34:54 -0700 (PDT) Received: from fauth1-smtp.messagingengine.com (fauth1-smtp.messagingengine.com. [103.168.172.200]) by smtp.gmail.com with ESMTPSA id d75a77b69052e-459aacf57d9sm38782891cf.76.2024.09.17.07.34.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Sep 2024 07:34:54 -0700 (PDT) Received: from phl-compute-06.internal (phl-compute-06.phl.internal [10.202.2.46]) by mailfauth.phl.internal (Postfix) with ESMTP id 9F73C1200070; Tue, 17 Sep 2024 10:34:53 -0400 (EDT) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-06.internal (MEProxy); Tue, 17 Sep 2024 10:34:53 -0400 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudekjedgkedtucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnegoufhushhpvggtthffohhmrghinhculdegledmnecujfgurhep hffvvefufffkofgggfestdekredtredttdenucfhrhhomhepuehoqhhunhcuhfgvnhhguc eosghoqhhunhdrfhgvnhhgsehgmhgrihhlrdgtohhmqeenucggtffrrghtthgvrhhnpeef ledvieetieelffdtfeeiudffhffhvefhiedviefghfefvddutedvjedviefhkeenucffoh hmrghinhepghhoohhglhgvrdgtohhmpdhkvghrnhgvlhdrohhrghdplhhptgdrvghvvghn thhsnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepsg hoqhhunhdomhgvshhmthhprghuthhhphgvrhhsohhnrghlihhthidqieelvdeghedtieeg qddujeejkeehheehvddqsghoqhhunhdrfhgvnhhgpeepghhmrghilhdrtghomhesfhhigi hmvgdrnhgrmhgvpdhnsggprhgtphhtthhopedvhedpmhhouggvpehsmhhtphhouhhtpdhr tghpthhtoheplhhinhhugidqkhgvrhhnvghlsehvghgvrhdrkhgvrhhnvghlrdhorhhgpd hrtghpthhtoheprhgtuhesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthhopehl ihhnuhigqdhmmheskhhvrggtkhdrohhrghdprhgtphhtthhopehlkhhmmhesvhhgvghrrd hkvghrnhgvlhdrohhrghdprhgtphhtthhopehprghulhhmtghksehkvghrnhgvlhdrohhr ghdprhgtphhtthhopehfrhgvuggvrhhitgeskhgvrhhnvghlrdhorhhgpdhrtghpthhtoh epnhgvvghrrghjrdhuphgrughhhigrhieskhgvrhhnvghlrdhorhhgpdhrtghpthhtohep jhhovghlsehjohgvlhhfvghrnhgrnhguvghsrdhorhhgpdhrtghpthhtohepjhhoshhhse hjohhshhhtrhhiphhlvghtthdrohhrgh X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 17 Sep 2024 10:34:53 -0400 (EDT) From: Boqun Feng To: linux-kernel@vger.kernel.org, rcu@vger.kernel.org, linux-mm@kvack.org, lkmm@vger.kernel.org Cc: "Paul E. McKenney" , Frederic Weisbecker , Neeraj Upadhyay , Joel Fernandes , Josh Triplett , Boqun Feng , Uladzislau Rezki , Steven Rostedt , Mathieu Desnoyers , Lai Jiangshan , Zqiang , Peter Zijlstra , Ingo Molnar , Will Deacon , Waiman Long , Mark Rutland , Thomas Gleixner , Kent Overstreet , Linus Torvalds , Vlastimil Babka , maged.michael@gmail.com Subject: [RFC PATCH 0/4] Add hazard pointers to kernel Date: Tue, 17 Sep 2024 07:33:58 -0700 Message-ID: <20240917143402.930114-1-boqun.feng@gmail.com> X-Mailer: git-send-email 2.45.2 MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: 6waaf6ku6qbow46f77juunig5a1nwemh X-Rspamd-Queue-Id: D484A160012 X-Rspamd-Server: rspam02 X-HE-Tag: 1726583695-712892 X-HE-Meta: U2FsdGVkX19hgiRgZQalUYww7gnY8wAhmEhyVI2o/8vb5uMjkqd1hmhrSIsMBZdX0JYsF+ZsLUwDcaWE9FnOy7ogxtDXC1umWMok6JTgA5UGB6jUDlHOyY2Yn9eQYFezoQK4JMxt/K+TKmLTcT3aBhARDpPKmNetJEkOh/8GFU+r/H9XhXz4OB08F7Fe3rgZf1LlpQfWS36t2uAmYjIHAOOv9/4N9gMBP37O/U2bI+VoRD3obgScY7sHpW4ZrJYL4Z7+qrwE9+uRIGBk/Z8ejxYkirqghBbdrGR/AFsfHifCgIVuJWPwW38hdCRxsrfhlTDWFp32sDzFXM77GycF8YqtNL0noduYyyiQ9uVI+84hALnNwh1t4XaXmqXczaZGRp8a8t804ug+g6jqhL8l7GfiEZCf/aERxSmocCP69jBiKZ88FMtTbcweq+eWRINWVFxFJHbHuR4ldg3YU5m+G7weLcsQyZhQTJksKMFUGb2vNlpCOjSZvWOZedS8Xe/rjqv8ZvojOxDksL8n+GhevnF7ochodsImk5jSvG6+UARtS4CYmcP9kampVIK8Hy6UiImiF3vPnAIwk32jlwvpmLa/br28yv1A4JZn2HYz12BDTVVyDao29vaUaVRvEACNwkEMGB6prmhMV2Enw0e/Af6+LcNAMaK0YaHxCpSpkzH9JT5N80YShYGma81jTR4mGaiSfEl25I8IerbpvprpDDEie0QKZxhczq9DlpL2/Q8mSUxugtK7S/IFrZW6Aqdk0fsgbi9BKO55oP2YQOMB8By8JSiONdorGGXw3zLFrj7PHsYVzTXOOLuufBSw3JizL9R44yYIHjMMDQlI455mk0XNh+0nb2h/L0DOFM+P/dYjsRiyZmAqPBZxzumM+uINz/9czmDRuVqZ9quv/4fMZgkeGMkiFruMY8BfV6UD6DDIe6O4nc2ZRsbsuqXEaBweEsEfmI3BZiYnC3jBGGy 3KTYGg3i QvbTnCA/FHWS+1o/zLdxSIYRbk14ni89WfWon3u6grbTNO5OprfZLSCQ1TqHoS68qrEdrNEQIBersArxUTSiIBGNp5qPkmAXjpNgG6Y/dGCS0Kyy+ib9O+Yugf4NluVxQeHUrxcChgfDRngUq++m1fxywALADkM7AGM8acseLP6RNgincTsWGxpFimZnNpjLcBwtjOhmZRvOHnKy/JcndERZM2i3a4XWkWaDBhfwxycslh5JXPAuZSqEK2+l0pfD+REzC7JDUKhbZtCYTGvE4J5Du4uENCILq2Xa1jjRG54N/Dn+VouoDjOQZ+jE0W3YAn5Lnynu22hpxDW0LB9DZYoygDNH9T4EguXfx9Bo+YvB42pJUG/8lJILdRSxiX8863wlNSEZGDgNXixiGY6/yxnxg9nN7+6vJ2Es3woqr2d9vNh4241io0vcKDJRuqRoMHMssaGuk4k7pQj/A1HJOBlwEIzR4BB43RrKY/oGbyMks/rBXDaEifVAoNmvuXBY45LjoDf+IBg+lLQXUWH7bopRLQj0ULHUJw4HHF/tvHS8VrhTkVXZhs86ea4n2EtNSV1wXeL0b5AgGe62oYva+oWA3Ww== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Hi, This series introduces hazard pointers [1] to kernel space. A TL;DR description of hazard pointers is "a scalable refcounting mechanim with RCU-like API". More information can be found at [2]. The problem we are trying to resolve here is refcount scalability issues that cannot be resolved simply by RCU or SRCU (maybe due to the requirement of an unbound protect duration). Neeraj has tried it in the scalability issue[3] he has been working on, and he will share more information in our LPC session [4] (and I will update in the list for those who cannot make it to the session later). My micro-benchmark shows the hazard pointers provide very good scalability on par with percpu_ref/RCU/SRCU on the reader side: (refscale in x86_64 + PREEMPT=y, avg reader duration in ns) nreaders 1 8 32 percpu_ref 6.95123 10.0869 8.9674 rcu 2.97923 3.243 3.55077 hazptr 8.5991 8.40443 8.5762 srcu 16.7754 22.4807 20.2406 Things that we know are currently not working: * Handling module unload, probably needs a hazptr_barrier() similar to rcu_barrier(). * rcutorture support should be added to catch potential bugs (esp. for callback handling). * Improvement for updater side performance, currently all callbacks are handled in one work, this can be improved by using multiple work_structs or threads. Of course, I might create some bugs, so please take a look. Also love to hear anything on the current API. Any feedback is welcome! Patch #1 is the implemenation of hazptr, Paul and Neeraj contributed a lot, but all bugs are mine ;-) Patch 2-3 add micro-benchmarks for hazptr and percpu_ref. Patch #4 is a simple test I've used for development, I put it here just in case someone wants to give a quick try, eventually, we need to add hazptr to rcutorture (or has its own torture) for more testing. Regards, Boqun [1]: M. M. Michael, "Hazard pointers: safe memory reclamation for lock-free objects," in IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004 [2]: https://docs.google.com/document/d/113WFjGlAW4m72xNbZWHUSE-yU2HIJnWpiXp91ShtgeE/ [3]: https://lore.kernel.org/lkml/20240916050811.473556-1-Neeraj.Upadhyay@amd.com/ [4]: https://lpc.events/event/18/contributions/1731/ [5]: Herlihy, Maurice, Victor Luchangco, and Mark Moir. "The repeat offender problem: A mechanism for supporting dynamic-sized, lock-free data structures." International Symposium on Distributed Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. Boqun Feng (4): hazptr: Add initial implementation of hazard pointers refscale: Add benchmarks for hazptr refscale: Add benchmarks for percpu_ref WIP: hazptr: Add hazptr test sample include/linux/hazptr.h | 83 +++++++ kernel/Makefile | 1 + kernel/hazptr.c | 463 +++++++++++++++++++++++++++++++++++ kernel/rcu/refscale.c | 127 +++++++++- samples/Kconfig | 6 + samples/Makefile | 1 + samples/hazptr/hazptr_test.c | 87 +++++++ 7 files changed, 767 insertions(+), 1 deletion(-) create mode 100644 include/linux/hazptr.h create mode 100644 kernel/hazptr.c create mode 100644 samples/hazptr/hazptr_test.c