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

6 files changed, 83 insertions, 34 deletions

diff --git a/src/responder/nss/nsssrv_mmap_cache.c b/src/responder/nss/nsssrv_mmap_cache.c
index 69fe2078..8655a1a0 100644
--- a/src/responder/nss/nsssrv_mmap_cache.c
+++ b/src/responder/nss/nsssrv_mmap_cache.c
@@ -93,6 +93,34 @@ struct sss_mc_ctx {
     else used = false; \
 } while (0)
 
+static inline
+uint32_t sss_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;
+    }
+}
+
+static inline
+void sss_mc_chain_slot_to_record_with_hash(struct sss_mc_rec *rec,
+                                           uint32_t hash,
+                                           uint32_t slot)
+{
+    /* changing a single uint32_t is atomic, so there is no
+     * need to use barriers in this case */
+    if (rec->hash1 == hash) {
+        rec->next1 = slot;
+    } else if (rec->hash2 == hash) {
+        rec->next2 = slot;
+    }
+}
+
 /* This function will store corrupted memcache to disk for later
  * analysis. */
 static void  sss_mc_save_corrupted(struct sss_mc_ctx *mc_ctx)
@@ -196,13 +224,12 @@ static void sss_mc_add_rec_to_chain(struct sss_mc_ctx *mcc,
             /* rec already stored in hash chain */
             return;
         }
-        slot = cur->next;
+        slot = sss_mc_next_slot_with_hash(cur, hash);
     } while (slot != MC_INVALID_VAL);
     /* end of chain, append our record here */
 
-    /* changing a single uint32_t is atomic, so there is no
-     * need to use barriers in this case */
-    cur->next = MC_PTR_TO_SLOT(mcc->data_table, rec);
+    slot = MC_PTR_TO_SLOT(mcc->data_table, rec);
+    sss_mc_chain_slot_to_record_with_hash(cur, hash, slot);
 }
 
 static void sss_mc_rm_rec_from_chain(struct sss_mc_ctx *mcc,
@@ -230,19 +257,19 @@ 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) {
-        mcc->hash_table[hash] = rec->next;
+        mcc->hash_table[hash] = sss_mc_next_slot_with_hash(rec, hash);
     } else {
-        slot = cur->next;
+        slot = sss_mc_next_slot_with_hash(cur, hash);
         while (slot != MC_INVALID_VAL) {
             prev = cur;
             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 */
-                prev->next = cur->next;
+                slot = sss_mc_next_slot_with_hash(cur, hash);
+
+                sss_mc_chain_slot_to_record_with_hash(prev, hash, slot);
                 slot = MC_INVALID_VAL;
             } else {
-                slot = cur->next;
+                slot = sss_mc_next_slot_with_hash(cur, hash);
             }
         }
     }
@@ -284,7 +311,8 @@ static void sss_mc_invalidate_rec(struct sss_mc_ctx *mcc,
                                         - sizeof(struct sss_mc_rec)));
     rec->len = MC_INVALID_VAL32;
     rec->expire = MC_INVALID_VAL64;
-    rec->next = MC_INVALID_VAL32;
+    rec->next1 = MC_INVALID_VAL32;
+    rec->next2 = MC_INVALID_VAL32;
     rec->hash1 = MC_INVALID_VAL32;
     rec->hash2 = MC_INVALID_VAL32;
     MC_LOWER_BARRIER(rec);
@@ -313,7 +341,7 @@ static bool sss_mc_is_valid_rec(struct sss_mc_ctx *mcc, struct sss_mc_rec *rec)
         return false;
     }
 
