ip_htable.c revision 145516
1145516Sdarrenr/* $FreeBSD: vendor-sys/ipfilter/dist/sys/contrib/ipfilter/netinet/ip_htable.c 145516 2005-04-25 18:15:41Z darrenr $ */ 2145516Sdarrenr 3145516Sdarrenr/* 4145516Sdarrenr * Copyright (C) 1993-2001, 2003 by Darren Reed. 5145516Sdarrenr * 6145516Sdarrenr * See the IPFILTER.LICENCE file for details on licencing. 7145516Sdarrenr */ 8145516Sdarrenr#if defined(KERNEL) || defined(_KERNEL) 9145516Sdarrenr# undef KERNEL 10145516Sdarrenr# undef _KERNEL 11145516Sdarrenr# define KERNEL 1 12145516Sdarrenr# define _KERNEL 1 13145516Sdarrenr#endif 14145516Sdarrenr#include <sys/param.h> 15145516Sdarrenr#include <sys/types.h> 16145516Sdarrenr#include <sys/errno.h> 17145516Sdarrenr#include <sys/time.h> 18145516Sdarrenr#include <sys/file.h> 19145516Sdarrenr#if !defined(_KERNEL) 20145516Sdarrenr# include <stdlib.h> 21145516Sdarrenr# include <string.h> 22145516Sdarrenr# define _KERNEL 23145516Sdarrenr# ifdef __OpenBSD__ 24145516Sdarrenrstruct file; 25145516Sdarrenr# endif 26145516Sdarrenr# include <sys/uio.h> 27145516Sdarrenr# undef _KERNEL 28145516Sdarrenr#endif 29145516Sdarrenr#include <sys/socket.h> 30145516Sdarrenr#if defined(__FreeBSD_version) && (__FreeBSD_version >= 300000) 31145516Sdarrenr# include <sys/malloc.h> 32145516Sdarrenr#endif 33145516Sdarrenr#if defined(__FreeBSD__) 34145516Sdarrenr# include <sys/cdefs.h> 35145516Sdarrenr# include <sys/proc.h> 36145516Sdarrenr#endif 37145516Sdarrenr#if !defined(__svr4__) && !defined(__SVR4) && !defined(__hpux) && \ 38145516Sdarrenr !defined(linux) 39145516Sdarrenr# include <sys/mbuf.h> 40145516Sdarrenr#endif 41145516Sdarrenr#if defined(_KERNEL) 42145516Sdarrenr# include <sys/systm.h> 43145516Sdarrenr#else 44145516Sdarrenr# include <stdio.h> 45145516Sdarrenr#endif 46145516Sdarrenr#include <netinet/in.h> 47145516Sdarrenr#include <net/if.h> 48145516Sdarrenr 49145516Sdarrenr#include "netinet/ip_compat.h" 50145516Sdarrenr#include "netinet/ip_fil.h" 51145516Sdarrenr#include "netinet/ip_lookup.h" 52145516Sdarrenr#include "netinet/ip_htable.h" 53145516Sdarrenr/* END OF INCLUDES */ 54145516Sdarrenr 55145516Sdarrenr#if !defined(lint) 56145516Sdarrenrstatic const char rcsid[] = "@(#)Id: ip_htable.c,v 2.34.2.2 2004/10/17 15:49:15 darrenr Exp"; 57145516Sdarrenr#endif 58145516Sdarrenr 59145516Sdarrenr#ifdef IPFILTER_LOOKUP 60145516Sdarrenrstatic iphtent_t *fr_iphmfind __P((iphtable_t *, struct in_addr *)); 61145516Sdarrenrstatic u_long ipht_nomem[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 }; 62145516Sdarrenrstatic u_long ipf_nhtables[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 }; 63145516Sdarrenrstatic u_long ipf_nhtnodes[IPL_LOGSIZE] = { 0, 0, 0, 0, 0, 0, 0, 0 }; 64145516Sdarrenr 65145516Sdarrenriphtable_t *ipf_htables[IPL_LOGSIZE] = { NULL, NULL, NULL, NULL, 66145516Sdarrenr NULL, NULL, NULL, NULL }; 67145516Sdarrenr 68145516Sdarrenr 69145516Sdarrenrvoid fr_htable_unload() 70145516Sdarrenr{ 71145516Sdarrenr iplookupflush_t fop; 72145516Sdarrenr 73145516Sdarrenr fop.iplf_unit = IPL_LOGALL; 74145516Sdarrenr (void)fr_flushhtable(&fop); 75145516Sdarrenr} 76145516Sdarrenr 77145516Sdarrenr 78145516Sdarrenrint fr_gethtablestat(op) 79145516Sdarrenriplookupop_t *op; 80145516Sdarrenr{ 81145516Sdarrenr iphtstat_t stats; 82145516Sdarrenr 83145516Sdarrenr if (op->iplo_size != sizeof(stats)) 84145516Sdarrenr return EINVAL; 85145516Sdarrenr 86145516Sdarrenr stats.iphs_tables = ipf_htables[op->iplo_unit]; 87145516Sdarrenr stats.iphs_numtables = ipf_nhtables[op->iplo_unit]; 88145516Sdarrenr stats.iphs_numnodes = ipf_nhtnodes[op->iplo_unit]; 89145516Sdarrenr stats.iphs_nomem = ipht_nomem[op->iplo_unit]; 90145516Sdarrenr 91145516Sdarrenr return COPYOUT(&stats, op->iplo_struct, sizeof(stats)); 92145516Sdarrenr 93145516Sdarrenr} 94145516Sdarrenr 95145516Sdarrenr 96145516Sdarrenr/* 97145516Sdarrenr * Create a new hash table using the template passed. 98145516Sdarrenr */ 99145516Sdarrenrint fr_newhtable(op) 100145516Sdarrenriplookupop_t *op; 101145516Sdarrenr{ 102145516Sdarrenr iphtable_t *iph, *oiph; 103145516Sdarrenr char name[FR_GROUPLEN]; 104145516Sdarrenr int err, i, unit; 105145516Sdarrenr 106145516Sdarrenr KMALLOC(iph, iphtable_t *); 107145516Sdarrenr if (iph == NULL) 108145516Sdarrenr return ENOMEM; 109145516Sdarrenr 110145516Sdarrenr err = COPYIN(op->iplo_struct, iph, sizeof(*iph)); 111145516Sdarrenr if (err != 0) { 112145516Sdarrenr KFREE(iph); 113145516Sdarrenr return EFAULT; 114145516Sdarrenr } 115145516Sdarrenr 116145516Sdarrenr unit = op->iplo_unit; 117145516Sdarrenr if (iph->iph_unit != unit) { 118145516Sdarrenr KFREE(iph); 119145516Sdarrenr return EINVAL; 120145516Sdarrenr } 121145516Sdarrenr 122145516Sdarrenr if ((op->iplo_arg & IPHASH_ANON) == 0) { 123145516Sdarrenr if (fr_findhtable(op->iplo_unit, op->iplo_name) != NULL) { 124145516Sdarrenr KFREE(iph); 125145516Sdarrenr return EEXIST; 126145516Sdarrenr } 127145516Sdarrenr } else { 128145516Sdarrenr i = IPHASH_ANON; 129145516Sdarrenr do { 130145516Sdarrenr i++; 131145516Sdarrenr#if defined(SNPRINTF) && defined(_KERNEL) 132145516Sdarrenr SNPRINTF(name, sizeof(name), "%u", i); 133145516Sdarrenr#else 134145516Sdarrenr (void)sprintf(name, "%u", i); 135145516Sdarrenr#endif 136145516Sdarrenr for (oiph = ipf_htables[unit]; oiph != NULL; 137145516Sdarrenr oiph = oiph->iph_next) 138145516Sdarrenr if (strncmp(oiph->iph_name, name, 139145516Sdarrenr sizeof(oiph->iph_name)) == 0) 140145516Sdarrenr break; 141145516Sdarrenr } while (oiph != NULL); 142145516Sdarrenr (void)strncpy(iph->iph_name, name, sizeof(iph->iph_name)); 143145516Sdarrenr err = COPYOUT(iph, op->iplo_struct, sizeof(*iph)); 144145516Sdarrenr if (err != 0) { 145145516Sdarrenr KFREE(iph); 146145516Sdarrenr return EFAULT; 147145516Sdarrenr } 148145516Sdarrenr iph->iph_type |= IPHASH_ANON; 149145516Sdarrenr } 150145516Sdarrenr 151145516Sdarrenr KMALLOCS(iph->iph_table, iphtent_t **, 152145516Sdarrenr iph->iph_size * sizeof(*iph->iph_table)); 153145516Sdarrenr if (iph->iph_table == NULL) { 154145516Sdarrenr KFREE(iph); 155145516Sdarrenr ipht_nomem[unit]++; 156145516Sdarrenr return ENOMEM; 157145516Sdarrenr } 158145516Sdarrenr 159145516Sdarrenr bzero((char *)iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 160145516Sdarrenr iph->iph_masks = 0; 161145516Sdarrenr 162145516Sdarrenr iph->iph_next = ipf_htables[unit]; 163145516Sdarrenr iph->iph_pnext = &ipf_htables[unit]; 164145516Sdarrenr if (ipf_htables[unit] != NULL) 165145516Sdarrenr ipf_htables[unit]->iph_pnext = &iph->iph_next; 166145516Sdarrenr ipf_htables[unit] = iph; 167145516Sdarrenr 168145516Sdarrenr ipf_nhtables[unit]++; 169145516Sdarrenr 170145516Sdarrenr return 0; 171145516Sdarrenr} 172145516Sdarrenr 173145516Sdarrenr 174145516Sdarrenr/* 175145516Sdarrenr */ 176145516Sdarrenrint fr_removehtable(op) 177145516Sdarrenriplookupop_t *op; 178145516Sdarrenr{ 179145516Sdarrenr iphtable_t *iph; 180145516Sdarrenr 181145516Sdarrenr 182145516Sdarrenr iph = fr_findhtable(op->iplo_unit, op->iplo_name); 183145516Sdarrenr if (iph == NULL) 184145516Sdarrenr return ESRCH; 185145516Sdarrenr 186145516Sdarrenr if (iph->iph_unit != op->iplo_unit) { 187145516Sdarrenr return EINVAL; 188145516Sdarrenr } 189145516Sdarrenr 190145516Sdarrenr if (iph->iph_ref != 0) { 191145516Sdarrenr return EBUSY; 192145516Sdarrenr } 193145516Sdarrenr 194145516Sdarrenr fr_delhtable(iph); 195145516Sdarrenr 196145516Sdarrenr return 0; 197145516Sdarrenr} 198145516Sdarrenr 199145516Sdarrenr 200145516Sdarrenrvoid fr_delhtable(iph) 201145516Sdarrenriphtable_t *iph; 202145516Sdarrenr{ 203145516Sdarrenr iphtent_t *ipe; 204145516Sdarrenr int i; 205145516Sdarrenr 206145516Sdarrenr for (i = 0; i < iph->iph_size; i++) 207145516Sdarrenr while ((ipe = iph->iph_table[i]) != NULL) 208145516Sdarrenr if (fr_delhtent(iph, ipe) != 0) 209145516Sdarrenr return; 210145516Sdarrenr 211145516Sdarrenr *iph->iph_pnext = iph->iph_next; 212145516Sdarrenr if (iph->iph_next != NULL) 213145516Sdarrenr iph->iph_next->iph_pnext = iph->iph_pnext; 214145516Sdarrenr 215145516Sdarrenr ipf_nhtables[iph->iph_unit]--; 216145516Sdarrenr 217145516Sdarrenr if (iph->iph_ref == 0) { 218145516Sdarrenr KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 219145516Sdarrenr KFREE(iph); 220145516Sdarrenr } 221145516Sdarrenr} 222145516Sdarrenr 223145516Sdarrenr 224145516Sdarrenrvoid fr_derefhtable(iph) 225145516Sdarrenriphtable_t *iph; 226145516Sdarrenr{ 227145516Sdarrenr iph->iph_ref--; 228145516Sdarrenr if (iph->iph_ref == 0) 229145516Sdarrenr fr_delhtable(iph); 230145516Sdarrenr} 231145516Sdarrenr 232145516Sdarrenr 233145516Sdarrenriphtable_t *fr_findhtable(unit, name) 234145516Sdarrenrint unit; 235145516Sdarrenrchar *name; 236145516Sdarrenr{ 237145516Sdarrenr iphtable_t *iph; 238145516Sdarrenr 239145516Sdarrenr for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next) 240145516Sdarrenr if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0) 241145516Sdarrenr break; 242145516Sdarrenr return iph; 243145516Sdarrenr} 244145516Sdarrenr 245145516Sdarrenr 246145516Sdarrenrsize_t fr_flushhtable(op) 247145516Sdarrenriplookupflush_t *op; 248145516Sdarrenr{ 249145516Sdarrenr iphtable_t *iph; 250145516Sdarrenr size_t freed; 251145516Sdarrenr int i; 252145516Sdarrenr 253145516Sdarrenr freed = 0; 254145516Sdarrenr 255145516Sdarrenr for (i = 0; i <= IPL_LOGMAX; i++) { 256145516Sdarrenr if (op->iplf_unit == i || op->iplf_unit == IPL_LOGALL) { 257145516Sdarrenr while ((iph = ipf_htables[i]) != NULL) { 258145516Sdarrenr fr_delhtable(iph); 259145516Sdarrenr freed++; 260145516Sdarrenr } 261145516Sdarrenr } 262145516Sdarrenr } 263145516Sdarrenr 264145516Sdarrenr return freed; 265145516Sdarrenr} 266145516Sdarrenr 267145516Sdarrenr 268145516Sdarrenr/* 269145516Sdarrenr * Add an entry to a hash table. 270145516Sdarrenr */ 271145516Sdarrenrint fr_addhtent(iph, ipeo) 272145516Sdarrenriphtable_t *iph; 273145516Sdarrenriphtent_t *ipeo; 274145516Sdarrenr{ 275145516Sdarrenr iphtent_t *ipe; 276145516Sdarrenr u_int hv; 277145516Sdarrenr int bits; 278145516Sdarrenr 279145516Sdarrenr KMALLOC(ipe, iphtent_t *); 280145516Sdarrenr if (ipe == NULL) 281145516Sdarrenr return -1; 282145516Sdarrenr 283145516Sdarrenr bcopy((char *)ipeo, (char *)ipe, sizeof(*ipe)); 284145516Sdarrenr ipe->ipe_addr.in4_addr &= ipe->ipe_mask.in4_addr; 285145516Sdarrenr ipe->ipe_addr.in4_addr = ntohl(ipe->ipe_addr.in4_addr); 286145516Sdarrenr bits = count4bits(ipe->ipe_mask.in4_addr); 287145516Sdarrenr ipe->ipe_mask.in4_addr = ntohl(ipe->ipe_mask.in4_addr); 288145516Sdarrenr 289145516Sdarrenr hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr, 290145516Sdarrenr iph->iph_size); 291145516Sdarrenr ipe->ipe_ref = 0; 292145516Sdarrenr ipe->ipe_next = iph->iph_table[hv]; 293145516Sdarrenr ipe->ipe_pnext = iph->iph_table + hv; 294145516Sdarrenr 295145516Sdarrenr if (iph->iph_table[hv] != NULL) 296145516Sdarrenr iph->iph_table[hv]->ipe_pnext = &ipe->ipe_next; 297145516Sdarrenr iph->iph_table[hv] = ipe; 298145516Sdarrenr if ((bits >= 0) && (bits != 32)) 299145516Sdarrenr iph->iph_masks |= 1 << bits; 300145516Sdarrenr 301145516Sdarrenr switch (iph->iph_type & ~IPHASH_ANON) 302145516Sdarrenr { 303145516Sdarrenr case IPHASH_GROUPMAP : 304145516Sdarrenr ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL, 305145516Sdarrenr iph->iph_flags, IPL_LOGIPF, 306145516Sdarrenr fr_active); 307145516Sdarrenr break; 308145516Sdarrenr 309145516Sdarrenr default : 310145516Sdarrenr ipe->ipe_ptr = NULL; 311145516Sdarrenr ipe->ipe_value = 0; 312145516Sdarrenr break; 313145516Sdarrenr } 314145516Sdarrenr 315145516Sdarrenr ipf_nhtnodes[iph->iph_unit]++; 316145516Sdarrenr 317145516Sdarrenr return 0; 318145516Sdarrenr} 319145516Sdarrenr 320145516Sdarrenr 321145516Sdarrenr/* 322145516Sdarrenr * Delete an entry from a hash table. 323145516Sdarrenr */ 324145516Sdarrenrint fr_delhtent(iph, ipe) 325145516Sdarrenriphtable_t *iph; 326145516Sdarrenriphtent_t *ipe; 327145516Sdarrenr{ 328145516Sdarrenr 329145516Sdarrenr if (ipe->ipe_ref != 0) 330145516Sdarrenr return EBUSY; 331145516Sdarrenr 332145516Sdarrenr 333145516Sdarrenr *ipe->ipe_pnext = ipe->ipe_next; 334145516Sdarrenr if (ipe->ipe_next != NULL) 335145516Sdarrenr ipe->ipe_next->ipe_pnext = ipe->ipe_pnext; 336145516Sdarrenr 337145516Sdarrenr switch (iph->iph_type & ~IPHASH_ANON) 338145516Sdarrenr { 339145516Sdarrenr case IPHASH_GROUPMAP : 340145516Sdarrenr if (ipe->ipe_group != NULL) 341145516Sdarrenr fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active); 342145516Sdarrenr break; 343145516Sdarrenr 344145516Sdarrenr default : 345145516Sdarrenr ipe->ipe_ptr = NULL; 346145516Sdarrenr ipe->ipe_value = 0; 347145516Sdarrenr break; 348145516Sdarrenr } 349145516Sdarrenr 350145516Sdarrenr KFREE(ipe); 351145516Sdarrenr 352145516Sdarrenr ipf_nhtnodes[iph->iph_unit]--; 353145516Sdarrenr 354145516Sdarrenr return 0; 355145516Sdarrenr} 356145516Sdarrenr 357145516Sdarrenr 358145516Sdarrenrvoid *fr_iphmfindgroup(tptr, aptr) 359145516Sdarrenrvoid *tptr, *aptr; 360145516Sdarrenr{ 361145516Sdarrenr struct in_addr *addr; 362145516Sdarrenr iphtable_t *iph; 363145516Sdarrenr iphtent_t *ipe; 364145516Sdarrenr void *rval; 365145516Sdarrenr 366145516Sdarrenr READ_ENTER(&ip_poolrw); 367145516Sdarrenr iph = tptr; 368145516Sdarrenr addr = aptr; 369145516Sdarrenr 370145516Sdarrenr ipe = fr_iphmfind(iph, addr); 371145516Sdarrenr if (ipe != NULL) 372145516Sdarrenr rval = ipe->ipe_ptr; 373145516Sdarrenr else 374145516Sdarrenr rval = NULL; 375145516Sdarrenr RWLOCK_EXIT(&ip_poolrw); 376145516Sdarrenr return rval; 377145516Sdarrenr} 378145516Sdarrenr 379145516Sdarrenr 380145516Sdarrenr/* ------------------------------------------------------------------------ */ 381145516Sdarrenr/* Function: fr_iphmfindip */ 382145516Sdarrenr/* Returns: int - 0 == +ve match, -1 == error, 1 == -ve/no match */ 383145516Sdarrenr/* Parameters: tptr(I) - pointer to the pool to search */ 384145516Sdarrenr/* version(I) - IP protocol version (4 or 6) */ 385145516Sdarrenr/* aptr(I) - pointer to address information */ 386145516Sdarrenr/* */ 387145516Sdarrenr/* Search the hash table for a given address and return a search result. */ 388145516Sdarrenr/* ------------------------------------------------------------------------ */ 389145516Sdarrenrint fr_iphmfindip(tptr, version, aptr) 390145516Sdarrenrvoid *tptr, *aptr; 391145516Sdarrenrint version; 392145516Sdarrenr{ 393145516Sdarrenr struct in_addr *addr; 394145516Sdarrenr iphtable_t *iph; 395145516Sdarrenr iphtent_t *ipe; 396145516Sdarrenr int rval; 397145516Sdarrenr 398145516Sdarrenr if (version != 4) 399145516Sdarrenr return -1; 400145516Sdarrenr 401145516Sdarrenr if (tptr == NULL || aptr == NULL) 402145516Sdarrenr return -1; 403145516Sdarrenr 404145516Sdarrenr iph = tptr; 405145516Sdarrenr addr = aptr; 406145516Sdarrenr 407145516Sdarrenr READ_ENTER(&ip_poolrw); 408145516Sdarrenr ipe = fr_iphmfind(iph, addr); 409145516Sdarrenr if (ipe != NULL) 410145516Sdarrenr rval = 0; 411145516Sdarrenr else 412145516Sdarrenr rval = 1; 413145516Sdarrenr RWLOCK_EXIT(&ip_poolrw); 414145516Sdarrenr return rval; 415145516Sdarrenr} 416145516Sdarrenr 417145516Sdarrenr 418145516Sdarrenr/* Locks: ip_poolrw */ 419145516Sdarrenrstatic iphtent_t *fr_iphmfind(iph, addr) 420145516Sdarrenriphtable_t *iph; 421145516Sdarrenrstruct in_addr *addr; 422145516Sdarrenr{ 423145516Sdarrenr u_32_t hmsk, msk, ips; 424145516Sdarrenr iphtent_t *ipe; 425145516Sdarrenr u_int hv; 426145516Sdarrenr 427145516Sdarrenr hmsk = iph->iph_masks; 428145516Sdarrenr msk = 0xffffffff; 429145516Sdarrenrmaskloop: 430145516Sdarrenr ips = ntohl(addr->s_addr) & msk; 431145516Sdarrenr hv = IPE_HASH_FN(ips, msk, iph->iph_size); 432145516Sdarrenr for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_next) { 433145516Sdarrenr if (ipe->ipe_mask.in4_addr != msk || 434145516Sdarrenr ipe->ipe_addr.in4_addr != ips) { 435145516Sdarrenr continue; 436145516Sdarrenr } 437145516Sdarrenr break; 438145516Sdarrenr } 439145516Sdarrenr 440145516Sdarrenr if ((ipe == NULL) && (hmsk != 0)) { 441145516Sdarrenr while (hmsk != 0) { 442145516Sdarrenr msk <<= 1; 443145516Sdarrenr if (hmsk & 0x80000000) 444145516Sdarrenr break; 445145516Sdarrenr hmsk <<= 1; 446145516Sdarrenr } 447145516Sdarrenr if (hmsk != 0) { 448145516Sdarrenr hmsk <<= 1; 449145516Sdarrenr goto maskloop; 450145516Sdarrenr } 451145516Sdarrenr } 452145516Sdarrenr return ipe; 453145516Sdarrenr} 454145516Sdarrenr 455145516Sdarrenr#endif /* IPFILTER_LOOKUP */ 456