summaryrefslogtreecommitdiff
path: root/net/ipv4/netfilter/ipt_recent.c
blob: 25ab9fabdcba3d66cb4bbf015514b6d671e6ed8f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
/* Kernel module to check if the source address has been seen recently. */
/* Copyright 2002-2003, Stephen Frost, 2.5.x port by laforge@netfilter.org */
/* Author: Stephen Frost <sfrost@snowman.net> */
/* Project Page: http://snowman.net/projects/ipt_recent/ */
/* This software is distributed under the terms of the GPL, Version 2 */
/* This copyright does not cover user programs that use kernel services
 * by normal system calls. */

#include <linux/module.h>
#include <linux/skbuff.h>
#include <linux/proc_fs.h>
#include <linux/spinlock.h>
#include <linux/interrupt.h>
#include <asm/uaccess.h>
#include <linux/ctype.h>
#include <linux/ip.h>
#include <linux/vmalloc.h>
#include <linux/moduleparam.h>

#include <linux/netfilter_ipv4/ip_tables.h>
#include <linux/netfilter_ipv4/ipt_recent.h>

#undef DEBUG
#define HASH_LOG 9

/* Defaults, these can be overridden on the module command-line. */
static int ip_list_tot = 100;
static int ip_pkt_list_tot = 20;
static int ip_list_hash_size = 0;
static int ip_list_perms = 0644;
#ifdef DEBUG
static int debug = 1;
#endif

static char version[] =
KERN_INFO RECENT_NAME " " RECENT_VER ": Stephen Frost <sfrost@snowman.net>.  http://snowman.net/projects/ipt_recent/\n";

MODULE_AUTHOR("Stephen Frost <sfrost@snowman.net>");
MODULE_DESCRIPTION("IP tables recently seen matching module " RECENT_VER);
MODULE_LICENSE("GPL");
module_param(ip_list_tot, int, 0400);
module_param(ip_pkt_list_tot, int, 0400);
module_param(ip_list_hash_size, int, 0400);
module_param(ip_list_perms, int, 0400);
#ifdef DEBUG
module_param(debug, int, 0600);
MODULE_PARM_DESC(debug,"debugging level, defaults to 1");
#endif
MODULE_PARM_DESC(ip_list_tot,"number of IPs to remember per list");
MODULE_PARM_DESC(ip_pkt_list_tot,"number of packets per IP to remember");
MODULE_PARM_DESC(ip_list_hash_size,"size of hash table used to look up IPs");
MODULE_PARM_DESC(ip_list_perms,"permissions on /proc/net/ipt_recent/* files");

/* Structure of our list of recently seen addresses. */
struct recent_ip_list {
	u_int32_t addr;
	u_int8_t  ttl;
	unsigned long last_seen;
	unsigned long *last_pkts;
	u_int32_t oldest_pkt;
	u_int32_t hash_entry;
	u_int32_t time_pos;
};

struct time_info_list {
	u_int32_t position;
	u_int32_t time;
};

/* Structure of our linked list of tables of recent lists. */
struct recent_ip_tables {
	char name[IPT_RECENT_NAME_LEN];
	int count;
	int time_pos;
	struct recent_ip_list *table;
	struct recent_ip_tables *next;
	spinlock_t list_lock;
	int *hash_table;
	struct time_info_list *time_info;
#ifdef CONFIG_PROC_FS
	struct proc_dir_entry *status_proc;
#endif /* CONFIG_PROC_FS */
};

/* Our current list of addresses we have recently seen.
 * Only added to on a --set, and only updated on --set || --update 
 */
static struct recent_ip_tables *r_tables = NULL;

/* We protect r_list with this spinlock so two processors are not modifying
 * the list at the same time. 
 */
static DEFINE_SPINLOCK(recent_lock);

#ifdef CONFIG_PROC_FS
/* Our /proc/net/ipt_recent entry */
static struct proc_dir_entry *proc_net_ipt_recent = NULL;
#endif

/* Function declaration for later. */
static int
match(const struct sk_buff *skb,
      const struct net_device *in,
      const struct net_device *out,
      const void *matchinfo,
      int offset,
      int *hotdrop);

/* Function to hash a given address into the hash table of table_size size */
static int hash_func(unsigned int addr, int table_size)
{
	int result = 0;
	unsigned int value = addr;
	do { result ^= value; } while((value >>= HASH_LOG));

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": %d = hash_func(%u,%d)\n",
			 result & (table_size - 1),
			 addr,
			 table_size);
#endif

	return(result & (table_size - 1));
}

#ifdef CONFIG_PROC_FS
/* This is the function which produces the output for our /proc output
 * interface which lists each IP address, the last seen time and the 
 * other recent times the address was seen.
 */

