[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