trunk/src/negcache.c

/*
 *  Copyright (c) 2002-2003 Andy Smith
 *  Copyright (c) 2014-2015 ircd-hybrid development team
 *
 *  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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  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 <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#include "irc.h"
#include "negcache.h"
#include "config.h"
#include "memory.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);

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

/*
 * 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 = xcalloc(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 = xcalloc(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 sockaddr_in ip;
   struct cnode *n;

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

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