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

dm btree: fix serious bug in btree_split_beneath()

2018-03-03T15:51:00+00:00

commit bc68d0a43560e950850fc69b58f0f8254b28f6d6 upstream.

When inserting a new key/value pair into a btree we walk down the spine of
btree nodes performing the following 2 operations:

  i) space for a new entry
  ii) adjusting the first key entry if the new key is lower than any in the node.

If the _root_ node is full, the function btree_split_beneath() allocates 2 new
nodes, and redistibutes the root nodes entries between them.  The root node is
left with 2 entries corresponding to the 2 new nodes.

btree_split_beneath() then adjusts the spine to point to one of the two new
children.  This means the first key is never adjusted if the new key was lower,
ie. operation (ii) gets missed out.  This can result in the new key being
'lost' for a period; until another low valued key is inserted that will uncover
it.

This is a serious bug, and quite hard to make trigger in normal use.  A
reproducing test case ("thin create devices-in-reverse-order") is
available as part of the thin-provision-tools project:
  https://github.com/jthornber/thin-provisioning-tools/blob/master/functional-tests/device-mapper/dm-tests.scm#L593

Fix the issue by changing btree_split_beneath() so it no longer adjusts
the spine.  Instead it unlocks both the new nodes, and lets the main
loop in btree_insert_raw() relock the appropriate one and make any
neccessary adjustments.

Reported-by: Monty Pavel 
Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
Signed-off-by: Ben Hutchings

dm btree: fix bufio buffer leaks in dm_btree_del() error path

2015-12-30T02:26:01+00:00

commit ed8b45a3679eb49069b094c0711b30833f27c734 upstream.

If dm_btree_del()'s call to push_frame() fails, e.g. due to
btree_node_validator finding invalid metadata, the dm_btree_del() error
path must unlock all frames (which have active dm-bufio buffers) that
were pushed onto the del_stack.

Otherwise, dm_bufio_client_destroy() will BUG_ON() because dm-bufio
buffers have leaked, e.g.:
  device-mapper: bufio: leaked buffer 3, hold count 1, list 0

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

dm btree: fix leak of bufio-backed block in btree_split_sibling error path

2015-12-30T02:25:59+00:00

commit 30ce6e1cc5a0f781d60227e9096c86e188d2c2bd upstream.

The block allocated at the start of btree_split_sibling() is never
released if later insert_at() fails.

Fix this by releasing the previously allocated bufio block using
unlock_block().

Reported-by: Mikulas Patocka 
Signed-off-by: Mike Snitzer 
Signed-off-by: Ben Hutchings

dm btree: fix leak of bufio-backed block in btree_split_beneath error path

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

commit 4dcb8b57df3593dcb20481d9d6cf79d1dc1534be upstream.

btree_split_beneath()'s error path had an outstanding FIXME that speaks
directly to the potential for _not_ cleaning up a previously allocated
bufio-backed block.

Fix this by releasing the previously allocated bufio block using
unlock_block().

Reported-by: Mikulas Patocka 
Signed-off-by: Mike Snitzer 
Acked-by: Joe Thornber 
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: silence lockdep lock inversion in dm_btree_del()

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

commit 1c7518794a3647eb345d59ee52844e8a40405198 upstream.

Allocate memory using GFP_NOIO when deleting a btree.  dm_btree_del()
can be called via an ioctl and we don't want to recurse into the FS or
block layer.

Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
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

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