sys/contrib/ipfilter/netinet/ip_htable.c

   1 /*      $FreeBSD$       */
   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.9 2007/02/02 23:06:16 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
  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
  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  */
  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         else
 110                 iph = NULL;
 111
 112         if (iph == NULL) {
 113                 KMALLOC(iph, iphtable_t *);
 114                 if (iph == NULL) {
 115                         ipht_nomem[op->iplo_unit]++;
 116                         return ENOMEM;
 117                 }
 118                 err = COPYIN(op->iplo_struct, iph, sizeof(*iph));
 119                 if (err != 0) {
 120                         KFREE(iph);
 121                         return EFAULT;
 122                 }
 123         } else {
 124                 if ((iph->iph_flags & IPHASH_DELETE) == 0)
 125                         return EEXIST;
 126         }
 127
 128         if (iph->iph_unit != unit) {
 129                 if ((iph->iph_flags & IPHASH_DELETE) == 0) {
 130                         KFREE(iph);
 131                 }
 132                 return EINVAL;
 133         }
 134
 135         if ((op->iplo_arg & IPHASH_ANON) != 0) {
 136                 i = IPHASH_ANON;
 137                 do {
 138                         i++;
 139 #if defined(SNPRINTF) && defined(_KERNEL)
 140                         SNPRINTF(name, sizeof(name), "%u", i);
 141 #else
 142                         (void)sprintf(name, "%u", i);
 143 #endif
 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)
 148                                         break;
 149                 } while (oiph != NULL);
 150
 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;
 154         }
 155
 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) {
 161                                 KFREE(iph);
 162                         }
 163                         ipht_nomem[unit]++;
 164                         return ENOMEM;
 165                 }
 166
 167                 bzero((char *)iph->iph_table,
 168                       iph->iph_size * sizeof(*iph->iph_table));
 169                 iph->iph_masks = 0;
 170                 iph->iph_list = NULL;
 171
 172                 iph->iph_ref = 1;
 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;
 178
 179                 ipf_nhtables[unit]++;
 180         }
 181
 182         iph->iph_flags &= ~IPHASH_DELETE;
 183
 184         return 0;
 185 }
 186
 187
 188 /*
 189  */
 190 int fr_removehtable(unit, name)
 191 int unit;
 192 char *name;
 193 {
 194         iphtable_t *iph;
 195
 196         iph = fr_findhtable(unit, name);
 197         if (iph == NULL)
 198                 return ESRCH;
 199
 200         if (iph->iph_unit != unit) {
 201                 return EINVAL;
 202         }
 203
 204         if (iph->iph_ref != 0) {
 205                 (void) fr_clearhtable(iph);
 206                 iph->iph_flags |= IPHASH_DELETE;
 207                 return 0;
 208         }
 209
 210         fr_delhtable(iph);
 211
 212         return 0;
 213 }
 214
 215
 216 int fr_clearhtable(iph)
 217 iphtable_t *iph;
 218 {
 219         iphtent_t *ipe;
 220
 221         while ((ipe = iph->iph_list) != NULL)
 222                 if (fr_delhtent(iph, ipe) != 0)
 223                         return 1;
 224         return 0;
 225 }
 226
 227
 228 int fr_delhtable(iph)
 229 iphtable_t *iph;
 230 {
 231
 232         if (fr_clearhtable(iph) != 0)
 233                 return 1;
 234
 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;
 239
 240         ipf_nhtables[iph->iph_unit]--;
 241
 242         return fr_derefhtable(iph);
 243 }
 244
 245
 246 /*
 247  * Delete an entry from a hash table.
 248  */
 249 int fr_delhtent(iph, ipe)
 250 iphtable_t *iph;
 251 iphtent_t *ipe;
 252 {
 253
 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;
 258
 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;
 263
 264         switch (iph->iph_type & ~IPHASH_ANON)
 265         {
 266         case IPHASH_GROUPMAP :
 267                 if (ipe->ipe_group != NULL)
 268                         fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active);
 269                 break;
 270
 271         default :
 272                 ipe->ipe_ptr = NULL;
 273                 ipe->ipe_value = 0;
 274                 break;
 275         }
 276
 277         return fr_derefhtent(ipe);
 278 }
 279
 280
 281 int fr_derefhtable(iph)
 282 iphtable_t *iph;
 283 {
 284         int refs;
 285
 286         iph->iph_ref--;
 287         refs = iph->iph_ref;
 288
 289         if (iph->iph_ref == 0) {
 290                 KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table));
 291                 KFREE(iph);
 292         }
 293
 294         return refs;
 295 }
 296
 297
 298 int fr_derefhtent(ipe)
 299 iphtent_t *ipe;
 300 {
 301
 302         ipe->ipe_ref--;
 303         if (ipe->ipe_ref == 0) {
 304                 ipf_nhtnodes[ipe->ipe_unit]--;
 305
 306                 KFREE(ipe);
 307
 308                 return 0;
 309         }
 310
 311         return ipe->ipe_ref;
 312 }
 313
 314
 315 iphtable_t *fr_existshtable(unit, name)
 316 int unit;
 317 char *name;
 318 {
 319         iphtable_t *iph;
 320
 321         for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next)
 322                 if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0)
 323                         break;
 324         return iph;
 325 }
 326
 327
 328 iphtable_t *fr_findhtable(unit, name)
 329 int unit;
 330 char *name;
 331 {
 332         iphtable_t *iph;
 333
 334         iph = fr_existshtable(unit, name);
 335         if ((iph != NULL) && (iph->iph_flags & IPHASH_DELETE) == 0)
 336                 return iph;
 337
 338         return NULL;
 339 }
 340
 341
 342 size_t fr_flushhtable(op)
 343 iplookupflush_t *op;
 344 {
 345         iphtable_t *iph;
 346         size_t freed;
 347         int i;
 348
 349         freed = 0;
 350
 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) {
 355                                         freed++;
 356                                 } else {
 357                                         iph->iph_flags |= IPHASH_DELETE;
 358                                 }
 359                         }
 360                 }
 361         }
 362
 363         return freed;
 364 }
 365
 366
 367 /*
 368  * Add an entry to a hash table.
 369  */
 370 int fr_addhtent(iph, ipeo)
 371 iphtable_t *iph;
 372 iphtent_t *ipeo;
 373 {
 374         iphtent_t *ipe;
 375         u_int hv;
 376         int bits;
 377
 378         KMALLOC(ipe, iphtent_t *);
 379         if (ipe == NULL)
 380                 return -1;
 381
 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);
 387
 388         hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr,
 389                          iph->iph_size);
 390         ipe->ipe_ref = 1;
 391         ipe->ipe_hnext = iph->iph_table[hv];
 392         ipe->ipe_phnext = iph->iph_table + hv;
 393
 394         if (iph->iph_table[hv] != NULL)
 395                 iph->iph_table[hv]->ipe_phnext = &ipe->ipe_hnext;
 396         iph->iph_table[hv] = ipe;
 397
 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;
 402         iph->iph_list = ipe;
 403
 404         if ((bits >= 0) && (bits != 32))
 405                 iph->iph_masks |= 1 << bits;
 406
 407         switch (iph->iph_type & ~IPHASH_ANON)
 408         {
 409         case IPHASH_GROUPMAP :
 410                 ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL,
 411                                            iph->iph_flags, IPL_LOGIPF,
 412                                            fr_active);
 413                 break;
 414
 415         default :
 416                 ipe->ipe_ptr = NULL;
 417                 ipe->ipe_value = 0;
 418                 break;
 419         }
 420
 421         ipe->ipe_unit = iph->iph_unit;
 422         ipf_nhtnodes[ipe->ipe_unit]++;
 423
 424         return 0;
 425 }
 426
 427
 428 void *fr_iphmfindgroup(tptr, aptr)
 429 void *tptr, *aptr;
 430 {
 431         struct in_addr *addr;
 432         iphtable_t *iph;
 433         iphtent_t *ipe;
 434         void *rval;
 435
 436         READ_ENTER(&ip_poolrw);
 437         iph = tptr;
 438         addr = aptr;
 439
 440         ipe = fr_iphmfind(iph, addr);
 441         if (ipe != NULL)
 442                 rval = ipe->ipe_ptr;
 443         else
 444                 rval = NULL;
 445         RWLOCK_EXIT(&ip_poolrw);
 446         return rval;
 447 }
 448
 449
 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               */
 456 /*                                                                          */
 457 /* Search the hash table for a given address and return a search result.    */
 458 /* ------------------------------------------------------------------------ */
 459 int fr_iphmfindip(tptr, ipversion, aptr)
 460 void *tptr, *aptr;
 461 int ipversion;
 462 {
 463         struct in_addr *addr;
 464         iphtable_t *iph;
 465         iphtent_t *ipe;
 466         int rval;
 467
 468         if (ipversion != 4)
 469                 return -1;
 470
 471         if (tptr == NULL || aptr == NULL)
 472                 return -1;
 473
 474         iph = tptr;
 475         addr = aptr;
 476
 477         READ_ENTER(&ip_poolrw);
 478         ipe = fr_iphmfind(iph, addr);
 479         if (ipe != NULL)
 480                 rval = 0;
 481         else
 482                 rval = 1;
 483         RWLOCK_EXIT(&ip_poolrw);
 484         return rval;
 485 }
 486
 487
 488 /* Locks:  ip_poolrw */
 489 static iphtent_t *fr_iphmfind(iph, addr)
 490 iphtable_t *iph;
 491 struct in_addr *addr;
 492 {
 493         u_32_t hmsk, msk, ips;
 494         iphtent_t *ipe;
 495         u_int hv;
 496
 497         hmsk = iph->iph_masks;
 498         msk = 0xffffffff;
 499 maskloop:
 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) {
 505                         continue;
 506                 }
 507                 break;
 508         }
 509
 510         if ((ipe == NULL) && (hmsk != 0)) {
 511                 while (hmsk != 0) {
 512                         msk <<= 1;
 513                         if (hmsk & 0x80000000)
 514                                 break;
 515                         hmsk <<= 1;
 516                 }
 517                 if (hmsk != 0) {
 518                         hmsk <<= 1;
 519                         goto maskloop;
 520                 }
 521         }
 522         return ipe;
 523 }
 524
 525
 526 int fr_htable_getnext(token, ilp)
 527 ipftoken_t *token;
 528 ipflookupiter_t *ilp;
 529 {
 530         iphtent_t *node, zn, *nextnode;
 531         iphtable_t *iph, zp, *nextiph;
 532         int err;
 533
 534         err = 0;
 535         iph = NULL;
 536         node = NULL;
 537         nextiph = NULL;
 538         nextnode = NULL;
 539
 540         READ_ENTER(&ip_poolrw);
 541
 542         switch (ilp->ili_otype)
 543         {
 544         case IPFLOOKUPITER_LIST :
 545                 iph = token->ipt_data;
 546                 if (iph == NULL) {
 547                         nextiph = ipf_htables[(int)ilp->ili_unit];
 548                 } else {
 549                         nextiph = iph->iph_next;
 550                 }
 551
 552                 if (nextiph != NULL) {
 553                         ATOMIC_INC(nextiph->iph_ref);
 554                         if (nextiph->iph_next == NULL)
 555                                 token->ipt_alive = 0;
 556                 } else {
 557                         bzero((char *)&zp, sizeof(zp));
 558                         nextiph = &zp;
 559                 }
 560                 break;
 561
 562         case IPFLOOKUPITER_NODE :
 563                 node = token->ipt_data;
 564                 if (node == NULL) {
 565                         iph = fr_findhtable(ilp->ili_unit, ilp->ili_name);
 566                         if (iph == NULL)
 567                                 err = ESRCH;
 568                         else {
 569                                 nextnode = iph->iph_list;
 570                         }
 571                 } else {
 572                         nextnode = node->ipe_next;
 573                 }
 574
 575                 if (nextnode != NULL) {
 576                         ATOMIC_INC(nextnode->ipe_ref);
 577                         if (nextnode->ipe_next == NULL)
 578                                 token->ipt_alive = 0;
 579                 } else {
 580                         bzero((char *)&zn, sizeof(zn));
 581                         nextnode = &zn;
 582                 }
 583                 break;
 584         default :
 585                 err = EINVAL;
 586                 break;
 587         }
 588
 589         RWLOCK_EXIT(&ip_poolrw);
 590         if (err != 0)
 591                 return err;
 592
 593         switch (ilp->ili_otype)
 594         {
 595         case IPFLOOKUPITER_LIST :
 596                 if (iph != NULL) {
 597                         WRITE_ENTER(&ip_poolrw);
 598                         fr_derefhtable(iph);
 599                         RWLOCK_EXIT(&ip_poolrw);
 600                 }
 601                 token->ipt_data = nextiph;
 602                 err = COPYOUT(nextiph, ilp->ili_data, sizeof(*nextiph));
 603                 if (err != 0)
 604                         err = EFAULT;
 605                 break;
 606
 607         case IPFLOOKUPITER_NODE :
 608                 if (node != NULL) {
 609                         WRITE_ENTER(&ip_poolrw);
 610                         fr_derefhtent(node);
 611                         RWLOCK_EXIT(&ip_poolrw);
 612                 }
 613                 token->ipt_data = nextnode;
 614                 err = COPYOUT(nextnode, ilp->ili_data, sizeof(*nextnode));
 615                 if (err != 0)
 616                         err = EFAULT;
 617                 break;
 618         }
 619
 620         return err;
 621 }
 622
 623
 624 void fr_htable_iterderef(otype, unit, data)
 625 u_int otype;
 626 int unit;
 627 void *data;
 628 {
 629
 630         if (data == NULL)
 631                 return;
 632
 633         if (unit < 0 || unit > IPL_LOGMAX)
 634                 return;
 635
 636         switch (otype)
 637         {
 638         case IPFLOOKUPITER_LIST :
 639                 WRITE_ENTER(&ip_poolrw);
 640                 fr_derefhtable((iphtable_t *)data);
 641                 RWLOCK_EXIT(&ip_poolrw);
 642                 break;
 643
 644         case IPFLOOKUPITER_NODE :
 645                 WRITE_ENTER(&ip_poolrw);
 646                 fr_derefhtent((iphtent_t *)data);
 647                 RWLOCK_EXIT(&ip_poolrw);
 648                 break;
 649         default :
 650                 break;
 651         }
 652 }
 653
 654 #endif /* IPFILTER_LOOKUP */