]>
Commit | Line | Data |
---|---|---|
5beef3c9 AL |
1 | /* |
2 | * Copyright (C) 2008-2009 B.A.T.M.A.N. contributors: | |
3 | * | |
4 | * Simon Wunderlich | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or | |
7 | * modify it under the terms of version 2 of the GNU General Public | |
8 | * License as published by the Free Software Foundation. | |
9 | * | |
10 | * This program is distributed in the hope that it will be useful, but | |
11 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | * 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 Street, Fifth Floor, Boston, MA | |
18 | * 02110-1301, USA | |
19 | * | |
20 | */ | |
21 | ||
22 | #include "main.h" | |
23 | #include "send.h" | |
24 | #include "translation-table.h" | |
25 | #include "vis.h" | |
5beef3c9 AL |
26 | #include "soft-interface.h" |
27 | #include "hard-interface.h" | |
28 | #include "hash.h" | |
29 | #include "compat.h" | |
30 | ||
31 | struct hashtable_t *vis_hash; | |
32 | DEFINE_SPINLOCK(vis_hash_lock); | |
33 | static struct vis_info *my_vis_info; | |
34 | static struct list_head send_list; /* always locked with vis_hash_lock */ | |
35 | ||
36 | static void start_vis_timer(void); | |
37 | ||
38 | /* free the info */ | |
39 | static void free_info(void *data) | |
40 | { | |
41 | struct vis_info *info = data; | |
42 | struct recvlist_node *entry, *tmp; | |
43 | ||
44 | list_del_init(&info->send_list); | |
45 | list_for_each_entry_safe(entry, tmp, &info->recv_list, list) { | |
46 | list_del(&entry->list); | |
47 | kfree(entry); | |
48 | } | |
49 | kfree(info); | |
50 | } | |
51 | ||
52 | /* set the mode of the visualization to client or server */ | |
53 | void vis_set_mode(int mode) | |
54 | { | |
55 | spin_lock(&vis_hash_lock); | |
56 | ||
57 | if (my_vis_info != NULL) | |
58 | my_vis_info->packet.vis_type = mode; | |
59 | ||
60 | spin_unlock(&vis_hash_lock); | |
61 | } | |
62 | ||
63 | /* is_vis_server(), locked outside */ | |
64 | static int is_vis_server_locked(void) | |
65 | { | |
66 | if (my_vis_info != NULL) | |
67 | if (my_vis_info->packet.vis_type == VIS_TYPE_SERVER_SYNC) | |
68 | return 1; | |
69 | ||
70 | return 0; | |
71 | } | |
72 | ||
73 | /* get the current set mode */ | |
74 | int is_vis_server(void) | |
75 | { | |
76 | int ret = 0; | |
77 | ||
78 | spin_lock(&vis_hash_lock); | |
79 | ret = is_vis_server_locked(); | |
80 | spin_unlock(&vis_hash_lock); | |
81 | ||
82 | return ret; | |
83 | } | |
84 | ||
85 | /* Compare two vis packets, used by the hashing algorithm */ | |
86 | static int vis_info_cmp(void *data1, void *data2) | |
87 | { | |
88 | struct vis_info *d1, *d2; | |
89 | d1 = data1; | |
90 | d2 = data2; | |
91 | return compare_orig(d1->packet.vis_orig, d2->packet.vis_orig); | |
92 | } | |
93 | ||
94 | /* hash function to choose an entry in a hash table of given size */ | |
95 | /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */ | |
96 | static int vis_info_choose(void *data, int size) | |
97 | { | |
98 | struct vis_info *vis_info = data; | |
99 | unsigned char *key; | |
100 | uint32_t hash = 0; | |
101 | size_t i; | |
102 | ||
103 | key = vis_info->packet.vis_orig; | |
104 | for (i = 0; i < ETH_ALEN; i++) { | |
105 | hash += key[i]; | |
106 | hash += (hash << 10); | |
107 | hash ^= (hash >> 6); | |
108 | } | |
109 | ||
110 | hash += (hash << 3); | |
111 | hash ^= (hash >> 11); | |
112 | hash += (hash << 15); | |
113 | ||
114 | return hash % size; | |
115 | } | |
116 | ||
117 | /* tries to add one entry to the receive list. */ | |
118 | static void recv_list_add(struct list_head *recv_list, char *mac) | |
119 | { | |
120 | struct recvlist_node *entry; | |
121 | entry = kmalloc(sizeof(struct recvlist_node), GFP_ATOMIC); | |
122 | if (!entry) | |
123 | return; | |
124 | ||
125 | memcpy(entry->mac, mac, ETH_ALEN); | |
126 | list_add_tail(&entry->list, recv_list); | |
127 | } | |
128 | ||
129 | /* returns 1 if this mac is in the recv_list */ | |
130 | static int recv_list_is_in(struct list_head *recv_list, char *mac) | |
131 | { | |
132 | struct recvlist_node *entry; | |
133 | ||
134 | list_for_each_entry(entry, recv_list, list) { | |
135 | if (memcmp(entry->mac, mac, ETH_ALEN) == 0) | |
136 | return 1; | |
137 | } | |
138 | ||
139 | return 0; | |
140 | } | |
141 | ||
142 | /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old, | |
143 | * broken.. ). vis hash must be locked outside. is_new is set when the packet | |
144 | * is newer than old entries in the hash. */ | |
145 | static struct vis_info *add_packet(struct vis_packet *vis_packet, | |
146 | int vis_info_len, int *is_new) | |
147 | { | |
148 | struct vis_info *info, *old_info; | |
149 | struct vis_info search_elem; | |
150 | ||
151 | *is_new = 0; | |
152 | /* sanity check */ | |
153 | if (vis_hash == NULL) | |
154 | return NULL; | |
155 | ||
156 | /* see if the packet is already in vis_hash */ | |
157 | memcpy(search_elem.packet.vis_orig, vis_packet->vis_orig, ETH_ALEN); | |
158 | old_info = hash_find(vis_hash, &search_elem); | |
159 | ||
160 | if (old_info != NULL) { | |
161 | if (vis_packet->seqno - old_info->packet.seqno <= 0) { | |
162 | if (old_info->packet.seqno == vis_packet->seqno) { | |
163 | recv_list_add(&old_info->recv_list, | |
164 | vis_packet->sender_orig); | |
165 | return old_info; | |
166 | } else { | |
167 | /* newer packet is already in hash. */ | |
168 | return NULL; | |
169 | } | |
170 | } | |
171 | /* remove old entry */ | |
172 | hash_remove(vis_hash, old_info); | |
173 | free_info(old_info); | |
174 | } | |
175 | ||
176 | info = kmalloc(sizeof(struct vis_info) + vis_info_len, GFP_ATOMIC); | |
177 | if (info == NULL) | |
178 | return NULL; | |
179 | ||
180 | INIT_LIST_HEAD(&info->send_list); | |
181 | INIT_LIST_HEAD(&info->recv_list); | |
182 | info->first_seen = jiffies; | |
183 | memcpy(&info->packet, vis_packet, | |
184 | sizeof(struct vis_packet) + vis_info_len); | |
185 | ||
186 | /* initialize and add new packet. */ | |
187 | *is_new = 1; | |
188 | ||
189 | /* repair if entries is longer than packet. */ | |
190 | if (info->packet.entries * sizeof(struct vis_info_entry) > vis_info_len) | |
191 | info->packet.entries = vis_info_len / sizeof(struct vis_info_entry); | |
192 | ||
193 | recv_list_add(&info->recv_list, info->packet.sender_orig); | |
194 | ||
195 | /* try to add it */ | |
196 | if (hash_add(vis_hash, info) < 0) { | |
197 | /* did not work (for some reason) */ | |
198 | free_info(info); | |
199 | info = NULL; | |
200 | } | |
201 | ||
202 | return info; | |
203 | } | |
204 | ||
205 | /* handle the server sync packet, forward if needed. */ | |
206 | void receive_server_sync_packet(struct vis_packet *vis_packet, int vis_info_len) | |
207 | { | |
208 | struct vis_info *info; | |
209 | int is_new; | |
210 | ||
211 | spin_lock(&vis_hash_lock); | |
212 | info = add_packet(vis_packet, vis_info_len, &is_new); | |
213 | if (info == NULL) | |
214 | goto end; | |
215 | ||
216 | /* only if we are server ourselves and packet is newer than the one in | |
217 | * hash.*/ | |
218 | if (is_vis_server_locked() && is_new) { | |
219 | memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN); | |
220 | if (list_empty(&info->send_list)) | |
221 | list_add_tail(&info->send_list, &send_list); | |
222 | } | |
223 | end: | |
224 | spin_unlock(&vis_hash_lock); | |
225 | } | |
226 | ||
227 | /* handle an incoming client update packet and schedule forward if needed. */ | |
228 | void receive_client_update_packet(struct vis_packet *vis_packet, | |
229 | int vis_info_len) | |
230 | { | |
231 | struct vis_info *info; | |
232 | int is_new; | |
233 | ||
234 | /* clients shall not broadcast. */ | |
235 | if (is_bcast(vis_packet->target_orig)) | |
236 | return; | |
237 | ||
238 | spin_lock(&vis_hash_lock); | |
239 | info = add_packet(vis_packet, vis_info_len, &is_new); | |
240 | if (info == NULL) | |
241 | goto end; | |
242 | /* note that outdated packets will be dropped at this point. */ | |
243 | ||
244 | ||
245 | /* send only if we're the target server or ... */ | |
246 | if (is_vis_server_locked() && | |
247 | is_my_mac(info->packet.target_orig) && | |
248 | is_new) { | |
249 | info->packet.vis_type = VIS_TYPE_SERVER_SYNC; /* upgrade! */ | |
250 | memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN); | |
251 | if (list_empty(&info->send_list)) | |
252 | list_add_tail(&info->send_list, &send_list); | |
253 | ||
254 | /* ... we're not the recipient (and thus need to forward). */ | |
255 | } else if (!is_my_mac(info->packet.target_orig)) { | |
256 | if (list_empty(&info->send_list)) | |
257 | list_add_tail(&info->send_list, &send_list); | |
258 | } | |
259 | end: | |
260 | spin_unlock(&vis_hash_lock); | |
261 | } | |
262 | ||
263 | /* Walk the originators and find the VIS server with the best tq. Set the packet | |
264 | * address to its address and return the best_tq. | |
265 | * | |
266 | * Must be called with the originator hash locked */ | |
267 | static int find_best_vis_server(struct vis_info *info) | |
268 | { | |
b6c35976 | 269 | HASHIT(hashit); |
5beef3c9 AL |
270 | struct orig_node *orig_node; |
271 | int best_tq = -1; | |
272 | ||
b6c35976 SW |
273 | while (hash_iterate(orig_hash, &hashit)) { |
274 | orig_node = hashit.bucket->data; | |
5beef3c9 AL |
275 | if ((orig_node != NULL) && |
276 | (orig_node->router != NULL) && | |
277 | (orig_node->flags & VIS_SERVER) && | |
278 | (orig_node->router->tq_avg > best_tq)) { | |
279 | best_tq = orig_node->router->tq_avg; | |
280 | memcpy(info->packet.target_orig, orig_node->orig, | |
281 | ETH_ALEN); | |
282 | } | |
283 | } | |
284 | return best_tq; | |
285 | } | |
286 | ||
287 | /* Return true if the vis packet is full. */ | |
288 | static bool vis_packet_full(struct vis_info *info) | |
289 | { | |
290 | if (info->packet.entries + 1 > | |
291 | (1000 - sizeof(struct vis_info)) / sizeof(struct vis_info_entry)) | |
292 | return true; | |
293 | return false; | |
294 | } | |
295 | ||
296 | /* generates a packet of own vis data, | |
297 | * returns 0 on success, -1 if no packet could be generated */ | |
298 | static int generate_vis_packet(void) | |
299 | { | |
b6c35976 SW |
300 | HASHIT(hashit_local); |
301 | HASHIT(hashit_global); | |
5beef3c9 AL |
302 | struct orig_node *orig_node; |
303 | struct vis_info *info = (struct vis_info *)my_vis_info; | |
304 | struct vis_info_entry *entry, *entry_array; | |
305 | struct hna_local_entry *hna_local_entry; | |
306 | int best_tq = -1; | |
307 | unsigned long flags; | |
308 | ||
309 | info->first_seen = jiffies; | |
310 | ||
311 | spin_lock(&orig_hash_lock); | |
312 | memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN); | |
313 | info->packet.ttl = TTL; | |
314 | info->packet.seqno++; | |
315 | info->packet.entries = 0; | |
316 | ||
317 | if (!is_vis_server_locked()) { | |
318 | best_tq = find_best_vis_server(info); | |
319 | if (best_tq < 0) { | |
320 | spin_unlock(&orig_hash_lock); | |
321 | return -1; | |
322 | } | |
323 | } | |
5beef3c9 AL |
324 | |
325 | entry_array = (struct vis_info_entry *) | |
326 | ((char *)info + sizeof(struct vis_info)); | |
327 | ||
b6c35976 SW |
328 | while (hash_iterate(orig_hash, &hashit_global)) { |
329 | orig_node = hashit_global.bucket->data; | |
5beef3c9 AL |
330 | if (orig_node->router != NULL |
331 | && compare_orig(orig_node->router->addr, orig_node->orig) | |
332 | && orig_node->batman_if | |
333 | && (orig_node->batman_if->if_active == IF_ACTIVE) | |
334 | && orig_node->router->tq_avg > 0) { | |
335 | ||
336 | /* fill one entry into buffer. */ | |
337 | entry = &entry_array[info->packet.entries]; | |
338 | memcpy(entry->src, orig_node->batman_if->net_dev->dev_addr, ETH_ALEN); | |
339 | memcpy(entry->dest, orig_node->orig, ETH_ALEN); | |
340 | entry->quality = orig_node->router->tq_avg; | |
341 | info->packet.entries++; | |
342 | ||
343 | if (vis_packet_full(info)) { | |
344 | spin_unlock(&orig_hash_lock); | |
345 | return 0; | |
346 | } | |
347 | } | |
348 | } | |
349 | ||
350 | spin_unlock(&orig_hash_lock); | |
351 | ||
5beef3c9 | 352 | spin_lock_irqsave(&hna_local_hash_lock, flags); |
b6c35976 SW |
353 | while (hash_iterate(hna_local_hash, &hashit_local)) { |
354 | hna_local_entry = hashit_local.bucket->data; | |
5beef3c9 AL |
355 | entry = &entry_array[info->packet.entries]; |
356 | memset(entry->src, 0, ETH_ALEN); | |
357 | memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN); | |
358 | entry->quality = 0; /* 0 means HNA */ | |
359 | info->packet.entries++; | |
360 | ||
361 | if (vis_packet_full(info)) { | |
362 | spin_unlock_irqrestore(&hna_local_hash_lock, flags); | |
363 | return 0; | |
364 | } | |
365 | } | |
366 | spin_unlock_irqrestore(&hna_local_hash_lock, flags); | |
367 | return 0; | |
368 | } | |
369 | ||
370 | static void purge_vis_packets(void) | |
371 | { | |
b6c35976 | 372 | HASHIT(hashit); |
5beef3c9 AL |
373 | struct vis_info *info; |
374 | ||
b6c35976 SW |
375 | while (hash_iterate(vis_hash, &hashit)) { |
376 | info = hashit.bucket->data; | |
5beef3c9 AL |
377 | if (info == my_vis_info) /* never purge own data. */ |
378 | continue; | |
379 | if (time_after(jiffies, | |
9bbf1ecd | 380 | info->first_seen + (VIS_TIMEOUT*HZ)/1000)) { |
b6c35976 | 381 | hash_remove_bucket(vis_hash, &hashit); |
5beef3c9 AL |
382 | free_info(info); |
383 | } | |
384 | } | |
385 | } | |
386 | ||
387 | static void broadcast_vis_packet(struct vis_info *info, int packet_length) | |
388 | { | |
b6c35976 | 389 | HASHIT(hashit); |
5beef3c9 AL |
390 | struct orig_node *orig_node; |
391 | ||
392 | spin_lock(&orig_hash_lock); | |
393 | ||
394 | /* send to all routers in range. */ | |
b6c35976 SW |
395 | while (hash_iterate(orig_hash, &hashit)) { |
396 | orig_node = hashit.bucket->data; | |
5beef3c9 AL |
397 | |
398 | /* if it's a vis server and reachable, send it. */ | |
399 | if (orig_node && | |
400 | (orig_node->flags & VIS_SERVER) && | |
401 | orig_node->batman_if && | |
402 | orig_node->router) { | |
403 | ||
404 | /* don't send it if we already received the packet from | |
405 | * this node. */ | |
406 | if (recv_list_is_in(&info->recv_list, orig_node->orig)) | |
407 | continue; | |
408 | ||
409 | memcpy(info->packet.target_orig, | |
410 | orig_node->orig, ETH_ALEN); | |
411 | ||
412 | send_raw_packet((unsigned char *) &info->packet, | |
413 | packet_length, | |
414 | orig_node->batman_if, | |
415 | orig_node->router->addr); | |
416 | } | |
417 | } | |
418 | memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN); | |
419 | spin_unlock(&orig_hash_lock); | |
420 | } | |
421 | ||
422 | static void unicast_vis_packet(struct vis_info *info, int packet_length) | |
423 | { | |
424 | struct orig_node *orig_node; | |
425 | ||
426 | spin_lock(&orig_hash_lock); | |
427 | orig_node = ((struct orig_node *) | |
428 | hash_find(orig_hash, info->packet.target_orig)); | |
429 | ||
430 | if ((orig_node != NULL) && | |
431 | (orig_node->batman_if != NULL) && | |
432 | (orig_node->router != NULL)) { | |
433 | send_raw_packet((unsigned char *) &info->packet, packet_length, | |
434 | orig_node->batman_if, | |
435 | orig_node->router->addr); | |
436 | } | |
437 | spin_unlock(&orig_hash_lock); | |
438 | } | |
439 | ||
440 | /* only send one vis packet. called from send_vis_packets() */ | |
441 | static void send_vis_packet(struct vis_info *info) | |
442 | { | |
443 | int packet_length; | |
444 | ||
445 | if (info->packet.ttl < 2) { | |
bad2239e | 446 | printk(KERN_WARNING "batman-adv: Error - can't send vis packet: ttl exceeded\n"); |
5beef3c9 AL |
447 | return; |
448 | } | |
449 | ||
450 | memcpy(info->packet.sender_orig, mainIfAddr, ETH_ALEN); | |
451 | info->packet.ttl--; | |
452 | ||
453 | packet_length = sizeof(struct vis_packet) + | |
454 | info->packet.entries * sizeof(struct vis_info_entry); | |
455 | ||
456 | if (is_bcast(info->packet.target_orig)) | |
457 | broadcast_vis_packet(info, packet_length); | |
458 | else | |
459 | unicast_vis_packet(info, packet_length); | |
460 | info->packet.ttl++; /* restore TTL */ | |
461 | } | |
462 | ||
463 | /* called from timer; send (and maybe generate) vis packet. */ | |
464 | static void send_vis_packets(struct work_struct *work) | |
465 | { | |
466 | struct vis_info *info, *temp; | |
467 | ||
468 | spin_lock(&vis_hash_lock); | |
469 | purge_vis_packets(); | |
470 | ||
471 | if (generate_vis_packet() == 0) | |
472 | /* schedule if generation was successful */ | |
473 | list_add_tail(&my_vis_info->send_list, &send_list); | |
474 | ||
475 | list_for_each_entry_safe(info, temp, &send_list, send_list) { | |
476 | list_del_init(&info->send_list); | |
477 | send_vis_packet(info); | |
478 | } | |
479 | spin_unlock(&vis_hash_lock); | |
480 | start_vis_timer(); | |
481 | } | |
482 | static DECLARE_DELAYED_WORK(vis_timer_wq, send_vis_packets); | |
483 | ||
484 | /* init the vis server. this may only be called when if_list is already | |
485 | * initialized (e.g. bat0 is initialized, interfaces have been added) */ | |
486 | int vis_init(void) | |
487 | { | |
488 | if (vis_hash) | |
489 | return 1; | |
490 | ||
491 | spin_lock(&vis_hash_lock); | |
492 | ||
493 | vis_hash = hash_new(256, vis_info_cmp, vis_info_choose); | |
494 | if (!vis_hash) { | |
bad2239e | 495 | printk(KERN_ERR "batman-adv:Can't initialize vis_hash\n"); |
5beef3c9 AL |
496 | goto err; |
497 | } | |
498 | ||
499 | my_vis_info = kmalloc(1000, GFP_ATOMIC); | |
500 | if (!my_vis_info) { | |
bad2239e | 501 | printk(KERN_ERR "batman-adv:Can't initialize vis packet\n"); |
5beef3c9 AL |
502 | goto err; |
503 | } | |
504 | ||
505 | /* prefill the vis info */ | |
506 | my_vis_info->first_seen = jiffies - atomic_read(&vis_interval); | |
507 | INIT_LIST_HEAD(&my_vis_info->recv_list); | |
508 | INIT_LIST_HEAD(&my_vis_info->send_list); | |
509 | my_vis_info->packet.version = COMPAT_VERSION; | |
510 | my_vis_info->packet.packet_type = BAT_VIS; | |
511 | my_vis_info->packet.vis_type = VIS_TYPE_CLIENT_UPDATE; | |
512 | my_vis_info->packet.ttl = TTL; | |
513 | my_vis_info->packet.seqno = 0; | |
514 | my_vis_info->packet.entries = 0; | |
515 | ||
516 | INIT_LIST_HEAD(&send_list); | |
517 | ||
518 | memcpy(my_vis_info->packet.vis_orig, mainIfAddr, ETH_ALEN); | |
519 | memcpy(my_vis_info->packet.sender_orig, mainIfAddr, ETH_ALEN); | |
520 | ||
521 | if (hash_add(vis_hash, my_vis_info) < 0) { | |
bad2239e AL |
522 | printk(KERN_ERR |
523 | "batman-adv:Can't add own vis packet into hash\n"); | |
5beef3c9 AL |
524 | free_info(my_vis_info); /* not in hash, need to remove it |
525 | * manually. */ | |
526 | goto err; | |
527 | } | |
528 | ||
529 | spin_unlock(&vis_hash_lock); | |
530 | start_vis_timer(); | |
531 | return 1; | |
532 | ||
533 | err: | |
534 | spin_unlock(&vis_hash_lock); | |
535 | vis_quit(); | |
536 | return 0; | |
537 | } | |
538 | ||
539 | /* shutdown vis-server */ | |
540 | void vis_quit(void) | |
541 | { | |
542 | if (!vis_hash) | |
543 | return; | |
544 | ||
545 | cancel_delayed_work_sync(&vis_timer_wq); | |
546 | ||
547 | spin_lock(&vis_hash_lock); | |
548 | /* properly remove, kill timers ... */ | |
549 | hash_delete(vis_hash, free_info); | |
550 | vis_hash = NULL; | |
551 | my_vis_info = NULL; | |
552 | spin_unlock(&vis_hash_lock); | |
553 | } | |
554 | ||
555 | /* schedule packets for (re)transmission */ | |
556 | static void start_vis_timer(void) | |
557 | { | |
558 | queue_delayed_work(bat_event_workqueue, &vis_timer_wq, | |
9bbf1ecd | 559 | (atomic_read(&vis_interval) * HZ) / 1000); |
5beef3c9 AL |
560 | } |
561 |