ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/hopm/trunk/src/negcache.c
Revision: 5266
Committed: Thu Jan 1 18:49:40 2015 UTC (9 years, 2 months ago) by michael
Content type: text/x-csrc
File size: 6325 byte(s)
Log Message:
- Removed obsolete AC_HEADER_TIME

File Contents

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

Properties

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