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 <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 <sys/types.h>
  15 #include <sys/time.h>
  16 #include <sys/signal.h>
  17 #include "switch.h"
  18 #include "hash.h"
  19
  20 #define HASH_SIZE 128
  21 #define HASH_MOD 11
  22
  23 struct hash_entry {
  24   struct hash_entry *next;
  25   struct hash_entry *prev;
  26   time_t last_seen;
  27   void *port;
  28   unsigned char dst[ETH_ALEN];
  29 };
  30
  31 static struct hash_entry *h[HASH_SIZE];
  32
  33 static int calc_hash(char *src)
  34 {
  35   return ((*(u_int32_t *) &src[0] % HASH_MOD) ^ src[4] ^ src[5] ) % HASH_SIZE ;
  36 }
  37
  38 static struct hash_entry *find_entry(char *dst)
  39 {
  40   struct hash_entry *e;
  41   int k = calc_hash(dst);
  42
  43   for(e = h[k]; e; e = e->next){
  44     if(!memcmp(&e->dst, dst, ETH_ALEN)) return(e);
  45   }
  46   return(NULL);
  47 }
  48
  49 void *find_in_hash(char *dst)
  50 {
  51   struct hash_entry *e = find_entry(dst);
  52   if(e == NULL) return(NULL);
  53   return(e->port);
  54 }
  55
  56 void insert_into_hash(char *src, void *port)
  57 {
  58   struct hash_entry *new;
  59   int k = calc_hash(src);
  60
  61   new = find_in_hash(src);
  62   if(new != NULL) return;
  63
  64   new = malloc(sizeof(*new));
  65   if(new == NULL){
  66     perror("Failed to malloc hash entry");
  67     return;
  68   }
  69
  70   memcpy(&new->dst, src, ETH_ALEN );
  71   if(h[k] != NULL) h[k]->prev = new;
  72   new->next = h[k];
  73   new->prev = NULL;
  74   new->port = port;
  75   new->last_seen = 0;
  76   h[k] = new;
  77 }
  78
  79 void update_entry_time(char *src)
  80 {
  81   struct hash_entry *e;
  82
  83   e = find_entry(src);
  84   if(e == NULL) return;
  85   e->last_seen = time(NULL);
  86 }
  87
  88 static void delete_hash_entry(struct hash_entry *old)
  89 {
  90   int k = calc_hash(old->dst);
  91
  92   if(old->prev != NULL) old->prev->next = old->next;
  93   if(old->next != NULL) old->next->prev = old->prev;
  94   if(h[k] == old) h[k] = old->next;
  95   free(old);
  96 }
  97
  98 void delete_hash(char *dst)
  99 {
 100   struct hash_entry *old = find_entry(dst);
 101
 102   if(old == NULL) return;
 103   delete_hash_entry(old);
 104 }
 105
 106 static void for_all_hash(void (*f)(struct hash_entry *, void *), void *arg)
 107 {
 108   int i;
 109   struct hash_entry *e, *next;
 110
 111   for(i = 0; i < HASH_SIZE; i++){
 112     for(e = h[i]; e; e = next){
 113       next = e->next;
 114       (*f)(e, arg);
 115     }
 116   }
 117 }
 118
 119 struct printer {
 120   time_t now;
 121   char *(*port_id)(void *);
 122 };
 123
 124 static void print_hash_entry(struct hash_entry *e, void *arg)
 125 {
 126   struct printer *p = arg;
 127
 128   printf("Hash: %d Addr: %02x:%02x:%02x:%02x:%02x:%02x to port: %s  "
 129          "age %ld secs\n", calc_hash(e->dst),
 130          e->dst[0], e->dst[1], e->dst[2], e->dst[3], e->dst[4], e->dst[5],
 131          (*p->port_id)(e->port), (int) p->now - e->last_seen);
 132 }
 133
 134 void print_hash(char *(*port_id)(void *))
 135 {
 136   struct printer p = ((struct printer) { now :          time(NULL),
 137                                          port_id :      port_id });
 138
 139   for_all_hash(print_hash_entry, &p);
 140 }
 141
 142 struct reassign_data {
 143         void *port;
 144         void *newport;
 145 };
 146
 147 static void reassing_iterator (struct hash_entry *e, void *arg)
 148 {
 149         struct reassign_data *p=arg;
 150
 151         if (e->port == p->port)
 152                 e->port = p->newport;
 153 }
 154
 155 void hash_reassign (void *port, void *newport)
 156 {
 157         struct reassign_data p=((struct reassign_data) { port : port,
 158                                                         newport : newport });
 159         for_all_hash(reassing_iterator, &p);
 160 }
 161
 162 static void delete_port_iterator (struct hash_entry *e, void *arg)
 163 {
 164         if (e->port == arg)
 165                 delete_hash_entry(e);
 166 }
 167
 168 void hash_delete_port (void *port)
 169 {
 170         for_all_hash(delete_port_iterator,port);
 171 }
 172
 173
 174 #define GC_INTERVAL 2
 175 #define GC_EXPIRE 100
 176
 177 static void gc(struct hash_entry *e, void *now)
 178 {
 179   time_t t = *(time_t *) now;
 180
 181   if(e->last_seen + GC_EXPIRE < t)
 182     delete_hash_entry(e);
 183 }
 184
 185 static void sig_alarm(int sig)
 186 {
 187   struct itimerval it;
 188   time_t t = time(NULL);
 189   for_all_hash(&gc, &t);
 190
 191   it.it_value.tv_sec = GC_INTERVAL;
 192   it.it_value.tv_usec = 0 ;
 193   it.it_interval.tv_sec = 0;
 194   it.it_interval.tv_usec = 0 ;
 195   setitimer(ITIMER_REAL, &it, NULL);
 196 }
 197
 198 void hash_init(void)
 199 {
 200   struct sigaction sa;
 201
 202   sa.sa_handler = sig_alarm;
 203   sa.sa_flags = SA_RESTART;
 204   if(sigaction(SIGALRM, &sa, NULL) < 0){
 205     perror("Setting handler for SIGALRM");
 206     return;
 207   }
 208   kill(getpid(), SIGALRM);
 209 }