Currently the regmap usage of the maple tree is a bit non-idomatic, rather
than storing register values directly we allocate arrays of contiguous
register values and store pointers to those arrays. This is all quite
fiddly, especially around adding values (where we may need to combine a new
allocation with adjacent ones) or dropping values (where we may have to
keep parts of a contiguous block). One reason for doing this is that the
maple tree wants to store pointers rather than integers, and in particular
has some problems when we want to store 0 as a value.

For 64 bit systems we can take advantage of the fact that regmap only
supports 32 bit values and store values with an extra high bit set in the
maple tree, avoiding the special cases with 0 and allowing us to save a
layer of indirection. This approach was suggested by Liam Howlett.

That doesn't help 32 bit systems though since we don't have any non-value bits there. For those we
can keep the same code structure by switching to do a separate allocation
for each value. The resulting data structure is not a thing of beauty but
the code is much less complicated, and should be able to make better use of
the slab allocator in cases where contiguous blocks of registers are not
powers of 2.

Let's implement these two approaches, using CONFIG_64BIT to choose between
direct storage and allocating per-register storage. The end result is much
simpler, making more direct usage of the maple tree API and the detailed
optimisation work that goes into it's implementation. One indication of
the simplifications is that even with having the two different allocation
strategies we still have an overall negative diffstat.

Signed-off-by: Mark Brown <broonie@kernel.org>
---
 drivers/base/regmap/regcache-maple.c | 320 +++++++++++++++--------------------
 1 file changed, 133 insertions(+), 187 deletions(-)

diff --git a/drivers/base/regmap/regcache-maple.c b/drivers/base/regmap/regcache-maple.c
index 2dea9d259c49..e1495326369b 100644
--- a/drivers/base/regmap/regcache-maple.c
+++ b/drivers/base/regmap/regcache-maple.c
@@ -13,26 +13,53 @@
 
 #include "internal.h"
 
-static int regcache_maple_read(struct regmap *map,
-			       unsigned int reg, unsigned int *value)
+#if IS_ENABLED(CONFIG_64BIT)
+/*
+ * On 64 bit systems uintptr_t will be 64 bit but unsigned long 32 bit
+ * so we can store the register values directly in the maple tree.  We
+ * need to always set an out of bounds bit due to maple tree's
+ * handling of NULL.
+ */
+#define REGCACHE_MAPLE_NONZERO (1UL << 32)
+
+static unsigned long regcache_maple_entry_to_value(void *entry)
+{
+	return (uintptr_t)entry & ~REGCACHE_MAPLE_NONZERO;
+}
+
+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);
-	unsigned long *entry;
+	uintptr_t entry = val | REGCACHE_MAPLE_NONZERO;
+	int ret;
 
-	rcu_read_lock();
+	/*
+	 * This is safe because the regmap lock means the Maple lock
+	 * is redundant, but we need to take it due to lockdep asserts
+	 * in the maple tree code.
+	 */
+	mas_lock(&mas);
 
-	entry = mas_walk(&mas);
-	if (!entry) {
-		rcu_read_unlock();
-		return -ENOENT;
-	}
+	mas_set_range(&mas, reg, reg);
+	ret = mas_store_gfp(&mas, (void *)entry, map->alloc_flags);
 
-	*value = entry[reg - mas.index];
+	mas_unlock(&mas);
 
-	rcu_read_unlock();
+	return ret;
+}
 
