[PATCH 0/2] regmap: Add basic maple tree register cache

[PATCH 0/2] regmap: Add basic maple tree register cache

[Mark Brown]

The current state of the art for sparse register maps is the rbtree cache.
This works well for most applications but isn't always ideal for sparser
register maps since the rbtree can get deep, requiring a lot of walking.
Fortunately the kernel has a data structure intended to address this very
problem, the maple tree. Provide an initial implementation of a register
cache based on the maple tree to start taking advantage of it.

This initial implementation is very simplistic and doesn't take full
advantage of the capabilities of the maple tree, we simply store each
register as a single value within the tree. Since maple tree values are
pointers and iteration doesn't naturally give us the key we allocate a
small structure for each register, effectively adding another layer to the
tree.

We also store data in host native format rather than device native format
as we do for rbtree, this will be a benefit for devices where we don't
marshal data within regmap and until we are able to store more than one
register in a node there's no reason to have preformatted data even where
we do marshal.

This works well enough to get started and should already work well for some
devices but there is a great deal of room for improvement, as well as
storing blocks rather than just individual registers we don't need the
locking that the maple tree does and are likely to benefit from caching the
last accessed entry. Very small register maps may continue to to better
with rbtree longer term.

This series depends on a number of patches sent previously and separately, 
including KUnit support and some core fixes and features.

Signed-off-by: Mark Brown <broonie@kernel.org>
---
Mark Brown (2):
      regmap: Factor out single value register syncing
      regmap: Add maple tree based register cache

 drivers/base/regmap/Makefile         |   2 +-
 drivers/base/regmap/internal.h       |   2 +
 drivers/base/regmap/regcache-maple.c | 154 +++++++++++++++++++++++++++++++++++
 drivers/base/regmap/regcache.c       |  41 ++++++----
 drivers/base/regmap/regmap-kunit.c   |   3 +
 include/linux/regmap.h               |   1 +
 6 files changed, 188 insertions(+), 15 deletions(-)
---
base-commit: c20bc1c03695287bd19922a32052f2bc7d4a462d
change-id: 20230325-regcache-maple-364e7581cf0c

Best regards,
-- 
Mark Brown <broonie@kernel.org>

[PATCH 1/2] regmap: Factor out single value register syncing

[Mark Brown]

In order to support sparse caches that don't store data in raw format
factor out the parts of the raw block sync implementation that deal with
writing a single register via _regmap_write().

Signed-off-by: Mark Brown <broonie@kernel.org>
---
 drivers/base/regmap/internal.h |  1 +
 drivers/base/regmap/regcache.c | 40 ++++++++++++++++++++++++++--------------
 2 files changed, 27 insertions(+), 14 deletions(-)

diff --git a/drivers/base/regmap/internal.h b/drivers/base/regmap/internal.h
index 10aca7119d33..7b9ef43bcea6 100644
--- a/drivers/base/regmap/internal.h
+++ b/drivers/base/regmap/internal.h
@@ -270,6 +270,7 @@ unsigned int regcache_get_val(struct regmap *map, const void *base,
 bool regcache_set_val(struct regmap *map, void *base, unsigned int idx,
 		      unsigned int val);
 int regcache_lookup_reg(struct regmap *map, unsigned int reg);
+int regcache_sync_val(struct regmap *map, unsigned int reg, unsigned int val);
 
 int _regmap_raw_write(struct regmap *map, unsigned int reg,
 		      const void *val, size_t val_len, bool noinc);
diff --git a/drivers/base/regmap/regcache.c b/drivers/base/regmap/regcache.c
index d4877099e990..e5d6b535c002 100644
--- a/drivers/base/regmap/regcache.c
+++ b/drivers/base/regmap/regcache.c
@@ -669,6 +669,30 @@ static bool regcache_reg_present(unsigned long *cache_present, unsigned int idx)
 	return test_bit(idx, cache_present);
 }
 
