2:05 p.m.
On (19/08/13 11:20), Simo Sorce wrote:
On Mon, 2013-08-19 at 14:58 +0200, Lukas Slebodnik wrote:
> On (19/08/13 07:58), Lukas Slebodnik wrote:
> >ehlo,
> >
> >detail description in attached patches.
> >
> >LS
>
> >From 295dd1e0966df7bf1fc9a51f84a0daa81a279b5e Mon Sep 17 00:00:00 2001
> >From: Lukas Slebodnik <lslebodn(a)redhat.com>
> >Date: Mon, 19 Aug 2013 05:39:28 +0200
> >Subject: [PATCH 1/2] mmap_cache: Skip records which doesn't have same hash
> >
> >Record in data table has two hashes hash1 and hash2. Hash table refers
> >to the first record with the searched hash key. We do a record chaining
> >in case of hash collision.
> >
> >When we removed record from cache hash_table was automaticaly updated to
> >the next record from chain. But it is not very likely that two following
> >records will have the same hashes (hash1 and hash2). Therefore it can happen,
> >that some hash table keys refers to records, which both hashes has different
> >values like hash key. Such record can be removed from memory cache,
> >but there will be reference in hash table with different key, which could
> >not be removed, but it points to removed data or in the worst case
> >it points in the middle of newly added record. And this was a reason
> >of crash in nss.
> >
>
> I will try to write example of this behaviour.
>
> 1. Adding new record with R1(hash1:111, hash2:222, next:INVALID_VAL)
> --record R1 will be added to data table to slot with index:0
> --hash keys fom record R1 will refer to slot_0
> hash_table[111] refers to slot_0
> hash_table[222] refers to slot_0
>
> 2. Adding another record R2(hash1:111, hash2:333, next:INVALID_VAL)
> --record R1 will be added to data table to the free slot with index:3
> --there is collision of hash key 111
> hash_table[111] will still refers to slot0, but we will add R2 to chain
> R1->next will refer to slot_3 (R2 is stored ins slot_3)
> hash_table[333] refers to slot_3 (there was no colision)
>
> 3. Removing R1
> --remove records from chains using R1->hash{1,2} (sss_mc_rm_rec_from_chain)
> in this situation hash_table[R1->hash1] and hash_table[R1->hash2] refers
> directly to R1, It is just a simplification of this example.
> --set hash_table[R1->hash1] to R1->next
> hash_table[111] will refer to slot_3
> --set hash_table[R1->hash2] to R1->next
> hash_table[222] will refer to slot_3
>
> Current situation:
> hash_table[111] refers to slot_3(R2)
> hash_table[222] refers to slot_3(R2)
> hash_table[333] refers to slot_3(R2)
Ah yeah it is a mistake that [222] here still holds a reference to R2,
as R2 has no such hash.
> 4. Removing R2.
> --remove rerords from chain using R2->hash{1,2}
> R2->next has value INVALID_VAL (there is not another record after R2)
> --set hash_table[R2->hash1] to R2->next (INVALID_VAL)
> hash_table[111] will refer to empty slot
> --set hash_table[R2->hash2] to R2->next (INVALID_VAL)
> hash_table[333] will refer to empty slot
>
> Current situation:
> hash_table[222] refers to slot_3 (but R2 was removed).
>
> 5. Adding new record R3(hash1: 999, hash2: 888, next:INVALID_VAL)
> this record is very log (10 slots) and it will be added to
> the first empty slot. (slot_0). This is just a simplification, because
> algorithm is different, but it can happen.
>
>
> Current situation:
> hash_table[888] refers to slot_0(R3)
> hash_table[999] refers to slot_0(R3)
> hash_table[222] refers to slot_3 (in the middle of R3).
> ^^^^^^^^^^^^^^^
> possible crash
Indeed, and I am sure this is how one of the crashes where we had stuff
pointing in the middle of a multi-slot field happened.
Thanks a lot for catching this.
However I am not completely sure the solution works correctly, I suspect
it may cause orphans.
Let me work out here an example and let's see where it leads.
Assume we have a high collision rate, and the following records are
added in order (the next lines are { record-id, slot1, slot2 }
R1, 111, 222
R2, 222, 333
R3, 111, 333
R4, 333, 444
R5, 222, 333
The hash chains look like after each insertion step (hash1/slot1 is
inserted first):
1.
[111] -> R1
[222] -> R1
[333]
[444]
2.
[111] -> R1 -> R2
[222] -> R1 -> R2
[333] -> R2
[444]
note how having only 1 ->next in the record causes duplication in the
chains, this is accounted for in the code already, it just makes the
flow a little bit messier and harder to follow unfortunately.
3.
[111] -> R1 -> R2 -> R3
[222] -> R1 -> R2 -> R3
[333] -> R2 -> R3
[444]
4.
[111] -> R1 -> R2 -> R3 -> R4
[222] -> R1 -> R2 -> R3 -> R4
[333] -> R2 -> R3 -> R4
[444] -> R4
5.
[111] -> R1 -> R2 -> R3 -> R4 -> R5
[222] -> R1 -> R2 -> R3 -> R4 -> R5
[333] -> R2 -> R3 -> R4 -> R5
[444] -> R4 -> R5
Original table for easier reference in next step:
R1, 111, 222
R2, 222, 333
R3, 111, 333
R4, 333, 444
R5, 222, 333
Now let's try to remove R2.
The first step with your patch checks if the hashes of next record (R3)
matches the current hash chain hash.
The first hash chain we check when removing R2 is [222], and R3 has
[111], [333], so it doesn't match, and is skipped.
The second step checks R4 that has 333, 444, again no match.
The third step matches R5 as it is also in the 222 chain.
So what we do is that we set the next record of R1 (which is R2's
previous record in chain [222] to R5.
After removing R2 from first chain:
[111] -> R1 -> R5
[222] -> R1 -> R5
[333] -> R2 -> R3 -> R4 -> R5
[444] -> R4 -> R5
Then we look at the second hash chain of R2 which is [333]
We check R3, which is again the next record to see if it is a record
that belongs to [333] by matching R3's hashes (111, 333). It does, so we
just set [333] to point directly at R3 as R2 was its first element.
This is how finally the chains look:
[111] -> R1 -> R5
[222] -> R1 -> R5
[333] -> R3 -> R4 -> R5
[444] -> R4 -> R5
As you can see they are not correct.
These are the remaining records:
R1, 111, 222
R3, 111, 333
R4, 333, 444
R5, 222, 333
R1 is properly linked by both chains.
R3 is not linked in 111 as it should.
R4 and R5 are referenced by both their chains.
So R3 now is 'lost' on one chain.
The problem here is that we are doing separate removals, but are not
considering the shared nature of the 'next' pointer when it comes to the
affected chains.
I think we should instead use the original approach to remove chains,
but then re-validate them:
Original table for easier reference in next step:
R1, 111, 222
R2, 222, 333
R3, 111, 333
R4, 333, 444
R5, 222, 333
Original status with all Record chained:
[111] -> R1 -> R2 -> R3 -> R4 -> R5
[222] -> R1 -> R2 -> R3 -> R4 -> R5
[333] -> R2 -> R3 -> R4 -> R5
[444] -> R4 -> R5
Let's remove R4 this time (chose R4 because it leaves a reference to R5
in the [444] as an orphan with the original method).
Removing R4 (from chains 333 and 444) with the original method leaves
this table:
[111] -> R1 -> R2 -> R3 -> R5
[222] -> R1 -> R2 -> R3 -> R5
[333] -> R2 -> R3 -> R5
[444] -> R5
After removal from both the chains R4 referred to we revalidate them (ie
we only revalidate 333 and 444:
First we revalidate [333], which has -> R2 -> R3 -> R5 as a chain.
R2 does have 333 as hash so it is valid
The next step needs to insure that the link R2 -> R5 makes sense. It
makes sense if any of the previous record hashes are matched.
So for the second step we need to match [333] plus R2's own hashes {222,
333}.
The list to match is therefore {222, 333} and R3 matches it with 333.
For the next record the list to match is {111, 333} + {222, 333}, or
{111, 222, 333}, and R5 matches and is the last element.
The chain is revalidated
The second chain to check is [444], which has only -> R5
R5 (222, 333) does not match, so we set [444] to R5->next, and continue.
Turns out R5 was the last element in the chain so [444] is empty.
Final situation after revalidation:
[111] -> R1 -> R2 -> R3 -> R5
[222] -> R1 -> R2 -> R3 -> R5
[333] -> R2 -> R3 -> R5
[444]
This algorithm seem to work with the R4 removal case (and your example
too).
It's a bit annoying to doi the validation for long chains as it requires
a dynamic array of hash values to test ->next elements against,
optimizations in there would be a nice to have if we can come up with
any.
Simo.
MAIN_PROBLEM: We know that main problem is when hash table entry referes
to record, which hashes are different.
(hash_key != rec->hash1 && hash_key != rec->hash2)
This can only happend if data in hash table are changed. Data in hash table can
be changed in two situation (adding record, removing record)
A) Adding record to hash table:
1) hash_table[hash_key] == MC_INVALID VAL
there is no record for hash_key and we can safely refer to new record.
hash_table[hash_key] refers to valid first record.
MAIN_PROBLEM cannot occur in this situation.
2) hash_table[hash_key] refers to valid object.
adding record to chain.
hash_table[hash_key] refers to valid record.
MAIN_PROBLEM cannot occur in this situation.
AS we can see, there is no problem with adding record to hash table.
B) Removing record from hash table
We need to remove record from chain (function sss_mc_rm_rec_from_chain)
1) Record is the first in chain and *HAS NOT* successor
(rec->next == MC_INVALID_VAL)
hash_table[hash_key] will be set to MC_INVALID_VAL
this mean that there is no record for hash_key.
MAIN_PROBLEM cannot occur in this situation.
2) Record is the first in chain and *HAS* successor
hash_table[hash_key] will be set to rec->next
*** MAIN_PROBLEM can occur ***
This will not be problem with attached patch
3) Record is in the middle of chain.
record will be removed from chain. (nothing else)
hash_table[hash_key] refers to valid record, because
1st record is untouched.
MAIN_PROBLEM cannot occur in this situation.
4) Record is at the end of chain.
The situation is the same as in previous point.
MAIN_PROBLEM cannot occur in this situation.
We can see that only one operation is problematic (B3).
Attached patch fixes this problematic situation. Chains will not be changed.
on hash_table[hash_key] will refer to first valid record after removed record.
Simo, thank you very much for review. I hope this version is correct.
LS