[PATCH v3 0/2] hwspinlock: convert to XArray and add summary in debugfs

[PATCH v3 0/2] hwspinlock: convert to XArray and add summary in debugfs

[Wolfram Sang]

TLDR: Changes since v2:

* don't hack radix-tree, convert to XArray instead

Renesas R-Car SoCs have their spinlocks inside a unit called MFIS. Up to
R-Car Gen4, there was only one MFIS unit on the SoC. Gen5, though, has
multiple instances and, thus, multiple spinlock providers. The spinlocks
are meant for specific cases (AP<->AP, AP<->RT, AP<->SCP...). For
development on these systems, it is helpful to have an overview of
registered spinlocks in debugfs. This series adds support for that. The
first patch converts the subsystem from the deprecated radix-tree to the
easier to handle XArray (Thank you again, Matthew!). The second patch
adds the summary in debugfs based on the new XArray implementation.

Patches are based on linux-next as of today plus the already applied
patch[1] "[PATCH] hwspinlock: propagate errno when registering single lock"

[1] https://lore.kernel.org/r/178370682988.2572738.9921265128936208294.b4-ty@kernel.org

A branch for testing is here:

git://git.kernel.org/pub/scm/linux/kernel/git/wsa/linux.git renesas/mfis/hwspinlock

It has been tested on a SparrowHawk board (R-Car V4H) with one MFIS
instance and an Ironhide board (R-Car X5H) with two MFIS instances.

Looking forward to comments.


Matthew Wilcox (Oracle) (1):
  hwspinlock: Convert to XArray

Wolfram Sang (1):
  hwspinlock: add list of mailboxes to debugfs

 drivers/hwspinlock/hwspinlock_core.c | 220 ++++++++++++++++-----------
 1 file changed, 127 insertions(+), 93 deletions(-)

-- 
2.47.3

[PATCH v3 1/2] hwspinlock: Convert to XArray

[Wolfram Sang]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

The radix tree is deprecated.  The XArray uses the same data structure
with a nicer interface.  The hwspinlock_tree_lock is not needed as the
spinlock built into the XArray is sufficient for all these cases after
we split a larger critical section in hwspin_lock_request_specific()
into two smaller ones.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
Co-developed-by: Wolfram Sang <wsa+renesas@sang-engineering.com>
Signed-off-by: Wolfram Sang <wsa+renesas@sang-engineering.com>
---

Changes since original implementation as a response to my v2:
* remove fix in hwspin_lock_register_single() which has been applied as
  a separate patch[1] meanwhile
* split the long critical section in hwspin_lock_request_specific() into
  two smaller ones suitable for a spinlock
* rename __hwspin_lock_request to hwspinlock_prepare and update docs
* handle return value of xas_get_mark() as bool not as int

[1] https://lore.kernel.org/r/178370682988.2572738.9921265128936208294.b4-ty@kernel.org

 drivers/hwspinlock/hwspinlock_core.c | 153 +++++++++++----------------
 1 file changed, 60 insertions(+), 93 deletions(-)

diff --git a/drivers/hwspinlock/hwspinlock_core.c b/drivers/hwspinlock/hwspinlock_core.c
index a509b73da190..55a5fa6aa200 100644
--- a/drivers/hwspinlock/hwspinlock_core.c
+++ b/drivers/hwspinlock/hwspinlock_core.c
@@ -16,7 +16,7 @@
 #include <linux/types.h>
 #include <linux/err.h>
 #include <linux/jiffies.h>
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
 #include <linux/hwspinlock.h>
 #include <linux/pm_runtime.h>
 #include <linux/mutex.h>
@@ -27,34 +27,21 @@
 /* retry delay used in atomic context */
 #define HWSPINLOCK_RETRY_DELAY_US	100
 