+int regcache_sync_val(struct regmap *map, unsigned int reg, unsigned int val)
+{
+	int ret;
+
+	if (!regcache_reg_needs_sync(map, reg, val))
+		return 0;
+
+	map->cache_bypass = true;
+
+	ret = _regmap_write(map, reg, val);
+
+	map->cache_bypass = false;
+
+	if (ret != 0) {
+		dev_err(map->dev, "Unable to sync register %#x. %d\n",
+			reg, ret);
+		return ret;
+	}
+	dev_dbg(map->dev, "Synced register %#x, value %#x\n",
+		reg, val);
+
+	return 0;
+}
+
 static int regcache_sync_block_single(struct regmap *map, void *block,
 				      unsigned long *cache_present,
 				      unsigned int block_base,
@@ -685,21 +709,9 @@ static int regcache_sync_block_single(struct regmap *map, void *block,
 			continue;
 
 		val = regcache_get_val(map, block, i);
-		if (!regcache_reg_needs_sync(map, regtmp, val))
-			continue;
-
-		map->cache_bypass = true;
-
-		ret = _regmap_write(map, regtmp, val);
-
-		map->cache_bypass = false;
-		if (ret != 0) {
-			dev_err(map->dev, "Unable to sync register %#x. %d\n",
-				regtmp, ret);
+		ret = regcache_sync_val(map, regtmp, val);
+		if (ret != 0)
 			return ret;
-		}
-		dev_dbg(map->dev, "Synced register %#x, value %#x\n",
-			regtmp, val);
 	}
 
 	return 0;

-- 
2.34.1

[PATCH 2/2] regmap: Add maple tree based register cache

[Mark Brown]

The current state of the art for sparse register maps is the rbtree cache.
This works well for most applications but isn't always ideal for sparser
register maps since the rbtree can get deep, requiring a lot of walking.
Fortunately the kernel has a data structure intended to address this very
problem, the maple tree. Provide an initial implementation of a register
cache based on the maple tree to start taking advantage of it.

This initial implementation is very simplistic and doesn't take full
advantage of the capabilities of the maple tree, we simply store each
register as a single value within the tree. Since maple tree values are
pointers and iteration doesn't naturally give us the key we allocate a
small structure for each register, effectively adding another layer to the
tree.

We also store data in host native format rather than device native format
as we do for rbtree, this will be a benefit for devices where we don't
marshal data within regmap and until we are able to store more than one
register in a node there's no reason to have preformatted data even where
we do marshal.

This works well enough to get started and should already work well for some
devices but there is a great deal of room for improvement, as well as
storing blocks rather than just individual registers we don't need the
locking that the maple tree does and are likely to benefit from caching the
last accessed entry. Very small register maps may continue to to better
with rbtree longer term.

Signed-off-by: Mark Brown <broonie@kernel.org>
---
 drivers/base/regmap/Makefile         |   2 +-
 drivers/base/regmap/internal.h       |   1 +
 drivers/base/regmap/regcache-maple.c | 154 +++++++++++++++++++++++++++++++++++
 drivers/base/regmap/regcache.c       |   1 +
 drivers/base/regmap/regmap-kunit.c   |   3 +
 include/linux/regmap.h               |   1 +
 6 files changed, 161 insertions(+), 1 deletion(-)

diff --git a/drivers/base/regmap/Makefile b/drivers/base/regmap/Makefile
index 4cb73468a197..f6c6cb017200 100644
--- a/drivers/base/regmap/Makefile
+++ b/drivers/base/regmap/Makefile
@@ -3,7 +3,7 @@
 CFLAGS_regmap.o := -I$(src)
 
 obj-$(CONFIG_REGMAP) += regmap.o regcache.o
-obj-$(CONFIG_REGMAP) += regcache-rbtree.o regcache-flat.o
+obj-$(CONFIG_REGMAP) += regcache-rbtree.o regcache-flat.o regcache-maple.o
 obj-$(CONFIG_DEBUG_FS) += regmap-debugfs.o
 obj-$(CONFIG_REGMAP_KUNIT) += regmap-kunit.o
 obj-$(CONFIG_REGMAP_AC97) += regmap-ac97.o
diff --git a/drivers/base/regmap/internal.h b/drivers/base/regmap/internal.h
index 7b9ef43bcea6..6361df6f553a 100644
--- a/drivers/base/regmap/internal.h
+++ b/drivers/base/regmap/internal.h
@@ -282,6 +282,7 @@ enum regmap_endian regmap_get_val_endian(struct device *dev,
 					 const struct regmap_config *config);
 
 extern struct regcache_ops regcache_rbtree_ops;
+extern struct regcache_ops regcache_maple_ops;
 extern struct regcache_ops regcache_flat_ops;
 
 static inline const char *regmap_name(const struct regmap *map)
diff --git a/drivers/base/regmap/regcache-maple.c b/drivers/base/regmap/regcache-maple.c
new file mode 100644
index 000000000000..a18966aed27e
--- /dev/null
+++ b/drivers/base/regmap/regcache-maple.c
@@ -0,0 +1,154 @@
+// SPDX-License-Identifier: GPL-2.0
+//
+// Register cache access API - maple tree based cache
+//
+// Copyright 2023 Arm, Ltd
+//
+// Author: Mark Brown <broonie@kernel.org>
+
+#include <linux/debugfs.h>
+#include <linux/device.h>
+#include <linux/maple_tree.h>
+#include <linux/slab.h>
+
+#include "internal.h"
+
+struct cache_entry {
+	unsigned int reg;
+	unsigned int val;
+};
+
+static int regcache_maple_read(struct regmap *map,
+			       unsigned int reg, unsigned int *value)
+{
+	struct maple_tree *mt = map->cache;
+	struct cache_entry *entry;
+
+	entry = mtree_load(mt, reg);
+	if (!entry)
+		return -ENOENT;
+
+	*value = entry->val;
+
+	return 0;
+}
+
+static int regcache_maple_write(struct regmap *map, unsigned int reg,
+				unsigned int val)
+{
+	struct maple_tree *mt = map->cache;
+	MA_STATE(mas, mt, reg, reg);
+	struct cache_entry *entry;
+	int ret;
+
+	entry = mas_find(&mas, reg);
+	if (entry) {
+		entry->val = val;
+		return 0;
+	}
+
+	entry = kmalloc(sizeof(*entry), GFP_KERNEL);
+	if (!entry)
+		return -ENOMEM;
+
+	entry->reg = reg;
+	entry->val = val;
+
+	ret = mtree_store(mt, reg, entry, GFP_KERNEL);
+	if (ret != 0)
+		kfree(entry);
+
+	return ret;
+}
+
+static int regcache_maple_drop(struct regmap *map, unsigned int min,
+			       unsigned int max)
+{
+	struct maple_tree *mt = map->cache;
+	MA_STATE(mas, mt, min, max);
+	struct cache_entry *entry;
+
+	for (entry = mas_find(&mas, min); entry; entry = mas_next(&mas, max)) {
+		kfree(entry);
+		mas_erase(&mas);
+	}
+
+	return 0;
+}
+
+static int regcache_maple_sync(struct regmap *map, unsigned int min,
+			       unsigned int max)
+{
+	struct maple_tree *mt = map->cache;
+	struct cache_entry *entry;
+	MA_STATE(mas, mt, min, max);
+	int ret;
+
+	map->cache_bypass = true;
+
+	for (entry = mas_find(&mas, min); entry; entry = mas_next(&mas, max)) {
+		ret = regcache_sync_val(map, entry->reg, entry->val);
+		if (ret != 0)
+			goto out;
+	}
+
+out:
+	map->cache_bypass = false;
+
+	return ret;
+}
+
+static int regcache_maple_exit(struct regmap *map)
+{
+	struct maple_tree *mt = map->cache;
+
+	/* if we've already been called then just return */
+	if (!mt)
+		return 0;
+
+	regcache_maple_drop(map, 0, UINT_MAX);
+
+	kfree(mt);
+	map->cache = NULL;
+
+	return 0;
+}
+
+static int regcache_maple_init(struct regmap *map)
+{
+	struct maple_tree *mt;
+	int i;
+	int ret;
+
+	mt = kmalloc(sizeof(*mt), GFP_KERNEL);
+	if (!mt)
+		return -ENOMEM;
+	map->cache = mt;
+
+	mt_init(mt);
+
+	for (i = 0; i < map->num_reg_defaults; i++) {
+		ret = regcache_maple_write(map,
+					   map->reg_defaults[i].reg,
+					   map->reg_defaults[i].def);
+		if (ret)
+			goto err;
+	}
+
+	return 0;
+
+err:
+	regcache_maple_exit(map);
+	return ret;
+}
+
+struct regcache_ops regcache_maple_ops = {
+	.type = REGCACHE_MAPLE,
+	.name = "maple",
+	.init = regcache_maple_init,
+	.exit = regcache_maple_exit,
+	.read = regcache_maple_read,
+	.write = regcache_maple_write,
+	.drop = regcache_maple_drop,
+	.sync = regcache_maple_sync,
+};
diff --git a/drivers/base/regmap/regcache.c b/drivers/base/regmap/regcache.c
index e5d6b535c002..0b47721089e6 100644
--- a/drivers/base/regmap/regcache.c
+++ b/drivers/base/regmap/regcache.c
@@ -17,6 +17,7 @@
 
 static const struct regcache_ops *cache_types[] = {
 	&regcache_rbtree_ops,
+	&regcache_maple_ops,
 	&regcache_flat_ops,
 };
 
diff --git a/drivers/base/regmap/regmap-kunit.c b/drivers/base/regmap/regmap-kunit.c
index 6f2bfa4650fe..3486bf9e28b8 100644
--- a/drivers/base/regmap/regmap-kunit.c
+++ b/drivers/base/regmap/regmap-kunit.c
@@ -29,6 +29,7 @@ static const struct regcache_types regcache_types_list[] = {
 	{ REGCACHE_NONE, "none" },
 	{ REGCACHE_FLAT, "flat" },
 	{ REGCACHE_RBTREE, "rbtree" },
+	{ REGCACHE_MAPLE, "maple" },
 };
 
 KUNIT_ARRAY_PARAM(regcache_types, regcache_types_list, case_to_desc);
@@ -36,12 +37,14 @@ KUNIT_ARRAY_PARAM(regcache_types, regcache_types_list, case_to_desc);
 static const struct regcache_types real_cache_types_list[] = {
 	{ REGCACHE_FLAT, "flat" },
 	{ REGCACHE_RBTREE, "rbtree" },
+	{ REGCACHE_MAPLE, "maple" },
 };
 
 KUNIT_ARRAY_PARAM(real_cache_types, real_cache_types_list, case_to_desc);
 
 static const struct regcache_types sparse_cache_types_list[] = {
 	{ REGCACHE_RBTREE, "rbtree" },
+	{ REGCACHE_MAPLE, "maple" },
 };
 
 KUNIT_ARRAY_PARAM(sparse_cache_types, sparse_cache_types_list, case_to_desc);
diff --git a/include/linux/regmap.h b/include/linux/regmap.h
index 24fc4a9ed1f9..11b360da199d 100644
--- a/include/linux/regmap.h
+++ b/include/linux/regmap.h
@@ -51,6 +51,7 @@ enum regcache_type {
 	REGCACHE_NONE,
 	REGCACHE_RBTREE,
 	REGCACHE_FLAT,
+	REGCACHE_MAPLE,
 };
 
 /**

-- 
2.34.1

Re: [PATCH 2/2] regmap: Add maple tree based register cache

[Liam R. Howlett]

* Mark Brown <broonie@kernel.org> [230325 17:53]:
> The current state of the art for sparse register maps is the rbtree cache.
> This works well for most applications but isn't always ideal for sparser
> register maps since the rbtree can get deep, requiring a lot of walking.
> Fortunately the kernel has a data structure intended to address this very
> problem, the maple tree. Provide an initial implementation of a register
> cache based on the maple tree to start taking advantage of it.
> 
> This initial implementation is very simplistic and doesn't take full
> advantage of the capabilities of the maple tree, we simply store each
> register as a single value within the tree. Since maple tree values are
> pointers and iteration doesn't naturally give us the key we allocate a
> small structure for each register, effectively adding another layer to the
> tree.
> 
> We also store data in host native format rather than device native format
> as we do for rbtree, this will be a benefit for devices where we don't
> marshal data within regmap and until we are able to store more than one
> register in a node there's no reason to have preformatted data even where
> we do marshal.
> 
> This works well enough to get started and should already work well for some
> devices but there is a great deal of room for improvement, as well as
> storing blocks rather than just individual registers we don't need the
> locking that the maple tree does and are likely to benefit from caching the
> last accessed entry. Very small register maps may continue to to better
> with rbtree longer term.

Without use of the locking, the maple tree will generate lockdep
complaints.

With the mas_* family of functions, you are responsible for locking.  On
read you can take the rcu_read_lock(), on writes you need to take
mas_lock(&mas).

If you have a lock you already use, you can init the tree with the
external lock flag and set the external lock like we do in the VMA code.

mtree_* functions handle this for you.

> 
> Signed-off-by: Mark Brown <broonie@kernel.org>
> ---
>  drivers/base/regmap/Makefile         |   2 +-
>  drivers/base/regmap/internal.h       |   1 +
>  drivers/base/regmap/regcache-maple.c | 154 +++++++++++++++++++++++++++++++++++
>  drivers/base/regmap/regcache.c       |   1 +
>  drivers/base/regmap/regmap-kunit.c   |   3 +
>  include/linux/regmap.h               |   1 +
>  6 files changed, 161 insertions(+), 1 deletion(-)
> 
> diff --git a/drivers/base/regmap/Makefile b/drivers/base/regmap/Makefile
> index 4cb73468a197..f6c6cb017200 100644
> --- a/drivers/base/regmap/Makefile
> +++ b/drivers/base/regmap/Makefile
> @@ -3,7 +3,7 @@
>  CFLAGS_regmap.o := -I$(src)
>  
>  obj-$(CONFIG_REGMAP) += regmap.o regcache.o
> -obj-$(CONFIG_REGMAP) += regcache-rbtree.o regcache-flat.o
> +obj-$(CONFIG_REGMAP) += regcache-rbtree.o regcache-flat.o regcache-maple.o
>  obj-$(CONFIG_DEBUG_FS) += regmap-debugfs.o
>  obj-$(CONFIG_REGMAP_KUNIT) += regmap-kunit.o
>  obj-$(CONFIG_REGMAP_AC97) += regmap-ac97.o
> diff --git a/drivers/base/regmap/internal.h b/drivers/base/regmap/internal.h
> index 7b9ef43bcea6..6361df6f553a 100644
> --- a/drivers/base/regmap/internal.h
> +++ b/drivers/base/regmap/internal.h
> @@ -282,6 +282,7 @@ enum regmap_endian regmap_get_val_endian(struct device *dev,
>  					 const struct regmap_config *config);
>  
>  extern struct regcache_ops regcache_rbtree_ops;
> +extern struct regcache_ops regcache_maple_ops;
>  extern struct regcache_ops regcache_flat_ops;
>  
>  static inline const char *regmap_name(const struct regmap *map)
> diff --git a/drivers/base/regmap/regcache-maple.c b/drivers/base/regmap/regcache-maple.c
> new file mode 100644
> index 000000000000..a18966aed27e
> --- /dev/null
> +++ b/drivers/base/regmap/regcache-maple.c
> @@ -0,0 +1,154 @@
> +// SPDX-License-Identifier: GPL-2.0
> +//
> +// Register cache access API - maple tree based cache
> +//
> +// Copyright 2023 Arm, Ltd
> +//
> +// Author: Mark Brown <broonie@kernel.org>
> +
> +#include <linux/debugfs.h>
> +#include <linux/device.h>
> +#include <linux/maple_tree.h>
> +#include <linux/slab.h>
> +
> +#include "internal.h"
> +
> +struct cache_entry {
> +	unsigned int reg;
> +	unsigned int val;
> +};
> +
> +static int regcache_maple_read(struct regmap *map,
> +			       unsigned int reg, unsigned int *value)
> +{
> +	struct maple_tree *mt = map->cache;
> +	struct cache_entry *entry;
> +
> +	entry = mtree_load(mt, reg);
> +	if (!entry)
> +		return -ENOENT;
> +
> +	*value = entry->val;
> +
> +	return 0;
> +}
> +
> +static int regcache_maple_write(struct regmap *map, unsigned int reg,
> +				unsigned int val)
> +{
> +	struct maple_tree *mt = map->cache;
> +	MA_STATE(mas, mt, reg, reg);
> +	struct cache_entry *entry;
> +	int ret;
> +

The locking is missing here, so you will get lockdep complaints.

> +	entry = mas_find(&mas, reg);
> +	if (entry) {
> +		entry->val = val;
> +		return 0;
> +	}
> +
> +	entry = kmalloc(sizeof(*entry), GFP_KERNEL);
> +	if (!entry)
> +		return -ENOMEM;
> +
> +	entry->reg = reg;
> +	entry->val = val;
> +
> +	ret = mtree_store(mt, reg, entry, GFP_KERNEL);
> +	if (ret != 0)
> +		kfree(entry);
> +
> +	return ret;
> +}
> +
> +static int regcache_maple_drop(struct regmap *map, unsigned int min,
> +			       unsigned int max)
> +{
> +	struct maple_tree *mt = map->cache;
> +	MA_STATE(mas, mt, min, max);
> +	struct cache_entry *entry;
> +

mas_lock(&mas);

> +	for (entry = mas_find(&mas, min); entry; entry = mas_next(&mas, max)) {

This can be written with the maple tree iterator:
mas_for_each(mas, entry, max) {


> +		kfree(entry);
> +		mas_erase(&mas);

This isn't the most efficient way of removing a list of entries, but it
certainly works for the first pass, as you say in the comments.

> +	}

mas_unlock(&mas);

> +
> +	return 0;
> +}

Wait, if this is for destroying the entire tree:
	mas_lock(&mas);
	mas_for_each(mas, entry, max)
		kfree(entry);
	__mt_destroy(mt);
	mas_unlock(&mas);

Calling erase for each item will cause the tree to slowly drain;
rebalancing and re-allocating new nodes over and over. mtree_destroy()
and the non-locking __mt_destroy() will more efficiently walk to free
every node.

If it's not for the entire tree, you can free a range then write a NULL
over the entire range.  But be conscience of the maple state range after
the iterator ends, you will need to mas_set_range(&mas, min, max) prior
to the mas_store_gfp().

> +
> +static int regcache_maple_sync(struct regmap *map, unsigned int min,
> +			       unsigned int max)
> +{
> +	struct maple_tree *mt = map->cache;
> +	struct cache_entry *entry;
> +	MA_STATE(mas, mt, min, max);
> +	int ret;
> +
> +	map->cache_bypass = true;
> +

rcu_read_lock();

> +	for (entry = mas_find(&mas, min); entry; entry = mas_next(&mas, max)) {

mas_for_each(mas, entry, max) {

> +		ret = regcache_sync_val(map, entry->reg, entry->val);
> +		if (ret != 0)
> +			goto out;
> +	}
> +
> +out:

rcu_read_unlock();

> +	map->cache_bypass = false;
> +
> +	return ret;
> +}
> +
> +static int regcache_maple_exit(struct regmap *map)
> +{
> +	struct maple_tree *mt = map->cache;
> +
> +	/* if we've already been called then just return */
> +	if (!mt)
> +		return 0;

There's not a race here with multiple tasks in here at once, right?

> +
> +	regcache_maple_drop(map, 0, UINT_MAX);
> +
> +	kfree(mt);
> +	map->cache = NULL;
> +
> +	return 0;
> +}
> +
> +static int regcache_maple_init(struct regmap *map)
> +{
> +	struct maple_tree *mt;
> +	int i;
> +	int ret;
> +
> +	mt = kmalloc(sizeof(*mt), GFP_KERNEL);
> +	if (!mt)
> +		return -ENOMEM;
> +	map->cache = mt;
> +
> +	mt_init(mt);
> +

The maple tree does support bulk loading (in the b-tree sense).  You can
put the maple tree in this state and pre-allocate nodes in bulk.
kernel/fork.c currently does this through the vma iterator interface.
Note that after a bulk-load, you have to ensure you call mas_destroy()
to free any unused nodes and to potentially cause a rebalance of the
last node (this is automatic).  But, again, like you said in your
comment; this is good for the first pass.

> +	for (i = 0; i < map->num_reg_defaults; i++) {
> +		ret = regcache_maple_write(map,
> +					   map->reg_defaults[i].reg,
> +					   map->reg_defaults[i].def);
> +		if (ret)
> +			goto err;
> +	}
> +
> +	return 0;
> +
> +err:
> +	regcache_maple_exit(map);
> +	return ret;
> +}
> +
> +struct regcache_ops regcache_maple_ops = {
> +	.type = REGCACHE_MAPLE,
> +	.name = "maple",
> +	.init = regcache_maple_init,
> +	.exit = regcache_maple_exit,
> +	.read = regcache_maple_read,
> +	.write = regcache_maple_write,
> +	.drop = regcache_maple_drop,
> +	.sync = regcache_maple_sync,
> +};
> diff --git a/drivers/base/regmap/regcache.c b/drivers/base/regmap/regcache.c
> index e5d6b535c002..0b47721089e6 100644
> --- a/drivers/base/regmap/regcache.c
> +++ b/drivers/base/regmap/regcache.c
> @@ -17,6 +17,7 @@
>  
>  static const struct regcache_ops *cache_types[] = {
>  	&regcache_rbtree_ops,
> +	&regcache_maple_ops,
>  	&regcache_flat_ops,
>  };
>  
> diff --git a/drivers/base/regmap/regmap-kunit.c b/drivers/base/regmap/regmap-kunit.c
> index 6f2bfa4650fe..3486bf9e28b8 100644
> --- a/drivers/base/regmap/regmap-kunit.c
> +++ b/drivers/base/regmap/regmap-kunit.c
> @@ -29,6 +29,7 @@ static const struct regcache_types regcache_types_list[] = {
>  	{ REGCACHE_NONE, "none" },
>  	{ REGCACHE_FLAT, "flat" },
>  	{ REGCACHE_RBTREE, "rbtree" },
> +	{ REGCACHE_MAPLE, "maple" },
>  };
>  
>  KUNIT_ARRAY_PARAM(regcache_types, regcache_types_list, case_to_desc);
> @@ -36,12 +37,14 @@ KUNIT_ARRAY_PARAM(regcache_types, regcache_types_list, case_to_desc);
>  static const struct regcache_types real_cache_types_list[] = {
>  	{ REGCACHE_FLAT, "flat" },
>  	{ REGCACHE_RBTREE, "rbtree" },
> +	{ REGCACHE_MAPLE, "maple" },
>  };
>  
>  KUNIT_ARRAY_PARAM(real_cache_types, real_cache_types_list, case_to_desc);
>  
>  static const struct regcache_types sparse_cache_types_list[] = {
>  	{ REGCACHE_RBTREE, "rbtree" },
> +	{ REGCACHE_MAPLE, "maple" },
>  };
>  
>  KUNIT_ARRAY_PARAM(sparse_cache_types, sparse_cache_types_list, case_to_desc);
> diff --git a/include/linux/regmap.h b/include/linux/regmap.h
> index 24fc4a9ed1f9..11b360da199d 100644
> --- a/include/linux/regmap.h
> +++ b/include/linux/regmap.h
> @@ -51,6 +51,7 @@ enum regcache_type {
>  	REGCACHE_NONE,
>  	REGCACHE_RBTREE,
>  	REGCACHE_FLAT,
> +	REGCACHE_MAPLE,
>  };
>  
>  /**
> 
> -- 
> 2.34.1
> 

Re: [PATCH 2/2] regmap: Add maple tree based register cache

[Mark Brown]

[-- Attachment #1: Type: text/plain, Size: 2955 bytes --]

On Sat, Mar 25, 2023 at 07:41:02PM -0400, Liam R. Howlett wrote:

> Without use of the locking, the maple tree will generate lockdep
> complaints.

> With the mas_* family of functions, you are responsible for locking.  On
> read you can take the rcu_read_lock(), on writes you need to take
> mas_lock(&mas).

> If you have a lock you already use, you can init the tree with the
> external lock flag and set the external lock like we do in the VMA code.

Oh, that's not ideal.  regmap does have an external lock but it's
already taken outside of the cache code, the cache code shouldn't
have to worry about locking.  This does mean the maple tree locks
should never be contended, but there'll still be some overhead.
OTOH we only have to be faster than accessing the underlying bus
so it's merely annoying.  I've added the locking locally.

> > +static int regcache_maple_drop(struct regmap *map, unsigned int min,
> > +			       unsigned int max)
> > +{

> Wait, if this is for destroying the entire tree:
> 	mas_lock(&mas);
> 	mas_for_each(mas, entry, max)
> 		kfree(entry);
> 	__mt_destroy(mt);
> 	mas_unlock(&mas);

It's not just for that - it's also used for selectively
discarding some entries in the cache, we just reuse the code when
freeing the regmap.  It may be worth using the above in the map
free case, though it's not exactly a hot path.

> If it's not for the entire tree, you can free a range then write a NULL
> over the entire range.  But be conscience of the maple state range after
> the iterator ends, you will need to mas_set_range(&mas, min, max) prior
> to the mas_store_gfp().

Will writing NULL leave tree entries in place that get iterated?
Though the code will need to become more complicated anyway if we
might need to split nodes that cover more than one register.

> > +static int regcache_maple_exit(struct regmap *map)
> > +{
> > +	struct maple_tree *mt = map->cache;
> > +
> > +	/* if we've already been called then just return */
> > +	if (!mt)
> > +		return 0;

