reiser4: precise discard - general case

This is the promised generalization, which is supposed to work for all discard
offsets and all discard unit sizes without any restrictions.

Complications in comparison with the previous implementation:

In this general case we need "precise" coordinates, where every individual byte
can be addressed. All local variables, which represent precise coordinates are
denoted with "prefixes" (a_len, d_off, p_tailp, etc). Local variables, which represent
"non-precise" coordinates (they are usually of type reiser4_block_nr) are denoted
without prefixes (start, len, end, tailp, etc).

Blocks, which contain head and tail paddings are now calculated using the function size_in_blocks(), which actually is an expression for the minimal number
of blocks containing the precise extent.

The next trouble is "peculiarity in 0", encountered when calculating the blocks of
head padding. if discard offset is different from 0, then the first discard unit of the
partition is partial (its other part doesn't belong to our partition, so we can not
discard it). We handle this peculiarity by an additional check.

In other bits everything is the same.

Possible optimization: If discard unit sizes are always powers of 2, then it makes
sense to replace "do_div(offset, unit_size)" with "offset & (unit_size - 1)".

Mount options discard.offset=xxx,discard.unit=yyy are to emulate various discard unit sizes and offsets on devices _without_ trim support (e.g. HDDs).
This is only for debugging purposes, don't use it for real SSD devices:
the kernel
retrieves the discard parameters on its own.

This patch is against the patch series of Ivan Shapovalov:
http://marc.info/?l=reiserfs-devel&m=141841865432082&w=2

Current status: not well-tested.

Edward.

Quoted 43 lines · Edward Shishkin

This is the promised generalization, which is supposed to work for all discard
offsets and all discard unit sizes without any restrictions.

Complications in comparison with the previous implementation:

In this general case we need "precise" coordinates, where every individual byte
can be addressed. All local variables, which represent precise coordinates are
denoted with "prefixes" (a_len, d_off, p_tailp, etc). Local variables, which represent
"non-precise" coordinates (they are usually of type reiser4_block_nr) are denoted
without prefixes (start, len, end, tailp, etc).

Blocks, which contain head and tail paddings are now calculated using the function size_in_blocks(), which actually is an expression for the minimal number
of blocks containing the precise extent.

The next trouble is "peculiarity in 0", encountered when calculating the blocks of
head padding. if discard offset is different from 0, then the first discard unit of the
partition is partial (its other part doesn't belong to our partition, so we can not
discard it). We handle this peculiarity by an additional check.

In other bits everything is the same.

Possible optimization: If discard unit sizes are always powers of 2, then it makes
sense to replace "do_div(offset, unit_size)" with "offset & (unit_size - 1)".

Mount options discard.offset=xxx,discard.unit=yyy are to emulate various discard unit sizes and offsets on devices _without_ trim support (e.g. HDDs).
This is only for debugging purposes, don't use it for real SSD devices:
the kernel
retrieves the discard parameters on its own.

Quoted 6 lines

This patch is against the patch series of Ivan Shapovalov:
http://marc.info/?l=reiserfs-devel&m=141841865432082&w=2

Current status: not well-tested.

Edward.

Hi,

I've found a bug in our implementation (don't know when it appeared, maybe it was quite some time ago). I've intended to fix it and send a patch along with description, but I still can't think of a viable fix.

So: the problem is that check_free_blocks() isn't idempotent, because it allocates blocks if the whole extent is clean. Therefore, it must not be called for overlapping ranges. However, in some conditions tail padding of some extent and head padding of next extent may overlap in terms of disk blocks (gluing code only catches overlapping erase units).

This will yield a false negative when checking the head padding, so it does not lead to any data losses (just to inefficiency).

Quoted 62 lines · Ivan Shapovalov

Quoted 43 lines · Edward Shishkin

This is the promised generalization, which is supposed to work for all discard
offsets and all discard unit sizes without any restrictions.

Complications in comparison with the previous implementation:

