linux-stable.git/drivers/md/persistent-data/dm-btree-remove.c, branch linux-3.2.y

dm btree remove: fix a bug when rebalancing nodes after removal

2015-11-17T15:54:45+00:00

commit 2871c69e025e8bc507651d5a9cf81a8a7da9d24b upstream.

Commit 4c7e309340ff ("dm btree remove: fix bug in redistribute3") wasn't
a complete fix for redistribute3().

The redistribute3 function takes 3 btree nodes and shares out the entries
evenly between them.  If the three nodes in total contained
(MAX_ENTRIES * 3) - 1 entries between them then this was erroneously getting
rebalanced as (MAX_ENTRIES - 1) on the left and right, and (MAX_ENTRIES + 1) in
the center.

Fix this issue by being more careful about calculating the target number
of entries for the left and right nodes.

Unit tested in userspace using this program:
https://github.com/jthornber/redistribute3-test/blob/master/redistribute3_t.c

Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
Signed-off-by: Ben Hutchings

dm btree: add ref counting ops for the leaves of top level btrees

2015-10-13T02:46:03+00:00

commit b0dc3c8bc157c60b1d470163882be8c13e1950af upstream.

When using nested btrees, the top leaves of the top levels contain
block addresses for the root of the next tree down.  If we shadow a
shared leaf node the leaf values (sub tree roots) should be incremented
accordingly.

This is only an issue if there is metadata sharing in the top levels.
Which only occurs if metadata snapshots are being used (as is possible
with dm-thinp).  And could result in a block from the thinp metadata
snap being reused early, thus corrupting the thinp metadata snap.

Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
[bwh: Backported to 3.2:
 - Drop change to remove_one()
 - Remove const pointer qualifications]
Signed-off-by: Ben Hutchings

dm btree remove: fix bug in redistribute3

2015-08-12T14:33:19+00:00

commit 4c7e309340ff85072e96f529582d159002c36734 upstream.

redistribute3() shares entries out across 3 nodes.  Some entries were
being moved the wrong way, breaking the ordering.  This manifested as a
BUG() in dm-btree-remove.c:shift() when entries were removed from the
btree.

For additional context see:
https://www.redhat.com/archives/dm-devel/2015-May/msg00113.html

Signed-off-by: Dennis Yang 
Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
Signed-off-by: Ben Hutchings

dm thin: fix discard corruption

2013-03-27T02:41:19+00:00

commit f046f89a99ccfd9408b94c653374ff3065c7edb3 upstream.

Fix a bug in dm_btree_remove that could leave leaf values with incorrect
reference counts.  The effect of this was that removal of a shared block
could result in the space maps thinking the block was no longer used.
More concretely, if you have a thin device and a snapshot of it, sending
a discard to a shared region of the thin could corrupt the snapshot.

Thinp uses a 2-level nested btree to store it's mappings.  This first
level is indexed by thin device, and the second level by logical
block.

Often when we're removing an entry in this mapping tree we need to
rebalance nodes, which can involve shadowing them, possibly creating a
copy if the block is shared.  If we do create a copy then children of
that node need to have their reference counts incremented.  In this
way reference counts percolate down the tree as shared trees diverge.

The rebalance functions were incrementing the children at the
appropriate time, but they were always assuming the children were
internal nodes.  This meant the leaf values (in our case packed
block/flags entries) were not being incremented.

Signed-off-by: Joe Thornber 
Signed-off-by: Alasdair G Kergon 
[bwh: Backported to 3.2: bump target version numbers from 1.0.1 to 1.0.2]
Signed-off-by: Ben Hutchings

dm persistent data: rename node to btree_node

2013-01-03T03:33:46+00:00

commit 550929faf89e2e2cdb3e9945ea87d383989274cf upstream.

This patch fixes a compilation failure on sparc32 by renaming struct node.

struct node is already defined in include/linux/node.h. On sparc32, it
happens to be included through other dependencies and persistent-data
doesn't compile because of conflicting declarations.

Signed-off-by: Mikulas Patocka 
Signed-off-by: Alasdair G Kergon 
[bwh: Backported to 3.2: adjust context]
Signed-off-by: Ben Hutchings

dm persistent data: fix btree rebalancing after remove

2012-04-02T16:53:05+00:00

commit b0988900bae9ecf968a8a8d086a9eec671a9517a upstream.

When we remove an entry from a node we sometimes rebalance with it's
two neighbours.  This wasn't being done correctly; in some cases
entries have to move all the way from the right neighbour to the left
neighbour, or vice versa.  This patch pretty much re-writes the
balancing code to fix it.

This code is barely used currently; only when you delete a thin
device, and then only if you have hundreds of them in the same pool.
Once we have discard support, which removes mappings, this will be used
much more heavily.

Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
Signed-off-by: Alasdair G Kergon 
Signed-off-by: Greg Kroah-Hartman

drivers/md: change module.h -> export.h in persistent-data/dm-*

2011-11-07T18:29:09+00:00

For the files which are not themselves modular, we can change
them to include only the smaller export.h since all they are
doing is looking for EXPORT_SYMBOL.

Reported-by: Stephen Rothwell 
Signed-off-by: Paul Gortmaker 
Signed-off-by: Linus Torvalds

dm: add persistent data library

2011-10-31T20:19:11+00:00

The persistent-data library offers a re-usable framework for the storage
and management of on-disk metadata in device-mapper targets.

It's used by the thin-provisioning target in the next patch and in an
upcoming hierarchical storage target.

For further information, please read
Documentation/device-mapper/persistent-data.txt

Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
Signed-off-by: Alasdair G Kergon