> There's not a race here with multiple tasks in here at once, right?

No, everything's locked at the caller level.  It's just
simplifying some of the error handling paths (IIRC the actual
issue is freeing a cache that was never allocated).

> > +	mt_init(mt);
> > +

> The maple tree does support bulk loading (in the b-tree sense).  You can
> put the maple tree in this state and pre-allocate nodes in bulk.
> kernel/fork.c currently does this through the vma iterator interface.
> Note that after a bulk-load, you have to ensure you call mas_destroy()
> to free any unused nodes and to potentially cause a rebalance of the
> last node (this is automatic).  But, again, like you said in your
> comment; this is good for the first pass.

Right, I saw the reallocation stuff and was going to save it for
later after I'd arranged to store ranges of registers directly in
the tree rather than having a node per register since there'll be
some overlap there.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 0/2] regmap: Add basic maple tree register cache

[Mark Brown]

On Sat, 25 Mar 2023 21:52:57 +0000, Mark Brown wrote:
> The current state of the art for sparse register maps is the rbtree cache.
> This works well for most applications but isn't always ideal for sparser
> register maps since the rbtree can get deep, requiring a lot of walking.
> Fortunately the kernel has a data structure intended to address this very
> problem, the maple tree. Provide an initial implementation of a register
> cache based on the maple tree to start taking advantage of it.
> 
> [...]

Applied to

   broonie/regmap.git for-next

Thanks!

[1/2] regmap: Factor out single value register syncing
      commit: 05933e2d44607767ecb4937a33df4e882bdf9ad3
[2/2] regmap: Add maple tree based register cache
      commit: f033c26de5a5734625d2dd1dc196745fae186f1b

All being well this means that it will be integrated into the linux-next
tree (usually sometime in the next 24 hours) and sent to Linus during
the next merge window (or sooner if it is a bug fix), however if
problems are discovered then the patch may be dropped or reverted.

You may get further e-mails resulting from automated or manual testing
and review of the tree, please engage with people reporting problems and
send followup patches addressing any issues that are reported if needed.

If any updates are required or you are submitting further changes they
should be sent as incremental updates against current git, existing
patches will not be replaced.

Please add any relevant lists and maintainers to the CCs when replying
to this mail.

Thanks,
Mark