[PATCH 0/3] reiser4: precise discard: fixes on top of everything

[PATCH 0/3] reiser4: precise discard: fixes on top of everything

[Ivan Shapovalov]

Here we fix two bugs in the precise discard implementation.
The first one is handling of "nearby" tail and head paddings which are parts
of the same disk block. Our block checking function is not idempotent, and
repeatedly calling it on the same block results in a false-negative. The fix is
to remember the last checked range (the tail padding) of an extent, and then
use this information during checking the head padding of the next extent.
Information about preceding blocks is never needed.

The second one is handling of discard extents at the end of the partition: we
must avoid checking blocks outside of the partition. The similar check already
exists for the first erase unit in the partition.

Ivan Shapovalov (3):
  reiser4: discard: signify non-idempotence of check_free_blocks() by changing its name.
  reiser4: discard: avoid checking same blocks multiple times.
  reiser4: discard: handle incomplete erase units at the end of a partition.

 fs/reiser4/discard.c | 194 +++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 165 insertions(+), 29 deletions(-)

-- 
2.3.0

[PATCH 1/3] reiser4: discard: signify non-idempotence of check_free_blocks() by changing its name.

[Ivan Shapovalov]

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/discard.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
index b4cd236..a615b7d 100644
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -185,8 +185,13 @@ static inline struct list_head *get_next_at(struct list_head *pos,
 	return pos->next == head ? NULL : pos->next;
 }
 
