1 files changed, 481 insertions, 0 deletions

diff --git a/src/auth/auth-cache.c b/src/auth/auth-cache.c
new file mode 100644
index 0000000..e8aa105
--- /dev/null
+++ b/src/auth/auth-cache.c
@@ -0,0 +1,481 @@
+/* Copyright (c) 2004-2018 Dovecot authors, see the included COPYING file */
+
+#include "auth-common.h"
+#include "lib-signals.h"
+#include "hash.h"
+#include "str.h"
+#include "strescape.h"
+#include "var-expand.h"
+#include "auth-request.h"
+#include "auth-cache.h"
+
+#include <time.h>
+
+struct auth_cache {
+	HASH_TABLE(char *, struct auth_cache_node *) hash;
+	struct auth_cache_node *head, *tail;
+
+	size_t max_size, size_left;
+	unsigned int ttl_secs, neg_ttl_secs;
+
+	unsigned int hit_count, miss_count;
+	unsigned int pos_entries, neg_entries;
+	unsigned long long pos_size, neg_size;
+};
+
+static bool
+auth_request_var_expand_tab_find(const char *key, unsigned int size,
+				 unsigned int *idx_r)
+{
+	const struct var_expand_table *tab = auth_request_var_expand_static_tab;
+	unsigned int i;
+
+	for (i = 0; tab[i].key != '\0' || tab[i].long_key != NULL; i++) {
+		if (size == 1) {
+			if (key[0] == tab[i].key) {
+				*idx_r = i;
+				return TRUE;
+			}
+		} else if (tab[i].long_key != NULL) {
+			if (strncmp(key, tab[i].long_key, size) == 0 &&
+			    tab[i].long_key[size] == '\0') {
+				*idx_r = i;
+				return TRUE;
+			}
+		}
+	}
+	return FALSE;
+}
+
+static void
+auth_cache_key_add_var(string_t *str, const char *data, unsigned int len)
+{
+	if (str_len(str) > 0)
+		str_append_c(str, '\t');
+	str_append_c(str, '%');
+	if (len == 1)
+		str_append_c(str, data[0]);
+	else {
+		str_append_c(str, '{');
+		str_append_data(str, data, len);
+		str_append_c(str, '}');
+	}
+}
+
+static void auth_cache_key_add_tab_idx(string_t *str, unsigned int i)
+{
+	const struct var_expand_table *tab =
+		&auth_request_var_expand_static_tab[i];
+
+	if (str_len(str) > 0)
+		str_append_c(str, '\t');
+	str_append_c(str, '%');
+	if (tab->key != '\0')
+		str_append_c(str, tab->key);
+	else {
+		str_append_c(str, '{');
+		str_append(str, tab->long_key);
+		str_append_c(str, '}');
+	}
+}
+
+char *auth_cache_parse_key(pool_t pool, const char *query)
+{
+	string_t *str;
+	bool key_seen[AUTH_REQUEST_VAR_TAB_COUNT];
+	const char *extra_vars;
+	unsigned int i, idx, size, tab_idx;
+
+	memset(key_seen, 0, sizeof(key_seen));
+
+	str = t_str_new(32);
+	for (; *query != '\0'; ) {
+		if (*query != '%') {
+			query++;
+			continue;
+		}
+
+		var_get_key_range(++query, &idx, &size);
+		if (size == 0) {
+			/* broken %variable ending too early */
+			break;
+		}
+		query += idx;
+
+		if (!auth_request_var_expand_tab_find(query, size, &tab_idx)) {
+			/* just add the key. it would be nice to prevent
+			   duplicates here as well, but that's just too
+			   much trouble and probably very rare. */
+			auth_cache_key_add_var(str, query, size);
+		} else {
+			i_assert(tab_idx < N_ELEMENTS(key_seen));
+			key_seen[tab_idx] = TRUE;
+		}
+		query += size;
+	}
+
+	if (key_seen[AUTH_REQUEST_VAR_TAB_USERNAME_IDX] &&
+	    key_seen[AUTH_REQUEST_VAR_TAB_DOMAIN_IDX]) {
+		/* %n and %d both used -> replace with %u */
+		key_seen[AUTH_REQUEST_VAR_TAB_USER_IDX] = TRUE;
+		key_seen[AUTH_REQUEST_VAR_TAB_USERNAME_IDX] = FALSE;
+		key_seen[AUTH_REQUEST_VAR_TAB_DOMAIN_IDX] = FALSE;
+	}
+
+	/* we rely on these being at the beginning */
+	i_assert(AUTH_REQUEST_VAR_TAB_USER_IDX == 0);
+	i_assert(AUTH_REQUEST_VAR_TAB_USERNAME_IDX == 1);
+	i_assert(AUTH_REQUEST_VAR_TAB_DOMAIN_IDX == 2);
+
+	extra_vars = t_strdup(str_c(str));
+	str_truncate(str, 0);
+	for (i = 0; i < N_ELEMENTS(key_seen); i++) {
+		if (key_seen[i])
+			auth_cache_key_add_tab_idx(str, i);
+	}
+
+	if (*extra_vars != '\0') {
+		if (str_len(str) > 0)
+			str_append_c(str, '\t');
+		str_append(str, extra_vars);
+	}
+
+	return p_strdup(pool, str_c(str));
+}
+
+static void
+auth_cache_node_unlink(struct auth_cache *cache, struct auth_cache_node *node)
+{
+	if (node->prev != NULL)
+		node->prev->next = node->next;
+	else {
+		/* unlinking tail */
+		cache->tail = node->next;
+	}
+
+	if (node->next != NULL)
+		node->next->prev = node->prev;
+	else {
+		/* unlinking head */
+		cache->head = node->prev;
+	}
+}
+
+static void
+auth_cache_node_link_head(struct auth_cache *cache,
+			  struct auth_cache_node *node)
+{
+	node->prev = cache->head;
+	node->next = NULL;
+
+	cache->head = node;
+	if (node->prev != NULL)
+		node->prev->next = node;
+	else
+		cache->tail = node;
+}
+
+static void
+auth_cache_node_destroy(struct auth_cache *cache, struct auth_cache_node *node)
+{
+	char *key = node->data;
+
+	auth_cache_node_unlink(cache, node);
+
+	cache->size_left += node->alloc_size;
+	hash_table_remove(cache->hash, key);
+	i_free(node);
+}
+
+static void sig_auth_cache_clear(const siginfo_t *si ATTR_UNUSED, void *context)
+{
+	struct auth_cache *cache = context;
+
+	i_info("SIGHUP received, %u cache entries flushed",
+	       auth_cache_clear(cache));
+}
+
+static void sig_auth_cache_stats(const siginfo_t *si ATTR_UNUSED, void *context)
+{
+	struct auth_cache *cache = context;
+	unsigned int total_count;
+	size_t cache_used;
+
+	total_count = cache->hit_count + cache->miss_count;
+	i_info("Authentication cache hits %u/%u (%u%%)",
+	       cache->hit_count, total_count,
+	       total_count == 0 ? 100 : (cache->hit_count * 100 / total_count));
+
+	i_info("Authentication cache inserts: "
+	       "positive: %u entries %llu bytes, "
+	       "negative: %u entries %llu bytes",
+	       cache->pos_entries, cache->pos_size,
+	       cache->neg_entries, cache->neg_size);
+
+	cache_used = cache->max_size - cache->size_left;
+	i_info("Authentication cache current size: "
+	       "%zu bytes used of %zu bytes (%u%%)",
+	       cache_used, cache->max_size,
+	       (unsigned int)(cache_used * 100ULL / cache->max_size));
+
+	/* reset counters */
+	cache->hit_count = cache->miss_count = 0;
+	cache->pos_entries = cache->neg_entries = 0;
+	cache->pos_size = cache->neg_size = 0;
+}
+
+struct auth_cache *auth_cache_new(size_t max_size, unsigned int ttl_secs,
+				  unsigned int neg_ttl_secs
+)
+{
+	struct auth_cache *cache;
+
+	cache = i_new(struct auth_cache, 1);
+	hash_table_create(&cache->hash, default_pool, 0, str_hash, strcmp);
+	cache->max_size = max_size;
+	cache->size_left = max_size;
+	cache->ttl_secs = ttl_secs;
+	cache->neg_ttl_secs = neg_ttl_secs;
+
+	lib_signals_set_handler(SIGHUP, LIBSIG_FLAGS_SAFE,
+				sig_auth_cache_clear, cache);
+	lib_signals_set_handler(SIGUSR2, LIBSIG_FLAGS_SAFE,
+				sig_auth_cache_stats, cache);
+	return cache;
+}
+
+void auth_cache_free(struct auth_cache **_cache)
+{
+	struct auth_cache *cache = *_cache;
+
+	*_cache = NULL;
+	lib_signals_unset_handler(SIGHUP, sig_auth_cache_clear, cache);
+	lib_signals_unset_handler(SIGUSR2, sig_auth_cache_stats, cache);
+
+	auth_cache_clear(cache);
+	hash_table_destroy(&cache->hash);
+	i_free(cache);
+}
+
+unsigned int auth_cache_clear(struct auth_cache *cache)
+{
+	unsigned int ret = hash_table_count(cache->hash);
+
+	while (cache->tail != NULL)
+		auth_cache_node_destroy(cache, cache->tail);
+	hash_table_clear(cache->hash, FALSE);
+	return ret;
+}
+
+static bool auth_cache_node_is_user(struct auth_cache_node *node,
+				    const char *username)
+{
+	const char *data = node->data;
+	size_t username_len;
+
+	/* The cache nodes begin with "P"/"U", passdb/userdb ID, optional
+	   "+" master user, "\t" and then usually followed by the username.
+	   It's too much trouble to keep track of all the cache keys, so we'll
+	   just match it as if it was the username. If e.g. '%n' is used in the
+	   cache key instead of '%u', it means that cache entries can be
+	   removed only when @domain isn't in the username parameter. */
+	if (*data != 'P' && *data != 'U')
+		return FALSE;
+	data++;
+
+	while (*data >= '0' && *data <= '9')
+		data++;
+	if (*data == '+') {
+		/* skip over +master_user */
+		while (*data != '\t' && *data != '\0')
+			data++;
+	}
+	if (*data != '\t')
+		return FALSE;
+	data++;
+
+	username_len = strlen(username);
+	return str_begins(data, username) &&
+		(data[username_len] == '\t' || data[username_len] == '\0');
+}
+
+static bool auth_cache_node_is_one_of_users(struct auth_cache_node *node,
+					    const char *const *usernames)
+{
+	unsigned int i;
+
+	for (i = 0; usernames[i] != NULL; i++) {
+		if (auth_cache_node_is_user(node, usernames[i]))
+			return TRUE;
+	}
+	return FALSE;
+}
+
+unsigned int auth_cache_clear_users(struct auth_cache *cache,
+				    const char *const *usernames)
+{
+	struct auth_cache_node *node, *next;
+	unsigned int ret = 0;
+
+	for (node = cache->tail; node != NULL; node = next) {
+		next = node->next;
+		if (auth_cache_node_is_one_of_users(node, usernames)) {
+			auth_cache_node_destroy(cache, node);
+			ret++;
+		}
+	}
+	return ret;
+}
+
+static const char *
+auth_cache_escape(const char *string,
+		  const struct auth_request *auth_request ATTR_UNUSED)
+{
+	/* cache key %variables are separated by tabs, make sure that there
+	   are no tabs in the string */
+	return str_tabescape(string);
+}
+
+static const char *
+auth_request_expand_cache_key(const struct auth_request *request,
+			      const char *key, const char *username)
+{
+	static bool error_logged = FALSE;
+	const char *error;
+
+	/* Uniquely identify the request's passdb/userdb with the P/U prefix
+	   and by "%!", which expands to the passdb/userdb ID number. */
+	key = t_strconcat(request->userdb_lookup ? "U" : "P", "%!",
+		request->fields.master_user == NULL ? "" : "+%{master_user}",
+		"\t", key, NULL);
+
+	/* It's fine to have unknown %variables in the cache key.
+	   For example db-ldap can have pass_attrs containing
+	   %{ldap:fields} which are used for output, not as part of
+	   the input needed for cache_key. Those could in theory be
+	   filtered out early in the cache_key, but that gets more
+	   problematic when it needs to support also filtering out
+	   e.g. %{sha256:ldap:fields}. */
+	string_t *value = t_str_new(128);
+	unsigned int count = 0;
+	const struct var_expand_table *table =
+		auth_request_get_var_expand_table_full(request,
+			username, auth_cache_escape, &count);
+	if (auth_request_var_expand_with_table(value, key, request, table,
+					       auth_cache_escape, &error) < 0 &&
+	    !error_logged) {
+		error_logged = TRUE;
+		e_error(authdb_event(request),
+			"Failed to expand auth cache key %s: %s", key, error);
+	}
+	return str_c(value);
+}
+
+const char *
+auth_cache_lookup(struct auth_cache *cache, const struct auth_request *request,
+		  const char *key, struct auth_cache_node **node_r,
+		  bool *expired_r, bool *neg_expired_r)
+{
+	struct auth_cache_node *node;
+	const char *value;
+	unsigned int ttl_secs;
+	time_t now;
+
+	*expired_r = FALSE;
+	*neg_expired_r = FALSE;
+
+	key = auth_request_expand_cache_key(request, key, request->fields.translated_username);
+	node = hash_table_lookup(cache->hash, key);
+	if (node == NULL) {
+		cache->miss_count++;
+		return NULL;
+	}
+
+	value = node->data + strlen(node->data) + 1;
+	ttl_secs = *value == '\0' ? cache->neg_ttl_secs : cache->ttl_secs;
+
+	now = time(NULL);
+	if (node->created < now - (time_t)ttl_secs) {
+		/* TTL expired */
+		cache->miss_count++;
+		*expired_r = TRUE;
+	} else {
+		/* move to head */
+		if (node != cache->head) {
+			auth_cache_node_unlink(cache, node);
+			auth_cache_node_link_head(cache, node);
+		}
+		cache->hit_count++;
+	}
+	if (node->created < now - (time_t)cache->neg_ttl_secs)
+		*neg_expired_r = TRUE;
+
+	if (node_r != NULL)
+		*node_r = node;
+
+	return value;
+}
+
+void auth_cache_insert(struct auth_cache *cache, struct auth_request *request,
+		       const char *key, const char *value, bool last_success)
+{
+        struct auth_cache_node *node;
+	size_t data_size, alloc_size, key_len, value_len = strlen(value);
+	char *hash_key;
+
+	if (*value == '\0' && cache->neg_ttl_secs == 0) {
+		/* we're not caching negative entries */
+		return;
+	}
+
+	key = auth_request_expand_cache_key(request, key, request->fields.translated_username);
+	key_len = strlen(key);
+
+	data_size = key_len + 1 + value_len + 1;
+	alloc_size = sizeof(struct auth_cache_node) + data_size;
+
+	/* make sure we have enough space */
+	while (cache->size_left < alloc_size && cache->tail != NULL)
+		auth_cache_node_destroy(cache, cache->tail);
+
+	node = hash_table_lookup(cache->hash, key);
+	if (node != NULL) {
+		/* key is already in cache (probably expired), remove it */
+		auth_cache_node_destroy(cache, node);
+	}
+
+	/* @UNSAFE */
+	node = i_malloc(alloc_size);
+	node->created = time(NULL);
+	node->alloc_size = alloc_size;
+	node->last_success = last_success;
+	memcpy(node->data, key, key_len);
+	memcpy(node->data + key_len + 1, value, value_len);
+
+	auth_cache_node_link_head(cache, node);
+
+	cache->size_left -= alloc_size;
+	hash_key = node->data;
+	hash_table_insert(cache->hash, hash_key, node);
+
+	if (*value != '\0') {
+		cache->pos_entries++;
+		cache->pos_size += alloc_size;
+	} else {
+		cache->neg_entries++;
+		cache->neg_size += alloc_size;
+	}
+}
+
+void auth_cache_remove(struct auth_cache *cache,
+		       const struct auth_request *request, const char *key)
+{
+	struct auth_cache_node *node;
+
+	key = auth_request_expand_cache_key(request, key, request->fields.user);
+	node = hash_table_lookup(cache->hash, key);
+	if (node == NULL)
+		return;
+
+	auth_cache_node_destroy(cache, node);
+}