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 <gregkh@linuxfoundation.org>
Signed-off-by: Mark Brown <broonie@kernel.org>

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 <dp@opensource.wolfsonmicro.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Mathieu Malaterre <malat@debian.org>
Signed-off-by: Mark Brown <broonie@kernel.org>

Use DEFINE_SHOW_ATTRIBUTE macro to simplify the code.

Signed-off-by: Yangtao Li <tiny.windzz@gmail.com>
Signed-off-by: Mark Brown <broonie@kernel.org>

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

Signed-off-by: Geliang Tang <geliangtang@gmail.com>
Signed-off-by: Mark Brown <broonie@kernel.org>

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 <lars@metafoo.de>
Signed-off-by: Mark Brown <broonie@kernel.org>

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

Signed-off-by: lixiubo <lixiubo@cmss.chinamobile.com>
Signed-off-by: Mark Brown <broonie@kernel.org>

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

Signed-off-by: lixiubo <lixiubo@cmss.chinamobile.com>
Signed-off-by: Mark Brown <broonie@kernel.org>

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 <Nikesh.Oswal@wolfsonmicro.com>
Signed-off-by: Mark Brown <broonie@kernel.org>

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 <linux@roeck-us.net>
Signed-off-by: Mark Brown <broonie@kernel.org>
Cc: stable@vger.kernel.org