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