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

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

Parent Directory Parent Directory | Revision Log Revision Log


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

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    
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 michael 5170 if (!inet_pton(AF_INET, ipstr, &(ip.sa4.sin_addr)))
214 michael 5052 {
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