[SSSD] [PATCH] mmap_cache: Use prime muber for size of hash table.

Lukas Slebodnik lslebodn at redhat.com
Mon Aug 19 11:35:44 UTC 2013


ehlo,

yet another patch to improve mmap_cache.

LS
-------------- next part --------------
>From 34787a11354b199f9562e8a3d530aae206f00d29 Mon Sep 17 00:00:00 2001
From: Lukas Slebodnik <lslebodn at redhat.com>
Date: Mon, 19 Aug 2013 13:02:57 +0200
Subject: [PATCH] mmap_cache: Use prime muber for size of hash table.

Hash funsction sss_ms_hash is calculated as
  murmurhash3 % HT_ELEMS(mcc->ht_size)

If size of hash table(HT_ELEMS(mcc->ht_size)) is prime number,
probability of hash collision will be lower.
---
 src/responder/nss/nsssrv_mmap_cache.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/src/responder/nss/nsssrv_mmap_cache.c b/src/responder/nss/nsssrv_mmap_cache.c
index e053e1631f9624987c255534d09df8a3db2309e3..dfd2af6d04c76e1e8828acd08c7e060ed498de4b 100644
--- a/src/responder/nss/nsssrv_mmap_cache.c
+++ b/src/responder/nss/nsssrv_mmap_cache.c
@@ -1150,6 +1150,17 @@ static int mc_ctx_destructor(struct sss_mc_ctx *mc_ctx)
     return 0;
 }
 
+static bool sss_is_prime(uint32_t num) {
+    uint32_t i = 2;
+    while (i*i < num) {
+        if (num % i == 0) {
+            return false;
+        }
+        ++i;
+    }
+    return true;;
+}
+
 errno_t sss_mmap_cache_init(TALLOC_CTX *mem_ctx, const char *name,
                             enum sss_mc_type type, size_t n_elem,
                             time_t timeout, struct sss_mc_ctx **mcc)
@@ -1158,6 +1169,7 @@ errno_t sss_mmap_cache_init(TALLOC_CTX *mem_ctx, const char *name,
     unsigned int rseed;
     int payload;
     int ret, dret;
+    uint32_t ht_elems;
 
     switch (type) {
     case SSS_MC_PASSWD:
@@ -1201,7 +1213,15 @@ errno_t sss_mmap_cache_init(TALLOC_CTX *mem_ctx, const char *name,
 
     /* hash table is double the size because it will store both forward and
      * reverse keys (name/uid, name/gid, ..) */
-    mc_ctx->ht_size = MC_HT_SIZE(n_elem * 2);
+    ht_elems = n_elem * 2;
+
+    /* If size of hash table is prime number, probability of hash collision
+     * will be lower. */
+    while (!sss_is_prime(ht_elems)) {
+        ++ht_elems;
+    }
+
+    mc_ctx->ht_size = MC_HT_SIZE(ht_elems);
     mc_ctx->dt_size = MC_DT_SIZE(n_elem, payload);
     mc_ctx->ft_size = MC_FT_SIZE(n_elem);
     mc_ctx->mmap_size = MC_HEADER_SIZE +
-- 
1.8.3.1



More information about the sssd-devel mailing list