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

[Mark Brown <broonie@kernel.org>]

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 v3:
- Rework locking so we don't allocate with the Maple lock.
- Link to v2: https://lore.kernel.org/r/20230325-regcache-maple-v2-0-799dcab3ecb1@kernel.org
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/20230325-regcache-maple-v1-0-1c76916359fb@kernel.org

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 | 278 +++++++++++++++++++++++++++++++++++
 drivers/base/regmap/regcache.c       |  41 ++++--
 drivers/base/regmap/regmap-kunit.c   |   3 +
 include/linux/regmap.h               |   1 +
 6 files changed, 312 insertions(+), 15 deletions(-)
---
base-commit: c20bc1c03695287bd19922a32052f2bc7d4a462d
change-id: 20230325-regcache-maple-364e7581cf0c

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