/*
 * Copyright (c) 2002-2006 Sendmail, Inc. and its suppliers.
 *	All rights reserved.
 *
 * By using this file, you agree to the terms and conditions set
 * forth in the LICENSE file which can be found at the top level of
 * the sendmail distribution.
 */

#include "sm/generic.h"
SM_RCSID("@(#)$Id: rsc.c,v 1.72 2006/10/05 04:27:37 ca Exp $")

#include "sm/assert.h"
#include "sm/error.h"
#include "sm/memops.h"
#include "sm/heap.h"
#include "sm/queue.h"
#include "sm/bhtable.h"

#define RSC_COMPILE 1

#if SM_RSC_TYPED
# include "sm/rsct.h"
#else
# include "sm/rsc.h"
#endif

#if MTA_USE_PTHREADS
# include "sm/pthread.h"
#endif

#ifndef SM_RSC_STATS
# define SM_RSC_STATS 1
#endif

/*
**  Notice:
**	if locking is active (MTA_USE_PTHREADS) then each function locks
**	the entire RSC during its operation. That means none of these
**	functions can call another one herein (if both use locking)!
**
**  Possible enhancements:
**	- change size of RSC? it should be easy to extend the RSC,
**	  there is a function for BHT to grow.  However, there is no
**	  function for BHT to shrink (which shouldn't matter much,
**	  we can just restrict the size of the RSC; that won't
**	  reclaim the memory in the BHT, but a bit in the RSC).
*/

/* abstraction layer for linking, XXX entries in struct are not abstracted */
#define link_P	rsc_entry_P
#define link_succ(r) CIRCLEQ_NEXT(r, rsce_link)
#define link_pred(r) CIRCLEQ_PREV(r, rsce_link)
#define LINK_INIT(rsc) CIRCLEQ_INIT(&((rsc)->rsc_link))
#define LINK_APPEND(rsc, entry)	CIRCLEQ_INSERT_HEAD(&((rsc)->rsc_link), entry, rsce_link)
#define LINK_REMOVE(rsc, entry) CIRCLEQ_REMOVE(&((rsc)->rsc_link), (entry), rsce_link)
#define LINK_OLDEST(rsc)	CIRCLEQ_LAST(&((rsc)->rsc_link))
#define LINK_NEWEST(rsc)	CIRCLEQ_FIRST(&((rsc)->rsc_link))
#define LINK_END(rsc)		CIRCLEQ_END(&((rsc)->rsc_link))

/* minimum size of an RSC */
#define RSC_MIN_SIZE	5

typedef struct rsc_entry_S rsc_entry_T, *rsc_entry_P;

/*
**  RSC entries are kept in most-recently used order.
**  A BHT is used to find RSC entries.
*/

struct rsc_entry_S
{
#if SM_RSCE_CHECK
	sm_magic_T	 sm_magic;
#endif
	CIRCLEQ_ENTRY(rsc_entry_S)	 rsce_link;	/* MRU linkage */
#if SM_RSC_TYPED
	uint		 rsce_type;	/* type of entry */
#endif
	const char	*rsce_key;	/* lookup key */
	uint		 rsce_len;	/* key len */
	void		*rsce_value;	/* corresponding value */
};

#if SM_RSC_TYPED
# define RSC_DELETE(rsc, value, type) (rsc)->rsc_delete(value, (rsc)->rsc_ctx, (type))
# define RSCTYPE	, type
#else
# define RSC_DELETE(rsc, value, type) (rsc)->rsc_delete(value, (rsc)->rsc_ctx)
# define RSCTYPE
#endif

struct sm_rsc_S
{
#if SM_RSC_CHECK
	sm_magic_T	 sm_magic;
#endif
	bht_P		 rsc_table;	/* table with key, rsc_entry pairs */
	uint		 rsc_limit;	/* max # of entries */
	uint		 rsc_used;	/* current # of entries */
	CIRCLEQ_HEAD(, rsc_entry_S)	 rsc_link;	/* MRU linkage */
	void		*rsc_ctx;	/* application context */
	sm_rsc_create_F	 rsc_create;	/* constructor */
	sm_rsc_delete_F	 rsc_delete;	/* destructor */
#if MTA_USE_PTHREADS
	pthread_mutex_t	 rsc_mutex;
#endif
#if SM_RSC_STATS
	uint		 rsc_max_used;	/* max # of entries */
#endif
};

