sys/dist/ipf/netinet/ip_htable.c

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