static int ip_recent_get_info(char *buffer, char **start, off_t offset, int length, int *eof, void *data)
{
	int len = 0, count, last_len = 0, pkt_count;
	off_t pos = 0;
	off_t begin = 0;
	struct recent_ip_tables *curr_table;

	curr_table = (struct recent_ip_tables*) data;

	spin_lock_bh(&curr_table->list_lock);
	for(count = 0; count < ip_list_tot; count++) {
		if(!curr_table->table[count].addr) continue;
		last_len = len;
		len += sprintf(buffer+len,"src=%u.%u.%u.%u ",NIPQUAD(curr_table->table[count].addr));
		len += sprintf(buffer+len,"ttl: %u ",curr_table->table[count].ttl);
		len += sprintf(buffer+len,"last_seen: %lu ",curr_table->table[count].last_seen);
		len += sprintf(buffer+len,"oldest_pkt: %u ",curr_table->table[count].oldest_pkt);
		len += sprintf(buffer+len,"last_pkts: %lu",curr_table->table[count].last_pkts[0]);
		for(pkt_count = 1; pkt_count < ip_pkt_list_tot; pkt_count++) {
			if(!curr_table->table[count].last_pkts[pkt_count]) break;
			len += sprintf(buffer+len,", %lu",curr_table->table[count].last_pkts[pkt_count]);
		}
		len += sprintf(buffer+len,"\n");
		pos = begin + len;
		if(pos < offset) { len = 0; begin = pos; }
		if(pos > offset + length) { len = last_len; break; }
	}

	*start = buffer + (offset - begin);
	len -= (offset - begin);
	if(len > length) len = length;

	spin_unlock_bh(&curr_table->list_lock);
	return len;
}

/* ip_recent_ctrl provides an interface for users to modify the table
 * directly.  This allows adding entries, removing entries, and
 * flushing the entire table.
 * This is done by opening up the appropriate table for writing and
 * sending one of:
 * xx.xx.xx.xx   -- Add entry to table with current time
 * +xx.xx.xx.xx  -- Add entry to table with current time
 * -xx.xx.xx.xx  -- Remove entry from table
 * clear         -- Flush table, remove all entries
 */

