4 * Copyright (C) 1993-2001, 2003 by Darren Reed.
6 * See the IPFILTER.LICENCE file for details on licencing.
8 #if defined(KERNEL) || defined(_KERNEL)
14 #include <sys/param.h>
15 #include <sys/types.h>
16 #include <sys/errno.h>
29 #include <sys/socket.h>
30 #if defined(__FreeBSD_version) && (__FreeBSD_version >= 300000)
31 # include <sys/malloc.h>
33 #if defined(__FreeBSD__)
34 # include <sys/cdefs.h>
35 # include <sys/proc.h>
37 #if !defined(__svr4__) && !defined(__SVR4) && !defined(__hpux) && \
39 # include <sys/mbuf.h>
42 # include <sys/systm.h>
46 #include <netinet/in.h>
49 #include "netinet/ip_compat.h"
50 #include "netinet/ip_fil.h"
51 #include "netinet/ip_lookup.h"
52 #include "netinet/ip_htable.h"
56 static const char rcsid[] = "@(#)$Id: ip_htable.c,v 2.34.2.9 2007/02/02 23:06:16 darrenr Exp $";
59 #ifdef IPFILTER_LOOKUP
60 static iphtent_t *fr_iphmfind __P((iphtable_t *, struct in_addr *));
61 static u_long ipht_nomem[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 };
62 static u_long ipf_nhtables[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 };
63 static u_long ipf_nhtnodes[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 };
65 iphtable_t *ipf_htables[IPL_LOGSIZE] = { NULL, NULL, NULL, NULL,
66 NULL, NULL, NULL, NULL };
69 void fr_htable_unload()
73 fop.iplf_unit = IPL_LOGALL;
74 (void)fr_flushhtable(&fop);
78 int fr_gethtablestat(op)
83 if (op->iplo_size != sizeof(stats))
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];
91 return COPYOUT(&stats, op->iplo_struct, sizeof(stats));
97 * Create a new hash table using the template passed.
102 iphtable_t *iph, *oiph;
103 char name[FR_GROUPLEN];
106 unit = op->iplo_unit;
107 if ((op->iplo_arg & IPHASH_ANON) == 0)
108 iph = fr_existshtable(unit, op->iplo_name);
113 KMALLOC(iph, iphtable_t *);
115 ipht_nomem[op->iplo_unit]++;
118 err = COPYIN(op->iplo_struct, iph, sizeof(*iph));
124 if ((iph->iph_flags & IPHASH_DELETE) == 0)
128 if (iph->iph_unit != unit) {
129 if ((iph->iph_flags & IPHASH_DELETE) == 0) {
135 if ((op->iplo_arg & IPHASH_ANON) != 0) {
139 #if defined(SNPRINTF) && defined(_KERNEL)
140 SNPRINTF(name, sizeof(name), "%u", i);
142 (void)sprintf(name, "%u", i);
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)
149 } while (oiph != NULL);
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;
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) {
167 bzero((char *)iph->iph_table,
168 iph->iph_size * sizeof(*iph->iph_table));
170 iph->iph_list = NULL;
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;
179 ipf_nhtables[unit]++;
182 iph->iph_flags &= ~IPHASH_DELETE;
190 int fr_removehtable(unit, name)
196 iph = fr_findhtable(unit, name);
200 if (iph->iph_unit != unit) {
204 if (iph->iph_ref != 0) {
205 (void) fr_clearhtable(iph);
206 iph->iph_flags |= IPHASH_DELETE;
216 int fr_clearhtable(iph)
221 while ((ipe = iph->iph_list) != NULL)
222 if (fr_delhtent(iph, ipe) != 0)
228 int fr_delhtable(iph)
232 if (fr_clearhtable(iph) != 0)
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;
240 ipf_nhtables[iph->iph_unit]--;
242 return fr_derefhtable(iph);
247 * Delete an entry from a hash table.
249 int fr_delhtent(iph, ipe)
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;
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;
264 switch (iph->iph_type & ~IPHASH_ANON)
266 case IPHASH_GROUPMAP :
267 if (ipe->ipe_group != NULL)
268 fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active);
277 return fr_derefhtent(ipe);
281 int fr_derefhtable(iph)
289 if (iph->iph_ref == 0) {
290 KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
298 int fr_derefhtent(ipe)
303 if (ipe->ipe_ref == 0) {
304 ipf_nhtnodes[ipe->ipe_unit]--;
315 iphtable_t *fr_existshtable(unit, name)
321 for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next)
322 if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0)
328 iphtable_t *fr_findhtable(unit, name)
334 iph = fr_existshtable(unit, name);
335 if ((iph != NULL) && (iph->iph_flags & IPHASH_DELETE) == 0)
342 size_t fr_flushhtable(op)
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) {
357 iph->iph_flags |= IPHASH_DELETE;
368 * Add an entry to a hash table.
370 int fr_addhtent(iph, ipeo)
378 KMALLOC(ipe, iphtent_t *);
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);
388 hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr,
391 ipe->ipe_hnext = iph->iph_table[hv];
392 ipe->ipe_phnext = iph->iph_table + hv;
394 if (iph->iph_table[hv] != NULL)
395 iph->iph_table[hv]->ipe_phnext = &ipe->ipe_hnext;
396 iph->iph_table[hv] = ipe;
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;
404 if ((bits >= 0) && (bits != 32))
405 iph->iph_masks |= 1 << bits;
407 switch (iph->iph_type & ~IPHASH_ANON)
409 case IPHASH_GROUPMAP :
410 ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL,
411 iph->iph_flags, IPL_LOGIPF,
421 ipe->ipe_unit = iph->iph_unit;
422 ipf_nhtnodes[ipe->ipe_unit]++;
428 void *fr_iphmfindgroup(tptr, aptr)
431 struct in_addr *addr;
436 READ_ENTER(&ip_poolrw);
440 ipe = fr_iphmfind(iph, addr);
445 RWLOCK_EXIT(&ip_poolrw);
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 */
457 /* Search the hash table for a given address and return a search result. */
458 /* ------------------------------------------------------------------------ */
459 int fr_iphmfindip(tptr, ipversion, aptr)
463 struct in_addr *addr;
471 if (tptr == NULL || aptr == NULL)
477 READ_ENTER(&ip_poolrw);
478 ipe = fr_iphmfind(iph, addr);
483 RWLOCK_EXIT(&ip_poolrw);
488 /* Locks: ip_poolrw */
489 static iphtent_t *fr_iphmfind(iph, addr)
491 struct in_addr *addr;
493 u_32_t hmsk, msk, ips;
497 hmsk = iph->iph_masks;
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) {
510 if ((ipe == NULL) && (hmsk != 0)) {
513 if (hmsk & 0x80000000)
526 int fr_htable_getnext(token, ilp)
528 ipflookupiter_t *ilp;
530 iphtent_t *node, zn, *nextnode;
531 iphtable_t *iph, zp, *nextiph;
540 READ_ENTER(&ip_poolrw);
542 switch (ilp->ili_otype)
544 case IPFLOOKUPITER_LIST :
545 iph = token->ipt_data;
547 nextiph = ipf_htables[(int)ilp->ili_unit];
549 nextiph = iph->iph_next;
552 if (nextiph != NULL) {
553 ATOMIC_INC(nextiph->iph_ref);
554 if (nextiph->iph_next == NULL)
555 token->ipt_alive = 0;
557 bzero((char *)&zp, sizeof(zp));
562 case IPFLOOKUPITER_NODE :
563 node = token->ipt_data;
565 iph = fr_findhtable(ilp->ili_unit, ilp->ili_name);
569 nextnode = iph->iph_list;
572 nextnode = node->ipe_next;
575 if (nextnode != NULL) {
576 ATOMIC_INC(nextnode->ipe_ref);
577 if (nextnode->ipe_next == NULL)
578 token->ipt_alive = 0;
580 bzero((char *)&zn, sizeof(zn));
589 RWLOCK_EXIT(&ip_poolrw);
593 switch (ilp->ili_otype)
595 case IPFLOOKUPITER_LIST :
597 WRITE_ENTER(&ip_poolrw);
599 RWLOCK_EXIT(&ip_poolrw);
601 token->ipt_data = nextiph;
602 err = COPYOUT(nextiph, ilp->ili_data, sizeof(*nextiph));
607 case IPFLOOKUPITER_NODE :
609 WRITE_ENTER(&ip_poolrw);
611 RWLOCK_EXIT(&ip_poolrw);
613 token->ipt_data = nextnode;
614 err = COPYOUT(nextnode, ilp->ili_data, sizeof(*nextnode));
624 void fr_htable_iterderef(otype, unit, data)
633 if (unit < 0 || unit > IPL_LOGMAX)
638 case IPFLOOKUPITER_LIST :
639 WRITE_ENTER(&ip_poolrw);
640 fr_derefhtable((iphtable_t *)data);
641 RWLOCK_EXIT(&ip_poolrw);
644 case IPFLOOKUPITER_NODE :
645 WRITE_ENTER(&ip_poolrw);
646 fr_derefhtent((iphtent_t *)data);
647 RWLOCK_EXIT(&ip_poolrw);
654 #endif /* IPFILTER_LOOKUP */