[SSSD] mmap_cache problem

Simo Sorce simo at redhat.com
Sat Sep 7 17:43:01 UTC 2013


On Fri, 2013-09-06 at 18:55 -0400, Simo Sorce wrote:
> On Fri, 2013-09-06 at 19:45 +0200, Lukas Slebodnik wrote:
> > 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?
> 
> It is clear to me, but what you describe here is not my original
> proposal.
> 
> Revalidation was the rechecking of chains when you remove an object.
> In your example revalidation of the chains when you remove R2 (not R3)
> would lead to removal of R3 from hash[1] and hash[2] chains resolving
> the problem.
> 
> I am only sorry I wasn't more firm on the revalidation idea now.
> 
> I will send some examples later.
> 
> Simo.
> 

Just a refresher of my original proposal:
After we remove a record we re-validate the 2 chains it belonged to, and
prune any record that does not match the chain record or any of the
chains referenced by the records that precede.


Ok here is the example.

---
This was the problem:
Add record R1(hash_1:1, hash_2:2) stored at slot index 0x12
Add record R2(hash_1:3, hash_2:1) stored at slot index 0x31
Add record R3(hash_1:4, hash_2:3) stored at slot index 0x43
Add record R4(hash_1:5, hash_2:4) stored at slot index 0x54
Remove record R2
Remove record R3

---
This was the state at step 4 of your first email, after everything was
added and before anything is removed:

hash[1] -> 0x12(R1) -> 0x31(R2) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> 0x31(R2) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[3] -> 0x31(R2) -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[4] -> 0x43(R3) -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL

---
So let's remove R2.

This is the state (as reported by you) after R2 is removed from all its
chains:

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

R2 was in chain 3 and 1, so *now* let's re-validate the chains.

First we do [3]
- First entry is R3 (4, 3), 3 matches so we keep it.
  And now the chains to match are [3, 4] ([3] + (4, 3))
- Second is R4 (5, 4), 4 matches so we keep it.
  And now the chains to match are [3, 4, 5] ([3, 4] + (5, 4))
- We are done, no more elements on hash[3]

Then we do hash[1]
- First entry is R1 (1, 2), 1 matches so we keep it.
  And now the chains to match are [1, 2] ([1] + (1, 2))
- Second entry is R3 (4, 3), it does *NOT* match any, so
   we skip it, which means pointing R1 to the next one (R4)
  Two chains are affected this way [1] and [2]:
  hash[1] -> 0x12(R1) -> 0x54(R4) -> MC_INVALID_VAL
  hash[2] -> 0x12(R1) -> 0x54(R4) -> MC_INVALID_VAL
- Third now is R4 (5, 4) and the matching table is still [1, 2]
  It does *NOT* match once again, so we skip this too.
  R1 is now pointing at MC_INVALID_VAL which is the next value for R4
  Two chains are affected this way [1] and [2]:
  hash[1] -> 0x12(R1) -> MC_INVALID_VAL
  hash[2] -> 0x12(R1) -> MC_INVALID_VAL
- We are done, no more elements on hash[1]

So the final status for step 5 (removal of R2) now is:
hash[1] -> 0x12(R1) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> 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 

Now we remove R3 (4, 3), which is a quite simple operation:

hash[1] -> 0x12(R1) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> MC_INVALID_VAL
hash[3] -> 0x54(R4) -> MC_INVALID_VAL
hash[4] -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL 

We have to do revalidation for chains [4], [3]

First we do hash[4]
- First entry is R4 (5, 4), 4 matches so we keep it.
  And now the chains to match are [4, 5] ([4] + (5, 4))
- We are done, no more elements on hash[4] 

Then we do hash[3]
- First entry is R4 (5, 4), it does *NOT* match any, so
  we skip it, which means pointing the head to MC_INVALID_VAL
  hash[3] -> MC_INVALID_VAL
- We are done, no more elements on hash[3] 

Final status after step 6 is:
hash[1] -> 0x12(R1) -> MC_INVALID_VAL
hash[2] -> 0x12(R1) -> MC_INVALID_VAL
hash[3] -> MC_INVALID_VAL
hash[4] -> 0x54(R4) -> MC_INVALID_VAL
hash[5] -> 0x54(R4) -> MC_INVALID_VAL 

Which is the correct status.
So re-validation of chains solves the problem as I had originally
proposed a few patches ago :)

Simo.

-- 
Simo Sorce * Red Hat, Inc * New York




More information about the sssd-devel mailing list