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