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)
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
LS