#if SM_RSC_CHECK
# define SM_IS_RSC(rsc)	SM_REQUIRE_ISA((rsc), SM_RSC_MAGIC)
#else
# define SM_IS_RSC(rsc)	SM_REQUIRE((rsc) != NULL)
#endif

/*
**  SM_RSC_CREATE -- create an RSC
**
**	Parameters:
**		limit -- maximum number of entries in the RSC
**		htsize -- size of BHT
**		create -- function to create an entry
**		delete -- function to delete an entry
**		context -- context for create/delete functions
**
**	Returns:
**		Pointer to RSC (NULL on error)
**		(fixme: should we return the usual error code??)
**
**	Last code review: 2005-04-07 22:20:17
**	Last code change: 2005-04-07 22:20:11
*/

sm_rsc_P
sm_rsc_new(uint limit, uint htsize,
		sm_rsc_create_F create, sm_rsc_delete_F delete,
		void *context)
{
	sm_rsc_P rsc;
#if MTA_USE_PTHREADS
	int r;
#endif

	if (limit < 1)
		return NULL;
	if (htsize < limit)	/* this include htsize = 0 */
		htsize = limit;
	rsc = (sm_rsc_P) sm_malloc(sizeof(*rsc));
	if (rsc == NULL)
		return NULL;
#if MTA_USE_PTHREADS
	r = pthread_mutex_init(&rsc->rsc_mutex, SM_PTHREAD_MUTEXATTR);
	if (r != 0)
		return NULL; /* sm_error_perm(SM_EM_RSC, r); */
#endif
	rsc->rsc_table = bht_new(htsize, limit);
	if (rsc->rsc_table == NULL)
	{
		sm_free_size(rsc, sizeof(*rsc));
		goto error;
	}
	rsc->rsc_limit = (limit < RSC_MIN_SIZE) ? RSC_MIN_SIZE : limit;
	rsc->rsc_used = 0;
#if SM_RSC_STATS
	rsc->rsc_max_used = 0;
#endif
	rsc->rsc_create = create;
	rsc->rsc_delete = delete;
	LINK_INIT(rsc);
	rsc->rsc_ctx = context;
#if SM_RSC_CHECK
	rsc->sm_magic = SM_RSC_MAGIC;
#endif
	return rsc;

  error:
#if MTA_USE_PTHREADS
	(void) pthread_mutex_destroy(&rsc->rsc_mutex);
#endif
	return NULL;
}

/*
**  SM_RSC_ADD -- add item to RSC or return old one
**
**	Parameters:
**		rsc -- RSC
**		delok -- is it ok to delete a value?
**		key -- key to lookup
**		len -- length of key
**		value -- value to add (passed to create function)
**		pvalue -- pointer to value of entry (output)
**		locktype -- kind of locking
**
**	Returns:
**		>=0: usage
**		<0: usual sm_error code; ENOMEM, SM_E_FULL
**
**	Side Effects: if RSC is full the function removes the oldest
**		entry which is not "undone" on error.
**
**	Locking: locks entire RSC during operation, returns unlocked
**		(depending on locktype)
**
**	Last code review: 2005-04-07 22:17:15; see comments
**	Last code change:
*/

