dm: add missing blank line after declarations/fix those

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: avoid useless 'else' after 'break' or return'

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: adjust EXPORT_SYMBOL() to follow functions immediately

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: add missing empty lines

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: correct block comments format.

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: address indent/space issues

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: change "unsigned" to "unsigned int"

Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm: add missing SPDX-License-Indentifiers

'GPL-2.0-only' is used instead of 'GPL-2.0' because SPDX has
deprecated its use.

Suggested-by: John Wiele <[email protected]>
Signed-off-by: Heinz Mauelsha

dm: add missing SPDX-License-Indentifiers

'GPL-2.0-only' is used instead of 'GPL-2.0' because SPDX has
deprecated its use.

Suggested-by: John Wiele <[email protected]>
Signed-off-by: Heinz Mauelshagen <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: add a defensive bounds check to insert_at()

Corrupt metadata could trigger an out of bounds write.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <snitzer@redhat

dm btree: add a defensive bounds check to insert_at()

Corrupt metadata could trigger an out of bounds write.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm space maps: improve performance with inc/dec on ranges of blocks

When we break sharing on btree nodes we typically need to increment
the reference counts to every value held in the node. This ca

dm space maps: improve performance with inc/dec on ranges of blocks

When we break sharing on btree nodes we typically need to increment
the reference counts to every value held in the node. This can
cause a lot of repeated calls to the space maps. Fix this by changing
the interface to the space map inc/dec methods to take ranges of
adjacent blocks to be operated on.

For installations that are using a lot of snapshots this will reduce
cpu overhead of fundamental operations such as provisioning a new block,
or deleting a snapshot, by as much as 10 times.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: improve btree residency

This commit improves the residency of btrees built in the metadata for
dm-thin and dm-cache.

When inserting a new entry into a full btree node the current code
spl

dm btree: improve btree residency

This commit improves the residency of btrees built in the metadata for
dm-thin and dm-cache.

When inserting a new entry into a full btree node the current code
splits the node into two. This can result in very many half full nodes,
particularly if the insertions are occurring in an ascending order (as
happens in dm-thin with large writes).

With this commit, when we insert into a full node we first try and move
some entries to a neighbouring node that has space, failing that it
tries to split two neighbouring nodes into three.

Results are given below. 'Residency' is how full nodes are on average
as a percentage. Average instruction counts for the operations
are given to show the extra processing has little overhead.

+--------------------------+--------------------------+
| Before | After |
+------------+-----------+-----------+--------------+-----------+--------------+
| Test | Phase | Residency | Instructions | Residency | Instructions |
+------------+-----------+-----------+--------------+-----------+--------------+
| Ascending | insert | 50 | 1876 | 96 | 1930 |
| | overwrite | 50 | 1789 | 96 | 1746 |
| | lookup | 50 | 778 | 96 | 778 |
| Descending | insert | 50 | 3024 | 96 | 3181 |
| | overwrite | 50 | 1789 | 96 | 1746 |
| | lookup | 50 | 778 | 96 | 778 |
| Random | insert | 68 | 3800 | 84 | 3736 |
| | overwrite | 68 | 4254 | 84 | 3911 |
| | lookup | 68 | 779 | 84 | 779 |
| Runs | insert | 63 | 2546 | 82 | 2815 |
| | overwrite | 63 | 2013 | 82 | 1986 |
| | lookup | 63 | 778 | 82 | 779 |
+------------+-----------+-----------+--------------+-----------+--------------+

Ascending - keys are inserted in ascending order.
Descending - keys are inserted in descending order.
Random - keys are inserted in random order.
Runs - keys are split into ascending runs of ~20 length. Then
the runs are shuffled.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Colin Ian King <[email protected]> # contains_key() fix
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm thin metadata: Remove unused local variable when create thin and snap

The local variable disk details is not used during the creating of thin & snap
devices. Remove them from dm-thin-metadata, an

dm thin metadata: Remove unused local variable when create thin and snap

The local variable disk details is not used during the creating of thin & snap
devices. Remove them from dm-thin-metadata, and add pointer validity check for
pointer value in btree_lookup_raw. Skip memory copy when the caller doesn't need
the value.

Signed-off-by: Huaisheng Ye <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: fix order of block initialization in btree_split_beneath

When btree_split_beneath() splits a node to two new children, it will
allocate two blocks: left and right. If right block's alloca

dm btree: fix order of block initialization in btree_split_beneath

