2 * Copyright (C) 2008-2009 B.A.T.M.A.N. contributors:
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.
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.
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
24 #include "translation-table.h"
27 #include "soft-interface.h"
28 #include "hard-interface.h"
32 struct hashtable_t
*vis_hash
;
33 DEFINE_SPINLOCK(vis_hash_lock
);
34 static struct vis_info
*my_vis_info
;
35 static struct list_head send_list
; /* always locked with vis_hash_lock */
37 static void start_vis_timer(void);
40 static void free_info(void *data
)
42 struct vis_info
*info
= data
;
43 struct recvlist_node
*entry
, *tmp
;
45 list_del_init(&info
->send_list
);
46 list_for_each_entry_safe(entry
, tmp
, &info
->recv_list
, list
) {
47 list_del(&entry
->list
);
53 /* set the mode of the visualization to client or server */
54 void vis_set_mode(int mode
)
56 spin_lock(&vis_hash_lock
);
58 if (my_vis_info
!= NULL
)
59 my_vis_info
->packet
.vis_type
= mode
;
61 spin_unlock(&vis_hash_lock
);
64 /* is_vis_server(), locked outside */
65 static int is_vis_server_locked(void)
67 if (my_vis_info
!= NULL
)
68 if (my_vis_info
->packet
.vis_type
== VIS_TYPE_SERVER_SYNC
)
74 /* get the current set mode */
75 int is_vis_server(void)
79 spin_lock(&vis_hash_lock
);
80 ret
= is_vis_server_locked();
81 spin_unlock(&vis_hash_lock
);
86 /* Compare two vis packets, used by the hashing algorithm */
87 static int vis_info_cmp(void *data1
, void *data2
)
89 struct vis_info
*d1
, *d2
;
92 return compare_orig(d1
->packet
.vis_orig
, d2
->packet
.vis_orig
);
95 /* hash function to choose an entry in a hash table of given size */
96 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
97 static int vis_info_choose(void *data
, int size
)
99 struct vis_info
*vis_info
= data
;
104 key
= vis_info
->packet
.vis_orig
;
105 for (i
= 0; i
< ETH_ALEN
; i
++) {
107 hash
+= (hash
<< 10);
112 hash
^= (hash
>> 11);
113 hash
+= (hash
<< 15);
118 /* tries to add one entry to the receive list. */
119 static void recv_list_add(struct list_head
*recv_list
, char *mac
)
121 struct recvlist_node
*entry
;
122 entry
= kmalloc(sizeof(struct recvlist_node
), GFP_ATOMIC
);
126 memcpy(entry
->mac
, mac
, ETH_ALEN
);
127 list_add_tail(&entry
->list
, recv_list
);
130 /* returns 1 if this mac is in the recv_list */
131 static int recv_list_is_in(struct list_head
*recv_list
, char *mac
)
133 struct recvlist_node
*entry
;
135 list_for_each_entry(entry
, recv_list
, list
) {
136 if (memcmp(entry
->mac
, mac
, ETH_ALEN
) == 0)
143 /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old,
144 * broken.. ). vis hash must be locked outside. is_new is set when the packet
145 * is newer than old entries in the hash. */
146 static struct vis_info
*add_packet(struct vis_packet
*vis_packet
,
147 int vis_info_len
, int *is_new
)
149 struct vis_info
*info
, *old_info
;
150 struct vis_info search_elem
;
154 if (vis_hash
== NULL
)
157 /* see if the packet is already in vis_hash */
158 memcpy(search_elem
.packet
.vis_orig
, vis_packet
->vis_orig
, ETH_ALEN
);
159 old_info
= hash_find(vis_hash
, &search_elem
);
161 if (old_info
!= NULL
) {
162 if (vis_packet
->seqno
- old_info
->packet
.seqno
<= 0) {
163 if (old_info
->packet
.seqno
== vis_packet
->seqno
) {
164 recv_list_add(&old_info
->recv_list
,
165 vis_packet
->sender_orig
);
168 /* newer packet is already in hash. */
172 /* remove old entry */
173 hash_remove(vis_hash
, old_info
);
177 info
= kmalloc(sizeof(struct vis_info
) + vis_info_len
, GFP_ATOMIC
);
181 INIT_LIST_HEAD(&info
->send_list
);
182 INIT_LIST_HEAD(&info
->recv_list
);
183 info
->first_seen
= jiffies
;
184 memcpy(&info
->packet
, vis_packet
,
185 sizeof(struct vis_packet
) + vis_info_len
);
187 /* initialize and add new packet. */
190 /* repair if entries is longer than packet. */
191 if (info
->packet
.entries
* sizeof(struct vis_info_entry
) > vis_info_len
)
192 info
->packet
.entries
= vis_info_len
/ sizeof(struct vis_info_entry
);
194 recv_list_add(&info
->recv_list
, info
->packet
.sender_orig
);
197 if (hash_add(vis_hash
, info
) < 0) {
198 /* did not work (for some reason) */
206 /* handle the server sync packet, forward if needed. */
207 void receive_server_sync_packet(struct vis_packet
*vis_packet
, int vis_info_len
)
209 struct vis_info
*info
;
212 spin_lock(&vis_hash_lock
);
213 info
= add_packet(vis_packet
, vis_info_len
, &is_new
);
217 /* only if we are server ourselves and packet is newer than the one in
219 if (is_vis_server_locked() && is_new
) {
220 memcpy(info
->packet
.target_orig
, broadcastAddr
, ETH_ALEN
);
221 if (list_empty(&info
->send_list
))
222 list_add_tail(&info
->send_list
, &send_list
);
225 spin_unlock(&vis_hash_lock
);
228 /* handle an incoming client update packet and schedule forward if needed. */
229 void receive_client_update_packet(struct vis_packet
*vis_packet
,
232 struct vis_info
*info
;
235 /* clients shall not broadcast. */
236 if (is_bcast(vis_packet
->target_orig
))
239 spin_lock(&vis_hash_lock
);
240 info
= add_packet(vis_packet
, vis_info_len
, &is_new
);
243 /* note that outdated packets will be dropped at this point. */
246 /* send only if we're the target server or ... */
247 if (is_vis_server_locked() &&
248 is_my_mac(info
->packet
.target_orig
) &&
250 info
->packet
.vis_type
= VIS_TYPE_SERVER_SYNC
; /* upgrade! */
251 memcpy(info
->packet
.target_orig
, broadcastAddr
, ETH_ALEN
);
252 if (list_empty(&info
->send_list
))
253 list_add_tail(&info
->send_list
, &send_list
);
255 /* ... we're not the recipient (and thus need to forward). */
256 } else if (!is_my_mac(info
->packet
.target_orig
)) {
257 if (list_empty(&info
->send_list
))
258 list_add_tail(&info
->send_list
, &send_list
);
261 spin_unlock(&vis_hash_lock
);
264 /* Walk the originators and find the VIS server with the best tq. Set the packet
265 * address to its address and return the best_tq.
267 * Must be called with the originator hash locked */
268 static int find_best_vis_server(struct vis_info
*info
)
270 struct hash_it_t
*hashit
= NULL
;
271 struct orig_node
*orig_node
;
274 while (NULL
!= (hashit
= hash_iterate(orig_hash
, hashit
))) {
275 orig_node
= hashit
->bucket
->data
;
276 if ((orig_node
!= NULL
) &&
277 (orig_node
->router
!= NULL
) &&
278 (orig_node
->flags
& VIS_SERVER
) &&
279 (orig_node
->router
->tq_avg
> best_tq
)) {
280 best_tq
= orig_node
->router
->tq_avg
;
281 memcpy(info
->packet
.target_orig
, orig_node
->orig
,
288 /* Return true if the vis packet is full. */
289 static bool vis_packet_full(struct vis_info
*info
)
291 if (info
->packet
.entries
+ 1 >
292 (1000 - sizeof(struct vis_info
)) / sizeof(struct vis_info_entry
))
297 /* generates a packet of own vis data,
298 * returns 0 on success, -1 if no packet could be generated */
299 static int generate_vis_packet(void)
301 struct hash_it_t
*hashit
= NULL
;
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
;
309 info
->first_seen
= jiffies
;
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;
317 if (!is_vis_server_locked()) {
318 best_tq
= find_best_vis_server(info
);
320 spin_unlock(&orig_hash_lock
);
326 entry_array
= (struct vis_info_entry
*)
327 ((char *)info
+ sizeof(struct vis_info
));
329 while (NULL
!= (hashit
= hash_iterate(orig_hash
, hashit
))) {
330 orig_node
= hashit
->bucket
->data
;
331 if (orig_node
->router
!= NULL
332 && compare_orig(orig_node
->router
->addr
, orig_node
->orig
)
333 && orig_node
->batman_if
334 && (orig_node
->batman_if
->if_active
== IF_ACTIVE
)
335 && orig_node
->router
->tq_avg
> 0) {
337 /* fill one entry into buffer. */
338 entry
= &entry_array
[info
->packet
.entries
];
339 memcpy(entry
->src
, orig_node
->batman_if
->net_dev
->dev_addr
, ETH_ALEN
);
340 memcpy(entry
->dest
, orig_node
->orig
, ETH_ALEN
);
341 entry
->quality
= orig_node
->router
->tq_avg
;
342 info
->packet
.entries
++;
344 if (vis_packet_full(info
)) {
345 spin_unlock(&orig_hash_lock
);
351 spin_unlock(&orig_hash_lock
);
354 spin_lock_irqsave(&hna_local_hash_lock
, flags
);
355 while (NULL
!= (hashit
= hash_iterate(hna_local_hash
, hashit
))) {
356 hna_local_entry
= hashit
->bucket
->data
;
357 entry
= &entry_array
[info
->packet
.entries
];
358 memset(entry
->src
, 0, ETH_ALEN
);
359 memcpy(entry
->dest
, hna_local_entry
->addr
, ETH_ALEN
);
360 entry
->quality
= 0; /* 0 means HNA */
361 info
->packet
.entries
++;
363 if (vis_packet_full(info
)) {
364 spin_unlock_irqrestore(&hna_local_hash_lock
, flags
);
368 spin_unlock_irqrestore(&hna_local_hash_lock
, flags
);
372 static void purge_vis_packets(void)
374 struct hash_it_t
*hashit
= NULL
;
375 struct vis_info
*info
;
377 while (NULL
!= (hashit
= hash_iterate(vis_hash
, hashit
))) {
378 info
= hashit
->bucket
->data
;
379 if (info
== my_vis_info
) /* never purge own data. */
381 if (time_after(jiffies
,
382 info
->first_seen
+ (VIS_TIMEOUT
/1000)*HZ
)) {
383 hash_remove_bucket(vis_hash
, hashit
);
389 static void broadcast_vis_packet(struct vis_info
*info
, int packet_length
)
391 struct hash_it_t
*hashit
= NULL
;
392 struct orig_node
*orig_node
;
394 spin_lock(&orig_hash_lock
);
396 /* send to all routers in range. */
397 while (NULL
!= (hashit
= hash_iterate(orig_hash
, hashit
))) {
398 orig_node
= hashit
->bucket
->data
;
400 /* if it's a vis server and reachable, send it. */
402 (orig_node
->flags
& VIS_SERVER
) &&
403 orig_node
->batman_if
&&
406 /* don't send it if we already received the packet from
408 if (recv_list_is_in(&info
->recv_list
, orig_node
->orig
))
411 memcpy(info
->packet
.target_orig
,
412 orig_node
->orig
, ETH_ALEN
);
414 send_raw_packet((unsigned char *) &info
->packet
,
416 orig_node
->batman_if
,
417 orig_node
->router
->addr
);
420 memcpy(info
->packet
.target_orig
, broadcastAddr
, ETH_ALEN
);
421 spin_unlock(&orig_hash_lock
);
424 static void unicast_vis_packet(struct vis_info
*info
, int packet_length
)
426 struct orig_node
*orig_node
;
428 spin_lock(&orig_hash_lock
);
429 orig_node
= ((struct orig_node
*)
430 hash_find(orig_hash
, info
->packet
.target_orig
));
432 if ((orig_node
!= NULL
) &&
433 (orig_node
->batman_if
!= NULL
) &&
434 (orig_node
->router
!= NULL
)) {
435 send_raw_packet((unsigned char *) &info
->packet
, packet_length
,
436 orig_node
->batman_if
,
437 orig_node
->router
->addr
);
439 spin_unlock(&orig_hash_lock
);
442 /* only send one vis packet. called from send_vis_packets() */
443 static void send_vis_packet(struct vis_info
*info
)
447 if (info
->packet
.ttl
< 2) {
448 debug_log(LOG_TYPE_NOTICE
,
449 "Error - can't send vis packet: ttl exceeded\n");
453 memcpy(info
->packet
.sender_orig
, mainIfAddr
, ETH_ALEN
);
456 packet_length
= sizeof(struct vis_packet
) +
457 info
->packet
.entries
* sizeof(struct vis_info_entry
);
459 if (is_bcast(info
->packet
.target_orig
))
460 broadcast_vis_packet(info
, packet_length
);
462 unicast_vis_packet(info
, packet_length
);
463 info
->packet
.ttl
++; /* restore TTL */
466 /* called from timer; send (and maybe generate) vis packet. */
467 static void send_vis_packets(struct work_struct
*work
)
469 struct vis_info
*info
, *temp
;
471 spin_lock(&vis_hash_lock
);
474 if (generate_vis_packet() == 0)
475 /* schedule if generation was successful */
476 list_add_tail(&my_vis_info
->send_list
, &send_list
);
478 list_for_each_entry_safe(info
, temp
, &send_list
, send_list
) {
479 list_del_init(&info
->send_list
);
480 send_vis_packet(info
);
482 spin_unlock(&vis_hash_lock
);
485 static DECLARE_DELAYED_WORK(vis_timer_wq
, send_vis_packets
);
487 /* init the vis server. this may only be called when if_list is already
488 * initialized (e.g. bat0 is initialized, interfaces have been added) */
494 spin_lock(&vis_hash_lock
);
496 vis_hash
= hash_new(256, vis_info_cmp
, vis_info_choose
);
498 debug_log(LOG_TYPE_CRIT
, "Can't initialize vis_hash\n");
502 my_vis_info
= kmalloc(1000, GFP_ATOMIC
);
504 debug_log(LOG_TYPE_CRIT
, "Can't initialize vis packet\n");
508 /* prefill the vis info */
509 my_vis_info
->first_seen
= jiffies
- atomic_read(&vis_interval
);
510 INIT_LIST_HEAD(&my_vis_info
->recv_list
);
511 INIT_LIST_HEAD(&my_vis_info
->send_list
);
512 my_vis_info
->packet
.version
= COMPAT_VERSION
;
513 my_vis_info
->packet
.packet_type
= BAT_VIS
;
514 my_vis_info
->packet
.vis_type
= VIS_TYPE_CLIENT_UPDATE
;
515 my_vis_info
->packet
.ttl
= TTL
;
516 my_vis_info
->packet
.seqno
= 0;
517 my_vis_info
->packet
.entries
= 0;
519 INIT_LIST_HEAD(&send_list
);
521 memcpy(my_vis_info
->packet
.vis_orig
, mainIfAddr
, ETH_ALEN
);
522 memcpy(my_vis_info
->packet
.sender_orig
, mainIfAddr
, ETH_ALEN
);
524 if (hash_add(vis_hash
, my_vis_info
) < 0) {
525 debug_log(LOG_TYPE_CRIT
,
526 "Can't add own vis packet into hash\n");
527 free_info(my_vis_info
); /* not in hash, need to remove it
532 spin_unlock(&vis_hash_lock
);
537 spin_unlock(&vis_hash_lock
);
542 /* shutdown vis-server */
548 cancel_delayed_work_sync(&vis_timer_wq
);
550 spin_lock(&vis_hash_lock
);
551 /* properly remove, kill timers ... */
552 hash_delete(vis_hash
, free_info
);
555 spin_unlock(&vis_hash_lock
);
558 /* schedule packets for (re)transmission */
559 static void start_vis_timer(void)
561 queue_delayed_work(bat_event_workqueue
, &vis_timer_wq
,
562 (atomic_read(&vis_interval
)/1000) * HZ
);