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