-	return 0;
+#else
+
+/*
+ * On 32 bit systems we can't distingush between NULL and a valid 0
+ * value in a 32 bit register so kmalloc() extra storage for the
+ * values.
+ */
+static unsigned long regcache_maple_entry_to_value(unsigned long *entry)
+{
+	return *entry;
 }
 
 static int regcache_maple_write(struct regmap *map, unsigned int reg,
@@ -40,49 +67,24 @@ static int regcache_maple_write(struct regmap *map, unsigned int reg,
 {
 	struct maple_tree *mt = map->cache;
 	MA_STATE(mas, mt, reg, reg);
-	unsigned long *entry, *upper, *lower;
-	unsigned long index, last;
-	size_t lower_sz, upper_sz;
+	unsigned long *entry;
 	int ret;
 
 	rcu_read_lock();
 
 	entry = mas_walk(&mas);
 	if (entry) {
-		entry[reg - mas.index] = val;
+		*entry = val;
 		rcu_read_unlock();
 		return 0;
 	}
 
-	/* Any adjacent entries to extend/merge? */
-	mas_set_range(&mas, reg - 1, reg + 1);
-	index = reg;
-	last = reg;
-
-	lower = mas_find(&mas, reg - 1);
-	if (lower) {
-		index = mas.index;
-		lower_sz = (mas.last - mas.index + 1) * sizeof(unsigned long);
-	}
-
-	upper = mas_find(&mas, reg + 1);
-	if (upper) {
-		last = mas.last;
-		upper_sz = (mas.last - mas.index + 1) * sizeof(unsigned long);
-	}
-
 	rcu_read_unlock();
 
-	entry = kmalloc((last - index + 1) * sizeof(unsigned long),
-			map->alloc_flags);
+	entry = kmalloc(sizeof(unsigned long), map->alloc_flags);
 	if (!entry)
 		return -ENOMEM;
-
-	if (lower)
-		memcpy(entry, lower, lower_sz);
-	entry[reg - index] = val;
-	if (upper)
-		memcpy(&entry[reg - index + 1], upper, upper_sz);
+	*entry = val;
 
 	/*
 	 * This is safe because the regmap lock means the Maple lock
@@ -91,97 +93,75 @@ static int regcache_maple_write(struct regmap *map, unsigned int reg,
 	 */
 	mas_lock(&mas);
 
-	mas_set_range(&mas, index, last);
+	mas_set_range(&mas, reg, reg);
 	ret = mas_store_gfp(&mas, entry, map->alloc_flags);
 
 	mas_unlock(&mas);
 
-	if (ret == 0) {
-		kfree(lower);
-		kfree(upper);
-	}
+	if (ret != 0)
+		kfree(entry);
 	
 	return ret;
 }
+#endif
+
+static int regcache_maple_read(struct regmap *map,
+			       unsigned int reg, unsigned int *value)
+{
+	struct maple_tree *mt = map->cache;
+	MA_STATE(mas, mt, reg, reg);
+	void *entry;
+
+	rcu_read_lock();
+
+	entry = mas_walk(&mas);
+	if (!entry) {
+		rcu_read_unlock();
+		return -ENOENT;
+	}
+
+	*value = regcache_maple_entry_to_value(entry);
+
+	rcu_read_unlock();
+
+	return 0;
+}
 
 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);
-	unsigned long *entry, *lower, *upper;
-	/* initialized to work around false-positive -Wuninitialized warning */
-	unsigned long lower_index = 0, lower_last = 0;
-	unsigned long upper_index, upper_last;
+	unsigned long *entry;
 	int ret = 0;
 
-	lower = NULL;
-	upper = NULL;
-
 	mas_lock(&mas);
 
 	mas_for_each(&mas, entry, max) {
+		if (WARN_ON_ONCE(mas.index != mas.last)) {
+			ret = -EFAULT;
+			goto out;
+		}
+
+		if (mas.index < min || mas.last > max)
+			continue;
+
 		/*
 		 * This is safe because the regmap lock means the
 		 * Maple lock is redundant, but we need to take it due
 		 * to lockdep asserts in the maple tree code.
 		 */
-		mas_unlock(&mas);
-
-		/* Do we need to save any of this entry? */
-		if (mas.index < min) {
-			lower_index = mas.index;
-			lower_last = min -1;
-
-			lower = kmemdup_array(entry,
-					      min - mas.index, sizeof(*lower),
-					      map->alloc_flags);
-			if (!lower) {
-				ret = -ENOMEM;
-				goto out_unlocked;
-			}
-		}
-
-		if (mas.last > max) {
-			upper_index = max + 1;
-			upper_last = mas.last;
-
-			upper = kmemdup_array(&entry[max - mas.index + 1],
-					      mas.last - max, sizeof(*upper),
-					      map->alloc_flags);
-			if (!upper) {
-				ret = -ENOMEM;
-				goto out_unlocked;
-			}
+		if (!IS_ENABLED(CONFIG_64BIT)) {
+			mas_unlock(&mas);
+			kfree(entry);
+			mas_lock(&mas);
 		}
 
-		kfree(entry);
-		mas_lock(&mas);
 		mas_erase(&mas);
-
-		/* Insert new nodes with the saved data */
-		if (lower) {
-			mas_set_range(&mas, lower_index, lower_last);
-			ret = mas_store_gfp(&mas, lower, map->alloc_flags);
-			if (ret != 0)
-				goto out;
-			lower = NULL;
-		}
-
-		if (upper) {
-			mas_set_range(&mas, upper_index, upper_last);
-			ret = mas_store_gfp(&mas, upper, map->alloc_flags);
-			if (ret != 0)
-				goto out;
-			upper = NULL;
-		}
 	}
 
 out:
 	mas_unlock(&mas);
-out_unlocked:
-	kfree(lower);
-	kfree(upper);
 
 	return ret;
 }
@@ -191,6 +171,7 @@ static int regcache_maple_sync_block(struct regmap *map, unsigned long *entry,
 				     unsigned int min, unsigned int max)
 {
 	void *buf;
+	unsigned int v;
 	unsigned long r;
 	size_t val_bytes = map->format.val_bytes;
 	int ret = 0;
@@ -211,19 +192,25 @@ static int regcache_maple_sync_block(struct regmap *map, unsigned long *entry,
 		}
 
 		/* Render the data for a raw write */
-		for (r = min; r < max; r++) {
-			regcache_set_val(map, buf, r - min,
-					 entry[r - mas->index]);
+		for (r = min; r < max + 1; r++) {
+			ret = regcache_maple_read(map, r, &v);
+			if (ret != 0) {
+				kfree(buf);
+				goto out;
+			}
+			regcache_set_val(map, buf, r - min, v);
 		}
 
-		ret = _regmap_raw_write(map, min, buf, (max - min) * val_bytes,
+		ret = _regmap_raw_write(map, min, buf, (max - min + 1) * val_bytes,
 					false);
 
 		kfree(buf);
 	} else {
-		for (r = min; r < max; r++) {
-			ret = _regmap_write(map, r,
-					    entry[r - mas->index]);
+		for (r = min; r < max + 1; r++) {
+			ret = regcache_maple_read(map, r, &v);
+			if (ret != 0)
+				goto out;
+			ret = _regmap_write(map, r, v);
 			if (ret != 0)
 				goto out;
 		}
@@ -241,9 +228,7 @@ static int regcache_maple_sync(struct regmap *map, unsigned int min,
 	struct maple_tree *mt = map->cache;
 	unsigned long *entry;
 	MA_STATE(mas, mt, min, max);
-	unsigned long lmin = min;
-	unsigned long lmax = max;
-	unsigned int r, v, sync_start;
+	unsigned int v, last, sync_start;
 	int ret = 0;
 	bool sync_needed = false;
 
@@ -252,34 +237,39 @@ static int regcache_maple_sync(struct regmap *map, unsigned int min,
 	rcu_read_lock();
 
 	mas_for_each(&mas, entry, max) {
-		for (r = max(mas.index, lmin); r <= min(mas.last, lmax); r++) {
-			v = entry[r - mas.index];
-
-			if (regcache_reg_needs_sync(map, r, v)) {
-				if (!sync_needed) {
-					sync_start = r;
-					sync_needed = true;
-				}
-				continue;
-			}
-
-			if (!sync_needed)
-				continue;
-
+		/* Flush if we hit a gap in the cache */
+		if (sync_needed && mas.index != last + 1) {
 			ret = regcache_maple_sync_block(map, entry, &mas,
-							sync_start, r);
+							sync_start, last);
 			if (ret != 0)
 				goto out;
 			sync_needed = false;
 		}
 
-		if (sync_needed) {
-			ret = regcache_maple_sync_block(map, entry, &mas,
-							sync_start, r);
-			if (ret != 0)
-				goto out;
-			sync_needed = false;
+		v = regcache_maple_entry_to_value(entry);
+
+		if (regcache_reg_needs_sync(map, mas.index, v)) {
+			if (!sync_needed) {
+				sync_start = mas.index;
+				sync_needed = true;
+			}
+			last = mas.index;
+			continue;
 		}
+
+		if (!sync_needed)
+			continue;
+
+		ret = regcache_maple_sync_block(map, entry, &mas,
+						sync_start, last);
+		if (ret != 0)
+			goto out;
+		sync_needed = false;
+	}
+
+	if (sync_needed) {
+		ret = regcache_maple_sync_block(map, entry, &mas,
+						sync_start, last);
 	}
 
 out:
@@ -301,8 +291,10 @@ static int regcache_maple_exit(struct regmap *map)
 		return 0;
 
 	mas_lock(&mas);
-	mas_for_each(&mas, entry, UINT_MAX)
-		kfree(entry);
+	if (!IS_ENABLED(CONFIG_64BIT)) {
+		mas_for_each(&mas, entry, UINT_MAX)
+			kfree(entry);
+	}
 	__mt_destroy(mt);
 	mas_unlock(&mas);
 
@@ -312,41 +304,11 @@ static int regcache_maple_exit(struct regmap *map)
 	return 0;
 }
 
-static int regcache_maple_insert_block(struct regmap *map, int first,
-					int last)
-{
-	struct maple_tree *mt = map->cache;
-	MA_STATE(mas, mt, first, last);
-	unsigned long *entry;
-	int i, ret;
-
-	entry = kcalloc(last - first + 1, sizeof(unsigned long), map->alloc_flags);
-	if (!entry)
-		return -ENOMEM;
-
-	for (i = 0; i < last - first + 1; i++)
-		entry[i] = map->reg_defaults[first + i].def;
-
-	mas_lock(&mas);
-
-	mas_set_range(&mas, map->reg_defaults[first].reg,
-		      map->reg_defaults[last].reg);
-	ret = mas_store_gfp(&mas, entry, map->alloc_flags);
-
-	mas_unlock(&mas);
-
-	if (ret)
-		kfree(entry);
-
-	return ret;
-}
-
 static int regcache_maple_init(struct regmap *map)
 {
 	struct maple_tree *mt;
 	int i;
 	int ret;
-	int range_start;
 
 	mt = kmalloc(sizeof(*mt), GFP_KERNEL);
 	if (!mt)
@@ -355,30 +317,14 @@ static int regcache_maple_init(struct regmap *map)
 
 	mt_init(mt);
 
-	if (!map->num_reg_defaults)
-		return 0;
-
-	range_start = 0;
-
-	/* Scan for ranges of contiguous registers */
-	for (i = 1; i < map->num_reg_defaults; i++) {
-		if (map->reg_defaults[i].reg !=
-		    map->reg_defaults[i - 1].reg + 1) {
-			ret = regcache_maple_insert_block(map, range_start,
-							  i - 1);
-			if (ret != 0)
-				goto err;
-
-			range_start = i;
-		}
+	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 != 0)
+			goto err;
 	}
 
-	/* Add the last block */
-	ret = regcache_maple_insert_block(map, range_start,
-					  map->num_reg_defaults - 1);
-	if (ret != 0)
-		goto err;
-
 	return 0;
 
 err:

---
base-commit: 98f7e32f20d28ec452afb208f9cffc08448a2652
change-id: 20240925-regmap-maple-idiomatic-f99357b9fb1e

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

Hi Mark,

On Thu, Sep 26, 2024 at 12:20 PM Mark Brown <broonie@kernel.org> wrote:
> Currently the regmap usage of the maple tree is a bit non-idomatic, rather
> than storing register values directly we allocate arrays of contiguous
> register values and store pointers to those arrays. This is all quite
> fiddly, especially around adding values (where we may need to combine a new
> allocation with adjacent ones) or dropping values (where we may have to
> keep parts of a contiguous block). One reason for doing this is that the
> maple tree wants to store pointers rather than integers, and in particular
> has some problems when we want to store 0 as a value.
>
> For 64 bit systems we can take advantage of the fact that regmap only
> supports 32 bit values and store values with an extra high bit set in the
> maple tree, avoiding the special cases with 0 and allowing us to save a
> layer of indirection. This approach was suggested by Liam Howlett.
>
> That doesn't help 32 bit systems though since we don't have any non-value bits there. For those we
> can keep the same code structure by switching to do a separate allocation
> for each value. The resulting data structure is not a thing of beauty but
> the code is much less complicated, and should be able to make better use of
> the slab allocator in cases where contiguous blocks of registers are not
> powers of 2.
>
> Let's implement these two approaches, using CONFIG_64BIT to choose between
> direct storage and allocating per-register storage. The end result is much
> simpler, making more direct usage of the maple tree API and the detailed
> optimisation work that goes into it's implementation. One indication of
> the simplifications is that even with having the two different allocation
> strategies we still have an overall negative diffstat.
>
> Signed-off-by: Mark Brown <broonie@kernel.org>

Thanks for your patch, which is now commit 49a85851b14cf663 ("regcache:
Store values more directly in maple trees") in regmap/for-next.

I started seeing intermittent memory corruption reports during s2idle
on Salvator-XS:

    BUG: KFENCE: memory corruption in
regcache_maple_sync_block.constprop.0+0xcc/0x1c8

    Corrupted memory at 0x00000000ba391541 [ ! . . . ] (in kfence-#12):
     regcache_maple_sync_block.constprop.0+0xcc/0x1c8
     regcache_maple_sync+0x140/0x1b0
     regcache_sync+0xc8/0x208
     vc5_resume+0x28/0x54
     dpm_run_callback+0x5c/0xc8
     device_resume+0xf8/0x1d4
     async_resume+0x20/0x34
     async_run_entry_fn+0x34/0xec
     process_scheduled_works+0x2e8/0x4a8
     worker_thread+0x150/0x1dc
     kthread+0xe4/0xf4
     ret_from_fork+0x10/0x20

    kfence-#12: 0x000000003219df44-0x0000000074811d38, size=4, cache=kmalloc-8

    allocated by task 1058 on cpu 6 at 694.672934s (0.104605s ago):
     regcache_maple_sync_block.constprop.0+0x70/0x1c8
     regcache_maple_sync+0x140/0x1b0
     regcache_sync+0xc8/0x208
     vc5_resume+0x28/0x54
     dpm_run_callback+0x5c/0xc8
     device_resume+0xf8/0x1d4
     async_resume+0x20/0x34
     async_run_entry_fn+0x34/0xec
     process_scheduled_works+0x2e8/0x4a8
     worker_thread+0x150/0x1dc
     kthread+0xe4/0xf4
     ret_from_fork+0x10/0x20

    freed by task 1058 on cpu 6 at 694.673657s (0.164678s ago):
     regcache_maple_sync_block.constprop.0+0xcc/0x1c8
     regcache_maple_sync+0x140/0x1b0
     regcache_sync+0xc8/0x208
     vc5_resume+0x28/0x54
     dpm_run_callback+0x5c/0xc8
     device_resume+0xf8/0x1d4
     async_resume+0x20/0x34
     async_run_entry_fn+0x34/0xec
     process_scheduled_works+0x2e8/0x4a8
     worker_thread+0x150/0x1dc
     kthread+0xe4/0xf4
     ret_from_fork+0x10/0x20

    CPU: 6 UID: 0 PID: 1058 Comm: kworker/u33:9 Tainted: G        W
      6.12.0-rc5-rcar3-05681-g29cac4e36a79 #148
    Tainted: [W]=WARN
    Hardware name: Renesas Salvator-X 2nd version board based on r8a77951 (DT)
    Workqueue: async async_run_entry_fn

While I did not bisect the issue, this change looks suspicious to me...

> --- a/drivers/base/regmap/regcache-maple.c
> +++ b/drivers/base/regmap/regcache-maple.c
> @@ -13,26 +13,53 @@
>
>  #include "internal.h"
>
> -static int regcache_maple_read(struct regmap *map,
> -                              unsigned int reg, unsigned int *value)
> +#if IS_ENABLED(CONFIG_64BIT)
> +/*
> + * On 64 bit systems uintptr_t will be 64 bit but unsigned long 32 bit
> + * so we can store the register values directly in the maple tree.  We

... as this assumption is not true: "unsigned long" is 64-bit on
64-bit platforms (and 32-bit on 32-bit platforms).

> + * need to always set an out of bounds bit due to maple tree's
> + * handling of NULL.
> + */

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

On Tue, Oct 29, 2024 at 03:26:41PM +0100, Geert Uytterhoeven wrote:
> On Thu, Sep 26, 2024 at 12:20 PM Mark Brown <broonie@kernel.org> wrote:

> > + * On 64 bit systems uintptr_t will be 64 bit but unsigned long 32 bit
> > + * so we can store the register values directly in the maple tree.  We

> ... as this assumption is not true: "unsigned long" is 64-bit on
> 64-bit platforms (and 32-bit on 32-bit platforms).

You're right, I'm not sure what I was thinking there.  I think it was
confusion caused by the spurious warnings generated with u64.

On Thu, 26 Sep 2024 12:18:41 +0200, Mark Brown wrote:
> Currently the regmap usage of the maple tree is a bit non-idomatic, rather
> than storing register values directly we allocate arrays of contiguous
> register values and store pointers to those arrays. This is all quite
> fiddly, especially around adding values (where we may need to combine a new
> allocation with adjacent ones) or dropping values (where we may have to
> keep parts of a contiguous block). One reason for doing this is that the
> maple tree wants to store pointers rather than integers, and in particular
> has some problems when we want to store 0 as a value.
> 
> [...]

Applied to

   https://git.kernel.org/pub/scm/linux/kernel/git/broonie/regmap.git for-next

Thanks!

[1/1] regcache: Store values more directly in maple trees
      commit: 49a85851b14cf6630013d1b9bae2ac2345c9430b

All 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