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