static int ip_recent_ctrl(struct file *file, const char __user *input, unsigned long size, void *data)
{
	static const u_int32_t max[4] = { 0xffffffff, 0xffffff, 0xffff, 0xff };
	u_int32_t val;
	int base, used = 0;
	char c, *cp;
	union iaddr {
		uint8_t bytes[4];
		uint32_t word;
	} res;
	uint8_t *pp = res.bytes;
	int digit;

	char buffer[20];
	int len, check_set = 0, count;
	u_int32_t addr = 0;
	struct sk_buff *skb;
	struct ipt_recent_info *info;
	struct recent_ip_tables *curr_table;

	curr_table = (struct recent_ip_tables*) data;

	if(size > 20) len = 20; else len = size;

	if(copy_from_user(buffer,input,len)) return -EFAULT;

	if(len < 20) buffer[len] = '\0';

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": ip_recent_ctrl len: %d, input: `%.20s'\n",len,buffer);
#endif

	cp = buffer;
	while(isspace(*cp)) { cp++; used++; if(used >= len-5) return used; }

	/* Check if we are asked to flush the entire table */
	if(!memcmp(cp,"clear",5)) {
		used += 5;
		spin_lock_bh(&curr_table->list_lock);
		curr_table->time_pos = 0;
		for(count = 0; count < ip_list_hash_size; count++) {
			curr_table->hash_table[count] = -1;
		}
		for(count = 0; count < ip_list_tot; count++) {
			curr_table->table[count].last_seen = 0;
			curr_table->table[count].addr = 0;
			curr_table->table[count].ttl = 0;
			memset(curr_table->table[count].last_pkts,0,ip_pkt_list_tot*sizeof(u_int32_t));
			curr_table->table[count].oldest_pkt = 0;
			curr_table->table[count].time_pos = 0;
			curr_table->time_info[count].position = count;
			curr_table->time_info[count].time = 0;
		}
		spin_unlock_bh(&curr_table->list_lock);
		return used;
	}

        check_set = IPT_RECENT_SET;
	switch(*cp) {
		case '+': check_set = IPT_RECENT_SET; cp++; used++; break;
		case '-': check_set = IPT_RECENT_REMOVE; cp++; used++; break;
		default: if(!isdigit(*cp)) return (used+1); break;
	}

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": ip_recent_ctrl cp: `%c', check_set: %d\n",*cp,check_set);
#endif
	/* Get addr (effectively inet_aton()) */
	/* Shamelessly stolen from libc, a function in the kernel for doing
	 * this would, of course, be greatly preferred, but our options appear
	 * to be rather limited, so we will just do it ourselves here.
	 */
	res.word = 0;

	c = *cp;
	for(;;) {
		if(!isdigit(c)) return used;
		val = 0; base = 10; digit = 0;
		if(c == '0') {
			c = *++cp;
			if(c == 'x' || c == 'X') base = 16, c = *++cp;
			else { base = 8; digit = 1; }
		}
		for(;;) {
			if(isascii(c) && isdigit(c)) {
				if(base == 8 && (c == '8' || c == '0')) return used;
				val = (val * base) + (c - '0');
				c = *++cp;
				digit = 1;
			} else if(base == 16 && isascii(c) && isxdigit(c)) {
				val = (val << 4) | (c + 10 - (islower(c) ? 'a' : 'A'));
				c = *++cp;
				digit = 1;
			} else break;
		}
		if(c == '.') {
			if(pp > res.bytes + 2 || val > 0xff) return used;
			*pp++ = val;
			c = *++cp;
		} else break;
	}
	used = cp - buffer;
	if(c != '\0' && (!isascii(c) || !isspace(c))) return used;
	if(c == '\n') used++;
	if(!digit) return used;

	if(val > max[pp - res.bytes]) return used;
	addr = res.word | htonl(val);

	if(!addr && check_set == IPT_RECENT_SET) return used;

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": ip_recent_ctrl c: %c, addr: %u used: %d\n",c,addr,used);
#endif

	/* Set up and just call match */
	info = kmalloc(sizeof(struct ipt_recent_info),GFP_KERNEL);
	if(!info) { return -ENOMEM; }
	info->seconds = 0;
	info->hit_count = 0;
	info->check_set = check_set;
	info->invert = 0;
	info->side = IPT_RECENT_SOURCE;
	strncpy(info->name,curr_table->name,IPT_RECENT_NAME_LEN);
	info->name[IPT_RECENT_NAME_LEN-1] = '\0';

	skb = kmalloc(sizeof(struct sk_buff),GFP_KERNEL);
	if (!skb) {
		used = -ENOMEM;
		goto out_free_info;
	}
	skb->nh.iph = kmalloc(sizeof(struct iphdr),GFP_KERNEL);
	if (!skb->nh.iph) {
		used = -ENOMEM;
		goto out_free_skb;
	}

	skb->nh.iph->saddr = addr;
	skb->nh.iph->daddr = 0;
	/* Clear ttl since we have no way of knowing it */
	skb->nh.iph->ttl = 0;
	match(skb,NULL,NULL,info,0,NULL);

	kfree(skb->nh.iph);
out_free_skb:
	kfree(skb);
out_free_info:
	kfree(info);

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": Leaving ip_recent_ctrl addr: %u used: %d\n",addr,used);
#endif
	return used;
}

#endif /* CONFIG_PROC_FS */

/* 'match' is our primary function, called by the kernel whenever a rule is
 * hit with our module as an option to it.
 * What this function does depends on what was specifically asked of it by
 * the user:
 * --set -- Add or update last seen time of the source address of the packet
 *   -- matchinfo->check_set == IPT_RECENT_SET
 * --rcheck -- Just check if the source address is in the list
 *   -- matchinfo->check_set == IPT_RECENT_CHECK
 * --update -- If the source address is in the list, update last_seen
 *   -- matchinfo->check_set == IPT_RECENT_UPDATE
 * --remove -- If the source address is in the list, remove it
 *   -- matchinfo->check_set == IPT_RECENT_REMOVE
 * --seconds -- Option to --rcheck/--update, only match if last_seen within seconds
 *   -- matchinfo->seconds
 * --hitcount -- Option to --rcheck/--update, only match if seen hitcount times
 *   -- matchinfo->hit_count
 * --seconds and --hitcount can be combined
 */
