ip_htable.c revision 147547 
1/*	$FreeBSD: head/sys/contrib/ipfilter/netinet/ip_htable.c 147547 2005-06-23 14:19:02Z 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.2 2004/10/17 15:49:15 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	KMALLOC(iph, iphtable_t *);
107	if (iph == NULL) {
108		ipht_nomem[op->iplo_unit]++;
109		return ENOMEM;
110	}
111
112	err = COPYIN(op->iplo_struct, iph, sizeof(*iph));
113	if (err != 0) {
114		KFREE(iph);
115		return EFAULT;
116	}
117
118	unit = op->iplo_unit;
119	if (iph->iph_unit != unit) {
120		KFREE(iph);
121		return EINVAL;
122	}
123
124	if ((op->iplo_arg & IPHASH_ANON) == 0) {
125		if (fr_findhtable(op->iplo_unit, op->iplo_name) != NULL) {
126			KFREE(iph);
127			return EEXIST;
128		}
129	} else {
130		i = IPHASH_ANON;
131		do {
132			i++;
133#if defined(SNPRINTF) && defined(_KERNEL)
134			SNPRINTF(name, sizeof(name), "%u", i);
135#else
136			(void)sprintf(name, "%u", i);
137#endif
138			for (oiph = ipf_htables[unit]; oiph != NULL;
139			     oiph = oiph->iph_next)
140				if (strncmp(oiph->iph_name, name,
141					    sizeof(oiph->iph_name)) == 0)
142					break;
143		} while (oiph != NULL);
144		(void)strncpy(iph->iph_name, name, sizeof(iph->iph_name));
145		err = COPYOUT(iph, op->iplo_struct, sizeof(*iph));
146		if (err != 0) {
147			KFREE(iph);
148			return EFAULT;
149		}
150		iph->iph_type |= IPHASH_ANON;
151	}
152
153	KMALLOCS(iph->iph_table, iphtent_t **,
154		 iph->iph_size * sizeof(*iph->iph_table));
155	if (iph->iph_table == NULL) {
156		KFREE(iph);
157		ipht_nomem[unit]++;
158		return ENOMEM;
159	}
160
161	bzero((char *)iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
162	iph->iph_masks = 0;
163
164	iph->iph_next = ipf_htables[unit];
165	iph->iph_pnext = &ipf_htables[unit];
166	if (ipf_htables[unit] != NULL)
167		ipf_htables[unit]->iph_pnext = &iph->iph_next;
168	ipf_htables[unit] = iph;
169
170	ipf_nhtables[unit]++;
171
172	return 0;
173}
174
175
176/*
177 */
178int fr_removehtable(op)
179iplookupop_t *op;
180{
181	iphtable_t *iph;
182
183
184	iph = fr_findhtable(op->iplo_unit, op->iplo_name);
185	if (iph == NULL)
186		return ESRCH;
187
188	if (iph->iph_unit != op->iplo_unit) {
189		return EINVAL;
190	}
191
192	if (iph->iph_ref != 0) {
193		return EBUSY;
194	}
195
196	fr_delhtable(iph);
197
198	return 0;
199}
200
201
202void fr_delhtable(iph)
203iphtable_t *iph;
204{
205	iphtent_t *ipe;
206	int i;
207
208	for (i = 0; i < iph->iph_size; i++)
209		while ((ipe = iph->iph_table[i]) != NULL)
210			if (fr_delhtent(iph, ipe) != 0)
211				return;
212
213	*iph->iph_pnext = iph->iph_next;
214	if (iph->iph_next != NULL)
215		iph->iph_next->iph_pnext = iph->iph_pnext;
216
217	ipf_nhtables[iph->iph_unit]--;
218
219	if (iph->iph_ref == 0) {
220		KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
221		KFREE(iph);
222	}
223}
224
225
226void fr_derefhtable(iph)
227iphtable_t *iph;
228{
229	iph->iph_ref--;
230	if (iph->iph_ref == 0)
231		fr_delhtable(iph);
232}
233
234
235iphtable_t *fr_findhtable(unit, name)
236int unit;
237char *name;
238{
239	iphtable_t *iph;
240
241	for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next)
242		if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0)
243			break;
244	return iph;
245}
246
247
248size_t fr_flushhtable(op)
249iplookupflush_t *op;
250{
251	iphtable_t *iph;
252	size_t freed;
253	int i;
254
255	freed = 0;
256
257	for (i = 0; i <= IPL_LOGMAX; i++) {
258		if (op->iplf_unit == i || op->iplf_unit == IPL_LOGALL) {
259			while ((iph = ipf_htables[i]) != NULL) {
260				fr_delhtable(iph);
261				freed++;
262			}
263		}
264	}
265
266	return freed;
267}
268
269
270/*
271 * Add an entry to a hash table.
272 */
273int fr_addhtent(iph, ipeo)
274iphtable_t *iph;
275iphtent_t *ipeo;
276{
277	iphtent_t *ipe;
278	u_int hv;
279	int bits;
280
281	KMALLOC(ipe, iphtent_t *);
282	if (ipe == NULL)
283		return -1;
284
285	bcopy((char *)ipeo, (char *)ipe, sizeof(*ipe));
286	ipe->ipe_addr.in4_addr &= ipe->ipe_mask.in4_addr;
287	ipe->ipe_addr.in4_addr = ntohl(ipe->ipe_addr.in4_addr);
288	bits = count4bits(ipe->ipe_mask.in4_addr);
289	ipe->ipe_mask.in4_addr = ntohl(ipe->ipe_mask.in4_addr);
290
291	hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr,
292			 iph->iph_size);
293	ipe->ipe_ref = 0;
294	ipe->ipe_next = iph->iph_table[hv];
295	ipe->ipe_pnext = iph->iph_table + hv;
296
297	if (iph->iph_table[hv] != NULL)
298		iph->iph_table[hv]->ipe_pnext = &ipe->ipe_next;
299	iph->iph_table[hv] = ipe;
300	if ((bits >= 0) && (bits != 32))
301		iph->iph_masks |= 1 << bits;
302
303	switch (iph->iph_type & ~IPHASH_ANON)
304	{
305	case IPHASH_GROUPMAP :
306		ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL,
307					   iph->iph_flags, IPL_LOGIPF,
308					   fr_active);
309		break;
310
311	default :
312		ipe->ipe_ptr = NULL;
313		ipe->ipe_value = 0;
314		break;
315	}
316
317	ipf_nhtnodes[iph->iph_unit]++;
318
319	return 0;
320}
321
322
323/*
324 * Delete an entry from a hash table.
325 */
326int fr_delhtent(iph, ipe)
327iphtable_t *iph;
328iphtent_t *ipe;
329{
330
331	if (ipe->ipe_ref != 0)
332		return EBUSY;
333
334
335	*ipe->ipe_pnext = ipe->ipe_next;
336	if (ipe->ipe_next != NULL)
337		ipe->ipe_next->ipe_pnext = ipe->ipe_pnext;
338
339	switch (iph->iph_type & ~IPHASH_ANON)
340	{
341	case IPHASH_GROUPMAP :
342		if (ipe->ipe_group != NULL)
343			fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active);
344		break;
345
346	default :
347		ipe->ipe_ptr = NULL;
348		ipe->ipe_value = 0;
349		break;
350	}
351
352	KFREE(ipe);
353
354	ipf_nhtnodes[iph->iph_unit]--;
355
356	return 0;
357}
358
359
360void *fr_iphmfindgroup(tptr, aptr)
361void *tptr, *aptr;
362{
363	struct in_addr *addr;
364	iphtable_t *iph;
365	iphtent_t *ipe;
366	void *rval;
367
368	READ_ENTER(&ip_poolrw);
369	iph = tptr;
370	addr = aptr;
371
372	ipe = fr_iphmfind(iph, addr);
373	if (ipe != NULL)
374		rval = ipe->ipe_ptr;
375	else
376		rval = NULL;
377	RWLOCK_EXIT(&ip_poolrw);
378	return rval;
379}
380
381
382/* ------------------------------------------------------------------------ */
383/* Function:    fr_iphmfindip                                               */
384/* Returns:     int     - 0 == +ve match, -1 == error, 1 == -ve/no match    */
385/* Parameters:  tptr(I)    - pointer to the pool to search                  */
386/*              version(I) - IP protocol version (4 or 6)                   */
387/*              aptr(I)    - pointer to address information                 */
388/*                                                                          */
389/* Search the hash table for a given address and return a search result.    */
390/* ------------------------------------------------------------------------ */
391int fr_iphmfindip(tptr, version, aptr)
392void *tptr, *aptr;
393int version;
394{
395	struct in_addr *addr;
396	iphtable_t *iph;
397	iphtent_t *ipe;
398	int rval;
399
400	if (version != 4)
401		return -1;
402
403	if (tptr == NULL || aptr == NULL)
404		return -1;
405
406	iph = tptr;
407	addr = aptr;
408
409	READ_ENTER(&ip_poolrw);
410	ipe = fr_iphmfind(iph, addr);
411	if (ipe != NULL)
412		rval = 0;
413	else
414		rval = 1;
415	RWLOCK_EXIT(&ip_poolrw);
416	return rval;
417}
418
419
420/* Locks:  ip_poolrw */
421static iphtent_t *fr_iphmfind(iph, addr)
422iphtable_t *iph;
423struct in_addr *addr;
424{
425	u_32_t hmsk, msk, ips;
426	iphtent_t *ipe;
427	u_int hv;
428
429	hmsk = iph->iph_masks;
430	msk = 0xffffffff;
431maskloop:
432	ips = ntohl(addr->s_addr) & msk;
433	hv = IPE_HASH_FN(ips, msk, iph->iph_size);
434	for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_next) {
435		if (ipe->ipe_mask.in4_addr != msk ||
436		    ipe->ipe_addr.in4_addr != ips) {
437			continue;
438		}
439		break;
440	}
441
442	if ((ipe == NULL) && (hmsk != 0)) {
443		while (hmsk != 0) {
444			msk <<= 1;
445			if (hmsk & 0x80000000)
446				break;
447			hmsk <<= 1;
448		}
449		if (hmsk != 0) {
450			hmsk <<= 1;
451			goto maskloop;
452		}
453	}
454	return ipe;
455}
456
457#endif /* IPFILTER_LOOKUP */
458