vde-2/src/vde_vxlan/vxlan_hash.c

   1 /*
   2  * VDE - vde_vxlan Network emulator for vde
   3  * Copyright (C) 2014 Renzo Davoli, Alessandro Ghedini VirtualSquare
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA.
  18  */
  19
  20 #include <stddef.h>
  21 #include <stdlib.h>
  22 #include <stdio.h>
  23 #include <unistd.h>
  24 #include <string.h>
  25 #include <errno.h>
  26 #include <time.h>
  27 #include <syslog.h>
  28 #include <sys/types.h>
  29 #include <sys/time.h>
  30 #include <sys/signal.h>
  31
  32 #include <config.h>
  33 #include <vde.h>
  34 #include <vdecommon.h>
  35
  36 #include "log.h"
  37 #include "switch.h"
  38 #include "vxlan_hash.h"
  39 #include "consmgmt.h"
  40 #include "bitarray.h"
  41
  42 #define MIN_PERSISTENCE_DFL 3
  43 static int min_persistence=MIN_PERSISTENCE_DFL;
  44 #define HASH_INIT_BITS 7
  45 static int hash_bits;
  46 static int hash_mask;
  47 #define HASH_SIZE (1 << hash_bits)
  48
  49 struct hash_entry {
  50         struct hash_entry *next;
  51         struct hash_entry **prev;
  52         time_t last_seen;
  53         in_addr_t port;
  54         u_int64_t dst;
  55 };
  56
  57 static struct hash_entry **h;
  58
  59 static int calc_hash(u_int64_t src)
  60 {
  61         src ^= src >> 33;
  62         src *= 0xff51afd7ed558ccd;
  63         src ^= src >> 33;
  64         src *= 0xc4ceb9fe1a85ec53;
  65         return src & hash_mask;
  66 }
  67
  68 #if BYTE_ORDER == LITTLE_ENDIAN
  69 #define EMAC2MAC6(X) \
  70         (u_int)((X)&0xff), (u_int)(((X)>>8)&0xff), (u_int)(((X)>>16)&0xff), \
  71   (u_int)(((X)>>24)&0xff), (u_int)(((X)>>32)&0xff), (u_int)(((X)>>40)&0xff)
  72 #elif BYTE_ORDER == BIG_ENDIAN
  73 #define EMAC2MAC6(X) \
  74         (u_int)(((X)>>24)&0xff), (u_int)(((X)>>16)&0xff), (u_int)(((X)>>8)&0xff), \
  75   (u_int)((X)&0xff), (u_int)(((X)>>40)&0xff), (u_int)(((X)>>32)&0xff)
  76 #else
  77 #error Unknown Endianess
  78 #endif
  79
  80 #define EMAC2VLAN(X) ((u_int16_t) ((X)>>48))
  81 #define EMAC2VLAN2(X) ((u_int) (((X)>>48) &0xff)), ((u_int) (((X)>>56) &0xff))
  82
  83 #define find_entry(MAC) \
  84         ({struct hash_entry *e; \
  85          int k = calc_hash(MAC);\
  86          for(e = h[k]; e && e->dst != (MAC); e = e->next)\
  87          ;\
  88          e; })
  89
  90
  91 #define extmac(MAC,VLAN) \
  92             ((*(u_int32_t *) &((MAC)[0])) + ((u_int64_t) ((*(u_int16_t *) &((MAC)[4]))+ ((u_int64_t) (VLAN) << 16)) << 32))
  93
  94 /* looks in global hash table 'h' for given address, and return associated
  95  * port */
  96 int find_in_hash(unsigned char *dst, int vlan, in_addr_t *out)
  97 {
  98         struct hash_entry *e = find_entry(extmac(dst,vlan));
  99         *out = 0;
 100         if(e == NULL) return 0;
 101         *out = e->port;
 102         return 1;
 103 }
 104
 105 int find_in_hash_update(unsigned char *src, int vlan, in_addr_t port, in_addr_t *out)
 106 {
 107         struct hash_entry *e;
 108         u_int64_t esrc=extmac(src,vlan);
 109         int k = calc_hash(esrc);
 110         in_addr_t oldport;
 111         time_t now;
 112         for(e = h[k]; e && e->dst != esrc; e = e->next)
 113                 ;
 114         if(e == NULL) {
 115                 e = (struct hash_entry *) malloc(sizeof(*e));
 116                 if(e == NULL){
 117                         printlog(LOG_WARNING,"Failed to malloc hash entry %s",strerror(errno));
 118                         return 0;
 119                 }
 120
 121                 DBGOUT(DBGHASHNEW,"%02x:%02x:%02x:%02x:%02x:%02x VLAN %02x:%02x Port %d",
 122                                 EMAC2MAC6(esrc), EMAC2VLAN2(esrc), port);
 123                 EVENTOUT(DBGHASHNEW,esrc);
 124                 e->dst = esrc;
 125                 if(h[k] != NULL) h[k]->prev = &(e->next);
 126                 e->next = h[k];
 127                 e->prev = &(h[k]);
 128                 e->port = port;
 129                 h[k] = e;
 130         }
 131         oldport=e->port;
 132         now=time(NULL);
 133         if (oldport!=port) {
 134                 if ((now - e->last_seen) > min_persistence) {
 135                         e->port=port;
 136                         e->last_seen = now;
 137                 }
 138         } else {
 139                 e->last_seen = now;
 140         }
 141         if (out != NULL) *out = oldport;
 142         return 1;
 143 }
 144
 145 #define delete_hash_entry(OLD) \
 146         ({ \
 147          DBGOUT(DBGHASHDEL,"%02x:%02x:%02x:%02x:%02x:%02x VLAN %02x:%02x Port %d", EMAC2MAC6(OLD->dst), EMAC2VLAN2(OLD->dst), OLD->port); \
 148          EVENTOUT(DBGHASHDEL,OLD->dst);\
 149          *((OLD)->prev)=(OLD)->next; \
 150          if((OLD)->next != NULL) (OLD)->next->prev = (OLD)->prev; \
 151          free((OLD)); \
 152          })
 153
 154
 155 /* for each entry of the global hash table 'h', calls function f, passing to it
 156  * the hash entry and the additional arg 'arg' */
 157 static void for_all_hash(void (*f)(struct hash_entry *, void *), void *arg)
 158 {
 159         int i;
 160         struct hash_entry *e, *next;
 161
 162         for(i = 0; i < HASH_SIZE; i++){
 163                 for(e = h[i]; e; e = next){
 164                         next = e->next;
 165                         (*f)(e, arg);
 166                 }
 167         }
 168 }
 169
 170 #define GC_INTERVAL 2
 171 #define GC_EXPIRE 100
 172 static int gc_interval;
 173 static int gc_expire;
 174
 175 /* clean from the hash table entries older than GC_EXPIRE seconds, given that
 176  * 'now' points to a time_t structure describing the current time */
 177 static void gc(struct hash_entry *e, void *now)
 178 {
 179         time_t t = *(time_t *) now;
 180         if(e->last_seen + gc_expire < t)
 181                 delete_hash_entry(e);
 182 }
 183
 184 /* clean old entries in the hash table 'h', and prepare the timer to be called
 185  * again between GC_INTERVAL seconds */
 186 void hash_gc(void)
 187 {
 188         time_t t = time(NULL);
 189         static time_t last_t;
 190         if (t - last_t > GC_INTERVAL) {
 191                 for_all_hash(&gc, &t);
 192                 last_t=t;
 193         }
 194 }
 195
 196 #define HASH_INIT(BIT) \
 197         ({ hash_bits=(BIT);\
 198          hash_mask=HASH_SIZE-1;\
 199          if ((h=(struct hash_entry **) calloc (HASH_SIZE,sizeof (struct hash_entry *))) == NULL) {\
 200          printlog(LOG_WARNING,"Failed to malloc hash table %s",strerror(errno));\
 201          exit(1); \
 202          }\
 203          })
 204
 205 static inline int po2round(int vx)
 206 {
 207         if (vx == 0)
 208                 return 0;
 209         else {
 210                 int i=0;
 211                 int x=vx-1;
 212                 while (x) { x>>=1; i++; }
 213                 if (vx != 1<<i)
 214                         printlog(LOG_WARNING,"Hash size must be a power of 2. %d rounded to %d",vx,1<<i);
 215                 return i;
 216         }
 217 }
 218
 219 int hash_set_gc_interval(int p)
 220 {
 221         gc_interval=p;
 222         return 0;
 223 }
 224
 225 int hash_set_gc_expire(int e)
 226 {
 227         gc_expire=e;
 228         return 0;
 229 }
 230
 231 int hash_set_minper(int e)
 232 {
 233         min_persistence=e;
 234         return 0;
 235 }
 236
 237 /* sets sig_alarm as handler for SIGALRM, and run it a first time */
 238 void hash_init(int hash_size)
 239 {
 240         HASH_INIT(po2round(hash_size));
 241
 242         gc_interval=GC_INTERVAL;
 243         gc_expire=GC_EXPIRE;
 244 }