ip_htable.c revision 172776 
1234287Sdim/*	$FreeBSD: head/sys/contrib/ipfilter/netinet/ip_htable.c 172776 2007-10-18 21:52:14Z darrenr $	*/
2234287Sdim
3234287Sdim/*
4234287Sdim * Copyright (C) 1993-2001, 2003 by Darren Reed.
5234287Sdim *
6234287Sdim * See the IPFILTER.LICENCE file for details on licencing.
7234287Sdim */
8234287Sdim#if defined(KERNEL) || defined(_KERNEL)
9234287Sdim# undef KERNEL
10234287Sdim# undef _KERNEL
11234287Sdim# define        KERNEL	1
12234287Sdim# define        _KERNEL	1
13234287Sdim#endif
14234287Sdim#include <sys/param.h>
15#include <sys/types.h>
16#include <sys/errno.h>
17#include <sys/time.h>
18#include <sys/file.h>
19#if !defined(_KERNEL)
20# include <stdlib.h>
21# include <string.h>
22# define _KERNEL
23# ifdef __OpenBSD__
24struct file;
25# endif
26# include <sys/uio.h>
27# undef _KERNEL
28#endif
29#include <sys/socket.h>
30#if defined(__FreeBSD_version) && (__FreeBSD_version >= 300000)
31# include <sys/malloc.h>
32#endif
33#if defined(__FreeBSD__)
34#  include <sys/cdefs.h>
35#  include <sys/proc.h>
36#endif
37#if !defined(__svr4__) && !defined(__SVR4) && !defined(__hpux) && \
38    !defined(linux)
39# include <sys/mbuf.h>
40#endif
41#if defined(_KERNEL)
42# include <sys/systm.h>
43#else
44# include <stdio.h>
45#endif
46#include <netinet/in.h>
47#include <net/if.h>
48
49#include "netinet/ip_compat.h"
50#include "netinet/ip_fil.h"
51#include "netinet/ip_lookup.h"
52#include "netinet/ip_htable.h"
53/* END OF INCLUDES */
54
55#if !defined(lint)
56static const char rcsid[] = "@(#)$Id: ip_htable.c,v 2.34.2.11 2007/09/20 12:51:51 darrenr Exp $";
57#endif
58
59#ifdef	IPFILTER_LOOKUP
60static iphtent_t *fr_iphmfind __P((iphtable_t *, struct in_addr *));
61static	u_long	ipht_nomem[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 };
62static	u_long	ipf_nhtables[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 };
63static	u_long	ipf_nhtnodes[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 };
64
65iphtable_t *ipf_htables[IPL_LOGSIZE] = { NULL, NULL, NULL, NULL,
66					 NULL, NULL, NULL, NULL };
67
68
69void fr_htable_unload()
70{
71	iplookupflush_t fop;
72
73	fop.iplf_unit = IPL_LOGALL;
74	(void)fr_flushhtable(&fop);
75}
76
77
78int fr_gethtablestat(op)
79iplookupop_t *op;
80{
81	iphtstat_t stats;
82
83	if (op->iplo_size != sizeof(stats))
84		return EINVAL;
85
86	stats.iphs_tables = ipf_htables[op->iplo_unit];
87	stats.iphs_numtables = ipf_nhtables[op->iplo_unit];
88	stats.iphs_numnodes = ipf_nhtnodes[op->iplo_unit];
89	stats.iphs_nomem = ipht_nomem[op->iplo_unit];
90
91	return COPYOUT(&stats, op->iplo_struct, sizeof(stats));
92
93}
94
95
96/*
97 * Create a new hash table using the template passed.
98 */
99int fr_newhtable(op)
100iplookupop_t *op;
101{
102	iphtable_t *iph, *oiph;
103	char name[FR_GROUPLEN];
104	int err, i, unit;
105
106	unit = op->iplo_unit;
107	if ((op->iplo_arg & IPHASH_ANON) == 0) {
108		iph = fr_existshtable(unit, op->iplo_name);
109		if (iph != NULL) {
110			if ((iph->iph_flags & IPHASH_DELETE) == 0)
111				return EEXIST;
112			iph->iph_flags &= ~IPHASH_DELETE;
113			return 0;
114		}
115	}
116
117	KMALLOC(iph, iphtable_t *);
118	if (iph == NULL) {
119		ipht_nomem[op->iplo_unit]++;
120		return ENOMEM;
121	}
122	err = COPYIN(op->iplo_struct, iph, sizeof(*iph));
123	if (err != 0) {
124		KFREE(iph);
125		return EFAULT;
126	}
127
128	if (iph->iph_unit != unit) {
129		KFREE(iph);
130		return EINVAL;
131	}
132
133	if ((op->iplo_arg & IPHASH_ANON) != 0) {
134		i = IPHASH_ANON;
135		do {
136			i++;
137#if defined(SNPRINTF) && defined(_KERNEL)
138			SNPRINTF(name, sizeof(name), "%u", i);
139#else
140			(void)sprintf(name, "%u", i);
141#endif
142			for (oiph = ipf_htables[unit]; oiph != NULL;
143			     oiph = oiph->iph_next)
144				if (strncmp(oiph->iph_name, name,
145					    sizeof(oiph->iph_name)) == 0)
146					break;
147		} while (oiph != NULL);
148
149		(void)strncpy(iph->iph_name, name, sizeof(iph->iph_name));
150		(void)strncpy(op->iplo_name, name, sizeof(op->iplo_name));
151		iph->iph_type |= IPHASH_ANON;
152	}
153
154	KMALLOCS(iph->iph_table, iphtent_t **,
155		 iph->iph_size * sizeof(*iph->iph_table));
156	if (iph->iph_table == NULL) {
157		KFREE(iph);
158		ipht_nomem[unit]++;
159		return ENOMEM;
160	}
161
162	bzero((char *)iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
163	iph->iph_masks = 0;
164	iph->iph_list = NULL;
165
166	iph->iph_ref = 1;
167	iph->iph_next = ipf_htables[unit];
168	iph->iph_pnext = &ipf_htables[unit];
169	if (ipf_htables[unit] != NULL)
170		ipf_htables[unit]->iph_pnext = &iph->iph_next;
171	ipf_htables[unit] = iph;
172	ipf_nhtables[unit]++;
173
174	return 0;
175}
176
177
178/*
179 */
180int fr_removehtable(unit, name)
181int unit;
182char *name;
183{
184	iphtable_t *iph;
185
186	iph = fr_findhtable(unit, name);
187	if (iph == NULL)
188		return ESRCH;
189
190	if (iph->iph_unit != unit) {
191		return EINVAL;
192	}
193
194	if (iph->iph_ref != 0) {
195		(void) fr_clearhtable(iph);
196		iph->iph_flags |= IPHASH_DELETE;
197		return 0;
198	}
199
200	fr_delhtable(iph);
201
202	return 0;
203}
204
205
206int fr_clearhtable(iph)
207iphtable_t *iph;
208{
209	iphtent_t *ipe;
210
211	while ((ipe = iph->iph_list) != NULL)
212		if (fr_delhtent(iph, ipe) != 0)
213			return 1;
214	return 0;
215}
216
217
218int fr_delhtable(iph)
219iphtable_t *iph;
220{
221
222	if (fr_clearhtable(iph) != 0)
223		return 1;
224
225	if (iph->iph_pnext != NULL)
226		*iph->iph_pnext = iph->iph_next;
227	if (iph->iph_next != NULL)
228		iph->iph_next->iph_pnext = iph->iph_pnext;
229
230	ipf_nhtables[iph->iph_unit]--;
231
232	return fr_derefhtable(iph);
233}
234
235
236/*
237 * Delete an entry from a hash table.
238 */
239int fr_delhtent(iph, ipe)
240iphtable_t *iph;
241iphtent_t *ipe;
242{
243
244	if (ipe->ipe_phnext != NULL)
245		*ipe->ipe_phnext = ipe->ipe_hnext;
246	if (ipe->ipe_hnext != NULL)
247		ipe->ipe_hnext->ipe_phnext = ipe->ipe_phnext;
248
249	if (ipe->ipe_pnext != NULL)
250		*ipe->ipe_pnext = ipe->ipe_next;
251	if (ipe->ipe_next != NULL)
252		ipe->ipe_next->ipe_pnext = ipe->ipe_pnext;
253
254	switch (iph->iph_type & ~IPHASH_ANON)
255	{
256	case IPHASH_GROUPMAP :
257		if (ipe->ipe_group != NULL)
258			fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active);
259		break;
260
261	default :
262		ipe->ipe_ptr = NULL;
263		ipe->ipe_value = 0;
264		break;
265	}
266
267	return fr_derefhtent(ipe);
268}
269
270
271int fr_derefhtable(iph)
272iphtable_t *iph;
273{
274	int refs;
275
276	iph->iph_ref--;
277	refs = iph->iph_ref;
278
279	if (iph->iph_ref == 0) {
280		KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
281		KFREE(iph);
282	}
283
284	return refs;
285}
286
287
288int fr_derefhtent(ipe)
289iphtent_t *ipe;
290{
291
292	ipe->ipe_ref--;
293	if (ipe->ipe_ref == 0) {
294		ipf_nhtnodes[ipe->ipe_unit]--;
295
296		KFREE(ipe);
297
298		return 0;
299	}
300
301	return ipe->ipe_ref;
302}
303
304
305iphtable_t *fr_existshtable(unit, name)
306int unit;
307char *name;
308{
309	iphtable_t *iph;
310
311	for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next)
312		if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0)
313			break;
314	return iph;
315}
316
317
318iphtable_t *fr_findhtable(unit, name)
319int unit;
320char *name;
321{
322	iphtable_t *iph;
323
324	iph = fr_existshtable(unit, name);
325	if ((iph != NULL) && (iph->iph_flags & IPHASH_DELETE) == 0)
326		return iph;
327
328	return NULL;
329}
330
331
332size_t fr_flushhtable(op)
333iplookupflush_t *op;
334{
335	iphtable_t *iph;
336	size_t freed;
337	int i;
338
339	freed = 0;
340
341	for (i = 0; i <= IPL_LOGMAX; i++) {
342		if (op->iplf_unit == i || op->iplf_unit == IPL_LOGALL) {
343			while ((iph = ipf_htables[i]) != NULL) {
344				if (fr_delhtable(iph) == 0) {
345					freed++;
346				} else {
347					iph->iph_flags |= IPHASH_DELETE;
348				}
349			}
350		}
351	}
352
353	return freed;
354}
355
356
357/*
358 * Add an entry to a hash table.
359 */
360int fr_addhtent(iph, ipeo)
361iphtable_t *iph;
362iphtent_t *ipeo;
363{
364	iphtent_t *ipe;
365	u_int hv;
366	int bits;
367
368	KMALLOC(ipe, iphtent_t *);
369	if (ipe == NULL)
370		return -1;
371
372	bcopy((char *)ipeo, (char *)ipe, sizeof(*ipe));
373	ipe->ipe_addr.in4_addr &= ipe->ipe_mask.in4_addr;
374	ipe->ipe_addr.in4_addr = ntohl(ipe->ipe_addr.in4_addr);
375	bits = count4bits(ipe->ipe_mask.in4_addr);
376	ipe->ipe_mask.in4_addr = ntohl(ipe->ipe_mask.in4_addr);
377
378	hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr,
379			 iph->iph_size);
380	ipe->ipe_ref = 1;
381	ipe->ipe_hnext = iph->iph_table[hv];
382	ipe->ipe_phnext = iph->iph_table + hv;
383
384	if (iph->iph_table[hv] != NULL)
385		iph->iph_table[hv]->ipe_phnext = &ipe->ipe_hnext;
386	iph->iph_table[hv] = ipe;
387
388	ipe->ipe_next = iph->iph_list;
389	ipe->ipe_pnext = &iph->iph_list;
390	if (ipe->ipe_next != NULL)
391		ipe->ipe_next->ipe_pnext = &ipe->ipe_next;
392	iph->iph_list = ipe;
393
394	if ((bits >= 0) && (bits != 32))
395		iph->iph_masks |= 1 << bits;
396
397	switch (iph->iph_type & ~IPHASH_ANON)
398	{
399	case IPHASH_GROUPMAP :
400		ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL,
401					   iph->iph_flags, IPL_LOGIPF,
402					   fr_active);
403		break;
404
405	default :
406		ipe->ipe_ptr = NULL;
407		ipe->ipe_value = 0;
408		break;
409	}
410
411	ipe->ipe_unit = iph->iph_unit;
412	ipf_nhtnodes[ipe->ipe_unit]++;
413
414	return 0;
415}
416
417
418void *fr_iphmfindgroup(tptr, aptr)
419void *tptr, *aptr;
420{
421	struct in_addr *addr;
422	iphtable_t *iph;
423	iphtent_t *ipe;
424	void *rval;
425
426	READ_ENTER(&ip_poolrw);
427	iph = tptr;
428	addr = aptr;
429
430	ipe = fr_iphmfind(iph, addr);
431	if (ipe != NULL)
432		rval = ipe->ipe_ptr;
433	else
434		rval = NULL;
435	RWLOCK_EXIT(&ip_poolrw);
436	return rval;
437}
438
439
440/* ------------------------------------------------------------------------ */
441/* Function:    fr_iphmfindip                                               */
442/* Returns:     int     - 0 == +ve match, -1 == error, 1 == -ve/no match    */
443/* Parameters:  tptr(I)      - pointer to the pool to search                */
444/*              ipversion(I) - IP protocol version (4 or 6)                 */
445/*              aptr(I)      - pointer to address information               */
446/*                                                                          */
447/* Search the hash table for a given address and return a search result.    */
448/* ------------------------------------------------------------------------ */
449int fr_iphmfindip(tptr, ipversion, aptr)
450void *tptr, *aptr;
451int ipversion;
452{
453	struct in_addr *addr;
454	iphtable_t *iph;
455	iphtent_t *ipe;
456	int rval;
457
458	if (ipversion != 4)
459		return -1;
460
461	if (tptr == NULL || aptr == NULL)
462		return -1;
463
464	iph = tptr;
465	addr = aptr;
466
467	READ_ENTER(&ip_poolrw);
468	ipe = fr_iphmfind(iph, addr);
469	if (ipe != NULL)
470		rval = 0;
471	else
472		rval = 1;
473	RWLOCK_EXIT(&ip_poolrw);
474	return rval;
475}
476
477
478/* Locks:  ip_poolrw */
479static iphtent_t *fr_iphmfind(iph, addr)
480iphtable_t *iph;
481struct in_addr *addr;
482{
483	u_32_t hmsk, msk, ips;
484	iphtent_t *ipe;
485	u_int hv;
486
487	hmsk = iph->iph_masks;
488	msk = 0xffffffff;
489maskloop:
490	ips = ntohl(addr->s_addr) & msk;
491	hv = IPE_HASH_FN(ips, msk, iph->iph_size);
492	for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_hnext) {
493		if (ipe->ipe_mask.in4_addr != msk ||
494		    ipe->ipe_addr.in4_addr != ips) {
495			continue;
496		}
497		break;
498	}
499
500	if ((ipe == NULL) && (hmsk != 0)) {
501		while (hmsk != 0) {
502			msk <<= 1;
503			if (hmsk & 0x80000000)
504				break;
505			hmsk <<= 1;
506		}
507		if (hmsk != 0) {
508			hmsk <<= 1;
509			goto maskloop;
510		}
511	}
512	return ipe;
513}
514
515
516int fr_htable_getnext(token, ilp)
517ipftoken_t *token;
518ipflookupiter_t *ilp;
519{
520	iphtent_t *node, zn, *nextnode;
521	iphtable_t *iph, zp, *nextiph;
522	int err;
523
524	err = 0;
525	iph = NULL;
526	node = NULL;
527	nextiph = NULL;
528	nextnode = NULL;
529
530	READ_ENTER(&ip_poolrw);
531
532	switch (ilp->ili_otype)
533	{
534	case IPFLOOKUPITER_LIST :
535		iph = token->ipt_data;
536		if (iph == NULL) {
537			nextiph = ipf_htables[(int)ilp->ili_unit];
538		} else {
539			nextiph = iph->iph_next;
540		}
541
542		if (nextiph != NULL) {
543			ATOMIC_INC(nextiph->iph_ref);
544			token->ipt_data = nextiph;
545		} else {
546			bzero((char *)&zp, sizeof(zp));
547			nextiph = &zp;
548			token->ipt_data = NULL;
549		}
550		break;
551
552	case IPFLOOKUPITER_NODE :
553		node = token->ipt_data;
554		if (node == NULL) {
555			iph = fr_findhtable(ilp->ili_unit, ilp->ili_name);
556			if (iph == NULL)
557				err = ESRCH;
558			else {
559				nextnode = iph->iph_list;
560			}
561		} else {
562			nextnode = node->ipe_next;
563		}
564
565		if (nextnode != NULL) {
566			ATOMIC_INC(nextnode->ipe_ref);
567			token->ipt_data = nextnode;
568		} else {
569			bzero((char *)&zn, sizeof(zn));
570			nextnode = &zn;
571			token->ipt_data = NULL;
572		}
573		break;
574	default :
575		err = EINVAL;
576		break;
577	}
578
579	RWLOCK_EXIT(&ip_poolrw);
580	if (err != 0)
581		return err;
582
583	switch (ilp->ili_otype)
584	{
585	case IPFLOOKUPITER_LIST :
586		if (iph != NULL) {
587			WRITE_ENTER(&ip_poolrw);
588			fr_derefhtable(iph);
589			RWLOCK_EXIT(&ip_poolrw);
590		}
591		err = COPYOUT(nextiph, ilp->ili_data, sizeof(*nextiph));
592		if (err != 0)
593			err = EFAULT;
594		break;
595
596	case IPFLOOKUPITER_NODE :
597		if (node != NULL) {
598			WRITE_ENTER(&ip_poolrw);
599			fr_derefhtent(node);
600			RWLOCK_EXIT(&ip_poolrw);
601		}
602		err = COPYOUT(nextnode, ilp->ili_data, sizeof(*nextnode));
603		if (err != 0)
604			err = EFAULT;
605		break;
606	}
607
608	return err;
609}
610
611
612void fr_htable_iterderef(otype, unit, data)
613u_int otype;
614int unit;
615void *data;
616{
617
618	if (data == NULL)
619		return;
620
621	if (unit < 0 || unit > IPL_LOGMAX)
622		return;
623
624	switch (otype)
625	{
626	case IPFLOOKUPITER_LIST :
627		WRITE_ENTER(&ip_poolrw);
628		fr_derefhtable((iphtable_t *)data);
629		RWLOCK_EXIT(&ip_poolrw);
630		break;
631
632	case IPFLOOKUPITER_NODE :
633		WRITE_ENTER(&ip_poolrw);
634		fr_derefhtent((iphtent_t *)data);
635		RWLOCK_EXIT(&ip_poolrw);
636		break;
637	default :
638		break;
639	}
640}
641
642#endif /* IPFILTER_LOOKUP */
643