1 /* 2 * Copyright (C) 1993-2001, 2003 by Darren Reed. 3 * 4 * See the IPFILTER.LICENCE file for details on licencing. 5 * 6 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 7 * Use is subject to license terms. 8 */ 9 10 #pragma ident "%Z%%M% %I% %E% SMI" 11 12 #if defined(KERNEL) || defined(_KERNEL) 13 # undef KERNEL 14 # undef _KERNEL 15 # define KERNEL 1 16 # define _KERNEL 1 17 #endif 18 #include <sys/param.h> 19 #include <sys/types.h> 20 #include <sys/errno.h> 21 #include <sys/time.h> 22 #include <sys/file.h> 23 #if !defined(_KERNEL) 24 # include <stdlib.h> 25 # include <string.h> 26 # define _KERNEL 27 # ifdef __OpenBSD__ 28 struct file; 29 # endif 30 # include <sys/uio.h> 31 # undef _KERNEL 32 #endif 33 #include <sys/socket.h> 34 #if defined(__FreeBSD_version) && (__FreeBSD_version >= 300000) 35 # include <sys/malloc.h> 36 #endif 37 #if defined(__FreeBSD__) 38 # include <sys/cdefs.h> 39 # include <sys/proc.h> 40 #endif 41 #if !defined(__svr4__) && !defined(__SVR4) && !defined(__hpux) 42 # include <sys/mbuf.h> 43 #endif 44 #if defined(_KERNEL) 45 # include <sys/systm.h> 46 #else 47 # include <stdio.h> 48 #endif 49 #include <netinet/in.h> 50 #include <net/if.h> 51 52 #if SOLARIS2 >= 10 53 #include "ip_compat.h" 54 #include "ip_fil.h" 55 #include "ip_lookup.h" 56 #include "ip_htable.h" 57 #else 58 #include "netinet/ip_compat.h" 59 #include "netinet/ip_fil.h" 60 #include "netinet/ip_lookup.h" 61 #include "netinet/ip_htable.h" 62 #endif 63 64 #if !defined(lint) 65 static const char rcsid[] = "@(#)$Id: ip_htable.c,v 2.24 2003/05/12 13:49:17 darrenr Exp $"; 66 #endif 67 68 #ifdef IPFILTER_LOOKUP 69 static iphtent_t *fr_iphmfind __P((iphtable_t *, struct in_addr *)); 70 #ifdef USE_INET6 71 static iphtent_t *fr_iphmfind6 __P((iphtable_t *, struct in6_addr *)); 72 static uint32_t sum4(uint32_t *); 73 static void left_shift_ipv6 __P((char *)); 74 #endif 75 76 static u_long ipht_nomem[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 }; 77 static u_long ipf_nhtables[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 }; 78 static u_long ipf_nhtnodes[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 }; 79 80 iphtable_t *ipf_htables[IPL_LOGSIZE] = { NULL, NULL, NULL, NULL, 81 NULL, NULL, NULL, NULL }; 82 83 void fr_htable_unload() 84 { 85 iplookupflush_t fop; 86 iphtable_t *iph; 87 int unit; 88 89 for (unit = 0; unit < IPL_LOGMAX; unit++) { 90 fop.iplf_unit = unit; 91 while ((iph = ipf_htables[unit]) != NULL) { 92 (void)strncpy(fop.iplf_name, iph->iph_name, 93 sizeof(fop.iplf_name)); 94 (void)fr_flushhtable(&fop); 95 } 96 } 97 } 98 99 int fr_gethtablestat(op) 100 iplookupop_t *op; 101 { 102 iphtstat_t stats; 103 104 if (op->iplo_size != sizeof(stats)) 105 return EINVAL; 106 107 stats.iphs_tables = ipf_htables[op->iplo_unit]; 108 stats.iphs_numtables = ipf_nhtables[op->iplo_unit]; 109 stats.iphs_numnodes = ipf_nhtnodes[op->iplo_unit]; 110 stats.iphs_nomem = ipht_nomem[op->iplo_unit]; 111 112 return COPYOUT(&stats, op->iplo_struct, sizeof(stats)); 113 114 } 115 116 117 /* 118 * Create a new hash table using the template passed. 119 */ 120 int fr_newhtable(op) 121 iplookupop_t *op; 122 { 123 iphtable_t *iph, *oiph; 124 char name[FR_GROUPLEN]; 125 int err, i, unit; 126 127 KMALLOC(iph, iphtable_t *); 128 if (iph == NULL) 129 return ENOMEM; 130 131 err = COPYIN(op->iplo_struct, iph, sizeof(*iph)); 132 if (err != 0) { 133 KFREE(iph); 134 return EFAULT; 135 } 136 137 unit = op->iplo_unit; 138 if (iph->iph_unit != unit) { 139 KFREE(iph); 140 return EINVAL; 141 } 142 143 if ((op->iplo_arg & IPHASH_ANON) == 0) { 144 if (fr_findhtable(op->iplo_unit, op->iplo_name) != NULL) { 145 KFREE(iph); 146 return EEXIST; 147 } 148 } else { 149 i = IPHASH_ANON; 150 do { 151 i++; 152 (void)sprintf(name, "%u", i); 153 for (oiph = ipf_htables[unit]; oiph != NULL; 154 oiph = oiph->iph_next) 155 if (strncmp(oiph->iph_name, name, 156 sizeof(oiph->iph_name)) == 0) 157 break; 158 } while (oiph != NULL); 159 (void)strncpy(iph->iph_name, name, sizeof(iph->iph_name)); 160 err = COPYOUT(iph, op->iplo_struct, sizeof(*iph)); 161 if (err != 0) { 162 KFREE(iph); 163 return EFAULT; 164 } 165 iph->iph_type |= IPHASH_ANON; 166 } 167 168 KMALLOCS(iph->iph_table, iphtent_t **, 169 iph->iph_size * sizeof(*iph->iph_table)); 170 if (iph->iph_table == NULL) { 171 KFREE(iph); 172 ipht_nomem[unit]++; 173 return ENOMEM; 174 } 175 176 bzero((char *)iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 177 iph->iph_masks[0] = 0; 178 iph->iph_masks[1] = 0; 179 iph->iph_masks[2] = 0; 180 iph->iph_masks[3] = 0; 181 182 iph->iph_next = ipf_htables[unit]; 183 iph->iph_pnext = &ipf_htables[unit]; 184 if (ipf_htables[unit] != NULL) 185 ipf_htables[unit]->iph_pnext = &iph->iph_next; 186 ipf_htables[unit] = iph; 187 188 ipf_nhtables[unit]++; 189 190 return 0; 191 } 192 193 194 /* 195 */ 196 int fr_removehtable(op) 197 iplookupop_t *op; 198 { 199 iphtable_t *iph; 200 201 202 iph = fr_findhtable(op->iplo_unit, op->iplo_name); 203 if (iph == NULL) 204 return ESRCH; 205 206 if (iph->iph_unit != op->iplo_unit) { 207 return EINVAL; 208 } 209 210 if (iph->iph_ref != 0) { 211 return EBUSY; 212 } 213 214 fr_delhtable(iph); 215 216 return 0; 217 } 218 219 220 void fr_delhtable(iph) 221 iphtable_t *iph; 222 { 223 224 *iph->iph_pnext = iph->iph_next; 225 if (iph->iph_next != NULL) 226 iph->iph_next->iph_pnext = iph->iph_pnext; 227 228 ipf_nhtables[iph->iph_unit]--; 229 230 KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 231 KFREE(iph); 232 } 233 234 235 void fr_derefhtable(iph) 236 iphtable_t *iph; 237 { 238 iph->iph_ref--; 239 if (iph->iph_ref == 0) 240 fr_delhtable(iph); 241 } 242 243 244 iphtable_t *fr_findhtable(unit, name) 245 int unit; 246 char *name; 247 { 248 iphtable_t *iph; 249 250 for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next) 251 if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0) 252 break; 253 return iph; 254 } 255 256 257 size_t fr_flushhtable(op) 258 iplookupflush_t *op; 259 { 260 iphtable_t *iph; 261 size_t i, freed; 262 iphtent_t *ipe; 263 264 iph = fr_findhtable(op->iplf_unit, op->iplf_name); 265 if (iph == NULL) { 266 return 0; 267 } 268 269 freed = 0; 270 *iph->iph_pnext = iph->iph_next; 271 if (iph->iph_next != NULL) 272 iph->iph_next->iph_pnext = iph->iph_pnext; 273 274 for (i = 0; i < iph->iph_size; i++) 275 while ((ipe = iph->iph_table[i]) != NULL) { 276 *ipe->ipe_pnext = ipe->ipe_next; 277 if (ipe->ipe_next != NULL) 278 ipe->ipe_next->ipe_pnext = ipe->ipe_pnext; 279 280 switch (iph->iph_type & ~IPHASH_ANON) 281 { 282 case IPHASH_GROUPMAP : 283 if (ipe->ipe_ptr != NULL) 284 fr_delgroup(ipe->ipe_group, 285 IPL_LOGIPF, fr_active); 286 break; 287 } 288 /* ipe_ref */ 289 KFREE(ipe); 290 freed++; 291 } 292 293 KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 294 KFREE(iph); 295 296 return freed; 297 } 298 299 300 /* 301 * Add an entry to a hash table. 302 */ 303 int fr_addhtent(iph, ipeo) 304 iphtable_t *iph; 305 iphtent_t *ipeo; 306 { 307 iphtent_t *ipe; 308 u_int hv; 309 int bits; 310 311 KMALLOC(ipe, iphtent_t *); 312 if (ipe == NULL) 313 return -1; 314 315 bcopy((char *)ipeo, (char *)ipe, sizeof(*ipe)); 316 #ifdef USE_INET6 317 if (ipe->ipe_family == AF_INET6) { 318 bits = count6bits((u_32_t *)ipe->ipe_mask.in6_addr8); 319 hv = IPE_HASH_FN(sum4((uint32_t *)ipe->ipe_addr.in6_addr8), 320 sum4((uint32_t *)ipe->ipe_mask.in6_addr8), 321 iph->iph_size); 322 } else 323 #endif 324 if (ipe->ipe_family == AF_INET) 325 { 326 ipe->ipe_addr.in4_addr &= ipe->ipe_mask.in4_addr; 327 ipe->ipe_addr.in4_addr = ntohl(ipe->ipe_addr.in4_addr); 328 bits = count4bits(ipe->ipe_mask.in4_addr); 329 ipe->ipe_mask.in4_addr = ntohl(ipe->ipe_mask.in4_addr); 330 331 hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr, 332 iph->iph_size); 333 } else 334 return -1; 335 336 ipe->ipe_ref = 0; 337 ipe->ipe_next = iph->iph_table[hv]; 338 ipe->ipe_pnext = iph->iph_table + hv; 339 340 if (iph->iph_table[hv] != NULL) 341 iph->iph_table[hv]->ipe_pnext = &ipe->ipe_next; 342 iph->iph_table[hv] = ipe; 343 #ifdef USE_INET6 344 if (ipe->ipe_family == AF_INET6) { 345 if ((bits >= 0) && (bits != 128)) 346 if (bits >= 96) 347 iph->iph_masks[0] |= 1 << (bits - 96); 348 else if (bits >= 64) 349 iph->iph_masks[1] |= 1 << (bits - 64); 350 else if (bits >= 32) 351 iph->iph_masks[2] |= 1 << (bits - 32); 352 else 353 iph->iph_masks[3] |= 1 << bits; 354 355 } else 356 #endif 357 { 358 if ((bits >= 0) && (bits != 32)) 359 iph->iph_masks[3] |= 1 << bits; 360 } 361 362 switch (iph->iph_type & ~IPHASH_ANON) 363 { 364 case IPHASH_GROUPMAP : 365 ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL, 366 iph->iph_flags, IPL_LOGIPF, 367 fr_active); 368 break; 369 370 default : 371 ipe->ipe_ptr = NULL; 372 ipe->ipe_value = 0; 373 break; 374 } 375 376 ipf_nhtnodes[iph->iph_unit]++; 377 378 return 0; 379 } 380 381 382 /* 383 * Delete an entry from a hash table. 384 */ 385 int fr_delhtent(iph, ipe) 386 iphtable_t *iph; 387 iphtent_t *ipe; 388 { 389 390 if (ipe->ipe_ref != 0) 391 return EBUSY; 392 393 394 *ipe->ipe_pnext = ipe->ipe_next; 395 if (ipe->ipe_next != NULL) 396 ipe->ipe_next->ipe_pnext = ipe->ipe_pnext; 397 398 switch (iph->iph_type & ~IPHASH_ANON) 399 { 400 case IPHASH_GROUPMAP : 401 if (ipe->ipe_group != NULL) 402 fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active); 403 break; 404 405 default : 406 ipe->ipe_ptr = NULL; 407 ipe->ipe_value = 0; 408 break; 409 } 410 411 KFREE(ipe); 412 413 ipf_nhtnodes[iph->iph_unit]--; 414 415 return 0; 416 } 417 418 419 void *fr_iphmfindgroup(tptr, version, aptr) 420 void *tptr, *aptr; 421 int version; 422 { 423 i6addr_t *addr; 424 iphtable_t *iph; 425 iphtent_t *ipe; 426 void *rval; 427 428 if ((version != 4) 429 #ifdef USE_INET6 430 && (version != 6) 431 #endif 432 ) 433 return NULL; 434 435 READ_ENTER(&ip_poolrw); 436 iph = tptr; 437 addr = aptr; 438 439 #ifdef USE_INET6 440 if (version == 6) 441 ipe = fr_iphmfind6(iph, &addr->in6); 442 else 443 #endif 444 if (version == 4) 445 ipe = fr_iphmfind(iph, &addr->in4); 446 else 447 ipe = NULL; 448 if (ipe != NULL) 449 rval = ipe->ipe_ptr; 450 else 451 rval = NULL; 452 RWLOCK_EXIT(&ip_poolrw); 453 return rval; 454 } 455 456 457 int fr_iphmfindip(tptr, version, aptr) 458 void *tptr, *aptr; 459 int version; 460 { 461 i6addr_t *addr; 462 iphtable_t *iph; 463 iphtent_t *ipe; 464 int rval; 465 466 if (tptr == NULL || aptr == NULL) 467 return 1; 468 469 iph = tptr; 470 addr = aptr; 471 472 READ_ENTER(&ip_poolrw); 473 #ifdef USE_INET6 474 if (version == 6) 475 ipe = fr_iphmfind6(iph, &addr->in6); 476 else 477 #endif 478 if (version == 4) 479 ipe = fr_iphmfind(iph, &addr->in4); 480 else 481 ipe = NULL; 482 if (ipe != NULL) 483 rval = 0; 484 else 485 rval = 1; 486 RWLOCK_EXIT(&ip_poolrw); 487 return rval; 488 } 489 490 491 /* Locks: ip_poolrw */ 492 static iphtent_t *fr_iphmfind(iph, addr) 493 iphtable_t *iph; 494 struct in_addr *addr; 495 { 496 u_32_t hmsk, msk, ips; 497 iphtent_t *ipe; 498 u_int hv; 499 500 hmsk = iph->iph_masks[3]; 501 502 msk = 0xffffffff; 503 maskloop: 504 ips = ntohl(addr->s_addr) & msk; 505 hv = IPE_HASH_FN(ips, msk, iph->iph_size); 506 for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_next) { 507 if (ipe->ipe_mask.in4_addr != msk || 508 ipe->ipe_addr.in4_addr != ips) { 509 continue; 510 } 511 break; 512 } 513 514 if ((ipe == NULL) && (hmsk != 0)) { 515 while (hmsk != 0) { 516 msk <<= 1; 517 if (hmsk & 0x80000000) 518 break; 519 hmsk <<= 1; 520 } 521 if (hmsk != 0) { 522 hmsk <<= 1; 523 goto maskloop; 524 } 525 } 526 527 return ipe; 528 } 529 530 531 #ifdef USE_INET6 532 /* Locks: ip_poolrw */ 533 static iphtent_t *fr_iphmfind6(iph, addr) 534 iphtable_t *iph; 535 struct in6_addr *addr; 536 { 537 u_32_t hmsk[4], msk[4], ips[4], *and; 538 iphtent_t *ipe; 539 u_int hv; 540 541 hmsk[0] = iph->iph_masks[0]; 542 hmsk[1] = iph->iph_masks[1]; 543 hmsk[2] = iph->iph_masks[2]; 544 hmsk[3] = iph->iph_masks[3]; 545 546 msk[0] = 0xffffffff; 547 msk[1] = 0xffffffff; 548 msk[2] = 0xffffffff; 549 msk[3] = 0xffffffff; 550 maskloop: 551 and = (u_32_t *)addr->s6_addr; 552 ips[0] = *and & msk[0]; 553 ips[1] = *(and + 1) & msk[1]; 554 ips[2] = *(and + 2) & msk[2]; 555 ips[3] = *(and + 3) & msk[3]; 556 557 hv = IPE_HASH_FN(sum4((uint32_t *)addr), sum4((uint32_t *)msk), 558 iph->iph_size); 559 for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_next) { 560 if (bcmp((void *)&ipe->ipe_mask.in6, (void *)msk, 16) || 561 bcmp((void *)&ipe->ipe_addr.in6, (void *)ips, 16)) 562 continue; 563 break; 564 } 565 566 if ((ipe == NULL) && ((hmsk[0] != 0) || 567 (hmsk[1] != 0) || 568 (hmsk[2] != 0) || 569 (hmsk[3] != 0) )) { 570 while ((hmsk[0] != 0) && (hmsk[1] != 0) && 571 (hmsk[2] != 0) && (hmsk[3] != 0)) { 572 left_shift_ipv6((char *)msk); 573 if (hmsk[0] & 0x80000000) 574 break; 575 left_shift_ipv6((char *)hmsk); 576 } 577 if ((hmsk[0] != 0) && (hmsk[1] != 0) && 578 (hmsk[2] != 0) && (hmsk[3] != 0)) { 579 left_shift_ipv6((char *)hmsk); 580 goto maskloop; 581 } 582 } 583 584 return ipe; 585 } 586 587 588 /* 589 * sum4: ipv6 add -> 4 bytes values 590 */ 591 static uint32_t sum4(add) 592 uint32_t *add; 593 { 594 return (*add + *(add + 1) + *(add + 2) + *(add + 3)); 595 } 596 597 /* 598 * left shift on 128 bits 599 */ 600 static void left_shift_ipv6(data) 601 char *data; 602 { 603 u_32_t *sd; 604 605 sd = (u_32_t *)data; 606 sd[0] <<= 1; 607 if (sd[1] >= 0x80000000) 608 sd[0] += 1; 609 610 sd[1] <<= 1; 611 if (sd[2] >= 0x80000000) 612 sd[1] += 1; 613 614 sd[2] <<= 1; 615 if (sd[3] >= 0x80000000) 616 sd[2] += 1; 617 618 sd[3] <<= 1; 619 } 620 #endif 621 #endif /* IPFILTER_LOOKUP */ 622