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

1 files 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 {