trunk/src/negcache.c

/*
Copyright (C) 2002-2003 Andy Smith
 
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
 
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with this program; if not, write to:
 
      the Free Software Foundation, Inc.
      59 Temple Place - Suite 330
      Boston, MA  02111-1307, USA.
 
*/

/*
 * A Negative caching implementation for IPv4 addresses.  The idea is that
 * every time an IP address is seen, it is checked against a patricia trie.  If
 * the IP address was previously seen and within an acceptable period of time,
 * it is not scanned again.  Otherwise, the address is scanned as normal.  If
 * it is proven to be OK (i.e.  it doesn't run an open proxy) then it is added
 * to the trie.
 *
 * I'm using a patricia trie as described on p253 of Sedgewick.  The reason for
 * this is that it can find any IP address with only log_2 N bit comparisons
 * and only requires as many nodes as we have IP addresses to store.
 *
 * I would have liked to have made the trie implementation generic but couldn't
 * see how to do it easily given that the trie structure depends on the data
 * within it.
 *  --grifferz
 */

#include "setup.h"

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

#include "irc.h"
#include "negcache.h"
#include "config.h"
#include "malloc.h"
#include "log.h"


extern unsigned int OPT_DEBUG;

static struct cnode *nc_search(struct cnode *head, const unsigned long ip);
static struct cnode *nc_insert(struct cnode *head, const unsigned long ip);
static void nc_rebuild(struct cnode *old_head, struct cnode *new_head,
                       struct cnode *n, time_t now);

time_t last_nc_expire;
unsigned int maxb;
extern struct cnode *nc_head;

/*
 * Return the bit which appears k bits from the right in x.
 */
#define GETBIT(x,k)     ((x >> k) & 1)


/*
 * Initialise the patricia trie we use for storing our negative cache.
 */
void nc_init(struct cnode **head)
{
   if (*head)
   {
      /* Cache already exists */
      return;
   }

   *head = MyMalloc(sizeof **head);

   maxb = (sizeof((*head)->ip) * 8);
   (*head)->ip = 0;
   (*head)->b = maxb;
   (*head)->l = (*head)->r = *head;
   last_nc_expire = time(NULL);
}

/*
 * Find and return a pointer to the trie node that corresponds to a given IP
 * address as expressed in network form, or return NULL if the IP isn't
 * present.
 */
static struct cnode *nc_search(struct cnode *head, const unsigned long ip)
{
   struct cnode *p, *x;

   p = head;
   x = head->l;

   while (p->b > x->b)
   {
      p = x;
      x = GETBIT(ip, x->b) ? x->r : x->l;
   }

   if (ip == x->ip)
      return(x);
   else
      return(NULL);
}

/*
 * Insert a new node into the trie, and return a pointer to it.
 */
static struct cnode *nc_insert(struct cnode *head, const unsigned long ip)
{
   unsigned int i;
   struct cnode *p, *t, *x;

   i = maxb;
   p = head;
   t = head->l;

   while (p->b > t->b)
   {
      p = t;
      t = GETBIT(ip, t->b) ? t->r : t->l;
   }

   if (ip == t->ip)
   {
      /* Node already exists. */
      return(t);
   }

   while (GETBIT(t->ip, i) == GETBIT(ip, i))
      i--;

   p = head;
   x = head->l;

   while (p->b > x->b && x->b > i)
   {
      p = x;
      x = GETBIT(ip, x->b) ? x->r : x->l;
   }

   t = MyMalloc(sizeof *t);
   t->ip = ip;
   t->b = i;
   t->l = GETBIT(ip, t->b) ? x : t;
   t->r = GETBIT(ip, t->b) ? t : x;

   if (GETBIT(ip, p->b))
      p->r = t;
   else
      p->l = t;

   return(t);
}

/*
 * Check whether an IP address is in our negative cache and was added
 * recently enough.  Return a pointer to its node if so, NULL otherwise.
 */
struct cnode *check_neg_cache(const unsigned long ip)
{
   time_t now;
   struct cnode *n;

   if (OptionsItem->negcache <= 0)
      return(NULL);

   n = nc_search(nc_head, ip);

   if (n)
   {
      /* Check it is recent enough. */
      now = time(NULL);

      if (now - n->seen <= OptionsItem->negcache)
         return(n);
   }

   return(NULL);
}

/*
 * Prepare an ASCII string representing an IPv4 address for inserting into
 * our negative cache.
 */
void negcache_insert(const char *ipstr)
{
   struct bopm_sockaddr ip;
   struct cnode *n;

   if (inet_pton(AF_INET, ipstr, &(ip.sa4.sin_addr)) <= 0)
   {
      log_printf("NEGCACHE -> Invalid IPv4 address '%s'", ipstr);
      return;
   }

   n = nc_insert(nc_head, ip.sa4.sin_addr.s_addr);

   if (n)
      n->seen = time(NULL);
}