static int
match(const struct sk_buff *skb,
      const struct net_device *in,
      const struct net_device *out,
      const void *matchinfo,
      int offset,
      int *hotdrop)
{
	int pkt_count, hits_found, ans;
	unsigned long now;
	const struct ipt_recent_info *info = matchinfo;
	u_int32_t addr = 0, time_temp;
	u_int8_t ttl = skb->nh.iph->ttl;
	int *hash_table;
	int orig_hash_result, hash_result, temp, location = 0, time_loc, end_collision_chain = -1;
	struct time_info_list *time_info;
	struct recent_ip_tables *curr_table;
	struct recent_ip_tables *last_table;
	struct recent_ip_list *r_list;

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": match() called\n");
#endif

	/* Default is false ^ info->invert */
	ans = info->invert;

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": match(): name = '%s'\n",info->name);
#endif

	/* if out != NULL then routing has been done and TTL changed.
	 * We change it back here internally for match what came in before routing. */
	if(out) ttl++;

	/* Find the right table */
	spin_lock_bh(&recent_lock);
	curr_table = r_tables;
	while( (last_table = curr_table) && strncmp(info->name,curr_table->name,IPT_RECENT_NAME_LEN) && (curr_table = curr_table->next) );

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": match(): table found('%s')\n",info->name);
#endif

	spin_unlock_bh(&recent_lock);

	/* Table with this name not found, match impossible */
	if(!curr_table) { return ans; }

	/* Make sure no one is changing the list while we work with it */
	spin_lock_bh(&curr_table->list_lock);

	r_list = curr_table->table;
	if(info->side == IPT_RECENT_DEST) addr = skb->nh.iph->daddr; else addr = skb->nh.iph->saddr;

	if(!addr) { 
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": match() address (%u) invalid, leaving.\n",addr);
#endif
		spin_unlock_bh(&curr_table->list_lock);
		return ans;
	}

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": match(): checking table, addr: %u, ttl: %u, orig_ttl: %u\n",addr,ttl,skb->nh.iph->ttl);
#endif

	/* Get jiffies now in case they changed while we were waiting for a lock */
	now = jiffies;
	hash_table = curr_table->hash_table;
	time_info = curr_table->time_info;

	orig_hash_result = hash_result = hash_func(addr,ip_list_hash_size);
	/* Hash entry at this result used */
	/* Check for TTL match if requested.  If TTL is zero then a match would never
	 * happen, so match regardless of existing TTL in that case.  Zero means the
	 * entry was added via the /proc interface anyway, so we will just use the
	 * first TTL we get for that IP address. */
	if(info->check_set & IPT_RECENT_TTL) {
		while(hash_table[hash_result] != -1 && !(r_list[hash_table[hash_result]].addr == addr &&
			(!r_list[hash_table[hash_result]].ttl || r_list[hash_table[hash_result]].ttl == ttl))) {
			/* Collision in hash table */
			hash_result = (hash_result + 1) % ip_list_hash_size;
		}
	} else {
		while(hash_table[hash_result] != -1 && r_list[hash_table[hash_result]].addr != addr) {
			/* Collision in hash table */
			hash_result = (hash_result + 1) % ip_list_hash_size;
		}
	}

	if(hash_table[hash_result] == -1 && !(info->check_set & IPT_RECENT_SET)) {
		/* IP not in list and not asked to SET */
		spin_unlock_bh(&curr_table->list_lock);
		return ans;
	}

	/* Check if we need to handle the collision, do not need to on REMOVE */
	if(orig_hash_result != hash_result && !(info->check_set & IPT_RECENT_REMOVE)) {
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": match(): Collision in hash table. (or: %d,hr: %d,oa: %u,ha: %u)\n",
				 orig_hash_result,
				 hash_result,
				 r_list[hash_table[orig_hash_result]].addr,
				 addr);
#endif

		/* We had a collision.
		 * orig_hash_result is where we started, hash_result is where we ended up.
		 * So, swap them because we are likely to see the same guy again sooner */
#ifdef DEBUG
		if(debug) {
		  printk(KERN_INFO RECENT_NAME ": match(): Collision; hash_table[orig_hash_result] = %d\n",hash_table[orig_hash_result]);
		  printk(KERN_INFO RECENT_NAME ": match(): Collision; r_list[hash_table[orig_hash_result]].hash_entry = %d\n",
				r_list[hash_table[orig_hash_result]].hash_entry);
		}
#endif

		r_list[hash_table[orig_hash_result]].hash_entry = hash_result;


		temp = hash_table[orig_hash_result];
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": match(): Collision; hash_table[hash_result] = %d\n",hash_table[hash_result]);
#endif
		hash_table[orig_hash_result] = hash_table[hash_result];
		hash_table[hash_result] = temp;
		temp = hash_result;
		hash_result = orig_hash_result;
		orig_hash_result = temp;
		time_info[r_list[hash_table[orig_hash_result]].time_pos].position = hash_table[orig_hash_result];
		if(hash_table[hash_result] != -1) {
			r_list[hash_table[hash_result]].hash_entry = hash_result;
			time_info[r_list[hash_table[hash_result]].time_pos].position = hash_table[hash_result];
		}

#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": match(): Collision handled.\n");
#endif
	}

	if(hash_table[hash_result] == -1) {
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": match(): New table entry. (hr: %d,ha: %u)\n",
				 hash_result, addr);
