mmap_cache: Use two chains for hash collision.

struct sss_mc_rec had two hash members (hash1 and hash2) but only one next
member. This was a big problem in case of higher probability of hash collision.

structure sss_mc_rec will have two next members (next1, next2) with this patch.
next1 is related to hash1 and next2 is related to hash1.

Iterating over chains is changed, because we need to choose right next pointer.
Right next pointer will be chosen after comparing record hashes.
This behaviour is wrapped in function sss_mc_next_slot_with_hash.

Adding new record to chain is also changed. The situation is very similar to
iterating. We need to choose right next pointer (next1 or next2).
Right next pointer will be chosen after comparing record hashes.
Adding reference to next slot is wrapped in function
sss_mc_chain_slot_to_record_with_hash

Size of structure sss_mc_rec was increased from 32 bytes to 40 bytes.

Resolves:
https://fedorahosted.org/sssd/ticket/2049

4 files changed, 23 insertions, 8 deletions

diff --git a/src/sss_client/nss_mc.h b/src/sss_client/nss_mc.h
index f3abaab9c..685cc41c0 100644
--- a/src/sss_client/nss_mc.h
+++ b/src/sss_client/nss_mc.h
@@ -58,6 +58,8 @@ errno_t sss_nss_mc_get_record(struct sss_cli_mc_ctx *ctx,
                               uint32_t slot, struct sss_mc_rec **_rec);
 errno_t sss_nss_str_ptr_from_buffer(char **str, void **cookie,
                                     char *buf, size_t len);
+uint32_t sss_nss_mc_next_slot_with_hash(struct sss_mc_rec *rec,
+                                        uint32_t hash);
 
 /* passwd db */
 errno_t sss_nss_mc_getpwnam(const char *name, size_t name_len,
diff --git a/src/sss_client/nss_mc_common.c b/src/sss_client/nss_mc_common.c
index a0a70abc0..db9be94b4 100644
--- a/src/sss_client/nss_mc_common.c
+++ b/src/sss_client/nss_mc_common.c
@@ -291,3 +291,16 @@ errno_t sss_nss_str_ptr_from_buffer(char **str, void **cookie,
     return 0;
 }
 
+uint32_t sss_nss_mc_next_slot_with_hash(struct sss_mc_rec *rec,
+                                        uint32_t hash)
+{
+    if (rec->hash1 == hash) {
+        return rec->next1;
+    } else if (rec->hash2 == hash) {
+        return rec->next2;
+    } else {
+        /* it should never happen. */
+        return MC_INVALID_VAL;
+    }
+
+}
diff --git a/src/sss_client/nss_mc_group.c b/src/sss_client/nss_mc_group.c
index 4e3d9fb0d..5610233ed 100644
--- a/src/sss_client/nss_mc_group.c
+++ b/src/sss_client/nss_mc_group.c
@@ -130,7 +130,7 @@ errno_t sss_nss_mc_getgrnam(const char *name, size_t name_len,
         /* check record matches what we are searching for */
         if (hash != rec->hash1) {
             /* if name hash does not match we can skip this immediately */
-            slot = rec->next;
+            slot = sss_nss_mc_next_slot_with_hash(rec, hash);
             continue;
         }
 
@@ -152,7 +152,7 @@ errno_t sss_nss_mc_getgrnam(const char *name, size_t name_len,
             break;
         }
 
-        slot = rec->next;
+        slot = sss_nss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (!MC_SLOT_WITHIN_BOUNDS(slot, gr_mc_ctx.dt_size)) {
@@ -205,7 +205,7 @@ errno_t sss_nss_mc_getgrgid(gid_t gid,
         /* check record matches what we are searching for */
         if (hash != rec->hash2) {
             /* if uid hash does not match we can skip this immediately */
-            slot = rec->next;
+            slot = sss_nss_mc_next_slot_with_hash(rec, hash);
             continue;
         }
 
@@ -214,7 +214,7 @@ errno_t sss_nss_mc_getgrgid(gid_t gid,
             break;
         }
 
-        slot = rec->next;
+        slot = sss_nss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (!MC_SLOT_WITHIN_BOUNDS(slot, gr_mc_ctx.dt_size)) {
diff --git a/src/sss_client/nss_mc_passwd.c b/src/sss_client/nss_mc_passwd.c
index a0a8d87f7..95b8a0407 100644
--- a/src/sss_client/nss_mc_passwd.c
+++ b/src/sss_client/nss_mc_passwd.c
@@ -131,7 +131,7 @@ errno_t sss_nss_mc_getpwnam(const char *name, size_t name_len,
         /* check record matches what we are searching for */
         if (hash != rec->hash1) {
             /* if name hash does not match we can skip this immediately */
-            slot = rec->next;
+            slot = sss_nss_mc_next_slot_with_hash(rec, hash);
             continue;
         }
 
@@ -154,7 +154,7 @@ errno_t sss_nss_mc_getpwnam(const char *name, size_t name_len,
             break;
         }
 
-        slot = rec->next;
+        slot = sss_nss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (!MC_SLOT_WITHIN_BOUNDS(slot, pw_mc_ctx.dt_size)) {
@@ -207,7 +207,7 @@ errno_t sss_nss_mc_getpwuid(uid_t uid,
         /* check record matches what we are searching for */
         if (hash != rec->hash2) {
             /* if uid hash does not match we can skip this immediately */
-            slot = rec->next;
+            slot = sss_nss_mc_next_slot_with_hash(rec, hash);
             continue;
         }
 
@@ -216,7 +216,7 @@ errno_t sss_nss_mc_getpwuid(uid_t uid,
             break;
         }
 
-        slot = rec->next;
+        slot = sss_nss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (!MC_SLOT_WITHIN_BOUNDS(slot, pw_mc_ctx.dt_size)) {