regmap: Add basic maple tree register cache
Subsystems (3)
Mark Brown
maintainercover regmap: Add basic maple tree register cache
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.
---
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,
Signature · 1 line
Mark Brown <[email protected]>
Mark Brown
maintainerPATCH 1/2 regmap: Factor out single value register syncing
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().
--- drivers/base/regmap/internal.h | 1 + drivers/base/regmap/regcache.c | 40 ++++++++++++++++++++++++++-------------- 2 files changed, 27 insertions(+), 14 deletions(-)
drivers/base/regmap/internal.h +1 -0
@@ -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);
drivers/base/regmap/regcache.c +26 -14
@@ -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 ;
Signature · 1 line
2.34.1
Mark Brown
maintainerPATCH 2/2 regmap: Add maple tree based register cache
In reply to Mark BrownThe 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.
--- 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(-)
drivers/base/regmap/Makefile +1 -1
@@ -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
drivers/base/regmap/internal.h +1 -0
@@ -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)
drivers/base/regmap/regcache-maple.c new file +154 -0
154 lines not on this page · raw message
drivers/base/regmap/regcache.c +1 -0
@@ -17,6 +17,7 @@static const struct regcache_ops *cache_types[] = { ®cache_rbtree_ops, + ®cache_maple_ops, ®cache_flat_ops, };
drivers/base/regmap/regmap-kunit.c +3 -0
@@ -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);
include/linux/regmap.h +1 -0
@@ -51,6 +51,7 @@ enum regcache_type {REGCACHE_NONE ,REGCACHE_RBTREE ,REGCACHE_FLAT , + REGCACHE_MAPLE, };/**
Signature · 1 line
2.34.1
Re: [PATCH 2/2] regmap: Add maple tree based register cache
Quoted 20 lines · 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.
Quoted 6 lines
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.
Quoted 75 lines
Signed-off-by Mark Brown <[email protected]>--- 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(-)drivers/base/regmap/Makefile +1
-1@@ -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.odrivers/base/regmap/internal.h +1
-0@@ -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)drivers/base/regmap/regcache-maple.c new file +33
-0@@ -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 <[email protected]> + +#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 ;
drivers/base/regmap/regcache-maple.c line 43
Quoted 10 lines
drivers/base/regmap/regcache-maple.c new file +10
-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.
Quoted 17 lines
drivers/base/regmap/regcache-maple.c new file +17
-0+ 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); +
drivers/base/regmap/regcache-maple.c line 70
Quoted 10 lines
drivers/base/regmap/regcache-maple.c new file +10
-0+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);
drivers/base/regmap/regcache-maple.c line 71
Quoted 1 line
drivers/base/regmap/regcache-maple.c new file +1
-0+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) {
drivers/base/regmap/regcache-maple.c line 73
Quoted 2 lines
drivers/base/regmap/regcache-maple.c new file +2
-0+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.
drivers/base/regmap/regcache-maple.c line 74
Quoted 1 line
drivers/base/regmap/regcache-maple.c new file +1
-0+ }
mas_unlock(&mas);
drivers/base/regmap/regcache-maple.c line 34
Quoted 3 lines
drivers/base/regmap/regcache-maple.c new file +3
-0+ +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().
drivers/base/regmap/regcache-maple.c line 88
Quoted 11 lines
drivers/base/regmap/regcache-maple.c new file +11
-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; +
rcu_read_lock();
drivers/base/regmap/regcache-maple.c line 89
Quoted 1 line
drivers/base/regmap/regcache-maple.c new file +1
-0+for (entry =mas_find (&mas, min); entry; entry =mas_next (&mas, max)) {
mas_for_each(mas, entry, max) {
drivers/base/regmap/regcache-maple.c line 95
Quoted 6 lines
drivers/base/regmap/regcache-maple.c new file +6
-0+ ret =regcache_sync_val (map, entry->reg, entry->val); +if (ret !=0 ) + goto out; + } + +out:
rcu_read_unlock();
drivers/base/regmap/regcache-maple.c line 107
Quoted 12 lines
drivers/base/regmap/regcache-maple.c new file +12
-0+ 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?
Quoted 12 lines
drivers/base/regmap/regcache-maple.c new file +12
-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;
drivers/base/regmap/regcache-maple.c line 129
Quoted 10 lines
drivers/base/regmap/regcache-maple.c new file +10
-0+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.
Quoted 80 lines
drivers/base/regmap/regcache-maple.c new file +25
-0+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, +};drivers/base/regmap/regcache.c +1
-0@@ -17,6 +17,7 @@static const struct regcache_ops *cache_types[] = { ®cache_rbtree_ops, + ®cache_maple_ops, ®cache_flat_ops, };drivers/base/regmap/regmap-kunit.c +3
-0@@ -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);include/linux/regmap.h +1
-0@@ -51,6 +51,7 @@ enum regcache_type {REGCACHE_NONE ,REGCACHE_RBTREE ,REGCACHE_FLAT , + REGCACHE_MAPLE, };/** Signature · 2 lines
-- 2.34.1
Mark Brown
maintainerRe: [PATCH 2/2] regmap: Add maple tree based register cache
Quoted 9 lines · Liam R. Howlett
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 takemas_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.
Quoted 10 lines
drivers/base/regmap/regcache-maple.c line 66
Quoted 3 lines
drivers/base/regmap/regcache-maple.c new file +3
-0+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.
Quoted 4 lines
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 themas_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.
Quoted 9 lines
drivers/base/regmap/regcache-maple.c line 107
Quoted 7 lines
drivers/base/regmap/regcache-maple.c new file +7
-0+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).
Quoted 10 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ 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.ccurrently does this through the vma iterator interface. Note that after a bulk-load, you have to ensure you callmas_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.
Mark Brown
maintainerQuoted 8 lines · 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.
[...]
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: f033c26de5a5734625d2dd1dc196745fae186f1bAll 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