regmap: Add basic maple tree register cache
Subsystems (3)
Mark Brown
maintainerPATCH v2 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.
The entries stored in the maple tree are arrays of register values, with the maple tree keys holding the register addresses. We 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 simplifies the code but will result in additional CPU overhead when syncing the cache on devices where we do marshal data in regmap.
This should work well for a lot of devices, though there's some additional areas that could be looked at such as caching the last accessed entry like we do for rbtree and trying to minimise the maple tree level locking. We should also use bulk writes rather than single register writes when resyncing the cache where possible, even if we don't store in device native format.
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 | 265 +++++++++++++++++++++++++++++++++++ drivers/base/regmap/regcache.c | 1 + drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 272 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 +265 -0
265 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
Mark Brown
maintainerPATCH v2 1/2 regmap: Factor out single value register syncing
In reply to Mark BrownIn 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
maintainerv2 cover 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.
The entries stored in the maple tree are arrays of register values, with the maple tree keys holding the register addresses. We 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 simplifies the code but will result in additional CPU overhead when syncing the cache on devices where we do marshal data in regmap.
This should work well for a lot of devices, though there's some additional areas that could be looked at such as caching the last accessed entry like we do for rbtree and trying to minimise the maple tree level locking. We should also use bulk writes rather than single register writes when syncing the cache where possible, even if we don't store in device native format, and there is room for improvement in how we load register defaults into the cache.
Very small register maps may continue to to better with rbtree longer term, though the difference should become marginal especially in the context of the cost of register I/O.
Changes in v2:
- Rework to store multiple values per maple tree node with
coalescing, bringing us much closer to the state of the art
with rbtree.
- Add locking required for maple tree usage.
- Use more efficent code suggested by Liam to free the register
map.
- Link to v1: https://lore.kernel.org/r/[email protected]
---
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 | 265 +++++++++++++++++++++++++++++++++++ drivers/base/regmap/regcache.c | 41 ++++-- drivers/base/regmap/regmap-kunit.c | 3 + include/linux/regmap.h | 1 + 6 files changed, 299 insertions(+), 15 deletions(-)
---
base-commit: c20bc1c03695287bd19922a32052f2bc7d4a462d
change-id: 20230325-regcache-maple-364e7581cf0c
Best regards,
Signature · 1 line
Mark Brown <[email protected]>