/*
 * This code is derived from inetd.c as distributed with various BSD versions.
 */

/*
 * Copyright (c) 1983, 1991, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
/* XXX do we need to preserve this copyright string in the binary? */
static const char copyright[] =
"@(#) Copyright (c) 1983, 1991, 1993, 1994\n\
	The Regents of the University of California.  All rights reserved.\n";
#endif /* not lint */

#include "sm/generic.h"
SM_RCSID("@(#)$Id: connctl.c,v 1.19 2006/05/02 17:13:40 ca Exp $")

#include "sm/assert.h"
#include "sm/error.h"
#include "sm/memops.h"
#include "sm/heap.h"
#include "sm/connctl.h"

#define MAXCPM	100

#ifndef HASH_ALG
# define HASH_ALG	2
#endif

/* time granularity: 10s (that's one "tick") */
#define CHTGRAN		10
#define CHTSIZE		6

/*
Jose Marcio Martins da Cruz:
2. You have both information : connection rate and number of open
connections stored in the same data structure. I don't know if this is a
good idea as lifetime for these two informations may be very different :
you do connection rate control over one minute, but some clients may let
their connection last for much more than this. In this case, you shall
not replace old data after one minute. An extreme example of this is,
e.g. if one client opens 50 connections at the same minute and let them
open for two hours.

At this moment, e.g., the connection duration is (over 24 hours) - these
are typical values :

   min    mean     max   std-dev
  0.010  20.738 7225.487 132.717
*/

/* Number of connections for a certain "tick" */
struct conntime_S
{
	ulong	ct_ticks;
	int	ct_count;
};

typedef struct conntime_S	conntime_T, *conntime_P;

struct connhash_S
{
	in_addr_T	ch_addr;	/* addr of connection XXX IPv6 */
	time_t		ch_ltime;	/* last touch */
#if SM_CONNCTL_PERF
	ulong		ch_colls;	/* number of collisions */
#endif

	/* 6 buckets for ticks: 60s */
	conntime_T	ch_times[CHTSIZE];
};

typedef struct connhash_S	connhash_T, *connhash_P;

struct connctx_S
{
#if SM_CONNCTL_CHECK
	sm_magic_T	sm_magic;
#endif
	uint		cc_size;	/* size of hash table */
	uint		cc_max_steps;	/* max. entries to search */
	connhash_P	cc_chashary;	/* hash table */
#if SM_CONNCTL_PERF
	uint		cc_maxcoll;
	ulong		cc_total;
#endif
};

/*
**  SM_CONNCTL_FREE -- free connection control context
**
**	Parameters:
**		cctx -- connection control context
**
**	Returns:
**		usual sm_error code
*/

sm_ret_T
sm_connctl_free(connctx_P cctx)
{
	if (cctx == NULL)
		return SM_SUCCESS;
	SM_FREE(cctx->cc_chashary);
	sm_free_size(cctx, sizeof(*cctx));
#if SM_CONNCTL_CHECK
	cctx->sm_magic = SM_MAGIC_NULL;
#endif
	return SM_SUCCESS;
}

/*
**  SM_CONNCTL_NEW -- create new connection control context
**
**	Parameters:
**		size -- size of hash table
**		steps -- number of entries to search for a "free" one
**		pcctx -- connection control context (output)
**
**	Returns:
**		usual sm_error code
*/

sm_ret_T
sm_connctl_new(uint size, uint steps, connctx_P *pcctx)
{
	connctx_P cctx;
	size_t s;

	SM_REQUIRE(pcctx != NULL);
	SM_REQUIRE(size > 4);
	/* require size to be a power of 2? */

	SM_REQUIRE(steps > 2);

	cctx = (connctx_P) sm_zalloc(sizeof(*cctx));
	if (cctx == NULL)
		return sm_err_temp(ENOMEM);

	s = size * sizeof(*(cctx->cc_chashary));
	cctx->cc_chashary = (connhash_P) sm_zalloc(s);
	if (cctx->cc_chashary == NULL)
	{
		sm_free_size(cctx, sizeof(*cctx));
		return sm_err_temp(ENOMEM);
	}
	cctx->cc_size = size;
	cctx->cc_max_steps = steps;
#if SM_CONNCTL_CHECK
	cctx->sm_magic = SM_CONNCTL_MAGIC;
#endif

	*pcctx = cctx;
	return SM_SUCCESS;
}

/*
**  SM_CONNCTL -- perform connection control
**
**	Parameters:
**		cctx -- connection control context
**		addr -- connection address
**		t -- time of connection
**
**	return a struct with the information, i.e., CPM, open conn?
**
**	Returns:
**		>=0: connection rate
**		<0: usual sm_error code
*/

