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 |
|
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 |
if (!inet_pton(AF_INET, ipstr, &(ip.sa4.sin_addr))) |
215 |
{ |
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 |
} |