regmap: cache: rbtree: use krealloc_array() to replace krealloc()

Use krealloc_array() to replace krealloc() with multiplication.
krealloc_array() has multiply overflow check, which will be safer.

regmap: cache: rbtree: use krealloc_array() to replace krealloc()

Use krealloc_array() to replace krealloc() with multiplication.
krealloc_array() has multiply overflow check, which will be safer.

Signed-off-by: Andy Shevchenko <[email protected]>
Link: https://patch.msgid.link/[email protected]
Signed-off-by: Mark Brown <[email protected]>

show more ...

regcache: use map->alloc_flags also for allocating cache

Commit fd4ebc07b4df ("regmap: Hold the regmap lock when allocating and
freeing the cache") introduced a locking around the allocating and
fre

regcache: use map->alloc_flags also for allocating cache

Commit fd4ebc07b4df ("regmap: Hold the regmap lock when allocating and
freeing the cache") introduced a locking around the allocating and
freeing a regmap cache, so adjust the memory allocation flags to the ones
given in the regmap configuration instead of the hardcoded GFP_KERNEL.

This fixes the "BUG: sleeping function called from invalid context"
introduced by the mentioned commit.

Fixes: fd4ebc07b4df ("regmap: Hold the regmap lock when allocating and freeing the cache")
Signed-off-by: Marek Szyprowski <[email protected]>
Link: https://patch.msgid.link/[email protected]
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Fix wrong register marked as in-cache when creating new node

When regcache_rbtree_write() creates a new rbtree_node it was passing the
wrong bit number to regcache_rbtree_set_registe

regmap: rbtree: Fix wrong register marked as in-cache when creating new node

When regcache_rbtree_write() creates a new rbtree_node it was passing the
wrong bit number to regcache_rbtree_set_register(). The bit number is the
offset __in number of registers__, but in the case of creating a new block
regcache_rbtree_write() was not dividing by the address stride to get the
number of registers.

Fix this by dividing by map->reg_stride.
Compare with regcache_rbtree_read() where the bit is checked.

This bug meant that the wrong register was marked as present. The register
that was written to the cache could not be read from the cache because it
was not marked as cached. But a nearby register could be marked as having
a cached value even if it was never written to the cache.

Signed-off-by: Richard Fitzgerald <[email protected]>
Fixes: 3f4ff561bc88 ("regmap: rbtree: Make cache_present bitmap per node")
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: Fix the type used for a bitmap pointer

Bitmaps should be defined as 'unsigned long', not 'long'.
Fix the type of 'cache_present' is the 'struct regcache_rbtree_node'.

Signed-off-by: Christo

regmap: Fix the type used for a bitmap pointer

Bitmaps should be defined as 'unsigned long', not 'long'.
Fix the type of 'cache_present' is the 'struct regcache_rbtree_node'.

Signed-off-by: Christophe JAILLET <[email protected]>
Link: https://lore.kernel.org/r/5600df5003d23da10efcfafbda97ca55776d0d29.1689960321.git.christophe.jaillet@wanadoo.fr
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Use alloc_flags for memory allocations

The kunit tests discovered a sleeping in atomic bug. The allocations
in the regcache-rbtree code should use the map->alloc_flags instead of
GF

regmap: rbtree: Use alloc_flags for memory allocations

The kunit tests discovered a sleeping in atomic bug. The allocations
in the regcache-rbtree code should use the map->alloc_flags instead of
GFP_KERNEL.

[ 5.005510] BUG: sleeping function called from invalid context at include/linux/sched/mm.h:306
[ 5.005960] in_atomic(): 1, irqs_disabled(): 128, non_block: 0, pid: 117, name: kunit_try_catch
[ 5.006219] preempt_count: 1, expected: 0
[ 5.006414] 1 lock held by kunit_try_catch/117:
[ 5.006590] #0: 833b9010 (regmap_kunit:86:(config)->lock){....}-{2:2}, at: regmap_lock_spinlock+0x14/0x1c
[ 5.007493] irq event stamp: 162
[ 5.007627] hardirqs last enabled at (161): [<80786738>] crng_make_state+0x1a0/0x294
[ 5.007871] hardirqs last disabled at (162): [<80c531ec>] _raw_spin_lock_irqsave+0x7c/0x80
[ 5.008119] softirqs last enabled at (0): [<801110ac>] copy_process+0x810/0x2138
[ 5.008356] softirqs last disabled at (0): [<00000000>] 0x0
[ 5.008688] CPU: 0 PID: 117 Comm: kunit_try_catch Tainted: G N 6.4.4-rc3-g0e8d2fdfb188 #1
[ 5.009011] Hardware name: Generic DT based system
[ 5.009277] unwind_backtrace from show_stack+0x18/0x1c
[ 5.009497] show_stack from dump_stack_lvl+0x38/0x5c
[ 5.009676] dump_stack_lvl from __might_resched+0x188/0x2d0
[ 5.009860] __might_resched from __kmem_cache_alloc_node+0x1dc/0x25c
[ 5.010061] __kmem_cache_alloc_node from kmalloc_trace+0x30/0xc8
[ 5.010254] kmalloc_trace from regcache_rbtree_write+0x26c/0x468
[ 5.010446] regcache_rbtree_write from _regmap_write+0x88/0x140
[ 5.010634] _regmap_write from regmap_write+0x44/0x68
[ 5.010803] regmap_write from basic_read_write+0x8c/0x270
[ 5.010980] basic_read_write from kunit_try_run_case+0x48/0xa0

Fixes: 28644c809f44 ("regmap: Add the rbtree cache support")
Reported-by: Guenter Roeck <[email protected]>
Closes: https://lore.kernel.org/all/[email protected]/
Signed-off-by: Dan Carpenter <[email protected]>
Tested-by: Guenter Roeck <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Mark Brown <[email protected]>

show more ...

regcache: Push async I/O request down into the rbtree cache

Currently the regcache core unconditionally enables async I/O for all cache
types, causing problems for the maple tree cache which dynamic

regcache: Push async I/O request down into the rbtree cache

Currently the regcache core unconditionally enables async I/O for all cache
types, causing problems for the maple tree cache which dynamically allocates
the buffers used to write registers to the device since async requires the
buffers to be kept around until the I/O has been completed.

This use of async I/O is mainly for the rbtree cache which stores data in
a format directly usable for regmap_raw_write(), though there is a special
case for single register writes which would also have allowed it to be used
with the flat cache. It is a bit of a landmine for other caches since it
implicitly converts sync operations to async, and with modern hardware it
is not clear that async I/O is actually a performance win as shown by the
performance work David Jander did with SPI. In multi core systems the cost
of managing concurrency ends up swamping the performance benefit and almost
all modern systems are multi core.

Address this by pushing the enablement of async I/O down into the rbtree
cache where it is actively used, avoiding surprises for other cache
implementations.

Reported-by: Charles Keepax <[email protected]>
Fixes: bfa0b38c1483 ("regmap: maple: Implement block sync for the maple tree cache")
Reviewed-by: Charles Keepax <[email protected]>
Tested-by: Charles Keepax <[email protected]>
Signed-off-by: Mark Brown <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: Fix possible double-free in regcache_rbtree_exit()

In regcache_rbtree_insert_to_block(), when 'present' realloc failed,
the 'blk' which is supposed to assign to 'rbnode->block' will be freed

regmap: Fix possible double-free in regcache_rbtree_exit()

In regcache_rbtree_insert_to_block(), when 'present' realloc failed,
the 'blk' which is supposed to assign to 'rbnode->block' will be freed,
so 'rbnode->block' points a freed memory, in the error handling path of
regcache_rbtree_init(), 'rbnode->block' will be freed again in
regcache_rbtree_exit(), KASAN will report double-free as follows:

BUG: KASAN: double-free or invalid-free in kfree+0xce/0x390
Call Trace:
slab_free_freelist_hook+0x10d/0x240
kfree+0xce/0x390
regcache_rbtree_exit+0x15d/0x1a0
regcache_rbtree_init+0x224/0x2c0
regcache_init+0x88d/0x1310
__regmap_init+0x3151/0x4a80
__devm_regmap_init+0x7d/0x100
madera_spi_probe+0x10f/0x333 [madera_spi]
spi_probe+0x183/0x210
really_probe+0x285/0xc30

To fix this, moving up the assignment of rbnode->block to immediately after
the reallocation has succeeded so that the data structure stays valid even
if the second reallocation fails.

Reported-by: Hulk Robot <[email protected]>
Fixes: 3f4ff561bc88b ("regmap: rbtree: Make cache_present bitmap per node")
Signed-off-by: Yang Yingliang <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: add proper SPDX identifiers on files that did not have them.

There were a few files in the regmap code that did not have SPDX
identifiers on them, so fix that up. At the same time, remove t

regmap: add proper SPDX identifiers on files that did not have them.

There were a few files in the regmap code that did not have SPDX
identifiers on them, so fix that up. At the same time, remove the "free
form" text that specified the license of the file, as that is impossible
for any tool to properly parse.

Also, as Mark loves // comment markers, convert all of the headers to be
the same to make things look consistent :)

Signed-off-by: Greg Kroah-Hartman <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: Remove attribute packed from struct 'regcache_rbtree_node'

On one hand commit 28644c809f44 ("regmap: Add the rbtree cache support")
added 'regcache_rbtree_node' as packed structure, while on

regmap: Remove attribute packed from struct 'regcache_rbtree_node'

On one hand commit 28644c809f44 ("regmap: Add the rbtree cache support")
added 'regcache_rbtree_node' as packed structure, while on the other hand
commit e977145aeaad ("[RBTREE] Add explicit alignment to sizeof(long)
for struct rb_node.") declared struct 'rb_node' as aligned.

Solve the ambiguity of placing aligned structure in a packed one by
removing the packed attribute from struct. This seems to be the behavior
of gcc anyway.

This removes the following warning (W=1):

drivers/base/regmap/regcache-rbtree.c:36:1: warning: alignment 1 of 'struct regcache_rbtree_node' is less than 4 [-Wpacked-not-aligned]

Cc: Dimitris Papastamos <[email protected]>
Cc: David Woodhouse <[email protected]>
Signed-off-by: Mathieu Malaterre <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: convert to DEFINE_SHOW_ATTRIBUTE

Use DEFINE_SHOW_ATTRIBUTE macro to simplify the code.

Signed-off-by: Yangtao Li <[email protected]>
Signed-off-by: Mark Brown <[email protected]

regmap: rbtree: convert to DEFINE_SHOW_ATTRIBUTE

Use DEFINE_SHOW_ATTRIBUTE macro to simplify the code.

Signed-off-by: Yangtao Li <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: use rb_entry()

To make the code clearer, use rb_entry() instead of container_of() to
deal with rbtree.

Signed-off-by: Geliang Tang <[email protected]>
Signed-off-by: Mark Brown <broonie

regmap: use rb_entry()

To make the code clearer, use rb_entry() instead of container_of() to
deal with rbtree.

Signed-off-by: Geliang Tang <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Avoid overlapping nodes

When searching for a suitable node that should be used for inserting a new
register, which does not fall within the range of any existing node, we not
only lo

regmap: rbtree: Avoid overlapping nodes

When searching for a suitable node that should be used for inserting a new
register, which does not fall within the range of any existing node, we not
only looks for nodes which are directly adjacent to the new register, but
for nodes within a certain proximity. This is done to avoid creating lots
of small nodes with just a few registers spacing in between, which would
increase memory usage as well as tree traversal time.

This means there might be multiple node candidates which fall within the
proximity range of the new register. If we choose the first node we
encounter, under certain register insertion patterns it is possible to end
up with overlapping ranges. This will break order in the rbtree and can
cause the cached register value to become corrupted.

E.g. take the simplified example where the proximity range is 2 and the
register insertion sequence is 1, 4, 2, 3, 5.
* Insert of register 1 creates a new node, this is the root of the rbtree
* Insert of register 4 creates a new node, which is inserted to the right
of the root.
* Insert of register 2 gets inserted to the first node
* Insert of register 3 gets inserted to the first node
* Insert of register 5 also gets inserted into the first node since
this is the first node encountered and it is within the proximity range.
Now there are two overlapping nodes.

To avoid this always choose the node that is closest to the new register.
This will ensure that nodes will not overlap. The tree traversal is still
done as a binary search, we just don't stop at the first node found. So the
complexity of the algorithm stays within the same order.

Ideally if a new register is in the range of two adjacent blocks those
blocks should be merged, but that is a much more invasive change and left
for later.

The issue was initially introduced in commit 472fdec7380c ("regmap: rbtree:
Reduce number of nodes, take 2"), but became much more exposed by commit
6399aea629b0 ("regmap: rbtree: When adding a reg do a bsearch for target
node") which changed the order in which nodes are looked-up.

Fixes: 6399aea629b0 ("regmap: rbtree: When adding a reg do a bsearch for target node")
Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: replace kmalloc with kmalloc_array

Replace kmalloc with specialized function kmalloc_array when the size
is a multiplication of : number * size

Signed-off-by: lixiubo <[email protected]

regmap: replace kmalloc with kmalloc_array

Replace kmalloc with specialized function kmalloc_array when the size
is a multiplication of : number * size

Signed-off-by: lixiubo <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: replace kzalloc with kcalloc

Replace kzalloc with specialized function kcalloc when the size is
a multiplication of : number * sizeof

Signed-off-by: lixiubo <[email protected]>
S

regmap: replace kzalloc with kcalloc

Replace kzalloc with specialized function kcalloc when the size is
a multiplication of : number * sizeof

Signed-off-by: lixiubo <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: When adding a reg do a bsearch for target node

A binary search is much more efficient rather than iterating
over the rbtree in ascending order which the current code is
doing.

Durin

regmap: rbtree: When adding a reg do a bsearch for target node

A binary search is much more efficient rather than iterating
over the rbtree in ascending order which the current code is
doing.

During initialisation the reg defaults are written to the
cache in a large chunk and these are always sorted in the
ascending order so for this situation ideally we should have
iterated the rbtree in descending order.

But at runtime the drivers may write into the cache in any
random order so this patch selects to use a bsearch to give
an optimal runtime performance and also at initialisation
time when reg defaults are written the performance of binary
search would be much better than iterating in ascending order
which the current code was doing.

Signed-off-by: Nikesh Oswal <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: regcache-rbtree: Clean new present bits on present bitmap resize

When inserting a new register into a block, the present bit map size is
increased using krealloc. krealloc does not clear the

regmap: regcache-rbtree: Clean new present bits on present bitmap resize

When inserting a new register into a block, the present bit map size is
increased using krealloc. krealloc does not clear the additionally
allocated memory, leaving it filled with random values. Result is that
some registers are considered cached even though this is not the case.

Fix the problem by clearing the additionally allocated memory. Also, if
the bitmap size does not increase, do not reallocate the bitmap at all
to reduce overhead.

Fixes: 3f4ff561bc88 ("regmap: rbtree: Make cache_present bitmap per node")
Signed-off-by: Guenter Roeck <[email protected]>
Signed-off-by: Mark Brown <[email protected]>
Cc: [email protected]

show more ...

regmap: regcache-rbtree: Fix present bitmap resize

When inserting a new register into a block at the lower end the present
bitmap is currently shifted into the wrong direction. The effect of this is

regmap: regcache-rbtree: Fix present bitmap resize

When inserting a new register into a block at the lower end the present
bitmap is currently shifted into the wrong direction. The effect of this is
that the bitmap becomes corrupted and registers which are present might be
reported as not present and vice versa.

Fix this by shifting left rather than right.

Fixes: 472fdec7380c("regmap: rbtree: Reduce number of nodes, take 2")
Reported-by: Daniel Baluta <[email protected]>
Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>
Cc: [email protected]

show more ...

regmap: cache: Sort include headers alphabetically

If the inlcude headers aren't sorted alphabetically, then the
logical choice is to append new ones, however that creates a
lot of potential for con

regmap: cache: Sort include headers alphabetically

If the inlcude headers aren't sorted alphabetically, then the
logical choice is to append new ones, however that creates a
lot of potential for conflicts or duplicates because every change
will then add new includes in the same location.

Signed-off-by: Xiubo Li <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: Fix regcache debugfs initialization

Commit 6cfec04bcc05 ("regmap: Separate regmap dev initialization") moved the
regmap debugfs initialization after regcache initialization. This means
that

regmap: Fix regcache debugfs initialization

Commit 6cfec04bcc05 ("regmap: Separate regmap dev initialization") moved the
regmap debugfs initialization after regcache initialization. This means
that the regmap debugfs directory is not created yet when the cache
initialization runs and so any debugfs files registered by the regcache are
created in the debugfs root directory rather than the debugfs directory of
the regmap instance. Fix this by adding a separate callback for the
regcache debugfs initialization which will be called after the parent
debugfs entry has been created.

Fixes: 6cfec04bcc05 (regmap: Separate regmap dev initialization)
Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>
Cc: [email protected]

show more ...

regmap: rbtree: improve 64bits memory alignment

Change regcache_rbtree_node strcuture fields order to align the pointers on
64bits architectures.

Signed-off-by: Jean-Christophe PINCE <jean-christop

regmap: rbtree: improve 64bits memory alignment

Change regcache_rbtree_node strcuture fields order to align the pointers on
64bits architectures.

Signed-off-by: Jean-Christophe PINCE <[email protected]>
Signed-off-by: David Cohen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Make cache_present bitmap per node

With devices which have a dense and small register map but placed at a large
offset the global cache_present bitmap imposes a huge memory overhead.

regmap: rbtree: Make cache_present bitmap per node

With devices which have a dense and small register map but placed at a large
offset the global cache_present bitmap imposes a huge memory overhead. Making
the cache_present per rbtree node avoids the issue and easily reduces the memory
footprint by a factor of ten. For devices with a more sparse map or without a
large base register offset the memory usage might increase slightly by a few
bytes, but not significantly. E.g. for a device which has ~50 registers at
offset 0x4000 the memory footprint of the register cache goes down form 2496
bytes to 175 bytes.

Moving the bitmap to a per node basis means that the handling of the bitmap is
now cache implementation specific and can no longer be managed by the core. The
regcache_sync_block() function is extended by a additional parameter so that the
cache implementation can tell the core which registers in the block are set and
which are not. The parameter is optional and if NULL the core assumes that all
registers are set. The rbtree cache also needs to implement its own drop
callback instead of relying on the core to handle this.

Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Reduce number of nodes, take 2

Support for reducing the number of nodes and memory consumption of the rbtree
cache by allowing for small unused holes in the node's register cache blo

regmap: rbtree: Reduce number of nodes, take 2

Support for reducing the number of nodes and memory consumption of the rbtree
cache by allowing for small unused holes in the node's register cache block was
initially added in commit 0c7ed856 ("regmap: Cut down on the average # of nodes
in the rbtree cache"). But the commit had problems and so its effect was
reverted again in commit 4e67fb5 ("regmap: rbtree: Fix overlapping rbnodes.").
This patch brings the feature back of reducing the average number of nodes,
which will speedup node look-up, while at the same time also reducing the memory
usage of the rbtree cache. This patch takes a slightly different approach than
the original patch though. It modifies the adjacent node look-up to not only
consider nodes that are just one to the left or the right of the register but
any node that falls in a certain range around the register. The range is
calculated based on how much memory it would take to allocate a new node
compared to how much memory it takes adding a set of unused registers to an
existing node. E.g. if a node takes up 24 bytes and each register in a block
uses 1 byte the range will be from the register address - 24 to the register
address + 24. If we find a node that falls within this range it is cheaper or as
expensive to add the register to the existing node and have a couple of unused
registers in the node's cache compared to allocating a new node.

Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Simplify adjacent node look-up

A register which is adjacent to a node will either be left to the first
register or right to the last register. It will not be within the node's range,

regmap: rbtree: Simplify adjacent node look-up

A register which is adjacent to a node will either be left to the first
register or right to the last register. It will not be within the node's range,
so there is no point in checking for each register cached by the node whether
the new register is next to it. It is sufficient to check whether the register
comes before the first register or after the last register of the node.

Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regcache-rbtree: Fix reg_stride != 1

There are a couple of calculations, which convert between register addresses and
block indices, in regcache_rbtree_sync() and regcache_rbtree_node_alloc() which

regcache-rbtree: Fix reg_stride != 1

There are a couple of calculations, which convert between register addresses and
block indices, in regcache_rbtree_sync() and regcache_rbtree_node_alloc() which
assume that reg_stride is 1. This will break the rb cache for configurations
which do not use a reg_stride of 1.

Also rename 'base' in regcache_rbtree_sync() to 'start' to avoid confusion with
'base_reg'.

Signed-off-by: Lars-Peter Clausen <[email protected]>
Signed-off-by: Mark Brown <[email protected]>

show more ...

regmap: rbtree: Fix overlapping rbnodes.

Avoid overlapping register regions by making the initial blklen of a new
node 1. If a register write occurs to a yet uncached register, that is
lower than bu

regmap: rbtree: Fix overlapping rbnodes.

Avoid overlapping register regions by making the initial blklen of a new
node 1. If a register write occurs to a yet uncached register, that is
lower than but near an existing node's base_reg, a new node is created
and it's blklen is set to an arbitrary value (sizeof(*rbnode)). That may
cause this node to overlap with another node. Those nodes should be merged,
but this merge doesn't happen yet, so this patch at least makes the initial
blklen small enough to avoid hitting the wrong node, which may otherwise
lead to severe breakage.

Signed-off-by: David Jander <[email protected]>
Signed-off-by: Mark Brown <[email protected]>
Cc: [email protected]

show more ...