1 /* $FreeBSD: stable/9/sys/contrib/ipfilter/netinet/ip_htable.c 172776 2007-10-18 21:52:14Z 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__
24 struct 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)
56 static 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
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 };
64
65 iphtable_t *ipf_htables[IPL_LOGSIZE] = { NULL, NULL, NULL, NULL,
66 NULL, NULL, NULL, NULL };
67
68
fr_htable_unload()69 void fr_htable_unload()
70 {
71 iplookupflush_t fop;
72
73 fop.iplf_unit = IPL_LOGALL;
74 (void)fr_flushhtable(&fop);
75 }
76
77
fr_gethtablestat(op)78 int fr_gethtablestat(op)
79 iplookupop_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 */
fr_newhtable(op)99 int fr_newhtable(op)
100 iplookupop_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 */
fr_removehtable(unit,name)180 int fr_removehtable(unit, name)
181 int unit;
182 char *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
fr_clearhtable(iph)206 int fr_clearhtable(iph)
207 iphtable_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
fr_delhtable(iph)218 int fr_delhtable(iph)
219 iphtable_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 */
fr_delhtent(iph,ipe)239 int fr_delhtent(iph, ipe)
240 iphtable_t *iph;
241 iphtent_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
fr_derefhtable(iph)271 int fr_derefhtable(iph)
272 iphtable_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
fr_derefhtent(ipe)288 int fr_derefhtent(ipe)
289 iphtent_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
fr_existshtable(unit,name)305 iphtable_t *fr_existshtable(unit, name)
306 int unit;
307 char *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
fr_findhtable(unit,name)318 iphtable_t *fr_findhtable(unit, name)
319 int unit;
320 char *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
fr_flushhtable(op)332 size_t fr_flushhtable(op)
333 iplookupflush_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 */
fr_addhtent(iph,ipeo)360 int fr_addhtent(iph, ipeo)
361 iphtable_t *iph;
362 iphtent_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
fr_iphmfindgroup(tptr,aptr)418 void *fr_iphmfindgroup(tptr, aptr)
419 void *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 /* ------------------------------------------------------------------------ */
fr_iphmfindip(tptr,ipversion,aptr)449 int fr_iphmfindip(tptr, ipversion, aptr)
450 void *tptr, *aptr;
451 int 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 */
fr_iphmfind(iph,addr)479 static iphtent_t *fr_iphmfind(iph, addr)
480 iphtable_t *iph;
481 struct 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;
489 maskloop:
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
fr_htable_getnext(token,ilp)516 int fr_htable_getnext(token, ilp)
517 ipftoken_t *token;
518 ipflookupiter_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
fr_htable_iterderef(otype,unit,data)612 void fr_htable_iterderef(otype, unit, data)
613 u_int otype;
614 int unit;
615 void *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