When btree_split_beneath() splits a node to two new children, it will
allocate two blocks: left and right. If right block's allocation
failed, the left block will be unlocked and marked dirty. If this
happened, the left block'ss content is zero, because it wasn't
initialized with the btree struct before the attempot to allocate the
right block. Upon return, when flushing the left block to disk, the
validator will fail when check this block. Then a BUG_ON is raised.

Fix this by completely initializing the left block before allocating and
initializing the right block.

Fixes: 4dcb8b57df359 ("dm btree: fix leak of bufio-backed block in btree_split_beneath error path")
Cc: [email protected]
Signed-off-by: ZhangXiaoxu <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: fix serious bug in btree_split_beneath()

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

dm btree: fix serious bug in btree_split_beneath()

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.

Cc: [email protected]
Reported-by: Monty Pavel <[email protected]>
Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: fix for dm_btree_find_lowest_key()

dm_btree_find_lowest_key() is giving incorrect results. find_key()
traverses the btree correctly for finding the highest key, but there is
an error in t

dm btree: fix for dm_btree_find_lowest_key()

dm_btree_find_lowest_key() is giving incorrect results. find_key()
traverses the btree correctly for finding the highest key, but there is
an error in the way it traverses the btree for retrieving the lowest
key. dm_btree_find_lowest_key() fetches the first key of the rightmost
block of the btree instead of fetching the first key from the leftmost
block.

Fix this by conditionally passing the correct parameter to value64()
based on the @find_highest flag.

Cc: [email protected]
Signed-off-by: Erez Zadok <[email protected]>
Signed-off-by: Vinothkumar Raja <[email protected]>
Signed-off-by: Nidhi Panpalia <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm persistent data: add cursor skip functions to the cursor APIs

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm btree: use GFP_NOFS in dm_btree_del()

dm_btree_del() is called from an ioctl so don't recurse into FS.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]

dm btree: use GFP_NOFS in dm_btree_del()

dm_btree_del() is called from an ioctl so don't recurse into FS.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: introduce cursor api

This uses prefetching to speed up iteration through a btree.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

dm btree: fix a bug in dm_btree_find_next_single()

dm_btree_find_next_single() can short-circuit the search for a block
with a return of -ENODATA if all entries are higher than the search key
passed

dm btree: fix a bug in dm_btree_find_next_single()

dm_btree_find_next_single() can short-circuit the search for a block
with a return of -ENODATA if all entries are higher than the search key
passed to lower_bound().

This hasn't been a problem because of the way the btree has been used by
DM thinp. But it must be fixed now in preparation for fixing the race
in DM thinp's handling of simultaneous block discard vs allocation.
Otherwise, once that fix is in place, some of the blocks in a discard
would not be unmapped as expected.

Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

dm btree: factor out need_insert() helper

Eliminates code duplication within insert().

Signed-off-by: Mike Snitzer <[email protected]>

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

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

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

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 <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>
Cc: [email protected]

show more ...

dm thin metadata: fix bug in dm_thin_remove_range()

dm_btree_remove_leaves() only unmaps a contiguous region so we need a
loop, in __remove_range(), to handle ranges that contain multiple
regions.

dm thin metadata: fix bug in dm_thin_remove_range()

dm_btree_remove_leaves() only unmaps a contiguous region so we need a
loop, in __remove_range(), to handle ranges that contain multiple
regions.

A new btree function, dm_btree_lookup_next(), is introduced which is
more efficiently able to skip over regions of the thin device which
aren't mapped. __remove_range() uses dm_btree_lookup_next() for each
iteration of __remove_range()'s loop.

Also, improve description of dm_btree_remove_leaves().

Fixes: 6550f075 ("dm thin metadata: add dm_thin_remove_range()")
Signed-off-by: Joe Thornber <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>
Cc: [email protected] # 4.1+

show more ...

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

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

Fix this by releas

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

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 <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>
Cc: [email protected]

show more ...

dm persistent data: eliminate unnecessary return values

dm_bm_unlock and dm_tm_unlock return an integer value but the returned
value is always 0. The calling code sometimes checks the return value

dm persistent data: eliminate unnecessary return values

dm_bm_unlock and dm_tm_unlock return an integer value but the returned
value is always 0. The calling code sometimes checks the return value
and sometimes doesn't.

Eliminate these unnecessary return values and also the checks for them.

Signed-off-by: Mikulas Patocka <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

show more ...

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

btree_split_beneath()'s error path had an outstanding FIXME that speaks
directly to the potential for _not_ cleaning up a p

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

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 <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>
Acked-by: Joe Thornber <[email protected]>
Cc: [email protected]

show more ...