-static inline int check_free_blocks(const reiser4_block_nr start,
-				    const reiser4_block_nr len)
+/*
+ * Check if a given block range is free (clean) and allocate it.
+ *
+ * NOTE: this operation is not idempotent.
+ */
+static inline int try_allocate_blocks(const reiser4_block_nr start,
+				      const reiser4_block_nr len)
 {
 	/*
 	 * NOTE: we do not use BA_PERMANENT in out allocations
@@ -321,7 +326,7 @@ static int discard_precise_extents(struct list_head *head)
 		}
 		else if (p_start >= p_headp /* discard unit is complete */ &&
 			 !headp_is_known_dirty &&
-			 check_free_blocks(start - headp, headp)) {
+			 try_allocate_blocks(start - headp, headp)) {
 			/*
 			 * pad the head
 			 */
@@ -379,7 +384,7 @@ static int discard_precise_extents(struct list_head *head)
 				 * check space between the extents;
 				 * if it is free, then allocate it
 				 */
-				if (check_free_blocks(end, next_start - end)) {
+				if (try_allocate_blocks(end, next_start - end)) {
 					/*
 					 * jump to the glued extent
 					 */
@@ -422,7 +427,7 @@ static int discard_precise_extents(struct list_head *head)
 				 */
 				if (tailp == 0)
 					break;
-				else if (check_free_blocks(end, tailp)) {
+				else if (try_allocate_blocks(end, tailp)) {
 					/*
 					 * tail padding is clean,
 					 * pad the tail
-- 
2.3.0

[PATCH 2/3] reiser4: discard: avoid checking same blocks multiple times.

[Ivan Shapovalov]

It was previously possible for an extent's tail padding and next extent's head
padding to overlap in terms of occupied disk blocks.

In this case the head padding check would yield a false negative because blocks
would appear already allocated, while in fact they would have been previously
allocated by us.

Solve this by saving last checked tail padding and a bit of case analysis.

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/discard.c | 182 +++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 156 insertions(+), 26 deletions(-)

diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
index a615b7d..10c1707 100644
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -272,9 +272,57 @@ static int discard_precise_extents(struct list_head *head)
 	int d_off;
 	struct list_head *pos;
 	struct super_block *sb = reiser4_get_current_sb();
-	int headp_is_known_dirty = 0;
 	int blkbits = sb->s_blocksize_bits;
 
+	/* This is a "cache" which holds the last block range checked during
+	 * processing of an extent. This information is used to avoid allocating
+	 * the same blocks multiple times, if two successive extents become
+	 * overlapped (in terms of disk blocks) after padding.
+	 *
+	 * The problem with allocating the same blocks multiple times:
+	 * our function try_allocate_blocks() is not idempotent. More precisely,
+	 * after a positive result has been returned for a given range [A;B), we
+	 * must not call try_allocate_blocks() on any range which overlaps [A;B),
+	 * or we will get a false negative result.
+	 * (Also, we must not call try_allocate_blocks() on any range which
+	 * overlaps extents in the discard set.)
+	 *
+	 * Let's show that we can avoid false-negatives with this cache.
+	 *
+	 * 1. All blocks between the stored tail padding and the beginning of
+	 *    the current extent are safe to allocate.
+	 *
+	 * 2. Let's analyze all combinations of the previous tail padding's check
+	 *    result and the current head padding's disposition relative to the
+	 *    previous tail padding. Note that we are speaking in terms of
+	 *    occupied disk blocks.
+	 *
+	 * 2.0. The head padding does not overlap the tail padding.
+	 *      In this case head padding is safe to allocate.
+	 *
+	 * 2.1. The tail padding is dirty. The head padding partially overlaps it.
+	 *      In this case both parts of the head padding are safe to allocate.
+	 *
+	 * 2.2. The tail padding is dirty. The head padding completely covers it
+	 *      (maybe extending back beyond).
+	 *      In this case the head padding is transitively dirty.
+	 *
+	 * 2.3. The tail padding is clean. The head padding overlaps or covers it
+	 *      (not extending back beyond).
+	 *      In this case:
+	 *      - the overlapping part of the head padding can be skipped
+	 *      - the rest is safe to allocate
+	 *
+	 * 2.4. The tail padding is clean. The head padding extends beyond it.
+	 *      This is not possible. It would mean that our head padding
+	 *      shares an erase unit with the previous tail padding.
+	 *      Such extent combinations are handled by the gluing code.
+	 */
+
+	reiser4_block_nr last_padding_start = 0;
+	reiser4_block_nr last_padding_end = 0;
+	int last_padding_clean = 0;
+
 	d_off = get_super_private(sb)->discard.offset;
 	d_uni = get_super_private(sb)->discard.unit;
 
@@ -316,34 +364,89 @@ static int discard_precise_extents(struct list_head *head)
 		p_headp = precise_extent_headp(p_start, d_off, d_uni);
 		headp = size_in_blocks(p_headp, blkbits);
 
+		/*
+		 * Our head padding can't extend back beyond the saved tail
+		 * padding, if the latter is clean.
+		 * (cf. situation 2.4 from the above description)
+		 */
+		assert("intelfx-80", ergo(last_padding_clean,
+					  last_padding_start <= start - headp));
+
 		if (headp == 0) {
 			/*
 			 * empty head padding
 			 */
-			assert("edward-1635", headp_is_known_dirty == 0);
 			a_start = p_start;
 			a_len = p_len;
-		}
-		else if (p_start >= p_headp /* discard unit is complete */ &&
-			 !headp_is_known_dirty &&
-			 try_allocate_blocks(start - headp, headp)) {
-			/*
-			 * pad the head
-			 */
-			a_start = p_start - p_headp;
-			a_len = p_len + p_headp;
-			estart -= headp;
 		} else {
+			int headp_is_clean;
+
 			/*
-			 * head padding is dirty,
-			 * or discard unit is incomplete (can not
-			 * check blocks outside of the partition),
-			 * cut the head
+			 * If our discard unit is incomplete, don't pad.
 			 */
-			headp_is_known_dirty = 0;
-			a_start = p_start + (d_uni - p_headp);
-			a_len = p_len - (d_uni - p_headp);
+			if (p_start < p_headp)
+				headp_is_clean = 0;
+
+			/*
+			 * Maybe last checked extent is dirty and completely
+			 * embedded in ours? Then our one is dirty too.
+			 * (cf. situation 2.2 from the above description)
+			 */
+			else if (!last_padding_clean &&
+				 last_padding_start >= start - headp &&
+				 last_padding_end <= start)
+				headp_is_clean = 0;
+
+			/*
+			 * Maybe last checked extent is clean and completely
+			 * covers ours? Then our one is clean too.
+			 * (cf. situation 2.3 from the above description)
+			 */
+			else if (last_padding_clean &&
+				 last_padding_end >= start)
+				headp_is_clean = 1;
+
+			/*
+			 * Maybe last checked extent is clean and partially
+			 * overlaps ours? Then we must check the remaining part.
+			 * (cf. situation 2.3 from the above description)
+			 */
+			else if (last_padding_clean &&
+				 last_padding_end > start - headp) {
+				headp_is_clean = try_allocate_blocks(last_padding_end, start - last_padding_end);
+				if (headp_is_clean)
+					estart = last_padding_end;
+			}
+
+			/*
+			 * Otherwise check the whole padding.
+			 * (cf. situations 2.0, 2.1 from the above description)
+			 */
+			else {
+				headp_is_clean = try_allocate_blocks(start - headp, headp);
+				if (headp_is_clean)
+					estart -= headp;
+			}
+
+			if (headp_is_clean) {
+				/*
+				 * head padding is clean,
+				 * pad the head
+				 */
+				a_start = p_start - p_headp;
+				a_len = p_len + p_headp;
+			} else {
+				/*
+				 * head padding is dirty,
+				 * or discard unit is incomplete (can not
+				 * check blocks outside of the partition),
+				 * cut the head
+				 */
+				a_start = p_start + (d_uni - p_headp);
+				a_len = p_len - (d_uni - p_headp);
+			}
 		}
+
 		/*
 		 * Step II. Try to glue all nearby extents to the tail
 		 *          Cut or pad the tail of the last extent.
@@ -410,10 +513,14 @@ static int discard_precise_extents(struct list_head *head)
 					/*
 					 * gluing failed, cut the tail
 					 */
-					if (p_end + p_tailp > p_next_start)
-						headp_is_known_dirty = 1;
-
 					a_len -= (d_uni - p_tailp);
+
+					/*
+					 * save the tail padding
+					 */
+					last_padding_start = end;
+					last_padding_end = next_start;
+					last_padding_clean = 0;
 					break;
 				}
 
@@ -425,21 +532,44 @@ static int discard_precise_extents(struct list_head *head)
 				 * rest of tail padding and finish with
 				 * the extent
 				 */
-				if (tailp == 0)
-					break;
-				else if (try_allocate_blocks(end, tailp)) {
+				if (tailp == 0) {
+					/*
+					 * empty tail padding.
+					 *
+					 * save a fake tail padding to aid debugging
+					 */
+					last_padding_start = end;
+					last_padding_end = end;
+					last_padding_clean = 1;
+
+				} else if (try_allocate_blocks(end, tailp)) {
 					/*
 					 * tail padding is clean,
 					 * pad the tail
 					 */
 					a_len += p_tailp;
 					eend += tailp;
-				} else
+
+					/*
+					 * save the tail padding
+					 */
+					last_padding_start = end;
+					last_padding_end = end + tailp;
+					last_padding_clean = 1;
+				} else {
 					/*
 					 * tail padding is dirty,
 					 * cut the tail
 					 */
 					a_len -= (d_uni - p_tailp);
+
+					/*
+					 * save the tail padding
+					 */
+					last_padding_start = end;
+					last_padding_end = end + tailp;
+					last_padding_clean = 0;
+				}
 				break;
 			}
 		}
-- 
2.3.0

Re: [PATCH 2/3] reiser4: discard: avoid checking same blocks multiple times.

[Edward Shishkin]

OK, thanks,
I'll take a look at leisure.
The function is extremely complicated, and
every time it takes me a lot of time to recall
what is going on here...

Thanks,
Edward.


On 02/13/2015 06:02 AM, Ivan Shapovalov wrote:
> It was previously possible for an extent's tail padding and next extent's head
> padding to overlap in terms of occupied disk blocks.
>
> In this case the head padding check would yield a false negative because blocks
> would appear already allocated, while in fact they would have been previously
> allocated by us.
>
> Solve this by saving last checked tail padding and a bit of case analysis.
>
> Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
> ---
>   fs/reiser4/discard.c | 182 +++++++++++++++++++++++++++++++++++++++++++--------
>   1 file changed, 156 insertions(+), 26 deletions(-)
>
> diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
> index a615b7d..10c1707 100644
> --- a/fs/reiser4/discard.c
> +++ b/fs/reiser4/discard.c
> @@ -272,9 +272,57 @@ static int discard_precise_extents(struct list_head *head)
>   	int d_off;
>   	struct list_head *pos;
>   	struct super_block *sb = reiser4_get_current_sb();
> -	int headp_is_known_dirty = 0;
>   	int blkbits = sb->s_blocksize_bits;
>   
> +	/* This is a "cache" which holds the last block range checked during
> +	 * processing of an extent. This information is used to avoid allocating
> +	 * the same blocks multiple times, if two successive extents become
> +	 * overlapped (in terms of disk blocks) after padding.
> +	 *
> +	 * The problem with allocating the same blocks multiple times:
> +	 * our function try_allocate_blocks() is not idempotent. More precisely,
> +	 * after a positive result has been returned for a given range [A;B), we
> +	 * must not call try_allocate_blocks() on any range which overlaps [A;B),
> +	 * or we will get a false negative result.
> +	 * (Also, we must not call try_allocate_blocks() on any range which
> +	 * overlaps extents in the discard set.)
> +	 *
> +	 * Let's show that we can avoid false-negatives with this cache.
> +	 *
> +	 * 1. All blocks between the stored tail padding and the beginning of
> +	 *    the current extent are safe to allocate.
> +	 *
> +	 * 2. Let's analyze all combinations of the previous tail padding's check
> +	 *    result and the current head padding's disposition relative to the
> +	 *    previous tail padding. Note that we are speaking in terms of
> +	 *    occupied disk blocks.
> +	 *
> +	 * 2.0. The head padding does not overlap the tail padding.
> +	 *      In this case head padding is safe to allocate.
> +	 *
> +	 * 2.1. The tail padding is dirty. The head padding partially overlaps it.
> +	 *      In this case both parts of the head padding are safe to allocate.
> +	 *
> +	 * 2.2. The tail padding is dirty. The head padding completely covers it
> +	 *      (maybe extending back beyond).
> +	 *      In this case the head padding is transitively dirty.
> +	 *
> +	 * 2.3. The tail padding is clean. The head padding overlaps or covers it
> +	 *      (not extending back beyond).
> +	 *      In this case:
> +	 *      - the overlapping part of the head padding can be skipped
> +	 *      - the rest is safe to allocate
> +	 *
> +	 * 2.4. The tail padding is clean. The head padding extends beyond it.
> +	 *      This is not possible. It would mean that our head padding
> +	 *      shares an erase unit with the previous tail padding.
> +	 *      Such extent combinations are handled by the gluing code.
> +	 */
> +
> +	reiser4_block_nr last_padding_start = 0;
> +	reiser4_block_nr last_padding_end = 0;
> +	int last_padding_clean = 0;
> +
>   	d_off = get_super_private(sb)->discard.offset;
>   	d_uni = get_super_private(sb)->discard.unit;
>   
> @@ -316,34 +364,89 @@ static int discard_precise_extents(struct list_head *head)
>   		p_headp = precise_extent_headp(p_start, d_off, d_uni);
>   		headp = size_in_blocks(p_headp, blkbits);
>   
> +		/*
> +		 * Our head padding can't extend back beyond the saved tail
> +		 * padding, if the latter is clean.
> +		 * (cf. situation 2.4 from the above description)
> +		 */
> +		assert("intelfx-80", ergo(last_padding_clean,
> +					  last_padding_start <= start - headp));
> +
>   		if (headp == 0) {
>   			/*
>   			 * empty head padding
>   			 */
> -			assert("edward-1635", headp_is_known_dirty == 0);
>   			a_start = p_start;
>   			a_len = p_len;
> -		}
> -		else if (p_start >= p_headp /* discard unit is complete */ &&
> -			 !headp_is_known_dirty &&
> -			 try_allocate_blocks(start - headp, headp)) {
> -			/*
> -			 * pad the head
> -			 */
> -			a_start = p_start - p_headp;
> -			a_len = p_len + p_headp;
> -			estart -= headp;
>   		} else {
> +			int headp_is_clean;
> +
>   			/*
> -			 * head padding is dirty,
> -			 * or discard unit is incomplete (can not
> -			 * check blocks outside of the partition),
> -			 * cut the head
> +			 * If our discard unit is incomplete, don't pad.
>   			 */
> -			headp_is_known_dirty = 0;
> -			a_start = p_start + (d_uni - p_headp);
> -			a_len = p_len - (d_uni - p_headp);
> +			if (p_start < p_headp)
> +				headp_is_clean = 0;
> +
> +			/*
> +			 * Maybe last checked extent is dirty and completely
> +			 * embedded in ours? Then our one is dirty too.
> +			 * (cf. situation 2.2 from the above description)
> +			 */
> +			else if (!last_padding_clean &&
> +				 last_padding_start >= start - headp &&
> +				 last_padding_end <= start)
> +				headp_is_clean = 0;
> +
> +			/*
> +			 * Maybe last checked extent is clean and completely
> +			 * covers ours? Then our one is clean too.
> +			 * (cf. situation 2.3 from the above description)
> +			 */
> +			else if (last_padding_clean &&
> +				 last_padding_end >= start)
> +				headp_is_clean = 1;
> +
> +			/*
> +			 * Maybe last checked extent is clean and partially
> +			 * overlaps ours? Then we must check the remaining part.
> +			 * (cf. situation 2.3 from the above description)
> +			 */
> +			else if (last_padding_clean &&
> +				 last_padding_end > start - headp) {
> +				headp_is_clean = try_allocate_blocks(last_padding_end, start - last_padding_end);
> +				if (headp_is_clean)
> +					estart = last_padding_end;
> +			}
> +
> +			/*
> +			 * Otherwise check the whole padding.
> +			 * (cf. situations 2.0, 2.1 from the above description)
> +			 */
> +			else {
> +				headp_is_clean = try_allocate_blocks(start - headp, headp);
> +				if (headp_is_clean)
> +					estart -= headp;
> +			}
> +
> +			if (headp_is_clean) {
> +				/*
> +				 * head padding is clean,
> +				 * pad the head
> +				 */
> +				a_start = p_start - p_headp;
> +				a_len = p_len + p_headp;
> +			} else {
> +				/*
> +				 * head padding is dirty,
> +				 * or discard unit is incomplete (can not
> +				 * check blocks outside of the partition),
> +				 * cut the head
> +				 */
> +				a_start = p_start + (d_uni - p_headp);
> +				a_len = p_len - (d_uni - p_headp);
> +			}
>   		}
> +
>   		/*
>   		 * Step II. Try to glue all nearby extents to the tail
>   		 *          Cut or pad the tail of the last extent.
> @@ -410,10 +513,14 @@ static int discard_precise_extents(struct list_head *head)
>   					/*
>   					 * gluing failed, cut the tail
>   					 */
> -					if (p_end + p_tailp > p_next_start)
> -						headp_is_known_dirty = 1;
> -
>   					a_len -= (d_uni - p_tailp);
> +
> +					/*
> +					 * save the tail padding
> +					 */
> +					last_padding_start = end;
> +					last_padding_end = next_start;
> +					last_padding_clean = 0;
>   					break;
>   				}
>   
> @@ -425,21 +532,44 @@ static int discard_precise_extents(struct list_head *head)
>   				 * rest of tail padding and finish with
>   				 * the extent
>   				 */
> -				if (tailp == 0)
> -					break;
> -				else if (try_allocate_blocks(end, tailp)) {
> +				if (tailp == 0) {
> +					/*
> +					 * empty tail padding.
> +					 *
> +					 * save a fake tail padding to aid debugging
> +					 */
> +					last_padding_start = end;
> +					last_padding_end = end;
> +					last_padding_clean = 1;
> +
> +				} else if (try_allocate_blocks(end, tailp)) {
>   					/*
>   					 * tail padding is clean,
>   					 * pad the tail
>   					 */
>   					a_len += p_tailp;
>   					eend += tailp;
> -				} else
> +
> +					/*
> +					 * save the tail padding
> +					 */
> +					last_padding_start = end;
> +					last_padding_end = end + tailp;
> +					last_padding_clean = 1;
> +				} else {
>   					/*
>   					 * tail padding is dirty,
>   					 * cut the tail
>   					 */
>   					a_len -= (d_uni - p_tailp);
> +
> +					/*
> +					 * save the tail padding
> +					 */
> +					last_padding_start = end;
> +					last_padding_end = end + tailp;
> +					last_padding_clean = 0;
> +				}
>   				break;
>   			}
>   		}