In this general case we need "precise" coordinates, where every individual byte
can be addressed. All local variables, which represent precise coordinates are
denoted with "prefixes" (a_len, d_off, p_tailp, etc). Local variables, which represent
"non-precise" coordinates (they are usually of type reiser4_block_nr) are denoted
without prefixes (start, len, end, tailp, etc).

Blocks, which contain head and tail paddings are now calculated using the function size_in_blocks(), which actually is an expression for the minimal number
of blocks containing the precise extent.

The next trouble is "peculiarity in 0", encountered when calculating the blocks of
head padding. if discard offset is different from 0, then the first discard unit of the
partition is partial (its other part doesn't belong to our partition, so we can not
discard it). We handle this peculiarity by an additional check.

In other bits everything is the same.

Possible optimization: If discard unit sizes are always powers of 2, then it makes
sense to replace "do_div(offset, unit_size)" with "offset & (unit_size - 1)".

Mount options discard.offset=xxx,discard.unit=yyy are to emulate various discard unit sizes and offsets on devices _without_ trim support (e.g. HDDs).
This is only for debugging purposes, don't use it for real SSD devices:
the kernel
retrieves the discard parameters on its own.

Quoted 6 lines

This patch is against the patch series of Ivan Shapovalov:
http://marc.info/?l=reiserfs-devel&m=141841865432082&w=2

Current status: not well-tested.

Edward.

Hi,

I've found a bug in our implementation (don't know when it appeared, maybe it was quite some time ago). I've intended to fix it and send a patch along with description, but I still can't think of a viable fix.

So: the problem is that check_free_blocks() isn't idempotent, because it allocates blocks if the whole extent is clean. Therefore, it must not be called for overlapping ranges. However, in some conditions tail padding of some extent and head padding of next extent may overlap in terms of disk blocks (gluing code only catches overlapping erase units).

Quoted 2 lines

This will yield a false negative when checking the head padding, so it does not lead to any data losses (just to inefficiency).

You mean that sometimes we perform unneeded checks? I see nothing criminal, as we don't exceed announced (2N_e) number of checks, where N_e is number of extents in the discard set.

As to fixup: I think that we need to set up the local variable head_is_known_dirty properly..

Quoted 63 lines · Edward Shishkin

Quoted 62 lines · Ivan Shapovalov

Quoted 43 lines · Edward Shishkin

This is the promised generalization, which is supposed to work for all discard
offsets and all discard unit sizes without any restrictions.

Complications in comparison with the previous implementation:

In this general case we need "precise" coordinates, where every individual byte
can be addressed. All local variables, which represent precise coordinates are
denoted with "prefixes" (a_len, d_off, p_tailp, etc). Local variables, which represent
"non-precise" coordinates (they are usually of type reiser4_block_nr) are denoted
without prefixes (start, len, end, tailp, etc).

Blocks, which contain head and tail paddings are now calculated using the function size_in_blocks(), which actually is an expression for the minimal number
of blocks containing the precise extent.

The next trouble is "peculiarity in 0", encountered when calculating the blocks of
head padding. if discard offset is different from 0, then the first discard unit of the
partition is partial (its other part doesn't belong to our partition, so we can not
discard it). We handle this peculiarity by an additional check.

In other bits everything is the same.

Possible optimization: If discard unit sizes are always powers of 2, then it makes
sense to replace "do_div(offset, unit_size)" with "offset & (unit_size - 1)".

Mount options discard.offset=xxx,discard.unit=yyy are to emulate various discard unit sizes and offsets on devices _without_ trim support (e.g. HDDs).
This is only for debugging purposes, don't use it for real SSD devices:
the kernel
retrieves the discard parameters on its own.

Quoted 6 lines

This patch is against the patch series of Ivan Shapovalov:
http://marc.info/?l=reiserfs-devel&m=141841865432082&w=2

Current status: not well-tested.

Edward.

Hi,

I've found a bug in our implementation (don't know when it appeared, maybe it was quite some time ago). I've intended to fix it and send a patch along with description, but I still can't think of a viable fix.

So: the problem is that check_free_blocks() isn't idempotent, because it allocates blocks if the whole extent is clean. Therefore, it must not be called for overlapping ranges. However, in some conditions tail padding of some extent and head padding of next extent may overlap in terms of disk blocks (gluing code only catches overlapping erase units).

