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@xxxxxxxxxx>
---
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@xxxxxxxxxx>
