Commit | Line | Data |
---|---|---|
c6c8fea2 | 1 | /* |
64afe353 | 2 | * Copyright (C) 2008-2011 B.A.T.M.A.N. contributors: |
c6c8fea2 SE |
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" | |
26 | #include "soft-interface.h" | |
27 | #include "hard-interface.h" | |
28 | #include "hash.h" | |
29 | #include "originator.h" | |
30 | ||
31 | #define MAX_VIS_PACKET_SIZE 1000 | |
32 | ||
33 | /* Returns the smallest signed integer in two's complement with the sizeof x */ | |
34 | #define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u))) | |
35 | ||
36 | /* Checks if a sequence number x is a predecessor/successor of y. | |
37 | * they handle overflows/underflows and can correctly check for a | |
38 | * predecessor/successor unless the variable sequence number has grown by | |
39 | * more then 2**(bitwidth(x)-1)-1. | |
40 | * This means that for a uint8_t with the maximum value 255, it would think: | |
41 | * - when adding nothing - it is neither a predecessor nor a successor | |
42 | * - before adding more than 127 to the starting value - it is a predecessor, | |
43 | * - when adding 128 - it is neither a predecessor nor a successor, | |
44 | * - after adding more than 127 to the starting value - it is a successor */ | |
45 | #define seq_before(x, y) ({typeof(x) _dummy = (x - y); \ | |
46 | _dummy > smallest_signed_int(_dummy); }) | |
47 | #define seq_after(x, y) seq_before(y, x) | |
48 | ||
49 | static void start_vis_timer(struct bat_priv *bat_priv); | |
50 | ||
51 | /* free the info */ | |
52 | static void free_info(struct kref *ref) | |
53 | { | |
54 | struct vis_info *info = container_of(ref, struct vis_info, refcount); | |
55 | struct bat_priv *bat_priv = info->bat_priv; | |
56 | struct recvlist_node *entry, *tmp; | |
57 | ||
58 | list_del_init(&info->send_list); | |
59 | spin_lock_bh(&bat_priv->vis_list_lock); | |
60 | list_for_each_entry_safe(entry, tmp, &info->recv_list, list) { | |
61 | list_del(&entry->list); | |
62 | kfree(entry); | |
63 | } | |
64 | ||
65 | spin_unlock_bh(&bat_priv->vis_list_lock); | |
66 | kfree_skb(info->skb_packet); | |
67 | } | |
68 | ||
69 | /* Compare two vis packets, used by the hashing algorithm */ | |
7aadf889 | 70 | static int vis_info_cmp(struct hlist_node *node, void *data2) |
c6c8fea2 SE |
71 | { |
72 | struct vis_info *d1, *d2; | |
73 | struct vis_packet *p1, *p2; | |
7aadf889 ML |
74 | |
75 | d1 = container_of(node, struct vis_info, hash_entry); | |
c6c8fea2 SE |
76 | d2 = data2; |
77 | p1 = (struct vis_packet *)d1->skb_packet->data; | |
78 | p2 = (struct vis_packet *)d2->skb_packet->data; | |
39901e71 | 79 | return compare_eth(p1->vis_orig, p2->vis_orig); |
c6c8fea2 SE |
80 | } |
81 | ||
82 | /* hash function to choose an entry in a hash table of given size */ | |
83 | /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */ | |
84 | static int vis_info_choose(void *data, int size) | |
85 | { | |
86 | struct vis_info *vis_info = data; | |
87 | struct vis_packet *packet; | |
88 | unsigned char *key; | |
89 | uint32_t hash = 0; | |
90 | size_t i; | |
91 | ||
92 | packet = (struct vis_packet *)vis_info->skb_packet->data; | |
93 | key = packet->vis_orig; | |
94 | for (i = 0; i < ETH_ALEN; i++) { | |
95 | hash += key[i]; | |
96 | hash += (hash << 10); | |
97 | hash ^= (hash >> 6); | |
98 | } | |
99 | ||
100 | hash += (hash << 3); | |
101 | hash ^= (hash >> 11); | |
102 | hash += (hash << 15); | |
103 | ||
104 | return hash % size; | |
105 | } | |
106 | ||
7aadf889 ML |
107 | static struct vis_info *vis_hash_find(struct bat_priv *bat_priv, |
108 | void *data) | |
109 | { | |
110 | struct hashtable_t *hash = bat_priv->vis_hash; | |
111 | struct hlist_head *head; | |
112 | struct hlist_node *node; | |
113 | struct vis_info *vis_info, *vis_info_tmp = NULL; | |
114 | int index; | |
115 | ||
116 | if (!hash) | |
117 | return NULL; | |
118 | ||
119 | index = vis_info_choose(data, hash->size); | |
120 | head = &hash->table[index]; | |
121 | ||
122 | rcu_read_lock(); | |
123 | hlist_for_each_entry_rcu(vis_info, node, head, hash_entry) { | |
124 | if (!vis_info_cmp(node, data)) | |
125 | continue; | |
126 | ||
127 | vis_info_tmp = vis_info; | |
128 | break; | |
129 | } | |
130 | rcu_read_unlock(); | |
131 | ||
132 | return vis_info_tmp; | |
133 | } | |
134 | ||
c6c8fea2 SE |
135 | /* insert interface to the list of interfaces of one originator, if it |
136 | * does not already exist in the list */ | |
137 | static void vis_data_insert_interface(const uint8_t *interface, | |
138 | struct hlist_head *if_list, | |
139 | bool primary) | |
140 | { | |
141 | struct if_list_entry *entry; | |
142 | struct hlist_node *pos; | |
143 | ||
144 | hlist_for_each_entry(entry, pos, if_list, list) { | |
39901e71 | 145 | if (compare_eth(entry->addr, (void *)interface)) |
c6c8fea2 SE |
146 | return; |
147 | } | |
148 | ||
149 | /* its a new address, add it to the list */ | |
150 | entry = kmalloc(sizeof(*entry), GFP_ATOMIC); | |
151 | if (!entry) | |
152 | return; | |
153 | memcpy(entry->addr, interface, ETH_ALEN); | |
154 | entry->primary = primary; | |
155 | hlist_add_head(&entry->list, if_list); | |
156 | } | |
157 | ||
158 | static ssize_t vis_data_read_prim_sec(char *buff, struct hlist_head *if_list) | |
159 | { | |
160 | struct if_list_entry *entry; | |
161 | struct hlist_node *pos; | |
162 | size_t len = 0; | |
163 | ||
164 | hlist_for_each_entry(entry, pos, if_list, list) { | |
165 | if (entry->primary) | |
166 | len += sprintf(buff + len, "PRIMARY, "); | |
167 | else | |
168 | len += sprintf(buff + len, "SEC %pM, ", entry->addr); | |
169 | } | |
170 | ||
171 | return len; | |
172 | } | |
173 | ||
174 | static size_t vis_data_count_prim_sec(struct hlist_head *if_list) | |
175 | { | |
176 | struct if_list_entry *entry; | |
177 | struct hlist_node *pos; | |
178 | size_t count = 0; | |
179 | ||
180 | hlist_for_each_entry(entry, pos, if_list, list) { | |
181 | if (entry->primary) | |
182 | count += 9; | |
183 | else | |
184 | count += 23; | |
185 | } | |
186 | ||
187 | return count; | |
188 | } | |
189 | ||
190 | /* read an entry */ | |
191 | static ssize_t vis_data_read_entry(char *buff, struct vis_info_entry *entry, | |
192 | uint8_t *src, bool primary) | |
193 | { | |
194 | /* maximal length: max(4+17+2, 3+17+1+3+2) == 26 */ | |
195 | if (primary && entry->quality == 0) | |
196 | return sprintf(buff, "HNA %pM, ", entry->dest); | |
39901e71 | 197 | else if (compare_eth(entry->src, src)) |
c6c8fea2 SE |
198 | return sprintf(buff, "TQ %pM %d, ", entry->dest, |
199 | entry->quality); | |
200 | ||
201 | return 0; | |
202 | } | |
203 | ||
204 | int vis_seq_print_text(struct seq_file *seq, void *offset) | |
205 | { | |
7aadf889 | 206 | struct hlist_node *node; |
c6c8fea2 | 207 | struct hlist_head *head; |
c6c8fea2 SE |
208 | struct vis_info *info; |
209 | struct vis_packet *packet; | |
210 | struct vis_info_entry *entries; | |
211 | struct net_device *net_dev = (struct net_device *)seq->private; | |
212 | struct bat_priv *bat_priv = netdev_priv(net_dev); | |
213 | struct hashtable_t *hash = bat_priv->vis_hash; | |
214 | HLIST_HEAD(vis_if_list); | |
215 | struct if_list_entry *entry; | |
216 | struct hlist_node *pos, *n; | |
217 | int i, j; | |
218 | int vis_server = atomic_read(&bat_priv->vis_mode); | |
219 | size_t buff_pos, buf_size; | |
220 | char *buff; | |
221 | int compare; | |
222 | ||
223 | if ((!bat_priv->primary_if) || | |
224 | (vis_server == VIS_TYPE_CLIENT_UPDATE)) | |
225 | return 0; | |
226 | ||
227 | buf_size = 1; | |
228 | /* Estimate length */ | |
229 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
230 | for (i = 0; i < hash->size; i++) { | |
231 | head = &hash->table[i]; | |
232 | ||
7aadf889 ML |
233 | rcu_read_lock(); |
234 | hlist_for_each_entry_rcu(info, node, head, hash_entry) { | |
c6c8fea2 SE |
235 | packet = (struct vis_packet *)info->skb_packet->data; |
236 | entries = (struct vis_info_entry *) | |
237 | ((char *)packet + sizeof(struct vis_packet)); | |
238 | ||
239 | for (j = 0; j < packet->entries; j++) { | |
240 | if (entries[j].quality == 0) | |
241 | continue; | |
242 | compare = | |
39901e71 | 243 | compare_eth(entries[j].src, packet->vis_orig); |
c6c8fea2 SE |
244 | vis_data_insert_interface(entries[j].src, |
245 | &vis_if_list, | |
246 | compare); | |
247 | } | |
248 | ||
249 | hlist_for_each_entry(entry, pos, &vis_if_list, list) { | |
250 | buf_size += 18 + 26 * packet->entries; | |
251 | ||
252 | /* add primary/secondary records */ | |
39901e71 | 253 | if (compare_eth(entry->addr, packet->vis_orig)) |
c6c8fea2 SE |
254 | buf_size += |
255 | vis_data_count_prim_sec(&vis_if_list); | |
256 | ||
257 | buf_size += 1; | |
258 | } | |
259 | ||
260 | hlist_for_each_entry_safe(entry, pos, n, &vis_if_list, | |
261 | list) { | |
262 | hlist_del(&entry->list); | |
263 | kfree(entry); | |
264 | } | |
265 | } | |
7aadf889 | 266 | rcu_read_unlock(); |
c6c8fea2 SE |
267 | } |
268 | ||
269 | buff = kmalloc(buf_size, GFP_ATOMIC); | |
270 | if (!buff) { | |
271 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
272 | return -ENOMEM; | |
273 | } | |
274 | buff[0] = '\0'; | |
275 | buff_pos = 0; | |
276 | ||
277 | for (i = 0; i < hash->size; i++) { | |
278 | head = &hash->table[i]; | |
279 | ||
7aadf889 ML |
280 | rcu_read_lock(); |
281 | hlist_for_each_entry_rcu(info, node, head, hash_entry) { | |
c6c8fea2 SE |
282 | packet = (struct vis_packet *)info->skb_packet->data; |
283 | entries = (struct vis_info_entry *) | |
284 | ((char *)packet + sizeof(struct vis_packet)); | |
285 | ||
286 | for (j = 0; j < packet->entries; j++) { | |
287 | if (entries[j].quality == 0) | |
288 | continue; | |
289 | compare = | |
39901e71 | 290 | compare_eth(entries[j].src, packet->vis_orig); |
c6c8fea2 SE |
291 | vis_data_insert_interface(entries[j].src, |
292 | &vis_if_list, | |
293 | compare); | |
294 | } | |
295 | ||
296 | hlist_for_each_entry(entry, pos, &vis_if_list, list) { | |
297 | buff_pos += sprintf(buff + buff_pos, "%pM,", | |
298 | entry->addr); | |
299 | ||
300 | for (i = 0; i < packet->entries; i++) | |
301 | buff_pos += vis_data_read_entry( | |
302 | buff + buff_pos, | |
303 | &entries[i], | |
304 | entry->addr, | |
305 | entry->primary); | |
306 | ||
307 | /* add primary/secondary records */ | |
39901e71 | 308 | if (compare_eth(entry->addr, packet->vis_orig)) |
c6c8fea2 SE |
309 | buff_pos += |
310 | vis_data_read_prim_sec(buff + buff_pos, | |
311 | &vis_if_list); | |
312 | ||
313 | buff_pos += sprintf(buff + buff_pos, "\n"); | |
314 | } | |
315 | ||
316 | hlist_for_each_entry_safe(entry, pos, n, &vis_if_list, | |
317 | list) { | |
318 | hlist_del(&entry->list); | |
319 | kfree(entry); | |
320 | } | |
321 | } | |
7aadf889 | 322 | rcu_read_unlock(); |
c6c8fea2 SE |
323 | } |
324 | ||
325 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
326 | ||
327 | seq_printf(seq, "%s", buff); | |
328 | kfree(buff); | |
329 | ||
330 | return 0; | |
331 | } | |
332 | ||
333 | /* add the info packet to the send list, if it was not | |
334 | * already linked in. */ | |
335 | static void send_list_add(struct bat_priv *bat_priv, struct vis_info *info) | |
336 | { | |
337 | if (list_empty(&info->send_list)) { | |
338 | kref_get(&info->refcount); | |
339 | list_add_tail(&info->send_list, &bat_priv->vis_send_list); | |
340 | } | |
341 | } | |
342 | ||
343 | /* delete the info packet from the send list, if it was | |
344 | * linked in. */ | |
345 | static void send_list_del(struct vis_info *info) | |
346 | { | |
347 | if (!list_empty(&info->send_list)) { | |
348 | list_del_init(&info->send_list); | |
349 | kref_put(&info->refcount, free_info); | |
350 | } | |
351 | } | |
352 | ||
353 | /* tries to add one entry to the receive list. */ | |
354 | static void recv_list_add(struct bat_priv *bat_priv, | |
355 | struct list_head *recv_list, char *mac) | |
356 | { | |
357 | struct recvlist_node *entry; | |
358 | ||
359 | entry = kmalloc(sizeof(struct recvlist_node), GFP_ATOMIC); | |
360 | if (!entry) | |
361 | return; | |
362 | ||
363 | memcpy(entry->mac, mac, ETH_ALEN); | |
364 | spin_lock_bh(&bat_priv->vis_list_lock); | |
365 | list_add_tail(&entry->list, recv_list); | |
366 | spin_unlock_bh(&bat_priv->vis_list_lock); | |
367 | } | |
368 | ||
369 | /* returns 1 if this mac is in the recv_list */ | |
370 | static int recv_list_is_in(struct bat_priv *bat_priv, | |
371 | struct list_head *recv_list, char *mac) | |
372 | { | |
373 | struct recvlist_node *entry; | |
374 | ||
375 | spin_lock_bh(&bat_priv->vis_list_lock); | |
376 | list_for_each_entry(entry, recv_list, list) { | |
39901e71 | 377 | if (compare_eth(entry->mac, mac)) { |
c6c8fea2 SE |
378 | spin_unlock_bh(&bat_priv->vis_list_lock); |
379 | return 1; | |
380 | } | |
381 | } | |
382 | spin_unlock_bh(&bat_priv->vis_list_lock); | |
383 | return 0; | |
384 | } | |
385 | ||
386 | /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old, | |
387 | * broken.. ). vis hash must be locked outside. is_new is set when the packet | |
388 | * is newer than old entries in the hash. */ | |
389 | static struct vis_info *add_packet(struct bat_priv *bat_priv, | |
390 | struct vis_packet *vis_packet, | |
391 | int vis_info_len, int *is_new, | |
392 | int make_broadcast) | |
393 | { | |
394 | struct vis_info *info, *old_info; | |
395 | struct vis_packet *search_packet, *old_packet; | |
396 | struct vis_info search_elem; | |
397 | struct vis_packet *packet; | |
398 | int hash_added; | |
399 | ||
400 | *is_new = 0; | |
401 | /* sanity check */ | |
402 | if (!bat_priv->vis_hash) | |
403 | return NULL; | |
404 | ||
405 | /* see if the packet is already in vis_hash */ | |
406 | search_elem.skb_packet = dev_alloc_skb(sizeof(struct vis_packet)); | |
407 | if (!search_elem.skb_packet) | |
408 | return NULL; | |
409 | search_packet = (struct vis_packet *)skb_put(search_elem.skb_packet, | |
410 | sizeof(struct vis_packet)); | |
411 | ||
412 | memcpy(search_packet->vis_orig, vis_packet->vis_orig, ETH_ALEN); | |
7aadf889 | 413 | old_info = vis_hash_find(bat_priv, &search_elem); |
c6c8fea2 SE |
414 | kfree_skb(search_elem.skb_packet); |
415 | ||
416 | if (old_info) { | |
417 | old_packet = (struct vis_packet *)old_info->skb_packet->data; | |
418 | if (!seq_after(ntohl(vis_packet->seqno), | |
419 | ntohl(old_packet->seqno))) { | |
420 | if (old_packet->seqno == vis_packet->seqno) { | |
421 | recv_list_add(bat_priv, &old_info->recv_list, | |
422 | vis_packet->sender_orig); | |
423 | return old_info; | |
424 | } else { | |
425 | /* newer packet is already in hash. */ | |
426 | return NULL; | |
427 | } | |
428 | } | |
429 | /* remove old entry */ | |
430 | hash_remove(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, | |
431 | old_info); | |
432 | send_list_del(old_info); | |
433 | kref_put(&old_info->refcount, free_info); | |
434 | } | |
435 | ||
436 | info = kmalloc(sizeof(struct vis_info), GFP_ATOMIC); | |
437 | if (!info) | |
438 | return NULL; | |
439 | ||
440 | info->skb_packet = dev_alloc_skb(sizeof(struct vis_packet) + | |
441 | vis_info_len + sizeof(struct ethhdr)); | |
442 | if (!info->skb_packet) { | |
443 | kfree(info); | |
444 | return NULL; | |
445 | } | |
446 | skb_reserve(info->skb_packet, sizeof(struct ethhdr)); | |
447 | packet = (struct vis_packet *)skb_put(info->skb_packet, | |
448 | sizeof(struct vis_packet) + | |
449 | vis_info_len); | |
450 | ||
451 | kref_init(&info->refcount); | |
452 | INIT_LIST_HEAD(&info->send_list); | |
453 | INIT_LIST_HEAD(&info->recv_list); | |
454 | info->first_seen = jiffies; | |
455 | info->bat_priv = bat_priv; | |
456 | memcpy(packet, vis_packet, sizeof(struct vis_packet) + vis_info_len); | |
457 | ||
458 | /* initialize and add new packet. */ | |
459 | *is_new = 1; | |
460 | ||
461 | /* Make it a broadcast packet, if required */ | |
462 | if (make_broadcast) | |
463 | memcpy(packet->target_orig, broadcast_addr, ETH_ALEN); | |
464 | ||
465 | /* repair if entries is longer than packet. */ | |
466 | if (packet->entries * sizeof(struct vis_info_entry) > vis_info_len) | |
467 | packet->entries = vis_info_len / sizeof(struct vis_info_entry); | |
468 | ||
469 | recv_list_add(bat_priv, &info->recv_list, packet->sender_orig); | |
470 | ||
471 | /* try to add it */ | |
472 | hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, | |
7aadf889 | 473 | info, &info->hash_entry); |
c6c8fea2 SE |
474 | if (hash_added < 0) { |
475 | /* did not work (for some reason) */ | |
476 | kref_put(&old_info->refcount, free_info); | |
477 | info = NULL; | |
478 | } | |
479 | ||
480 | return info; | |
481 | } | |
482 | ||
483 | /* handle the server sync packet, forward if needed. */ | |
484 | void receive_server_sync_packet(struct bat_priv *bat_priv, | |
485 | struct vis_packet *vis_packet, | |
486 | int vis_info_len) | |
487 | { | |
488 | struct vis_info *info; | |
489 | int is_new, make_broadcast; | |
490 | int vis_server = atomic_read(&bat_priv->vis_mode); | |
491 | ||
492 | make_broadcast = (vis_server == VIS_TYPE_SERVER_SYNC); | |
493 | ||
494 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
495 | info = add_packet(bat_priv, vis_packet, vis_info_len, | |
496 | &is_new, make_broadcast); | |
497 | if (!info) | |
498 | goto end; | |
499 | ||
500 | /* only if we are server ourselves and packet is newer than the one in | |
501 | * hash.*/ | |
502 | if (vis_server == VIS_TYPE_SERVER_SYNC && is_new) | |
503 | send_list_add(bat_priv, info); | |
504 | end: | |
505 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
506 | } | |
507 | ||
508 | /* handle an incoming client update packet and schedule forward if needed. */ | |
509 | void receive_client_update_packet(struct bat_priv *bat_priv, | |
510 | struct vis_packet *vis_packet, | |
511 | int vis_info_len) | |
512 | { | |
513 | struct vis_info *info; | |
514 | struct vis_packet *packet; | |
515 | int is_new; | |
516 | int vis_server = atomic_read(&bat_priv->vis_mode); | |
517 | int are_target = 0; | |
518 | ||
519 | /* clients shall not broadcast. */ | |
520 | if (is_broadcast_ether_addr(vis_packet->target_orig)) | |
521 | return; | |
522 | ||
523 | /* Are we the target for this VIS packet? */ | |
524 | if (vis_server == VIS_TYPE_SERVER_SYNC && | |
525 | is_my_mac(vis_packet->target_orig)) | |
526 | are_target = 1; | |
527 | ||
528 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
529 | info = add_packet(bat_priv, vis_packet, vis_info_len, | |
530 | &is_new, are_target); | |
531 | ||
532 | if (!info) | |
533 | goto end; | |
534 | /* note that outdated packets will be dropped at this point. */ | |
535 | ||
536 | packet = (struct vis_packet *)info->skb_packet->data; | |
537 | ||
538 | /* send only if we're the target server or ... */ | |
539 | if (are_target && is_new) { | |
540 | packet->vis_type = VIS_TYPE_SERVER_SYNC; /* upgrade! */ | |
541 | send_list_add(bat_priv, info); | |
542 | ||
543 | /* ... we're not the recipient (and thus need to forward). */ | |
544 | } else if (!is_my_mac(packet->target_orig)) { | |
545 | send_list_add(bat_priv, info); | |
546 | } | |
547 | ||
548 | end: | |
549 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
550 | } | |
551 | ||
552 | /* Walk the originators and find the VIS server with the best tq. Set the packet | |
553 | * address to its address and return the best_tq. | |
554 | * | |
555 | * Must be called with the originator hash locked */ | |
556 | static int find_best_vis_server(struct bat_priv *bat_priv, | |
557 | struct vis_info *info) | |
558 | { | |
559 | struct hashtable_t *hash = bat_priv->orig_hash; | |
7aadf889 | 560 | struct hlist_node *node; |
c6c8fea2 | 561 | struct hlist_head *head; |
c6c8fea2 SE |
562 | struct orig_node *orig_node; |
563 | struct vis_packet *packet; | |
564 | int best_tq = -1, i; | |
565 | ||
566 | packet = (struct vis_packet *)info->skb_packet->data; | |
567 | ||
568 | for (i = 0; i < hash->size; i++) { | |
569 | head = &hash->table[i]; | |
570 | ||
fb778ea1 | 571 | rcu_read_lock(); |
7aadf889 | 572 | hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { |
c6c8fea2 | 573 | if ((orig_node) && (orig_node->router) && |
7aadf889 ML |
574 | (orig_node->flags & VIS_SERVER) && |
575 | (orig_node->router->tq_avg > best_tq)) { | |
c6c8fea2 SE |
576 | best_tq = orig_node->router->tq_avg; |
577 | memcpy(packet->target_orig, orig_node->orig, | |
578 | ETH_ALEN); | |
579 | } | |
580 | } | |
fb778ea1 | 581 | rcu_read_unlock(); |
c6c8fea2 SE |
582 | } |
583 | ||
584 | return best_tq; | |
585 | } | |
586 | ||
587 | /* Return true if the vis packet is full. */ | |
588 | static bool vis_packet_full(struct vis_info *info) | |
589 | { | |
590 | struct vis_packet *packet; | |
591 | packet = (struct vis_packet *)info->skb_packet->data; | |
592 | ||
593 | if (MAX_VIS_PACKET_SIZE / sizeof(struct vis_info_entry) | |
594 | < packet->entries + 1) | |
595 | return true; | |
596 | return false; | |
597 | } | |
598 | ||
599 | /* generates a packet of own vis data, | |
600 | * returns 0 on success, -1 if no packet could be generated */ | |
601 | static int generate_vis_packet(struct bat_priv *bat_priv) | |
602 | { | |
603 | struct hashtable_t *hash = bat_priv->orig_hash; | |
7aadf889 | 604 | struct hlist_node *node; |
c6c8fea2 | 605 | struct hlist_head *head; |
c6c8fea2 SE |
606 | struct orig_node *orig_node; |
607 | struct neigh_node *neigh_node; | |
608 | struct vis_info *info = (struct vis_info *)bat_priv->my_vis_info; | |
609 | struct vis_packet *packet = (struct vis_packet *)info->skb_packet->data; | |
610 | struct vis_info_entry *entry; | |
611 | struct hna_local_entry *hna_local_entry; | |
612 | int best_tq = -1, i; | |
613 | ||
614 | info->first_seen = jiffies; | |
615 | packet->vis_type = atomic_read(&bat_priv->vis_mode); | |
616 | ||
c6c8fea2 SE |
617 | memcpy(packet->target_orig, broadcast_addr, ETH_ALEN); |
618 | packet->ttl = TTL; | |
619 | packet->seqno = htonl(ntohl(packet->seqno) + 1); | |
620 | packet->entries = 0; | |
621 | skb_trim(info->skb_packet, sizeof(struct vis_packet)); | |
622 | ||
623 | if (packet->vis_type == VIS_TYPE_CLIENT_UPDATE) { | |
624 | best_tq = find_best_vis_server(bat_priv, info); | |
625 | ||
d0072609 | 626 | if (best_tq < 0) |
c6c8fea2 | 627 | return -1; |
c6c8fea2 SE |
628 | } |
629 | ||
630 | for (i = 0; i < hash->size; i++) { | |
631 | head = &hash->table[i]; | |
632 | ||
fb778ea1 | 633 | rcu_read_lock(); |
7aadf889 | 634 | hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { |
c6c8fea2 SE |
635 | neigh_node = orig_node->router; |
636 | ||
637 | if (!neigh_node) | |
638 | continue; | |
639 | ||
39901e71 | 640 | if (!compare_eth(neigh_node->addr, orig_node->orig)) |
c6c8fea2 SE |
641 | continue; |
642 | ||
643 | if (neigh_node->if_incoming->if_status != IF_ACTIVE) | |
644 | continue; | |
645 | ||
646 | if (neigh_node->tq_avg < 1) | |
647 | continue; | |
648 | ||
649 | /* fill one entry into buffer. */ | |
650 | entry = (struct vis_info_entry *) | |
651 | skb_put(info->skb_packet, sizeof(*entry)); | |
652 | memcpy(entry->src, | |
653 | neigh_node->if_incoming->net_dev->dev_addr, | |
654 | ETH_ALEN); | |
655 | memcpy(entry->dest, orig_node->orig, ETH_ALEN); | |
656 | entry->quality = neigh_node->tq_avg; | |
657 | packet->entries++; | |
658 | ||
d0072609 ML |
659 | if (vis_packet_full(info)) |
660 | goto unlock; | |
c6c8fea2 | 661 | } |
fb778ea1 | 662 | rcu_read_unlock(); |
c6c8fea2 SE |
663 | } |
664 | ||
c6c8fea2 SE |
665 | hash = bat_priv->hna_local_hash; |
666 | ||
667 | spin_lock_bh(&bat_priv->hna_lhash_lock); | |
668 | for (i = 0; i < hash->size; i++) { | |
669 | head = &hash->table[i]; | |
670 | ||
7aadf889 | 671 | hlist_for_each_entry(hna_local_entry, node, head, hash_entry) { |
c6c8fea2 SE |
672 | entry = (struct vis_info_entry *) |
673 | skb_put(info->skb_packet, | |
674 | sizeof(*entry)); | |
675 | memset(entry->src, 0, ETH_ALEN); | |
676 | memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN); | |
677 | entry->quality = 0; /* 0 means HNA */ | |
678 | packet->entries++; | |
679 | ||
680 | if (vis_packet_full(info)) { | |
681 | spin_unlock_bh(&bat_priv->hna_lhash_lock); | |
682 | return 0; | |
683 | } | |
684 | } | |
685 | } | |
686 | ||
687 | spin_unlock_bh(&bat_priv->hna_lhash_lock); | |
688 | return 0; | |
d0072609 ML |
689 | |
690 | unlock: | |
691 | rcu_read_unlock(); | |
692 | return 0; | |
c6c8fea2 SE |
693 | } |
694 | ||
695 | /* free old vis packets. Must be called with this vis_hash_lock | |
696 | * held */ | |
697 | static void purge_vis_packets(struct bat_priv *bat_priv) | |
698 | { | |
699 | int i; | |
700 | struct hashtable_t *hash = bat_priv->vis_hash; | |
7aadf889 | 701 | struct hlist_node *node, *node_tmp; |
c6c8fea2 | 702 | struct hlist_head *head; |
c6c8fea2 SE |
703 | struct vis_info *info; |
704 | ||
705 | for (i = 0; i < hash->size; i++) { | |
706 | head = &hash->table[i]; | |
707 | ||
7aadf889 ML |
708 | hlist_for_each_entry_safe(info, node, node_tmp, |
709 | head, hash_entry) { | |
c6c8fea2 SE |
710 | /* never purge own data. */ |
711 | if (info == bat_priv->my_vis_info) | |
712 | continue; | |
713 | ||
714 | if (time_after(jiffies, | |
715 | info->first_seen + VIS_TIMEOUT * HZ)) { | |
7aadf889 | 716 | hlist_del(node); |
c6c8fea2 SE |
717 | send_list_del(info); |
718 | kref_put(&info->refcount, free_info); | |
719 | } | |
720 | } | |
721 | } | |
722 | } | |
723 | ||
724 | static void broadcast_vis_packet(struct bat_priv *bat_priv, | |
725 | struct vis_info *info) | |
726 | { | |
727 | struct hashtable_t *hash = bat_priv->orig_hash; | |
7aadf889 | 728 | struct hlist_node *node; |
c6c8fea2 | 729 | struct hlist_head *head; |
c6c8fea2 SE |
730 | struct orig_node *orig_node; |
731 | struct vis_packet *packet; | |
732 | struct sk_buff *skb; | |
733 | struct batman_if *batman_if; | |
734 | uint8_t dstaddr[ETH_ALEN]; | |
735 | int i; | |
736 | ||
737 | ||
c6c8fea2 SE |
738 | packet = (struct vis_packet *)info->skb_packet->data; |
739 | ||
740 | /* send to all routers in range. */ | |
741 | for (i = 0; i < hash->size; i++) { | |
742 | head = &hash->table[i]; | |
743 | ||
fb778ea1 | 744 | rcu_read_lock(); |
7aadf889 | 745 | hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { |
c6c8fea2 SE |
746 | /* if it's a vis server and reachable, send it. */ |
747 | if ((!orig_node) || (!orig_node->router)) | |
748 | continue; | |
749 | if (!(orig_node->flags & VIS_SERVER)) | |
750 | continue; | |
751 | /* don't send it if we already received the packet from | |
752 | * this node. */ | |
753 | if (recv_list_is_in(bat_priv, &info->recv_list, | |
754 | orig_node->orig)) | |
755 | continue; | |
756 | ||
757 | memcpy(packet->target_orig, orig_node->orig, ETH_ALEN); | |
758 | batman_if = orig_node->router->if_incoming; | |
759 | memcpy(dstaddr, orig_node->router->addr, ETH_ALEN); | |
c6c8fea2 SE |
760 | |
761 | skb = skb_clone(info->skb_packet, GFP_ATOMIC); | |
762 | if (skb) | |
763 | send_skb_packet(skb, batman_if, dstaddr); | |
764 | ||
c6c8fea2 | 765 | } |
fb778ea1 | 766 | rcu_read_unlock(); |
c6c8fea2 | 767 | } |
c6c8fea2 SE |
768 | } |
769 | ||
770 | static void unicast_vis_packet(struct bat_priv *bat_priv, | |
771 | struct vis_info *info) | |
772 | { | |
773 | struct orig_node *orig_node; | |
44524fcd | 774 | struct neigh_node *neigh_node = NULL; |
c6c8fea2 SE |
775 | struct sk_buff *skb; |
776 | struct vis_packet *packet; | |
c6c8fea2 | 777 | |
c6c8fea2 | 778 | packet = (struct vis_packet *)info->skb_packet->data; |
44524fcd | 779 | |
fb778ea1 | 780 | rcu_read_lock(); |
7aadf889 | 781 | orig_node = orig_hash_find(bat_priv, packet->target_orig); |
c6c8fea2 | 782 | |
44524fcd ML |
783 | if (!orig_node) |
784 | goto unlock; | |
785 | ||
44524fcd ML |
786 | neigh_node = orig_node->router; |
787 | ||
788 | if (!neigh_node) | |
789 | goto unlock; | |
790 | ||
791 | if (!atomic_inc_not_zero(&neigh_node->refcount)) { | |
792 | neigh_node = NULL; | |
793 | goto unlock; | |
794 | } | |
795 | ||
796 | rcu_read_unlock(); | |
c6c8fea2 | 797 | |
c6c8fea2 SE |
798 | skb = skb_clone(info->skb_packet, GFP_ATOMIC); |
799 | if (skb) | |
d0072609 ML |
800 | send_skb_packet(skb, neigh_node->if_incoming, |
801 | neigh_node->addr); | |
c6c8fea2 | 802 | |
44524fcd | 803 | goto out; |
c6c8fea2 | 804 | |
44524fcd ML |
805 | unlock: |
806 | rcu_read_unlock(); | |
44524fcd ML |
807 | out: |
808 | if (neigh_node) | |
809 | neigh_node_free_ref(neigh_node); | |
810 | if (orig_node) | |
7b36e8ee | 811 | orig_node_free_ref(orig_node); |
44524fcd | 812 | return; |
c6c8fea2 SE |
813 | } |
814 | ||
815 | /* only send one vis packet. called from send_vis_packets() */ | |
816 | static void send_vis_packet(struct bat_priv *bat_priv, struct vis_info *info) | |
817 | { | |
818 | struct vis_packet *packet; | |
819 | ||
820 | packet = (struct vis_packet *)info->skb_packet->data; | |
821 | if (packet->ttl < 2) { | |
822 | pr_debug("Error - can't send vis packet: ttl exceeded\n"); | |
823 | return; | |
824 | } | |
825 | ||
826 | memcpy(packet->sender_orig, bat_priv->primary_if->net_dev->dev_addr, | |
827 | ETH_ALEN); | |
828 | packet->ttl--; | |
829 | ||
830 | if (is_broadcast_ether_addr(packet->target_orig)) | |
831 | broadcast_vis_packet(bat_priv, info); | |
832 | else | |
833 | unicast_vis_packet(bat_priv, info); | |
834 | packet->ttl++; /* restore TTL */ | |
835 | } | |
836 | ||
837 | /* called from timer; send (and maybe generate) vis packet. */ | |
838 | static void send_vis_packets(struct work_struct *work) | |
839 | { | |
840 | struct delayed_work *delayed_work = | |
841 | container_of(work, struct delayed_work, work); | |
842 | struct bat_priv *bat_priv = | |
843 | container_of(delayed_work, struct bat_priv, vis_work); | |
844 | struct vis_info *info, *temp; | |
845 | ||
846 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
847 | purge_vis_packets(bat_priv); | |
848 | ||
849 | if (generate_vis_packet(bat_priv) == 0) { | |
850 | /* schedule if generation was successful */ | |
851 | send_list_add(bat_priv, bat_priv->my_vis_info); | |
852 | } | |
853 | ||
854 | list_for_each_entry_safe(info, temp, &bat_priv->vis_send_list, | |
855 | send_list) { | |
856 | ||
857 | kref_get(&info->refcount); | |
858 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
859 | ||
860 | if (bat_priv->primary_if) | |
861 | send_vis_packet(bat_priv, info); | |
862 | ||
863 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
864 | send_list_del(info); | |
865 | kref_put(&info->refcount, free_info); | |
866 | } | |
867 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
868 | start_vis_timer(bat_priv); | |
869 | } | |
870 | ||
871 | /* init the vis server. this may only be called when if_list is already | |
872 | * initialized (e.g. bat0 is initialized, interfaces have been added) */ | |
873 | int vis_init(struct bat_priv *bat_priv) | |
874 | { | |
875 | struct vis_packet *packet; | |
876 | int hash_added; | |
877 | ||
878 | if (bat_priv->vis_hash) | |
879 | return 1; | |
880 | ||
881 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
882 | ||
883 | bat_priv->vis_hash = hash_new(256); | |
884 | if (!bat_priv->vis_hash) { | |
885 | pr_err("Can't initialize vis_hash\n"); | |
886 | goto err; | |
887 | } | |
888 | ||
889 | bat_priv->my_vis_info = kmalloc(MAX_VIS_PACKET_SIZE, GFP_ATOMIC); | |
890 | if (!bat_priv->my_vis_info) { | |
891 | pr_err("Can't initialize vis packet\n"); | |
892 | goto err; | |
893 | } | |
894 | ||
895 | bat_priv->my_vis_info->skb_packet = dev_alloc_skb( | |
896 | sizeof(struct vis_packet) + | |
897 | MAX_VIS_PACKET_SIZE + | |
898 | sizeof(struct ethhdr)); | |
899 | if (!bat_priv->my_vis_info->skb_packet) | |
900 | goto free_info; | |
901 | ||
902 | skb_reserve(bat_priv->my_vis_info->skb_packet, sizeof(struct ethhdr)); | |
903 | packet = (struct vis_packet *)skb_put( | |
904 | bat_priv->my_vis_info->skb_packet, | |
905 | sizeof(struct vis_packet)); | |
906 | ||
907 | /* prefill the vis info */ | |
908 | bat_priv->my_vis_info->first_seen = jiffies - | |
909 | msecs_to_jiffies(VIS_INTERVAL); | |
910 | INIT_LIST_HEAD(&bat_priv->my_vis_info->recv_list); | |
911 | INIT_LIST_HEAD(&bat_priv->my_vis_info->send_list); | |
912 | kref_init(&bat_priv->my_vis_info->refcount); | |
913 | bat_priv->my_vis_info->bat_priv = bat_priv; | |
914 | packet->version = COMPAT_VERSION; | |
915 | packet->packet_type = BAT_VIS; | |
916 | packet->ttl = TTL; | |
917 | packet->seqno = 0; | |
918 | packet->entries = 0; | |
919 | ||
920 | INIT_LIST_HEAD(&bat_priv->vis_send_list); | |
921 | ||
922 | hash_added = hash_add(bat_priv->vis_hash, vis_info_cmp, vis_info_choose, | |
7aadf889 ML |
923 | bat_priv->my_vis_info, |
924 | &bat_priv->my_vis_info->hash_entry); | |
c6c8fea2 SE |
925 | if (hash_added < 0) { |
926 | pr_err("Can't add own vis packet into hash\n"); | |
927 | /* not in hash, need to remove it manually. */ | |
928 | kref_put(&bat_priv->my_vis_info->refcount, free_info); | |
929 | goto err; | |
930 | } | |
931 | ||
932 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
933 | start_vis_timer(bat_priv); | |
934 | return 1; | |
935 | ||
936 | free_info: | |
937 | kfree(bat_priv->my_vis_info); | |
938 | bat_priv->my_vis_info = NULL; | |
939 | err: | |
940 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
941 | vis_quit(bat_priv); | |
942 | return 0; | |
943 | } | |
944 | ||
945 | /* Decrease the reference count on a hash item info */ | |
7aadf889 | 946 | static void free_info_ref(struct hlist_node *node, void *arg) |
c6c8fea2 | 947 | { |
7aadf889 | 948 | struct vis_info *info; |
c6c8fea2 | 949 | |
7aadf889 | 950 | info = container_of(node, struct vis_info, hash_entry); |
c6c8fea2 SE |
951 | send_list_del(info); |
952 | kref_put(&info->refcount, free_info); | |
953 | } | |
954 | ||
955 | /* shutdown vis-server */ | |
956 | void vis_quit(struct bat_priv *bat_priv) | |
957 | { | |
958 | if (!bat_priv->vis_hash) | |
959 | return; | |
960 | ||
961 | cancel_delayed_work_sync(&bat_priv->vis_work); | |
962 | ||
963 | spin_lock_bh(&bat_priv->vis_hash_lock); | |
964 | /* properly remove, kill timers ... */ | |
965 | hash_delete(bat_priv->vis_hash, free_info_ref, NULL); | |
966 | bat_priv->vis_hash = NULL; | |
967 | bat_priv->my_vis_info = NULL; | |
968 | spin_unlock_bh(&bat_priv->vis_hash_lock); | |
969 | } | |
970 | ||
971 | /* schedule packets for (re)transmission */ | |
972 | static void start_vis_timer(struct bat_priv *bat_priv) | |
973 | { | |
974 | INIT_DELAYED_WORK(&bat_priv->vis_work, send_vis_packets); | |
975 | queue_delayed_work(bat_event_workqueue, &bat_priv->vis_work, | |
976 | msecs_to_jiffies(VIS_INTERVAL)); | |
977 | } |