sm_ret_T
sm_rsc_add(sm_rsc_P rsc, bool delok,
#if SM_RSC_TYPED
	uint type,
#endif
	char *key, uint len, void *value, void **pvalue
#if MTA_USE_PTHREADS
	, thr_lock_T locktype
#endif
	)
{
	rsc_entry_P entry;
	sm_ret_T ret;
#if MTA_USE_PTHREADS
	int r;
#endif

	SM_IS_RSC(rsc);
#if MTA_USE_PTHREADS
	if (thr_lock_it(locktype))
	{
		r = pthread_mutex_lock(&rsc->rsc_mutex);
		SM_LOCK_OK(r);
		if (r != 0)
		{
			/* LOG? */
			return sm_error_perm(SM_EM_RSC, r);
		}
	}
#endif
	entry = (rsc_entry_P) bht_find(rsc->rsc_table, key, len);
	if (entry == NULL)
	{
		bool allocated;
		bht_entry_P bht_entry;

		allocated = false;

		/* not in RSC: is limit reached? */
		if (rsc->rsc_used >= rsc->rsc_limit)
		{

			if (!delok)
			{
				ret = sm_error_temp(SM_EM_RSC, SM_E_FULL);
				goto error;
			}

			/* remove oldest entry (not "undone" on error!) */
			entry = LINK_OLDEST(rsc);
			if (rsc->rsc_delete != NULL)
			{
				ret = RSC_DELETE(rsc, entry->rsce_value,
						entry->rsce_type);
				if (sm_is_err(ret))
					goto error;
			}
			LINK_REMOVE(rsc, entry);
			bht_rm(rsc->rsc_table, entry->rsce_key,
				entry->rsce_len, NULL, NULL);
		}
		else
		{
			entry = (rsc_entry_P) sm_zalloc(sizeof(*entry));
			if (entry == NULL)
			{
				ret = sm_error_temp(SM_EM_RSC, ENOMEM);
				goto error;
			}
			allocated = true;
			rsc->rsc_used++;
#if SM_RSC_STATS
			if (rsc->rsc_used > rsc->rsc_max_used)
				rsc->rsc_max_used = rsc->rsc_used;
#endif

		}

		/* this must not fail... fixme: handle NULL return? */
		entry->rsce_value = rsc->rsc_create(key, len, value,
						rsc->rsc_ctx RSCTYPE);
		ret = bht_add(rsc->rsc_table, key, len,
				(char *) entry, &bht_entry);
		if (sm_is_err(ret))
		{
			/* clean up! */
			if (rsc->rsc_delete != NULL)
				RSC_DELETE(rsc, entry->rsce_value,
						entry->rsce_type);
			if (allocated)
				sm_free_size(entry, sizeof(*entry));
			rsc->rsc_used--;
			goto error;
		}
		entry->rsce_key = bht_entry->bhe_key;
		entry->rsce_len = len;
#if SM_RSC_TYPED
		entry->rsce_type = type;
#endif

		/* insert entry right at (after) the head */
		LINK_APPEND(rsc, entry);
	}
	else if (entry != LINK_NEWEST(rsc))
	{
		/* move the entry up front */
		LINK_REMOVE(rsc, entry);
		LINK_APPEND(rsc, entry);
	}
	if (pvalue != NULL)
		*pvalue = entry->rsce_value;
#if MTA_USE_PTHREADS
	if (thr_unl_no_err(locktype))
	{
		r = pthread_mutex_unlock(&rsc->rsc_mutex);
		SM_ASSERT(r == 0);
		/* r isn't checked further; will fail on next iteration */
	}
#endif
	return (int) ((rsc->rsc_used * 100) / rsc->rsc_limit);

  error:
#if MTA_USE_PTHREADS
	if (thr_unl_if_err(locktype))
	{
		r = pthread_mutex_unlock(&rsc->rsc_mutex);
		SM_ASSERT(r == 0);	/* MUST NOT happen */
		if (r != 0 && sm_is_success(ret))
			ret = sm_error_perm(SM_EM_RSC, r);
	}
#endif
	return ret;
}

/*
**  SM_RSC_RM -- remove item from RSC.
**
**	Parameters:
**		rsc -- RSC
**		key -- key to lookup
**		len -- length of key
**		locktype -- kind of locking
**
**	Returns:
**		usual sm_error code; SM_E_NOTFOUND
**
**	Side Effects: no side effects on error.
**
**	Locking: locks entire RSC during operation, returns unlocked
**		(depending on locktype)
**
**	Last code review: 2005-03-31 17:51:39
**	Last code change:
*/