#endif

		/* New item found and IPT_RECENT_SET, so we need to add it */
		location = time_info[curr_table->time_pos].position;
		hash_table[r_list[location].hash_entry] = -1;
		hash_table[hash_result] = location;
		memset(r_list[location].last_pkts,0,ip_pkt_list_tot*sizeof(u_int32_t));
		r_list[location].time_pos = curr_table->time_pos;
		r_list[location].addr = addr;
		r_list[location].ttl = ttl;
		r_list[location].last_seen = now;
		r_list[location].oldest_pkt = 1;
		r_list[location].last_pkts[0] = now;
		r_list[location].hash_entry = hash_result;
		time_info[curr_table->time_pos].time = r_list[location].last_seen;
		curr_table->time_pos = (curr_table->time_pos + 1) % ip_list_tot;

		ans = !info->invert;
	} else {
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": match(): Existing table entry. (hr: %d,ha: %u)\n",
				 hash_result,
				 addr);
#endif

		/* Existing item found */
		location = hash_table[hash_result];
		/* We have a match on address, now to make sure it meets all requirements for a
		 * full match. */
		if(info->check_set & IPT_RECENT_CHECK || info->check_set & IPT_RECENT_UPDATE) {
			if(!info->seconds && !info->hit_count) ans = !info->invert; else ans = info->invert;
			if(info->seconds && !info->hit_count) {
				if(time_before_eq(now,r_list[location].last_seen+info->seconds*HZ)) ans = !info->invert; else ans = info->invert;
			}
			if(info->seconds && info->hit_count) {
				for(pkt_count = 0, hits_found = 0; pkt_count < ip_pkt_list_tot; pkt_count++) {
					if(time_before_eq(now,r_list[location].last_pkts[pkt_count]+info->seconds*HZ)) hits_found++;
				}
				if(hits_found >= info->hit_count) ans = !info->invert; else ans = info->invert;
			}
			if(info->hit_count && !info->seconds) {
				for(pkt_count = 0, hits_found = 0; pkt_count < ip_pkt_list_tot; pkt_count++) {
					if(r_list[location].last_pkts[pkt_count] == 0) break;
					hits_found++;
				}
				if(hits_found >= info->hit_count) ans = !info->invert; else ans = info->invert;
			}
		}
#ifdef DEBUG
		if(debug) {
			if(ans)
				printk(KERN_INFO RECENT_NAME ": match(): match addr: %u\n",addr);
			else
				printk(KERN_INFO RECENT_NAME ": match(): no match addr: %u\n",addr);
		}
