winpcap/packetNtx/driver/normal_lookup.c

   1 /*
   2  * Copyright (c) 2001 - 2003
   3  * NetGroup, Politecnico di Torino (Italy)
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  * notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the Politecnico di Torino nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  *
  31  */
  32
  33 #ifdef WIN32
  34 #include "tme.h"
  35 #include "normal_lookup.h"
  36 #endif
  37
  38 #ifdef __FreeBSD__
  39
  40 #ifdef _KERNEL
  41 #include <net/tme/tme.h>
  42 #include <net/tme/normal_lookup.h>
  43 #else
  44 #include <tme/tme.h>
  45 #include <tme/normal_lookup.h>
  46 #endif
  47
  48 #endif
  49
  50
  51 /* lookup in the table, seen as an hash               */
  52 /* if not found, inserts an element                   */
  53 /* returns TME_TRUE if the entry is found or created, */
  54 /* returns TME_FALSE if no more blocks are available  */
  55 uint32 normal_lut_w_insert(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
  56 {
  57         uint32 i;
  58         uint32 tocs=0;
  59         uint32 *key32=(uint32*) key;
  60         uint32 shrinked_key=0;
  61         uint32 index;
  62         RECORD *records=(RECORD*)data->lut_base_address;
  63         uint8 *offset;
  64         uint32 key_len=data->key_len;
  65         /*the key is shrinked into a 32-bit value */
  66         for (i=0; i<key_len;i++)
  67                 shrinked_key^=key32[i];
  68     /*the first index in the table is calculated*/
  69         index=shrinked_key % data->lut_entries;
  70
  71         while (tocs<=data->filled_entries)
  72         {
  73
  74                 if (records[index].block==0)
  75                 {   /*creation of a new entry*/
  76
  77                         if (data->filled_blocks==data->shared_memory_blocks)
  78                         {
  79                                 /*no more free blocks*/
  80                                 GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
  81                                 data->last_found=NULL;
  82                                 return TME_FALSE;
  83                         }
  84
  85                         /*offset=absolute pointer to the block associated*/
  86                         /*with the newly created entry*/
  87                         offset=data->shared_memory_base_address+
  88                         data->block_size*data->filled_blocks;
  89
  90                         /*copy the key in the block*/
  91                         COPY_MEMORY(offset,key32,key_len*4);
  92                         GET_TIME((struct timeval *)(offset+4*key_len),time_ref);
  93                         /*assign the block relative offset to the entry, in NBO*/
  94                         SW_ULONG_ASSIGN(&records[index].block,offset-mem_ex->buffer);
  95
  96                         data->filled_blocks++;
  97
  98                         /*assign the exec function ID to the entry, in NBO*/
  99                         SW_ULONG_ASSIGN(&records[index].exec_fcn,data->default_exec);
 100                         data->filled_entries++;
 101
 102                         data->last_found=(uint8*)&records[index];
 103
 104                         return TME_TRUE;
 105                 }
 106                 /*offset contains the absolute pointer to the block*/
 107                 /*associated with the current entry */
 108                 offset=mem_ex->buffer+SW_ULONG_AT(&records[index].block,0);
 109
 110                 for (i=0; (i<key_len) && (key32[i]==ULONG_AT(offset,i*4)); i++);
 111
 112                 if (i==key_len)
 113                         {
 114                                 /*key in the block matches the one provided, right entry*/
 115                                 GET_TIME((struct timeval *)(offset+4*key_len),time_ref);
 116                                 data->last_found=(uint8*)&records[index];
 117                                 return TME_TRUE;
 118                         }
 119                 else
 120                 {
 121                         /* wrong entry, rehashing */
 122                         if (IS_DELETABLE(offset+key_len*4,data))
 123                         {
 124                                 ZERO_MEMORY(offset,data->block_size);
 125                                 COPY_MEMORY(offset,key32,key_len*4);
 126                                 SW_ULONG_ASSIGN(&records[index].exec_fcn,data->default_exec);
 127                                 GET_TIME((struct timeval*)(offset+key_len*4),time_ref);
 128                                 data->last_found=(uint8*)&records[index];
 129                                 return TME_TRUE;
 130                         }
 131                         else
 132                         {
 133                                 index=(index+data->rehashing_value) % data->lut_entries;
 134                                 tocs++;
 135                         }
 136                 }
 137         }
 138
 139         /* nothing found, last found= out of lut */
 140         GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
 141         data->last_found=NULL;
 142         return TME_FALSE;
 143
 144 }
 145
 146 /* lookup in the table, seen as an hash           */
 147 /* if not found, returns out of count entry index */
 148 /* returns TME_TRUE if the entry is found         */
 149 /* returns TME_FALSE if the entry is not found    */
 150 uint32 normal_lut_wo_insert(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
 151 {
 152         uint32 i;
 153         uint32 tocs=0;
 154         uint32 *key32=(uint32*) key;
 155         uint32 shrinked_key=0;
 156         uint32 index;
 157         RECORD *records=(RECORD*)data->lut_base_address;
 158         uint8 *offset;
 159         uint32 key_len=data->key_len;
 160         /*the key is shrinked into a 32-bit value */
 161         for (i=0; i<key_len;i++)
 162                 shrinked_key^=key32[i];
 163     /*the first index in the table is calculated*/
 164         index=shrinked_key % data->lut_entries;
 165
 166         while (tocs<=data->filled_entries)
 167         {
 168
 169                 if (records[index].block==0)
 170                 {   /*out of table, insertion is not allowed*/
 171                         GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
 172                         data->last_found=NULL;
 173                         return TME_FALSE;
 174                 }
 175                 /*offset contains the absolute pointer to the block*/
 176                 /*associated with the current entry */
 177
 178                 offset=mem_ex->buffer+SW_ULONG_AT(&records[index].block,0);
 179
 180                 for (i=0; (i<key_len) && (key32[i]==ULONG_AT(offset,i*4)); i++);
 181
 182                 if (i==key_len)
 183                         {
 184                                 /*key in the block matches the one provided, right entry*/
 185                                 GET_TIME((struct timeval *)(offset+4*key_len),time_ref);
 186                                 data->last_found=(uint8*)&records[index];
 187                                 return TME_TRUE;
 188                         }
 189                 else
 190                 {
 191                         /*wrong entry, rehashing*/
 192                         index=(index+data->rehashing_value) % data->lut_entries;
 193                         tocs++;
 194                 }
 195         }
 196
 197         /*nothing found, last found= out of lut*/
 198         GET_TIME((struct timeval *)(data->shared_memory_base_address+4*key_len),time_ref);
 199         data->last_found=NULL;
 200         return TME_FALSE;
 201
 202 }