2.3.2/src/vde_switch/hash.c

   1 /* Copyright 2005 Renzo Davoli VDE-2
   2  * Copyright 2002 Yon Uriarte and Jeff Dike (uml_switch)
   3  * Licensed under the GPLv2
   4  * Modified 2003 Renzo Davoli
   5  */
   6
   7 #include <stddef.h>
   8 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <unistd.h>
  11 #include <string.h>
  12 #include <errno.h>
  13 #include <time.h>
  14 #include <syslog.h>
  15 #include <sys/types.h>
  16 #include <sys/time.h>
  17 #include <sys/signal.h>
  18
  19 #include <config.h>
  20 #include <vde.h>
  21 #include <vdecommon.h>
  22
  23 #include "switch.h"
  24 #include "hash.h"
  25 #include "qtimer.h"
  26 #include "consmgmt.h"
  27 #include "bitarray.h"
  28
  29 #define MIN_PERSISTENCE_DFL 3
  30 static int min_persistence=MIN_PERSISTENCE_DFL;
  31 #define HASH_INIT_BITS 7
  32 static int hash_bits;
  33 static int hash_mask;
  34 #define HASH_SIZE (1 << hash_bits)
  35
  36 #ifdef DEBUGOPT
  37 #define DBGHASHNEW (dl)
  38 #define DBGHASHDEL (dl+1)
  39 static struct dbgcl dl[]= {
  40         {"hash/+","hash: new element",D_HASH|D_PLUS},
  41         {"hash/-","hash: discarded element",D_HASH|D_MINUS},
  42 };
  43 #endif
  44 struct hash_entry {
  45         struct hash_entry *next;
  46         struct hash_entry **prev;
  47         time_t last_seen;
  48         int port;
  49         u_int64_t dst;
  50 };
  51
  52 static struct hash_entry **h;
  53
  54 static int calc_hash(u_int64_t src)
  55 {
  56         register int x = src * 0x030507090b0d1113LL;
  57         x = (x ^ x >> 12 ^ x >> 8 ^ x >> 4) & hash_mask;
  58         /*printf("HASH %02x:%02x:%02x:%02x:%02x:%02x V%d -> %d\n", src[0], src[1], src[2], src[3], src[4], src[5],(src[6]>>8)+src[7],x);*/
  59         return x;
  60 }
  61
  62 #if BYTE_ORDER == LITTLE_ENDIAN
  63 #define EMAC2MAC6(X) \
  64         (u_int)((X)&0xff), (u_int)(((X)>>8)&0xff), (u_int)(((X)>>16)&0xff), \
  65   (u_int)(((X)>>24)&0xff), (u_int)(((X)>>32)&0xff), (u_int)(((X)>>40)&0xff)
  66 #elif BYTE_ORDER == BIG_ENDIAN
  67 #define EMAC2MAC6(X) \
  68         (u_int)(((X)>>24)&0xff), (u_int)(((X)>>16)&0xff), (u_int)(((X)>>8)&0xff), \
  69   (u_int)((X)&0xff), (u_int)(((X)>>40)&0xff), (u_int)(((X)>>32)&0xff)
  70 #else
  71 #error Unknown Endianess
  72 #endif
  73
  74 #define EMAC2VLAN(X) ((u_int16_t) ((X)>>48))
  75 #define EMAC2VLAN2(X) ((u_int) (((X)>>48) &0xff)), ((u_int) (((X)>>56) &0xff))
  76
  77 #define find_entry(MAC) \
  78         ({struct hash_entry *e; \
  79          int k = calc_hash(MAC);\
  80          for(e = h[k]; e && e->dst != (MAC); e = e->next)\
  81          ;\
  82          e; })
  83
  84
  85 #define extmac(MAC,VLAN) \
  86             ((*(u_int32_t *) &((MAC)[0])) + ((u_int64_t) ((*(u_int16_t *) &((MAC)[4]))+ ((u_int64_t) (VLAN) << 16)) << 32))
  87
  88 /* looks in global hash table 'h' for given address, and return associated
  89  * port */
  90 int find_in_hash(unsigned char *dst,int vlan)
  91 {
  92         struct hash_entry *e = find_entry(extmac(dst,vlan));
  93         if(e == NULL) return -1;
  94         return(e->port);
  95 }
  96
  97
  98 int find_in_hash_update(unsigned char *src,int vlan,int port)
  99 {
 100         struct hash_entry *e;
 101         u_int64_t esrc=extmac(src,vlan);
 102         int k = calc_hash(esrc);
 103         int oldport;
 104         time_t now;
 105         for(e = h[k]; e && e->dst != esrc; e = e->next)
 106                 ;
 107         if(e == NULL) {
 108                 e = (struct hash_entry *) malloc(sizeof(*e));
 109                 if(e == NULL){
 110                         printlog(LOG_WARNING,"Failed to malloc hash entry %s",strerror(errno));
 111                         return -1;
 112                 }
 113
 114                 DBGOUT(DBGHASHNEW,"%02x:%02x:%02x:%02x:%02x:%02x VLAN %02x:%02x Port %d",
 115                                 EMAC2MAC6(esrc), EMAC2VLAN2(esrc), port);
 116                 EVENTOUT(DBGHASHNEW,esrc);
 117                 e->dst = esrc;
 118                 if(h[k] != NULL) h[k]->prev = &(e->next);
 119                 e->next = h[k];
 120                 e->prev = &(h[k]);
 121                 e->port = port;
 122                 h[k] = e;
 123         }
 124         oldport=e->port;
 125         now=qtime();
 126         if (oldport!=port) {
 127                 if ((now - e->last_seen) > min_persistence) {
 128                         e->port=port;
 129                         e->last_seen = now;
 130                 }
 131         } else {
 132                 e->last_seen = now;
 133         }
 134         return oldport;
 135 }
 136
 137 #define delete_hash_entry(OLD) \
 138         ({ \
 139          DBGOUT(DBGHASHDEL,"%02x:%02x:%02x:%02x:%02x:%02x VLAN %02x:%02x Port %d", EMAC2MAC6(OLD->dst), EMAC2VLAN2(OLD->dst), OLD->port); \
 140          EVENTOUT(DBGHASHDEL,OLD->dst);\
 141          *((OLD)->prev)=(OLD)->next; \
 142          if((OLD)->next != NULL) (OLD)->next->prev = (OLD)->prev; \
 143          free((OLD)); \
 144          })
 145
 146
 147 void delete_hash(unsigned char *dst,int vlan)
 148 {
 149         struct hash_entry *old = find_entry(extmac(dst,vlan));
 150
 151         if(old == NULL) return;
 152         qtime_csenter();
 153         delete_hash_entry(old);
 154         qtime_csexit();
 155 }
 156
 157 /* for each entry of the global hash table 'h', calls function f, passing to it
 158  * the hash entry and the additional arg 'arg' */
 159 static void for_all_hash(void (*f)(struct hash_entry *, void *), void *arg)
 160 {
 161         int i;
 162         struct hash_entry *e, *next;
 163
 164         for(i = 0; i < HASH_SIZE; i++){
 165                 for(e = h[i]; e; e = next){
 166                         next = e->next;
 167                         (*f)(e, arg);
 168                 }
 169         }
 170 }
 171
 172 static void delete_port_iterator (struct hash_entry *e, void *arg)
 173 {
 174         int *pport=(int *)arg;
 175         if (e->port == *pport)
 176                 delete_hash_entry(e);
 177 }
 178
 179 void hash_delete_port (int port)
 180 {
 181         qtime_csenter();
 182         for_all_hash(delete_port_iterator,&port);
 183         qtime_csexit();
 184 }
 185
 186 static void delete_vlan_iterator (struct hash_entry *e, void *arg)
 187 {
 188         int *vlan=(int *)arg;
 189         if (EMAC2VLAN(e->dst) == (u_int16_t)(*vlan))
 190                 delete_hash_entry(e);
 191 }
 192
 193 void hash_delete_vlan (int vlan)
 194 {
 195         qtime_csenter();
 196         for_all_hash(delete_vlan_iterator,&vlan);
 197         qtime_csexit();
 198 }
 199
 200 struct vlanport {int vlan; int port;};
 201
 202 static void delete_vlanport_iterator (struct hash_entry *e, void *arg)
 203 {
 204         struct vlanport *vp=(struct vlanport *)arg;
 205         if ((EMAC2VLAN(e->dst)) == (u_int16_t)(vp->vlan) &&
 206                         e->port == vp->port)
 207                 delete_hash_entry(e);
 208 }
 209
 210 void hash_delete_vlanport (int vlan,int port)
 211 {
 212         struct vlanport vp={vlan,port};
 213         qtime_csenter();
 214         for_all_hash(delete_vlanport_iterator,&vp);
 215         qtime_csexit();
 216 }
 217
 218 struct vlansetofports {int vlan; bitarray setofports;};
 219
 220 static void delete_vlansetofports_iterator (struct hash_entry *e, void *arg)
 221 {
 222         struct vlansetofports *vp=(struct vlansetofports *)arg;
 223         if ((EMAC2VLAN(e->dst)) == (u_int16_t)(vp->vlan) &&
 224                         ba_check(vp->setofports,e->port))
 225                 delete_hash_entry(e);
 226 }
 227
 228 void hash_delete_vlanports (int vlan,bitarray setofports)
 229 {
 230         struct vlansetofports vp={vlan,setofports};
 231         qtime_csenter();
 232         for_all_hash(delete_vlansetofports_iterator,&vp);
 233         qtime_csexit();
 234 }
 235
 236 static void flush_iterator (struct hash_entry *e, void *arg)
 237 {
 238         delete_hash_entry(e);
 239 }
 240
 241 void hash_flush ()
 242 {
 243         qtime_csenter();
 244         for_all_hash(flush_iterator,NULL);
 245         qtime_csexit();
 246 }
 247
 248
 249 #define GC_INTERVAL 2
 250 #define GC_EXPIRE 100
 251 static int gc_interval;
 252 static int gc_expire;
 253 static unsigned int gc_timerno;
 254
 255 /* clean from the hash table entries older than GC_EXPIRE seconds, given that
 256  * 'now' points to a time_t structure describing the current time */
 257 static void gc(struct hash_entry *e, void *now)
 258 {
 259         time_t t = *(time_t *) now;
 260
 261         if(e->last_seen + gc_expire < t)
 262                 delete_hash_entry(e);
 263 }
 264
 265 /* clean old entries in the hash table 'h', and prepare the timer to be called
 266  * again between GC_INTERVAL seconds */
 267 static void hash_gc(void *arg)
 268 {
 269         time_t t = qtime();
 270         for_all_hash(&gc, &t);
 271 }
 272
 273 #define HASH_INIT(BIT) \
 274         ({ hash_bits=(BIT);\
 275          hash_mask=HASH_SIZE-1;\
 276          if ((h=(struct hash_entry **) calloc (HASH_SIZE,sizeof (struct hash_entry *))) == NULL) {\
 277          printlog(LOG_WARNING,"Failed to malloc hash table %s",strerror(errno));\
 278          exit(1); \
 279          }\
 280          })
 281
 282 static inline int po2round(int vx)
 283 {
 284         if (vx == 0)
 285                 return 0;
 286         else {
 287                 register int i=0;
 288                 register int x=vx-1;
 289                 while (x) { x>>=1; i++; }
 290                 if (vx != 1<<i)
 291                         printlog(LOG_WARNING,"Hash size must be a power of 2. %d rounded to %d",vx,1<<i);
 292                 return i;
 293         }
 294 }
 295
 296 int hash_resize(int hash_size)
 297 {
 298         if (hash_size > 0) {
 299                 hash_flush();
 300                 qtime_csenter();
 301                 free(h);
 302                 HASH_INIT(po2round(hash_size));
 303                 qtime_csexit();
 304                 return 0;
 305         } else
 306                 return EINVAL;
 307 }
 308
 309 int hash_set_gc_interval(int p)
 310 {
 311         qtimer_del(gc_timerno);
 312         gc_interval=p;
 313         gc_timerno=qtimer_add(gc_interval,0,hash_gc,NULL);
 314         return 0;
 315 }
 316
 317 int hash_set_gc_expire(int e)
 318 {
 319         gc_expire=e;
 320         return 0;
 321 }
 322
 323 int hash_set_minper(int e)
 324 {
 325         min_persistence=e;
 326         return 0;
 327 }
 328
 329 int hash_get_gc_interval()
 330 {
 331         return gc_interval;
 332 }
 333
 334 int hash_get_gc_expire()
 335 {
 336         return gc_expire;
 337 }
 338
 339 static int find_hash(FILE *fd,char *strmac)
 340 {
 341         int maci[ETH_ALEN];
 342         unsigned char macv[ETH_ALEN];
 343         unsigned char *mac=macv;
 344         int rv=-1;
 345         int vlan=0;
 346         struct hash_entry *e;
 347         if (index(strmac,':') != NULL)
 348                 rv=sscanf(strmac,"%x:%x:%x:%x:%x:%x %d", maci+0, maci+1, maci+2, maci+3, maci+4, maci+5, &vlan);
 349         else
 350                 rv=sscanf(strmac,"%x.%x.%x.%x.%x.%x %d", maci+0, maci+1, maci+2, maci+3, maci+4, maci+5, &vlan);
 351         if (rv < 6)
 352                 return EINVAL;
 353         else    {
 354                 register int i;
 355                 for (i=0;i<ETH_ALEN;i++)
 356                         mac[i]=maci[i];
 357                 e=find_entry(extmac(mac,vlan));
 358                 if (e==NULL)
 359                         return ENODEV;
 360                 else {
 361                         printoutc(fd,"Hash: %04d Addr: %02x:%02x:%02x:%02x:%02x:%02x VLAN %04d to port: %03d  "
 362                                         "age %ld secs", calc_hash(e->dst),
 363                                 EMAC2MAC6(e->dst),EMAC2VLAN(e->dst), e->port+1, qtime() - e->last_seen);
 364                         return 0;
 365                 }
 366         }
 367 }
 368
 369 static void print_hash_entry(struct hash_entry *e, void *arg)
 370 {
 371
 372         FILE *pfd=arg;
 373         printoutc(pfd,"Hash: %04d Addr: %02x:%02x:%02x:%02x:%02x:%02x VLAN %04d to port: %03d  "
 374                         "age %ld secs", calc_hash(e->dst),
 375                         EMAC2MAC6(e->dst),EMAC2VLAN(e->dst), e->port, qtime() - e->last_seen);
 376 }
 377
 378 static int print_hash(FILE *fd)
 379 {
 380         qtime_csenter();
 381         for_all_hash(print_hash_entry, fd);
 382         qtime_csexit();
 383         return 0;
 384 }
 385
 386 static int showinfo(FILE *fd)
 387 {
 388         printoutc(fd,"Hash size %d",HASH_SIZE);
 389         printoutc(fd,"GC interval %d secs",gc_interval);
 390         printoutc(fd,"GC expire %d secs",gc_expire);
 391         printoutc(fd,"Min persistence %d secs",min_persistence);
 392         return 0;
 393 }
 394
 395 static struct comlist cl[]={
 396         {"hash","============","HASH TABLE MENU",NULL,NOARG},
 397         {"hash/showinfo","","show hash info",showinfo,NOARG|WITHFILE},
 398         {"hash/setsize","N","change hash size",hash_resize,INTARG},
 399         {"hash/setgcint","N","change garbage collector interval",hash_set_gc_interval,INTARG},
 400         {"hash/setexpire","N","change hash entries expire time",hash_set_gc_expire,INTARG},
 401         {"hash/setminper","N","minimum persistence time",hash_set_minper,INTARG},
 402         {"hash/print","","print the hash table",print_hash,NOARG|WITHFILE},
 403         {"hash/find","MAC [VLAN]","MAC lookup",find_hash,STRARG|WITHFILE},
 404 };
 405
 406 /* sets sig_alarm as handler for SIGALRM, and run it a first time */
 407 void hash_init(int hash_size)
 408 {
 409         HASH_INIT(po2round(hash_size));
 410
 411         gc_interval=GC_INTERVAL;
 412         gc_expire=GC_EXPIRE;
 413         gc_timerno=qtimer_add(gc_interval,0,hash_gc,NULL);
 414         ADDCL(cl);
 415 #ifdef DEBUGOPT
 416         ADDDBGCL(dl);
 417 #endif
 418 }