-/* radix tree tags */
-#define HWSPINLOCK_UNUSED	(0) /* tags an hwspinlock as unused */
+/* XArray search mark */
+#define HWSPINLOCK_UNUSED	XA_MARK_0 /* marks a hwspinlock as unused */
 
 /*
- * A radix tree is used to maintain the available hwspinlock instances.
+ * An XArray is used to maintain the available hwspinlock instances.
  * The tree associates hwspinlock pointers with their integer key id,
  * and provides easy-to-use API which makes the hwspinlock core code simple
  * and easy to read.
  *
- * Radix trees are quick on lookups, and reasonably efficient in terms of
+ * XArrays are quick on lookups, and reasonably efficient in terms of
  * storage, especially with high density usages such as this framework
  * requires (a continuous range of integer keys, beginning with zero, is
- * used as the ID's of the hwspinlock instances).
- *
- * The radix tree API supports tagging items in the tree, which this
- * framework uses to mark unused hwspinlock instances (see the
- * HWSPINLOCK_UNUSED tag above). As a result, the process of querying the
- * tree, looking for an unused hwspinlock instance, is now reduced to a
- * single radix tree API call.
- */
-static RADIX_TREE(hwspinlock_tree, GFP_KERNEL);
-
-/*
- * Synchronization of access to the tree is achieved using this mutex,
- * as the radix-tree API requires that users provide all synchronisation.
- * A mutex is needed because we're using non-atomic radix tree allocations.
+ * used as the ID of the hwspinlock instances).
  */
