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