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>

#ifdef STDC_HEADERS
#include <stdlib.h>
#endif

#ifdef TIME_WITH_SYS_TIME
#include <sys/time.h>
#include <time.h>
#else
# ifdef HAVE_SYS_TIME_H
#  include <sys/time.h>
# else
#  include <time.h>
# endif
#endif

#include "inet.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)))
   {
      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:	5170
Committed:	Fri Dec 26 20:53:09 2014 UTC (10 years, 8 months ago) by michael
Content type:	text/x-csrc
File size:	6490 byte(s)
Log Message:	- Continue to use inet_pton() until we add full ipv6 support, but at least replace all occurrences of inet_aton() with inet_pton()
#	User	Rev	Content
1	michael	5052	/*
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
45			#ifdef STDC_HEADERS
46			#include <stdlib.h>
47			#endif
48
49			#ifdef TIME_WITH_SYS_TIME
50			#include <sys/time.h>
51			#include <time.h>
52			#else
53			# ifdef HAVE_SYS_TIME_H
54			# include <sys/time.h>
55			# else
56			# include <time.h>
57			# endif
58			#endif
59
60			#include "inet.h"
61			#include "irc.h"
62			#include "negcache.h"
63			#include "config.h"
64			#include "malloc.h"
65			#include "log.h"
66
67
68			extern unsigned int OPT_DEBUG;
69
70			static struct cnode nc_search(struct cnode head, const unsigned long ip);
71			static struct cnode nc_insert(struct cnode head, const unsigned long ip);
72			static void nc_rebuild(struct cnode old_head, struct cnode new_head,
73			struct cnode *n, time_t now);
74
75			time_t last_nc_expire;
76			unsigned int maxb;
77			extern struct cnode *nc_head;
78
79			/*
80			* Return the bit which appears k bits from the right in x.
81			*/
82			#define GETBIT(x,k) ((x >> k) & 1)
83
84
85			/*
86			* Initialise the patricia trie we use for storing our negative cache.
87			*/
88			void nc_init(struct cnode **head)
89			{
90			if (*head)
91			{
92			/* Cache already exists */
93			return;
94			}
95
96			head = MyMalloc(sizeof *head);
97
98			maxb = (sizeof((head)->ip) 8);
99			(*head)->ip = 0;
100			(*head)->b = maxb;
101			(head)->l = (head)->r = *head;
102			last_nc_expire = time(NULL);
103			}
104
105			/*
106			* Find and return a pointer to the trie node that corresponds to a given IP
107			* address as expressed in network form, or return NULL if the IP isn't
108			* present.
109			*/
110			static struct cnode nc_search(struct cnode head, const unsigned long ip)
111			{
112			struct cnode p, x;
113
114			p = head;
115			x = head->l;
116
117			while (p->b > x->b)
118			{
119			p = x;
120			x = GETBIT(ip, x->b) ? x->r : x->l;
121			}
122
123			if (ip == x->ip)
124			return(x);
125			else
126			return(NULL);
127			}
128
129			/*
130			* Insert a new node into the trie, and return a pointer to it.
131			*/
132			static struct cnode nc_insert(struct cnode head, const unsigned long ip)
133			{
134			unsigned int i;
135			struct cnode p, t, *x;
136
137			i = maxb;
138			p = head;
139			t = head->l;
140
141			while (p->b > t->b)
142			{
143			p = t;
144			t = GETBIT(ip, t->b) ? t->r : t->l;
145			}
146
147			if (ip == t->ip)
148			{
149			/* Node already exists. */
150			return(t);
151			}
152
153			while (GETBIT(t->ip, i) == GETBIT(ip, i))
154			i--;
155
156			p = head;
157			x = head->l;
158
159			while (p->b > x->b && x->b > i)
160			{
161			p = x;
162			x = GETBIT(ip, x->b) ? x->r : x->l;
163			}
164
165			t = MyMalloc(sizeof *t);
166			t->ip = ip;
167			t->b = i;
168			t->l = GETBIT(ip, t->b) ? x : t;
169			t->r = GETBIT(ip, t->b) ? t : x;
170
171			if (GETBIT(ip, p->b))
172			p->r = t;
173			else
174			p->l = t;
175
176			return(t);
177			}
178
179			/*
180			* Check whether an IP address is in our negative cache and was added
181			* recently enough. Return a pointer to its node if so, NULL otherwise.
182			*/
183			struct cnode *check_neg_cache(const unsigned long ip)
184			{
185			time_t now;
186			struct cnode *n;
187
188			if (OptionsItem->negcache <= 0)
189			return(NULL);
190
191			n = nc_search(nc_head, ip);
192
193			if (n)
194			{
195			/* Check it is recent enough. */
196			now = time(NULL);
197
198			if (now - n->seen <= OptionsItem->negcache)
199			return(n);
200			}
201
202			return(NULL);
203			}
204
205			/*
206			* Prepare an ASCII string representing an IPv4 address for inserting into
207			* our negative cache.
208			*/
209			void negcache_insert(const char *ipstr)
210			{
211			struct bopm_sockaddr ip;
212			struct cnode *n;
213
214	michael	5170	if (!inet_pton(AF_INET, ipstr, &(ip.sa4.sin_addr)))
215	michael	5052	{
216			log_printf("NEGCACHE -> Invalid IPv4 address '%s'", ipstr);
217			return;
218			}
219
220			n = nc_insert(nc_head, ip.sa4.sin_addr.s_addr);
221
222			if (n)
223			n->seen = time(NULL);
224			}
225
226			/*
227			* Recursively walk the cache and insert the nodes into a new patricia trie,
228			* skipping nodes that are too old.
229			*/
230			static void nc_rebuild(struct cnode old_head, struct cnode new_head,
231			struct cnode *n, time_t now)
232			{
233			struct cnode *new;
234
235			if (!n)
236			{
237			/* Start at head. */
238			n = old_head->l;
239			}
240
241			if (n == old_head)
242			{
243			/* Trie is empty. */
244			return;
245			}
246
247			if (n->b > n->l->b)
248			{
249			/*
250			* If the trie extends via the left branch, follow it
251			* recursively.
252			*/
253			nc_rebuild(old_head, new_head, n->l, now);
254			}
255
256			if (n->b > n->r->b)
257			{
258			/*
259			* If the trie extends via the right branch, follow it
260			* recursively.
261			*/
262			nc_rebuild(old_head, new_head, n->r, now);
263			}
264
265			if ((now - n->seen) < OptionsItem->negcache)
266			{
267			/*
268			* We want to keep this node, so insert it into the new
269			* trie.
270			*/
271			new = nc_insert(new_head, n->ip);
272			new->seen = n->seen;
273			}
274			else if (OPT_DEBUG >= 2)
275			{
276			log_printf("NEGCACHE -> Deleting negcache node for %lu added at %lu", n->ip,
277			n->seen);
278			}
279
280			/* Safe to free() this node now. */
281			MyFree(n);
282			}
283
284			/*
285			* Wrapper for recursive rebuild function.
286			*/
287			void negcache_rebuild(void)
288			{
289			time_t now;
290			struct cnode *new_head;
291
292			now = time(NULL);
293			new_head = NULL;
294
295			nc_init(&new_head);
296			nc_rebuild(nc_head, new_head, NULL, now);
297			MyFree(nc_head);
298			nc_head = new_head;
299			}