kernel/drivers/md/persistent-data/dm-btree.h, branch linux-6.9.y

dm: add missing blank line after declarations/fix those

2023-02-14T19:23:07Z

Signed-off-by: Heinz Mauelshagen Signed-off-by: Mike Snitzer

dm: change "unsigned" to "unsigned int"

2023-02-14T19:23:06Z

Signed-off-by: Heinz Mauelshagen Signed-off-by: Mike Snitzer

dm: add missing SPDX-License-Indentifiers

2023-02-14T19:23:06Z

'GPL-2.0-only' is used instead of 'GPL-2.0' because SPDX has deprecated its use. Suggested-by: John Wiele Signed-off-by: Heinz Mauelshagen Signed-off-by: Mike Snitzer

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

2021-06-04T16:07:22Z

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

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

2017-02-16T18:12:50Z

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

dm btree: introduce cursor api

2016-09-22T15:15:04Z

This uses prefetching to speed up iteration through a btree. Signed-off-by: Joe Thornber Signed-off-by: Mike Snitzer

dm thin metadata: fix bug in dm_thin_remove_range()

2015-12-02T18:26:49Z

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 Signed-off-by: Mike Snitzer Cc: stable@vger.kernel.org # 4.1+

dm btree: add dm_btree_remove_leaves()

2015-06-11T21:13:03Z

Removes a range of leaf values from the tree. Signed-off-by: Joe Thornber Signed-off-by: Mike Snitzer

dm btree: add dm_btree_find_lowest_key

2014-01-09T21:29:17Z

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 persistent data: add btree_walk

2013-03-01T22:45:50Z

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