ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/hopm/trunk/src/negcache.c
Revision: 5134
Committed: Thu Dec 25 18:50:02 2014 UTC (9 years, 3 months ago) by michael
Content type: text/x-csrc
File size: 6490 byte(s)
Log Message:
- propset svn:keywords "Id"

File Contents

# 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
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 }

Properties

Name Value
svn:keywords Id