/*
 * Recursively walk the cache and insert the nodes into a new patricia trie,
 * skipping nodes that are too old.
 */
static void nc_rebuild(struct cnode *old_head, struct cnode *new_head,
                       struct cnode *n, time_t now)
{
   struct cnode *new;

   if (!n)
   {
      /* Start at head. */
      n = old_head->l;
   }

   if (n == old_head)
   {
      /* Trie is empty. */
      return;
   }

   if (n->b > n->l->b)
   {
      /*
       * If the trie extends via the left branch, follow it
       * recursively.
       */
      nc_rebuild(old_head, new_head, n->l, now);
   }

   if (n->b > n->r->b)
   {
      /*
       * If the trie extends via the right branch, follow it
       * recursively.
       */
      nc_rebuild(old_head, new_head, n->r, now);
   }

   if ((now - n->seen) < OptionsItem->negcache)
   {
      /*
       * We want to keep this node, so insert it into the new
       * trie.
       */
      new = nc_insert(new_head, n->ip);
      new->seen = n->seen;
   }
   else if (OPT_DEBUG >= 2)
   {
      log_printf("NEGCACHE -> Deleting negcache node for %lu added at %lu", n->ip,
          n->seen);
   }

   /* Safe to free() this node now. */
   MyFree(n);
}

/*
 * Wrapper for recursive rebuild function.
 */
