On (19/08/13 16:49), Simo Sorce wrote: >On Mon, 2013-08-19 at 21:05 +0200, Lukas Slebodnik wrote: >> 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. > >After quite some thinking I couldn't find a way to break this, indeed I >guess the only case where a record can remain orphaned and accessible on >a chain is if it is the second record on the chain but brought there >only because it is a next record on another chain, and the first record >on that chain is removed. > >So this new patch seem to address the problem correctly, however I would >like to see comments before bot the critical assignments in the code >that points out that the difference in treatment is intentional (so that >if someone needs to modify the code at a later time he will not 'fix' >the discrepancy bymistake). done.
> >Also I think we need to rewrite the comment of the commit, I still do >not think it is clear enough to convey what the actual issue is. > >What about this: > >"The code uses 2 hashes for each record, but only one hash table to >index them both, furthermore each record has only one single 'next' >pointer. > >This means that in certain conditions a record main end up being on a >hash chain even though its hashes do not match the hash chain. This can >happen when another record 'drags' it in from another hash chain where >they both belong. > >If the record without matching hashes happens to be the second of the >chain and the first record is removed, then the non matching record is >left on the wrong chain. On removal of the non-matching record the hash >chain will not be updated and the hash chain will end up pointing to an >invalid slot. >This slot may be later reused for another record and may not be the >first slot of this new record. In this case the hash chain will point to >arbitrary data and may cause issues if the slot is interpreted as the >head of a record. > >By skipping any block that has no matching hashes upon removing the >first record in a chain we insure that dangling references cannot be >left in the hash table" I am highly influenced by debugging this, so my point of view is not objective. I reused your proposal without any change. I also changed resolves section to https://fedorahosted.org/sssd/ticket/2049, because I used reproducers from BZ997406 and reporter used sssd from master (including Michal's patch). Functionality of 1st patch is not changed. Thank you very much for review. LS
>From 6e95ece6809a8a6c6b4fcddb6e076514dd835857 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 The code uses 2 hashes for each record, but only one hash table to index them both, furthermore each record has only one single 'next' pointer. This means that in certain conditions a record main end up being on a hash chain even though its hashes do not match the hash chain. This can happen when another record 'drags' it in from another hash chain where they both belong. If the record without matching hashes happens to be the second of the chain and the first record is removed, then the non matching record is left on the wrong chain. On removal of the non-matching record the hash chain will not be updated and the hash chain will end up pointing to an invalid slot. This slot may be later reused for another record and may not be the first slot of this new record. In this case the hash chain will point to arbitrary data and may cause issues if the slot is interpreted as the head of a record. By skipping any block that has no matching hashes upon removing the first record in a chain we insure that dangling references cannot be left in the hash table Resolves: https://fedorahosted.org/sssd/ticket/2049 --- src/responder/nss/nsssrv_mmap_cache.c | 36 +++++++++++++++++++++++++++++++++-- 1 file changed, 34 insertions(+), 2 deletions(-) diff --git a/src/responder/nss/nsssrv_mmap_cache.c b/src/responder/nss/nsssrv_mmap_cache.c index fced018ebafb4224b3ea216ec99461538ea878da..522e6fa57640261ff4cc17bf554776d7d905bf7a 100644 --- a/src/responder/nss/nsssrv_mmap_cache.c +++ b/src/responder/nss/nsssrv_mmap_cache.c @@ -196,6 +196,27 @@ static void sss_mc_add_rec_to_chain(struct sss_mc_ctx *mcc, cur->next = MC_PTR_TO_SLOT(mcc->data_table, rec); } +static inline uint32_t +sss_mc_get_next_slot_with_hash(struct sss_mc_ctx *mcc, + struct sss_mc_rec *start_rec, + uint32_t hash) +{ + struct sss_mc_rec *rec; + uint32_t slot; + + slot = start_rec->next; + while (slot != MC_INVALID_VAL) { + rec = MC_SLOT_TO_PTR(mcc->data_table, slot, struct sss_mc_rec); + if (rec->hash1 == hash || rec->hash2 == hash) { + break; + } + + slot = rec->next; + } + + return slot; +} + static void sss_mc_rm_rec_from_chain(struct sss_mc_ctx *mcc, struct sss_mc_rec *rec, uint32_t hash) @@ -213,7 +234,11 @@ static void sss_mc_rm_rec_from_chain(struct sss_mc_ctx *mcc, slot = mcc->hash_table[hash]; cur = MC_SLOT_TO_PTR(mcc->data_table, slot, struct sss_mc_rec); if (cur == rec) { - mcc->hash_table[hash] = rec->next; + /* rec->next can refer to record without matching hashes. + * We need to skip this(those) records, because + * mcc->hash_table[hash] have to refer to valid start of the chain. + */ + mcc->hash_table[hash] = sss_mc_get_next_slot_with_hash(mcc, rec, hash); } else { slot = cur->next; while (slot != MC_INVALID_VAL) { @@ -221,7 +246,14 @@ static void sss_mc_rm_rec_from_chain(struct sss_mc_ctx *mcc, cur = MC_SLOT_TO_PTR(mcc->data_table, slot, struct sss_mc_rec); if (cur == rec) { /* changing a single uint32_t is atomic, so there is no - * need to use barriers in this case */ + * need to use barriers in this case. + * + * This situation is different to the removing record from + * the beggining of the chain. The record have to only be + * removed from chain, because this chain can be + * subset or supperset of another chain and we don't want + * to break another chains. + */ prev->next = cur->next; slot = MC_INVALID_VAL; } else { -- 1.8.3.1
>From 6a6f9c3a48fbfd7c61cd0c6d0aa9b4bf7bdb5fd6 Mon Sep 17 00:00:00 2001 From: Lukas Slebodnik <[email protected]> Date: Mon, 19 Aug 2013 07:24:46 +0200 Subject: [PATCH 2/2] mmap_cache: Use stricter check for hash keys. ht_size is size of hash_table in bytes, but hash keys have type uint32_t --- src/responder/nss/nsssrv_mmap_cache.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/src/responder/nss/nsssrv_mmap_cache.c b/src/responder/nss/nsssrv_mmap_cache.c index 522e6fa57640261ff4cc17bf554776d7d905bf7a..c34997b8034d05796687ff7d380b367d5c7bba06 100644 --- a/src/responder/nss/nsssrv_mmap_cache.c +++ b/src/responder/nss/nsssrv_mmap_cache.c @@ -168,7 +168,7 @@ static void sss_mc_add_rec_to_chain(struct sss_mc_ctx *mcc, struct sss_mc_rec *cur; uint32_t slot; - if (hash > mcc->ht_size) { + if (hash > MC_HT_ELEMS(mcc->ht_size)) { /* Invalid hash. This should never happen, but better * return than trying to access out of bounds memory */ return; @@ -225,9 +225,11 @@ static void sss_mc_rm_rec_from_chain(struct sss_mc_ctx *mcc, struct sss_mc_rec *cur = NULL; uint32_t slot; - if (hash > mcc->ht_size) { - /* Invalid hash. This should never happen, but better - * return than trying to access out of bounds memory */ + if (hash > MC_HT_ELEMS(mcc->ht_size)) { + /* It can happen if rec->hash1 and rec->has2 was the same. + * or it is invalid hash. It is better to return + * than trying to access out of bounds memory + */ return; } -- 1.8.3.1
_______________________________________________ sssd-devel mailing list [email protected] https://lists.fedorahosted.org/mailman/listinfo/sssd-devel
