/*
* 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 */
syntax highlighted by Code2HTML, v. 0.9.1