* Copyright (c) 2004-2013 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 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_n(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;

	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 %lluB, negative: %u %lluB",
	       cache->pos_entries, cache->pos_size,
	       cache->neg_entries, cache->neg_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->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;
	unsigned int username_len;

	/* The cache nodes begin with "P"/"U", passdb/userdb ID, "/" 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 != '/')
		return FALSE;
	data++;

	username_len = strlen(username);
	return strncmp(data, username, username_len) == 0 &&
		(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)
{
	string_t *str;

	/* 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", "%!/", key, NULL);

	str = t_str_new(256);
	var_expand(str, key,
		   auth_request_get_var_expand_table(request, auth_cache_escape));
	return str_c(str);
}

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);
	node = hash_table_lookup(cache->hash, key);
	if (node == NULL) {
		cache->miss_count++;
		return NULL;
	}
	cache->hit_count++;

	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 */
		*expired_r = TRUE;
	} else {
		/* move to head */
		if (node != cache->head) {
			auth_cache_node_unlink(cache, node);
			auth_cache_node_link_head(cache, node);
		}
	}
	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, *current_username;

	if (*value == '\0' && cache->neg_ttl_secs == 0) {
		/* we're not caching negative entries */
		return;
	}

	/* store into cache using the translated username, except if we're doing
	   a master user login */
	current_username = request->user;
	if (request->translated_username != NULL &&
	    request->requested_login_user == NULL)
		request->user = t_strdup_noconst(request->translated_username);

	key = auth_request_expand_cache_key(request, key);
	key_len = strlen(key);

	request->user = current_username;

	data_size = key_len + 1 + value_len + 1;
	alloc_size = sizeof(struct auth_cache_node) -
		sizeof(node->data) + 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);
	node = hash_table_lookup(cache->hash, key);
	if (node == NULL)
		return;

	auth_cache_node_destroy(cache, node);
}