sm_ret_T
sm_connctl(connctx_P cctx, in_addr_T addr, time_t t)
{
	int cnt;
	uint u;
#if SM_CONNCTL_PERF
	bool coll;
#endif
	uint hv, ticks;
	uchar *p;
	connhash_P chbest;
	conntime_P ct;
#if HASH_ALG != 1
	int c, d;
#endif

	SM_IS_CONNCTX(cctx);

	cnt = 0;
	hv = 0xABC3D20F;
	ticks = t / CHTGRAN;
	chbest = NULL;

#if SM_CONNCTL_PERF
	++cctx->cc_total;
#endif

	/* compute hash value */
	for (u = 0, p = (uchar *) &addr; u < sizeof(addr); ++u, ++p)
#if HASH_ALG == 1
		hv = (hv << 5) ^ (hv >> 23) ^ *p;
	hv = (hv ^ (hv >> 16));
#elif HASH_ALG == 2
	{
		d = *p;
		c = d;
		c ^= c<<6;
		hv += (c<<11) ^ (c>>1);
		hv ^= (d<<14) + (d<<7) + (d<<4) + d;
	}
#elif HASH_ALG == 3
	{
		hv = (hv << 4) + *p;
		d = hv & 0xf0000000;
		if (d != 0)
		{
			hv ^= (d >> 24);
			hv ^= d;
		}
	}
#else /* HASH_ALG == 1 */
		hv = ((hv << 1) ^ (*p & 0377)) % cctx->cc_size;
#endif /* HASH_ALG == 1 */

#if SM_CONNCTL_PERF
	coll = true;
#endif

	/*
	**  Find matching or free bucket.
	**  Remember the least recently used bucket in case no matching
	**  or free bucket is found.
	*/

	for (u = 0; u < cctx->cc_max_steps; ++u)
	{
		connhash_P ch;

		/* Use & if size == 2^n */
		ch = &(cctx->cc_chashary[(hv + u) % cctx->cc_size]);

		/* matching or free entry? */
		if (addr.s_addr == ch->ch_addr.s_addr ||
		    ch->ch_addr.s_addr == 0)
		{
			chbest = ch;
#if SM_CONNCTL_PERF
			coll = false;
#endif
			break;
		}
		if (chbest == NULL || ch->ch_ltime == 0 ||
		    ch->ch_ltime < chbest->ch_ltime)
			chbest = ch;
	}
#if SM_CONNCTL_PERF
	if (coll && (t - chbest->ch_ltime < CollTime))
	{
# if SM_CONNCTL_DBG
		if (Verbose > 1)
		{
			fprintf(stderr,
				"collision: %08x ~= %08x, now=%ld, last=%ld\n",
				addr.s_addr, chbest->ch_addr.s_addr,
				(long) t, (long) chbest->ch_ltime);
		}
# endif /* SM_CONNCTL_DBG */
		chbest->ch_colls++;
		if (chbest->ch_colls > cctx->cc_maxcoll)
			cctx->cc_maxcoll = chbest->ch_colls;
	}
#endif /* SM_CONNCTL_PERF */

	/*
	**  If it's not a match, then replace the data.
	**  Note: this purges the history of a colliding entry,
	**  which may cause "overruns", i.e., if two entries are
	**  "cancelling" each other out, then they may exceed
	**  the limits that are set. This might be mitigated a bit
	**  by the above "best of 5" (cc_max_steps) function however.
	**
	**  Alternative approach: just use the old data, which may
	**  cause false positives however.
	*/

	if (addr.s_addr != chbest->ch_addr.s_addr)
	{
		chbest->ch_addr = addr;
		sm_memzero(chbest->ch_times, sizeof(chbest->ch_times));
	}
	chbest->ch_ltime = t;
	ct = &chbest->ch_times[ticks % CHTSIZE];
	if (ct->ct_ticks != ticks)
	{
		ct->ct_ticks = ticks;
		ct->ct_count = 0;
	}
	++ct->ct_count;
	for (u = 0; u < CHTSIZE; ++u)
	{
		ct = &chbest->ch_times[u];
		if (ct->ct_ticks <= ticks &&
		    ct->ct_ticks >= ticks - CHTSIZE)
			cnt += ct->ct_count;
	}
	return (cnt * 60) / (CHTSIZE * CHTGRAN);
}

#if SM_CONNCTL_PERF
/*
**  SM_CONNCTL_STATS -- return connection control statistics
**
**	Parameters:
**		cctx -- connection control context
**		pcolls -- collisions (output)
**		pmaxcolls -- max collisions for a single entry (output)
**		punused -- unused entries (output)
**		ptotal -- total calls (output)
**
**	Returns:
**		usual sm_error code
*/

sm_ret_T
sm_connctl_stats(connctx_P cctx, ulong *pcolls, ulong *pmaxcolls, ulong *punused, ulong *ptotal)
{
	int r;
	ulong colls, maxcolls, unused;

	SM_REQUIRE(pcolls != NULL);
	SM_REQUIRE(pmaxcolls != NULL);
	SM_REQUIRE(punused != NULL);
	colls = maxcolls = unused = 0;
	for (r = 0; r < cctx->cc_size; r++)
	{
		connhash_P ch;

		ch = &(cctx->cc_chashary[r]);
		if (ch->ch_ltime == 0)
		{
			++unused;
			continue;
		}
		colls += ch->ch_colls;
	}
	*pcolls = colls;
	*pmaxcolls = maxcolls;
	*punused = unused;
	*ptotal = cctx->cc_total;
	return SM_SUCCESS;
}
#endif /* SM_CONNCTL_PERF */