From c1c8dba96ef13bfc8725a5142d751601c48c6719 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Fri, 8 Apr 2016 22:04:36 +0100 Subject: [PATCH] [Feature] Use heap in LRU caches Signed-off-by: Vsevolod Stakhov --- src/fuzzy_storage.c | 4 +- src/libcryptobox/keypairs_cache.c | 2 +- src/libutil/hash.c | 90 ++++--------------------------- src/libutil/hash.h | 16 ++---- src/plugins/dkim_check.c | 12 +---- src/plugins/spf.c | 21 +------- 6 files changed, 21 insertions(+), 124 deletions(-) diff --git a/src/fuzzy_storage.c b/src/fuzzy_storage.c index 4ab92cc9f..f43cb3f44 100644 --- a/src/fuzzy_storage.c +++ b/src/fuzzy_storage.c @@ -1162,7 +1162,7 @@ fuzzy_parse_keypair (rspamd_mempool_t *pool, key->key = kp; keystat = g_slice_alloc0 (sizeof (*keystat)); /* Hash of ip -> fuzzy_key_stat */ - keystat->last_ips = rspamd_lru_hash_new_full (0, 1024, + keystat->last_ips = rspamd_lru_hash_new_full (1024, (GDestroyNotify)rspamd_inet_address_destroy, fuzzy_key_stat_dtor, rspamd_inet_address_hash, rspamd_inet_address_equal); key->stat = keystat; @@ -1213,7 +1213,7 @@ init_fuzzy (struct rspamd_config *cfg) ctx->keypair_cache_size = DEFAULT_KEYPAIR_CACHE_SIZE; ctx->keys = g_hash_table_new_full (fuzzy_kp_hash, fuzzy_kp_equal, NULL, fuzzy_key_dtor); - ctx->errors_ips = rspamd_lru_hash_new_full (0, 1024, + ctx->errors_ips = rspamd_lru_hash_new_full (1024, (GDestroyNotify) rspamd_inet_address_destroy, g_free, rspamd_inet_address_hash, rspamd_inet_address_equal); diff --git a/src/libcryptobox/keypairs_cache.c b/src/libcryptobox/keypairs_cache.c index a259c2ac1..069158789 100644 --- a/src/libcryptobox/keypairs_cache.c +++ b/src/libcryptobox/keypairs_cache.c @@ -63,7 +63,7 @@ rspamd_keypair_cache_new (guint max_items) g_assert (max_items > 0); c = g_slice_alloc (sizeof (*c)); - c->hash = rspamd_lru_hash_new_full (max_items, -1, NULL, + c->hash = rspamd_lru_hash_new_full (max_items, NULL, rspamd_keypair_destroy, rspamd_keypair_hash, rspamd_keypair_equal); return c; diff --git a/src/libutil/hash.c b/src/libutil/hash.c index b41177e63..fc6c9cda2 100644 --- a/src/libutil/hash.c +++ b/src/libutil/hash.c @@ -26,9 +26,8 @@ struct rspamd_lru_hash_s { gint maxage; GDestroyNotify value_destroy; GDestroyNotify key_destroy; - + struct rspamd_min_heap *heap; GHashTable *tbl; - GQueue *exp; /* Elements are inserted to the tail and removed from the front */ }; static void @@ -43,9 +42,6 @@ rspamd_lru_destroy_node (gpointer value) if (elt->hash && elt->hash->value_destroy) { elt->hash->value_destroy (elt->data); } - if (elt->hash && elt->link) { - g_queue_delete_link (elt->hash->exp, elt->link); - } g_slice_free1 (sizeof (*elt), elt); } @@ -63,8 +59,8 @@ rspamd_lru_create_node (rspamd_lru_hash_t *hash, node = g_slice_alloc (sizeof (rspamd_lru_element_t)); node->data = value; node->key = key; - node->store_time = now; node->ttl = ttl; + node->helt.pri = now; node->hash = hash; return node; @@ -73,7 +69,6 @@ rspamd_lru_create_node (rspamd_lru_hash_t *hash, rspamd_lru_hash_t * rspamd_lru_hash_new_full ( gint maxsize, - gint maxage, GDestroyNotify key_destroy, GDestroyNotify value_destroy, GHashFunc hf, @@ -83,8 +78,7 @@ rspamd_lru_hash_new_full ( new = g_slice_alloc (sizeof (rspamd_lru_hash_t)); new->tbl = g_hash_table_new_full (hf, cmpf, NULL, rspamd_lru_destroy_node); - new->exp = g_queue_new (); - new->maxage = maxage; + new->heap = rspamd_min_heap_create (maxsize); new->maxsize = maxsize; new->value_destroy = value_destroy; new->key_destroy = key_destroy; @@ -95,11 +89,10 @@ rspamd_lru_hash_new_full ( rspamd_lru_hash_t * rspamd_lru_hash_new ( gint maxsize, - gint maxage, GDestroyNotify key_destroy, GDestroyNotify value_destroy) { - return rspamd_lru_hash_new_full (maxsize, maxage, + return rspamd_lru_hash_new_full (maxsize, key_destroy, value_destroy, rspamd_strcase_hash, rspamd_strcase_equal); } @@ -108,44 +101,18 @@ gpointer rspamd_lru_hash_lookup (rspamd_lru_hash_t *hash, gconstpointer key, time_t now) { rspamd_lru_element_t *res; - GList *cur, *tmp; res = g_hash_table_lookup (hash->tbl, key); if (res != NULL) { if (res->ttl != 0) { - if (now - res->store_time > res->ttl) { + if (((guint)now) - res->helt.pri > res->ttl) { + rspamd_min_heap_remove_elt (hash->heap, &res->helt); g_hash_table_remove (hash->tbl, key); return NULL; } } - if (hash->maxage > 0) { - if (now - res->store_time > hash->maxage) { - /* Expire elements from queue head */ - cur = hash->exp->head; - while (cur) { - tmp = cur->next; - res = (rspamd_lru_element_t *)cur->data; - - if (now - res->store_time > hash->maxage) { - /* That would also remove element from the queue */ - g_hash_table_remove (hash->tbl, res->key); - } - else { - break; - } - - cur = tmp; - } - return NULL; - } - } - else { - res->store_time = now; - /* Reinsert element to the tail */ - g_queue_unlink (hash->exp, res->link); - g_queue_push_tail_link (hash->exp, res->link); - } + rspamd_min_heap_update_elt (hash->heap, &res->helt, now); return res->data; } @@ -158,8 +125,6 @@ rspamd_lru_hash_insert (rspamd_lru_hash_t *hash, gpointer key, gpointer value, time_t now, guint ttl) { rspamd_lru_element_t *res; - gint removed = 0; - GList *cur, *tmp; res = g_hash_table_lookup (hash->tbl, key); if (res != NULL) { @@ -168,44 +133,21 @@ rspamd_lru_hash_insert (rspamd_lru_hash_t *hash, gpointer key, gpointer value, else { if (hash->maxsize > 0 && (gint)g_hash_table_size (hash->tbl) >= hash->maxsize) { - /* Expire some elements */ - if (hash->maxage > 0) { - cur = hash->exp->head; - while (cur) { - tmp = cur->next; - res = (rspamd_lru_element_t *)cur->data; - - if (now - res->store_time > hash->maxage) { - /* That would also remove element from the queue */ - g_hash_table_remove (hash->tbl, res->key); - removed ++; - } - else { - break; - } - - cur = tmp; - } - } - if (removed == 0) { - /* Just unlink the element at the head */ - res = (rspamd_lru_element_t *)hash->exp->head->data; - g_hash_table_remove (hash->tbl, res->key); - } + res = (rspamd_lru_element_t *)rspamd_min_heap_pop (hash->heap); + g_hash_table_remove (hash->tbl, res->key); } } res = rspamd_lru_create_node (hash, key, value, now, ttl); g_hash_table_insert (hash->tbl, key, res); - g_queue_push_tail (hash->exp, res); - res->link = hash->exp->tail; + rspamd_min_heap_push (hash->heap, &res->helt); } void rspamd_lru_hash_destroy (rspamd_lru_hash_t *hash) { + rspamd_min_heap_destroy (hash->heap); g_hash_table_unref (hash->tbl); - g_queue_free (hash->exp); g_slice_free1 (sizeof (rspamd_lru_hash_t), hash); } @@ -215,13 +157,3 @@ rspamd_lru_hash_get_htable (rspamd_lru_hash_t *hash) { return hash->tbl; } - -GQueue * -rspamd_lru_hash_get_queue (rspamd_lru_hash_t *hash) -{ - return hash->exp; -} - -/* - * vi:ts=4 - */ diff --git a/src/libutil/hash.h b/src/libutil/hash.h index 62005f9f8..a7a2a3a26 100644 --- a/src/libutil/hash.h +++ b/src/libutil/hash.h @@ -8,18 +8,17 @@ #define RSPAMD_HASH_H #include "config.h" +#include "heap.h" struct rspamd_lru_hash_s; typedef struct rspamd_lru_hash_s rspamd_lru_hash_t; typedef struct rspamd_lru_element_s { + struct rspamd_min_heap_elt helt; + guint ttl; gpointer data; gpointer key; - time_t store_time; - guint ttl; rspamd_lru_hash_t *hash; - GList *link; - } rspamd_lru_element_t; @@ -33,7 +32,6 @@ typedef struct rspamd_lru_element_s { */ rspamd_lru_hash_t * rspamd_lru_hash_new ( gint maxsize, - gint maxage, GDestroyNotify key_destroy, GDestroyNotify value_destroy); @@ -48,7 +46,6 @@ rspamd_lru_hash_t * rspamd_lru_hash_new ( */ rspamd_lru_hash_t * rspamd_lru_hash_new_full ( gint maxsize, - gint maxage, GDestroyNotify key_destroy, GDestroyNotify value_destroy, GHashFunc hfunc, @@ -86,13 +83,6 @@ void rspamd_lru_hash_destroy (rspamd_lru_hash_t *hash); * Get hash table for this lru hash (use rspamd_lru_element_t as data) */ GHashTable *rspamd_lru_hash_get_htable (rspamd_lru_hash_t *hash); - - -/** - * Get expire queue for this lru hash (use rspamd_lru_element_t as data) - */ -GQueue *rspamd_lru_hash_get_queue (rspamd_lru_hash_t *hash); - #endif /* diff --git a/src/plugins/dkim_check.c b/src/plugins/dkim_check.c index 7852ddd6c..ee62eb50e 100644 --- a/src/plugins/dkim_check.c +++ b/src/plugins/dkim_check.c @@ -222,7 +222,7 @@ dkim_module_config (struct rspamd_config *cfg) const ucl_object_t *value; const gchar *str; gint res = TRUE, cb_id; - guint cache_size, cache_expire; + guint cache_size; gboolean got_trusted = FALSE; if (!rspamd_config_is_module_enabled (cfg, "dkim")) { @@ -261,14 +261,7 @@ dkim_module_config (struct rspamd_config *cfg) else { cache_size = DEFAULT_CACHE_SIZE; } - if ((value = - rspamd_config_get_module_opt (cfg, "dkim", - "dkim_cache_expire")) != NULL) { - cache_expire = ucl_obj_todouble (value); - } - else { - cache_expire = DEFAULT_CACHE_MAXAGE; - } + if ((value = rspamd_config_get_module_opt (cfg, "dkim", "time_jitter")) != NULL) { dkim_module_ctx->time_jitter = ucl_obj_todouble (value); @@ -364,7 +357,6 @@ dkim_module_config (struct rspamd_config *cfg) dkim_module_ctx->dkim_hash = rspamd_lru_hash_new ( cache_size, - cache_expire, g_free, /* Keys are just C-strings */ dkim_module_key_dtor); diff --git a/src/plugins/spf.c b/src/plugins/spf.c index edad4bfc9..a71958b4c 100644 --- a/src/plugins/spf.c +++ b/src/plugins/spf.c @@ -153,15 +153,6 @@ spf_module_init (struct rspamd_config *cfg, struct module_ctx **ctx) 0, NULL, 0); - rspamd_rcl_add_doc_by_path (cfg, - "spf", - "Maximum lifetime for the elements in the SPF cache", - "spf_cache_expire", - UCL_TIME, - NULL, - 0, - NULL, - 0); return 0; } @@ -172,7 +163,7 @@ spf_module_config (struct rspamd_config *cfg) { const ucl_object_t *value; gint res = TRUE, cb_id; - guint cache_size, cache_expire; + guint cache_size; const gchar *str; if (!rspamd_config_is_module_enabled (cfg, "spf")) { @@ -216,14 +207,7 @@ spf_module_config (struct rspamd_config *cfg) else { cache_size = DEFAULT_CACHE_SIZE; } - if ((value = - rspamd_config_get_module_opt (cfg, "spf", - "spf_cache_expire")) != NULL) { - cache_expire = ucl_obj_toint (value); - } - else { - cache_expire = DEFAULT_CACHE_MAXAGE; - } + if ((value = rspamd_config_get_module_opt (cfg, "spf", "whitelist")) != NULL) { @@ -265,7 +249,6 @@ spf_module_config (struct rspamd_config *cfg) spf_module_ctx->spf_hash = rspamd_lru_hash_new ( cache_size, - cache_expire, NULL, (GDestroyNotify)spf_record_unref); -- 2.39.5