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