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 <[email protected]> >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 _______________________________________________ sssd-devel mailing list [email protected] https://lists.fedorahosted.org/mailman/listinfo/sssd-devel
