From patchwork Sun Sep 22 10:20:02 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mathieu Desnoyers X-Patchwork-Id: 13809026 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 09755CF9C64 for ; Sun, 22 Sep 2024 10:21:14 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 70A556B007B; Sun, 22 Sep 2024 06:21:13 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6B96A6B0082; Sun, 22 Sep 2024 06:21:13 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 55A0B6B0085; Sun, 22 Sep 2024 06:21:13 -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 34A9B6B007B for ; Sun, 22 Sep 2024 06:21:13 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 8FE1A160CE5 for ; Sun, 22 Sep 2024 10:21:12 +0000 (UTC) X-FDA: 82591981584.07.7C5453D Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) by imf25.hostedemail.com (Postfix) with ESMTP id 070B4A000D for ; Sun, 22 Sep 2024 10:21:09 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=efficios.com header.s=smtpout1 header.b=w6B+oLdh; spf=pass (imf25.hostedemail.com: domain of mathieu.desnoyers@efficios.com designates 167.114.26.122 as permitted sender) smtp.mailfrom=mathieu.desnoyers@efficios.com; dmarc=pass (policy=none) header.from=efficios.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1727000436; 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=+ZXx72zeKlQdeasQu48dBoj5tr1YTC0ggEFqx7XfuMg=; b=YNagz2rPWVxzSFPR3lTuYVGf2wAAYJqh0o0TZHseP2ZtPQg2bNZ8EKQgvumwWz/Vp0R3zA wQFl/oODaMA6uWLe7jUgQsHHShBT/fAGUhbTBQy4GcNbNh2ihStbHqC6lTegtB/cbHojsW URXRjS73Nxk7/sUREKnANFWTwch6yBE= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=efficios.com header.s=smtpout1 header.b=w6B+oLdh; spf=pass (imf25.hostedemail.com: domain of mathieu.desnoyers@efficios.com designates 167.114.26.122 as permitted sender) smtp.mailfrom=mathieu.desnoyers@efficios.com; dmarc=pass (policy=none) header.from=efficios.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1727000436; a=rsa-sha256; cv=none; b=Llnlj8mTqaz/0VvmaWcez5Nb2Yc+06jhC/mU1vAtx/kNnkrLNOSuWAB6PpRw2D818sZx8m n6GXlH2U5fRCBtFUU28lKPdu2ngYMy6Lg2Bz/+aT1M5HYKnKGVldsAVlGR4wNsApkkIcMq +7AAOfGjZ/YD5arzEznuUzz7PNwGMwQ= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1727000468; bh=AqutN8Rp4xr64uA7iGd20GtzJ3zFhQeFxEf1rQBQiq0=; h=From:To:Cc:Subject:Date:From; b=w6B+oLdhJxQedXSkAVG8HuyPsrQqfuiZYnbPPj1bKrnXW8EPz7uipzzNnAFh997jw 6/MWJJ9tH9YIPcUAinYtJ4Xqs0ZWq2U/O9ErDWpDRiLv9qoEv33GyOZO8ROSELKc+G 4HOMqZpJrs48pPX6Zbv5AEZu6YSPVx8qvdDZ9x6KogDonC/QX5V8e4z6pKbB6AVAIU ZdVdmZwkkaISVMKrEyazff+Ny3LOvO4HuaQxdvxarAU9/Fxor8dKo1IWJo2UmPeDyJ bN4EDR56Sgrzq5dmHsIG/aVxNa9Y4N92FlW4tdUISdYz0Tb/8mFq/qabIJe3My2lwk nx/nf18WBmXtg== Received: from thinkos.internal.efficios.com (ip148.ip-54-37-222.eu [54.37.222.148]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4XBMbD2lXHz1LkR; Sun, 22 Sep 2024 06:20:56 -0400 (EDT) From: Mathieu Desnoyers To: Boqun Feng , "Paul E. McKenney" Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , Will Deacon , Peter Zijlstra , Alan Stern , John Stultz , Neeraj Upadhyay , Linus Torvalds , 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 , rcu@vger.kernel.org, linux-mm@kvack.org, lkmm@lists.linux.dev Subject: [RFC PATCH v1 1/1] hpref: Hazard Pointers with Reference Counter Date: Sun, 22 Sep 2024 12:20:02 +0200 Message-Id: <20240922102002.321008-1-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: 3ykihi8h7qe6jzib7rs9z4q6zwooaonp X-Rspamd-Queue-Id: 070B4A000D X-Rspamd-Server: rspam11 X-HE-Tag: 1727000469-982292 X-HE-Meta: U2FsdGVkX19ntuwmLtFVBZklbjJNTDlgp7Ff6OESreKdPPw38B1rWF5DJAkoWstWhXofWnHCzjMqZPKHCXyK2pM2BIRi0YcICOX9A1om0FvKelnjNO6hRYzLR5510f4e383H15JiPshW+bwCmbu779KjawdDG+u86FkUDfaKRcPSEXz6YrnGbnMHalj98q49juqIbxuLKdq/LHmUTZaBWn2/MW3sKReBY9B4hyJkCm5gNheqXesVXcWDwe54pJgHDUdJ5q+2DboEI/ygw9yqcj8EmPOjJN6k0Gz3CWNLpHgO7UCYCFmb1yNANOBR3Qv5kTd5EgaecTKdHMHNsRNI8VMJ2eOvElmx+3805Y3bC3feiAL6WY3FiYR2Jh4LQMaw087OhmGVlmBCPt9c6Yxlm/agp/1KI15LsGOj7Ls11YAkTd8Gq1JNx8sICblch8InxFb3kfF6AKjod7wwGjfUxqdnX0q455WR9DsQDt9wn4oeV60XPMQtT+4M/XQvnRpKlVCU2/ssmLLL030WRbhvY5e7PMTlELgavhm2W8U2LqDnZ+LcrKHKi7E3VlWCFdECCL+eLpHmRpE9MR4TncZ4IYoD/6xynxqSxEvFZDDR0pjwsjszKYUiTQFwF4TKKdRimR3XzIl5ILvWEPRBeYuMD5Ampl+/0Dbok5tAB/ewQtjOgp4MldsGac7I07XOOcjMoug+OMqgU1sMkAzvXUHjjpancYx4f5/A/jfmg9L6+PpUtJZuerQfC2YLcQlWyrZIsx9wGhLXuDrBVFvqj0QHYzxYPjhdPogpCrlLfVWzG4Mf+l0NOQkiTfTUYezqixb95b7fSlDYuj9pZN44UarGWIozsuYzbatqZ710FxH5mJmY0n9w1qFOHc3+5BW5Qb4PZmjX3GvhSakXS1Xfo2g8Zfyc6lzn3YdQ572yy2+XtfBjO/r49zfmKTmz12YVr6dwYbOCA10z+Mfzb9Vy+E1 yBoONztv vCNA7fDgutvImS0bZqKrQhdyVZKA1jT/+8QdPmb8pM53vnGwUL0YYsfccs/ehEzHbYbo8lutf+0AUMZYp/gomUXzxeF4jTrllvwX3lWT2Xqw3Q7rrcWPtDovYo20u9AqN8x/68fSIVPZA0BmedR+eZ1nJsdAbC3AVnVgiIEupb3MVNnfa89+ymvY1X7PwPfjQptHR/svRW6Yz3yYUU/XnWDBhE1Cd0YxQlmMcvs63qIqRx8pk/R9EJw8v9rck9+ktlkgEwVXjlwp8Ccj5sfuMROsBL1MSCvVTlBR4mEQuDvEYDX7RbKCTXF3WUlvuHCSP3VkVH15/X5Z+p+eBRruCvRmC2iwO5eYbm+sDLPFwwsqwAbpnlTfrSu5bJQt+OrLmSkWNkOHVBNfT9V/5Rd3Sv/kyJV5WWkNOg8pd9LhjpaTVGhUa+mTyjrFKZZ8OpKO3pUrgphR+N3vSWTUCgTsAHqz546J515nLOLpDQNz02orMx0/5EkJvAG37CDWtXSNHpto9iZNmLZoTSNahvdew7u5pVV7ue5y0sg4FoB6XG5i8pJMsHTZKWPYsdhcqqJNmDY4fs+0aPTQ5KXJLFjZrnMD613jQKO8Sd8XSrf/IWN5Rnc5DwGIr1xvkGPSIUfzekffE4ZyOq9tDLcBcW5NQpA3Kjjq32qaNQPtNVNIoiRoGjqF8+5ALwpKCgI1d1BYv8k4NyBH3Iz6Pzx+622HcaZrSEN9ZcXX4OckJVsqXPiBx4NuPn1Ff7IirVcopuwVWM6IFf7mTOsbxQQbpmzacYm6bW2w43c9RLhKKlI6Uyqkqz05Xiia6Oq4t4/A/0BBJQ/CsNOmh6IuZabDOEDS0zNgYmLbWqsVodJyQZudf1qe4zRh5Nu8acJUoLlCmp2+NoAgOcGRID/hs5yh3v0glItrbRy1rTY4DRxmlVTcx5X+SK6Qja6nbw4c4PSrH7jmSw5OpOlhVVIAkmXAiWoVsH4epu6Vs dc+Nc8rH F2IrAuqykYzk6bdfx/XiN/iX36FDkCcswmDE90y5jso= 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: Boqun Feng's patch series and LPC talk gave me a few ideas I wanted to try. I figured we could improve the concept of reference counters by adding a hazard-pointer protected fast-path to them. This API combines hazard pointers and reference counters. It uses hazard pointers as fast-paths, and falls back to reference counters either explicitly when the reader expects to hold the object for a long time, or when no hazard pointer slots are available. This prototype is implemented in userspace within the liburcu project, and depends on librseq for per-cpu data structure allocation, indexing, and updates. - The top of this liburcu feature branch can be found at: https://github.com/compudj/userspace-rcu-dev/tree/hpref (it's implemented within liburcu for convenience, but it does not actually use RCU). - librseq can be found at: https://git.kernel.org/pub/scm/libs/librseq/librseq.git/ This leverages the fact that both synchronization mechanisms aim to guarantee existence of objects, and those existence guarantees can be chained. Each mechanism achieves its purpose in a different way with different tradeoffs. The hazard pointers are faster to read and scale better than reference counters, but they consume more memory than a per-object reference counter. The fall-back to reference counter allows bounding the number of hazard pointer slots to a fixed size for the entire system: nr_cpus * N, where N=8 as it fills a single 64 bytes cache line on 64-bit architectures. Porting it to the Linux kernel should be straightforward. We might want to pick heavily contented reference counts such as the mm_struct mm_count field as a starting point to see if it provides significant performance gains. The hpref read-side performs well even compared to RCU in my benchmarks: Results: CPU(s): 16 On-line CPU(s) list: 0-15 Vendor ID: AuthenticAMD Model name: AMD Ryzen 7 PRO 6850U with Radeon Graphics 8 readers, 1 writer, 10s test_rwlock nr_reads 190461165 nr_writes 12 nr_ops 190461177 test_mutex nr_reads 248594205 nr_writes 26088306 nr_ops 274682511 test_urcu_mb (smp_mb) nr_reads 829829784 nr_writes 18057836 nr_ops 847887620 test_perthreadlock nr_reads 1623365032 nr_writes 1244814 nr_ops 1624609846 test_hpref_benchmark (smp_mb) nr_reads 1994298193 nr_writes 22293162 nr_ops 2016591355 test_hpref_benchmark (barrier/membarrier) nr_reads 15208690879 nr_writes 1893785 nr_ops 15210584664 test_urcu_bp (barrier/membarrier) nr_reads 20242102863 nr_writes 599484 nr_ops 20242702347 test_urcu (barrier/membarrier) nr_reads 20714490759 nr_writes 782045 nr_ops 20715272804 test_urcu_qsbr nr_reads 40774708959 nr_writes 3512904 nr_ops 40778221863 References: [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 Link: https://lore.kernel.org/lkml/j3scdl5iymjlxavomgc6u5ndg3svhab6ga23dr36o4f5mt333w@7xslvq6b6hmv/ Link: https://lpc.events/event/18/contributions/1731/ Signed-off-by: Mathieu Desnoyers Change-Id: I6369064a0e1a1f9632394df31ff41c76905d17e3 Cc: "Paul E. McKenney" Cc: Will Deacon Cc: Peter Zijlstra Cc: Boqun Feng Cc: Alan Stern Cc: John Stultz Cc: Neeraj Upadhyay Cc: Linus Torvalds Cc: Boqun Feng Cc: Frederic Weisbecker Cc: Joel Fernandes Cc: Josh Triplett Cc: Uladzislau Rezki Cc: Steven Rostedt Cc: Lai Jiangshan Cc: Zqiang Cc: Ingo Molnar Cc: Waiman Long Cc: Mark Rutland Cc: Thomas Gleixner Cc: Vlastimil Babka Cc: maged.michael@gmail.com Cc: Mateusz Guzik Cc: rcu@vger.kernel.org Cc: linux-mm@kvack.org Cc: lkmm@lists.linux.dev --- Changes since v0: - Re-load cpu and cpu_slots when rseq critical section aborts, - Remove the notion of "current_slot" hint from the hpref_hp_get fast-path. Just try all slots instead. Removing this counter management improves performance of the fast path by about 50%. --- include/urcu/hpref.h | 229 +++++++++++++++++++++++++++++++++++++++++++ src/Makefile.am | 6 +- src/hpref.c | 78 +++++++++++++++ 3 files changed, 312 insertions(+), 1 deletion(-) create mode 100644 include/urcu/hpref.h create mode 100644 src/hpref.c diff --git a/include/urcu/hpref.h b/include/urcu/hpref.h new file mode 100644 index 00000000..34f2bb9b --- /dev/null +++ b/include/urcu/hpref.h @@ -0,0 +1,229 @@ +// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers +// +// SPDX-License-Identifier: LGPL-2.1-or-later + +#ifndef _URCU_HPREF_H +#define _URCU_HPREF_H + +/* + * HPREF: Hazard pointers with reference counters + * + * This API combines hazard pointers and reference counters. + * It uses hazard pointers as fast-paths, and fall-back to reference + * counters either explicitly when the reader expects to hold the object + * for a long time, or when no hazard pointer slots are available. + * + * This leverages the fact that both synchronization mechanisms aim to + * guarantee existence of objects, and those existence guarantees can be + * chained. Each mechanism achieves its purpose in a different way with + * different tradeoffs. The hazard pointers are faster to read and scale + * better than reference counters, but they consume more memory than a + * per-object reference counter. + * + * The fall-back to reference counter allows bounding the number of + * hazard pointer slots to a fixed size for the entire system: + * nr_cpus * N, where N=8 as it fills a single 64 bytes cache line on + * 64-bit architectures. + * + * References: + * + * [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 + */ + +#include +#include +#include +#include +#include /* Per-CPU memory */ +#include + +#include +#include +#include + +struct hpref_node { + struct urcu_ref refcount; + void (*release)(struct hpref_node *node); +}; + +struct hpref_slot { + /* Use rseq to set from reader only if zero. */ + struct hpref_node *node; +}; + +#define NR_PERCPU_SLOTS_BITS 3 +#define HPREF_NR_PERCPU_SLOTS (1U << NR_PERCPU_SLOTS_BITS) +/* + * The emergency slot is only used for short critical sections + * (would be preempt off in when porting this code to the kernel): only + * to ensure we have a free slot for taking a reference count as + * fallback. + */ +#define HPREF_EMERGENCY_SLOT (HPREF_NR_PERCPU_SLOTS - 1) + +struct hpref_percpu_slots { + struct hpref_slot slots[HPREF_NR_PERCPU_SLOTS]; +}; + +enum hpref_type { + HPREF_TYPE_HP, + HPREF_TYPE_REF, +}; + +struct hpref_ctx { + struct hpref_slot *slot; + struct hpref_node *hp; + enum hpref_type type; +}; + +#ifdef __cplusplus +extern "C" { +#endif + +extern struct hpref_percpu_slots *hpref_percpu_slots; + +void hpref_release(struct urcu_ref *ref); + +/* + * hpref_synchronize: Wait for any reader possessing a hazard pointer to + * @node to clear its hazard pointer slot. + */ +void hpref_synchronize(struct hpref_node *node); + +/* + * hpref_synchronize_put: Wait for any reader possessing a hazard + * pointer to clear its slot and put reference + * count. + */ +void hpref_synchronize_put(struct hpref_node *node); + +static inline +void hpref_node_init(struct hpref_node *node, + void (*release)(struct hpref_node *node)) +{ + urcu_ref_init(&node->refcount); + node->release = release; +} + +/* + * hpref_promote_hp_to_ref: Promote hazard pointer to reference count. + */ +static inline +void hpref_promote_hp_to_ref(struct hpref_ctx *ctx) +{ + if (ctx->type == HPREF_TYPE_REF) + return; + urcu_ref_get(&ctx->hp->refcount); + uatomic_store(&ctx->slot->node, NULL, CMM_RELEASE); + ctx->slot = NULL; + ctx->type = HPREF_TYPE_REF; +} + +/* + * hpref_hp_get: Obtain a reference to a stable object, protected either + * by hazard pointer (fast-path) or using reference + * counter as fall-back. + */ +static inline +bool hpref_hp_get(struct hpref_node **node_p, struct hpref_ctx *ctx) +{ + int cpu = rseq_current_cpu_raw(), ret; + struct hpref_percpu_slots *cpu_slots = rseq_percpu_ptr(hpref_percpu_slots, cpu); + struct hpref_node *node, *node2; + struct hpref_slot *slot; + unsigned int slot_nr; + + node = uatomic_load(node_p, CMM_RELAXED); + if (!node) + return false; +retry: + for (slot_nr = 0; slot_nr < HPREF_NR_PERCPU_SLOTS; /* inc in loop. */) { + slot = &cpu_slots->slots[slot_nr]; + /* Use rseq to try setting slot hp. Store B. */ + ret = rseq_load_cbne_store__ptr(RSEQ_MO_RELAXED, RSEQ_PERCPU_CPU_ID, + (intptr_t *) &slot->node, (intptr_t) NULL, + (intptr_t) node, cpu); + if (!ret) + break; /* Success. */ + if (ret < 0) { + /* + * Abort due to preemption/migration/signal + * delivery or CPU number mismatch. + */ + cpu = rseq_current_cpu_raw(); + cpu_slots = rseq_percpu_ptr(hpref_percpu_slots, cpu); + } + if (slot_nr == HPREF_EMERGENCY_SLOT) { + /* + * This may busy-wait for another reader using the + * emergency slot to transition to refcount. + */ + caa_cpu_relax(); + } else { + slot_nr++; + } + goto retry; + } + /* Memory ordering: Store B before Load A. */ + cmm_smp_mb(); + node2 = uatomic_load(node_p, CMM_RELAXED); /* Load A */ + /* + * If @node_p content has changed since the first load, + * clear the hazard pointer and try again. + */ + if (node != node2) { + uatomic_store(&slot->node, NULL, CMM_RELAXED); + if (!node2) + return false; + node = node2; + goto retry; + } + ctx->type = HPREF_TYPE_HP; + ctx->hp = node; + ctx->slot = slot; + if (slot_nr == HPREF_EMERGENCY_SLOT) + hpref_promote_hp_to_ref(ctx); + return true; +} + +static inline +void hpref_put(struct hpref_ctx *ctx) +{ + if (ctx->type == HPREF_TYPE_REF) { + urcu_ref_put(&ctx->hp->refcount, hpref_release); + } else { + /* Release HP. */ + uatomic_store(&ctx->slot->node, NULL, CMM_RELEASE); + } + ctx->hp = NULL; +} + +/* + * hpref_set_pointer: Store pointer @node to @ptr, with RCU publication + * guarantees. + */ +static inline +void hpref_set_pointer(struct hpref_node **ptr, struct hpref_node *node) +{ + if (__builtin_constant_p(node) && node == NULL) + uatomic_store(ptr, NULL, CMM_RELAXED); + else + uatomic_store(ptr, node, CMM_RELEASE); +} + +/* + * Return the content of the hpref context hazard pointer field. + */ +static inline +struct hpref_node *hpref_ctx_pointer(struct hpref_ctx *ctx) +{ + return ctx->hp; +} + +#ifdef __cplusplus +} +#endif + +#endif /* _URCU_HPREF_H */ diff --git a/src/Makefile.am b/src/Makefile.am index b555c818..7312c9f7 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -19,7 +19,8 @@ RCULFHASH = rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c \ lib_LTLIBRARIES = liburcu-common.la \ liburcu.la liburcu-qsbr.la \ liburcu-mb.la liburcu-bp.la \ - liburcu-memb.la liburcu-cds.la + liburcu-memb.la liburcu-cds.la \ + liburcu-hpref.la # # liburcu-common contains wait-free queues (needed by call_rcu) as well @@ -50,6 +51,9 @@ liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c lfstack.c \ workqueue.c workqueue.h $(RCULFHASH) $(COMPAT) liburcu_cds_la_LIBADD = liburcu-common.la +liburcu_hpref_la_SOURCES = hpref.c +liburcu_hpref_la_LIBADD = -lrseq + pkgconfigdir = $(libdir)/pkgconfig pkgconfig_DATA = liburcu-cds.pc liburcu.pc liburcu-bp.pc liburcu-qsbr.pc \ liburcu-mb.pc liburcu-memb.pc diff --git a/src/hpref.c b/src/hpref.c new file mode 100644 index 00000000..f63530f5 --- /dev/null +++ b/src/hpref.c @@ -0,0 +1,78 @@ +// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers +// +// SPDX-License-Identifier: LGPL-2.1-or-later + +/* + * HPREF: Hazard pointers with reference counters + */ + +#define _LGPL_SOURCE +#include +#include /* Per-CPU memory */ + +static struct rseq_mempool *mempool; +struct hpref_percpu_slots *hpref_percpu_slots; + +void hpref_release(struct urcu_ref *ref) +{ + struct hpref_node *node = caa_container_of(ref, struct hpref_node, refcount); + + node->release(node); +} + +/* + * hpref_synchronize: Wait for any reader possessing a hazard pointer to + * @node to clear its hazard pointer slot. + */ +void hpref_synchronize(struct hpref_node *node) +{ + int nr_cpus = rseq_get_max_nr_cpus(), cpu; + + /* Memory ordering: Store A before Load B. */ + cmm_smp_mb(); + /* Scan all CPUs slots. */ + for (cpu = 0; cpu < nr_cpus; cpu++) { + struct hpref_percpu_slots *cpu_slots = rseq_percpu_ptr(hpref_percpu_slots, cpu); + struct hpref_slot *slot; + unsigned int i; + + for (i = 0; i < HPREF_NR_PERCPU_SLOTS; i++) { + slot = &cpu_slots->slots[i]; + /* Busy-wait if node is found. */ + while (uatomic_load(&slot->node, CMM_ACQUIRE) == node) /* Load B */ + caa_cpu_relax(); + } + } +} + +/* + * hpref_synchronize_put: Wait for any reader possessing a hazard + * pointer to clear its slot and put reference + * count. + */ +void hpref_synchronize_put(struct hpref_node *node) +{ + if (!node) + return; + hpref_synchronize(node); + urcu_ref_put(&node->refcount, hpref_release); +} + +static __attribute__((constructor)) +void hpref_init(void) +{ + mempool = rseq_mempool_create("hpref", sizeof(struct hpref_percpu_slots), NULL); + if (!mempool) + abort(); + hpref_percpu_slots = rseq_mempool_percpu_zmalloc(mempool); + if (!hpref_percpu_slots) + abort(); +} + +static __attribute__((destructor)) +void hpref_exit(void) +{ + rseq_mempool_percpu_free(hpref_percpu_slots); + if (rseq_mempool_destroy(mempool)) + abort(); +}