ip_htable.c revision 170268 
1/*	$FreeBSD: head/sys/contrib/ipfilter/netinet/ip_htable.c 170268 2007-06-04 02:54:36Z darrenr $	*/
2
3/*
4 * Copyright (C) 1993-2001, 2003 by Darren Reed.
5 *
6 * See the IPFILTER.LICENCE file for details on licencing.
7 */
8#if defined(KERNEL) || defined(_KERNEL)
9# undef KERNEL
10# undef _KERNEL
11# define        KERNEL	1
12# define        _KERNEL	1
13#endif
14#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.9 2007/02/02 23:06:16 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	else
110		iph = NULL;
111
112	if (iph == NULL) {
113		KMALLOC(iph, iphtable_t *);
114		if (iph == NULL) {
115			ipht_nomem[op->iplo_unit]++;
116			return ENOMEM;
117		}
118		err = COPYIN(op->iplo_struct, iph, sizeof(*iph));
119		if (err != 0) {
120			KFREE(iph);
121			return EFAULT;
122		}
123	} else {
124		if ((iph->iph_flags & IPHASH_DELETE) == 0)
125			return EEXIST;
126	}
127
128	if (iph->iph_unit != unit) {
129		if ((iph->iph_flags & IPHASH_DELETE) == 0) {
130			KFREE(iph);
131		}
132		return EINVAL;
133	}
134
135	if ((op->iplo_arg & IPHASH_ANON) != 0) {
136		i = IPHASH_ANON;
137		do {
138			i++;
139#if defined(SNPRINTF) && defined(_KERNEL)
140			SNPRINTF(name, sizeof(name), "%u", i);
141#else
142			(void)sprintf(name, "%u", i);
143#endif
144			for (oiph = ipf_htables[unit]; oiph != NULL;
145			     oiph = oiph->iph_next)
146				if (strncmp(oiph->iph_name, name,
147					    sizeof(oiph->iph_name)) == 0)
148					break;
149		} while (oiph != NULL);
150
151		(void)strncpy(iph->iph_name, name, sizeof(iph->iph_name));
152		(void)strncpy(op->iplo_name, name, sizeof(op->iplo_name));
153		iph->iph_type |= IPHASH_ANON;
154	}
155
156	if ((iph->iph_flags & IPHASH_DELETE) == 0) {
157		KMALLOCS(iph->iph_table, iphtent_t **,
158			 iph->iph_size * sizeof(*iph->iph_table));
159		if (iph->iph_table == NULL) {
160			if ((iph->iph_flags & IPHASH_DELETE) == 0) {
161				KFREE(iph);
162			}
163			ipht_nomem[unit]++;
164			return ENOMEM;
165		}
166
167		bzero((char *)iph->iph_table,
168		      iph->iph_size * sizeof(*iph->iph_table));
169		iph->iph_masks = 0;
170		iph->iph_list = NULL;
171
172		iph->iph_ref = 1;
173		iph->iph_next = ipf_htables[unit];
174		iph->iph_pnext = &ipf_htables[unit];
175		if (ipf_htables[unit] != NULL)
176			ipf_htables[unit]->iph_pnext = &iph->iph_next;
177		ipf_htables[unit] = iph;
178
179		ipf_nhtables[unit]++;
180	}
181
182	iph->iph_flags &= ~IPHASH_DELETE;
183
184	return 0;
185}
186
187
188/*
189 */
190int fr_removehtable(unit, name)
191int unit;
192char *name;
193{
194	iphtable_t *iph;
195
196	iph = fr_findhtable(unit, name);
197	if (iph == NULL)
198		return ESRCH;
199
200	if (iph->iph_unit != unit) {
201		return EINVAL;
202	}
203
204	if (iph->iph_ref != 0) {
205		(void) fr_clearhtable(iph);
206		iph->iph_flags |= IPHASH_DELETE;
207		return 0;
208	}
209
210	fr_delhtable(iph);
211
212	return 0;
213}
214
215
216int fr_clearhtable(iph)
217iphtable_t *iph;
218{
219	iphtent_t *ipe;
220
221	while ((ipe = iph->iph_list) != NULL)
222		if (fr_delhtent(iph, ipe) != 0)
223			return 1;
224	return 0;
225}
226
227
228int fr_delhtable(iph)
229iphtable_t *iph;
230{
231
232	if (fr_clearhtable(iph) != 0)
233		return 1;
234
235	if (iph->iph_pnext != NULL)
236		*iph->iph_pnext = iph->iph_next;
237	if (iph->iph_next != NULL)
238		iph->iph_next->iph_pnext = iph->iph_pnext;
239
240	ipf_nhtables[iph->iph_unit]--;
241
242	return fr_derefhtable(iph);
243}
244
245
246/*
247 * Delete an entry from a hash table.
248 */
249int fr_delhtent(iph, ipe)
250iphtable_t *iph;
251iphtent_t *ipe;
252{
253
254	if (ipe->ipe_phnext != NULL)
255		*ipe->ipe_phnext = ipe->ipe_hnext;
256	if (ipe->ipe_hnext != NULL)
257		ipe->ipe_hnext->ipe_phnext = ipe->ipe_phnext;
258
259	if (ipe->ipe_pnext != NULL)
260		*ipe->ipe_pnext = ipe->ipe_next;
261	if (ipe->ipe_next != NULL)
262		ipe->ipe_next->ipe_pnext = ipe->ipe_pnext;
263
264	switch (iph->iph_type & ~IPHASH_ANON)
265	{
266	case IPHASH_GROUPMAP :
267		if (ipe->ipe_group != NULL)
268			fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active);
269		break;
270
271	default :
272		ipe->ipe_ptr = NULL;
273		ipe->ipe_value = 0;
274		break;
275	}
276
277	return fr_derefhtent(ipe);
278}
279
280
281int fr_derefhtable(iph)
282iphtable_t *iph;
283{
284	int refs;
285
286	iph->iph_ref--;
287	refs = iph->iph_ref;
288
289	if (iph->iph_ref == 0) {
290		KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
291		KFREE(iph);
292	}
293
294	return refs;
295}
296
297
298int fr_derefhtent(ipe)
299iphtent_t *ipe;
300{
301
302	ipe->ipe_ref--;
303	if (ipe->ipe_ref == 0) {
304		ipf_nhtnodes[ipe->ipe_unit]--;
305
306		KFREE(ipe);
307
308		return 0;
309	}
310
311	return ipe->ipe_ref;
312}
313
314
315iphtable_t *fr_existshtable(unit, name)
316int unit;
317char *name;
318{
319	iphtable_t *iph;
320
321	for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next)
322		if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0)
323			break;
324	return iph;
325}
326
327
328iphtable_t *fr_findhtable(unit, name)
329int unit;
330char *name;
331{
332	iphtable_t *iph;
333
334	iph = fr_existshtable(unit, name);
335	if ((iph != NULL) && (iph->iph_flags & IPHASH_DELETE) == 0)
336		return iph;
337
338	return NULL;
339}
340
341
342size_t fr_flushhtable(op)
343iplookupflush_t *op;
344{
345	iphtable_t *iph;
346	size_t freed;
347	int i;
348
349	freed = 0;
350
351	for (i = 0; i <= IPL_LOGMAX; i++) {
352		if (op->iplf_unit == i || op->iplf_unit == IPL_LOGALL) {
353			while ((iph = ipf_htables[i]) != NULL) {
354				if (fr_delhtable(iph) == 0) {
355					freed++;
356				} else {
357					iph->iph_flags |= IPHASH_DELETE;
358				}
359			}
360		}
361	}
362
363	return freed;
364}
365
366
367/*
368 * Add an entry to a hash table.
369 */
370int fr_addhtent(iph, ipeo)
371iphtable_t *iph;
372iphtent_t *ipeo;
373{
374	iphtent_t *ipe;
375	u_int hv;
376	int bits;
377
378	KMALLOC(ipe, iphtent_t *);
379	if (ipe == NULL)
380		return -1;
381
382	bcopy((char *)ipeo, (char *)ipe, sizeof(*ipe));
383	ipe->ipe_addr.in4_addr &= ipe->ipe_mask.in4_addr;
384	ipe->ipe_addr.in4_addr = ntohl(ipe->ipe_addr.in4_addr);
385	bits = count4bits(ipe->ipe_mask.in4_addr);
386	ipe->ipe_mask.in4_addr = ntohl(ipe->ipe_mask.in4_addr);
387
388	hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr,
389			 iph->iph_size);
390	ipe->ipe_ref = 1;
391	ipe->ipe_hnext = iph->iph_table[hv];
392	ipe->ipe_phnext = iph->iph_table + hv;
393
394	if (iph->iph_table[hv] != NULL)
395		iph->iph_table[hv]->ipe_phnext = &ipe->ipe_hnext;
396	iph->iph_table[hv] = ipe;
397
398	ipe->ipe_next = iph->iph_list;
399	ipe->ipe_pnext = &iph->iph_list;
400	if (ipe->ipe_next != NULL)
401		ipe->ipe_next->ipe_pnext = &ipe->ipe_next;
402	iph->iph_list = ipe;
403
404	if ((bits >= 0) && (bits != 32))
405		iph->iph_masks |= 1 << bits;
406
407	switch (iph->iph_type & ~IPHASH_ANON)
408	{
409	case IPHASH_GROUPMAP :
410		ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL,
411					   iph->iph_flags, IPL_LOGIPF,
412					   fr_active);
413		break;
414
415	default :
416		ipe->ipe_ptr = NULL;
417		ipe->ipe_value = 0;
418		break;
419	}
420
421	ipe->ipe_unit = iph->iph_unit;
422	ipf_nhtnodes[ipe->ipe_unit]++;
423
424	return 0;
425}
426
427
428void *fr_iphmfindgroup(tptr, aptr)
429void *tptr, *aptr;
430{
431	struct in_addr *addr;
432	iphtable_t *iph;
433	iphtent_t *ipe;
434	void *rval;
435
436	READ_ENTER(&ip_poolrw);
437	iph = tptr;
438	addr = aptr;
439
440	ipe = fr_iphmfind(iph, addr);
441	if (ipe != NULL)
442		rval = ipe->ipe_ptr;
443	else
444		rval = NULL;
445	RWLOCK_EXIT(&ip_poolrw);
446	return rval;
447}
448
449
450/* ------------------------------------------------------------------------ */
451/* Function:    fr_iphmfindip                                               */
452/* Returns:     int     - 0 == +ve match, -1 == error, 1 == -ve/no match    */
453/* Parameters:  tptr(I)      - pointer to the pool to search                */
454/*              ipversion(I) - IP protocol version (4 or 6)                 */
455/*              aptr(I)      - pointer to address information               */
456/*                                                                          */
457/* Search the hash table for a given address and return a search result.    */
458/* ------------------------------------------------------------------------ */
459int fr_iphmfindip(tptr, ipversion, aptr)
460void *tptr, *aptr;
461int ipversion;
462{
463	struct in_addr *addr;
464	iphtable_t *iph;
465	iphtent_t *ipe;
466	int rval;
467
468	if (ipversion != 4)
469		return -1;
470
471	if (tptr == NULL || aptr == NULL)
472		return -1;
473
474	iph = tptr;
475	addr = aptr;
476
477	READ_ENTER(&ip_poolrw);
478	ipe = fr_iphmfind(iph, addr);
479	if (ipe != NULL)
480		rval = 0;
481	else
482		rval = 1;
483	RWLOCK_EXIT(&ip_poolrw);
484	return rval;
485}
486
487
488/* Locks:  ip_poolrw */
489static iphtent_t *fr_iphmfind(iph, addr)
490iphtable_t *iph;
491struct in_addr *addr;
492{
493	u_32_t hmsk, msk, ips;
494	iphtent_t *ipe;
495	u_int hv;
496
497	hmsk = iph->iph_masks;
498	msk = 0xffffffff;
499maskloop:
500	ips = ntohl(addr->s_addr) & msk;
501	hv = IPE_HASH_FN(ips, msk, iph->iph_size);
502	for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_hnext) {
503		if (ipe->ipe_mask.in4_addr != msk ||
504		    ipe->ipe_addr.in4_addr != ips) {
505			continue;
506		}
507		break;
508	}
509
510	if ((ipe == NULL) && (hmsk != 0)) {
511		while (hmsk != 0) {
512			msk <<= 1;
513			if (hmsk & 0x80000000)
514				break;
515			hmsk <<= 1;
516		}
517		if (hmsk != 0) {
518			hmsk <<= 1;
519			goto maskloop;
520		}
521	}
522	return ipe;
523}
524
525
526int fr_htable_getnext(token, ilp)
527ipftoken_t *token;
528ipflookupiter_t *ilp;
529{
530	iphtent_t *node, zn, *nextnode;
531	iphtable_t *iph, zp, *nextiph;
532	int err;
533
534	err = 0;
535	iph = NULL;
536	node = NULL;
537	nextiph = NULL;
538	nextnode = NULL;
539
540	READ_ENTER(&ip_poolrw);
541
542	switch (ilp->ili_otype)
543	{
544	case IPFLOOKUPITER_LIST :
545		iph = token->ipt_data;
546		if (iph == NULL) {
547			nextiph = ipf_htables[(int)ilp->ili_unit];
548		} else {
549			nextiph = iph->iph_next;
550		}
551
552		if (nextiph != NULL) {
553			ATOMIC_INC(nextiph->iph_ref);
554			if (nextiph->iph_next == NULL)
555				token->ipt_alive = 0;
556		} else {
557			bzero((char *)&zp, sizeof(zp));
558			nextiph = &zp;
559		}
560		break;
561
562	case IPFLOOKUPITER_NODE :
563		node = token->ipt_data;
564		if (node == NULL) {
565			iph = fr_findhtable(ilp->ili_unit, ilp->ili_name);
566			if (iph == NULL)
567				err = ESRCH;
568			else {
569				nextnode = iph->iph_list;
570			}
571		} else {
572			nextnode = node->ipe_next;
573		}
574
575		if (nextnode != NULL) {
576			ATOMIC_INC(nextnode->ipe_ref);
577			if (nextnode->ipe_next == NULL)
578				token->ipt_alive = 0;
579		} else {
580			bzero((char *)&zn, sizeof(zn));
581			nextnode = &zn;
582		}
583		break;
584	default :
585		err = EINVAL;
586		break;
587	}
588
589	RWLOCK_EXIT(&ip_poolrw);
590	if (err != 0)
591		return err;
592
593	switch (ilp->ili_otype)
594	{
595	case IPFLOOKUPITER_LIST :
596		if (iph != NULL) {
597			WRITE_ENTER(&ip_poolrw);
598			fr_derefhtable(iph);
599			RWLOCK_EXIT(&ip_poolrw);
600		}
601		token->ipt_data = nextiph;
602		err = COPYOUT(nextiph, ilp->ili_data, sizeof(*nextiph));
603		if (err != 0)
604			err = EFAULT;
605		break;
606
607	case IPFLOOKUPITER_NODE :
608		if (node != NULL) {
609			WRITE_ENTER(&ip_poolrw);
610			fr_derefhtent(node);
611			RWLOCK_EXIT(&ip_poolrw);
612		}
613		token->ipt_data = nextnode;
614		err = COPYOUT(nextnode, ilp->ili_data, sizeof(*nextnode));
615		if (err != 0)
616			err = EFAULT;
617		break;
618	}
619
620	return err;
621}
622
623
624void fr_htable_iterderef(otype, unit, data)
625u_int otype;
626int unit;
627void *data;
628{
629
630	if (data == NULL)
631		return;
632
633	if (unit < 0 || unit > IPL_LOGMAX)
634		return;
635
636	switch (otype)
637	{
638	case IPFLOOKUPITER_LIST :
639		WRITE_ENTER(&ip_poolrw);
640		fr_derefhtable((iphtable_t *)data);
641		RWLOCK_EXIT(&ip_poolrw);
642		break;
643
644	case IPFLOOKUPITER_NODE :
645		WRITE_ENTER(&ip_poolrw);
646		fr_derefhtent((iphtent_t *)data);
647		RWLOCK_EXIT(&ip_poolrw);
648		break;
649	default :
650		break;
651	}
652}
653
654#endif /* IPFILTER_LOOKUP */
655