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
16 #include <sys/types.h>
18 #include <sys/signal.h>
26 #define HASH_INIT_BITS 7
29 #define HASH_SIZE (1 << hash_bits)
32 struct hash_entry
*next
;
33 struct hash_entry
**prev
;
36 unsigned char dst
[ETH_ALEN
+2];
39 static struct hash_entry
**h
;
41 static int calc_hash(unsigned char *src
)
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);*/
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)\
58 #define extmac(EMAC,MAC,VLAN) \
59 ({ memcpy(EMAC,(MAC),ETH_ALEN); \
60 *((u_int16_t *)(EMAC+ETH_ALEN))=(u_int16_t) VLAN; \
63 /* looks in global hash table 'h' for given address, and return associated
65 int find_in_hash(unsigned char *dst
,int vlan
)
67 unsigned char edst
[ETH_ALEN
+2];
68 struct hash_entry
*e
= find_entry(extmac(edst
,dst
,vlan
));
69 if(e
== NULL
) return -1;
74 int find_in_hash_update(unsigned char *src
,int vlan
,int port
)
76 unsigned char esrc
[ETH_ALEN
+2];
78 int k
= calc_hash(extmac(esrc
,src
,vlan
));
80 for(e
= h
[k
]; e
&& memcmp(&e
->dst
, esrc
, ETH_ALEN
+2); e
= e
->next
)
83 e
= (struct hash_entry
*) malloc(sizeof(*e
));
85 printlog(LOG_WARNING
,"Failed to malloc hash entry %s",strerror(errno
));
89 memcpy(&e
->dst
, esrc
, ETH_ALEN
+2);
90 if(h
[k
] != NULL
) h
[k
]->prev
= &(e
->next
);
98 e
->last_seen
= qtime();
102 #define delete_hash_entry(OLD) \
104 *((OLD)->prev)=(OLD)->next; \
105 if((OLD)->next != NULL) (OLD)->next->prev = (OLD)->prev; \
110 void delete_hash(unsigned char *dst
,int vlan
)
112 unsigned char edst
[ETH_ALEN
+2];
113 struct hash_entry
*old
= find_entry(extmac(edst
,dst
,vlan
));
115 if(old
== NULL
) return;
117 delete_hash_entry(old
);
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
)
126 struct hash_entry
*e
, *next
;
128 for(i
= 0; i
< HASH_SIZE
; i
++){
129 for(e
= h
[i
]; e
; e
= next
){
136 static void delete_port_iterator (struct hash_entry
*e
, void *arg
)
138 int *pport
=(int *)arg
;
139 if (e
->port
== *pport
)
140 delete_hash_entry(e
);
143 void hash_delete_port (int port
)
146 for_all_hash(delete_port_iterator
,&port
);
150 static void delete_vlan_iterator (struct hash_entry
*e
, void *arg
)
152 int *vlan
=(int *)arg
;
153 if (*((u_int16_t
*)(e
->dst
+ETH_ALEN
)) == (u_int16_t
)(*vlan
))
154 delete_hash_entry(e
);
157 void hash_delete_vlan (int vlan
)
160 for_all_hash(delete_vlan_iterator
,&vlan
);
164 struct vlanport
{int vlan
; int port
;};
166 static void delete_vlanport_iterator (struct hash_entry
*e
, void *arg
)
168 struct vlanport
*vp
=(struct vlanport
*)arg
;
169 if (*((u_int16_t
*)(e
->dst
+ETH_ALEN
)) == (u_int16_t
)(vp
->vlan
) &&
171 delete_hash_entry(e
);
174 void hash_delete_vlanport (int vlan
,int port
)
176 struct vlanport vp
={vlan
,port
};
178 for_all_hash(delete_vlanport_iterator
,&vp
);
182 struct vlansetofports
{int vlan
; bitarray setofports
;};
184 static void delete_vlansetofports_iterator (struct hash_entry
*e
, void *arg
)
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
);
192 void hash_delete_vlanports (int vlan
,bitarray setofports
)
194 struct vlansetofports vp
={vlan
,setofports
};
196 for_all_hash(delete_vlansetofports_iterator
,&vp
);
200 static void flush_iterator (struct hash_entry
*e
, void *arg
)
202 delete_hash_entry(e
);
208 for_all_hash(flush_iterator
,NULL
);
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
;
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
)
223 time_t t
= *(time_t *) now
;
225 if(e
->last_seen
+ gc_expire
< t
)
226 delete_hash_entry(e
);
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
)
234 for_all_hash(&gc
, &t
);
237 #define HASH_INIT(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));\
246 #define PO2ROUND(VX) \
247 ({ register int i=0; \
248 register int x=(VX)-1; \
249 while (x) { x>>=1; i++; } \
251 printlog(LOG_WARNING,"Hash size must be a power of 2. %d rounded to %d",(VX),1<<i);\
254 int hash_resize(int hash_size
)
259 HASH_INIT(PO2ROUND(hash_size
));
264 int hash_set_gc_interval(int p
)
266 qtimer_del(gc_timerno
);
268 gc_timerno
=qtimer_add(gc_interval
,0,hash_gc
,NULL
);
272 int hash_set_gc_expire(int e
)
278 int hash_get_gc_interval()
283 int hash_get_gc_expire()
288 static int find_hash(int fd
,char *strmac
)
291 unsigned char mac
[ETH_ALEN
];
292 unsigned char emac
[ETH_ALEN
+2];
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
);
299 rv
=sscanf(strmac
,"%x.%x.%x.%x.%x.%x %d", maci
+0, maci
+1, maci
+2, maci
+3, maci
+4, maci
+5, &vlan
);
304 for (i
=0;i
<ETH_ALEN
;i
++)
306 e
=find_entry(extmac(emac
,mac
,vlan
));
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
);
319 static void print_hash_entry(struct hash_entry
*e
, void *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
);
330 static int print_hash(int fd
)
333 for_all_hash(print_hash_entry
, &fd
);
338 static int showinfo(int fd
)
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
);
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
},
356 /* sets sig_alarm as handler for SIGALRM, and run it a first time */
357 void hash_init(int hash_size
)
359 HASH_INIT(PO2ROUND(hash_size
));
361 gc_interval
=GC_INTERVAL
;
363 gc_timerno
=qtimer_add(gc_interval
,0,hash_gc
,NULL
);