sm_ret_T
sm_rsc_rm(sm_rsc_P rsc, const char *key, uint len
#if MTA_USE_PTHREADS
	, thr_lock_T locktype
#endif
	)
{
	sm_ret_T ret;
#if MTA_USE_PTHREADS
	int r;
#endif
	rsc_entry_P entry;

	SM_IS_RSC(rsc);
#if MTA_USE_PTHREADS
	if (thr_lock_it(locktype))
	{
		r = pthread_mutex_lock(&rsc->rsc_mutex);
		SM_LOCK_OK(r);
		if (r != 0)
		{
			/* LOG? */
			return sm_error_perm(SM_EM_RSC, r);
		}
	}
#endif
	ret = SM_SUCCESS;
	entry = (rsc_entry_P) bht_find(rsc->rsc_table, key, len);
	if (entry == NULL)
	{
		ret = sm_error_perm(SM_EM_RSC, SM_E_NOTFOUND);
		goto error;
	}

	LINK_REMOVE(rsc, entry);
	if (rsc->rsc_delete != NULL)
		RSC_DELETE(rsc, entry->rsce_value, entry->rsce_type);
	bht_rm(rsc->rsc_table, entry->rsce_key, entry->rsce_len, NULL, NULL);
	SM_ASSERT(rsc->rsc_used > 0);
	--rsc->rsc_used;
	sm_free_size(entry, sizeof(*entry));
#if MTA_USE_PTHREADS
	if (thr_unl_no_err(locktype))
	{
		r = pthread_mutex_unlock(&rsc->rsc_mutex);
		SM_ASSERT(r == 0);
		if (r != 0 && sm_is_success(ret))
			ret = sm_error_perm(SM_EM_RSC, r);
	}
#endif
	return ret;

  error:
#if MTA_USE_PTHREADS
	if (thr_unl_if_err(locktype))
	{
		r = pthread_mutex_unlock(&rsc->rsc_mutex);
		SM_ASSERT(r == 0);
		if (r != 0 && sm_is_success(ret))
			ret = sm_error_perm(SM_EM_RSC, r);
	}
#endif
	return ret;
}

/*
**  SM_RSC_LOOKUP -- look up item in RSC
**
**	Parameters:
**		rsc -- RSC
**		key -- key to lookup
**		len -- length of key
**		locktype -- kind of locking
**
**	Returns:
**		Pointer to value of entry (NULL if not found)
**		(fixme: should we return the usual error code??)
**
**	Locking: locks entire RSC during operation, returns unlocked
**		(depending on locktype)
**		Note: the item that is returned is not locked hence
**		there's a possible race condition depending on the
**		application (how it uses those items).
**
** #if SM_RSC_TYPED
**	Restrict this to a certain type?
** #endif
**
**	Last code review: 2005-03-31 17:47:15
**	Last code change:
*/

const void *
sm_rsc_lookup(sm_rsc_P rsc, const char *key, uint len
#if MTA_USE_PTHREADS
	, thr_lock_T locktype
#endif
	)
{
	rsc_entry_P entry;
#if MTA_USE_PTHREADS
	int r;
#endif

	SM_IS_RSC(rsc);
#if MTA_USE_PTHREADS
	if (thr_lock_it(locktype))
	{
		r = pthread_mutex_lock(&rsc->rsc_mutex);
		SM_LOCK_OK(r);
		if (r != 0)
		{
			/* LOG? */
			return NULL; /* sm_error_perm(SM_EM_RSC, r); */
		}
	}
#endif
	entry = (rsc_entry_P) bht_find(rsc->rsc_table, key, len);
#if MTA_USE_PTHREADS
	if (thr_unl_always(locktype))
	{
		r = pthread_mutex_unlock(&rsc->rsc_mutex);
		SM_ASSERT(r == 0);	/* MUST NOT happen */
		/* r isn't checked further; will fail on next iteration */
	}
#endif
	if (entry == NULL)
		return NULL;
	return entry->rsce_value;
}

/*
**  SM_RSC_FREE_CALLBACK -- callback function for rsc_free
**
**	Parameters:
**		ptr -- pointer to RSC element
**		key -- key (unused)
**		ctx -- context.
**
**	Returns:
**		Nothing.
**
**	Last code review: 2005-04-07 22:19:13
**	Last code change: 2005-04-07 22:18:49
*/

static void
sm_rsc_free_callback(void *ptr, void *key, void *ctx)
{
	rsc_entry_P entry;
	sm_rsc_P rsc;

	(void) key;
	SM_REQUIRE(ptr != NULL);
	entry = (rsc_entry_P) ptr;
	rsc = (sm_rsc_P) ctx;
	SM_IS_RSC(rsc);
	if (rsc->rsc_delete != NULL)
		RSC_DELETE(rsc, entry->rsce_value, entry->rsce_type);
	sm_free_size(entry, sizeof(*entry));
}

/*
**  SM_RSC_FREE -- free rsc and its contents
**
**	Parameters:
**		rsc -- RSC
**
**	Returns:
**		Nothing.
**
**	Last code review: 2005-04-07 22:22:52
**	Last code change: 2005-04-07 22:22:48
*/

