drivers/net/packet/bucket_lookup.c

   1 /*
   2  * Copyright (c) 2001
   3  *      Politecnico di Torino.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that: (1) source code distributions
   7  * retain the above copyright notice and this paragraph in its entirety, (2)
   8  * distributions including binary code include the above copyright notice and
   9  * this paragraph in its entirety in the documentation or other materials
  10  * provided with the distribution, and (3) all advertising materials mentioning
  11  * features or use of this software display the following acknowledgement:
  12  * ``This product includes software developed by the Politecnico
  13  * di Torino, and its contributors.'' Neither the name of
  14  * the University nor the names of its contributors may be used to endorse
  15  * or promote products derived from this software without specific prior
  16  * written permission.
  17  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20  */
  21
  22 #ifdef WIN32
  23 #include "tme.h"
  24 #include "bucket_lookup.h"
  25 #endif
  26
  27 #ifdef __FreeBSD__
  28
  29 #ifdef _KERNEL
  30 #include <net/tme/tme.h>
  31 #include <net/tme/bucket_lookup.h>
  32 #else
  33 #include <tme/tme.h>
  34 #include <tme/bucket_lookup.h>
  35 #endif
  36
  37 #endif
  38
  39
  40
  41 /* the key is represented by the initial and final value */
  42 /* of the bucket. At the moment bucket_lookup is able to */
  43 /* manage values of 16, 32 bits.                         */
  44 uint32 bucket_lookup(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
  45 {
  46         uint32 value;
  47         uint32 i,j;
  48         int found=-1;
  49         uint32 blocks;
  50         uint32 block_size;
  51         uint8 *temp;
  52         if ((data->key_len!=1)&&  /*16 bit value*/
  53                 (data->key_len!=2))   /*32 bit value*/
  54                 return TME_ERROR;
  55
  56         /*32 bit values*/
  57         blocks=data->filled_blocks-1;
  58         block_size=data->block_size;
  59         i=blocks/2; /*relative shift*/
  60         j=i;
  61         temp=data->shared_memory_base_address+block_size;
  62
  63         if (data->key_len==2)
  64         {
  65                 value=SW_ULONG_AT(key,0);
  66
  67                 if((value<SW_ULONG_AT(temp,0))||(value>SW_ULONG_AT(temp+block_size*(blocks-1),4)))
  68                 {
  69                         uint32 *key32=(uint32*) key;
  70                         key32[0]=key32[1]=0;
  71
  72                         GET_TIME((struct timeval *)(data->shared_memory_base_address+8),time_ref);
  73
  74                         data->last_found=NULL;
  75                         return TME_FALSE;
  76                 }
  77
  78                 while(found==-1) /* search routine */
  79                 {
  80                         i=(i==1)? 1:i>>1;
  81                         if (SW_ULONG_AT(temp+block_size*j,0)>value)
  82                                 if (SW_ULONG_AT(temp+block_size*(j-1),4)<value)
  83                                         found=-2;
  84                                 else
  85                                         j-=i;
  86                         else
  87                                 if (SW_ULONG_AT(temp+block_size*j,4)<value)
  88                                         if (SW_ULONG_AT(temp+block_size*j,0)>value)
  89                                                 found=-2;
  90                                         else
  91                                                 j+=i;
  92                                 else found=j;
  93                 }
  94                 if (found<0)
  95                 {
  96                         uint32 *key32=(uint32*) key;
  97                         key32[0]=key32[1]=0;
  98
  99                         GET_TIME((struct timeval *)(data->shared_memory_base_address+8),time_ref);
 100
 101                         data->last_found=NULL;
 102                         return TME_FALSE;
 103                 }
 104
 105                 data->last_found=data->lut_base_address+found*sizeof(RECORD);
 106
 107                 COPY_MEMORY(key,temp+block_size*found,8);
 108
 109                 GET_TIME((struct timeval *)(temp+block_size*found+8),time_ref);
 110
 111                 return TME_TRUE;
 112         }
 113         else
 114         {
 115                 value=SW_USHORT_AT(key,0);
 116
 117                 if((value<SW_USHORT_AT(temp,0))||(value>SW_USHORT_AT(temp+block_size*(blocks-1),2)))
 118                 {
 119                         uint16 *key16=(uint16*) key;
 120                         key16[0]=key16[1]=0;
 121
 122                         GET_TIME((struct timeval *)(data->shared_memory_base_address+4),time_ref);
 123
 124                         data->last_found=NULL;
 125                         return TME_FALSE;
 126                 }
 127
 128                 while(found==-1) /* search routine */
 129                 {
 130                         i=(i==1)? 1:i>>1;
 131                         if (SW_USHORT_AT(temp+block_size*j,0)>value)
 132                                 if (SW_USHORT_AT(temp+block_size*(j-1),2)<value)
 133                                         found=-2;
 134                                 else
 135                                         j-=i;
 136                         else
 137                                 if (SW_USHORT_AT(temp+block_size*j,2)<value)
 138                                         if (SW_USHORT_AT(temp+block_size*j,0)>value)
 139                                                 found=-2;
 140                                         else
 141                                                 j+=i;
 142                                 else found=j;
 143                 }
 144
 145                 if (found<0)
 146                 {
 147                         uint16 *key16=(uint16*) key;
 148                         key16[0]=key16[1]=0;
 149
 150                         GET_TIME((struct timeval *)(data->shared_memory_base_address+4),time_ref);
 151
 152                         data->last_found=NULL;
 153                         return TME_FALSE;
 154                 }
 155
 156                 data->last_found=data->lut_base_address+found*sizeof(RECORD);
 157
 158                 GET_TIME((struct timeval *)(temp+block_size*found+4),time_ref);
 159
 160                 COPY_MEMORY(key,temp+block_size*found,4);
 161
 162                 return TME_TRUE;
 163         }
 164
 165 }
 166
 167 uint32 bucket_lookup_insert(uint8 *key, TME_DATA *data, MEM_TYPE *mem_ex, struct time_conv *time_ref)
 168 {
 169         RECORD *records=(RECORD*)data->lut_base_address;
 170
 171         if ((data->key_len!=1)&&  /*16 bit value*/
 172                 (data->key_len!=2))   /*32 bit value*/
 173                 return TME_ERROR;
 174
 175         if(data->key_len==2)
 176         {
 177                 uint32 start,stop;
 178                 uint8 *tmp;
 179
 180                 start=SW_ULONG_AT(key,0);
 181                 stop=SW_ULONG_AT(key,4);
 182
 183                 if (start>stop)
 184                         return TME_ERROR;
 185                 if (data->filled_entries>0)
 186                 {
 187                         tmp=mem_ex->buffer+SW_ULONG_AT(&records[data->filled_entries-1].block,0);
 188                         /*check if it is coherent with the previous block*/
 189                         if (SW_ULONG_AT(tmp,4)>=start)
 190                                 return TME_ERROR;
 191                 }
 192
 193                 if (data->filled_blocks==data->shared_memory_blocks)
 194                         return TME_ERROR;
 195
 196                 if (data->filled_entries==data->lut_entries)
 197                         return TME_ERROR;
 198
 199                 tmp=data->shared_memory_base_address+data->block_size*data->filled_blocks;
 200
 201                 COPY_MEMORY(tmp,key,8);
 202
 203                 SW_ULONG_ASSIGN(&records[data->filled_entries].block,tmp-mem_ex->buffer);
 204                 SW_ULONG_ASSIGN(&records[data->filled_entries].exec_fcn,data->default_exec);
 205
 206                 GET_TIME((struct timeval *)(tmp+8),time_ref);
 207
 208                 data->filled_blocks++;
 209                 data->filled_entries++;
 210
 211                 return TME_TRUE;
 212         }
 213         else
 214         {
 215                 uint16 start,stop;
 216                 uint8 *tmp;
 217
 218                 start=SW_USHORT_AT(key,0);
 219                 stop=SW_USHORT_AT(key,2);
 220
 221                 if (start>stop)
 222                         return TME_ERROR;
 223                 if (data->filled_entries>0)
 224                 {
 225                         tmp=mem_ex->buffer+SW_ULONG_AT(&records[data->filled_entries-1].block,0);
 226                         /*check if it is coherent with the previous block*/
 227                         if (SW_USHORT_AT(tmp,2)>=start)
 228                                 return TME_ERROR;
 229                 }
 230
 231                 if (data->filled_blocks==data->shared_memory_blocks)
 232                         return TME_ERROR;
 233
 234                 if (data->filled_entries==data->lut_entries)
 235                         return TME_ERROR;
 236
 237                 tmp=mem_ex->buffer+SW_ULONG_AT(&records[data->filled_entries].block,0);
 238
 239                 COPY_MEMORY(tmp,key,4);
 240
 241                 SW_ULONG_ASSIGN(&records[data->filled_entries].block,tmp-mem_ex->buffer);
 242                 SW_ULONG_ASSIGN(&records[data->filled_entries].exec_fcn,data->default_exec);
 243
 244                 GET_TIME((struct timeval *)(tmp+4),time_ref);
 245
 246                 data->filled_blocks++;
 247                 data->filled_entries++;
 248
 249                 return TME_TRUE;
 250         }
 251 }
 252