On (06/09/13 12:48), Simo Sorce wrote:
On Fri, 2013-09-06 at 16:26 +0200, Lukas Slebodnik wrote:
> Step 6) Remove record R3(hash_1:4, hash_2:3) stored at slot index 0x43
> a) Remove record R3 from chain starting by hash R3->hash1 (value 4)
> hash[1] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
> hash[2] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
> hash[3] -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
> hash[4] -> 0x54(R4) -> MC_INVALID_VAL
> hash[5] -> 0x54(R4) -> MC_INVALID_VAL
>
> b) Remove record R3 from chain starting by hash R3->hash2 (value 3)
> hash[1] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
> hash[2] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
> hash[3] -> MC_INVALID_VAL
> hash[4] -> 0x54(R4) -> MC_INVALID_VAL
> hash[5] -> 0x54(R4) -> MC_INVALID_VAL
>
>
I do not see how this happens, in hash[3] you have another record after
R3 so hash[3] should be
This behaviour was introduced by patch
4662725ffef62b3b2502481438effa7c8fef9f80
and it is very similar to reinvalidation.
hash[3] -> 0x54(R4) -> MC_INVALID_VAL
however I do see how R3 would remain in hash[1] and hash[2].
And that is a problem, the problem I was trying to wrap my mind around
with the patch you proposed last time. Wouldn't the revalidation idea I
had last time fix this issue ?
Simo.
record R1(hash_1:1, hash_2:2) stored at slot index 0x12
record R2(hash_1:3, hash_2:1) stored at slot index 0x31
record R3(hash_1:4, hash_2:3) stored at slot index 0x43
record R4(hash_1:5, hash_2:4) stored at slot index 0x54
Last state:
-------------------------
hash[1] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[3] -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[4] -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL
I will try to describe last removing with your idea about reinvalidation.
Step 6) Remove record R3(hash_1:4, hash_2:3) stored at slot index 0x43
a) Remove record R3 from the 1st chain starting by hash R3->hash1 (value 4)
hash[1] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[3] -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[4] -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL
b) Revalidate chain for R3->hash1 (value 4)
-- chain for hash[4] refers to 0x54(R4) and R4 has hash with value 4
c) Remove record R3 from the 2nd chain starting by hash R3->hash2 (value 3)
hash[1] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[3] -> 0x54(R4) -> MC_INVALID_VAL
hash[4] -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL
d) Revalidate chain for R3->hash2 (value 3)
-- chain for hash[3] refers to 0x54(R4)
and R4 *DOES NOT have* hash with value 4
--hash[3] will refer wo successor of R4, MC_INVALID_VAL
hash[1] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[3] -> MC_INVALID_VAL
hash[4] -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL
e) Revalidate all succesors of record R3. R3->next == 0x54 (R4)
in this case, only record R4(hash_1:5, hash_2:4) is in chain
-- chain for hash[5] refers to 0x54(R4) and R4 has hash with value 5
-- chain for hash[4] refers to 0x54(R4) and R4 has hash with value 4
f) slots for record R2 will be invalidated.
hash[1] -> 0x12(R1) -> INVALIDATED_SLOT ??-> 0x54(R4) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> INVALIDATED_SLOT ??-> 0x54(R4) -> MC_INVALID_VAL
hash[3] -> MC_INVALID_VAL
hash[4] -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL
As you can see the, result is the same as from my previous mail.
This is a special case, but it can happen.
I spent a lot of time with reproducing this case and with analysis.
So I hope this explanation helps to understand this special case.
Is it clear now?
LS