Skip to content

L
linux
Switch branch/tag
  1. 04 Aug, 2016 1 commit
    • Lars-Peter Clausen's avatar
      regmap: rbtree: Avoid overlapping nodes · 1bc8da4e
      Lars-Peter Clausen authored 
      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 472fdec7 ("regmap: rbtree:
Reduce number of nodes, take 2"), but became much more exposed by commit
6399aea6 ("regmap: rbtree: When adding a reg do a bsearch for target
node") which changed the order in which nodes are looked-up.

Fixes: 6399aea6 ("regmap: rbtree: When adding a reg do a bsearch for target node")
Signed-off-by: default avatarLars-Peter Clausen <lars@metafoo.de>
Signed-off-by: default avatarMark Brown <broonie@kernel.org>
      1bc8da4e
  3. 15 Jul, 2016 2 commits
  5. 11 Jul, 2016 2 commits
    • Linus Torvalds's avatar
      Linux 4.7-rc7 · 92d21ac7
      Linus Torvalds authored
      92d21ac7
    • Hugh Dickins's avatar
      tmpfs: fix regression hang in fallocate undo · 7f556567
      Hugh Dickins authored 
      The well-spotted fallocate undo fix is good in most cases, but not when
fallocate failed on the very first page.  index 0 then passes lend -1
to shmem_undo_range(), and that has two bad effects: (a) that it will
undo every fallocation throughout the file, unrestricted by the current
range; but more importantly (b) it can cause the undo to hang, because
lend -1 is treated as truncation, which makes it keep on retrying until
every page has gone, but those already fully instantiated will never go
away.  Big thank you to xfstests generic/269 which demonstrates this.

Fixes: b9b4bb26 ("tmpfs: don't undo fallocate past its last page")
Cc: stable@vger.kernel.org
Signed-off-by: default avatarHugh Dickins <hughd@google.com>
Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      7f556567
  7. 10 Jul, 2016 1 commit
  9. 09 Jul, 2016 1 commit
  11. 08 Jul, 2016 19 commits
  13. 07 Jul, 2016 11 commits
  15. 06 Jul, 2016 3 commits
GitLab Nexedi Edition | About GitLab | About Nexedi | 沪ICP备2021021310号-2 | 沪ICP备2021021310号-7