-static DEFINE_MUTEX(hwspinlock_tree_lock);
+static DEFINE_XARRAY(hwspinlocks);
 
 
 /**
@@ -369,10 +356,9 @@ of_hwspin_lock_simple_xlate(const struct of_phandle_args *hwlock_spec)
  */
 int of_hwspin_lock_get_id(struct device_node *np, int index)
 {
+	XA_STATE(xas, &hwspinlocks, 0);
 	struct of_phandle_args args;
 	struct hwspinlock *hwlock;
-	struct radix_tree_iter iter;
-	void **slot;
 	int id;
 	int ret;
 
@@ -389,15 +375,9 @@ int of_hwspin_lock_get_id(struct device_node *np, int index)
 	/* Find the hwspinlock device: we need its base_id */
 	ret = -EPROBE_DEFER;
 	rcu_read_lock();
-	radix_tree_for_each_slot(slot, &hwspinlock_tree, &iter, 0) {
-		hwlock = radix_tree_deref_slot(slot);
-		if (unlikely(!hwlock))
+	xas_for_each(&xas, hwlock, ULONG_MAX) {
+		if (xas_retry(&xas, hwlock))
 			continue;
-		if (radix_tree_deref_retry(hwlock)) {
-			slot = radix_tree_iter_retry(&iter);
-			continue;
-		}
-
 		if (device_match_of_node(hwlock->bank->dev, args.np)) {
 			ret = 0;
 			break;
@@ -452,51 +432,47 @@ EXPORT_SYMBOL_GPL(of_hwspin_lock_get_id_byname);
 
 static int hwspin_lock_register_single(struct hwspinlock *hwlock, int id)
 {
-	struct hwspinlock *tmp;
+	XA_STATE(xas, &hwspinlocks, id);
+	struct hwspinlock *existing;
 	int ret;
 
-	mutex_lock(&hwspinlock_tree_lock);
-
-	ret = radix_tree_insert(&hwspinlock_tree, id, hwlock);
-	if (ret) {
-		if (ret == -EEXIST)
-			pr_err("hwspinlock id %d already exists!\n", id);
-		goto out;
+	xas_lock(&xas);
+	existing = xas_load(&xas);
+	if (existing) {
+		pr_err("hwspinlock id %d already exists!\n", id);
+		xas_set_err(&xas, -EBUSY);
 	}
+	xas_store(&xas, hwlock);
 
 	/* mark this hwspinlock as available */
-	tmp = radix_tree_tag_set(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
+	xas_set_mark(&xas, HWSPINLOCK_UNUSED);
+	ret = xas_error(&xas);
+	xas_unlock(&xas);
 
-	/* self-sanity check which should never fail */
-	WARN_ON(tmp != hwlock);
-
-out:
-	mutex_unlock(&hwspinlock_tree_lock);
 	return ret;
 }
 
 static struct hwspinlock *hwspin_lock_unregister_single(unsigned int id)
 {
+	XA_STATE(xas, &hwspinlocks, id);
 	struct hwspinlock *hwlock = NULL;
-	int ret;
+	bool unused;
 
-	mutex_lock(&hwspinlock_tree_lock);
+	xas_lock(&xas);
 
-	/* make sure the hwspinlock is not in use (tag is set) */
-	ret = radix_tree_tag_get(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
-	if (ret == 0) {
+	/* make sure the hwspinlock is not in use (mark is set) */
+	unused = xas_get_mark(&xas, HWSPINLOCK_UNUSED);
+	if (!unused) {
 		pr_err("hwspinlock %d still in use (or not present)\n", id);
 		goto out;
 	}
 
-	hwlock = radix_tree_delete(&hwspinlock_tree, id);
-	if (!hwlock) {
-		pr_err("failed to delete hwspinlock %d\n", id);
-		goto out;
-	}
+	hwlock = xas_store(&xas, NULL);
+	if (!hwlock)
+		pr_err("hwspinlock %d already deleted\n", id);
 
 out:
-	mutex_unlock(&hwspinlock_tree_lock);
+	xas_unlock(&xas);
 	return hwlock;
 }
 
@@ -666,20 +642,18 @@ int devm_hwspin_lock_register(struct device *dev,
 EXPORT_SYMBOL_GPL(devm_hwspin_lock_register);
 
 /**
- * __hwspin_lock_request() - tag an hwspinlock as used and power it up
+ * hwspinlock_prepare() - prepare a hwspinlock
  * @hwlock: the target hwspinlock
  *
  * This is an internal function that prepares an hwspinlock instance
- * before it is given to the user. The function assumes that
- * hwspinlock_tree_lock is taken.
+ * before it is given to the user.
  *
  * Returns: %0 or positive to indicate success, and a negative value to
  * indicate an error (with the appropriate error code)
  */
-static int __hwspin_lock_request(struct hwspinlock *hwlock)
+static int hwspinlock_prepare(struct hwspinlock *hwlock)
 {
 	struct device *dev = hwlock->bank->dev;
-	struct hwspinlock *tmp;
 	int ret;
 
 	/* prevent underlying implementation from being removed */
@@ -697,16 +671,7 @@ static int __hwspin_lock_request(struct hwspinlock *hwlock)
 		return ret;
 	}
 
-	ret = 0;
-
-	/* mark hwspinlock as used, should not fail */
-	tmp = radix_tree_tag_clear(&hwspinlock_tree, hwlock_to_id(hwlock),
-							HWSPINLOCK_UNUSED);
-
-	/* self-sanity check that should never fail */
-	WARN_ON(tmp != hwlock);
-
-	return ret;
+	return 0;
 }
 
 /**
@@ -724,13 +689,14 @@ static int __hwspin_lock_request(struct hwspinlock *hwlock)
  */
 struct hwspinlock *hwspin_lock_request_specific(unsigned int id)
 {
+	XA_STATE(xas, &hwspinlocks, id);
 	struct hwspinlock *hwlock;
+	bool unused;
 	int ret;
 
-	mutex_lock(&hwspinlock_tree_lock);
+	xas_lock(&xas);
 
-	/* make sure this hwspinlock exists */
-	hwlock = radix_tree_lookup(&hwspinlock_tree, id);
+	hwlock = xas_load(&xas);
 	if (!hwlock) {
 		pr_warn("hwspinlock %u does not exist\n", id);
 		goto out;
@@ -739,21 +705,25 @@ struct hwspinlock *hwspin_lock_request_specific(unsigned int id)
 	/* sanity check (this shouldn't happen) */
 	WARN_ON(hwlock_to_id(hwlock) != id);
 
-	/* make sure this hwspinlock is unused */
-	ret = radix_tree_tag_get(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
-	if (ret == 0) {
+	unused = xas_get_mark(&xas, HWSPINLOCK_UNUSED);
+	if (!unused) {
 		pr_warn("hwspinlock %u is already in use\n", id);
 		hwlock = NULL;
 		goto out;
 	}
 
-	/* mark as used and power up */
-	ret = __hwspin_lock_request(hwlock);
-	if (ret < 0)
-		hwlock = NULL;
+	xas_clear_mark(&xas, HWSPINLOCK_UNUSED);
+	xas_unlock(&xas);
+
+	ret = hwspinlock_prepare(hwlock);
 
+	xas_lock(&xas);
+	if (ret < 0) {
+		hwlock = NULL;
+		xas_set_mark(&xas, HWSPINLOCK_UNUSED);
+	}
 out:
-	mutex_unlock(&hwspinlock_tree_lock);
+	xas_unlock(&xas);
 	return hwlock;
 }
 EXPORT_SYMBOL_GPL(hwspin_lock_request_specific);
@@ -772,9 +742,10 @@ EXPORT_SYMBOL_GPL(hwspin_lock_request_specific);
  */
 int hwspin_lock_free(struct hwspinlock *hwlock)
 {
+	XA_STATE(xas, &hwspinlocks, 0);
 	struct device *dev;
-	struct hwspinlock *tmp;
-	int ret;
+	bool unused;
+	int ret = 0;
 
 	if (!hwlock) {
 		pr_err("invalid hwlock\n");
@@ -782,12 +753,12 @@ int hwspin_lock_free(struct hwspinlock *hwlock)
 	}
 
 	dev = hwlock->bank->dev;
-	mutex_lock(&hwspinlock_tree_lock);
+	xas_lock(&xas);
+	xas_set(&xas, hwlock_to_id(hwlock));
 
 	/* make sure the hwspinlock is used */
-	ret = radix_tree_tag_get(&hwspinlock_tree, hwlock_to_id(hwlock),
-							HWSPINLOCK_UNUSED);
-	if (ret == 1) {
+	unused = xas_get_mark(&xas, HWSPINLOCK_UNUSED);
+	if (unused) {
 		dev_err(dev, "%s: hwlock is already free\n", __func__);
 		dump_stack();
 		ret = -EINVAL;
@@ -798,16 +769,12 @@ int hwspin_lock_free(struct hwspinlock *hwlock)
 	pm_runtime_put(dev);
 
 	/* mark this hwspinlock as available */
-	tmp = radix_tree_tag_set(&hwspinlock_tree, hwlock_to_id(hwlock),
-							HWSPINLOCK_UNUSED);
-
-	/* sanity check (this shouldn't happen) */
-	WARN_ON(tmp != hwlock);
+	xas_set_mark(&xas, HWSPINLOCK_UNUSED);
 
 	module_put(dev->driver->owner);
 
 out:
-	mutex_unlock(&hwspinlock_tree_lock);
+	xas_unlock(&xas);
 	return ret;
 }
 EXPORT_SYMBOL_GPL(hwspin_lock_free);
-- 
2.47.3

3 XArray questions (was: Re: [PATCH v3 1/2] hwspinlock: Convert to XArray)

[Wolfram Sang]

Hi Matthew,

Sashiko found issues with the XArray conversion[1]. I tried to educate
myself enough to evaluate its findings. Yet, I'd be happy if you could
double-check my reasoning. Note: I left all issues with use-after-free
aside. Reason is that the hwspinlock subsystem has so many problems with
removing locks that I proposed to remove the removal[2].

[1] https://sashiko.dev/#/patchset/20260713124622.63181-1-wsa%2Brenesas%40sang-engineering.com
[2] https://lkml.iu.edu/2605.1/07475.html

Now for the issues:

> > +	xas_lock(&xas);
> > +	existing = xas_load(&xas);
> > +	if (existing) {
> > +		pr_err("hwspinlock id %d already exists!\n", id);
> > +		xas_set_err(&xas, -EBUSY);
> >  	}
> > +	xas_store(&xas, hwlock);
> 
> [Severity: High]
> Could xas_store() fail with -ENOMEM under mild memory fragmentation?
> 
> Because xas_lock() acquires a spinlock, XArray's internal node allocations
> are restricted to GFP_NOWAIT. XArray typically requires callers modifying the
> array under a lock to wrap the operation in a xas_nomem() retry loop,
> similar to:
> 
>     do {
>         xas_lock(&xas);
>         ...
>         xas_store(&xas, hwlock);
>         ...
>         xas_unlock(&xas);
>     } while (xas_nomem(&xas, GFP_KERNEL));
> 
> Without this loop, the GFP_NOWAIT allocation failure would be fatal. Could
> this cause hardware spinlock registration to fail spuriously?

Reading the documentation of xas_nomem(), I think Sashiko is right and
such a loop is needed, or?

> >  	/* mark this hwspinlock as available */
> > -	tmp = radix_tree_tag_set(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
> > +	xas_set_mark(&xas, HWSPINLOCK_UNUSED);
> > +	ret = xas_error(&xas);
> > +	xas_unlock(&xas);
> >  
> > -	/* self-sanity check which should never fail */
> > -	WARN_ON(tmp != hwlock);
> > -
> > -out:
> > -	mutex_lock(&hwspinlock_tree_lock);
> >  	return ret;
> >  }
> >  
> >  static struct hwspinlock *hwspin_lock_unregister_single(unsigned int id)
> >  {
> > +	XA_STATE(xas, &hwspinlocks, id);
> >  	struct hwspinlock *hwlock = NULL;
> > -	int ret;
> > +	bool unused;
> >  
> > -	mutex_lock(&hwspinlock_tree_lock);
> > +	xas_lock(&xas);
> >  
> > -	/* make sure the hwspinlock is not in use (tag is set) */
> > -	ret = radix_tree_tag_get(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
> > -	if (ret == 0) {
> > +	/* make sure the hwspinlock is not in use (mark is set) */
> > +	unused = xas_get_mark(&xas, HWSPINLOCK_UNUSED);
> 
> [Severity: High]
> Does xas_get_mark() return the correct value here?
> 
> Since the XA_STATE is freshly initialized and xas_load() hasn't been called
> to walk the tree, xas->xa_node is NULL. In this state, xas_get_mark() queries
> the global root mark of the XArray.
> 
> If any lock in the XArray is unused, won't this return true, potentially
> allowing active locks to be erroneously deleted?

Despite I intend to remove this function in the future anyhow, the fix
for this issue is a simple 'xas_load(&xas);' right before
'xas_get_mark()'?

> > @@ -782,12 +753,12 @@ int hwspin_lock_free(struct hwspinlock *hwlock)
> >  	}
> >  
> >  	dev = hwlock->bank->dev;
> > -	mutex_lock(&hwspinlock_tree_lock);
> > +	xas_lock(&xas);
> > +	xas_set(&xas, hwlock_to_id(hwlock));
> >  
> >  	/* make sure the hwspinlock is used */
> > -	ret = radix_tree_tag_get(&hwspinlock_tree, hwlock_to_id(hwlock),
> > -							HWSPINLOCK_UNUSED);
> > -	if (ret == 1) {
> > +	unused = xas_get_mark(&xas, HWSPINLOCK_UNUSED);
> 
> [Severity: High]
> Will xas_get_mark() silently abort here?
> 
> Calling xas_set() initializes the state to XAS_RESTART, which makes
> xas_invalid() evaluate to true. Because of this, both xas_get_mark() and the
> subsequent xas_set_mark() further down will silently return or abort without
> performing their intended operations.
> 
> Could this prevent the lock from being marked as available again, effectively
> leaking it permanently?

Not sure if I parse this correctly, but I think xas_load() is also
needed after xas_set() and before xas_get_mark()?

Thanks and happy hacking,

   Wolfram

[PATCH v3 2/2] hwspinlock: add list of mailboxes to debugfs

[Wolfram Sang]

To help debugging, offer a list of registered hwspinlocks in debugfs. It
will also print the responsible hwspinlock_device and if the spinlock is
currently used. It does not show if the lock is taken because of
side-effects. Often, reading a lock means actually taking it.

Signed-off-by: Wolfram Sang <wsa+renesas@sang-engineering.com>
---

Changes since v2:
* totally rewritten because it traverses an XArray now instead of a
  radix tree

 drivers/hwspinlock/hwspinlock_core.c | 67 ++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)

diff --git a/drivers/hwspinlock/hwspinlock_core.c b/drivers/hwspinlock/hwspinlock_core.c
index 55a5fa6aa200..d5c6807631d3 100644
--- a/drivers/hwspinlock/hwspinlock_core.c
+++ b/drivers/hwspinlock/hwspinlock_core.c
@@ -9,6 +9,7 @@
 
 #define pr_fmt(fmt)    "%s: " fmt, __func__
 
+#include <linux/debugfs.h>
 #include <linux/delay.h>
 #include <linux/kernel.h>
 #include <linux/module.h>
@@ -21,6 +22,7 @@
 #include <linux/pm_runtime.h>
 #include <linux/mutex.h>
 #include <linux/of.h>
+#include <linux/seq_file.h>
 
 #include "hwspinlock_internal.h"
 
@@ -855,5 +857,70 @@ struct hwspinlock *devm_hwspin_lock_request_specific(struct device *dev,
 }
 EXPORT_SYMBOL_GPL(devm_hwspin_lock_request_specific);
 
+#ifdef CONFIG_DEBUG_FS
+static void *hwspinlock_seq_start(struct seq_file *s, loff_t *ppos)
+{
+	unsigned long index = *ppos;
+	struct hwspinlock *hwlock;
+
+	rcu_read_lock();
+	hwlock = xa_find(&hwspinlocks, &index, ULONG_MAX, XA_PRESENT);
+	*ppos = index;
+
+	return hwlock;
+}
+
+static void *hwspinlock_seq_next(struct seq_file *s, void *v, loff_t *ppos)
+{
+	/* Increase ppos here to avoid endless loops. Don't use xa_find_after() */
+	unsigned long index = *ppos + 1;
+	struct hwspinlock *hwlock;
+
+	hwlock = xa_find(&hwspinlocks, &index, ULONG_MAX, XA_PRESENT);
+	*ppos = index;
+
+	return hwlock;
+}
+
+static void hwspinlock_seq_stop(struct seq_file *s, void *v)
+{
+	rcu_read_unlock();
+}
+
+static int hwspinlock_seq_show(struct seq_file *s, void *v)
+{
+	struct hwspinlock *hwlock = v;
+	bool unused = xa_get_mark(&hwspinlocks, s->index, HWSPINLOCK_UNUSED);
+
+	seq_printf(s, "%4llu:\t%s\t%s\n", s->index, unused ? "free" : "in use",
+		   dev_name(hwlock->bank->dev));
+	return 0;
+}
+
+static const struct seq_operations hwspinlock_sops = {
+	.start = hwspinlock_seq_start,
+	.next = hwspinlock_seq_next,
+	.stop = hwspinlock_seq_stop,
+	.show = hwspinlock_seq_show,
+};
+DEFINE_SEQ_ATTRIBUTE(hwspinlock);
+
+/*
+ * subsys_initcall() is used here but controllers may already have been
+ * registered earlier or will be later. The rationale is that debugfs is
+ * accessed only late, i.e. from userspace. So, files created here must make no
+ * assumptions about initcall ordering.
+ */
+static int __init hwspinlock_init(void)
+{
+	struct dentry *hwspinlock_debugfs = debugfs_create_dir("hwspinlock", NULL);
+
+	debugfs_create_file("hwspinlock_summary", 0444, hwspinlock_debugfs,
+			    NULL, &hwspinlock_fops);
+	return 0;
+}
+subsys_initcall(hwspinlock_init);
+#endif	/* DEBUG_FS */
+
 MODULE_DESCRIPTION("Hardware spinlock interface");
 MODULE_AUTHOR("Ohad Ben-Cohen <ohad@wizery.com>");
-- 
2.47.3