Quoted 7 lines

Quoted 2 lines

This will yield a false negative when checking the head padding, so it does not lead to any data losses (just to inefficiency).

You mean that sometimes we perform unneeded checks? I see nothing criminal, as we don't exceed announced (2N_e) number of checks, where N_e is number of extents in the discard set.

No, I didn't talk about that.

Quoted 2 lines

As to fixup: I think that we need to set up the local variable head_is_known_dirty properly..

Hmm, head_is_known_dirty is an optimization: either known dirty (in which case we skip checking and cut the head), or unknown (in which case we do the check).

I'm talking about a different scenario:
- tail padding of an extent is clean
- head padding of the next extent is clean
- these two paddings overlap in terms of disk blocks

In this case, the head padding check will yield false ("dirty") because part of it has been already allocated for the tail padding, but in fact it is clean. Thus a false negative: the head will be cut while it can be padded.

More generally, our check_free_blocks() is not idempotent. After a positive result has been returned for a given range [A;B), check_free_blocks() must not be called for any range [A';B') such that [A;B) ∩ [A';B') ≠ ∅. Otherwise a false negative can be returned.

Actually, during the last night I've *apparently* came up with a solution for this :) I'll send a patch once I figure out how to explain it properly in the comments...

Thanks,

12 февр. 2015 г., в 2:40, Edward Shishkin <[email protected]> написал(а):

Quoted 85 lines · Ivan Shapovalov

Quoted 64 lines · Edward Shishkin

Quoted 63 lines · Ivan Shapovalov

Quoted 44 lines · Edward Shishkin

This is the promised generalization, which is supposed to work for all discard
offsets and all discard unit sizes without any restrictions.

Complications in comparison with the previous implementation:

In this general case we need "precise" coordinates, where every individual byte
can be addressed. All local variables, which represent precise coordinates are
denoted with "prefixes" (a_len, d_off, p_tailp, etc). Local variables, which represent
"non-precise" coordinates (they are usually of type reiser4_block_nr) are denoted
without prefixes (start, len, end, tailp, etc).

Blocks, which contain head and tail paddings are now calculated using the function size_in_blocks(), which actually is an expression for the minimal number
of blocks containing the precise extent.

The next trouble is "peculiarity in 0", encountered when calculating the blocks of
head padding. if discard offset is different from 0, then the first discard unit of the
partition is partial (its other part doesn't belong to our partition, so we can not
discard it). We handle this peculiarity by an additional check.

In other bits everything is the same.

Possible optimization: If discard unit sizes are always powers of 2, then it makes
sense to replace "do_div(offset, unit_size)" with "offset & (unit_size - 1)".

Mount options discard.offset=xxx,discard.unit=yyy are to emulate various discard unit sizes and offsets on devices _without_ trim support (e.g. HDDs).
This is only for debugging purposes, don't use it for real SSD devices:
the kernel
retrieves the discard parameters on its own.

Quoted 6 lines

This patch is against the patch series of Ivan Shapovalov:
http://marc.info/?l=reiserfs-devel&m=141841865432082&w=2

Current status: not well-tested.

Edward.

Hi,

I've found a bug in our implementation (don't know when it appeared, maybe it was quite some time ago). I've intended to fix it and send a patch along with description, but I still can't think of a viable fix.

So: the problem is that check_free_blocks() isn't idempotent, because it allocates blocks if the whole extent is clean. Therefore, it must not be called for overlapping ranges. However, in some conditions tail padding of some extent and head padding of next extent may overlap in terms of disk blocks (gluing code only catches overlapping erase units).

Quoted 7 lines

Quoted 2 lines

This will yield a false negative when checking the head padding, so it does not lead to any data losses (just to inefficiency).

You mean that sometimes we perform unneeded checks? I see nothing criminal, as we don't exceed announced (2N_e) number of checks, where N_e is number of extents in the discard set.

No, I didn't talk about that.

Quoted 2 lines

