vde/hash.c

   1 /* Copyright 2002 Yon Uriarte and Jeff Dike
   2  * Licensed under the GPL
   3  * This file is part of the original uml_switch code
   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
  23 #define HASH_SIZE 128
  24 #define HASH_MOD 11
  25
  26 struct hash_entry {
  27   struct hash_entry *next;
  28   struct hash_entry *prev;
  29   time_t last_seen;
  30   void *port;
  31   unsigned char dst[ETH_ALEN];
  32 };
  33
  34 static struct hash_entry *h[HASH_SIZE];
  35
  36 static int calc_hash(char *src)
  37 {
  38   return ((*(u_int32_t *) &src[0] % HASH_MOD) ^ src[4] ^ src[5] ) % HASH_SIZE ;
  39 }
  40
  41 static struct hash_entry *find_entry(char *dst)
  42 {
  43   struct hash_entry *e;
  44   int k = calc_hash(dst);
  45
  46   for(e = h[k]; e; e = e->next){
  47     if(!memcmp(&e->dst, dst, ETH_ALEN)) return(e);
  48   }
  49   return(NULL);
  50 }
  51
  52 /* looks in global hash table 'h' for given address, and return associated
  53  * port */
  54 void *find_in_hash(char *dst)
  55 {
  56   struct hash_entry *e = find_entry(dst);
  57   if(e == NULL) return(NULL);
  58   return(e->port);
  59 }
  60
  61 void insert_into_hash(char *src, void *port)
  62 {
  63   struct hash_entry *new;
  64   int k = calc_hash(src);
  65
  66   new = find_in_hash(src);
  67   if(new != NULL) return;
  68
  69   new = malloc(sizeof(*new));
  70   if(new == NULL){
  71     printlog(LOG_WARNING,"Failed to malloc hash entry %s",strerror(errno));
  72     return;
  73   }
  74
  75   memcpy(&new->dst, src, ETH_ALEN );
  76   if(h[k] != NULL) h[k]->prev = new;
  77   new->next = h[k];
  78   new->prev = NULL;
  79   new->port = port;
  80   new->last_seen = 0;
  81   h[k] = new;
  82 }
  83
  84 void update_entry_time(char *src)
  85 {
  86   struct hash_entry *e;
  87
  88   e = find_entry(src);
  89   if(e == NULL) return;
  90   e->last_seen = time(NULL);
  91 }
  92
  93 /* removes given hash entry from the global table 'h' */
  94 static void delete_hash_entry(struct hash_entry *old)
  95 {
  96   int k = calc_hash(old->dst);
  97
  98   if(old->prev != NULL) old->prev->next = old->next;
  99   if(old->next != NULL) old->next->prev = old->prev;
 100   if(h[k] == old) h[k] = old->next;
 101   free(old);
 102 }
 103
 104 void delete_hash(char *dst)
 105 {
 106   struct hash_entry *old = find_entry(dst);
 107
 108   if(old == NULL) return;
 109   delete_hash_entry(old);
 110 }
 111
 112 /* for each entry of the global hash table 'h', calls function f, passing to it
 113  * the hash entry and the additional arg 'arg' */
 114 static void for_all_hash(void (*f)(struct hash_entry *, void *), void *arg)
 115 {
 116   int i;
 117   struct hash_entry *e, *next;
 118
 119   for(i = 0; i < HASH_SIZE; i++){
 120     for(e = h[i]; e; e = next){
 121       next = e->next;
 122       (*f)(e, arg);
 123     }
 124   }
 125 }
 126
 127 struct printer {
 128   time_t now;
 129   char *(*port_id)(void *);
 130 };
 131
 132 static void print_hash_entry(struct hash_entry *e, void *arg)
 133 {
 134   struct printer *p = arg;
 135
 136   printf("Hash: %d Addr: %02x:%02x:%02x:%02x:%02x:%02x to port: %s  "
 137          "age %ld secs\n", calc_hash(e->dst),
 138          e->dst[0], e->dst[1], e->dst[2], e->dst[3], e->dst[4], e->dst[5],
 139          (*p->port_id)(e->port), (int) p->now - e->last_seen);
 140 }
 141
 142 void print_hash(char *(*port_id)(void *))
 143 {
 144   struct printer p = ((struct printer) { now :          time(NULL),
 145                                          port_id :      port_id });
 146
 147   for_all_hash(print_hash_entry, &p);
 148 }
 149
 150 struct reassign_data {
 151         void *port;
 152         void *newport;
 153 };
 154
 155 static void reassing_iterator (struct hash_entry *e, void *arg)
 156 {
 157         struct reassign_data *p=arg;
 158
 159         if (e->port == p->port)
 160                 e->port = p->newport;
 161 }
 162
 163 void hash_reassign (void *port, void *newport)
 164 {
 165         struct reassign_data p=((struct reassign_data) { port : port,
 166                                                         newport : newport });
 167         for_all_hash(reassing_iterator, &p);
 168 }
 169
 170 static void delete_port_iterator (struct hash_entry *e, void *arg)
 171 {
 172         if (e->port == arg)
 173                 delete_hash_entry(e);
 174 }
 175
 176 void hash_delete_port (void *port)
 177 {
 178         for_all_hash(delete_port_iterator,port);
 179 }
 180
 181
 182 #define GC_INTERVAL 2
 183 #define GC_EXPIRE 100
 184
 185 /* clean from the hash table entries older than GC_EXPIRE seconds, given that
 186  * 'now' points to a time_t structure describing the current time */
 187 static void gc(struct hash_entry *e, void *now)
 188 {
 189   time_t t = *(time_t *) now;
 190
 191   if(e->last_seen + GC_EXPIRE < t)
 192     delete_hash_entry(e);
 193 }
 194
 195 /* clean old entries in the hash table 'h', and prepare the timer to be called
 196  * again between GC_INTERVAL seconds */
 197 static void sig_alarm(int sig)
 198 {
 199   struct itimerval it;
 200   time_t t = time(NULL);
 201   for_all_hash(&gc, &t);
 202
 203   it.it_value.tv_sec = GC_INTERVAL;
 204   it.it_value.tv_usec = 0 ;
 205   it.it_interval.tv_sec = 0;
 206   it.it_interval.tv_usec = 0 ;
 207   setitimer(ITIMER_REAL, &it, NULL);
 208 }
 209
 210 /* sets sig_alarm as handler for SIGALRM, and run it a first time */
 211 void hash_init(void)
 212 {
 213   struct sigaction sa;
 214
 215   sa.sa_handler = sig_alarm;
 216   sa.sa_flags = SA_RESTART;
 217   if(sigaction(SIGALRM, &sa, NULL) < 0){
 218     printlog(LOG_WARNING,"Setting handler for SIGALRM %s", strerror(errno));
 219     return;
 220   }
 221   kill(getpid(), SIGALRM);
 222 }