[NETFILTER]: Fix recent match jiffies wrap mismatches
[linux-2.6.git] / net / ipv4 / netfilter / ipt_recent.c
1 /* Kernel module to check if the source address has been seen recently. */
2 /* Copyright 2002-2003, Stephen Frost, 2.5.x port by laforge@netfilter.org */
3 /* Author: Stephen Frost <sfrost@snowman.net> */
4 /* Project Page: http://snowman.net/projects/ipt_recent/ */
5 /* This software is distributed under the terms of the GPL, Version 2 */
6 /* This copyright does not cover user programs that use kernel services
7  * by normal system calls. */
8
9 #include <linux/module.h>
10 #include <linux/skbuff.h>
11 #include <linux/proc_fs.h>
12 #include <linux/spinlock.h>
13 #include <linux/interrupt.h>
14 #include <asm/uaccess.h>
15 #include <linux/ctype.h>
16 #include <linux/ip.h>
17 #include <linux/vmalloc.h>
18 #include <linux/moduleparam.h>
19
20 #include <linux/netfilter_ipv4/ip_tables.h>
21 #include <linux/netfilter_ipv4/ipt_recent.h>
22
23 #undef DEBUG
24 #define HASH_LOG 9
25
26 /* Defaults, these can be overridden on the module command-line. */
27 static int ip_list_tot = 100;
28 static int ip_pkt_list_tot = 20;
29 static int ip_list_hash_size = 0;
30 static int ip_list_perms = 0644;
31 #ifdef DEBUG
32 static int debug = 1;
33 #endif
34
35 static char version[] =
36 KERN_INFO RECENT_NAME " " RECENT_VER ": Stephen Frost <sfrost@snowman.net>.  http://snowman.net/projects/ipt_recent/\n";
37
38 MODULE_AUTHOR("Stephen Frost <sfrost@snowman.net>");
39 MODULE_DESCRIPTION("IP tables recently seen matching module " RECENT_VER);
40 MODULE_LICENSE("GPL");
41 module_param(ip_list_tot, int, 0400);
42 module_param(ip_pkt_list_tot, int, 0400);
43 module_param(ip_list_hash_size, int, 0400);
44 module_param(ip_list_perms, int, 0400);
45 #ifdef DEBUG
46 module_param(debug, int, 0600);
47 MODULE_PARM_DESC(debug,"debugging level, defaults to 1");
48 #endif
49 MODULE_PARM_DESC(ip_list_tot,"number of IPs to remember per list");
50 MODULE_PARM_DESC(ip_pkt_list_tot,"number of packets per IP to remember");
51 MODULE_PARM_DESC(ip_list_hash_size,"size of hash table used to look up IPs");
52 MODULE_PARM_DESC(ip_list_perms,"permissions on /proc/net/ipt_recent/* files");
53
54 /* Structure of our list of recently seen addresses. */
55 struct recent_ip_list {
56         u_int32_t addr;
57         u_int8_t  ttl;
58         unsigned long last_seen;
59         unsigned long *last_pkts;
60         u_int32_t oldest_pkt;
61         u_int32_t hash_entry;
62         u_int32_t time_pos;
63 };
64
65 struct time_info_list {
66         u_int32_t position;
67         u_int32_t time;
68 };
69
70 /* Structure of our linked list of tables of recent lists. */
71 struct recent_ip_tables {
72         char name[IPT_RECENT_NAME_LEN];
73         int count;
74         int time_pos;
75         struct recent_ip_list *table;
76         struct recent_ip_tables *next;
77         spinlock_t list_lock;
78         int *hash_table;
79         struct time_info_list *time_info;
80 #ifdef CONFIG_PROC_FS
81         struct proc_dir_entry *status_proc;
82 #endif /* CONFIG_PROC_FS */
83 };
84
85 /* Our current list of addresses we have recently seen.
86  * Only added to on a --set, and only updated on --set || --update 
87  */
88 static struct recent_ip_tables *r_tables = NULL;
89
90 /* We protect r_list with this spinlock so two processors are not modifying
91  * the list at the same time. 
92  */
93 static DEFINE_SPINLOCK(recent_lock);
94
95 #ifdef CONFIG_PROC_FS
96 /* Our /proc/net/ipt_recent entry */
97 static struct proc_dir_entry *proc_net_ipt_recent = NULL;
98 #endif
99
100 /* Function declaration for later. */
101 static int
102 match(const struct sk_buff *skb,
103       const struct net_device *in,
104       const struct net_device *out,
105       const void *matchinfo,
106       int offset,
107       int *hotdrop);
108
109 /* Function to hash a given address into the hash table of table_size size */
110 static int hash_func(unsigned int addr, int table_size)
111 {
112         int result = 0;
113         unsigned int value = addr;
114         do { result ^= value; } while((value >>= HASH_LOG));
115
116 #ifdef DEBUG
117         if(debug) printk(KERN_INFO RECENT_NAME ": %d = hash_func(%u,%d)\n",
118                          result & (table_size - 1),
119                          addr,
120                          table_size);
121 #endif
122
123         return(result & (table_size - 1));
124 }
125
126 #ifdef CONFIG_PROC_FS
127 /* This is the function which produces the output for our /proc output
128  * interface which lists each IP address, the last seen time and the 
129  * other recent times the address was seen.
130  */
131
132 static int ip_recent_get_info(char *buffer, char **start, off_t offset, int length, int *eof, void *data)
133 {
134         int len = 0, count, last_len = 0, pkt_count;
135         off_t pos = 0;
136         off_t begin = 0;
137         struct recent_ip_tables *curr_table;
138
139         curr_table = (struct recent_ip_tables*) data;
140
141         spin_lock_bh(&curr_table->list_lock);
142         for(count = 0; count < ip_list_tot; count++) {
143                 if(!curr_table->table[count].addr) continue;
144                 last_len = len;
145                 len += sprintf(buffer+len,"src=%u.%u.%u.%u ",NIPQUAD(curr_table->table[count].addr));
146                 len += sprintf(buffer+len,"ttl: %u ",curr_table->table[count].ttl);
147                 len += sprintf(buffer+len,"last_seen: %lu ",curr_table->table[count].last_seen);
148                 len += sprintf(buffer+len,"oldest_pkt: %u ",curr_table->table[count].oldest_pkt);
149                 len += sprintf(buffer+len,"last_pkts: %lu",curr_table->table[count].last_pkts[0]);
150                 for(pkt_count = 1; pkt_count < ip_pkt_list_tot; pkt_count++) {
151                         if(!curr_table->table[count].last_pkts[pkt_count]) break;
152                         len += sprintf(buffer+len,", %lu",curr_table->table[count].last_pkts[pkt_count]);
153                 }
154                 len += sprintf(buffer+len,"\n");
155                 pos = begin + len;
156                 if(pos < offset) { len = 0; begin = pos; }
157                 if(pos > offset + length) { len = last_len; break; }
158         }
159
160         *start = buffer + (offset - begin);
161         len -= (offset - begin);
162         if(len > length) len = length;
163
164         spin_unlock_bh(&curr_table->list_lock);
165         return len;
166 }
167
168 /* ip_recent_ctrl provides an interface for users to modify the table
169  * directly.  This allows adding entries, removing entries, and
170  * flushing the entire table.
171  * This is done by opening up the appropriate table for writing and
172  * sending one of:
173  * xx.xx.xx.xx   -- Add entry to table with current time
174  * +xx.xx.xx.xx  -- Add entry to table with current time
175  * -xx.xx.xx.xx  -- Remove entry from table
176  * clear         -- Flush table, remove all entries
177  */
178
179 static int ip_recent_ctrl(struct file *file, const char __user *input, unsigned long size, void *data)
180 {
181         static const u_int32_t max[4] = { 0xffffffff, 0xffffff, 0xffff, 0xff };
182         u_int32_t val;
183         int base, used = 0;
184         char c, *cp;
185         union iaddr {
186                 uint8_t bytes[4];
187                 uint32_t word;
188         } res;
189         uint8_t *pp = res.bytes;
190         int digit;
191
192         char buffer[20];
193         int len, check_set = 0, count;
194         u_int32_t addr = 0;
195         struct sk_buff *skb;
196         struct ipt_recent_info *info;
197         struct recent_ip_tables *curr_table;
198
199         curr_table = (struct recent_ip_tables*) data;
200
201         if(size > 20) len = 20; else len = size;
202
203         if(copy_from_user(buffer,input,len)) return -EFAULT;
204
205         if(len < 20) buffer[len] = '\0';
206
207 #ifdef DEBUG
208         if(debug) printk(KERN_INFO RECENT_NAME ": ip_recent_ctrl len: %d, input: `%.20s'\n",len,buffer);
209 #endif
210
211         cp = buffer;
212         while(isspace(*cp)) { cp++; used++; if(used >= len-5) return used; }
213
214         /* Check if we are asked to flush the entire table */
215         if(!memcmp(cp,"clear",5)) {
216                 used += 5;
217                 spin_lock_bh(&curr_table->list_lock);
218                 curr_table->time_pos = 0;
219                 for(count = 0; count < ip_list_hash_size; count++) {
220                         curr_table->hash_table[count] = -1;
221                 }
222                 for(count = 0; count < ip_list_tot; count++) {
223                         curr_table->table[count].last_seen = 0;
224                         curr_table->table[count].addr = 0;
225                         curr_table->table[count].ttl = 0;
226                         memset(curr_table->table[count].last_pkts,0,ip_pkt_list_tot*sizeof(unsigned long));
227                         curr_table->table[count].oldest_pkt = 0;
228                         curr_table->table[count].time_pos = 0;
229                         curr_table->time_info[count].position = count;
230                         curr_table->time_info[count].time = 0;
231                 }
232                 spin_unlock_bh(&curr_table->list_lock);
233                 return used;
234         }
235
236         check_set = IPT_RECENT_SET;
237         switch(*cp) {
238                 case '+': check_set = IPT_RECENT_SET; cp++; used++; break;
239                 case '-': check_set = IPT_RECENT_REMOVE; cp++; used++; break;
240                 default: if(!isdigit(*cp)) return (used+1); break;
241         }
242
243 #ifdef DEBUG
244         if(debug) printk(KERN_INFO RECENT_NAME ": ip_recent_ctrl cp: `%c', check_set: %d\n",*cp,check_set);
245 #endif
246         /* Get addr (effectively inet_aton()) */
247         /* Shamelessly stolen from libc, a function in the kernel for doing
248          * this would, of course, be greatly preferred, but our options appear
249          * to be rather limited, so we will just do it ourselves here.
250          */
251         res.word = 0;
252
253         c = *cp;
254         for(;;) {
255                 if(!isdigit(c)) return used;
256                 val = 0; base = 10; digit = 0;
257                 if(c == '0') {
258                         c = *++cp;
259                         if(c == 'x' || c == 'X') base = 16, c = *++cp;
260                         else { base = 8; digit = 1; }
261                 }
262                 for(;;) {
263                         if(isascii(c) && isdigit(c)) {
264                                 if(base == 8 && (c == '8' || c == '0')) return used;
265                                 val = (val * base) + (c - '0');
266                                 c = *++cp;
267                                 digit = 1;
268                         } else if(base == 16 && isascii(c) && isxdigit(c)) {
269                                 val = (val << 4) | (c + 10 - (islower(c) ? 'a' : 'A'));
270                                 c = *++cp;
271                                 digit = 1;
272                         } else break;
273                 }
274                 if(c == '.') {
275                         if(pp > res.bytes + 2 || val > 0xff) return used;
276                         *pp++ = val;
277                         c = *++cp;
278                 } else break;
279         }
280         used = cp - buffer;
281         if(c != '\0' && (!isascii(c) || !isspace(c))) return used;
282         if(c == '\n') used++;
283         if(!digit) return used;
284
285         if(val > max[pp - res.bytes]) return used;
286         addr = res.word | htonl(val);
287
288         if(!addr && check_set == IPT_RECENT_SET) return used;
289
290 #ifdef DEBUG
291         if(debug) printk(KERN_INFO RECENT_NAME ": ip_recent_ctrl c: %c, addr: %u used: %d\n",c,addr,used);
292 #endif
293
294         /* Set up and just call match */
295         info = kmalloc(sizeof(struct ipt_recent_info),GFP_KERNEL);
296         if(!info) { return -ENOMEM; }
297         info->seconds = 0;
298         info->hit_count = 0;
299         info->check_set = check_set;
300         info->invert = 0;
301         info->side = IPT_RECENT_SOURCE;
302         strncpy(info->name,curr_table->name,IPT_RECENT_NAME_LEN);
303         info->name[IPT_RECENT_NAME_LEN-1] = '\0';
304
305         skb = kmalloc(sizeof(struct sk_buff),GFP_KERNEL);
306         if (!skb) {
307                 used = -ENOMEM;
308                 goto out_free_info;
309         }
310         skb->nh.iph = kmalloc(sizeof(struct iphdr),GFP_KERNEL);
311         if (!skb->nh.iph) {
312                 used = -ENOMEM;
313                 goto out_free_skb;
314         }
315
316         skb->nh.iph->saddr = addr;
317         skb->nh.iph->daddr = 0;
318         /* Clear ttl since we have no way of knowing it */
319         skb->nh.iph->ttl = 0;
320         match(skb,NULL,NULL,info,0,NULL);
321
322         kfree(skb->nh.iph);
323 out_free_skb:
324         kfree(skb);
325 out_free_info:
326         kfree(info);
327
328 #ifdef DEBUG
329         if(debug) printk(KERN_INFO RECENT_NAME ": Leaving ip_recent_ctrl addr: %u used: %d\n",addr,used);
330 #endif
331         return used;
332 }
333
334 #endif /* CONFIG_PROC_FS */
335
336 /* 'match' is our primary function, called by the kernel whenever a rule is
337  * hit with our module as an option to it.
338  * What this function does depends on what was specifically asked of it by
339  * the user:
340  * --set -- Add or update last seen time of the source address of the packet
341  *   -- matchinfo->check_set == IPT_RECENT_SET
342  * --rcheck -- Just check if the source address is in the list
343  *   -- matchinfo->check_set == IPT_RECENT_CHECK
344  * --update -- If the source address is in the list, update last_seen
345  *   -- matchinfo->check_set == IPT_RECENT_UPDATE
346  * --remove -- If the source address is in the list, remove it
347  *   -- matchinfo->check_set == IPT_RECENT_REMOVE
348  * --seconds -- Option to --rcheck/--update, only match if last_seen within seconds
349  *   -- matchinfo->seconds
350  * --hitcount -- Option to --rcheck/--update, only match if seen hitcount times
351  *   -- matchinfo->hit_count
352  * --seconds and --hitcount can be combined
353  */
354 static int
355 match(const struct sk_buff *skb,
356       const struct net_device *in,
357       const struct net_device *out,
358       const void *matchinfo,
359       int offset,
360       int *hotdrop)
361 {
362         int pkt_count, hits_found, ans;
363         unsigned long now;
364         const struct ipt_recent_info *info = matchinfo;
365         u_int32_t addr = 0, time_temp;
366         u_int8_t ttl = skb->nh.iph->ttl;
367         int *hash_table;
368         int orig_hash_result, hash_result, temp, location = 0, time_loc, end_collision_chain = -1;
369         struct time_info_list *time_info;
370         struct recent_ip_tables *curr_table;
371         struct recent_ip_tables *last_table;
372         struct recent_ip_list *r_list;
373
374 #ifdef DEBUG
375         if(debug) printk(KERN_INFO RECENT_NAME ": match() called\n");
376 #endif
377
378         /* Default is false ^ info->invert */
379         ans = info->invert;
380
381 #ifdef DEBUG
382         if(debug) printk(KERN_INFO RECENT_NAME ": match(): name = '%s'\n",info->name);
383 #endif
384
385         /* if out != NULL then routing has been done and TTL changed.
386          * We change it back here internally for match what came in before routing. */
387         if(out) ttl++;
388
389         /* Find the right table */
390         spin_lock_bh(&recent_lock);
391         curr_table = r_tables;
392         while( (last_table = curr_table) && strncmp(info->name,curr_table->name,IPT_RECENT_NAME_LEN) && (curr_table = curr_table->next) );
393
394 #ifdef DEBUG
395         if(debug) printk(KERN_INFO RECENT_NAME ": match(): table found('%s')\n",info->name);
396 #endif
397
398         spin_unlock_bh(&recent_lock);
399
400         /* Table with this name not found, match impossible */
401         if(!curr_table) { return ans; }
402
403         /* Make sure no one is changing the list while we work with it */
404         spin_lock_bh(&curr_table->list_lock);
405
406         r_list = curr_table->table;
407         if(info->side == IPT_RECENT_DEST) addr = skb->nh.iph->daddr; else addr = skb->nh.iph->saddr;
408
409         if(!addr) { 
410 #ifdef DEBUG
411                 if(debug) printk(KERN_INFO RECENT_NAME ": match() address (%u) invalid, leaving.\n",addr);
412 #endif
413                 spin_unlock_bh(&curr_table->list_lock);
414                 return ans;
415         }
416
417 #ifdef DEBUG
418         if(debug) printk(KERN_INFO RECENT_NAME ": match(): checking table, addr: %u, ttl: %u, orig_ttl: %u\n",addr,ttl,skb->nh.iph->ttl);
419 #endif
420
421         /* Get jiffies now in case they changed while we were waiting for a lock */
422         now = jiffies;
423         hash_table = curr_table->hash_table;
424         time_info = curr_table->time_info;
425
426         orig_hash_result = hash_result = hash_func(addr,ip_list_hash_size);
427         /* Hash entry at this result used */
428         /* Check for TTL match if requested.  If TTL is zero then a match would never
429          * happen, so match regardless of existing TTL in that case.  Zero means the
430          * entry was added via the /proc interface anyway, so we will just use the
431          * first TTL we get for that IP address. */
432         if(info->check_set & IPT_RECENT_TTL) {
433                 while(hash_table[hash_result] != -1 && !(r_list[hash_table[hash_result]].addr == addr &&
434                         (!r_list[hash_table[hash_result]].ttl || r_list[hash_table[hash_result]].ttl == ttl))) {
435                         /* Collision in hash table */
436                         hash_result = (hash_result + 1) % ip_list_hash_size;
437                 }
438         } else {
439                 while(hash_table[hash_result] != -1 && r_list[hash_table[hash_result]].addr != addr) {
440                         /* Collision in hash table */
441                         hash_result = (hash_result + 1) % ip_list_hash_size;
442                 }
443         }
444
445         if(hash_table[hash_result] == -1 && !(info->check_set & IPT_RECENT_SET)) {
446                 /* IP not in list and not asked to SET */
447                 spin_unlock_bh(&curr_table->list_lock);
448                 return ans;
449         }
450
451         /* Check if we need to handle the collision, do not need to on REMOVE */
452         if(orig_hash_result != hash_result && !(info->check_set & IPT_RECENT_REMOVE)) {
453 #ifdef DEBUG
454                 if(debug) printk(KERN_INFO RECENT_NAME ": match(): Collision in hash table. (or: %d,hr: %d,oa: %u,ha: %u)\n",
455                                  orig_hash_result,
456                                  hash_result,
457                                  r_list[hash_table[orig_hash_result]].addr,
458                                  addr);
459 #endif
460
461                 /* We had a collision.
462                  * orig_hash_result is where we started, hash_result is where we ended up.
463                  * So, swap them because we are likely to see the same guy again sooner */
464 #ifdef DEBUG
465                 if(debug) {
466                   printk(KERN_INFO RECENT_NAME ": match(): Collision; hash_table[orig_hash_result] = %d\n",hash_table[orig_hash_result]);
467                   printk(KERN_INFO RECENT_NAME ": match(): Collision; r_list[hash_table[orig_hash_result]].hash_entry = %d\n",
468                                 r_list[hash_table[orig_hash_result]].hash_entry);
469                 }
470 #endif
471
472                 r_list[hash_table[orig_hash_result]].hash_entry = hash_result;
473
474
475                 temp = hash_table[orig_hash_result];
476 #ifdef DEBUG
477                 if(debug) printk(KERN_INFO RECENT_NAME ": match(): Collision; hash_table[hash_result] = %d\n",hash_table[hash_result]);
478 #endif
479                 hash_table[orig_hash_result] = hash_table[hash_result];
480                 hash_table[hash_result] = temp;
481                 temp = hash_result;
482                 hash_result = orig_hash_result;
483                 orig_hash_result = temp;
484                 time_info[r_list[hash_table[orig_hash_result]].time_pos].position = hash_table[orig_hash_result];
485                 if(hash_table[hash_result] != -1) {
486                         r_list[hash_table[hash_result]].hash_entry = hash_result;
487                         time_info[r_list[hash_table[hash_result]].time_pos].position = hash_table[hash_result];
488                 }
489
490 #ifdef DEBUG
491                 if(debug) printk(KERN_INFO RECENT_NAME ": match(): Collision handled.\n");
492 #endif
493         }
494
495         if(hash_table[hash_result] == -1) {
496 #ifdef DEBUG
497                 if(debug) printk(KERN_INFO RECENT_NAME ": match(): New table entry. (hr: %d,ha: %u)\n",
498                                  hash_result, addr);
499 #endif
500
501                 /* New item found and IPT_RECENT_SET, so we need to add it */
502                 location = time_info[curr_table->time_pos].position;
503                 hash_table[r_list[location].hash_entry] = -1;
504                 hash_table[hash_result] = location;
505                 memset(r_list[location].last_pkts,0,ip_pkt_list_tot*sizeof(unsigned long));
506                 r_list[location].time_pos = curr_table->time_pos;
507                 r_list[location].addr = addr;
508                 r_list[location].ttl = ttl;
509                 r_list[location].last_seen = now;
510                 r_list[location].oldest_pkt = 1;
511                 r_list[location].last_pkts[0] = now;
512                 r_list[location].hash_entry = hash_result;
513                 time_info[curr_table->time_pos].time = r_list[location].last_seen;
514                 curr_table->time_pos = (curr_table->time_pos + 1) % ip_list_tot;
515
516                 ans = !info->invert;
517         } else {
518 #ifdef DEBUG
519                 if(debug) printk(KERN_INFO RECENT_NAME ": match(): Existing table entry. (hr: %d,ha: %u)\n",
520                                  hash_result,
521                                  addr);
522 #endif
523
524                 /* Existing item found */
525                 location = hash_table[hash_result];
526                 /* We have a match on address, now to make sure it meets all requirements for a
527                  * full match. */
528                 if(info->check_set & IPT_RECENT_CHECK || info->check_set & IPT_RECENT_UPDATE) {
529                         if(!info->seconds && !info->hit_count) ans = !info->invert; else ans = info->invert;
530                         if(info->seconds && !info->hit_count) {
531                                 if(time_before_eq(now,r_list[location].last_seen+info->seconds*HZ)) ans = !info->invert; else ans = info->invert;
532                         }
533                         if(info->seconds && info->hit_count) {
534                                 for(pkt_count = 0, hits_found = 0; pkt_count < ip_pkt_list_tot; pkt_count++) {
535                                         if(r_list[location].last_pkts[pkt_count] == 0) break;
536                                         if(time_before_eq(now,r_list[location].last_pkts[pkt_count]+info->seconds*HZ)) hits_found++;
537                                 }
538                                 if(hits_found >= info->hit_count) ans = !info->invert; else ans = info->invert;
539                         }
540                         if(info->hit_count && !info->seconds) {
541                                 for(pkt_count = 0, hits_found = 0; pkt_count < ip_pkt_list_tot; pkt_count++) {
542                                         if(r_list[location].last_pkts[pkt_count] == 0) break;
543                                         hits_found++;
544                                 }
545                                 if(hits_found >= info->hit_count) ans = !info->invert; else ans = info->invert;
546                         }
547                 }
548 #ifdef DEBUG
549                 if(debug) {
550                         if(ans)
551                                 printk(KERN_INFO RECENT_NAME ": match(): match addr: %u\n",addr);
552                         else
553                                 printk(KERN_INFO RECENT_NAME ": match(): no match addr: %u\n",addr);
554                 }
555 #endif
556
557                 /* If and only if we have been asked to SET, or to UPDATE (on match) do we add the
558                  * current timestamp to the last_seen. */
559                 if((info->check_set & IPT_RECENT_SET && (ans = !info->invert)) || (info->check_set & IPT_RECENT_UPDATE && ans)) {
560 #ifdef DEBUG
561                         if(debug) printk(KERN_INFO RECENT_NAME ": match(): SET or UPDATE; updating time info.\n");
562 #endif
563                         /* Have to update our time info */
564                         time_loc = r_list[location].time_pos;
565                         time_info[time_loc].time = now;
566                         time_info[time_loc].position = location;
567                         while((time_info[(time_loc+1) % ip_list_tot].time < time_info[time_loc].time) && ((time_loc+1) % ip_list_tot) != curr_table->time_pos) {
568                                 time_temp = time_info[time_loc].time;
569                                 time_info[time_loc].time = time_info[(time_loc+1)%ip_list_tot].time;
570                                 time_info[(time_loc+1)%ip_list_tot].time = time_temp;
571                                 time_temp = time_info[time_loc].position;
572                                 time_info[time_loc].position = time_info[(time_loc+1)%ip_list_tot].position;
573                                 time_info[(time_loc+1)%ip_list_tot].position = time_temp;
574                                 r_list[time_info[time_loc].position].time_pos = time_loc;
575                                 r_list[time_info[(time_loc+1)%ip_list_tot].position].time_pos = (time_loc+1)%ip_list_tot;
576                                 time_loc = (time_loc+1) % ip_list_tot;
577                         }
578                         r_list[location].time_pos = time_loc;
579                         r_list[location].ttl = ttl;
580                         r_list[location].last_pkts[r_list[location].oldest_pkt] = now;
581                         r_list[location].oldest_pkt = ++r_list[location].oldest_pkt % ip_pkt_list_tot;
582                         r_list[location].last_seen = now;
583                 }
584                 /* If we have been asked to remove the entry from the list, just set it to 0 */
585                 if(info->check_set & IPT_RECENT_REMOVE) {
586 #ifdef DEBUG
587                         if(debug) printk(KERN_INFO RECENT_NAME ": match(): REMOVE; clearing entry (or: %d, hr: %d).\n",orig_hash_result,hash_result);
588 #endif
589                         /* Check if this is part of a collision chain */
590                         while(hash_table[(orig_hash_result+1) % ip_list_hash_size] != -1) {
591                                 orig_hash_result++;
592                                 if(hash_func(r_list[hash_table[orig_hash_result]].addr,ip_list_hash_size) == hash_result) {
593                                         /* Found collision chain, how deep does this rabbit hole go? */
594 #ifdef DEBUG
595                                         if(debug) printk(KERN_INFO RECENT_NAME ": match(): REMOVE; found collision chain.\n");
596 #endif
597                                         end_collision_chain = orig_hash_result;
598                                 }
599                         }
600                         if(end_collision_chain != -1) {
601 #ifdef DEBUG
602                                 if(debug) printk(KERN_INFO RECENT_NAME ": match(): REMOVE; part of collision chain, moving to end.\n");
603 #endif
604                                 /* Part of a collision chain, swap it with the end of the chain
605                                  * before removing. */
606                                 r_list[hash_table[end_collision_chain]].hash_entry = hash_result;
607                                 temp = hash_table[end_collision_chain];
608                                 hash_table[end_collision_chain] = hash_table[hash_result];
609                                 hash_table[hash_result] = temp;
610                                 time_info[r_list[hash_table[hash_result]].time_pos].position = hash_table[hash_result];
611                                 hash_result = end_collision_chain;
612                                 r_list[hash_table[hash_result]].hash_entry = hash_result;
613                                 time_info[r_list[hash_table[hash_result]].time_pos].position = hash_table[hash_result];
614                         }
615                         location = hash_table[hash_result];
616                         hash_table[r_list[location].hash_entry] = -1;
617                         time_loc = r_list[location].time_pos;
618                         time_info[time_loc].time = 0;
619                         time_info[time_loc].position = location;
620                         while((time_info[(time_loc+1) % ip_list_tot].time < time_info[time_loc].time) && ((time_loc+1) % ip_list_tot) != curr_table->time_pos) {
621                                 time_temp = time_info[time_loc].time;
622                                 time_info[time_loc].time = time_info[(time_loc+1)%ip_list_tot].time;
623                                 time_info[(time_loc+1)%ip_list_tot].time = time_temp;
624                                 time_temp = time_info[time_loc].position;
625                                 time_info[time_loc].position = time_info[(time_loc+1)%ip_list_tot].position;
626                                 time_info[(time_loc+1)%ip_list_tot].position = time_temp;
627                                 r_list[time_info[time_loc].position].time_pos = time_loc;
628                                 r_list[time_info[(time_loc+1)%ip_list_tot].position].time_pos = (time_loc+1)%ip_list_tot;
629                                 time_loc = (time_loc+1) % ip_list_tot;
630                         }
631                         r_list[location].time_pos = time_loc;
632                         r_list[location].last_seen = 0;
633                         r_list[location].addr = 0;
634                         r_list[location].ttl = 0;
635                         memset(r_list[location].last_pkts,0,ip_pkt_list_tot*sizeof(unsigned long));
636                         r_list[location].oldest_pkt = 0;
637                         ans = !info->invert;
638                 }
639                 spin_unlock_bh(&curr_table->list_lock);
640                 return ans;
641         }
642
643         spin_unlock_bh(&curr_table->list_lock);
644 #ifdef DEBUG
645         if(debug) printk(KERN_INFO RECENT_NAME ": match() left.\n");
646 #endif
647         return ans;
648 }
649
650 /* This function is to verify that the rule given during the userspace iptables
651  * command is correct.
652  * If the command is valid then we check if the table name referred to by the
653  * rule exists, if not it is created.
654  */
655 static int
656 checkentry(const char *tablename,
657            const struct ipt_ip *ip,
658            void *matchinfo,
659            unsigned int matchsize,
660            unsigned int hook_mask)
661 {
662         int flag = 0, c;
663         unsigned long *hold;
664         const struct ipt_recent_info *info = matchinfo;
665         struct recent_ip_tables *curr_table, *find_table, *last_table;
666
667 #ifdef DEBUG
668         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() entered.\n");
669 #endif
670
671         if (matchsize != IPT_ALIGN(sizeof(struct ipt_recent_info))) return 0;
672
673         /* seconds and hit_count only valid for CHECK/UPDATE */
674         if(info->check_set & IPT_RECENT_SET) { flag++; if(info->seconds || info->hit_count) return 0; }
675         if(info->check_set & IPT_RECENT_REMOVE) { flag++; if(info->seconds || info->hit_count) return 0; }
676         if(info->check_set & IPT_RECENT_CHECK) flag++;
677         if(info->check_set & IPT_RECENT_UPDATE) flag++;
678
679         /* One and only one of these should ever be set */
680         if(flag != 1) return 0;
681
682         /* Name must be set to something */
683         if(!info->name || !info->name[0]) return 0;
684
685         /* Things look good, create a list for this if it does not exist */
686         /* Lock the linked list while we play with it */
687         spin_lock_bh(&recent_lock);
688
689         /* Look for an entry with this name already created */
690         /* Finds the end of the list and the entry before the end if current name does not exist */
691         find_table = r_tables;
692         while( (last_table = find_table) && strncmp(info->name,find_table->name,IPT_RECENT_NAME_LEN) && (find_table = find_table->next) );
693
694         /* If a table already exists just increment the count on that table and return */
695         if(find_table) { 
696 #ifdef DEBUG
697                 if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: table found (%s), incrementing count.\n",info->name);
698 #endif
699                 find_table->count++;
700                 spin_unlock_bh(&recent_lock);
701                 return 1;
702         }
703
704         spin_unlock_bh(&recent_lock);
705
706         /* Table with this name not found */
707         /* Allocate memory for new linked list item */
708
709 #ifdef DEBUG
710         if(debug) {
711                 printk(KERN_INFO RECENT_NAME ": checkentry: no table found (%s)\n",info->name);
712                 printk(KERN_INFO RECENT_NAME ": checkentry: Allocationg %d for link-list entry.\n",sizeof(struct recent_ip_tables));
713         }
714 #endif
715
716         curr_table = vmalloc(sizeof(struct recent_ip_tables));
717         if(curr_table == NULL) return 0;
718
719         spin_lock_init(&curr_table->list_lock);
720         curr_table->next = NULL;
721         curr_table->count = 1;
722         curr_table->time_pos = 0;
723         strncpy(curr_table->name,info->name,IPT_RECENT_NAME_LEN);
724         curr_table->name[IPT_RECENT_NAME_LEN-1] = '\0';
725
726         /* Allocate memory for this table and the list of packets in each entry. */
727 #ifdef DEBUG
728         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for table (%s).\n",
729                         sizeof(struct recent_ip_list)*ip_list_tot,
730                         info->name);
731 #endif
732
733         curr_table->table = vmalloc(sizeof(struct recent_ip_list)*ip_list_tot);
734         if(curr_table->table == NULL) { vfree(curr_table); return 0; }
735         memset(curr_table->table,0,sizeof(struct recent_ip_list)*ip_list_tot);
736 #ifdef DEBUG
737         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for pkt_list.\n",
738                         sizeof(unsigned long)*ip_pkt_list_tot*ip_list_tot);
739 #endif
740
741         hold = vmalloc(sizeof(unsigned long)*ip_pkt_list_tot*ip_list_tot);
742 #ifdef DEBUG
743         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: After pkt_list allocation.\n");
744 #endif
745         if(hold == NULL) { 
746                 printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for pkt_list.\n");
747                 vfree(curr_table->table); 
748                 vfree(curr_table);
749                 return 0;
750         }
751         for(c = 0; c < ip_list_tot; c++) {
752                 curr_table->table[c].last_pkts = hold + c*ip_pkt_list_tot;
753         }
754
755         /* Allocate memory for the hash table */
756 #ifdef DEBUG
757         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for hash_table.\n",
758                         sizeof(int)*ip_list_hash_size);
759 #endif
760
761         curr_table->hash_table = vmalloc(sizeof(int)*ip_list_hash_size);
762         if(!curr_table->hash_table) {
763                 printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for hash_table.\n");
764                 vfree(hold);
765                 vfree(curr_table->table); 
766                 vfree(curr_table);
767                 return 0;
768         }
769
770         for(c = 0; c < ip_list_hash_size; c++) {
771                 curr_table->hash_table[c] = -1;
772         }
773
774         /* Allocate memory for the time info */
775 #ifdef DEBUG
776         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for time_info.\n",
777                         sizeof(struct time_info_list)*ip_list_tot);
778 #endif
779
780         curr_table->time_info = vmalloc(sizeof(struct time_info_list)*ip_list_tot);
781         if(!curr_table->time_info) {
782                 printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for time_info.\n");
783                 vfree(curr_table->hash_table);
784                 vfree(hold);
785                 vfree(curr_table->table); 
786                 vfree(curr_table);
787                 return 0;
788         }
789         for(c = 0; c < ip_list_tot; c++) {
790                 curr_table->time_info[c].position = c;
791                 curr_table->time_info[c].time = 0;
792         }
793
794         /* Put the new table in place */
795         spin_lock_bh(&recent_lock);
796         find_table = r_tables;
797         while( (last_table = find_table) && strncmp(info->name,find_table->name,IPT_RECENT_NAME_LEN) && (find_table = find_table->next) );
798
799         /* If a table already exists just increment the count on that table and return */
800         if(find_table) { 
801                 find_table->count++;    
802                 spin_unlock_bh(&recent_lock);
803 #ifdef DEBUG
804                 if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: table found (%s), created by other process.\n",info->name);
805 #endif
806                 vfree(curr_table->time_info);
807                 vfree(curr_table->hash_table);
808                 vfree(hold);
809                 vfree(curr_table->table);
810                 vfree(curr_table);
811                 return 1;
812         }
813         if(!last_table) r_tables = curr_table; else last_table->next = curr_table;
814
815         spin_unlock_bh(&recent_lock);
816
817 #ifdef CONFIG_PROC_FS
818         /* Create our proc 'status' entry. */
819         curr_table->status_proc = create_proc_entry(curr_table->name, ip_list_perms, proc_net_ipt_recent);
820         if (!curr_table->status_proc) {
821                 printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for /proc entry.\n");
822                 /* Destroy the created table */
823                 spin_lock_bh(&recent_lock);
824                 last_table = NULL;
825                 curr_table = r_tables;
826                 if(!curr_table) {
827 #ifdef DEBUG
828                         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() create_proc failed, no tables.\n");
829 #endif
830                         spin_unlock_bh(&recent_lock);
831                         return 0;
832                 }
833                 while( strncmp(info->name,curr_table->name,IPT_RECENT_NAME_LEN) && (last_table = curr_table) && (curr_table = curr_table->next) );
834                 if(!curr_table) {
835 #ifdef DEBUG
836                         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() create_proc failed, table already destroyed.\n");
837 #endif
838                         spin_unlock_bh(&recent_lock);
839                         return 0;
840                 }
841                 if(last_table) last_table->next = curr_table->next; else r_tables = curr_table->next;
842                 spin_unlock_bh(&recent_lock);
843                 vfree(curr_table->time_info);
844                 vfree(curr_table->hash_table);
845                 vfree(hold);
846                 vfree(curr_table->table);
847                 vfree(curr_table);
848                 return 0;
849         }
850         
851         curr_table->status_proc->owner = THIS_MODULE;
852         curr_table->status_proc->data = curr_table;
853         wmb();
854         curr_table->status_proc->read_proc = ip_recent_get_info;
855         curr_table->status_proc->write_proc = ip_recent_ctrl;
856 #endif /* CONFIG_PROC_FS */
857
858 #ifdef DEBUG
859         if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() left.\n");
860 #endif
861
862         return 1;
863 }
864
865 /* This function is called in the event that a rule matching this module is
866  * removed.
867  * When this happens we need to check if there are no other rules matching
868  * the table given.  If that is the case then we remove the table and clean
869  * up its memory.
870  */
871 static void
872 destroy(void *matchinfo, unsigned int matchsize)
873 {
874         const struct ipt_recent_info *info = matchinfo;
875         struct recent_ip_tables *curr_table, *last_table;
876
877 #ifdef DEBUG
878         if(debug) printk(KERN_INFO RECENT_NAME ": destroy() entered.\n");
879 #endif
880
881         if(matchsize != IPT_ALIGN(sizeof(struct ipt_recent_info))) return;
882
883         /* Lock the linked list while we play with it */
884         spin_lock_bh(&recent_lock);
885
886         /* Look for an entry with this name already created */
887         /* Finds the end of the list and the entry before the end if current name does not exist */
888         last_table = NULL;
889         curr_table = r_tables;
890         if(!curr_table) { 
891 #ifdef DEBUG
892                 if(debug) printk(KERN_INFO RECENT_NAME ": destroy() No tables found, leaving.\n");
893 #endif
894                 spin_unlock_bh(&recent_lock);
895                 return;
896         }
897         while( strncmp(info->name,curr_table->name,IPT_RECENT_NAME_LEN) && (last_table = curr_table) && (curr_table = curr_table->next) );
898
899         /* If a table does not exist then do nothing and return */
900         if(!curr_table) { 
901 #ifdef DEBUG
902                 if(debug) printk(KERN_INFO RECENT_NAME ": destroy() table not found, leaving.\n");
903 #endif
904                 spin_unlock_bh(&recent_lock);
905                 return;
906         }
907
908         curr_table->count--;
909
910         /* If count is still non-zero then there are still rules referenceing it so we do nothing */
911         if(curr_table->count) { 
912 #ifdef DEBUG
913                 if(debug) printk(KERN_INFO RECENT_NAME ": destroy() table found, non-zero count, leaving.\n");
914 #endif
915                 spin_unlock_bh(&recent_lock);
916                 return;
917         }
918
919 #ifdef DEBUG
920         if(debug) printk(KERN_INFO RECENT_NAME ": destroy() table found, zero count, removing.\n");
921 #endif
922
923         /* Count must be zero so we remove this table from the list */
924         if(last_table) last_table->next = curr_table->next; else r_tables = curr_table->next;
925
926         spin_unlock_bh(&recent_lock);
927
928         /* lock to make sure any late-runners still using this after we removed it from
929          * the list finish up then remove everything */
930         spin_lock_bh(&curr_table->list_lock);
931         spin_unlock_bh(&curr_table->list_lock);
932
933 #ifdef CONFIG_PROC_FS
934         if(curr_table->status_proc) remove_proc_entry(curr_table->name,proc_net_ipt_recent);
935 #endif /* CONFIG_PROC_FS */
936         vfree(curr_table->table[0].last_pkts);
937         vfree(curr_table->table);
938         vfree(curr_table->hash_table);
939         vfree(curr_table->time_info);
940         vfree(curr_table);
941
942 #ifdef DEBUG
943         if(debug) printk(KERN_INFO RECENT_NAME ": destroy() left.\n");
944 #endif
945
946         return;
947 }
948
949 /* This is the structure we pass to ipt_register to register our
950  * module with iptables.
951  */
952 static struct ipt_match recent_match = { 
953   .name = "recent", 
954   .match = &match, 
955   .checkentry = &checkentry, 
956   .destroy = &destroy, 
957   .me = THIS_MODULE
958 };
959
960 /* Kernel module initialization. */
961 static int __init init(void)
962 {
963         int err, count;
964
965         printk(version);
966 #ifdef CONFIG_PROC_FS
967         proc_net_ipt_recent = proc_mkdir("ipt_recent",proc_net);
968         if(!proc_net_ipt_recent) return -ENOMEM;
969 #endif
970
971         if(ip_list_hash_size && ip_list_hash_size <= ip_list_tot) {
972           printk(KERN_WARNING RECENT_NAME ": ip_list_hash_size too small, resetting to default.\n");
973           ip_list_hash_size = 0;
974         }
975
976         if(!ip_list_hash_size) {
977                 ip_list_hash_size = ip_list_tot*3;
978                 count = 2*2;
979                 while(ip_list_hash_size > count) count = count*2;
980                 ip_list_hash_size = count;
981         }
982
983 #ifdef DEBUG
984         if(debug) printk(KERN_INFO RECENT_NAME ": ip_list_hash_size: %d\n",ip_list_hash_size);
985 #endif
986
987         err = ipt_register_match(&recent_match);
988         if (err)
989                 remove_proc_entry("ipt_recent", proc_net);
990         return err;
991 }
992
993 /* Kernel module destruction. */
994 static void __exit fini(void)
995 {
996         ipt_unregister_match(&recent_match);
997
998         remove_proc_entry("ipt_recent",proc_net);
999 }
1000
1001 /* Register our module with the kernel. */
1002 module_init(init);
1003 module_exit(fini);