/[svn]/hopm/trunk/src/negcache.c
ViewVC logotype

Contents of /hopm/trunk/src/negcache.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5175 - (show annotations)
Fri Dec 26 21:09:41 2014 UTC (5 years, 7 months ago) by michael
File MIME type: text/x-chdr
File size: 6472 byte(s)
- Removed now unused inet.c and inet.h

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

Properties

Name Value
svn:eol-style native
svn:keywords Id

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.28