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