ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/hopm/branches/1.0.x/src/negcache.c
Revision: 5321
Committed: Tue Jan 6 14:59:31 2015 UTC (9 years, 2 months ago) by michael
Content type: text/x-csrc
File size: 6398 byte(s)
Log Message:
- Fixed coding convention issues

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

Properties

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