-    /* rec->next can be invalid if there are no next records */
+    /* next record can be invalid if there are no next records */
 
     if (rec->hash1 == MC_INVALID_VAL32) {
         return false;
@@ -322,7 +350,7 @@ static bool sss_mc_is_valid_rec(struct sss_mc_ctx *mcc, struct sss_mc_rec *rec)
         slot = mcc->hash_table[rec->hash1];
         while (slot != MC_INVALID_VAL32 && self != rec) {
             self = MC_SLOT_TO_PTR(mcc->data_table, slot, struct sss_mc_rec);
-            slot = self->next;
+            slot = sss_mc_next_slot_with_hash(self, rec->hash1);
         }
         if (self != rec) {
             return false;
@@ -333,7 +361,7 @@ static bool sss_mc_is_valid_rec(struct sss_mc_ctx *mcc, struct sss_mc_rec *rec)
         slot = mcc->hash_table[rec->hash2];
         while (slot != MC_INVALID_VAL32 && self != rec) {
             self = MC_SLOT_TO_PTR(mcc->data_table, slot, struct sss_mc_rec);
-            slot = self->next;
+            slot = sss_mc_next_slot_with_hash(self, rec->hash2);
         }
         if (self != rec) {
             return false;
@@ -527,7 +555,7 @@ static struct sss_mc_rec *sss_mc_find_record(struct sss_mc_ctx *mcc,
             break;
         }
 
-        slot = rec->next;
+        slot = sss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (slot == MC_INVALID_VAL) {
@@ -583,7 +611,9 @@ static errno_t sss_mc_get_record(struct sss_mc_ctx **_mcc,
     /* mark as not valid yet */
     MC_RAISE_INVALID_BARRIER(rec);
     rec->len = rec_len;
-    rec->next = MC_INVALID_VAL;
+    rec->next1 = MC_INVALID_VAL;
+    rec->next2 = MC_INVALID_VAL;
+    rec->padding = MC_INVALID_VAL;
     MC_LOWER_BARRIER(rec);
 
     /* and now mark slots as used */
@@ -769,7 +799,7 @@ errno_t sss_mmap_cache_pw_invalidate_uid(struct sss_mc_ctx *mcc, uid_t uid)
             break;
         }
 
-        slot = rec->next;
+        slot = sss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (slot == MC_INVALID_VAL) {
@@ -908,7 +938,7 @@ errno_t sss_mmap_cache_gr_invalidate_gid(struct sss_mc_ctx *mcc, gid_t gid)
             break;
         }
 
-        slot = rec->next;
+        slot = sss_mc_next_slot_with_hash(rec, hash);
     }
 
     if (slot == MC_INVALID_VAL) {
diff --git a/src/sss_client/nss_mc.h b/src/sss_client/nss_mc.h
index f3abaab9..685cc41c 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 a0a70abc..db9be94b 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 4e3d9fb0..5610233e 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 a0a8d87f..95b8a040 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)) {
diff --git a/src/util/mmap_cache.h b/src/util/mmap_cache.h
index 7c6693ac..81269fe7 100644
--- a/src/util/mmap_cache.h
+++ b/src/util/mmap_cache.h
@@ -53,15 +53,15 @@ typedef uint32_t rel_ptr_t;
 #define MC_INVALID_VAL MC_INVALID_VAL32
 
 /*
- * 32 seem a good compromise for slot size
+ * 40 seem a good compromise for slot size
  * 4 blocks are enough for the average passwd entry of 42 bytes
- * passwd records have 84 bytes of overhead, 128 - 82 = 46 bytes
- * 3 blocks can contain a very minimal entry, 96 - 82 = 14 bytes
+ * passwd records have 84 bytes of overhead, 160 - 82 = 78 bytes
+ * 3 blocks can contain a very minimal entry, 120 - 82 = 38 bytes
  *
  * 3 blocks are enough for groups w/o users (private user groups)
- * group records have 68 bytes of overhead, 96 - 66 = 30 bytes
+ * group records have 68 bytes of overhead, 120 - 66 = 54 bytes
  */
-#define MC_SLOT_SIZE 32
+#define MC_SLOT_SIZE 40
 #define MC_SIZE_TO_SLOTS(len) (((len) + (MC_SLOT_SIZE - 1)) / MC_SLOT_SIZE)
 #define MC_PTR_TO_SLOT(base, ptr) (MC_PTR_DIFF(ptr, base) / MC_SLOT_SIZE)
 #define MC_SLOT_TO_PTR(base, slot, type) \
@@ -78,8 +78,8 @@ typedef uint32_t rel_ptr_t;
                             - MC_PTR_DIFF(rec, (mc_ctx)->data_table))))
 
 
-#define SSS_MC_MAJOR_VNO    0
-#define SSS_MC_MINOR_VNO    4
+#define SSS_MC_MAJOR_VNO    1
+#define SSS_MC_MINOR_VNO    0
 
 #define SSS_MC_HEADER_UNINIT    0   /* after ftruncate or before reset */
 #define SSS_MC_HEADER_ALIVE     1   /* current and in use */
@@ -106,9 +106,13 @@ struct sss_mc_rec {
     uint32_t b1;            /* barrier 1 */
     uint32_t len;           /* total record length including record data */
     uint64_t expire;        /* record expiration time (cast to time_t) */
-    rel_ptr_t next;         /* ptr of next record rel to data_table */
+    rel_ptr_t next1;        /* ptr of next record rel to data_table */
+                            /* next1 is related to hash1 */
+    rel_ptr_t next2;        /* ptr of next record rel to data_table */
+                            /* next2 is related to hash2 */
     uint32_t hash1;         /* val of first hash (usually name of record) */
     uint32_t hash2;         /* val of second hash (usually id of record) */
+    uint32_t padding;       /* padding & reserved for future changes */
     uint32_t b2;            /* barrier 2 - 32 bytes mark, fits a slot */
     char data[0];
 };