#endif

		/* If and only if we have been asked to SET, or to UPDATE (on match) do we add the
		 * current timestamp to the last_seen. */
		if((info->check_set & IPT_RECENT_SET && (ans = !info->invert)) || (info->check_set & IPT_RECENT_UPDATE && ans)) {
#ifdef DEBUG
			if(debug) printk(KERN_INFO RECENT_NAME ": match(): SET or UPDATE; updating time info.\n");
#endif
			/* Have to update our time info */
			time_loc = r_list[location].time_pos;
			time_info[time_loc].time = now;
			time_info[time_loc].position = location;
			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) {
				time_temp = time_info[time_loc].time;
				time_info[time_loc].time = time_info[(time_loc+1)%ip_list_tot].time;
				time_info[(time_loc+1)%ip_list_tot].time = time_temp;
				time_temp = time_info[time_loc].position;
				time_info[time_loc].position = time_info[(time_loc+1)%ip_list_tot].position;
				time_info[(time_loc+1)%ip_list_tot].position = time_temp;
				r_list[time_info[time_loc].position].time_pos = time_loc;
				r_list[time_info[(time_loc+1)%ip_list_tot].position].time_pos = (time_loc+1)%ip_list_tot;
				time_loc = (time_loc+1) % ip_list_tot;
			}
			r_list[location].time_pos = time_loc;
			r_list[location].ttl = ttl;
			r_list[location].last_pkts[r_list[location].oldest_pkt] = now;
			r_list[location].oldest_pkt = ++r_list[location].oldest_pkt % ip_pkt_list_tot;
			r_list[location].last_seen = now;
		}
		/* If we have been asked to remove the entry from the list, just set it to 0 */
		if(info->check_set & IPT_RECENT_REMOVE) {
#ifdef DEBUG
			if(debug) printk(KERN_INFO RECENT_NAME ": match(): REMOVE; clearing entry (or: %d, hr: %d).\n",orig_hash_result,hash_result);
#endif
			/* Check if this is part of a collision chain */
			while(hash_table[(orig_hash_result+1) % ip_list_hash_size] != -1) {
				orig_hash_result++;
				if(hash_func(r_list[hash_table[orig_hash_result]].addr,ip_list_hash_size) == hash_result) {
					/* Found collision chain, how deep does this rabbit hole go? */
#ifdef DEBUG
					if(debug) printk(KERN_INFO RECENT_NAME ": match(): REMOVE; found collision chain.\n");
#endif
					end_collision_chain = orig_hash_result;
				}
			}
			if(end_collision_chain != -1) {
#ifdef DEBUG
				if(debug) printk(KERN_INFO RECENT_NAME ": match(): REMOVE; part of collision chain, moving to end.\n");
#endif
				/* Part of a collision chain, swap it with the end of the chain
				 * before removing. */
				r_list[hash_table[end_collision_chain]].hash_entry = hash_result;
				temp = hash_table[end_collision_chain];
				hash_table[end_collision_chain] = hash_table[hash_result];
				hash_table[hash_result] = temp;
				time_info[r_list[hash_table[hash_result]].time_pos].position = hash_table[hash_result];
				hash_result = end_collision_chain;
				r_list[hash_table[hash_result]].hash_entry = hash_result;
				time_info[r_list[hash_table[hash_result]].time_pos].position = hash_table[hash_result];
			}
			location = hash_table[hash_result];
			hash_table[r_list[location].hash_entry] = -1;
			time_loc = r_list[location].time_pos;
			time_info[time_loc].time = 0;
			time_info[time_loc].position = location;
			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) {
				time_temp = time_info[time_loc].time;
				time_info[time_loc].time = time_info[(time_loc+1)%ip_list_tot].time;
				time_info[(time_loc+1)%ip_list_tot].time = time_temp;
				time_temp = time_info[time_loc].position;
				time_info[time_loc].position = time_info[(time_loc+1)%ip_list_tot].position;
				time_info[(time_loc+1)%ip_list_tot].position = time_temp;
				r_list[time_info[time_loc].position].time_pos = time_loc;
				r_list[time_info[(time_loc+1)%ip_list_tot].position].time_pos = (time_loc+1)%ip_list_tot;
				time_loc = (time_loc+1) % ip_list_tot;
			}
			r_list[location].time_pos = time_loc;
			r_list[location].last_seen = 0;
			r_list[location].addr = 0;
			r_list[location].ttl = 0;
			memset(r_list[location].last_pkts,0,ip_pkt_list_tot*sizeof(u_int32_t));
			r_list[location].oldest_pkt = 0;
			ans = !info->invert;
		}
		spin_unlock_bh(&curr_table->list_lock);
		return ans;
	}

	spin_unlock_bh(&curr_table->list_lock);
#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": match() left.\n");
#endif
	return ans;
}

/* This function is to verify that the rule given during the userspace iptables
 * command is correct.
 * If the command is valid then we check if the table name referred to by the
 * rule exists, if not it is created.
 */
static int
checkentry(const char *tablename,
           const struct ipt_ip *ip,
           void *matchinfo,
           unsigned int matchsize,
           unsigned int hook_mask)
{
	int flag = 0, c;
	unsigned long *hold;
	const struct ipt_recent_info *info = matchinfo;
	struct recent_ip_tables *curr_table, *find_table, *last_table;

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() entered.\n");
#endif

	if (matchsize != IPT_ALIGN(sizeof(struct ipt_recent_info))) return 0;

	/* seconds and hit_count only valid for CHECK/UPDATE */
	if(info->check_set & IPT_RECENT_SET) { flag++; if(info->seconds || info->hit_count) return 0; }
	if(info->check_set & IPT_RECENT_REMOVE) { flag++; if(info->seconds || info->hit_count) return 0; }
	if(info->check_set & IPT_RECENT_CHECK) flag++;
	if(info->check_set & IPT_RECENT_UPDATE) flag++;

	/* One and only one of these should ever be set */
	if(flag != 1) return 0;

	/* Name must be set to something */
	if(!info->name || !info->name[0]) return 0;

	/* Things look good, create a list for this if it does not exist */
	/* Lock the linked list while we play with it */
	spin_lock_bh(&recent_lock);

	/* Look for an entry with this name already created */
	/* Finds the end of the list and the entry before the end if current name does not exist */
	find_table = r_tables;
	while( (last_table = find_table) && strncmp(info->name,find_table->name,IPT_RECENT_NAME_LEN) && (find_table = find_table->next) );

	/* If a table already exists just increment the count on that table and return */
	if(find_table) { 
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: table found (%s), incrementing count.\n",info->name);
#endif
		find_table->count++;
		spin_unlock_bh(&recent_lock);
		return 1;
	}

	spin_unlock_bh(&recent_lock);

	/* Table with this name not found */
	/* Allocate memory for new linked list item */

#ifdef DEBUG
	if(debug) {
		printk(KERN_INFO RECENT_NAME ": checkentry: no table found (%s)\n",info->name);
		printk(KERN_INFO RECENT_NAME ": checkentry: Allocationg %d for link-list entry.\n",sizeof(struct recent_ip_tables));
	}
#endif

	curr_table = vmalloc(sizeof(struct recent_ip_tables));
	if(curr_table == NULL) return 0;

	spin_lock_init(&curr_table->list_lock);
	curr_table->next = NULL;
	curr_table->count = 1;
	curr_table->time_pos = 0;
	strncpy(curr_table->name,info->name,IPT_RECENT_NAME_LEN);
	curr_table->name[IPT_RECENT_NAME_LEN-1] = '\0';

	/* Allocate memory for this table and the list of packets in each entry. */
#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for table (%s).\n",
			sizeof(struct recent_ip_list)*ip_list_tot,
			info->name);
