linux-toradex.git/drivers/md/persistent-data/dm-btree.c, branch v3.18-rc5

dm btree: fix a recursion depth bug in btree walking code

2014-11-10T20:23:58+00:00

The walk code was using a 'ro_spine' to hold it's locked btree nodes.
But this data structure is designed for the rolling lock scheme, and
as such automatically unlocks blocks that are two steps up the call
chain.  This is not suitable for the simple recursive walk algorithm,
which retraces its steps.

This code is only used by the persistent array code, which in turn is
only used by dm-cache.  In order to trigger it you need to have a
mapping tree that is more than 2 levels deep; which equates to 8-16
million cache blocks.  For instance a 4T ssd with a very small block
size of 32k only just triggers this bug.

The fix just places the locked blocks on the stack, and stops using
the ro_spine altogether.

Signed-off-by: Joe Thornber 
Signed-off-by: Mike Snitzer 
Cc: stable@vger.kernel.org

dm btree: add dm_btree_find_lowest_key

2014-01-09T21:29:17+00:00

dm_btree_find_lowest_key is the reciprocal of dm_btree_find_highest_key.
Factor out common code for dm_btree_find_{highest,lowest}_key.

dm_btree_find_lowest_key is needed for an upcoming DM target, as such it
is best to get this interface in place.

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

dm btree: prefetch child nodes when walking tree for a dm_btree_del

2013-08-23T13:02:14+00:00

dm-btree now takes advantage of dm-bufio's ability to prefetch data via
dm_bm_prefetch().  Prior to this change many btree node visits were
causing a synchronous read.

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

dm btree: use pop_frame in dm_btree_del to cleanup code

2013-08-23T13:02:14+00:00

Remove a visited leaf straight away from the stack, rather than
marking all it's children as visited and letting it get removed on the
next iteration.  May also offer a micro optimisation in dm_btree_del.

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

dm persistent data: add btree_walk

2013-03-01T22:45:50+00:00

Add dm_btree_walk to iterate through the contents of a btree.
This will be used by the dm cache target.

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

dm persistent data: fix nested btree deletion

2012-12-21T20:23:32+00:00

When deleting nested btrees, the code forgets to delete the innermost
btree.  The thin-metadata code serendipitously compensates for this by
claiming there is one extra layer in the tree.

This patch corrects both problems.

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

dm persistent data: rename node to btree_node

2012-12-21T20:23:30+00:00

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 
Cc: stable@vger.kernel.org
Signed-off-by: Alasdair G Kergon

dm persistent data: remove redundant value_size arg from value_ptr

2012-03-28T17:41:25+00:00

Now that the value_size is held within every node of the btrees we can
remove this argument from value_ptr().

For the last few months a BUG_ON has been checking this argument is
the same as that held in the node.  No issues were reported.  So this
is a safe change.

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

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