As to fixup: I think that we need to set up the local variable head_is_known_dirty properly..

Hmm, head_is_known_dirty is an optimization: either known dirty (in which case we skip checking and cut the head), or unknown (in which case we do the check).

I'm talking about a different scenario:
- tail padding of an extent is clean
- head padding of the next extent is clean
- these two paddings overlap in terms of disk blocks

Quoted 4 lines

In this case, the head padding check will yield false ("dirty") because part of it has been already allocated for the tail padding, but in fact it is clean. Thus a false negative: the head will be cut while it can be padded.

Ah, you suspect non-preciseness (leak of "garbage")?

If tail padding of the current extent overlaps with the head padding of the next extent, then the end of the current extent and the beginning of the next extent are in the same erase unit. Otherwise we'll end with contradiction. Correct?

Quoted 22 lines

You mean that sometimes we perform unneeded checks? I see nothing criminal, as we don't exceed announced (2N_e) number of checks, where N_e is number of extents in the discard set.

Quoted 17 lines

No, I didn't talk about that.

Quoted 2 lines

As to fixup: I think that we need to set up the local variable head_is_known_dirty properly..

Hmm, head_is_known_dirty is an optimization: either known dirty (in which case we skip checking and cut the head), or unknown (in which case we do the check).

I'm talking about a different scenario:
- tail padding of an extent is clean
- head padding of the next extent is clean
- these two paddings overlap in terms of disk blocks

In this case, the head padding check will yield false ("dirty") because part of it has been already allocated for the tail padding, but in fact it is clean. Thus a false negative: the head will be cut while it can be padded.

Quoted 6 lines

Ah, you suspect non-preciseness (leak of "garbage")?

If tail padding of the current extent overlaps with the head padding of the next extent, then the end of the current extent and the beginning of the next extent are in the same erase unit. Otherwise we'll end with contradiction. Correct?

Correct, but I'm talking about a different situation where the end of the current extent and the beginning of the next extent are in distinct erase units but in the same disk block. Then we'll end up checking that disk block twice.

[...]

You correctly pointed out the possibility of garbage leak in the case of block_size > erase_unit_size. However, the current gluing policy prevents such leak.

Indeed, let AB be a current extent, and CD - next extent

----*-----*-----*-----*-----*-----*-----*---> units --|-----------|-----------|-----------|-----> blocks
A B C D

Note that since extents are sorted and merged, distance between any 2 extents are not smaller than block_size.
In particular, |BC| >= block_size. (1)

Suppose that tail padding of the current extent and head padding of the next extent are in the same disk block. However, in this case, in accordance with the definitions
of tail and head paddings, we have that |BC| <= block_size. (2)

From (1) and (2) we have that |BC| == block_size, and
p_end + p_tailp == C == start-of-next-extent.

Quoted 18 lines · Edward Shishkin

[...]

You correctly pointed out the possibility of garbage leak in the case of block_size > erase_unit_size. However, the current gluing policy prevents such leak.

Indeed, let AB be a current extent, and CD - next extent

----*-----*-----*-----*-----*-----*-----*---> units --|-----------|-----------|-----------|-----> blocks
A B C D

Note that since extents are sorted and merged, distance between any 2 extents are not smaller than block_size.
In particular, |BC| >= block_size. (1)

Quoted 7 lines

Suppose that tail padding of the current extent and head padding of the next extent are in the same disk block. However, in this case, in accordance with the definitions
of tail and head paddings, we have that |BC| <= block_size. (2)

From (1) and (2) we have that |BC| == block_size, and
p_end + p_tailp == C == start-of-next-extent.

This is not correct. p_* variables are byte-granular, so p_end + p_tailp ends up somewhere between B and C. More precisely, it will point at the first unit-unit boundary inside (B; C). So the condition referenced below is not fulfilled.

That is, we only glue extents which overlap in terms of erase units, not in terms of disk blocks after padding.

One may suggest to relax the condition instead; in other words, to make it look something like this:

if (end + tailp >= blocknr_list_entry_start(next))

However, it potentially makes us discard already clean units. I don't remember if there are any other problems with this approach.