From 4662725ffef62b3b2502481438effa7c8fef9f80 Mon Sep 17 00:00:00 2001 From: Lukas Slebodnik Date: Mon, 19 Aug 2013 05:39:28 +0200 Subject: 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 1f584a29..66afe6fd 100644 --- a/src/responder/nss/nsssrv_mmap_cache.c +++ b/src/responder/nss/nsssrv_mmap_cache.c @@ -205,6 +205,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) @@ -222,7 +243,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) { @@ -230,7 +255,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 { -- cgit