void negcache_rebuild(void)
{
   time_t now;
   struct cnode *new_head;

   now = time(NULL);
   new_head = NULL;

   nc_init(&new_head);
   nc_rebuild(nc_head, new_head, NULL, now);
   MyFree(nc_head);
   nc_head = new_head;
}
Revision:	5266
Committed:	Thu Jan 1 18:49:40 2015 UTC (9 years, 3 months ago) by michael
Content type:	text/x-csrc
File size:	6325 byte(s)
Log Message:	- Removed obsolete AC_HEADER_TIME
#	Content
1	/*
2	Copyright (C) 2002-2003 Andy Smith
3
4	This program is free software; you can redistribute it and/or
5	modify it under the terms of the GNU General Public License
6	as published by the Free Software Foundation; either version 2
7	of the License, or (at your option) any later version.
8
9	This program is distributed in the hope that it will be useful,
10	but WITHOUT ANY WARRANTY; without even the implied warranty of
11	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12	GNU General Public License for more details.
13
14	You should have received a copy of the GNU General Public License
15	along with this program; if not, write to:
16
17	the Free Software Foundation, Inc.
18	59 Temple Place - Suite 330
19	Boston, MA 02111-1307, USA.
20
21	*/
22
23	/*
24	* A Negative caching implementation for IPv4 addresses. The idea is that
25	* every time an IP address is seen, it is checked against a patricia trie. If
26	* the IP address was previously seen and within an acceptable period of time,
27	* it is not scanned again. Otherwise, the address is scanned as normal. If
28	* it is proven to be OK (i.e. it doesn't run an open proxy) then it is added
29	* to the trie.
30	*
31	* I'm using a patricia trie as described on p253 of Sedgewick. The reason for
32	* this is that it can find any IP address with only log_2 N bit comparisons
33	* and only requires as many nodes as we have IP addresses to store.
34	*
35	* I would have liked to have made the trie implementation generic but couldn't
36	* see how to do it easily given that the trie structure depends on the data
37	* within it.
38	* --grifferz
39	*/
40
41	#include "setup.h"
42
43	#include <stdio.h>
44	#include <stdlib.h>
45	#include <sys/time.h>
46	#include <time.h>
47
48	#include "irc.h"
49	#include "negcache.h"
50	#include "config.h"
51	#include "malloc.h"
52	#include "log.h"
53
54
55	extern unsigned int OPT_DEBUG;
56
57	static struct cnode nc_search(struct cnode head, const unsigned long ip);
58	static struct cnode nc_insert(struct cnode head, const unsigned long ip);
59	static void nc_rebuild(struct cnode old_head, struct cnode new_head,
60	struct cnode *n, time_t now);
61
62	time_t last_nc_expire;
63	unsigned int maxb;
64	extern struct cnode *nc_head;
65
66	/*
67	* Return the bit which appears k bits from the right in x.
68	*/
69	#define GETBIT(x,k) ((x >> k) & 1)
70
71
72	/*
73	* Initialise the patricia trie we use for storing our negative cache.
74	*/
75	void nc_init(struct cnode **head)
76	{
77	if (*head)
78	{
79	/* Cache already exists */
80	return;
81	}
82
83	head = MyMalloc(sizeof *head);
84
85	maxb = (sizeof((head)->ip) 8);
86	(*head)->ip = 0;
87	(*head)->b = maxb;
88	(head)->l = (head)->r = *head;
89	last_nc_expire = time(NULL);
90	}
91
92	/*
93	* Find and return a pointer to the trie node that corresponds to a given IP
94	* address as expressed in network form, or return NULL if the IP isn't
95	* present.
96	*/
97	static struct cnode nc_search(struct cnode head, const unsigned long ip)
98	{
99	struct cnode p, x;
100
101	p = head;
102	x = head->l;
103
104	while (p->b > x->b)
105	{
106	p = x;
107	x = GETBIT(ip, x->b) ? x->r : x->l;
108	}
109
110	if (ip == x->ip)
111	return(x);
112	else
113	return(NULL);
114	}
115
116	/*
117	* Insert a new node into the trie, and return a pointer to it.
118	*/
119	static struct cnode nc_insert(struct cnode head, const unsigned long ip)
120	{
121	unsigned int i;
122	struct cnode p, t, *x;
123
124	i = maxb;
125	p = head;
126	t = head->l;
127
128	while (p->b > t->b)
129	{
130	p = t;
131	t = GETBIT(ip, t->b) ? t->r : t->l;
132	}
133
134	if (ip == t->ip)
135	{
136	/* Node already exists. */
137	return(t);
138	}
139
140	while (GETBIT(t->ip, i) == GETBIT(ip, i))
141	i--;
142
143	p = head;
144	x = head->l;
145
146	while (p->b > x->b && x->b > i)
147	{
148	p = x;
149	x = GETBIT(ip, x->b) ? x->r : x->l;
150	}
151
152	t = MyMalloc(sizeof *t);
153	t->ip = ip;
154	t->b = i;
155	t->l = GETBIT(ip, t->b) ? x : t;
156	t->r = GETBIT(ip, t->b) ? t : x;
157
158	if (GETBIT(ip, p->b))
159	p->r = t;
160	else
161	p->l = t;
162
163	return(t);
164	}
165
166	/*
167	* Check whether an IP address is in our negative cache and was added
168	* recently enough. Return a pointer to its node if so, NULL otherwise.
169	*/
170	struct cnode *check_neg_cache(const unsigned long ip)
171	{
172	time_t now;
173	struct cnode *n;
174
175	if (OptionsItem->negcache <= 0)
176	return(NULL);
177
178	n = nc_search(nc_head, ip);
179
180	if (n)
181	{
182	/* Check it is recent enough. */
183	now = time(NULL);
184
185	if (now - n->seen <= OptionsItem->negcache)
186	return(n);
187	}
188
189	return(NULL);
190	}
191
192	/*
193	* Prepare an ASCII string representing an IPv4 address for inserting into
194	* our negative cache.
195	*/
196	void negcache_insert(const char *ipstr)
197	{
198	struct bopm_sockaddr ip;
199	struct cnode *n;
200
201	if (inet_pton(AF_INET, ipstr, &(ip.sa4.sin_addr)) <= 0)
202	{
203	log_printf("NEGCACHE -> Invalid IPv4 address '%s'", ipstr);
204	return;
205	}
206
207	n = nc_insert(nc_head, ip.sa4.sin_addr.s_addr);
208
209	if (n)
210	n->seen = time(NULL);
211	}
212
213	/*
214	* Recursively walk the cache and insert the nodes into a new patricia trie,
215	* skipping nodes that are too old.
216	*/
217	static void nc_rebuild(struct cnode old_head, struct cnode new_head,
218	struct cnode *n, time_t now)
219	{
220	struct cnode *new;
221
222	if (!n)
223	{
224	/* Start at head. */
225	n = old_head->l;
226	}
227
228	if (n == old_head)
229	{
230	/* Trie is empty. */
231	return;
232	}
233
234	if (n->b > n->l->b)
235	{
236	/*
237	* If the trie extends via the left branch, follow it
238	* recursively.
239	*/
240	nc_rebuild(old_head, new_head, n->l, now);
241	}
242
243	if (n->b > n->r->b)
244	{
245	/*
246	* If the trie extends via the right branch, follow it
247	* recursively.
248	*/
249	nc_rebuild(old_head, new_head, n->r, now);
250	}
251
252	if ((now - n->seen) < OptionsItem->negcache)
253	{
254	/*
255	* We want to keep this node, so insert it into the new
256	* trie.
257	*/
258	new = nc_insert(new_head, n->ip);
259	new->seen = n->seen;
260	}
261	else if (OPT_DEBUG >= 2)
262	{
263	log_printf("NEGCACHE -> Deleting negcache node for %lu added at %lu", n->ip,
264	n->seen);
265	}
266
267	/* Safe to free() this node now. */
268	MyFree(n);
269	}
270
271	/*
272	* Wrapper for recursive rebuild function.
273	*/
274	void negcache_rebuild(void)
275	{
276	time_t now;
277	struct cnode *new_head;
278
279	now = time(NULL);
280	new_head = NULL;
281
282	nc_init(&new_head);
283	nc_rebuild(nc_head, new_head, NULL, now);
284	MyFree(nc_head);
285	nc_head = new_head;
286	}