#endif

	curr_table->table = vmalloc(sizeof(struct recent_ip_list)*ip_list_tot);
	if(curr_table->table == NULL) { vfree(curr_table); return 0; }
	memset(curr_table->table,0,sizeof(struct recent_ip_list)*ip_list_tot);
#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for pkt_list.\n",
			sizeof(u_int32_t)*ip_pkt_list_tot*ip_list_tot);
#endif

	hold = vmalloc(sizeof(u_int32_t)*ip_pkt_list_tot*ip_list_tot);
#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: After pkt_list allocation.\n");
#endif
	if(hold == NULL) { 
		printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for pkt_list.\n");
		vfree(curr_table->table); 
		vfree(curr_table);
		return 0;
	}
	for(c = 0; c < ip_list_tot; c++) {
		curr_table->table[c].last_pkts = hold + c*ip_pkt_list_tot;
	}

	/* Allocate memory for the hash table */
#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for hash_table.\n",
			sizeof(int)*ip_list_hash_size);
#endif

	curr_table->hash_table = vmalloc(sizeof(int)*ip_list_hash_size);
	if(!curr_table->hash_table) {
		printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for hash_table.\n");
		vfree(hold);
		vfree(curr_table->table); 
		vfree(curr_table);
		return 0;
	}

	for(c = 0; c < ip_list_hash_size; c++) {
		curr_table->hash_table[c] = -1;
	}

	/* Allocate memory for the time info */
#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: Allocating %d for time_info.\n",
			sizeof(struct time_info_list)*ip_list_tot);
#endif

	curr_table->time_info = vmalloc(sizeof(struct time_info_list)*ip_list_tot);
	if(!curr_table->time_info) {
		printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for time_info.\n");
		vfree(curr_table->hash_table);
		vfree(hold);
		vfree(curr_table->table); 
		vfree(curr_table);
		return 0;
	}
	for(c = 0; c < ip_list_tot; c++) {
		curr_table->time_info[c].position = c;
		curr_table->time_info[c].time = 0;
	}

	/* Put the new table in place */
	spin_lock_bh(&recent_lock);
	find_table = r_tables;
	while( (last_table = find_table) && strncmp(info->name,find_table->name,IPT_RECENT_NAME_LEN) && (find_table = find_table->next) );

	/* If a table already exists just increment the count on that table and return */
	if(find_table) { 
		find_table->count++;	
		spin_unlock_bh(&recent_lock);
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": checkentry: table found (%s), created by other process.\n",info->name);
#endif
		vfree(curr_table->time_info);
		vfree(curr_table->hash_table);
		vfree(hold);
		vfree(curr_table->table);
		vfree(curr_table);
		return 1;
	}
	if(!last_table) r_tables = curr_table; else last_table->next = curr_table;

	spin_unlock_bh(&recent_lock);

#ifdef CONFIG_PROC_FS
	/* Create our proc 'status' entry. */
	curr_table->status_proc = create_proc_entry(curr_table->name, ip_list_perms, proc_net_ipt_recent);
	if (!curr_table->status_proc) {
		printk(KERN_INFO RECENT_NAME ": checkentry: unable to allocate for /proc entry.\n");
		/* Destroy the created table */
		spin_lock_bh(&recent_lock);
		last_table = NULL;
		curr_table = r_tables;
		if(!curr_table) {
#ifdef DEBUG
			if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() create_proc failed, no tables.\n");
#endif
			spin_unlock_bh(&recent_lock);
			return 0;
		}
		while( strncmp(info->name,curr_table->name,IPT_RECENT_NAME_LEN) && (last_table = curr_table) && (curr_table = curr_table->next) );
		if(!curr_table) {
#ifdef DEBUG
			if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() create_proc failed, table already destroyed.\n");
#endif
			spin_unlock_bh(&recent_lock);
			return 0;
		}
		if(last_table) last_table->next = curr_table->next; else r_tables = curr_table->next;
		spin_unlock_bh(&recent_lock);
		vfree(curr_table->time_info);
		vfree(curr_table->hash_table);
		vfree(hold);
		vfree(curr_table->table);
		vfree(curr_table);
		return 0;
	}
	
	curr_table->status_proc->owner = THIS_MODULE;
	curr_table->status_proc->data = curr_table;
	wmb();
	curr_table->status_proc->read_proc = ip_recent_get_info;
	curr_table->status_proc->write_proc = ip_recent_ctrl;