void
sm_rsc_free(sm_rsc_P rsc)
{
#if MTA_USE_PTHREADS
	int r;
#endif

	SM_IS_RSC(rsc);
	bht_destroy(rsc->rsc_table, sm_rsc_free_callback, (void *) rsc);
#if MTA_USE_PTHREADS
	r = pthread_mutex_destroy(&rsc->rsc_mutex);
	if (r != 0)
	{
		/* LOG an error?? */
	}
#endif
	sm_free_size(rsc, sizeof(*rsc));
}

/*
**  SM_RSC_WALK -- iterate over all rsc entries
**
**	Parameters:
**		rsc -- RSC
**		action -- function to apply
**		ctx -- context for action
**		locktype -- kind of locking
**
**	Returns:
**		SM_SUCCESS except for (un)lock errors
**
**	Locking: locks entire RSC during operation, returns unlocked
**		(depending on locktype)
**
**	Last code review: 2005-04-07 22:34:25
**	Last code change:
*/

sm_ret_T
sm_rsc_walk(sm_rsc_P rsc, sm_rsc_walk_F *action, void *ctx
#if MTA_USE_PTHREADS
	, thr_lock_T locktype
#endif
	)
{
	link_P entry, next;
#if MTA_USE_PTHREADS
	int r;
#endif

	SM_IS_RSC(rsc);
	SM_REQUIRE(action != NULL);
#if MTA_USE_PTHREADS
	if (thr_lock_it(locktype))
	{
		r = pthread_mutex_lock(&rsc->rsc_mutex);
		SM_LOCK_OK(r);
		if (r != 0)
		{
			/* LOG? */
			return sm_error_perm(SM_EM_RSC, r);
		}
	}
#endif
	for (entry = LINK_NEWEST(rsc); entry != LINK_END(rsc); entry = next)
	{
		next = link_succ(entry);
		action(entry->rsce_key, entry->rsce_value, rsc->rsc_ctx, ctx
#if SM_RSC_TYPED
			, entry->rsce_type
#endif
			);
	}
#if MTA_USE_PTHREADS
	if (thr_unl_always(locktype))
	{
		r = pthread_mutex_unlock(&rsc->rsc_mutex);
		SM_ASSERT(r == 0);
		if (r != 0)
			return sm_error_perm(SM_EM_RSC, r);
	}
#endif
	return SM_SUCCESS;
}

/*
**  SM_RSC_USAGE -- return percentage of # of item in RSC (* 100)
**
**	Parameters:
**		rsc -- RSC
**
**	Returns:
**		fill level
**
**	Locking: no locking, may return garbage.
**
**	Last code review: 2005-04-07 22:34:33
**	Last code change:
*/

uint
sm_rsc_usage(sm_rsc_P rsc)
{
	SM_IS_RSC(rsc);
	return (int) ((rsc->rsc_used * 100) / rsc->rsc_limit);
}

/*
**  SM_RSC_ENTRIES -- return # of items in RSC
**
**	Parameters:
**		rsc -- RSC
**		pmax_used -- (pointer to) max. number of entries (output)
**
**	Returns:
**		fill level
**
**	Locking: no locking, may return garbage.
**
**	Last code review: 2005-04-07 22:34:40
**	Last code change: 2005-05-19 20:16:33
*/

uint
sm_rsc_entries(sm_rsc_P rsc, uint *pmax_used)
{
	SM_IS_RSC(rsc);
	if (pmax_used != NULL)
#if SM_RSC_STATS
		*pmax_used = rsc->rsc_max_used;
#else
		*pmax_used = 0;
#endif
	return rsc->rsc_used;
}

/*
**  SM_RSC_STATS -- return bht stats of RSC
**
**	Parameters:
**		rsc -- RSC
**		out -- buffer to store stats in
**		len -- length of buffer out
**
**	Returns:
**		none
**
**	Locking: no locking, may return garbage.
**
**	Last code review: 2005-04-07 22:34:46
**	Last code change:
*/

void
sm_rsc_stats(sm_rsc_P rsc, char *out, uint len)
{
	SM_IS_RSC(rsc);
	bht_stats(rsc->rsc_table, out, len);
}