From patchwork Tue Sep 17 14:33:59 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Boqun Feng X-Patchwork-Id: 13806221 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 126D9C3601A for ; Tue, 17 Sep 2024 14:35:01 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6DD176B0088; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6CCD76B008A; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 46AF76B0089; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 1FBD86B0085 for ; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id C1356160506 for ; Tue, 17 Sep 2024 14:35:00 +0000 (UTC) X-FDA: 82574477160.07.DD31BB4 Received: from mail-qk1-f181.google.com (mail-qk1-f181.google.com [209.85.222.181]) by imf23.hostedemail.com (Postfix) with ESMTP id 8CF39140022 for ; Tue, 17 Sep 2024 14:34:57 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=K7HlJhHc; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf23.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.222.181 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726583666; a=rsa-sha256; cv=none; b=z5zEK9yZf5/ln5gxr4Fe9ltCRTgIh1hLn6BZfFw8rhgGHL998tG0IBEUFlNNyOXLCYLV/Q ghN70HieaNEuT2wuzmRMbMculziIBhp7FT1V+Ic/BCEnbGpcVzVc5WKFDQ+4NoJKP135WT 52O2/QlFWEBv/GQZgAYlI++RTHa69mc= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=K7HlJhHc; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf23.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.222.181 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=1726583666; 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:in-reply-to:references:references:dkim-signature; bh=zZq7RPD+uH42F46mDIKK9Ztk0MZzott+JAYc6fmxJrg=; b=rnuNzKnZKTImddUVGQsCNw2ijydoRzuoyZaJ+8kOd7Qg/8JWdidI7xxcHIKXRflwOMMQPR WMLBsXi1S6h9apQxc1U4HAS5krUb5ZMXlH14aRJarkV+XA6KFHvAwMzMceM07pEyQ/O3PV 3os3P9RHmFU8om9iG9Pu/hjcvARAUgU= Received: by mail-qk1-f181.google.com with SMTP id af79cd13be357-7a9a7bea3cfso367420585a.1 for ; Tue, 17 Sep 2024 07:34:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1726583696; x=1727188496; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:from:to:cc:subject :date:message-id:reply-to; bh=zZq7RPD+uH42F46mDIKK9Ztk0MZzott+JAYc6fmxJrg=; b=K7HlJhHcFEww5UVJ2bXR9dldQYYD9kJZLvMKdmzvF7Fkbxzr7hh1AbGjOg38u/qisO yyOdjORBhA5FOXqLS+ldfb2Bf3I2Tw+mBbD2SJXyzXfErhb3mleHAEKPN8kN56Gt43Va Zl8qd6xTxdLjL+YlnkagUBIBz1KM/kgZ07drNNYcb1bYFmTgefQdBmmh6RNHePrU43kF 0wCIOl0ppTkU0++aE/im+JSrrqtCTN8nSwTP8aNwp7xA6JgwLr5pgRAl4cSjy6R0GRTg 3S1i6t1AvkgTD3dl7BmQUdZn1cebw6pv6OekMnoANDAHRDZPb1VIF44TLi/OpkJeG2Vq ZR5Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726583696; x=1727188496; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=zZq7RPD+uH42F46mDIKK9Ztk0MZzott+JAYc6fmxJrg=; b=SHTCO8pnjeI99gtbfRfMDPhbE/1IrXELO9keRWgebGpt2UFuXJtibI/KxoHLqfpP4B 4INKdx9IFsF/SDmz61/jlgq+2yaG6axyr98EfXYqUYrfoXgwEe3FdMKQ7PBJi+jkgROG 6/r1H3/NGMXMWIApTIAdj5J+nVZ9KMIAOSmIQ/1MSMOjZjCj89XkjR6Jb0i5P8hu4Toa E/nuY3a6abv6r/cQUn8LxJkxKs4yj3x65YQL0RJaEfF6FwHAipv1cEZBQrB6RHnmKvxD 8Q6oC8V5xQMIohBV97/2dE0isjaq6NT/U7IFKYZOefTFQ9GSKADIHIyky7q1XDzPo7am HSgA== X-Forwarded-Encrypted: i=1; AJvYcCU/1oHEmR5NYOe4UzLgob6Af+d/o3PV7wqzOqbZqFo7CFQLDmjbjUmocos93bk4qtJ6ETMPTqfxEQ==@kvack.org X-Gm-Message-State: AOJu0Yw69YeZTPWxg+t2I9AR/d3rpKgAPtnVqzsp5NFwCf4K8fNAnhMv 9jrwVxvXHUVigNbZ56pzuLp1qCvcDBAEmVXlZPyQG47/Ux1hxvfofV6wpbaE X-Google-Smtp-Source: AGHT+IF2pmEI6yhOYlc9yJ0coEnr4ACImy1rxYaWM0jfd3MyvAsabH8ssbs86MX7XRNikWoU3iGneA== X-Received: by 2002:a05:6214:498b:b0:6c5:72c0:728b with SMTP id 6a1803df08f44-6c573572609mr285955006d6.24.1726583696247; Tue, 17 Sep 2024 07:34:56 -0700 (PDT) Received: from fauth1-smtp.messagingengine.com (fauth1-smtp.messagingengine.com. [103.168.172.200]) by smtp.gmail.com with ESMTPSA id 6a1803df08f44-6c58c7aefb7sm35174946d6.124.2024.09.17.07.34.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Sep 2024 07:34:55 -0700 (PDT) Received: from phl-compute-12.internal (phl-compute-12.phl.internal [10.202.2.52]) by mailfauth.phl.internal (Postfix) with ESMTP id 34B341200070; Tue, 17 Sep 2024 10:34:55 -0400 (EDT) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-12.internal (MEProxy); Tue, 17 Sep 2024 10:34:55 -0400 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudekjedgjeelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhephffvvefufffkofgjfhgggfestdekredtredttden ucfhrhhomhepuehoqhhunhcuhfgvnhhguceosghoqhhunhdrfhgvnhhgsehgmhgrihhlrd gtohhmqeenucggtffrrghtthgvrhhnpeegleejiedthedvheeggfejveefjeejkefgveff ieeujefhueeigfegueehgeeggfenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpegsohhquhhnodhmvghsmhhtphgruhhthhhpvghrshhonhgrlhhi thihqdeiledvgeehtdeigedqudejjeekheehhedvqdgsohhquhhnrdhfvghngheppehgmh grihhlrdgtohhmsehfihigmhgvrdhnrghmvgdpnhgspghrtghpthhtohepvdeipdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehlihhnuhigqdhkvghrnhgvlhesvhhgvghrrd hkvghrnhgvlhdrohhrghdprhgtphhtthhopehrtghusehvghgvrhdrkhgvrhhnvghlrdho rhhgpdhrtghpthhtoheplhhinhhugidqmhhmsehkvhgrtghkrdhorhhgpdhrtghpthhtoh eplhhkmhhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgruhhlmhgt kheskhgvrhhnvghlrdhorhhgpdhrtghpthhtohepfhhrvgguvghrihgtsehkvghrnhgvlh drohhrghdprhgtphhtthhopehnvggvrhgrjhdruhhprgguhhihrgihsehkvghrnhgvlhdr ohhrghdprhgtphhtthhopehjohgvlhesjhhovghlfhgvrhhnrghnuggvshdrohhrghdprh gtphhtthhopehjohhshhesjhhoshhhthhrihhplhgvthhtrdhorhhg X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 17 Sep 2024 10:34:54 -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, Neeraj Upadhyay Subject: [RFC PATCH 1/4] hazptr: Add initial implementation of hazard pointers Date: Tue, 17 Sep 2024 07:33:59 -0700 Message-ID: <20240917143402.930114-2-boqun.feng@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: <20240917143402.930114-1-boqun.feng@gmail.com> References: <20240917143402.930114-1-boqun.feng@gmail.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Queue-Id: 8CF39140022 X-Rspamd-Server: rspam01 X-Stat-Signature: ydfftcfzfsahk3uyyd4mbyqf6qnqjumt X-HE-Tag: 1726583697-638258 X-HE-Meta: U2FsdGVkX1+vZoG/OwJs9w6jpy0Qj7YzQqCELMvkc0Dib4gqDuLhMm4lh694k6Z6B2jhVsKkugKP7tiTxijmZ+h0BqETozPR1sZxvENg3U5WptgNzNv5jFm2f4tj04gj3yUnbDU/OIv7ngO8d3bd0b4LsJNjqdQUprv9r0GlwAIir5DqvIxdT7qZMg9qdOeuCTToid2ws83uOumSvmhDZcySzilWCoZQkUdVqpu+ExZUNyFmAGVlVqvzN/kgc1aJzFTW6k5xNtOq0UuKWbC8kSCw5UVhBEDDqWKNrDe+WSBC5MtV6tU3DSKSEMbyB8y+nnL+5aKf1EwEnawYkpEIhx1Y6513EVKzt9rSFCp7UblHMEVO5I4eQjyAe1eI+3wb8Ul3zSBIGsC5Osv7k/U93oYfuH1B4jy3qmzPaSc6weoDvvTh38nDMegIkJvEnE9em2naO17zX4Y9cc0swkHpacnLyAhSw6idLWFTqFSMW8YxmRNkEBYqEiTI8fX25f0Z71pmxJGNNFi3bSyz9oXiwE8XG3bkYZgDDyu1mwAM72I927H1kdieooHGFUXjTytd0P6gKTsHQN0xPuW96lj2foBqLdFtxIh1l/pms9KS5bKsoSZa7HeLWUUQ2fwX5QD2HkYra2CrmzG25SlAyeDu3oex90P4rLaksGrzNJEBymYdzhihyWjk+YjPibfki+JH/l3kJ+twDph8iXSaAGbtOSLeAhRn9D+/sfEEY3I4TNgnPG7FTSD4WN9lUmr9pp19spUkcC723RrVrU9ViShkUR2lQPeQmk3aaGsVcUwh/d/6IwMBxvAGvntUQhLrnlg4tPdcR0RZe/i/p3ADyhpljsN9vAMToahWFicPpuyQ99zprr3XPiTzcxcUPhAhmpknZvMxvorD+WzNy1tqvnSEVvIyWtNNCfjtb+InkQG/lFLP4UvG3jRY/At7hs80rhR43FwqfAUd+k3XV7fqkbM 1pMhsa6K QId3xhSADaXPyTfp+sSuUv946FbLFYCiY4jQUEC5ZNyk3rMYm+JYhOVPQGEedP9NeS9P7F+BNGEhhH7oidpe5Su6JrWchqZFFERk2QoFLBuDPOJb2YIH2Tz2QARPHKw/VMXfC7GQAVr5TY9Gu63juivQv9X2L8JeEzMv8hsKYZfBw1hKOqnp3vtBkUL62n2iyDHuybklvkG3fkZljJI+cWKWtgXxqDxP77Mdn4MuL7X0olq5wA6t4S+0xEjG2MY1zStSiULjpBievL8AjiwLEIsB3IpzwbHWEnZuULJBD5vcxA2dHSeN/1qul2qR6tg/7vG8sSrjYvOgHMp7gNMLH7eVLvAIBn6Mm6Z99kSUrrDuWgen+/iV4HCYoU7dhXrjz2vizQwFyZ3rOOkr0J+I31WcRG00lapUE+4ggOILq/WhmYnz9X7hdAOTnl9Y3lw4vocnKZWwSqn3XajASyx/0mbNzL+r097oGUvLu/rQsD6YWz+/pM8iGPdagBKDvhQv7iZHXpZNdSfSIDhg= 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: Hazard pointers [1] provide a way to dynamically distribute refcounting and can be used to improve the scalability of refcounting without significant space cost. Hazard pointers are similar to RCU: they build the synchronization between two part, readers and updaters. Readers are refcount users, they acquire and release refcount. Updaters cleanup objects when there are no reader referencing them (via call_hazptr()). The difference is instead of waiting for a grace period, hazard pointers can free an object as long as there is no one referencing the object. This means for a particular workload, hazard pointers may have smaller memory footprint due to fewer pending callbacks. The synchronization between readers and updaters is built around "hazard pointer slots": a slot readers can use to store a pointer value. Reader side protection: 1. Read the value of a pointer to the target data element. 2. Store it to a hazard pointer slot. 3. Enforce full ordering (e.g. smp_mb()). 4. Re-read the original pointer, reset the slot and retry if the value changed. 5. Otherwise, the continued existence of the target data element is guaranteed. Updater side check: 1. Unpublish the target data element (e.g. setting the pointer value to NULL). 2. Enforce full ordering. 3. Read the value from a hazard pointer slot. 4. If the value doesn't match the target data element, then this slot doesn't represent a reference to it. 5. Otherwise, updater needs to re-check (step 3). To distribute the accesses of hazptr slots from different contexts, hazptr_context is introduced. Users need to define/allocate their own hazptr_context to allocate hazard pointer slots. For the updater side to confirm no existing reference, it needs to scan all the possible slots, and to speed up this process, hazptr_context also contains an rbtree node for each slot so that updater can cache the reader-scan result in an rbtree. The rbtree nodes are pre-allocated in this way to prevent "allocate memory to free memory" in extreme cases. [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 Co-developed-by: Paul E. McKenney Signed-off-by: Paul E. McKenney Co-developed-by: Neeraj Upadhyay Signed-off-by: Neeraj Upadhyay Signed-off-by: Boqun Feng --- include/linux/hazptr.h | 83 ++++++++ kernel/Makefile | 1 + kernel/hazptr.c | 463 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 547 insertions(+) create mode 100644 include/linux/hazptr.h create mode 100644 kernel/hazptr.c diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h new file mode 100644 index 000000000000..4548ca8c75eb --- /dev/null +++ b/include/linux/hazptr.h @@ -0,0 +1,83 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_HAZPTR_H +#define _LINUX_HAZPTR_H + +#include +#include +#include + +/* Hazard pointer slot. */ +typedef void* hazptr_t; + +#define HAZPTR_SLOT_PER_CTX 8 + +struct hazptr_slot_snap { + struct rb_node node; + hazptr_t slot; +}; + +/* + * A set of hazard pointer slots for a context. + * + * The context can be a task, CPU or reader (depends on the use case). It may + * be allocated statically or dynamically. It can only be used after calling + * init_hazptr_context(), and users are also responsible to call + * cleaup_hazptr_context() when it's not used any more. + */ +struct hazptr_context { + // The lock of the percpu context lists. + spinlock_t *lock; + + struct list_head list; + struct hazptr_slot_snap snaps[HAZPTR_SLOT_PER_CTX]; + ____cacheline_aligned hazptr_t slots[HAZPTR_SLOT_PER_CTX]; +}; + +void init_hazptr_context(struct hazptr_context *hzcp); +void cleanup_hazptr_context(struct hazptr_context *hzcp); +hazptr_t *hazptr_alloc(struct hazptr_context *hzcp); +void hazptr_free(struct hazptr_context *hzcp, hazptr_t *hzp); + +#define hazptr_tryprotect(hzp, gp, field) (typeof(gp))__hazptr_tryprotect(hzp, (void **)&(gp), offsetof(typeof(*gp), field)) +#define hazptr_protect(hzp, gp, field) ({ \ + typeof(gp) ___p; \ + \ + ___p = hazptr_tryprotect(hzp, gp, field); \ + BUG_ON(!___p); \ + ___p; \ +}) + +static inline void *__hazptr_tryprotect(hazptr_t *hzp, + void *const *p, + unsigned long head_offset) +{ + void *ptr; + struct callback_head *head; + + ptr = READ_ONCE(*p); + + if (ptr == NULL) + return NULL; + + head = (struct callback_head *)(ptr + head_offset); + + WRITE_ONCE(*hzp, head); + smp_mb(); + + ptr = READ_ONCE(*p); // read again + + if (ptr + head_offset != head) { // pointer changed + WRITE_ONCE(*hzp, NULL); // reset hazard pointer + return NULL; + } else + return ptr; +} + +static inline void hazptr_clear(hazptr_t *hzp) +{ + /* Pairs with smp_load_acquire() in reader scan. */ + smp_store_release(hzp, NULL); +} + +void call_hazptr(struct callback_head *head, rcu_callback_t func); +#endif diff --git a/kernel/Makefile b/kernel/Makefile index 3c13240dfc9f..7927264b9870 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -50,6 +50,7 @@ obj-y += rcu/ obj-y += livepatch/ obj-y += dma/ obj-y += entry/ +obj-y += hazptr.o obj-$(CONFIG_MODULES) += module/ obj-$(CONFIG_KCMP) += kcmp.o diff --git a/kernel/hazptr.c b/kernel/hazptr.c new file mode 100644 index 000000000000..f22ccc2a4a62 --- /dev/null +++ b/kernel/hazptr.c @@ -0,0 +1,463 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#include +#include +#include +#include +#include + +#define HAZPTR_UNUSED (1ul) + +/* Per-CPU data for hazard pointer management. */ +struct hazptr_percpu { + spinlock_t ctx_lock; /* hazptr context list lock */ + struct list_head ctx_list; /* hazptr context list */ + spinlock_t callback_lock; /* Per-CPU callback queue lock */ + struct callback_head *queued; /* Per-CPU callback queue */ + struct callback_head **tail; +}; + +/* + * Per-CPU data contains context lists and callbacks, which are maintained in a + * per-CPU maner to reduce potential contention. This means a global scan (for + * readers or callbacks) has to take each CPU's lock, but it's less problematic + * because that's a slowpath. + */ +DEFINE_PER_CPU(struct hazptr_percpu, hzpcpu); + +/* A RBTree that stores the reader scan result of all hazptr slot */ +struct hazptr_reader_tree { + spinlock_t lock; + struct rb_root root; +}; + +static void init_hazptr_reader_tree(struct hazptr_reader_tree *tree) +{ + spin_lock_init(&tree->lock); + tree->root = RB_ROOT; +} + +static bool is_null_or_unused(hazptr_t slot) +{ + return slot == NULL || ((unsigned long)slot) == HAZPTR_UNUSED; +} + +static int hazptr_node_cmp(const void *key, const struct rb_node *curr) +{ + unsigned long slot = (unsigned long)key; + struct hazptr_slot_snap *curr_snap = container_of(curr, struct hazptr_slot_snap, node); + unsigned long curr_slot = (unsigned long)(curr_snap->slot); + + if (slot < curr_slot) + return -1; + else if (slot > curr_slot) + return 1; + else + return 0; +} + +static bool hazptr_node_less(struct rb_node *new, const struct rb_node *curr) +{ + struct hazptr_slot_snap *new_snap = container_of(new, struct hazptr_slot_snap, node); + + return hazptr_node_cmp((void *)new_snap->slot, curr) < 0; +} + +/* Add the snapshot into a search tree. tree->lock must be held. */ +static inline void reader_add_locked(struct hazptr_reader_tree *tree, + struct hazptr_slot_snap *snap) +{ + lockdep_assert_held(&tree->lock); + BUG_ON(is_null_or_unused(snap->slot)); + + rb_add(&snap->node, &tree->root, hazptr_node_less); +} + +static inline void reader_add(struct hazptr_reader_tree *tree, + struct hazptr_slot_snap *snap) +{ + guard(spinlock_irqsave)(&tree->lock); + + reader_add_locked(tree, snap); +} + +/* Delete the snapshot from a search tree. tree->lock must be held. */ +static inline void reader_del_locked(struct hazptr_reader_tree *tree, + struct hazptr_slot_snap *snap) +{ + lockdep_assert_held(&tree->lock); + + rb_erase(&snap->node, &tree->root); +} + +static inline void reader_del(struct hazptr_reader_tree *tree, + struct hazptr_slot_snap *snap) +{ + guard(spinlock_irqsave)(&tree->lock); + + reader_del_locked(tree, snap); +} + +/* Find whether a read exists. tree->lock must be held. */ +static inline bool reader_exist_locked(struct hazptr_reader_tree *tree, + unsigned long slot) +{ + lockdep_assert_held(&tree->lock); + + return !!rb_find((void *)slot, &tree->root, hazptr_node_cmp); +} + +static inline bool reader_exist(struct hazptr_reader_tree *tree, + unsigned long slot) +{ + guard(spinlock_irqsave)(&tree->lock); + + return reader_exist_locked(tree, slot); +} + +/* + * Scan the readers from one hazptr context and update the global readers tree. + * + * Must be called with hzcp->lock held. + */ +static void hazptr_context_snap_readers_locked(struct hazptr_reader_tree *tree, + struct hazptr_context *hzcp) +{ + lockdep_assert_held(hzcp->lock); + + for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) { + /* + * Pairs with smp_store_release() in hazptr_{clear,free}(). + * + * Ensure + * + * + * + * [access protected pointers] + * hazptr_clear(); + * smp_store_release() + * // in reader scan. + * smp_load_acquire(); // is null or unused. + * [run callbacks] // all accesses from + * // reader must be + * // observed. + */ + hazptr_t val = smp_load_acquire(&hzcp->slots[i]); + + if (!is_null_or_unused(val)) { + struct hazptr_slot_snap *snap = &hzcp->snaps[i]; + + // Already in the tree, need to remove first. + if (!is_null_or_unused(snap->slot)) { + reader_del(tree, snap); + } + snap->slot = val; + reader_add(tree, snap); + } + } +} + +/* + * Initialize a hazptr context. + * + * Must be called before using the context for hazptr allocation. + */ +void init_hazptr_context(struct hazptr_context *hzcp) +{ + struct hazptr_percpu *pcpu = this_cpu_ptr(&hzpcpu); + + for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) { + hzcp->slots[i] = (hazptr_t)HAZPTR_UNUSED; + hzcp->snaps[i].slot = (hazptr_t)HAZPTR_UNUSED; + } + + guard(spinlock_irqsave)(&pcpu->ctx_lock); + list_add(&hzcp->list, &pcpu->ctx_list); + hzcp->lock = &pcpu->ctx_lock; +} + +struct hazptr_struct { + struct work_struct work; + bool scheduled; + + // list of callbacks, we move percpu queued callbacks into the global + // queued list in workqueue function. + spinlock_t callback_lock; + struct callback_head *queued; + struct callback_head **tail; + + struct hazptr_reader_tree readers; +}; + +static struct hazptr_struct hazptr_struct; + +/* + * Clean up hazptr context. + * + * Must call before freeing the context. This function also removes any + * reference held by the hazard pointer slots in the context, even + * hazptr_clear() or hazptr_free() is not called previously. + */ +void cleanup_hazptr_context(struct hazptr_context *hzcp) +{ + if (hzcp->lock) { + scoped_guard(spinlock_irqsave, hzcp->lock) { + list_del(&hzcp->list); + hzcp->lock = NULL; + } + + for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) { + struct hazptr_slot_snap *snap = &hzcp->snaps[i]; + + if (!is_null_or_unused(snap->slot)) + reader_del(&hazptr_struct.readers, snap); + } + } +} + +/* + * Allocate a hazptr slot from a hazptr_context. + * + * Return: NULL means fail to allocate, otherwise the address of the allocated + * slot. + */ +hazptr_t *hazptr_alloc(struct hazptr_context *hzcp) +{ + unsigned long unused; + + for (int i = 0; i < HAZPTR_SLOT_PER_CTX; i++) { + if (((unsigned long)READ_ONCE(hzcp->slots[i])) == HAZPTR_UNUSED) { + unused = HAZPTR_UNUSED; + + /* + * rwm-sequence is relied on here. + * + * This is needed since in case of a previous reader: + * + * + * [access protected pointers] + * hazptr_free(): + * smp_store_release(); // hzptr == UNUSED + * hazptr_alloc(): + * try_cmpxchg_relaxed(); // hzptr == NULL + * + * // in reader scan + * smp_load_acquire(); // is null + * [run callbacks] + * + * Because of the rwm-sequence of release operations, + * when callbacks are run, accesses from reader 1 must + * be already observed by the updater. + */ + if (try_cmpxchg_relaxed(&hzcp->slots[i], &unused, NULL)) { + return (hazptr_t *)&hzcp->slots[i]; + } + } + } + + return NULL; +} + +/* Free a hazptr slot. */ +void hazptr_free(struct hazptr_context *hzcp, hazptr_t *hzptr) +{ + WARN_ON(((unsigned long)*hzptr) == HAZPTR_UNUSED); + + /* Pairs with smp_load_acquire() in reader scan */ + smp_store_release(hzptr, (void *)HAZPTR_UNUSED); +} + +/* Scan all possible readers, and update the global reader tree. */ +static void check_readers(struct hazptr_struct *hzst) +{ + int cpu; + + for_each_possible_cpu(cpu) { + struct hazptr_percpu *pcpu = per_cpu_ptr(&hzpcpu, cpu); + struct hazptr_context *ctx; + + guard(spinlock_irqsave)(&pcpu->ctx_lock); + list_for_each_entry(ctx, &pcpu->ctx_list, list) + hazptr_context_snap_readers_locked(&hzst->readers, ctx); + } +} + +/* + * Start the background work for hazptr callback handling if not started. + * + * Must be called with hazptr_struct lock held. + */ +static void kick_hazptr_work(void) +{ + if (hazptr_struct.scheduled) + return; + + queue_work(system_wq, &hazptr_struct.work); + hazptr_struct.scheduled = true; +} + +/* + * Check which callbacks are ready to be called. + * + * Return: a callback list that no reader is referencing the corresponding + * objects. + */ +static struct callback_head *do_hazptr(struct hazptr_struct *hzst) +{ + struct callback_head *tmp, **curr; + struct callback_head *todo = NULL, **todo_tail = &todo; + + // Currently, the lock is unnecessary, but maybe we will have multiple + // work_structs sharing the same callback list in the future; + guard(spinlock_irqsave)(&hzst->callback_lock); + + curr = &hzst->queued; + + while ((tmp = *curr)) { + // No reader, we can free the object. + if (!reader_exist(&hzst->readers, (unsigned long)tmp)) { + // Add tmp into todo. + *todo_tail = tmp; + todo_tail = &tmp->next; + + // Delete tmp from ->queued and move to the next entry. + *curr = tmp->next; + } else + curr = &tmp->next; + } + + hzst->tail = curr; + + // Keep checking if callback list is not empty. + if (hzst->queued) + kick_hazptr_work(); + + *todo_tail = NULL; + + return todo; +} + +static void hazptr_work_func(struct work_struct *work) +{ + struct hazptr_struct *hzst = container_of(work, struct hazptr_struct, work); + struct callback_head *todo; + + // Advance callbacks from hzpcpu to hzst + scoped_guard(spinlock_irqsave, &hzst->callback_lock) { + int cpu; + + hzst->scheduled = false; + for_each_possible_cpu(cpu) { + struct hazptr_percpu *pcpu = per_cpu_ptr(&hzpcpu, cpu); + + guard(spinlock)(&pcpu->callback_lock); + + if (pcpu->queued) { + *(hzst->tail) = pcpu->queued; + hzst->tail = pcpu->tail; + pcpu->queued = NULL; + pcpu->tail = &pcpu->queued; + } + } + } + + // Pairs with the smp_mb() on the reader side. This guarantees that if + // the hazptr work picked up the callback from an updater and the + // updater set the global pointer to NULL before enqueue the callback, + // the hazptr work must observe a reader that protects the hazptr before + // the updater. + // + // + // ptr = READ_ONCE(gp); + // WRITE_ONCE(*hazptr, ptr); + // smp_mb(); // => ->strong-fence + // tofree = gp; + // ptr = READ_ONCE(gp); // re-read, gp is not NULL + // // => ->fre + // WRITE_ONCE(gp, NULL); + // call_hazptr(gp, ...): + // lock(->callback_lock); + // [queued the callback] + // unlock(->callback_lock);// => ->po-unlock-lock-po + // lock(->callback_lock); + // [move from hzpcpu to hzst] + // + // smp_mb(); => ->strong-fence + // ptr = READ_ONCE(*hazptr); + // // ptr == gp, otherwise => ->fre + // + // If ptr != gp, it means there exists a circle with the following + // memory ordering relationships: + // ->strong-fence ->fre ->po-unlock-lock-po ->strong-fence ->fre + // => (due to the definition of prop) + // ->strong-fence ->prop ->strong-fence ->hb ->prop + // => (rotate the circle) + // ->prop ->strong-fence ->prop ->strong-fence ->hb + // => (due to the definition of pb) + // ->pb ->pb + // but pb is acyclic according to LKMM, so this cannot happen. + smp_mb(); + check_readers(hzst); + + todo = do_hazptr(hzst); + + while (todo) { + struct callback_head *next = todo->next; + void (*func)(struct callback_head *) = todo->func; + + func(todo); + + todo = next; + } +} + +/* + * Put @head into the cleanup callback queue. + * + * @func(@head) will be called after no one is referencing the object. Caller + * must ensure the object has been unpublished before calling this. + */ +void call_hazptr(struct callback_head *head, rcu_callback_t func) +{ + struct hazptr_percpu *pcpu = this_cpu_ptr(&hzpcpu); + + head->func = func; + head->next = NULL; + + scoped_guard(spinlock_irqsave, &pcpu->callback_lock) { + *(pcpu->tail) = head; + pcpu->tail = &head->next; + } + + guard(spinlock_irqsave)(&hazptr_struct.callback_lock); + kick_hazptr_work(); +} + +static int init_hazptr_struct(void) +{ + int cpu; + + INIT_WORK(&hazptr_struct.work, hazptr_work_func); + + spin_lock_init(&hazptr_struct.callback_lock); + hazptr_struct.queued = NULL; + hazptr_struct.tail = &hazptr_struct.queued; + + for_each_possible_cpu(cpu) { + struct hazptr_percpu *pcpu = per_cpu_ptr(&hzpcpu, cpu); + + spin_lock_init(&pcpu->ctx_lock); + INIT_LIST_HEAD(&pcpu->ctx_list); + + spin_lock_init(&pcpu->callback_lock); + pcpu->queued = NULL; + pcpu->tail = &pcpu->queued; + + } + + init_hazptr_reader_tree(&hazptr_struct.readers); + + return 0; +} + +early_initcall(init_hazptr_struct); From patchwork Tue Sep 17 14:34:00 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Boqun Feng X-Patchwork-Id: 13806222 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 4A23BEE6426 for ; Tue, 17 Sep 2024 14:35:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B71876B008A; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B230A6B0089; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8B89F6B008C; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 5545F6B0085 for ; Tue, 17 Sep 2024 10:35:01 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id CCDB8120544 for ; Tue, 17 Sep 2024 14:35:00 +0000 (UTC) X-FDA: 82574477160.28.5A19702 Received: from mail-qk1-f175.google.com (mail-qk1-f175.google.com [209.85.222.175]) by imf06.hostedemail.com (Postfix) with ESMTP id 99A2418000B for ; Tue, 17 Sep 2024 14:34:58 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=OWcqMGpB; spf=pass (imf06.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.222.175 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1726583587; 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:in-reply-to:references:references:dkim-signature; bh=IDKpmr/a+FSU5QkWBrZE0xc7m3+8vAVQA9drcgUYXjs=; b=n77VDYDo4Oi8wGPIo6VVU/GShngLbZXzKPPkl1uIFcUrUzTyvyXSal1bH0/MBFS70I4yzj Qc8lUJz3bE/y1VO71Y2WZW3G+18m+eD++pKZnLUNyvNRamKGTO6viYl9a++/a0bt9NPahi Zl76Q4wKVzQLSe+LDlegGqZSitvtxpE= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726583587; a=rsa-sha256; cv=none; b=BmAQ+hCIWrpuizjOe6CD0WQNtbLYN9r8VhQsdEQcESCu8XBinbYbFKsvFwncKDK2HCStgU WtELHF9vIrGCUuqAxZ6jSxPcN+cVsgXH6gzs0YQKkz/ufgx+ySoP8+jbzbMTQmZL3/MWdE 5Gr6xMrAIC+VW15R+IqH/dEnwXMX0c4= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=OWcqMGpB; spf=pass (imf06.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.222.175 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-qk1-f175.google.com with SMTP id af79cd13be357-7a9ab721058so587741685a.1 for ; Tue, 17 Sep 2024 07:34:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1726583698; x=1727188498; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:from:to:cc:subject :date:message-id:reply-to; bh=IDKpmr/a+FSU5QkWBrZE0xc7m3+8vAVQA9drcgUYXjs=; b=OWcqMGpBvTVZlDUkiGZfrfRI/R/JIPEU5IFipX0VCVADN5e6ZulhjW8Jyy4z6MM0/x ams8qMkaITty6mmgX8FYbsiYlHpHXu5laCzzzu/hppeouDQP/v12RA81ROgtVz/X/3EF vVHceq8u1CvcJzUB0Q12JVhgGtXSt7q8zGu1afGjugcU8XaKjxco/dX4ziXDhO9WXQgc +0C7grgdLTVf4ObuKUcnSVLHloDtXAoEq2z3qGdu5oSjyyPsCw1ZAseNPYEpdmRSJ+Ry hHq2uKmxobeZ2ehNPGRo3/Ei9C3D+4spHGTZm3Fs2ZHChE+nGhcPH4+38sZGtZV/+S35 VNAw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726583698; x=1727188498; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=IDKpmr/a+FSU5QkWBrZE0xc7m3+8vAVQA9drcgUYXjs=; b=TaqOkZBV9C8NJg+OvuNuhCHwLCQkfSiszzYdvVRqBF+gjLWX3BdnARkb2POL4rOEzZ 78DobzKQMU786TGirvv4cPIRbA7UjXbYNStQDGc8Ah4Hy5driouS6hrzK+rDn+/jgsQ3 TaHW41Cq3iZGYxfUm4Kdiddr9DpKpmDN4XxhBUXE3LlP5CYVZ1dcuxyd2BbBLYIzYO/s gSZctZjus+PP8hT9DJv1qVFwimEs0rvNt6RXbXVkiMUfOoAgZ2vqzYfiVNBZ1y1lxXvl 2qyt3eqbDpR/XSYFil7WSyMWylH/KrLOq3pMfSr1bPumPhYraSS6rU8UQxoW8LbeB2vV XbGw== X-Forwarded-Encrypted: i=1; AJvYcCWXSVu9AxLbda36H2CiGxxnNbvM6tDa7e+CbJYZCTDRnMGNT2tY9gBIhZkEG1QRBmPEnzipPzSM9A==@kvack.org X-Gm-Message-State: AOJu0YzA8+kYVZuH2IkV80xWnj/2LrT4jVVoL2QGuobXCTKKnSKlMg1x hx7tRRy1OluEpqZwSaFltqd7R0ELrZFxnAWJc7Yw7wgK2LFFjgoq X-Google-Smtp-Source: AGHT+IG2fokLCq1TmoMpmwBtIu0E6iGiVOGurVZcFpBIdhqlPDe2hAN6K3EzM3w6osDlDfCf58pZgw== X-Received: by 2002:a05:620a:450c:b0:7a4:d56a:a928 with SMTP id af79cd13be357-7a9bf9abe50mr4404654785a.21.1726583697681; Tue, 17 Sep 2024 07:34:57 -0700 (PDT) Received: from fauth1-smtp.messagingengine.com (fauth1-smtp.messagingengine.com. [103.168.172.200]) by smtp.gmail.com with ESMTPSA id af79cd13be357-7ab3e9b39cesm363636485a.65.2024.09.17.07.34.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Sep 2024 07:34:57 -0700 (PDT) Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfauth.phl.internal (Postfix) with ESMTP id B5DBB1200070; Tue, 17 Sep 2024 10:34:56 -0400 (EDT) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-05.internal (MEProxy); Tue, 17 Sep 2024 10:34:56 -0400 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudekjedgjeelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhephffvvefufffkofgjfhgggfestdekredtredttden ucfhrhhomhepuehoqhhunhcuhfgvnhhguceosghoqhhunhdrfhgvnhhgsehgmhgrihhlrd gtohhmqeenucggtffrrghtthgvrhhnpeegleejiedthedvheeggfejveefjeejkefgveff ieeujefhueeigfegueehgeeggfenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpegsohhquhhnodhmvghsmhhtphgruhhthhhpvghrshhonhgrlhhi thihqdeiledvgeehtdeigedqudejjeekheehhedvqdgsohhquhhnrdhfvghngheppehgmh grihhlrdgtohhmsehfihigmhgvrdhnrghmvgdpnhgspghrtghpthhtohepvdehpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehlihhnuhigqdhkvghrnhgvlhesvhhgvghrrd hkvghrnhgvlhdrohhrghdprhgtphhtthhopehrtghusehvghgvrhdrkhgvrhhnvghlrdho rhhgpdhrtghpthhtoheplhhinhhugidqmhhmsehkvhgrtghkrdhorhhgpdhrtghpthhtoh eplhhkmhhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgruhhlmhgt kheskhgvrhhnvghlrdhorhhgpdhrtghpthhtohepfhhrvgguvghrihgtsehkvghrnhgvlh drohhrghdprhgtphhtthhopehnvggvrhgrjhdruhhprgguhhihrgihsehkvghrnhgvlhdr ohhrghdprhgtphhtthhopehjohgvlhesjhhovghlfhgvrhhnrghnuggvshdrohhrghdprh gtphhtthhopehjohhshhesjhhoshhhthhrihhplhgvthhtrdhorhhg X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 17 Sep 2024 10:34:56 -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 2/4] refscale: Add benchmarks for hazptr Date: Tue, 17 Sep 2024 07:34:00 -0700 Message-ID: <20240917143402.930114-3-boqun.feng@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: <20240917143402.930114-1-boqun.feng@gmail.com> References: <20240917143402.930114-1-boqun.feng@gmail.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 99A2418000B X-Stat-Signature: 1fjsyemwg5rmpq1sazcfq1gbmbp6tzgo X-HE-Tag: 1726583698-464548 X-HE-Meta: U2FsdGVkX1+z9pGTyST/9+xadNuif1FI+GINscd20Q0EtIT1Zd8YDagGrEkOxsIH2nebrT0KEf1wI+UOSZqLOdmnCG4Vlj0/uEhj9Cb7QNvchSozQiqmRtiQkt0s44py4EVDyDaU+SETktrIQGKY1p54oQxf5yS2lR+7qJwG4vaju8Loi0jusU4AawRvQIX1/eM/IaLkqANSddRSuWH1A4SZ47Vtu5oBYyjmIoKurcnROzYV3ImCSTq1KPTjUuqCeqnhTBArgT7f5Jyz3i3I3Sb4oBWQGfdMaz6bVutOCCiuOkeGncAWb92jial73n6W1ZwrdeNwC+1HYbE5guTqbWF0a+cQDNVmX9hHilZztdUI2QejpgXQtukPWvV8Lnm9w+z/OmtBKScXvDxo1i2ONzUF8J5AY9YZSxItHr/3t6Q42IaLRcRoMr4EiA/9kRImCdfekOS/3ZpZXPwtonpz4qyce3tM8Rk8lKqAomAQ/MHgJjBoWv1wRMyKmaqIv/1evnnSK50+wvWO1AjD7rHCtOHJRsUCtxOtkNwbdkxExMPZYdQSrVBaDdpE4Xm9tcf0vJywKhfKLiuRLqep2LiD7GCm8GqwdHCs6ubmFgeZycceA9UyCi3+rBIFhiSmO4V+l8rupal8gXIAbsJr1qs5ORaxIVUwmeWukgyBX6K5VRt2o72WV568An/I+hnjOt5daznUQtbJJuhmPaktr+ankOzpknBy13/JsPrebwr+5fNI4r76OXFn9UTEoWpaYjXgsbyjJEt0G/+p7Tc9gSTC42rT7GXrus+Y+e4ckH5pfC9P0MOEsXyDcXATEfjrPkjmUEsRpam3uEjLK1SP7AiER3BXGVU4Cz36RRP98OyO5MDJ25UY0lnpbPXcY3fkDc0kOHd8C3lDXOY1z6rIPFVX8/c27dpSmwfyHPtVDgrMkuU/Xn3fAX3OyDaafuWfyJicEdf27OTYcZIwkoA9Bk1 C8OuheUb kPaBzVnWGnAaAKLY4A1aGFo6twf2ROrD6IvzDKbVqWTlF7GzIcDhqVQDv66MA/NYYT2HPb4KAwwjI79CCM0MA8OAhYtSTwd4SGwTrcggHOH0qAhktjDIHPVKmlaylsKCeb5kI4vetxAAipjeYWZ6UT7KjzEcJyw8vugvPC34A8/+WvV9LpgGglsMXo8yIEtsRVUQ3M6HCUnNdBcu+lt49PjuHq9R5ITiFjet1Kh+vDodNLEpVhAE1+70mAogtl4h0YZwyYa6HdS/NMoLE+EA4SAa2JKiPtdUh25Lxo2YyA9s3BzuXWBgniNqYv4ypExkoDhYMbrf6AQlS4pQCxm1KlWcc9UrqM0p/AldR50jIz3pqIMMAgX6CX+9Z/OKcsigbY648K6kqFzXi2BSd63mh/lRTPgqsKmozAhmg11wrod67Epj5PUyw5SkfV3NOqJ7LVEYCCQjGHws3lkyrWFMkWOh5CBJcivCfMRWGF1+CatHBZR11VwMlLr4FnA== 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: Benchmarks for hazptr are added to evaluate the reader side performance between hazptr and other refcounting mechanisms. Signed-off-by: Boqun Feng --- kernel/rcu/refscale.c | 79 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 78 insertions(+), 1 deletion(-) diff --git a/kernel/rcu/refscale.c b/kernel/rcu/refscale.c index f4ea5b1ec068..7e76ae5159e6 100644 --- a/kernel/rcu/refscale.c +++ b/kernel/rcu/refscale.c @@ -35,6 +35,7 @@ #include #include #include +#include #include "rcu.h" @@ -316,6 +317,82 @@ static struct ref_scale_ops refcnt_ops = { .name = "refcnt" }; +struct hazptr_data { + struct callback_head head; + int i; +}; + +static struct hazptr_data *hazptr_data; + +static bool hazptr_scale_init(void) +{ + hazptr_data = kmalloc(sizeof(*hazptr_data), GFP_KERNEL); + + return !!hazptr_data; +} + +static void free_hazptr_data(struct callback_head *head) +{ + struct hazptr_data *tofree = container_of(head, struct hazptr_data, head); + + kfree(tofree); +} + +static void hazptr_scale_cleanup(void) +{ + if (hazptr_data) { + struct hazptr_data *tmp = hazptr_data; + WRITE_ONCE(hazptr_data, NULL); + + call_hazptr(&tmp->head, free_hazptr_data); + } +} + +static void hazptr_section(const int nloops) +{ + int i; + struct hazptr_context ctx; + hazptr_t *hzptr; + + init_hazptr_context(&ctx); + hzptr = hazptr_alloc(&ctx); + + for (i = nloops; i >= 0; i--) { + BUG_ON(!hazptr_protect(hzptr, hazptr_data, head)); + hazptr_clear(hzptr); + } + + hazptr_free(&ctx, hzptr); + cleanup_hazptr_context(&ctx); +} + +static void hazptr_delay_section(const int nloops, const int udl, const int ndl) +{ + int i; + struct hazptr_context ctx; + hazptr_t *hzptr; + + init_hazptr_context(&ctx); + hzptr = hazptr_alloc(&ctx); + + for (i = nloops; i >= 0; i--) { + BUG_ON(!hazptr_protect(hzptr, hazptr_data, head)); + un_delay(udl, ndl); + hazptr_clear(hzptr); + } + + hazptr_free(&ctx, hzptr); + cleanup_hazptr_context(&ctx); +} + +static struct ref_scale_ops hazptr_ops = { + .init = hazptr_scale_init, + .cleanup = hazptr_scale_cleanup, + .readsection = hazptr_section, + .delaysection = hazptr_delay_section, + .name = "hazptr" +}; + // Definitions for rwlock static rwlock_t test_rwlock; @@ -1081,7 +1158,7 @@ ref_scale_init(void) static struct ref_scale_ops *scale_ops[] = { &rcu_ops, &srcu_ops, RCU_TRACE_OPS RCU_TASKS_OPS &refcnt_ops, &rwlock_ops, &rwsem_ops, &lock_ops, &lock_irq_ops, &acqrel_ops, &clock_ops, &jiffies_ops, - &typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, + &typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, &hazptr_ops, }; if (!torture_init_begin(scale_type, verbose)) From patchwork Tue Sep 17 14:34:01 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Boqun Feng X-Patchwork-Id: 13806223 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 96097C3601A for ; Tue, 17 Sep 2024 14:35:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 755A26B0089; Tue, 17 Sep 2024 10:35:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7039C6B0092; Tue, 17 Sep 2024 10:35:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 50ABA6B008C; Tue, 17 Sep 2024 10:35:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 2EF586B0085 for ; Tue, 17 Sep 2024 10:35:03 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id D64E9160538 for ; Tue, 17 Sep 2024 14:35:02 +0000 (UTC) X-FDA: 82574477244.16.16348BC Received: from mail-yb1-f170.google.com (mail-yb1-f170.google.com [209.85.219.170]) by imf17.hostedemail.com (Postfix) with ESMTP id AC20C40009 for ; Tue, 17 Sep 2024 14:35:00 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=nSreRGDn; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf17.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.219.170 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726583691; a=rsa-sha256; cv=none; b=oW1RUcB0Svclp1474ylbd1aiEJhn/OGZ3Z0imsCmIwxj8+PNBanSLoQp5zQ6bYcXt2kMFA NgCH5r863GldoJrneX+cfh4loslAB/InE7O3w0nvZmFrFLCaS+YmaxRjb7EsHnRlDI6Aqw Qf7pEfRKNFcktxLZjQZ8/BFhdwNQPys= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=nSreRGDn; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf17.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.219.170 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=1726583691; 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:in-reply-to:references:references:dkim-signature; bh=GcfRMZ3iyMDLyZX4twHVpqBTdlI1aOiND6/+aYkmmFI=; b=DTUokpJm2OUBW1ORvE9VVjqf+x1iQlLJvrRieKDYyCPloDraHJ0XKcZuyjtxN/LFAhUcd4 CNPZYEELqvoQlat3Lck22jACNZjHILz8wXP9DFJJqCR9zaP1wqTZs2p16xHi7yO1Nbu3J8 WssA8g8U8Hw+fjiASLIBH/XbMMrvUqc= Received: by mail-yb1-f170.google.com with SMTP id 3f1490d57ef6-e1a9e4fa5aaso5496565276.2 for ; Tue, 17 Sep 2024 07:35:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1726583700; x=1727188500; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:from:to:cc:subject :date:message-id:reply-to; bh=GcfRMZ3iyMDLyZX4twHVpqBTdlI1aOiND6/+aYkmmFI=; b=nSreRGDn437uvRl4CbHtsthTjgdOAe20YAbnJOErzLWDwMTr/eh48MsNJSW7e9sxup 6a0O6nQMuGSdm0HzQFyWpxxy2xN5+As6/kNDq0M9Ta9vNo1HqMphiH8JnkOtHI03md3c ynktDqEIU9DatDyXayW3QvVa0hcsroqU5M8YHyPYvPeZ0758wJZYHk0q3hrsEV9C/H/N 9XciIGkj/zgHPdMUjJd4M0Zzgw8i7S1ZmQl+Zuw7fpdiyvUBsf8MKRAjdnlK/oXyFirA 6t4mP4SfqnNTJKgKDDTI9/m1haBKGxXy2dM7T27JPQBDVbs0lMBHceqleZxbhpMJPdyy qdRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726583700; x=1727188500; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=GcfRMZ3iyMDLyZX4twHVpqBTdlI1aOiND6/+aYkmmFI=; b=hhY3WsV8f7NtlypJt+SYhi7BKnQbcC3WERT53Yjy0qwHQLYXeKPOOpWHb/0vrLDoZy TyjGn2k813c9+SbmazTJcxlWUB5tIe+FZ6xynnbjFlYnf2NMePVp09SEXoKxvwBbFb4y geLyT/Xg4zmMLPm6e6yvOHNb/En4H9sWJyft5k7D8liUO+ouJeC6ZZyjP82mssueHiZz fCgphBqSqwQj1XjVTBb5xKyHJl5XPaHZpdCRdzRojDyidHN0TI0NokwcNOUaStsiZton A5iXMr6oFYrbu37oE9rtkRWdxkIDhoreNrpifOidXG7EVn8fypsnMlu/hNHgayyTE1HA szJQ== X-Forwarded-Encrypted: i=1; AJvYcCViiVWpm9M2xFj5nTJGr88yf252x/4OQ9dtUiG/8FKkrMtek0E8Mu5UzT+HtvA8t6aJzbcpVV5Oyg==@kvack.org X-Gm-Message-State: AOJu0Ywor6tSe2r2Ao4XQxDX8MRZVDFZ9JDq2vSis3b7VVe3tnhOudMM hIHWChgEqZVnGmvE3e8Z7vI3iLmICwejkaVfG9MKvxutjlBal0LX X-Google-Smtp-Source: AGHT+IGuBl7w6kHeocxSsrq7wz1PL/D3xhcWK31fEFq1kkjp/eaeFPUIN6wONAeMPCU446DmR2QvTw== X-Received: by 2002:a05:6902:cc7:b0:e13:ceaa:59d9 with SMTP id 3f1490d57ef6-e1d9dc41795mr12290884276.41.1726583699724; Tue, 17 Sep 2024 07:34:59 -0700 (PDT) Received: from fauth1-smtp.messagingengine.com (fauth1-smtp.messagingengine.com. [103.168.172.200]) by smtp.gmail.com with ESMTPSA id 6a1803df08f44-6c58c7da98bsm34819796d6.145.2024.09.17.07.34.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Sep 2024 07:34:59 -0700 (PDT) Received: from phl-compute-04.internal (phl-compute-04.phl.internal [10.202.2.44]) by mailfauth.phl.internal (Postfix) with ESMTP id 7E0841200070; Tue, 17 Sep 2024 10:34:58 -0400 (EDT) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-04.internal (MEProxy); Tue, 17 Sep 2024 10:34:58 -0400 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudekjedgjeelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhephffvvefufffkofgjfhgggfestdekredtredttden ucfhrhhomhepuehoqhhunhcuhfgvnhhguceosghoqhhunhdrfhgvnhhgsehgmhgrihhlrd gtohhmqeenucggtffrrghtthgvrhhnpeegleejiedthedvheeggfejveefjeejkefgveff ieeujefhueeigfegueehgeeggfenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpegsohhquhhnodhmvghsmhhtphgruhhthhhpvghrshhonhgrlhhi thihqdeiledvgeehtdeigedqudejjeekheehhedvqdgsohhquhhnrdhfvghngheppehgmh grihhlrdgtohhmsehfihigmhgvrdhnrghmvgdpnhgspghrtghpthhtohepvdehpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehlihhnuhigqdhkvghrnhgvlhesvhhgvghrrd hkvghrnhgvlhdrohhrghdprhgtphhtthhopehrtghusehvghgvrhdrkhgvrhhnvghlrdho rhhgpdhrtghpthhtoheplhhinhhugidqmhhmsehkvhgrtghkrdhorhhgpdhrtghpthhtoh eplhhkmhhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgruhhlmhgt kheskhgvrhhnvghlrdhorhhgpdhrtghpthhtohepfhhrvgguvghrihgtsehkvghrnhgvlh drohhrghdprhgtphhtthhopehnvggvrhgrjhdruhhprgguhhihrgihsehkvghrnhgvlhdr ohhrghdprhgtphhtthhopehjohgvlhesjhhovghlfhgvrhhnrghnuggvshdrohhrghdprh gtphhtthhopehjohhshhesjhhoshhhthhrihhplhgvthhtrdhorhhg X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 17 Sep 2024 10:34:57 -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 3/4] refscale: Add benchmarks for percpu_ref Date: Tue, 17 Sep 2024 07:34:01 -0700 Message-ID: <20240917143402.930114-4-boqun.feng@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: <20240917143402.930114-1-boqun.feng@gmail.com> References: <20240917143402.930114-1-boqun.feng@gmail.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: 46iastom6bpggqg7aqz6km37noikfof7 X-Rspamd-Queue-Id: AC20C40009 X-Rspamd-Server: rspam02 X-HE-Tag: 1726583700-682198 X-HE-Meta: U2FsdGVkX1/48uisqpsVgPlcAqlddcFHQVOFpsHeoIjHwi0P+kIIhPDi+Zl4ovD4W97+w8HgcAgVP0bJBbosGWG8y/iPHZecO2FK8dmh4kKxx3xB5qIZ7pwy+o6SMuafJ8eFtNZzEXrbweHMWfYt6mll3ZlJoliZg7mTamy5+Lvj+1f7zI7U7koryH+XaQSGjqJECAJNzuj/zckNx0+XQ4zueT5eC0/ssr13uNyTffoRkeFrgu9nUv/s20KfXGk1jRTfzH5OZAIE2EYIoW8tfYb1cevirW6lMUyrb2RNKELFnj9gpynZ3u+c2Gho3TdkS75nwA7z/pkOZDT+CFfJDhiUeTEKha3G8qDnFrtEtNWgFwAPC4NvAEHp7Z1nOjDC80HFVg1IpGmAa/gUO/Qgwzu1RbxYUMAmygjp5gHkSrsXLm+ghuy6C17fXAbfGa3OCcbiVGLJY74ByRHrHZ9UfX7j3Qc6BuK9VWshITyXSzut3F9Ulg/OiQXogRwN9vZOYp2oh67OpbxVqlWpvWd674eFs1PkIyEfSflFTee5jXB+zKuFR+pzi6yEvEXnJ3tQdAEld7vnx6ukl6ixr+pLMp1cuo8AcW/WwngV9YGVjOD4k2bVaN+QuVJpvfZe7UtIMLHKpFjbqbkUm7hZoIYFnlVzm93vJnAfx+nDD6veomwIe0ZNGRCRhnBtcJcnhfvtLGBFUgnTqr/LU1eLxuBnCecWkT9cznbrpJBgRvczar8VkgXHHbXfmwZMZES94vR+uNC/utk7fJvkGeaPhjFz+ZTwSf5vPyZMYE2aOFjiyJ4DQFRE/RlIxv1/LoXB7H5lCY1JQm9h7bF25MxjJZ5f7Jtznvh1f8c2+CeRZ+0aBbxSW4Sf2WyadFtQOmbBpqbcY5NmVXV06FdfKlp+zEbeC4nJtpWBLFz78l7PjYyfpOfJVqRG8QA/SfuubD2hhZv02WSQTu5zHo2E5bZZ5h2 Oak7YDaL 8DcuhQPUbou8TcYzA4rT7YsuH9grKpHdxOtMS3d69A+I3XCuEsqERZHqiSbCGg7/4qULkP3Bk6VduW3lxxXxEExrYHOijiu3GWgtSotRINKPKu4xJxPItoRHnoLEYaq1je+bJOoKD2XnrhpQW/E+vZo47/qMeG+wAkRX41m6LaoCKyCboZ3xsoz9jUy3JHXw/j1s9uO7D+nWSIfq3qVnKJoRPt+j4QLL+hKF/SX9jysxAi27FGtAMPHmgrRB1MEpA/WDpxXU9z9S3xsvNkcb+otOp+CF9QetrAqwuxBi293R+lpC0l3q/W3uVybbADJRGLTVD5nhjkVWdzGQk3rGb3IJABaQC8vzt2WhasWZMeXqkg579p0746EjkZw5/NBVDT0owakAXqyWchWdDsVk5we26AGEijYk1G1cmGewsdBhIrXClxqV7Qu4sFcmk1icXOwKCEaXS79ScdrTdpHCgBrNKfBtuWJhAe4ux8kGZSlRjRaL5phtGEc1+gR6tpSBQgyrg 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: Benchmarks for percpu_ref are added to evaluate the reader side performance between percpu_ref and other refcounting mechanisms. Signed-off-by: Boqun Feng --- kernel/rcu/refscale.c | 50 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 49 insertions(+), 1 deletion(-) diff --git a/kernel/rcu/refscale.c b/kernel/rcu/refscale.c index 7e76ae5159e6..97b73c980c5d 100644 --- a/kernel/rcu/refscale.c +++ b/kernel/rcu/refscale.c @@ -393,6 +393,54 @@ static struct ref_scale_ops hazptr_ops = { .name = "hazptr" }; +struct percpu_ref percpu_ref; + +static void percpu_ref_dummy(struct percpu_ref *ref) {} + +static bool percpu_ref_scale_init(void) +{ + int ret; + + ret = percpu_ref_init(&percpu_ref, percpu_ref_dummy, PERCPU_REF_INIT_ATOMIC, GFP_KERNEL); + percpu_ref_switch_to_percpu(&percpu_ref); + + return !ret; +} + +static void percpu_ref_scale_cleanup(void) +{ + percpu_ref_exit(&percpu_ref); +} + +static void percpu_ref_section(const int nloops) +{ + int i; + + for (i = nloops; i >= 0; i--) { + percpu_ref_get(&percpu_ref); + percpu_ref_put(&percpu_ref); + } +} + +static void percpu_ref_delay_section(const int nloops, const int udl, const int ndl) +{ + int i; + + for (i = nloops; i >= 0; i--) { + percpu_ref_get(&percpu_ref); + un_delay(udl, ndl); + percpu_ref_put(&percpu_ref); + } +} + +static struct ref_scale_ops percpu_ref_ops = { + .init = percpu_ref_scale_init, + .cleanup = percpu_ref_scale_cleanup, + .readsection = percpu_ref_section, + .delaysection = percpu_ref_delay_section, + .name = "percpu_ref" +}; + // Definitions for rwlock static rwlock_t test_rwlock; @@ -1158,7 +1206,7 @@ ref_scale_init(void) static struct ref_scale_ops *scale_ops[] = { &rcu_ops, &srcu_ops, RCU_TRACE_OPS RCU_TASKS_OPS &refcnt_ops, &rwlock_ops, &rwsem_ops, &lock_ops, &lock_irq_ops, &acqrel_ops, &clock_ops, &jiffies_ops, - &typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, &hazptr_ops, + &typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops, &hazptr_ops, &percpu_ref_ops, }; if (!torture_init_begin(scale_type, verbose)) From patchwork Tue Sep 17 14:34:02 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Boqun Feng X-Patchwork-Id: 13806224 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 1E686EE6426 for ; Tue, 17 Sep 2024 14:35:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8B4096B008C; Tue, 17 Sep 2024 10:35:04 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 865226B0092; Tue, 17 Sep 2024 10:35:04 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6673B6B0093; Tue, 17 Sep 2024 10:35:04 -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 4206E6B008C for ; Tue, 17 Sep 2024 10:35:04 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 04FB0C04E3 for ; Tue, 17 Sep 2024 14:35:03 +0000 (UTC) X-FDA: 82574477328.28.951416F Received: from mail-qv1-f52.google.com (mail-qv1-f52.google.com [209.85.219.52]) by imf06.hostedemail.com (Postfix) with ESMTP id C7FAE18000A for ; Tue, 17 Sep 2024 14:35:01 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Sny00JNC; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.219.52 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726583670; a=rsa-sha256; cv=none; b=zbQebcFvh3yGmBLaNYldenVEoIyfQeU7a6kHqOtQyW6NYXcepcXkXUJqEIg4bBEPQpCFFx XEBXfdn8aNLN0ltstOnzNooY59/6IdWq8powpMc4z0PNCG+zOBBTGNV2e0EDzw2Zzg4vn5 cJLDH8MaCj9OOYsAIZ/jTjwL9vRddRo= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Sny00JNC; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.219.52 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=1726583670; 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:in-reply-to:references:references:dkim-signature; bh=cLQI6kZ6TnjcLlPN0cihMK1F/E38o+9g1wKleRuuDyM=; b=5iWUO35aKlQ3DgDOkgZJj/rNV+aIFKau+BzacceShFIclIFGQv3PhfnoRpD0CSmRIjubah U9ZIARBfWlo1pv0/ZKl89zNE5SPU8hWERWSGV8kUXDMmWjCLQ/Clmt+YbFvHElha93p6np LPFh3FqNQgKlb86kKqrz2+fGMjdz6eI= Received: by mail-qv1-f52.google.com with SMTP id 6a1803df08f44-6c579748bf4so44300056d6.1 for ; Tue, 17 Sep 2024 07:35:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1726583701; x=1727188501; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:from:to:cc:subject :date:message-id:reply-to; bh=cLQI6kZ6TnjcLlPN0cihMK1F/E38o+9g1wKleRuuDyM=; b=Sny00JNCOETEzrwNHbbT4CwRom7E7chzTKEgUN0cSNIXs6xWtCj7uSvsJOKGHfrdcg ou7HhQPEvLvPs7d9EcAZ5zu0iRMCg3HcqxoI5GajbnYNoUeo4Wpdt4y3fYF2drgqVYY4 8i/DnMkm4VQWj+K7bVdzoIiGP7pr5SFxcNiDVlqRC78fGDZAr5rbkG337/xBIeEzl/1h g4OtItwPodrosDwCbASXiMHETj20kYMEukiVDiangyPPCyC4Q0Mo+bQPwUkpQtU4Ff/L vDKSi0TaEngE20nqgHxlEJjM5PVa+T59+kbUaGewjtl4ErE9WevjstLCV5hOqCqIxE5A RkZg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726583701; x=1727188501; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:feedback-id:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=cLQI6kZ6TnjcLlPN0cihMK1F/E38o+9g1wKleRuuDyM=; b=G2rc+tAieaSRnL/J90Zqau8R5DCleI0N8hJqfQj9L56loCWnpG9e6r2xkkGprVwc/h l/O4OzF+RvqtUKhkRcyH48ehZQ2o8Jtau+T8nnT/d7WIrF3fNLFVEacXHwpc1BhQ58q5 K/+01epvQJpIQ4msDoHrekAM5HEzoe/yxryVJVqpVk0WZUvztu5bDTDdMHTlBeDYJg8g MF4wSyYU04hnFLkqTSW6vzYCcK3vnQTcPVE9svlrFV6VEQp/Zy7QXa1sACotbX/At66s CRI9zESqOLpQjeiML0co/T2s5xIJrURv0Q+cORLdYq5+9wt96Pmh4UDXz2GECypM7Zsu dq+w== X-Forwarded-Encrypted: i=1; AJvYcCWXdRDGFBK2D/j/CVqtrzK+elWKF3RpTDAQ7i9NiQK+3yY1gbeUfvCXQ7og6iXJsNlsPm+fDfniWw==@kvack.org X-Gm-Message-State: AOJu0YwAB+JgHhEPbX8PSUfq8zsa3z3C0QNUE7hfkv+0JoljxAj1jTu+ GtYcw9NTFbZjyA9gbF+bjvbvClsxGjU3m2QhSLDMiYTguIAkrXhE X-Google-Smtp-Source: AGHT+IHxAlrf3264M1eG0sU+WYQOpz1SeCGp6P57WflWDJF78YqG3aNM3gQ3OugWPUyeVTVmITSVWQ== X-Received: by 2002:a05:6214:440b:b0:6c3:62bc:5de3 with SMTP id 6a1803df08f44-6c57e240938mr223177656d6.53.1726583700929; Tue, 17 Sep 2024 07:35:00 -0700 (PDT) Received: from fauth1-smtp.messagingengine.com (fauth1-smtp.messagingengine.com. [103.168.172.200]) by smtp.gmail.com with ESMTPSA id 6a1803df08f44-6c58c645d27sm35018466d6.73.2024.09.17.07.35.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Sep 2024 07:35:00 -0700 (PDT) Received: from phl-compute-03.internal (phl-compute-03.phl.internal [10.202.2.43]) by mailfauth.phl.internal (Postfix) with ESMTP id F227C1200070; Tue, 17 Sep 2024 10:34:59 -0400 (EDT) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-03.internal (MEProxy); Tue, 17 Sep 2024 10:34:59 -0400 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudekjedgjeelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhephffvvefufffkofgjfhgggfestdekredtredttden ucfhrhhomhepuehoqhhunhcuhfgvnhhguceosghoqhhunhdrfhgvnhhgsehgmhgrihhlrd gtohhmqeenucggtffrrghtthgvrhhnpeegleejiedthedvheeggfejveefjeejkefgveff ieeujefhueeigfegueehgeeggfenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpegsohhquhhnodhmvghsmhhtphgruhhthhhpvghrshhonhgrlhhi thihqdeiledvgeehtdeigedqudejjeekheehhedvqdgsohhquhhnrdhfvghngheppehgmh grihhlrdgtohhmsehfihigmhgvrdhnrghmvgdpnhgspghrtghpthhtohepvdehpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehlihhnuhigqdhkvghrnhgvlhesvhhgvghrrd hkvghrnhgvlhdrohhrghdprhgtphhtthhopehrtghusehvghgvrhdrkhgvrhhnvghlrdho rhhgpdhrtghpthhtoheplhhinhhugidqmhhmsehkvhgrtghkrdhorhhgpdhrtghpthhtoh eplhhkmhhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgruhhlmhgt kheskhgvrhhnvghlrdhorhhgpdhrtghpthhtohepfhhrvgguvghrihgtsehkvghrnhgvlh drohhrghdprhgtphhtthhopehnvggvrhgrjhdruhhprgguhhihrgihsehkvghrnhgvlhdr ohhrghdprhgtphhtthhopehjohgvlhesjhhovghlfhgvrhhnrghnuggvshdrohhrghdprh gtphhtthhopehjohhshhesjhhoshhhthhrihhplhgvthhtrdhorhhg X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Tue, 17 Sep 2024 10:34:59 -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 4/4] WIP: hazptr: Add hazptr test sample Date: Tue, 17 Sep 2024 07:34:02 -0700 Message-ID: <20240917143402.930114-5-boqun.feng@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: <20240917143402.930114-1-boqun.feng@gmail.com> References: <20240917143402.930114-1-boqun.feng@gmail.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Queue-Id: C7FAE18000A X-Rspamd-Server: rspam01 X-Stat-Signature: sots6c9w8inptiotby5k6b1wx8439owk X-HE-Tag: 1726583701-622734 X-HE-Meta: U2FsdGVkX190KJprybLLTGOpraV8y5n6/Ojh43IUgsPkUTLWQmjM0fYgzVS7YQyIbNkyFiRG/hBeFaCgO0Zopobv5qg1HxcDH7m+cyxupqgbzkCXe0Eax9e5spFk3Jl+hHRNxTuFGDBaWleD1T1/HrsCHu3KRXRsu9p1Uncr1n1TQvLEnZJUn+3pj2+HQNzfsqZYAQ8idTx96/ndI/OqlqYtHLqSlFQ3O6f07MYyaRXsVsKH9NolflBVqrT27yQA2tuTRymiZXgVWuYtv2Td2rD0BfZY6qpSJfBl7DaE16lk8KJFtN0NsnVuyzvqZNBvrrXRN4XtfmkKxGNjLQB5TgkBr4GlFgpUD9nsrGjiCg1fGjKd7PIcrS/2NbRyhWwQJjui8Onp5eF/WasezO8kcYMxuVjazGV3ixovEAUk7UaSfklWlUBXedJ3Ws/FhQcxhqqHU2EfC2FYCAafIlT1if6f9TzUFPr/ZnXPQanZdoQ+sWX5BmWoZyeEeKjpJAG6IwWs2jwt7eys0zM1wcAXCk1Zwh5Lp/VhEpT+fOOOjaw44tHgmczmx45D5cpfmSDZjaEdEBTXdyTFPnlXdWl/DdliTZAC162iAYcux1RILu0E/mj4XdwY2QPgFzn6299xx/Lw5WD54l1sEQd0ABiJf8yO3JVOEr8rHr0ozZ0rhBvUHVo9CTd/Y3K0t7TF6ueDMpKKD1WJrbITGtxMX9W1rztmKz3Ejm+ly61+uiZRiOfRd5oPACjLUTezwbhb84cy7Rfn2cg/+Ea3VPkc1w6WNjkpjAe+DzI8Oc56hiNzJ6925FY4QNwSCAo52UfIj6fw7V+QcORdxnBiiFOu4g9GbSaJQa6mwCn8XJHAXkOd7OasaWFsGeAIQr8CZX5f2s66Ki4sYMZBmZFW15Ahbih74uhLJTb1QNwBsR0e+jl0s3eZ6MhFRoEyfjbYAgNJw1j7AbSUvA/Xf8KnNEhsKPV nqVDJdgj zeJfONqb41H0PiwjB4w3IeEYHt2mk3vY4/n5KIMfyv91A7a6/pkK5sxZIRLRrWxQsuhMIRcMqrZ0WEPqUGpPsBp/3wnSmIhBcWKhqGMlZEFl394fZ+FwhmPlBGHfIUazN037/NYJz0uPiq6gelwyxAJMOOgV7JTfTWO7cAAmlL6rv1ePSgVonXaylyOHlnpouxWWDZQzgsGpMNM+KTmpFfyDTX6UlbW2KN2KvxAT5STon4pq6kiWUcW7+U+O0RoW+EcH0rHWVx54qYddPVr7gr7quXACoQbJnP50A+QMadc3MlXSU8l9yCcnVKdQx2HYQRN+2fTr3n7zVBEvEOOhBmwPQOvWRyKi1FX28bGY+GwfmcBg/RzabG/0j0/18mm5gXSpJeap0GL/k0feKj2H7klDLtfMbfj0CFJmto/dJ+Kx8zjI2IgXLdkufYKK9vIavj1Ar 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: Sample code for hazptr. This should go away or get more polished when hazptr support is added into rcutorture. Signed-off-by: Boqun Feng --- samples/Kconfig | 6 +++ samples/Makefile | 1 + samples/hazptr/hazptr_test.c | 87 ++++++++++++++++++++++++++++++++++++ 3 files changed, 94 insertions(+) create mode 100644 samples/hazptr/hazptr_test.c diff --git a/samples/Kconfig b/samples/Kconfig index b288d9991d27..9b42cde35dca 100644 --- a/samples/Kconfig +++ b/samples/Kconfig @@ -293,6 +293,12 @@ config SAMPLE_CGROUP source "samples/rust/Kconfig" +config SAMPLE_HAZPTR + bool "Build hazptr sample code" + help + Build samples that shows hazard pointer usage. Currently only + builtin usage is supported. + endif # SAMPLES config HAVE_SAMPLE_FTRACE_DIRECT diff --git a/samples/Makefile b/samples/Makefile index b85fa64390c5..0be21edc8a30 100644 --- a/samples/Makefile +++ b/samples/Makefile @@ -39,3 +39,4 @@ obj-$(CONFIG_SAMPLE_KMEMLEAK) += kmemleak/ obj-$(CONFIG_SAMPLE_CORESIGHT_SYSCFG) += coresight/ obj-$(CONFIG_SAMPLE_FPROBE) += fprobe/ obj-$(CONFIG_SAMPLES_RUST) += rust/ +obj-$(CONFIG_SAMPLE_HAZPTR) += hazptr/ diff --git a/samples/hazptr/hazptr_test.c b/samples/hazptr/hazptr_test.c new file mode 100644 index 000000000000..3cf0cdc8a83a --- /dev/null +++ b/samples/hazptr/hazptr_test.c @@ -0,0 +1,87 @@ +#include +#include +#include + +struct foo { + int i; + struct callback_head head; +}; + +static void simple_func(struct callback_head *head) +{ + struct foo *ptr = container_of(head, struct foo, head); + + printk("callback called %px, i is %d\n", ptr, ptr->i); + kfree(ptr); +} + +static void simple(void) +{ + struct hazptr_context ctx; + struct foo *dummy, *tmp, *other; + hazptr_t *hptr; + hazptr_t *hptr2; + + dummy = kzalloc(sizeof(*dummy), GFP_KERNEL); + dummy->i = 42; + + other = kzalloc(sizeof(*dummy), GFP_KERNEL); + other->i = 43; + + if (!dummy || !other) { + printk("allocation failed, skip test\n"); + return; + } + + init_hazptr_context(&ctx); + hptr = hazptr_alloc(&ctx); + BUG_ON(!hptr); + + // Get a second hptr. + hptr2 = hazptr_alloc(&ctx); + BUG_ON(!hptr2); + + // No one is modifying 'dummy', protection must succeed. + BUG_ON(!hazptr_tryprotect(hptr, dummy, head)); + + // Simulate changing a global pointer. + tmp = dummy; + WRITE_ONCE(dummy, other); + + // Callback will run after no active readers. + printk("callback added, %px\n", tmp); + + call_hazptr(&tmp->head, simple_func); + + // No one is modifying 'dummy', protection must succeed. + tmp = hazptr_protect(hptr2, dummy, head); + + printk("reader2 got %px, i is %d\n", tmp, tmp->i); + + // The above callback should run after this. + hazptr_clear(hptr); + printk("first reader is out\n"); + + for (int i = 0; i < 10; i++) + schedule(); // yield a few times. + + // Simulate freeing a global pointer. + tmp = dummy; + WRITE_ONCE(dummy, NULL); + printk("callback added, %px\n", tmp); + call_hazptr(&tmp->head, simple_func); + + cleanup_hazptr_context(&ctx); + printk("no reader here\n"); + + for (int i = 0; i < 10; i++) + schedule(); // yield a few times. +} + +static int hazptr_test(void) +{ + simple(); + printk("test ends\n"); + return 0; +} +module_init(hazptr_test);