[PATCH 3/3] reiser4: discard: handle incomplete erase units at the end of a partition.

[Ivan Shapovalov]

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/discard.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
index 10c1707..6163ea2 100644
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -542,7 +542,8 @@ static int discard_precise_extents(struct list_head *head)
 					last_padding_end = end;
 					last_padding_clean = 1;
 
-				} else if (try_allocate_blocks(end, tailp)) {
+				} else if (end + tailp <= reiser4_block_count(sb) &&
+					   try_allocate_blocks(end, tailp)) {
 					/*
 					 * tail padding is clean,
 					 * pad the tail
-- 
2.3.0

Re: [PATCH 3/3] reiser4: discard: handle incomplete erase units at the end of a partition.

[Edward Shishkin]

Ok.

On 02/13/2015 06:02 AM, Ivan Shapovalov wrote:
> Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
> ---
>   fs/reiser4/discard.c | 3 ++-
>   1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
> index 10c1707..6163ea2 100644
> --- a/fs/reiser4/discard.c
> +++ b/fs/reiser4/discard.c
> @@ -542,7 +542,8 @@ static int discard_precise_extents(struct list_head *head)
>   					last_padding_end = end;
>   					last_padding_clean = 1;
>   
> -				} else if (try_allocate_blocks(end, tailp)) {
> +				} else if (end + tailp <= reiser4_block_count(sb) &&
> +					   try_allocate_blocks(end, tailp)) {
>   					/*
>   					 * tail padding is clean,
>   					 * pad the tail