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