@@ -23,43 +23,32 @@
#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>
#include <linux/of.h>
#include "hwspinlock_internal.h"
-/* radix tree tags */
-#define HWSPINLOCK_UNUSED (0) /* tags an hwspinlock as unused */
+#define HWSPINLOCK_UNUSED XA_TAG_0
/*
- * A radix tree is used to maintain the available hwspinlock instances.
- * The tree associates hwspinlock pointers with their integer key id,
+ * An xarray is used to maintain the available hwspinlock instances.
+ * The array 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
+ * The XArray is 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.
+ * The xarray API supports tagging items, which this framework uses to mark
+ * unused hwspinlock instances (see the HWSPINLOCK_UNUSED tag above). As a
+ * result, the process of querying the array, looking for an unused
+ * hwspinlock instance, is reduced to a single 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.
- */
-static DEFINE_MUTEX(hwspinlock_tree_lock);
-
+static DEFINE_XARRAY(hwspinlock_xa);
/**
* __hwspin_trylock() - attempt to lock a specific hwspinlock
@@ -294,10 +283,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, &hwspinlock_xa, 0);
struct of_phandle_args args;
struct hwspinlock *hwlock;
- struct radix_tree_iter iter;
- void **slot;
int id;
int ret;
@@ -309,22 +297,15 @@ 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))
- continue;
- if (radix_tree_deref_retry(hwlock)) {
- slot = radix_tree_iter_retry(&iter);
+ xas_for_each(&xas, hwlock, ULONG_MAX) {
+ if (xas_retry(&xas, hwlock))
continue;
- }
- if (hwlock->bank->dev->of_node == args.np) {
- ret = 0;
+ if (hwlock->bank->dev->of_node == args.np)
break;
- }
}
rcu_read_unlock();
- if (ret < 0)
+ if (!hwlock)
goto out;
id = of_hwspin_lock_simple_xlate(&args);
@@ -332,6 +313,7 @@ int of_hwspin_lock_get_id(struct device_node *np, int index)
ret = -EINVAL;
goto out;
}
+ ret = 0;
id += hwlock->bank->base_id;
out:
@@ -342,26 +324,19 @@ EXPORT_SYMBOL_GPL(of_hwspin_lock_get_id);
static int hwspin_lock_register_single(struct hwspinlock *hwlock, int id)
{
- struct hwspinlock *tmp;
- int ret;
+ void *curr;
- mutex_lock(&hwspinlock_tree_lock);
-
- ret = radix_tree_insert(&hwspinlock_tree, id, hwlock);
- if (ret) {
- if (ret == -EEXIST)
+ curr = xa_cmpxchg(&hwspinlock_xa, id, NULL, hwlock, GFP_KERNEL);
+ if (curr) {
+ if (!xa_is_err(curr))
pr_err("hwspinlock id %d already exists!\n", id);
goto out;
}
/* mark this hwspinlock as available */
- tmp = radix_tree_tag_set(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
-
- /* self-sanity check which should never fail */
- WARN_ON(tmp != hwlock);
+ xa_set_tag(&hwspinlock_xa, id, HWSPINLOCK_UNUSED);
out:
- mutex_unlock(&hwspinlock_tree_lock);
return 0;
}
@@ -370,23 +345,16 @@ static struct hwspinlock *hwspin_lock_unregister_single(unsigned int id)
struct hwspinlock *hwlock = NULL;
int ret;
- mutex_lock(&hwspinlock_tree_lock);
-
/* make sure the hwspinlock is not in use (tag is set) */
- ret = radix_tree_tag_get(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
+ ret = xa_get_tag(&hwspinlock_xa, id, HWSPINLOCK_UNUSED);
if (ret == 0) {
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 = xa_erase(&hwspinlock_xa, id);
out:
- mutex_unlock(&hwspinlock_tree_lock);
return hwlock;
}
@@ -477,8 +445,7 @@ EXPORT_SYMBOL_GPL(hwspin_lock_unregister);
* __hwspin_lock_request() - tag an hwspinlock as used and power it up
*
* 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)
@@ -486,7 +453,6 @@ EXPORT_SYMBOL_GPL(hwspin_lock_unregister);
static int __hwspin_lock_request(struct hwspinlock *hwlock)
{
struct device *dev = hwlock->bank->dev;
- struct hwspinlock *tmp;
int ret;
/* prevent underlying implementation from being removed */
@@ -501,16 +467,7 @@ static int __hwspin_lock_request(struct hwspinlock *hwlock)
dev_err(dev, "%s: can't power on device\n", __func__);
pm_runtime_put_noidle(dev);
module_put(dev->driver->owner);
- return ret;
}
-
- /* 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;
}
@@ -548,29 +505,28 @@ struct hwspinlock *hwspin_lock_request(void)
{
struct hwspinlock *hwlock;
int ret;
+ unsigned long index = 0;
- mutex_lock(&hwspinlock_tree_lock);
+ xa_lock(&hwspinlock_xa);
/* look for an unused lock */
- ret = radix_tree_gang_lookup_tag(&hwspinlock_tree, (void **)&hwlock,
- 0, 1, HWSPINLOCK_UNUSED);
- if (ret == 0) {
+ hwlock = xa_find(&hwspinlock_xa, &index, ULONG_MAX, HWSPINLOCK_UNUSED);
+ if (!hwlock) {
pr_warn("a free hwspinlock is not available\n");
- hwlock = NULL;
- goto out;
+ xa_unlock(&hwspinlock_xa);
+ return NULL;
}
- /* sanity check that should never fail */
- WARN_ON(ret > 1);
-
/* mark as used and power up */
+ __xa_clear_tag(&hwspinlock_xa, index, HWSPINLOCK_UNUSED);
+ xa_unlock(&hwspinlock_xa);
+
ret = __hwspin_lock_request(hwlock);
- if (ret < 0)
- hwlock = NULL;
+ if (ret == 0)
+ return hwlock;
-out:
- mutex_unlock(&hwspinlock_tree_lock);
- return hwlock;
+ xa_set_tag(&hwspinlock_xa, index, HWSPINLOCK_UNUSED);
+ return NULL;
}
EXPORT_SYMBOL_GPL(hwspin_lock_request);
@@ -592,10 +548,10 @@ struct hwspinlock *hwspin_lock_request_specific(unsigned int id)
struct hwspinlock *hwlock;
int ret;
- mutex_lock(&hwspinlock_tree_lock);
+ xa_lock(&hwspinlock_xa);
/* make sure this hwspinlock exists */
- hwlock = radix_tree_lookup(&hwspinlock_tree, id);
+ hwlock = xa_load(&hwspinlock_xa, id);
if (!hwlock) {
pr_warn("hwspinlock %u does not exist\n", id);
goto out;
@@ -605,21 +561,25 @@ struct hwspinlock *hwspin_lock_request_specific(unsigned int id)
WARN_ON(hwlock_to_id(hwlock) != id);
/* make sure this hwspinlock is unused */
- ret = radix_tree_tag_get(&hwspinlock_tree, id, HWSPINLOCK_UNUSED);
+ ret = xa_get_tag(&hwspinlock_xa, id, HWSPINLOCK_UNUSED);
if (ret == 0) {
pr_warn("hwspinlock %u is already in use\n", id);
- hwlock = NULL;
goto out;
}
/* mark as used and power up */
+ __xa_clear_tag(&hwspinlock_xa, id, HWSPINLOCK_UNUSED);
+ xa_unlock(&hwspinlock_xa);
+
ret = __hwspin_lock_request(hwlock);
- if (ret < 0)
- hwlock = NULL;
+ if (ret == 0)
+ return hwlock;
+ xa_set_tag(&hwspinlock_xa, id, HWSPINLOCK_UNUSED);
+ return NULL;
out:
- mutex_unlock(&hwspinlock_tree_lock);
- return hwlock;
+ xa_unlock(&hwspinlock_xa);
+ return NULL;
}
EXPORT_SYMBOL_GPL(hwspin_lock_request_specific);
@@ -638,7 +598,6 @@ EXPORT_SYMBOL_GPL(hwspin_lock_request_specific);
int hwspin_lock_free(struct hwspinlock *hwlock)
{
struct device *dev;
- struct hwspinlock *tmp;
int ret;
if (!hwlock) {
@@ -647,12 +606,11 @@ int hwspin_lock_free(struct hwspinlock *hwlock)
}
dev = hwlock->bank->dev;
- mutex_lock(&hwspinlock_tree_lock);
/* make sure the hwspinlock is used */
- ret = radix_tree_tag_get(&hwspinlock_tree, hwlock_to_id(hwlock),
+ ret = xa_get_tag(&hwspinlock_xa, hwlock_to_id(hwlock),
HWSPINLOCK_UNUSED);
- if (ret == 1) {
+ if (ret) {
dev_err(dev, "%s: hwlock is already free\n", __func__);
dump_stack();
ret = -EINVAL;
@@ -665,16 +623,11 @@ int hwspin_lock_free(struct hwspinlock *hwlock)
goto out;
/* 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);
+ xa_set_tag(&hwspinlock_xa, hwlock_to_id(hwlock), HWSPINLOCK_UNUSED);
module_put(dev->driver->owner);
out:
- mutex_unlock(&hwspinlock_tree_lock);
return ret;
}
EXPORT_SYMBOL_GPL(hwspin_lock_free);