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@xxxxxxxxxx>
---
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@xxxxxxxxxx>
+
+#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[] = {
®cache_rbtree_ops,
+ ®cache_maple_ops,
®cache_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
