ip_htable.c revision 153876
1145516Sdarrenr/* $FreeBSD: head/sys/contrib/ipfilter/netinet/ip_htable.c 153876 2005-12-30 11:32:23Z guido $ */ 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) 56153876Sguidostatic const char rcsid[] = "@(#)$Id: ip_htable.c,v 2.34.2.4 2005/11/13 15:38:37 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 *); 107147547Sdarrenr if (iph == NULL) { 108147547Sdarrenr ipht_nomem[op->iplo_unit]++; 109145516Sdarrenr return ENOMEM; 110147547Sdarrenr } 111145516Sdarrenr 112145516Sdarrenr err = COPYIN(op->iplo_struct, iph, sizeof(*iph)); 113145516Sdarrenr if (err != 0) { 114145516Sdarrenr KFREE(iph); 115145516Sdarrenr return EFAULT; 116145516Sdarrenr } 117145516Sdarrenr 118145516Sdarrenr unit = op->iplo_unit; 119145516Sdarrenr if (iph->iph_unit != unit) { 120145516Sdarrenr KFREE(iph); 121145516Sdarrenr return EINVAL; 122145516Sdarrenr } 123145516Sdarrenr 124145516Sdarrenr if ((op->iplo_arg & IPHASH_ANON) == 0) { 125145516Sdarrenr if (fr_findhtable(op->iplo_unit, op->iplo_name) != NULL) { 126145516Sdarrenr KFREE(iph); 127145516Sdarrenr return EEXIST; 128145516Sdarrenr } 129145516Sdarrenr } else { 130145516Sdarrenr i = IPHASH_ANON; 131145516Sdarrenr do { 132145516Sdarrenr i++; 133145516Sdarrenr#if defined(SNPRINTF) && defined(_KERNEL) 134145516Sdarrenr SNPRINTF(name, sizeof(name), "%u", i); 135145516Sdarrenr#else 136145516Sdarrenr (void)sprintf(name, "%u", i); 137145516Sdarrenr#endif 138145516Sdarrenr for (oiph = ipf_htables[unit]; oiph != NULL; 139145516Sdarrenr oiph = oiph->iph_next) 140145516Sdarrenr if (strncmp(oiph->iph_name, name, 141145516Sdarrenr sizeof(oiph->iph_name)) == 0) 142145516Sdarrenr break; 143145516Sdarrenr } while (oiph != NULL); 144153876Sguido 145145516Sdarrenr (void)strncpy(iph->iph_name, name, sizeof(iph->iph_name)); 146153876Sguido (void)strncpy(op->iplo_name, name, sizeof(op->iplo_name)); 147145516Sdarrenr iph->iph_type |= IPHASH_ANON; 148145516Sdarrenr } 149145516Sdarrenr 150145516Sdarrenr KMALLOCS(iph->iph_table, iphtent_t **, 151145516Sdarrenr iph->iph_size * sizeof(*iph->iph_table)); 152145516Sdarrenr if (iph->iph_table == NULL) { 153145516Sdarrenr KFREE(iph); 154145516Sdarrenr ipht_nomem[unit]++; 155145516Sdarrenr return ENOMEM; 156145516Sdarrenr } 157145516Sdarrenr 158145516Sdarrenr bzero((char *)iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 159145516Sdarrenr iph->iph_masks = 0; 160145516Sdarrenr 161145516Sdarrenr iph->iph_next = ipf_htables[unit]; 162145516Sdarrenr iph->iph_pnext = &ipf_htables[unit]; 163145516Sdarrenr if (ipf_htables[unit] != NULL) 164145516Sdarrenr ipf_htables[unit]->iph_pnext = &iph->iph_next; 165145516Sdarrenr ipf_htables[unit] = iph; 166145516Sdarrenr 167145516Sdarrenr ipf_nhtables[unit]++; 168145516Sdarrenr 169145516Sdarrenr return 0; 170145516Sdarrenr} 171145516Sdarrenr 172145516Sdarrenr 173145516Sdarrenr/* 174145516Sdarrenr */ 175145516Sdarrenrint fr_removehtable(op) 176145516Sdarrenriplookupop_t *op; 177145516Sdarrenr{ 178145516Sdarrenr iphtable_t *iph; 179145516Sdarrenr 180145516Sdarrenr 181145516Sdarrenr iph = fr_findhtable(op->iplo_unit, op->iplo_name); 182145516Sdarrenr if (iph == NULL) 183145516Sdarrenr return ESRCH; 184145516Sdarrenr 185145516Sdarrenr if (iph->iph_unit != op->iplo_unit) { 186145516Sdarrenr return EINVAL; 187145516Sdarrenr } 188145516Sdarrenr 189145516Sdarrenr if (iph->iph_ref != 0) { 190145516Sdarrenr return EBUSY; 191145516Sdarrenr } 192145516Sdarrenr 193145516Sdarrenr fr_delhtable(iph); 194145516Sdarrenr 195145516Sdarrenr return 0; 196145516Sdarrenr} 197145516Sdarrenr 198145516Sdarrenr 199145516Sdarrenrvoid fr_delhtable(iph) 200145516Sdarrenriphtable_t *iph; 201145516Sdarrenr{ 202145516Sdarrenr iphtent_t *ipe; 203145516Sdarrenr int i; 204145516Sdarrenr 205145516Sdarrenr for (i = 0; i < iph->iph_size; i++) 206145516Sdarrenr while ((ipe = iph->iph_table[i]) != NULL) 207145516Sdarrenr if (fr_delhtent(iph, ipe) != 0) 208145516Sdarrenr return; 209145516Sdarrenr 210145516Sdarrenr *iph->iph_pnext = iph->iph_next; 211145516Sdarrenr if (iph->iph_next != NULL) 212145516Sdarrenr iph->iph_next->iph_pnext = iph->iph_pnext; 213145516Sdarrenr 214145516Sdarrenr ipf_nhtables[iph->iph_unit]--; 215145516Sdarrenr 216145516Sdarrenr if (iph->iph_ref == 0) { 217145516Sdarrenr KFREES(iph->iph_table, iph->iph_size * sizeof(*iph->iph_table)); 218145516Sdarrenr KFREE(iph); 219145516Sdarrenr } 220145516Sdarrenr} 221145516Sdarrenr 222145516Sdarrenr 223145516Sdarrenrvoid fr_derefhtable(iph) 224145516Sdarrenriphtable_t *iph; 225145516Sdarrenr{ 226145516Sdarrenr iph->iph_ref--; 227145516Sdarrenr if (iph->iph_ref == 0) 228145516Sdarrenr fr_delhtable(iph); 229145516Sdarrenr} 230145516Sdarrenr 231145516Sdarrenr 232145516Sdarrenriphtable_t *fr_findhtable(unit, name) 233145516Sdarrenrint unit; 234145516Sdarrenrchar *name; 235145516Sdarrenr{ 236145516Sdarrenr iphtable_t *iph; 237145516Sdarrenr 238145516Sdarrenr for (iph = ipf_htables[unit]; iph != NULL; iph = iph->iph_next) 239145516Sdarrenr if (strncmp(iph->iph_name, name, sizeof(iph->iph_name)) == 0) 240145516Sdarrenr break; 241145516Sdarrenr return iph; 242145516Sdarrenr} 243145516Sdarrenr 244145516Sdarrenr 245145516Sdarrenrsize_t fr_flushhtable(op) 246145516Sdarrenriplookupflush_t *op; 247145516Sdarrenr{ 248145516Sdarrenr iphtable_t *iph; 249145516Sdarrenr size_t freed; 250145516Sdarrenr int i; 251145516Sdarrenr 252145516Sdarrenr freed = 0; 253145516Sdarrenr 254145516Sdarrenr for (i = 0; i <= IPL_LOGMAX; i++) { 255145516Sdarrenr if (op->iplf_unit == i || op->iplf_unit == IPL_LOGALL) { 256145516Sdarrenr while ((iph = ipf_htables[i]) != NULL) { 257145516Sdarrenr fr_delhtable(iph); 258145516Sdarrenr freed++; 259145516Sdarrenr } 260145516Sdarrenr } 261145516Sdarrenr } 262145516Sdarrenr 263145516Sdarrenr return freed; 264145516Sdarrenr} 265145516Sdarrenr 266145516Sdarrenr 267145516Sdarrenr/* 268145516Sdarrenr * Add an entry to a hash table. 269145516Sdarrenr */ 270145516Sdarrenrint fr_addhtent(iph, ipeo) 271145516Sdarrenriphtable_t *iph; 272145516Sdarrenriphtent_t *ipeo; 273145516Sdarrenr{ 274145516Sdarrenr iphtent_t *ipe; 275145516Sdarrenr u_int hv; 276145516Sdarrenr int bits; 277145516Sdarrenr 278145516Sdarrenr KMALLOC(ipe, iphtent_t *); 279145516Sdarrenr if (ipe == NULL) 280145516Sdarrenr return -1; 281145516Sdarrenr 282145516Sdarrenr bcopy((char *)ipeo, (char *)ipe, sizeof(*ipe)); 283145516Sdarrenr ipe->ipe_addr.in4_addr &= ipe->ipe_mask.in4_addr; 284145516Sdarrenr ipe->ipe_addr.in4_addr = ntohl(ipe->ipe_addr.in4_addr); 285145516Sdarrenr bits = count4bits(ipe->ipe_mask.in4_addr); 286145516Sdarrenr ipe->ipe_mask.in4_addr = ntohl(ipe->ipe_mask.in4_addr); 287145516Sdarrenr 288145516Sdarrenr hv = IPE_HASH_FN(ipe->ipe_addr.in4_addr, ipe->ipe_mask.in4_addr, 289145516Sdarrenr iph->iph_size); 290145516Sdarrenr ipe->ipe_ref = 0; 291145516Sdarrenr ipe->ipe_next = iph->iph_table[hv]; 292145516Sdarrenr ipe->ipe_pnext = iph->iph_table + hv; 293145516Sdarrenr 294145516Sdarrenr if (iph->iph_table[hv] != NULL) 295145516Sdarrenr iph->iph_table[hv]->ipe_pnext = &ipe->ipe_next; 296145516Sdarrenr iph->iph_table[hv] = ipe; 297145516Sdarrenr if ((bits >= 0) && (bits != 32)) 298145516Sdarrenr iph->iph_masks |= 1 << bits; 299145516Sdarrenr 300145516Sdarrenr switch (iph->iph_type & ~IPHASH_ANON) 301145516Sdarrenr { 302145516Sdarrenr case IPHASH_GROUPMAP : 303145516Sdarrenr ipe->ipe_ptr = fr_addgroup(ipe->ipe_group, NULL, 304145516Sdarrenr iph->iph_flags, IPL_LOGIPF, 305145516Sdarrenr fr_active); 306145516Sdarrenr break; 307145516Sdarrenr 308145516Sdarrenr default : 309145516Sdarrenr ipe->ipe_ptr = NULL; 310145516Sdarrenr ipe->ipe_value = 0; 311145516Sdarrenr break; 312145516Sdarrenr } 313145516Sdarrenr 314145516Sdarrenr ipf_nhtnodes[iph->iph_unit]++; 315145516Sdarrenr 316145516Sdarrenr return 0; 317145516Sdarrenr} 318145516Sdarrenr 319145516Sdarrenr 320145516Sdarrenr/* 321145516Sdarrenr * Delete an entry from a hash table. 322145516Sdarrenr */ 323145516Sdarrenrint fr_delhtent(iph, ipe) 324145516Sdarrenriphtable_t *iph; 325145516Sdarrenriphtent_t *ipe; 326145516Sdarrenr{ 327145516Sdarrenr 328145516Sdarrenr if (ipe->ipe_ref != 0) 329145516Sdarrenr return EBUSY; 330145516Sdarrenr 331145516Sdarrenr 332145516Sdarrenr *ipe->ipe_pnext = ipe->ipe_next; 333145516Sdarrenr if (ipe->ipe_next != NULL) 334145516Sdarrenr ipe->ipe_next->ipe_pnext = ipe->ipe_pnext; 335145516Sdarrenr 336145516Sdarrenr switch (iph->iph_type & ~IPHASH_ANON) 337145516Sdarrenr { 338145516Sdarrenr case IPHASH_GROUPMAP : 339145516Sdarrenr if (ipe->ipe_group != NULL) 340145516Sdarrenr fr_delgroup(ipe->ipe_group, IPL_LOGIPF, fr_active); 341145516Sdarrenr break; 342145516Sdarrenr 343145516Sdarrenr default : 344145516Sdarrenr ipe->ipe_ptr = NULL; 345145516Sdarrenr ipe->ipe_value = 0; 346145516Sdarrenr break; 347145516Sdarrenr } 348145516Sdarrenr 349145516Sdarrenr KFREE(ipe); 350145516Sdarrenr 351145516Sdarrenr ipf_nhtnodes[iph->iph_unit]--; 352145516Sdarrenr 353145516Sdarrenr return 0; 354145516Sdarrenr} 355145516Sdarrenr 356145516Sdarrenr 357145516Sdarrenrvoid *fr_iphmfindgroup(tptr, aptr) 358145516Sdarrenrvoid *tptr, *aptr; 359145516Sdarrenr{ 360145516Sdarrenr struct in_addr *addr; 361145516Sdarrenr iphtable_t *iph; 362145516Sdarrenr iphtent_t *ipe; 363145516Sdarrenr void *rval; 364145516Sdarrenr 365145516Sdarrenr READ_ENTER(&ip_poolrw); 366145516Sdarrenr iph = tptr; 367145516Sdarrenr addr = aptr; 368145516Sdarrenr 369145516Sdarrenr ipe = fr_iphmfind(iph, addr); 370145516Sdarrenr if (ipe != NULL) 371145516Sdarrenr rval = ipe->ipe_ptr; 372145516Sdarrenr else 373145516Sdarrenr rval = NULL; 374145516Sdarrenr RWLOCK_EXIT(&ip_poolrw); 375145516Sdarrenr return rval; 376145516Sdarrenr} 377145516Sdarrenr 378145516Sdarrenr 379145516Sdarrenr/* ------------------------------------------------------------------------ */ 380145516Sdarrenr/* Function: fr_iphmfindip */ 381145516Sdarrenr/* Returns: int - 0 == +ve match, -1 == error, 1 == -ve/no match */ 382145516Sdarrenr/* Parameters: tptr(I) - pointer to the pool to search */ 383145516Sdarrenr/* version(I) - IP protocol version (4 or 6) */ 384145516Sdarrenr/* aptr(I) - pointer to address information */ 385145516Sdarrenr/* */ 386145516Sdarrenr/* Search the hash table for a given address and return a search result. */ 387145516Sdarrenr/* ------------------------------------------------------------------------ */ 388145516Sdarrenrint fr_iphmfindip(tptr, version, aptr) 389145516Sdarrenrvoid *tptr, *aptr; 390145516Sdarrenrint version; 391145516Sdarrenr{ 392145516Sdarrenr struct in_addr *addr; 393145516Sdarrenr iphtable_t *iph; 394145516Sdarrenr iphtent_t *ipe; 395145516Sdarrenr int rval; 396145516Sdarrenr 397145516Sdarrenr if (version != 4) 398145516Sdarrenr return -1; 399145516Sdarrenr 400145516Sdarrenr if (tptr == NULL || aptr == NULL) 401145516Sdarrenr return -1; 402145516Sdarrenr 403145516Sdarrenr iph = tptr; 404145516Sdarrenr addr = aptr; 405145516Sdarrenr 406145516Sdarrenr READ_ENTER(&ip_poolrw); 407145516Sdarrenr ipe = fr_iphmfind(iph, addr); 408145516Sdarrenr if (ipe != NULL) 409145516Sdarrenr rval = 0; 410145516Sdarrenr else 411145516Sdarrenr rval = 1; 412145516Sdarrenr RWLOCK_EXIT(&ip_poolrw); 413145516Sdarrenr return rval; 414145516Sdarrenr} 415145516Sdarrenr 416145516Sdarrenr 417145516Sdarrenr/* Locks: ip_poolrw */ 418145516Sdarrenrstatic iphtent_t *fr_iphmfind(iph, addr) 419145516Sdarrenriphtable_t *iph; 420145516Sdarrenrstruct in_addr *addr; 421145516Sdarrenr{ 422145516Sdarrenr u_32_t hmsk, msk, ips; 423145516Sdarrenr iphtent_t *ipe; 424145516Sdarrenr u_int hv; 425145516Sdarrenr 426145516Sdarrenr hmsk = iph->iph_masks; 427145516Sdarrenr msk = 0xffffffff; 428145516Sdarrenrmaskloop: 429145516Sdarrenr ips = ntohl(addr->s_addr) & msk; 430145516Sdarrenr hv = IPE_HASH_FN(ips, msk, iph->iph_size); 431145516Sdarrenr for (ipe = iph->iph_table[hv]; (ipe != NULL); ipe = ipe->ipe_next) { 432145516Sdarrenr if (ipe->ipe_mask.in4_addr != msk || 433145516Sdarrenr ipe->ipe_addr.in4_addr != ips) { 434145516Sdarrenr continue; 435145516Sdarrenr } 436145516Sdarrenr break; 437145516Sdarrenr } 438145516Sdarrenr 439145516Sdarrenr if ((ipe == NULL) && (hmsk != 0)) { 440145516Sdarrenr while (hmsk != 0) { 441145516Sdarrenr msk <<= 1; 442145516Sdarrenr if (hmsk & 0x80000000) 443145516Sdarrenr break; 444145516Sdarrenr hmsk <<= 1; 445145516Sdarrenr } 446145516Sdarrenr if (hmsk != 0) { 447145516Sdarrenr hmsk <<= 1; 448145516Sdarrenr goto maskloop; 449145516Sdarrenr } 450145516Sdarrenr } 451145516Sdarrenr return ipe; 452145516Sdarrenr} 453145516Sdarrenr 454145516Sdarrenr#endif /* IPFILTER_LOOKUP */ 455