ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/hopm/branches/1.0.x/src/negcache.c
Revision: 5696
Committed: Sun Mar 15 13:04:50 2015 UTC (9 years ago) by michael
Content type: text/x-csrc
File size: 6489 byte(s)
Log Message:
- Style corrections

File Contents

# User Rev Content
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     }

Properties

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