1 |
michael |
5052 |
/* |
2 |
michael |
5350 |
* 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 |
michael |
5052 |
|
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 |
michael |
5312 |
#include <sys/types.h> |
46 |
|
|
#include <sys/socket.h> |
47 |
|
|
#include <netinet/in.h> |
48 |
|
|
#include <arpa/inet.h> |
49 |
michael |
5052 |
|
50 |
|
|
#include "irc.h" |
51 |
|
|
#include "negcache.h" |
52 |
|
|
#include "config.h" |
53 |
michael |
5336 |
#include "memory.h" |
54 |
michael |
5052 |
#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 |
michael |
5321 |
struct cnode *nc_head; |
65 |
michael |
5052 |
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 |
michael |
5275 |
*head = xcalloc(sizeof **head); |
86 |
michael |
5052 |
|
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 |
michael |
5275 |
t = xcalloc(sizeof *t); |
155 |
michael |
5052 |
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 |
michael |
5696 |
if (OptionsItem->negcache == 0) |
178 |
michael |
5052 |
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 |
michael |
5312 |
struct sockaddr_in ip; |
201 |
michael |
5052 |
struct cnode *n; |
202 |
|
|
|
203 |
michael |
5312 |
if (inet_pton(AF_INET, ipstr, &ip.sin_addr) <= 0) |
204 |
michael |
5052 |
{ |
205 |
|
|
log_printf("NEGCACHE -> Invalid IPv4 address '%s'", ipstr); |
206 |
|
|
return; |
207 |
|
|
} |
208 |
|
|
|
209 |
michael |
5312 |
n = nc_insert(nc_head, ip.sin_addr.s_addr); |
210 |
michael |
5052 |
|
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 |
michael |
5427 |
xfree(n); |
271 |
michael |
5052 |
} |
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 |
michael |
5427 |
xfree(nc_head); |
287 |
michael |
5052 |
nc_head = new_head; |
288 |
|
|
} |