#endif /* CONFIG_PROC_FS */

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": checkentry() left.\n");
#endif

	return 1;
}

/* This function is called in the event that a rule matching this module is
 * removed.
 * When this happens we need to check if there are no other rules matching
 * the table given.  If that is the case then we remove the table and clean
 * up its memory.
 */
static void
destroy(void *matchinfo, unsigned int matchsize)
{
	const struct ipt_recent_info *info = matchinfo;
	struct recent_ip_tables *curr_table, *last_table;

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": destroy() entered.\n");
#endif

	if(matchsize != IPT_ALIGN(sizeof(struct ipt_recent_info))) return;

	/* Lock the linked list while we play with it */
	spin_lock_bh(&recent_lock);

	/* Look for an entry with this name already created */
	/* Finds the end of the list and the entry before the end if current name does not exist */
	last_table = NULL;
	curr_table = r_tables;
	if(!curr_table) { 
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": destroy() No tables found, leaving.\n");
#endif
		spin_unlock_bh(&recent_lock);
		return;
	}
	while( strncmp(info->name,curr_table->name,IPT_RECENT_NAME_LEN) && (last_table = curr_table) && (curr_table = curr_table->next) );

	/* If a table does not exist then do nothing and return */
	if(!curr_table) { 
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": destroy() table not found, leaving.\n");
#endif
		spin_unlock_bh(&recent_lock);
		return;
	}

	curr_table->count--;

	/* If count is still non-zero then there are still rules referenceing it so we do nothing */
	if(curr_table->count) { 
#ifdef DEBUG
		if(debug) printk(KERN_INFO RECENT_NAME ": destroy() table found, non-zero count, leaving.\n");
#endif
		spin_unlock_bh(&recent_lock);
		return;
	}

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": destroy() table found, zero count, removing.\n");
#endif

	/* Count must be zero so we remove this table from the list */
	if(last_table) last_table->next = curr_table->next; else r_tables = curr_table->next;

	spin_unlock_bh(&recent_lock);

	/* lock to make sure any late-runners still using this after we removed it from
	 * the list finish up then remove everything */
	spin_lock_bh(&curr_table->list_lock);
	spin_unlock_bh(&curr_table->list_lock);

#ifdef CONFIG_PROC_FS
	if(curr_table->status_proc) remove_proc_entry(curr_table->name,proc_net_ipt_recent);
#endif /* CONFIG_PROC_FS */
	vfree(curr_table->table[0].last_pkts);
	vfree(curr_table->table);
	vfree(curr_table->hash_table);
	vfree(curr_table->time_info);
	vfree(curr_table);

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": destroy() left.\n");
#endif

	return;
}

/* This is the structure we pass to ipt_register to register our
 * module with iptables.
 */
static struct ipt_match recent_match = { 
  .name = "recent", 
  .match = &match, 
  .checkentry = &checkentry, 
  .destroy = &destroy, 
  .me = THIS_MODULE
};

/* Kernel module initialization. */
static int __init init(void)
{
	int err, count;

	printk(version);
#ifdef CONFIG_PROC_FS
	proc_net_ipt_recent = proc_mkdir("ipt_recent",proc_net);
	if(!proc_net_ipt_recent) return -ENOMEM;
#endif

	if(ip_list_hash_size && ip_list_hash_size <= ip_list_tot) {
	  printk(KERN_WARNING RECENT_NAME ": ip_list_hash_size too small, resetting to default.\n");
	  ip_list_hash_size = 0;
	}

	if(!ip_list_hash_size) {
		ip_list_hash_size = ip_list_tot*3;
		count = 2*2;
		while(ip_list_hash_size > count) count = count*2;
		ip_list_hash_size = count;
	}

#ifdef DEBUG
	if(debug) printk(KERN_INFO RECENT_NAME ": ip_list_hash_size: %d\n",ip_list_hash_size);
#endif

	err = ipt_register_match(&recent_match);
	if (err)
		remove_proc_entry("ipt_recent", proc_net);
	return err;
}

/* Kernel module destruction. */
static void __exit fini(void)
{
	ipt_unregister_match(&recent_match);

	remove_proc_entry("ipt_recent",proc_net);
}

/* Register our module with the kernel. */
module_init(init);
module_exit(fini);