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@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