2 * Copyright (C) 2008-2010 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"
26 #include "soft-interface.h"
27 #include "hard-interface.h"
30 /* Returns the smallest signed integer in two's complement with the sizeof x */
31 #define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u)))
33 /* Checks if a sequence number x is a predecessor/successor of y.
34 they handle overflows/underflows and can correctly check for a
35 predecessor/successor unless the variable sequence number has grown by
36 more then 2**(bitwidth(x)-1)-1.
37 This means that for a uint8_t with the maximum value 255, it would think:
38 * when adding nothing - it is neither a predecessor nor a successor
39 * before adding more than 127 to the starting value - it is a predecessor,
40 * when adding 128 - it is neither a predecessor nor a successor,
41 * after adding more than 127 to the starting value - it is a successor */
42 #define seq_before(x, y) ({typeof(x) _dummy = (x - y); \
43 _dummy > smallest_signed_int(_dummy); })
44 #define seq_after(x, y) seq_before(y, x)
46 struct hashtable_t *vis_hash;
47 DEFINE_SPINLOCK(vis_hash_lock);
48 static DEFINE_SPINLOCK(recv_list_lock);
49 static struct vis_info *my_vis_info;
50 static struct list_head send_list; /* always locked with vis_hash_lock */
52 static void start_vis_timer(void);
55 static void free_info(struct kref *ref)
57 struct vis_info *info = container_of(ref, struct vis_info, refcount);
58 struct recvlist_node *entry, *tmp;
61 list_del_init(&info->send_list);
62 spin_lock_irqsave(&recv_list_lock, flags);
63 list_for_each_entry_safe(entry, tmp, &info->recv_list, list) {
64 list_del(&entry->list);
67 spin_unlock_irqrestore(&recv_list_lock, flags);
71 /* Compare two vis packets, used by the hashing algorithm */
72 static int vis_info_cmp(void *data1, void *data2)
74 struct vis_info *d1, *d2;
77 return compare_orig(d1->packet.vis_orig, d2->packet.vis_orig);
80 /* hash function to choose an entry in a hash table of given size */
81 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
82 static int vis_info_choose(void *data, int size)
84 struct vis_info *vis_info = data;
89 key = vis_info->packet.vis_orig;
90 for (i = 0; i < ETH_ALEN; i++) {
103 /* insert interface to the list of interfaces of one originator, if it
104 * does not already exist in the list */
105 void proc_vis_insert_interface(const uint8_t *interface,
106 struct hlist_head *if_list,
109 struct if_list_entry *entry;
110 struct hlist_node *pos;
112 hlist_for_each_entry(entry, pos, if_list, list) {
113 if (compare_orig(entry->addr, (void *)interface))
117 /* its a new address, add it to the list */
118 entry = kmalloc(sizeof(*entry), GFP_KERNEL);
121 memcpy(entry->addr, interface, ETH_ALEN);
122 entry->primary = primary;
123 hlist_add_head(&entry->list, if_list);
126 void proc_vis_read_prim_sec(struct seq_file *seq,
127 struct hlist_head *if_list)
129 struct if_list_entry *entry;
130 struct hlist_node *pos;
131 char tmp_addr_str[ETH_STR_LEN];
133 hlist_for_each_entry(entry, pos, if_list, list) {
135 seq_printf(seq, "PRIMARY, ");
137 addr_to_string(tmp_addr_str, entry->addr);
138 seq_printf(seq, "SEC %s, ", tmp_addr_str);
144 void proc_vis_read_entry(struct seq_file *seq,
145 struct vis_info_entry *entry,
151 addr_to_string(to, entry->dest);
152 if (primary && entry->quality == 0)
153 seq_printf(seq, "HNA %s, ", to);
154 else if (compare_orig(entry->src, src))
155 seq_printf(seq, "TQ %s %d, ", to, entry->quality);
158 /* add the info packet to the send list, if it was not
159 * already linked in. */
160 static void send_list_add(struct vis_info *info)
162 if (list_empty(&info->send_list)) {
163 kref_get(&info->refcount);
164 list_add_tail(&info->send_list, &send_list);
168 /* delete the info packet from the send list, if it was
170 static void send_list_del(struct vis_info *info)
172 if (!list_empty(&info->send_list)) {
173 list_del_init(&info->send_list);
174 kref_put(&info->refcount, free_info);
178 /* tries to add one entry to the receive list. */
179 static void recv_list_add(struct list_head *recv_list, char *mac)
181 struct recvlist_node *entry;
184 entry = kmalloc(sizeof(struct recvlist_node), GFP_ATOMIC);
188 memcpy(entry->mac, mac, ETH_ALEN);
189 spin_lock_irqsave(&recv_list_lock, flags);
190 list_add_tail(&entry->list, recv_list);
191 spin_unlock_irqrestore(&recv_list_lock, flags);
194 /* returns 1 if this mac is in the recv_list */
195 static int recv_list_is_in(struct list_head *recv_list, char *mac)
197 struct recvlist_node *entry;
200 spin_lock_irqsave(&recv_list_lock, flags);
201 list_for_each_entry(entry, recv_list, list) {
202 if (memcmp(entry->mac, mac, ETH_ALEN) == 0) {
203 spin_unlock_irqrestore(&recv_list_lock, flags);
207 spin_unlock_irqrestore(&recv_list_lock, flags);
211 /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old,
212 * broken.. ). vis hash must be locked outside. is_new is set when the packet
213 * is newer than old entries in the hash. */
214 static struct vis_info *add_packet(struct vis_packet *vis_packet,
215 int vis_info_len, int *is_new,
218 struct vis_info *info, *old_info;
219 struct vis_info search_elem;
223 if (vis_hash == NULL)
226 /* see if the packet is already in vis_hash */
227 memcpy(search_elem.packet.vis_orig, vis_packet->vis_orig, ETH_ALEN);
228 old_info = hash_find(vis_hash, &search_elem);
230 if (old_info != NULL) {
231 if (!seq_after(vis_packet->seqno, old_info->packet.seqno)) {
232 if (old_info->packet.seqno == vis_packet->seqno) {
233 recv_list_add(&old_info->recv_list,
234 vis_packet->sender_orig);
237 /* newer packet is already in hash. */
241 /* remove old entry */
242 hash_remove(vis_hash, old_info);
243 send_list_del(old_info);
244 kref_put(&old_info->refcount, free_info);
247 info = kmalloc(sizeof(struct vis_info) + vis_info_len, GFP_ATOMIC);
251 kref_init(&info->refcount);
252 INIT_LIST_HEAD(&info->send_list);
253 INIT_LIST_HEAD(&info->recv_list);
254 info->first_seen = jiffies;
255 memcpy(&info->packet, vis_packet,
256 sizeof(struct vis_packet) + vis_info_len);
258 /* initialize and add new packet. */
261 /* Make it a broadcast packet, if required */
263 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
265 /* repair if entries is longer than packet. */
266 if (info->packet.entries * sizeof(struct vis_info_entry) > vis_info_len)
267 info->packet.entries = vis_info_len /
268 sizeof(struct vis_info_entry);
270 recv_list_add(&info->recv_list, info->packet.sender_orig);
273 if (hash_add(vis_hash, info) < 0) {
274 /* did not work (for some reason) */
275 kref_put(&old_info->refcount, free_info);
282 /* handle the server sync packet, forward if needed. */
283 void receive_server_sync_packet(struct vis_packet *vis_packet, int vis_info_len)
285 struct vis_info *info;
286 int is_new, make_broadcast;
288 int vis_server = atomic_read(&vis_mode);
290 make_broadcast = (vis_server == VIS_TYPE_SERVER_SYNC);
292 spin_lock_irqsave(&vis_hash_lock, flags);
293 info = add_packet(vis_packet, vis_info_len, &is_new, make_broadcast);
297 /* only if we are server ourselves and packet is newer than the one in
299 if (vis_server == VIS_TYPE_SERVER_SYNC && is_new)
302 spin_unlock_irqrestore(&vis_hash_lock, flags);
305 /* handle an incoming client update packet and schedule forward if needed. */
306 void receive_client_update_packet(struct vis_packet *vis_packet,
309 struct vis_info *info;
312 int vis_server = atomic_read(&vis_mode);
315 /* clients shall not broadcast. */
316 if (is_bcast(vis_packet->target_orig))
319 /* Are we the target for this VIS packet? */
320 if (vis_server == VIS_TYPE_SERVER_SYNC &&
321 is_my_mac(vis_packet->target_orig))
324 spin_lock_irqsave(&vis_hash_lock, flags);
325 info = add_packet(vis_packet, vis_info_len, &is_new, are_target);
328 /* note that outdated packets will be dropped at this point. */
331 /* send only if we're the target server or ... */
332 if (are_target && is_new) {
333 info->packet.vis_type = VIS_TYPE_SERVER_SYNC; /* upgrade! */
336 /* ... we're not the recipient (and thus need to forward). */
337 } else if (!is_my_mac(info->packet.target_orig)) {
341 spin_unlock_irqrestore(&vis_hash_lock, flags);
344 /* Walk the originators and find the VIS server with the best tq. Set the packet
345 * address to its address and return the best_tq.
347 * Must be called with the originator hash locked */
348 static int find_best_vis_server(struct vis_info *info)
351 struct orig_node *orig_node;
354 while (hash_iterate(orig_hash, &hashit)) {
355 orig_node = hashit.bucket->data;
356 if ((orig_node != NULL) &&
357 (orig_node->router != NULL) &&
358 (orig_node->flags & VIS_SERVER) &&
359 (orig_node->router->tq_avg > best_tq)) {
360 best_tq = orig_node->router->tq_avg;
361 memcpy(info->packet.target_orig, orig_node->orig,
368 /* Return true if the vis packet is full. */
369 static bool vis_packet_full(struct vis_info *info)
371 if (info->packet.entries + 1 >
372 (1000 - sizeof(struct vis_info)) / sizeof(struct vis_info_entry))
377 /* generates a packet of own vis data,
378 * returns 0 on success, -1 if no packet could be generated */
379 static int generate_vis_packet(void)
381 HASHIT(hashit_local);
382 HASHIT(hashit_global);
383 struct orig_node *orig_node;
384 struct vis_info *info = (struct vis_info *)my_vis_info;
385 struct vis_info_entry *entry, *entry_array;
386 struct hna_local_entry *hna_local_entry;
390 info->first_seen = jiffies;
391 info->packet.vis_type = atomic_read(&vis_mode);
393 spin_lock_irqsave(&orig_hash_lock, flags);
394 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
395 info->packet.ttl = TTL;
396 info->packet.seqno++;
397 info->packet.entries = 0;
399 if (info->packet.vis_type == VIS_TYPE_CLIENT_UPDATE) {
400 best_tq = find_best_vis_server(info);
402 spin_unlock_irqrestore(&orig_hash_lock, flags);
407 entry_array = (struct vis_info_entry *)
408 ((char *)info + sizeof(struct vis_info));
410 while (hash_iterate(orig_hash, &hashit_global)) {
411 orig_node = hashit_global.bucket->data;
412 if (orig_node->router != NULL
413 && compare_orig(orig_node->router->addr,
415 && orig_node->batman_if
416 && (orig_node->batman_if->if_active == IF_ACTIVE)
417 && orig_node->router->tq_avg > 0) {
419 /* fill one entry into buffer. */
420 entry = &entry_array[info->packet.entries];
422 orig_node->batman_if->net_dev->dev_addr,
424 memcpy(entry->dest, orig_node->orig, ETH_ALEN);
425 entry->quality = orig_node->router->tq_avg;
426 info->packet.entries++;
428 if (vis_packet_full(info)) {
429 spin_unlock_irqrestore(&orig_hash_lock, flags);
435 spin_unlock_irqrestore(&orig_hash_lock, flags);
437 spin_lock_irqsave(&hna_local_hash_lock, flags);
438 while (hash_iterate(hna_local_hash, &hashit_local)) {
439 hna_local_entry = hashit_local.bucket->data;
440 entry = &entry_array[info->packet.entries];
441 memset(entry->src, 0, ETH_ALEN);
442 memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN);
443 entry->quality = 0; /* 0 means HNA */
444 info->packet.entries++;
446 if (vis_packet_full(info)) {
447 spin_unlock_irqrestore(&hna_local_hash_lock, flags);
451 spin_unlock_irqrestore(&hna_local_hash_lock, flags);
455 /* free old vis packets. Must be called with this vis_hash_lock
457 static void purge_vis_packets(void)
460 struct vis_info *info;
462 while (hash_iterate(vis_hash, &hashit)) {
463 info = hashit.bucket->data;
464 if (info == my_vis_info) /* never purge own data. */
466 if (time_after(jiffies,
467 info->first_seen + (VIS_TIMEOUT*HZ)/1000)) {
468 hash_remove_bucket(vis_hash, &hashit);
470 kref_put(&info->refcount, free_info);
475 static void broadcast_vis_packet(struct vis_info *info, int packet_length)
478 struct orig_node *orig_node;
480 struct batman_if *batman_if;
481 uint8_t dstaddr[ETH_ALEN];
483 spin_lock_irqsave(&orig_hash_lock, flags);
485 /* send to all routers in range. */
486 while (hash_iterate(orig_hash, &hashit)) {
487 orig_node = hashit.bucket->data;
489 /* if it's a vis server and reachable, send it. */
490 if ((!orig_node) || (!orig_node->batman_if) ||
491 (!orig_node->router))
493 if (!(orig_node->flags & VIS_SERVER))
495 /* don't send it if we already received the packet from
497 if (recv_list_is_in(&info->recv_list, orig_node->orig))
500 memcpy(info->packet.target_orig, orig_node->orig, ETH_ALEN);
501 batman_if = orig_node->batman_if;
502 memcpy(dstaddr, orig_node->router->addr, ETH_ALEN);
503 spin_unlock_irqrestore(&orig_hash_lock, flags);
505 send_raw_packet((unsigned char *)&info->packet,
506 packet_length, batman_if, dstaddr);
508 spin_lock_irqsave(&orig_hash_lock, flags);
511 spin_unlock_irqrestore(&orig_hash_lock, flags);
512 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
515 static void unicast_vis_packet(struct vis_info *info, int packet_length)
517 struct orig_node *orig_node;
519 struct batman_if *batman_if;
520 uint8_t dstaddr[ETH_ALEN];
522 spin_lock_irqsave(&orig_hash_lock, flags);
523 orig_node = ((struct orig_node *)
524 hash_find(orig_hash, info->packet.target_orig));
526 if ((!orig_node) || (!orig_node->batman_if) || (!orig_node->router))
529 /* don't lock while sending the packets ... we therefore
530 * copy the required data before sending */
531 batman_if = orig_node->batman_if;
532 memcpy(dstaddr, orig_node->router->addr, ETH_ALEN);
533 spin_unlock_irqrestore(&orig_hash_lock, flags);
535 send_raw_packet((unsigned char *)&info->packet,
536 packet_length, batman_if, dstaddr);
540 spin_unlock_irqrestore(&orig_hash_lock, flags);
543 /* only send one vis packet. called from send_vis_packets() */
544 static void send_vis_packet(struct vis_info *info)
548 if (info->packet.ttl < 2) {
549 printk(KERN_WARNING "batman-adv: Error - can't send vis packet: ttl exceeded\n");
553 memcpy(info->packet.sender_orig, mainIfAddr, ETH_ALEN);
556 packet_length = sizeof(struct vis_packet) +
557 info->packet.entries * sizeof(struct vis_info_entry);
559 if (is_bcast(info->packet.target_orig))
560 broadcast_vis_packet(info, packet_length);
562 unicast_vis_packet(info, packet_length);
563 info->packet.ttl++; /* restore TTL */
566 /* called from timer; send (and maybe generate) vis packet. */
567 static void send_vis_packets(struct work_struct *work)
569 struct vis_info *info, *temp;
572 spin_lock_irqsave(&vis_hash_lock, flags);
576 if (generate_vis_packet() == 0) {
577 /* schedule if generation was successful */
578 send_list_add(my_vis_info);
581 list_for_each_entry_safe(info, temp, &send_list, send_list) {
583 kref_get(&info->refcount);
584 spin_unlock_irqrestore(&vis_hash_lock, flags);
586 send_vis_packet(info);
588 spin_lock_irqsave(&vis_hash_lock, flags);
590 kref_put(&info->refcount, free_info);
592 spin_unlock_irqrestore(&vis_hash_lock, flags);
595 static DECLARE_DELAYED_WORK(vis_timer_wq, send_vis_packets);
597 /* init the vis server. this may only be called when if_list is already
598 * initialized (e.g. bat0 is initialized, interfaces have been added) */
605 spin_lock_irqsave(&vis_hash_lock, flags);
607 vis_hash = hash_new(256, vis_info_cmp, vis_info_choose);
609 printk(KERN_ERR "batman-adv:Can't initialize vis_hash\n");
613 my_vis_info = kmalloc(1000, GFP_ATOMIC);
615 printk(KERN_ERR "batman-adv:Can't initialize vis packet\n");
619 /* prefill the vis info */
620 my_vis_info->first_seen = jiffies - atomic_read(&vis_interval);
621 INIT_LIST_HEAD(&my_vis_info->recv_list);
622 INIT_LIST_HEAD(&my_vis_info->send_list);
623 kref_init(&my_vis_info->refcount);
624 my_vis_info->packet.version = COMPAT_VERSION;
625 my_vis_info->packet.packet_type = BAT_VIS;
626 my_vis_info->packet.ttl = TTL;
627 my_vis_info->packet.seqno = 0;
628 my_vis_info->packet.entries = 0;
630 INIT_LIST_HEAD(&send_list);
632 memcpy(my_vis_info->packet.vis_orig, mainIfAddr, ETH_ALEN);
633 memcpy(my_vis_info->packet.sender_orig, mainIfAddr, ETH_ALEN);
635 if (hash_add(vis_hash, my_vis_info) < 0) {
637 "batman-adv:Can't add own vis packet into hash\n");
638 /* not in hash, need to remove it manually. */
639 kref_put(&my_vis_info->refcount, free_info);
643 spin_unlock_irqrestore(&vis_hash_lock, flags);
648 spin_unlock_irqrestore(&vis_hash_lock, flags);
653 /* Decrease the reference count on a hash item info */
654 static void free_info_ref(void *data)
656 struct vis_info *info = data;
659 kref_put(&info->refcount, free_info);
662 /* shutdown vis-server */
669 cancel_delayed_work_sync(&vis_timer_wq);
671 spin_lock_irqsave(&vis_hash_lock, flags);
672 /* properly remove, kill timers ... */
673 hash_delete(vis_hash, free_info_ref);
676 spin_unlock_irqrestore(&vis_hash_lock, flags);
679 /* schedule packets for (re)transmission */
680 static void start_vis_timer(void)
682 queue_delayed_work(bat_event_workqueue, &vis_timer_wq,
683 (atomic_read(&vis_interval) * HZ) / 1000);