From mboxrd@z Thu Jan 1 00:00:00 1970 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 DC454CFB451 for ; Mon, 7 Oct 2024 18:18:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id EF3616B0083; Mon, 7 Oct 2024 14:18:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E7C956B0085; Mon, 7 Oct 2024 14:18:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CD0DF6B0088; Mon, 7 Oct 2024 14:18:18 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id AF75F6B0083 for ; Mon, 7 Oct 2024 14:18:18 -0400 (EDT) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 2EF03140D99 for ; Mon, 7 Oct 2024 18:18:18 +0000 (UTC) X-FDA: 82647615876.02.8E26433 Received: from nyc.source.kernel.org (nyc.source.kernel.org [147.75.193.91]) by imf04.hostedemail.com (Postfix) with ESMTP id 6B19840005 for ; Mon, 7 Oct 2024 18:18:16 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=eYMWuHFh; dmarc=pass (policy=quarantine) header.from=kernel.org; spf=pass (imf04.hostedemail.com: domain of "SRS0=eCVx=RD=paulmck-ThinkPad-P17-Gen-1.home=paulmck@kernel.org" designates 147.75.193.91 as permitted sender) smtp.mailfrom="SRS0=eCVx=RD=paulmck-ThinkPad-P17-Gen-1.home=paulmck@kernel.org" ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1728324997; a=rsa-sha256; cv=none; b=h6j+rSvbJ54PTX0QgpuVioxO12ZjzH8pCNdxBWU4vrZ1k+TzRplybeeS3saxttTC3VjyyL +Z5O++VBuvP4FD6PxithzlDX4EdTnuYPb1PVm6GfAUu1IeRlDj2y/8XdlFF04PQYqqp4ty OmtPznXY9V1Xmiyzu3O+TR7yimWb8nE= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=eYMWuHFh; dmarc=pass (policy=quarantine) header.from=kernel.org; spf=pass (imf04.hostedemail.com: domain of "SRS0=eCVx=RD=paulmck-ThinkPad-P17-Gen-1.home=paulmck@kernel.org" designates 147.75.193.91 as permitted sender) smtp.mailfrom="SRS0=eCVx=RD=paulmck-ThinkPad-P17-Gen-1.home=paulmck@kernel.org" ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1728324997; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=pjHyjJTVhJTdaBpRphisxkDQvaZa9ZEzvNT0NZNMd7A=; b=hPapq4AZX8TnlYSMjYbF6cFptVQi5HK1Lq4/bgS9yfJmpFIFnwTclGh84ZFsmK+qnJAxbA XX8exhATEeENgJi9Nd5zJ7CTjU7qJ5rnagMaj1ISf9d7d4eH+fjGUYEgaaG+1bNPb2j6nn S1i9zbwAd7bquwTsEUoFknOqTkqDkOg= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by nyc.source.kernel.org (Postfix) with ESMTP id DD881A41F45; Mon, 7 Oct 2024 18:18:06 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 1B340C4CEC6; Mon, 7 Oct 2024 18:18:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1728325095; bh=A0/KfeW8kFe4SaoCo5h9qpqTYsDndvVMYxZSEAiT0ZQ=; h=Date:From:To:Cc:Subject:Reply-To:References:In-Reply-To:From; b=eYMWuHFhI1UgHQXm7m0Y33G/ah0+84x42wJKK6E03FtyWiBuW8YLuXtcEvKItewhn xDlIqZvcPbTmPN0a3/OcIOSDz5NGldxTcyg05mgS0MZlJoImpFW998BV1mt5a2pi2j zDsqRUlag2Of03xtyB+ubJQwjPGKUV80//waKG0hYC3vRPvD9ppDasWhlHs6MVB8SD jDeCk1BXHJXDlKVASNBIH/gw96EKdBAcpIokgGvPaEyj2f5p53oA207DooiOdXQk6C 6Rn9OVCBfXwcpgvMAWo4VoQnFBd9fyiFVga/b+VKD9fCVtlgOJKw29je5+xIEFaxsZ v4laO9pBCrShA== Received: by paulmck-ThinkPad-P17-Gen-1.home (Postfix, from userid 1000) id B7BE8CE1594; Mon, 7 Oct 2024 11:18:14 -0700 (PDT) Date: Mon, 7 Oct 2024 11:18:14 -0700 From: "Paul E. McKenney" To: Mathieu Desnoyers Cc: Peter Zijlstra , Boqun Feng , linux-kernel@vger.kernel.org, Linus Torvalds , Andrew Morton , Nicholas Piggin , Michael Ellerman , Greg Kroah-Hartman , Sebastian Andrzej Siewior , Will Deacon , Alan Stern , John Stultz , Neeraj Upadhyay , Frederic Weisbecker , Joel Fernandes , Josh Triplett , Uladzislau Rezki , Steven Rostedt , Lai Jiangshan , Zqiang , Ingo Molnar , Waiman Long , Mark Rutland , Thomas Gleixner , Vlastimil Babka , maged.michael@gmail.com, Mateusz Guzik , Jonas Oberhauser , rcu@vger.kernel.org, linux-mm@kvack.org, lkmm@lists.linux.dev Subject: Re: [RFC PATCH v2 3/4] hp: Implement Hazard Pointers Message-ID: <5d695bdd-afd2-4e9f-ba92-376a4b302566@paulmck-laptop> Reply-To: paulmck@kernel.org References: <20241004182734.1761555-1-mathieu.desnoyers@efficios.com> <20241004182734.1761555-4-mathieu.desnoyers@efficios.com> <20241005160444.GA18071@noisy.programming.kicks-ass.net> <20241007104030.GB4879@noisy.programming.kicks-ass.net> <1de5d6ac-7f44-48d6-a5f3-9839d436891a@efficios.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1de5d6ac-7f44-48d6-a5f3-9839d436891a@efficios.com> X-Rspamd-Queue-Id: 6B19840005 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 1mqdn3g7yzgf4m383sxqrezrikw1p65f X-HE-Tag: 1728325096-407704 X-HE-Meta: U2FsdGVkX1/LBRJtZN3Q14/euGfCeomFw50tNc6WQzjb3ueCuAf4WjsGJo9yshN0XUVEBO9ZIykQYyakN3PnUYlADaHUHPkXooP4kvlSl2y0jJpriywIrIwYVANypj3EoeBzBQyyHFJzWsXWk0YlH674Qlo81xfFcGwx62E92tzxaoSDEh1rrr19Yym+bU7J2kGXf8eFVq43UYcHtlDOwMNum+Jd1hRQa8LyZPeqiS5ZyoJhmoqN/TceBcfVo0Q2A+VHR7v7DVVLlZFTQSZ7sI6YeWR2PJC0tzdOpq9OXdne+RuM0CfXEN0HLmEmajVuaDN1oLUQqkboV8GP+YnNd+lAPtQgKUf1lWvuMkflWXC/rsZV2XCWe5rNh1bdl1K1hRDCDADM39ylaEMMAAVSa4UR2v5nJvsxOAlxoJHBArTUhkKuviLp8P4BrlSZbjUG/rXp4HcUhNm6oJJ4TZYw56P+59zfSp8ipmzdijJrM+fmLObQVTrszGSkZGk6XRIbg3xSWMy+6V3hkyq3mmTXdSAHA3n/XaviqIyHnGz1yfSK6s15BCSVICnw1cu8UEyxDT4O8GEGKaR2vsNemVCETzoNMNfzVAAPGbQfhIQPd4meRn6Or9t7ijN0YBTX76kRRzNqKE8j7asgkIEt8ImwzSxBZ52Z5l7qlYVKecMOC8wLqvYcZMvZqvueboIJg7GQP1rd8wjwQ++QyQTwFOafkpiq8eVbDrKr3Y5uXgW2Tu5QvtZciwgNRuo560oTp/G+5DQxkyd8gk8mtbcZbgGKpM0Lk79qkfvz2j+bCO02LRXcpKQypFMQZno7p54xpH+uMEfSIVNvHWaDQvcy4zEXonjDRapH7a7csD/mefIEGnBC6Z1gPPwyKActStNS/qZhJxz5VjSjJgDJ67muh47+vQtkkkWBm8kfcLAJnmH5ZDuNMob8cFy8uKwoxWClQEIZrOmwLaJPOHsKZez9ciM X1E9wVSS QrVGlev5pjObB0ys/D50qpQW59FoELsLCs1MqeznMZ80mUyw9ua1zvNzo6/ijja3rZBiFftM0MWsY4dCC2I7lqEuie0YvFzJRlTF96EIF6wJp6bA6o3KdhL4+IOWi6F0ouSgWAQjOfN3sIdG3vsBga1p1maAvYCN2/a5eDpvC1rEWGWnToO+W5dFCen7t7c44D+m8ooghgDNqQpQtXujy3tuGAfQSDS2ULmCYII7sC6X5GLdaPZK2dwD1Jy1sQq/7I/DRVeVQ+GPnz1TtPJJRdQPwjQUjNpfmwl23saqCP4MhS2O/SJzrwJ//Enct9mXaOFQdoWepYy6h/5ely3lZQSpKYGIHN6tAdSwxR1ZFX2xc7eCErm3jLzwVV4ewozjHV5W5jdLNkHon9euk2vsviiYRc/F1MRNtIAO/9Dx7UOlHLqt9qq6P/GsTeWZcMS58PfkOi8tWUajObhzEHSeeEN4qITHqZaCDNmMO5eHmv3opQ6RYwVknQGVb++ed4UD5INA6itKrQCaV8ENSEpQMddNh4v3an2deJlXCerXI1wwLDf7KzLB1x4kjOmNpL16LAWYba2Tzh42sW0gDj5pPp8QYy+YZnC123yU6gmQVtteVaR+3GyqiHNfP1tKMkm8yAzxOD6yU0KiXaT9c9QgK46h4qLdYfvwniSGc6SZl+GRgmkMoLl75HaVs+U7nyGAsHI9tRNXRkQfA17AEcBE/uw//QPo89Mj6I/kQ 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: On Mon, Oct 07, 2024 at 10:50:46AM -0400, Mathieu Desnoyers wrote: > On 2024-10-07 12:40, Peter Zijlstra wrote: > > On Sat, Oct 05, 2024 at 02:50:17PM -0400, Mathieu Desnoyers wrote: > > > On 2024-10-05 18:04, Peter Zijlstra wrote: > > > > > > > > > +/* > > > > > + * hp_allocate: Allocate a hazard pointer. > > > > > + * > > > > > + * Allocate a hazard pointer slot for @addr. The object existence should > > > > > + * be guaranteed by the caller. Expects to be called from preempt > > > > > + * disable context. > > > > > + * > > > > > + * Returns a hazard pointer context. > > > > > > > > So you made the WTF'o'meter crack, this here function does not allocate > > > > nothing. Naming is bad. At best this is something like > > > > try-set-hazard-pointer or somesuch. > > > > > > I went with the naming from the 2004 paper from Maged Michael, but I > > > agree it could be clearer. > > > > > > I'm tempted to go for "hp_try_post()" and "hp_remove()", basically > > > "posting" the intent to use a pointer (as in on a metaphorical billboard), > > > and removing it when it's done. > > > > For RCU we've taken to using the word: 'publish', no? > > I'm so glad you suggest this, because it turns out that from all > the possible words you could choose from, 'publish' is probably the > most actively confusing. I'll explain. > > Let me first do a 10'000 feet comparison of RCU vs Hazard Pointers > through a simple example: > > [ Note: I've renamed the HP dereference try_post to HP load try_post > based on further discussion below. ] > > *** RCU *** > > * Dereference RCU-protected pointer: > rcu_read_lock(); // [ Begin read transaction ] > l_p = rcu_dereference(p); // [ Load p: @addr or NULL ] > if (l_p) > [ use *l_p ...] > rcu_read_unlock(); // [ End read transaction ] > > * Publish @addr: addr = kmalloc(); > init(addr); > rcu_assign_pointer(p, addr); > > * Reclaim @addr: rcu_assign_pointer(p, NULL); // [ Unpublish @addr ] > synchronize_rcu(); // Wait for all pre-existing > // read transactions to complete. > kfree(addr); > > > *** Hazard Pointers *** > > * Load and post a HP-protected pointer: > l_p = hp_load_try_post(domain, &p, &slot); > if (l_p) { > [ use *l_p ...] > hp_remove(&slot, l_p); > } > > * Publish @addr: addr = kmalloc(); > init(addr); > rcu_assign_pointer(p, addr); > > * Reclaim @addr: rcu_assign_pointer(p, NULL); // [ Unpublish @addr ] > hp_scan(domain, addr, NULL); > kfree(addr); > > Both HP and RCU have publication guarantees, which can in fact be > implemented in the same way (e.g. rcu_assign_pointer paired with > something that respects address dependencies ordering). A stronger > implementation of this would be pairing a store-release with a > load-acquire: it works, but it would add needless overhead on > weakly-ordered CPUs. > > How the two mechanisms differ is in how they track when it is > safe to reclaim @addr. RCU tracks reader "transactions" begin/end, > and makes sure that all pre-existing transactions are gone before > synchronize_rcu() is allowed to complete. HP does this by tracking > "posted" pointer slots with a HP domain. As long as hp_scan observes > that HP readers are showing interest in @addr, it will wait. > > One notable difference between RCU and HP is that HP knows exactly > which pointer is blocking progress, and from which CPU (at least > with my per-CPU HP domain implementation). Therefore, it is possible > for HP to issue an IPI and make sure the HP user either completes its > use of the pointer quickly, or stops using it right away (e.g. making > the active mm use idle mm instead). > > One strength of RCU is that it can track use of a whole set of RCU > pointers just by tracking reader transaction begin/end, but this is > also one of its weaknesses: a long reader transaction can postpone > completion of grace period for a long time and increase the memory > footprint. In comparison, HP can immediately complete as soon as the > pointer it is scanning for is gone. Even better, it can send an IPI > to the belate CPU and abort use of the pointer using a callback. Plus, in contrast to hazard pointers, rcu_dereference() cannot say "no". This all sounds like arguments *for* use of the term "publish" for hazard pointers rather than against it. What am I missing here? Thanx, Paul > > > > > +/* > > > > > + * hp_dereference_allocate: Dereference and allocate a hazard pointer. > > > > > + * > > > > > + * Returns a hazard pointer context. Expects to be called from preempt > > > > > + * disable context. > > > > > + */ > > > > > > > > More terrible naming. Same as above, but additionally, I would expect a > > > > 'dereference' to actually dereference the pointer and have a return > > > > value of the dereferenced type. > > > > > > hp_dereference_try_post() ? > > > > > > > > > > > This function seems to double check and update the hp_ctx thing. I'm not > > > > at all sure yet wtf this is doing -- and the total lack of comments > > > > aren't helping. > > > > > > The hp_ctx contains the outputs. > > > > > > The function loads *addr_p to then try_post it into a HP slot. On success, > > > it re-reads the *addr_p (with address dependency) and if it still matches, > > > use that as output address pointer. > > > > > > I'm planning to remove hp_ctx, and just have: > > > > > > /* > > > * hp_try_post: Try to post a hazard pointer. > > > * > > > * Post a hazard pointer slot for @addr. The object existence should > > > * be guaranteed by the caller. Expects to be called from preempt > > > * disable context. > > > * > > > * Returns true if post succeeds, false otherwise. > > > */ > > > static inline > > > bool hp_try_post(struct hp_domain *hp_domain, void *addr, struct hp_slot **_slot) > > > [...] > > > > > > /* > > > * hp_dereference_try_post: Dereference and try to post a hazard pointer. > > > * > > > * Returns a hazard pointer context. Expects to be called from preempt > > > * disable context. > > > */ > > > static inline > > > void *__hp_dereference_try_post(struct hp_domain *hp_domain, > > > void * const * addr_p, struct hp_slot **_slot) > > > [...] > > > > > > #define hp_dereference_try_post(domain, p, slot_p) \ > > > ((__typeof__(*(p))) __hp_dereference_try_post(domain, (void * const *) p, slot_p)) > > > > This will compile, but do the wrong thing when p is a regular pointer, no? > > Right, at least in some cases the compiler may not complain, and people used to > rcu_dereference() will expect that "p" is the pointer to load rather than the > address of that pointer. This would be unexpected. > > I must admit that passing the address holding the pointer to load rather than > the pointer to load itself makes it much less troublesome in terms of macro > layers. But perhaps this is another example where we should wander away from the > beaten path and use a word different from "dereference" here. E.g.: > > /* > * Use a comma expression within typeof: __typeof__((void)**(addr_p), *(addr_p)) > * to generate a compile error if addr_p is not a pointer to a pointer. > */ > #define hp_load_try_post(domain, addr_p, slot_p) \ > ((__typeof__((void)**(addr_p), *(addr_p))) __hp_load_try_post(domain, (void * const *) (addr_p), slot_p)) > > > > > > > > > /* Clear the hazard pointer in @slot. */ > > > static inline > > > void hp_remove(struct hp_slot *slot) > > > [...] > > > > Differently weird, but better I suppose :-) > > If you find a better word than "remove" to pair with "post", I'm all in :) > > > > > > > > > > +void hp_scan(struct hp_slot __percpu *percpu_slots, void *addr, > > > > > + void (*retire_cb)(int cpu, struct hp_slot *slot, void *addr)) > > > > > +{ > > > > > + int cpu; > > > > > + > > > > > + /* > > > > > + * Store A precedes hp_scan(): it unpublishes addr (sets it to > > > > > + * NULL or to a different value), and thus hides it from hazard > > > > > + * pointer readers. > > > > > + */ > > > > > + > > > > > + if (!addr) > > > > > + return; > > > > > + /* Memory ordering: Store A before Load B. */ > > > > > + smp_mb(); > > > > > + /* Scan all CPUs slots. */ > > > > > + for_each_possible_cpu(cpu) { > > > > > + struct hp_slot *slot = per_cpu_ptr(percpu_slots, cpu); > > > > > + > > > > > + if (retire_cb && smp_load_acquire(&slot->addr) == addr) /* Load B */ > > > > > + retire_cb(cpu, slot, addr); > > > > > > > > Is retirce_cb allowed to cmpxchg the thing? > > > > > > It could, but we'd need to make sure the slot is not re-used by another > > > hp_try_post() before the current user removes its own post. It would > > > need to synchronize with the current HP user (e.g. with IPI). > > > > > > I've actually renamed retire_cb to "on_match_cb". > > > > Hmm, I think I see. Would it make sense to pass the expected addr to > > hp_remove() and double check we don't NULL out something unexpected? -- > > maybe just for a DEBUG option. > > > > I'm always seeing the NOHZ_FULL guys hating on this :-) > > That's a fair point. Sure, we can do this as an extra safety net. For now I > will just make the check always present, we can always move it to a debug > option later. > > And now I notice that hp_remove is also used for CPU hotplug (grep > matches for cpuhp_remove_state()). I wonder if we should go for something > more grep-friendly than "hp_", e.g. "hazptr_" and rename hp.h to hazptr.h ? > > Thanks, > > Mathieu > > > -- > Mathieu Desnoyers > EfficiOS Inc. > https://www.efficios.com >