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