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