1 /* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors:
3 * Martin Hundebøll, Jeppe Ledet-Pedersen
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of version 2 of the GNU General Public
7 * License as published by the Free Software Foundation.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 #include <linux/debugfs.h>
24 #include "network-coding.h"
26 #include "originator.h"
27 #include "hard-interface.h"
30 static struct lock_class_key batadv_nc_coding_hash_lock_class_key
;
31 static struct lock_class_key batadv_nc_decoding_hash_lock_class_key
;
33 static void batadv_nc_worker(struct work_struct
*work
);
34 static int batadv_nc_recv_coded_packet(struct sk_buff
*skb
,
35 struct batadv_hard_iface
*recv_if
);
38 * batadv_nc_init - one-time initialization for network coding
40 int __init
batadv_nc_init(void)
44 /* Register our packet type */
45 ret
= batadv_recv_handler_register(BATADV_CODED
,
46 batadv_nc_recv_coded_packet
);
52 * batadv_nc_start_timer - initialise the nc periodic worker
53 * @bat_priv: the bat priv with all the soft interface information
55 static void batadv_nc_start_timer(struct batadv_priv
*bat_priv
)
57 queue_delayed_work(batadv_event_workqueue
, &bat_priv
->nc
.work
,
58 msecs_to_jiffies(10));
62 * batadv_nc_mesh_init - initialise coding hash table and start house keeping
63 * @bat_priv: the bat priv with all the soft interface information
65 int batadv_nc_mesh_init(struct batadv_priv
*bat_priv
)
67 bat_priv
->nc
.timestamp_fwd_flush
= jiffies
;
68 bat_priv
->nc
.timestamp_sniffed_purge
= jiffies
;
70 if (bat_priv
->nc
.coding_hash
|| bat_priv
->nc
.decoding_hash
)
73 bat_priv
->nc
.coding_hash
= batadv_hash_new(128);
74 if (!bat_priv
->nc
.coding_hash
)
77 batadv_hash_set_lock_class(bat_priv
->nc
.coding_hash
,
78 &batadv_nc_coding_hash_lock_class_key
);
80 bat_priv
->nc
.decoding_hash
= batadv_hash_new(128);
81 if (!bat_priv
->nc
.decoding_hash
)
84 batadv_hash_set_lock_class(bat_priv
->nc
.coding_hash
,
85 &batadv_nc_decoding_hash_lock_class_key
);
87 INIT_DELAYED_WORK(&bat_priv
->nc
.work
, batadv_nc_worker
);
88 batadv_nc_start_timer(bat_priv
);
97 * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables
98 * @bat_priv: the bat priv with all the soft interface information
100 void batadv_nc_init_bat_priv(struct batadv_priv
*bat_priv
)
102 atomic_set(&bat_priv
->network_coding
, 1);
103 bat_priv
->nc
.min_tq
= 200;
104 bat_priv
->nc
.max_fwd_delay
= 10;
105 bat_priv
->nc
.max_buffer_time
= 200;
109 * batadv_nc_init_orig - initialise the nc fields of an orig_node
110 * @orig_node: the orig_node which is going to be initialised
112 void batadv_nc_init_orig(struct batadv_orig_node
*orig_node
)
114 INIT_LIST_HEAD(&orig_node
->in_coding_list
);
115 INIT_LIST_HEAD(&orig_node
->out_coding_list
);
116 spin_lock_init(&orig_node
->in_coding_list_lock
);
117 spin_lock_init(&orig_node
->out_coding_list_lock
);
121 * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove
122 * its refcount on the orig_node
123 * @rcu: rcu pointer of the nc node
125 static void batadv_nc_node_free_rcu(struct rcu_head
*rcu
)
127 struct batadv_nc_node
*nc_node
;
129 nc_node
= container_of(rcu
, struct batadv_nc_node
, rcu
);
130 batadv_orig_node_free_ref(nc_node
->orig_node
);
135 * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly
137 * @nc_node: the nc node to free
139 static void batadv_nc_node_free_ref(struct batadv_nc_node
*nc_node
)
141 if (atomic_dec_and_test(&nc_node
->refcount
))
142 call_rcu(&nc_node
->rcu
, batadv_nc_node_free_rcu
);
146 * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly
148 * @nc_path: the nc node to free
150 static void batadv_nc_path_free_ref(struct batadv_nc_path
*nc_path
)
152 if (atomic_dec_and_test(&nc_path
->refcount
))
153 kfree_rcu(nc_path
, rcu
);
157 * batadv_nc_packet_free - frees nc packet
158 * @nc_packet: the nc packet to free
160 static void batadv_nc_packet_free(struct batadv_nc_packet
*nc_packet
)
163 kfree_skb(nc_packet
->skb
);
165 batadv_nc_path_free_ref(nc_packet
->nc_path
);
170 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
171 * @bat_priv: the bat priv with all the soft interface information
172 * @nc_node: the nc node to check
174 * Returns true if the entry has to be purged now, false otherwise
176 static bool batadv_nc_to_purge_nc_node(struct batadv_priv
*bat_priv
,
177 struct batadv_nc_node
*nc_node
)
179 if (atomic_read(&bat_priv
->mesh_state
) != BATADV_MESH_ACTIVE
)
182 return batadv_has_timed_out(nc_node
->last_seen
, BATADV_NC_NODE_TIMEOUT
);
186 * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out
187 * @bat_priv: the bat priv with all the soft interface information
188 * @nc_path: the nc path to check
190 * Returns true if the entry has to be purged now, false otherwise
192 static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv
*bat_priv
,
193 struct batadv_nc_path
*nc_path
)
195 if (atomic_read(&bat_priv
->mesh_state
) != BATADV_MESH_ACTIVE
)
198 /* purge the path when no packets has been added for 10 times the
201 return batadv_has_timed_out(nc_path
->last_valid
,
202 bat_priv
->nc
.max_fwd_delay
* 10);
206 * batadv_nc_to_purge_nc_path_decoding - checks whether an nc path has timed out
207 * @bat_priv: the bat priv with all the soft interface information
208 * @nc_path: the nc path to check
210 * Returns true if the entry has to be purged now, false otherwise
212 static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv
*bat_priv
,
213 struct batadv_nc_path
*nc_path
)
215 if (atomic_read(&bat_priv
->mesh_state
) != BATADV_MESH_ACTIVE
)
218 /* purge the path when no packets has been added for 10 times the
221 return batadv_has_timed_out(nc_path
->last_valid
,
222 bat_priv
->nc
.max_buffer_time
*10);
226 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
228 * @bat_priv: the bat priv with all the soft interface information
229 * @list: list of nc nodes
230 * @lock: nc node list lock
231 * @to_purge: function in charge to decide whether an entry has to be purged or
232 * not. This function takes the nc node as argument and has to return
233 * a boolean value: true if the entry has to be deleted, false
237 batadv_nc_purge_orig_nc_nodes(struct batadv_priv
*bat_priv
,
238 struct list_head
*list
,
240 bool (*to_purge
)(struct batadv_priv
*,
241 struct batadv_nc_node
*))
243 struct batadv_nc_node
*nc_node
, *nc_node_tmp
;
245 /* For each nc_node in list */
247 list_for_each_entry_safe(nc_node
, nc_node_tmp
, list
, list
) {
248 /* if an helper function has been passed as parameter,
249 * ask it if the entry has to be purged or not
251 if (to_purge
&& !to_purge(bat_priv
, nc_node
))
254 batadv_dbg(BATADV_DBG_NC
, bat_priv
,
255 "Removing nc_node %pM -> %pM\n",
256 nc_node
->addr
, nc_node
->orig_node
->orig
);
257 list_del_rcu(&nc_node
->list
);
258 batadv_nc_node_free_ref(nc_node
);
260 spin_unlock_bh(lock
);
264 * batadv_nc_purge_orig - purges all nc node data attached of the given
266 * @bat_priv: the bat priv with all the soft interface information
267 * @orig_node: orig_node with the nc node entries to be purged
268 * @to_purge: function in charge to decide whether an entry has to be purged or
269 * not. This function takes the nc node as argument and has to return
270 * a boolean value: true is the entry has to be deleted, false
273 void batadv_nc_purge_orig(struct batadv_priv
*bat_priv
,
274 struct batadv_orig_node
*orig_node
,
275 bool (*to_purge
)(struct batadv_priv
*,
276 struct batadv_nc_node
*))
278 /* Check ingoing nc_node's of this orig_node */
279 batadv_nc_purge_orig_nc_nodes(bat_priv
, &orig_node
->in_coding_list
,
280 &orig_node
->in_coding_list_lock
,
283 /* Check outgoing nc_node's of this orig_node */
284 batadv_nc_purge_orig_nc_nodes(bat_priv
, &orig_node
->out_coding_list
,
285 &orig_node
->out_coding_list_lock
,
290 * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
291 * have timed out nc nodes
292 * @bat_priv: the bat priv with all the soft interface information
294 static void batadv_nc_purge_orig_hash(struct batadv_priv
*bat_priv
)
296 struct batadv_hashtable
*hash
= bat_priv
->orig_hash
;
297 struct hlist_head
*head
;
298 struct batadv_orig_node
*orig_node
;
304 /* For each orig_node */
305 for (i
= 0; i
< hash
->size
; i
++) {
306 head
= &hash
->table
[i
];
309 hlist_for_each_entry_rcu(orig_node
, head
, hash_entry
)
310 batadv_nc_purge_orig(bat_priv
, orig_node
,
311 batadv_nc_to_purge_nc_node
);
317 * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove
319 * @bat_priv: the bat priv with all the soft interface information
320 * @hash: hash table containing the nc paths to check
321 * @to_purge: function in charge to decide whether an entry has to be purged or
322 * not. This function takes the nc node as argument and has to return
323 * a boolean value: true is the entry has to be deleted, false
326 static void batadv_nc_purge_paths(struct batadv_priv
*bat_priv
,
327 struct batadv_hashtable
*hash
,
328 bool (*to_purge
)(struct batadv_priv
*,
329 struct batadv_nc_path
*))
331 struct hlist_head
*head
;
332 struct hlist_node
*node_tmp
;
333 struct batadv_nc_path
*nc_path
;
334 spinlock_t
*lock
; /* Protects lists in hash */
337 for (i
= 0; i
< hash
->size
; i
++) {
338 head
= &hash
->table
[i
];
339 lock
= &hash
->list_locks
[i
];
341 /* For each nc_path in this bin */
343 hlist_for_each_entry_safe(nc_path
, node_tmp
, head
, hash_entry
) {
344 /* if an helper function has been passed as parameter,
345 * ask it if the entry has to be purged or not
347 if (to_purge
&& !to_purge(bat_priv
, nc_path
))
350 /* purging an non-empty nc_path should never happen, but
351 * is observed under high CPU load. Delay the purging
352 * until next iteration to allow the packet_list to be
355 if (!unlikely(list_empty(&nc_path
->packet_list
))) {
356 net_ratelimited_function(printk
,
358 "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
364 /* nc_path is unused, so remove it */
365 batadv_dbg(BATADV_DBG_NC
, bat_priv
,
366 "Remove nc_path %pM -> %pM\n",
367 nc_path
->prev_hop
, nc_path
->next_hop
);
368 hlist_del_rcu(&nc_path
->hash_entry
);
369 batadv_nc_path_free_ref(nc_path
);
371 spin_unlock_bh(lock
);
376 * batadv_nc_hash_key_gen - computes the nc_path hash key
377 * @key: buffer to hold the final hash key
378 * @src: source ethernet mac address going into the hash key
379 * @dst: destination ethernet mac address going into the hash key
381 static void batadv_nc_hash_key_gen(struct batadv_nc_path
*key
, const char *src
,
384 memcpy(key
->prev_hop
, src
, sizeof(key
->prev_hop
));
385 memcpy(key
->next_hop
, dst
, sizeof(key
->next_hop
));
389 * batadv_nc_hash_choose - compute the hash value for an nc path
390 * @data: data to hash
391 * @size: size of the hash table
393 * Returns the selected index in the hash table for the given data.
395 static uint32_t batadv_nc_hash_choose(const void *data
, uint32_t size
)
397 const struct batadv_nc_path
*nc_path
= data
;
400 hash
= batadv_hash_bytes(hash
, &nc_path
->prev_hop
,
401 sizeof(nc_path
->prev_hop
));
402 hash
= batadv_hash_bytes(hash
, &nc_path
->next_hop
,
403 sizeof(nc_path
->next_hop
));
406 hash
^= (hash
>> 11);
407 hash
+= (hash
<< 15);
413 * batadv_nc_hash_compare - comparing function used in the network coding hash
415 * @node: node in the local table
416 * @data2: second object to compare the node to
418 * Returns 1 if the two entry are the same, 0 otherwise
420 static int batadv_nc_hash_compare(const struct hlist_node
*node
,
423 const struct batadv_nc_path
*nc_path1
, *nc_path2
;
425 nc_path1
= container_of(node
, struct batadv_nc_path
, hash_entry
);
428 /* Return 1 if the two keys are identical */
429 if (memcmp(nc_path1
->prev_hop
, nc_path2
->prev_hop
,
430 sizeof(nc_path1
->prev_hop
)) != 0)
433 if (memcmp(nc_path1
->next_hop
, nc_path2
->next_hop
,
434 sizeof(nc_path1
->next_hop
)) != 0)
441 * batadv_nc_hash_find - search for an existing nc path and return it
442 * @hash: hash table containing the nc path
445 * Returns the nc_path if found, NULL otherwise.
447 static struct batadv_nc_path
*
448 batadv_nc_hash_find(struct batadv_hashtable
*hash
,
451 struct hlist_head
*head
;
452 struct batadv_nc_path
*nc_path
, *nc_path_tmp
= NULL
;
458 index
= batadv_nc_hash_choose(data
, hash
->size
);
459 head
= &hash
->table
[index
];
462 hlist_for_each_entry_rcu(nc_path
, head
, hash_entry
) {
463 if (!batadv_nc_hash_compare(&nc_path
->hash_entry
, data
))
466 if (!atomic_inc_not_zero(&nc_path
->refcount
))
469 nc_path_tmp
= nc_path
;
478 * batadv_nc_send_packet - send non-coded packet and free nc_packet struct
479 * @nc_packet: the nc packet to send
481 static void batadv_nc_send_packet(struct batadv_nc_packet
*nc_packet
)
483 batadv_send_skb_packet(nc_packet
->skb
,
484 nc_packet
->neigh_node
->if_incoming
,
485 nc_packet
->nc_path
->next_hop
);
486 nc_packet
->skb
= NULL
;
487 batadv_nc_packet_free(nc_packet
);
491 * batadv_nc_sniffed_purge - Checks timestamp of given sniffed nc_packet.
492 * @bat_priv: the bat priv with all the soft interface information
493 * @nc_path: the nc path the packet belongs to
494 * @nc_packet: the nc packet to be checked
496 * Checks whether the given sniffed (overheard) nc_packet has hit its buffering
497 * timeout. If so, the packet is no longer kept and the entry deleted from the
498 * queue. Has to be called with the appropriate locks.
500 * Returns false as soon as the entry in the fifo queue has not been timed out
501 * yet and true otherwise.
503 static bool batadv_nc_sniffed_purge(struct batadv_priv
*bat_priv
,
504 struct batadv_nc_path
*nc_path
,
505 struct batadv_nc_packet
*nc_packet
)
507 unsigned long timeout
= bat_priv
->nc
.max_buffer_time
;
510 /* Packets are added to tail, so the remaining packets did not time
511 * out and we can stop processing the current queue
513 if (atomic_read(&bat_priv
->mesh_state
) == BATADV_MESH_ACTIVE
&&
514 !batadv_has_timed_out(nc_packet
->timestamp
, timeout
))
517 /* purge nc packet */
518 list_del(&nc_packet
->list
);
519 batadv_nc_packet_free(nc_packet
);
528 * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet.
529 * @bat_priv: the bat priv with all the soft interface information
530 * @nc_path: the nc path the packet belongs to
531 * @nc_packet: the nc packet to be checked
533 * Checks whether the given nc packet has hit its forward timeout. If so, the
534 * packet is no longer delayed, immediately sent and the entry deleted from the
535 * queue. Has to be called with the appropriate locks.
537 * Returns false as soon as the entry in the fifo queue has not been timed out
538 * yet and true otherwise.
540 static bool batadv_nc_fwd_flush(struct batadv_priv
*bat_priv
,
541 struct batadv_nc_path
*nc_path
,
542 struct batadv_nc_packet
*nc_packet
)
544 unsigned long timeout
= bat_priv
->nc
.max_fwd_delay
;
546 /* Packets are added to tail, so the remaining packets did not time
547 * out and we can stop processing the current queue
549 if (atomic_read(&bat_priv
->mesh_state
) == BATADV_MESH_ACTIVE
&&
550 !batadv_has_timed_out(nc_packet
->timestamp
, timeout
))
554 batadv_inc_counter(bat_priv
, BATADV_CNT_FORWARD
);
555 batadv_add_counter(bat_priv
, BATADV_CNT_FORWARD_BYTES
,
556 nc_packet
->skb
->len
+ ETH_HLEN
);
557 list_del(&nc_packet
->list
);
558 batadv_nc_send_packet(nc_packet
);
564 * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out
566 * @bat_priv: the bat priv with all the soft interface information
567 * @hash: to be processed hash table
568 * @process_fn: Function called to process given nc packet. Should return true
569 * to encourage this function to proceed with the next packet.
570 * Otherwise the rest of the current queue is skipped.
573 batadv_nc_process_nc_paths(struct batadv_priv
*bat_priv
,
574 struct batadv_hashtable
*hash
,
575 bool (*process_fn
)(struct batadv_priv
*,
576 struct batadv_nc_path
*,
577 struct batadv_nc_packet
*))
579 struct hlist_head
*head
;
580 struct batadv_nc_packet
*nc_packet
, *nc_packet_tmp
;
581 struct batadv_nc_path
*nc_path
;
588 /* Loop hash table bins */
589 for (i
= 0; i
< hash
->size
; i
++) {
590 head
= &hash
->table
[i
];
592 /* Loop coding paths */
594 hlist_for_each_entry_rcu(nc_path
, head
, hash_entry
) {
596 spin_lock_bh(&nc_path
->packet_list_lock
);
597 list_for_each_entry_safe(nc_packet
, nc_packet_tmp
,
598 &nc_path
->packet_list
, list
) {
599 ret
= process_fn(bat_priv
, nc_path
, nc_packet
);
603 spin_unlock_bh(&nc_path
->packet_list_lock
);
610 * batadv_nc_worker - periodic task for house keeping related to network coding
611 * @work: kernel work struct
613 static void batadv_nc_worker(struct work_struct
*work
)
615 struct delayed_work
*delayed_work
;
616 struct batadv_priv_nc
*priv_nc
;
617 struct batadv_priv
*bat_priv
;
618 unsigned long timeout
;
620 delayed_work
= container_of(work
, struct delayed_work
, work
);
621 priv_nc
= container_of(delayed_work
, struct batadv_priv_nc
, work
);
622 bat_priv
= container_of(priv_nc
, struct batadv_priv
, nc
);
624 batadv_nc_purge_orig_hash(bat_priv
);
625 batadv_nc_purge_paths(bat_priv
, bat_priv
->nc
.coding_hash
,
626 batadv_nc_to_purge_nc_path_coding
);
627 batadv_nc_purge_paths(bat_priv
, bat_priv
->nc
.decoding_hash
,
628 batadv_nc_to_purge_nc_path_decoding
);
630 timeout
= bat_priv
->nc
.max_fwd_delay
;
632 if (batadv_has_timed_out(bat_priv
->nc
.timestamp_fwd_flush
, timeout
)) {
633 batadv_nc_process_nc_paths(bat_priv
, bat_priv
->nc
.coding_hash
,
634 batadv_nc_fwd_flush
);
635 bat_priv
->nc
.timestamp_fwd_flush
= jiffies
;
638 if (batadv_has_timed_out(bat_priv
->nc
.timestamp_sniffed_purge
,
639 bat_priv
->nc
.max_buffer_time
)) {
640 batadv_nc_process_nc_paths(bat_priv
, bat_priv
->nc
.decoding_hash
,
641 batadv_nc_sniffed_purge
);
642 bat_priv
->nc
.timestamp_sniffed_purge
= jiffies
;
645 /* Schedule a new check */
646 batadv_nc_start_timer(bat_priv
);
650 * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
652 * @bat_priv: the bat priv with all the soft interface information
653 * @orig_node: neighboring orig node which may be used as nc candidate
654 * @ogm_packet: incoming ogm packet also used for the checks
657 * 1) The OGM must have the most recent sequence number.
658 * 2) The TTL must be decremented by one and only one.
659 * 3) The OGM must be received from the first hop from orig_node.
660 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
662 static bool batadv_can_nc_with_orig(struct batadv_priv
*bat_priv
,
663 struct batadv_orig_node
*orig_node
,
664 struct batadv_ogm_packet
*ogm_packet
)
666 if (orig_node
->last_real_seqno
!= ntohl(ogm_packet
->seqno
))
668 if (orig_node
->last_ttl
!= ogm_packet
->header
.ttl
+ 1)
670 if (!batadv_compare_eth(ogm_packet
->orig
, ogm_packet
->prev_sender
))
672 if (ogm_packet
->tq
< bat_priv
->nc
.min_tq
)
679 * batadv_nc_find_nc_node - search for an existing nc node and return it
680 * @orig_node: orig node originating the ogm packet
681 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
682 * (can be equal to orig_node)
683 * @in_coding: traverse incoming or outgoing network coding list
685 * Returns the nc_node if found, NULL otherwise.
687 static struct batadv_nc_node
688 *batadv_nc_find_nc_node(struct batadv_orig_node
*orig_node
,
689 struct batadv_orig_node
*orig_neigh_node
,
692 struct batadv_nc_node
*nc_node
, *nc_node_out
= NULL
;
693 struct list_head
*list
;
696 list
= &orig_neigh_node
->in_coding_list
;
698 list
= &orig_neigh_node
->out_coding_list
;
700 /* Traverse list of nc_nodes to orig_node */
702 list_for_each_entry_rcu(nc_node
, list
, list
) {
703 if (!batadv_compare_eth(nc_node
->addr
, orig_node
->orig
))
706 if (!atomic_inc_not_zero(&nc_node
->refcount
))
710 nc_node_out
= nc_node
;
719 * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
721 * @bat_priv: the bat priv with all the soft interface information
722 * @orig_node: orig node originating the ogm packet
723 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
724 * (can be equal to orig_node)
725 * @in_coding: traverse incoming or outgoing network coding list
727 * Returns the nc_node if found or created, NULL in case of an error.
729 static struct batadv_nc_node
730 *batadv_nc_get_nc_node(struct batadv_priv
*bat_priv
,
731 struct batadv_orig_node
*orig_node
,
732 struct batadv_orig_node
*orig_neigh_node
,
735 struct batadv_nc_node
*nc_node
;
736 spinlock_t
*lock
; /* Used to lock list selected by "int in_coding" */
737 struct list_head
*list
;
739 /* Check if nc_node is already added */
740 nc_node
= batadv_nc_find_nc_node(orig_node
, orig_neigh_node
, in_coding
);
746 nc_node
= kzalloc(sizeof(*nc_node
), GFP_ATOMIC
);
750 if (!atomic_inc_not_zero(&orig_neigh_node
->refcount
))
753 /* Initialize nc_node */
754 INIT_LIST_HEAD(&nc_node
->list
);
755 memcpy(nc_node
->addr
, orig_node
->orig
, ETH_ALEN
);
756 nc_node
->orig_node
= orig_neigh_node
;
757 atomic_set(&nc_node
->refcount
, 2);
759 /* Select ingoing or outgoing coding node */
761 lock
= &orig_neigh_node
->in_coding_list_lock
;
762 list
= &orig_neigh_node
->in_coding_list
;
764 lock
= &orig_neigh_node
->out_coding_list_lock
;
765 list
= &orig_neigh_node
->out_coding_list
;
768 batadv_dbg(BATADV_DBG_NC
, bat_priv
, "Adding nc_node %pM -> %pM\n",
769 nc_node
->addr
, nc_node
->orig_node
->orig
);
771 /* Add nc_node to orig_node */
773 list_add_tail_rcu(&nc_node
->list
, list
);
774 spin_unlock_bh(lock
);
784 * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs
785 * (best called on incoming OGMs)
786 * @bat_priv: the bat priv with all the soft interface information
787 * @orig_node: orig node originating the ogm packet
788 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
789 * (can be equal to orig_node)
790 * @ogm_packet: incoming ogm packet
791 * @is_single_hop_neigh: orig_node is a single hop neighbor
793 void batadv_nc_update_nc_node(struct batadv_priv
*bat_priv
,
794 struct batadv_orig_node
*orig_node
,
795 struct batadv_orig_node
*orig_neigh_node
,
796 struct batadv_ogm_packet
*ogm_packet
,
797 int is_single_hop_neigh
)
799 struct batadv_nc_node
*in_nc_node
= NULL
, *out_nc_node
= NULL
;
801 /* Check if network coding is enabled */
802 if (!atomic_read(&bat_priv
->network_coding
))
805 /* accept ogms from 'good' neighbors and single hop neighbors */
806 if (!batadv_can_nc_with_orig(bat_priv
, orig_node
, ogm_packet
) &&
807 !is_single_hop_neigh
)
810 /* Add orig_node as in_nc_node on hop */
811 in_nc_node
= batadv_nc_get_nc_node(bat_priv
, orig_node
,
812 orig_neigh_node
, true);
816 in_nc_node
->last_seen
= jiffies
;
818 /* Add hop as out_nc_node on orig_node */
819 out_nc_node
= batadv_nc_get_nc_node(bat_priv
, orig_neigh_node
,
824 out_nc_node
->last_seen
= jiffies
;
828 batadv_nc_node_free_ref(in_nc_node
);
830 batadv_nc_node_free_ref(out_nc_node
);
834 * batadv_nc_get_path - get existing nc_path or allocate a new one
835 * @bat_priv: the bat priv with all the soft interface information
836 * @hash: hash table containing the nc path
837 * @src: ethernet source address - first half of the nc path search key
838 * @dst: ethernet destination address - second half of the nc path search key
840 * Returns pointer to nc_path if the path was found or created, returns NULL
843 static struct batadv_nc_path
*batadv_nc_get_path(struct batadv_priv
*bat_priv
,
844 struct batadv_hashtable
*hash
,
849 struct batadv_nc_path
*nc_path
, nc_path_key
;
851 batadv_nc_hash_key_gen(&nc_path_key
, src
, dst
);
853 /* Search for existing nc_path */
854 nc_path
= batadv_nc_hash_find(hash
, (void *)&nc_path_key
);
857 /* Set timestamp to delay removal of nc_path */
858 nc_path
->last_valid
= jiffies
;
862 /* No existing nc_path was found; create a new */
863 nc_path
= kzalloc(sizeof(*nc_path
), GFP_ATOMIC
);
868 /* Initialize nc_path */
869 INIT_LIST_HEAD(&nc_path
->packet_list
);
870 spin_lock_init(&nc_path
->packet_list_lock
);
871 atomic_set(&nc_path
->refcount
, 2);
872 nc_path
->last_valid
= jiffies
;
873 memcpy(nc_path
->next_hop
, dst
, ETH_ALEN
);
874 memcpy(nc_path
->prev_hop
, src
, ETH_ALEN
);
876 batadv_dbg(BATADV_DBG_NC
, bat_priv
, "Adding nc_path %pM -> %pM\n",
880 /* Add nc_path to hash table */
881 hash_added
= batadv_hash_add(hash
, batadv_nc_hash_compare
,
882 batadv_nc_hash_choose
, &nc_path_key
,
883 &nc_path
->hash_entry
);
885 if (hash_added
< 0) {
894 * batadv_nc_random_weight_tq - scale the receivers TQ-value to avoid unfair
895 * selection of a receiver with slightly lower TQ than the other
896 * @tq: to be weighted tq value
898 static uint8_t batadv_nc_random_weight_tq(uint8_t tq
)
900 uint8_t rand_val
, rand_tq
;
902 get_random_bytes(&rand_val
, sizeof(rand_val
));
904 /* randomize the estimated packet loss (max TQ - estimated TQ) */
905 rand_tq
= rand_val
* (BATADV_TQ_MAX_VALUE
- tq
);
907 /* normalize the randomized packet loss */
908 rand_tq
/= BATADV_TQ_MAX_VALUE
;
910 /* convert to (randomized) estimated tq again */
911 return BATADV_TQ_MAX_VALUE
- rand_tq
;
915 * batadv_nc_memxor - XOR destination with source
916 * @dst: byte array to XOR into
917 * @src: byte array to XOR from
918 * @len: length of destination array
920 static void batadv_nc_memxor(char *dst
, const char *src
, unsigned int len
)
924 for (i
= 0; i
< len
; ++i
)
929 * batadv_nc_code_packets - code a received unicast_packet with an nc packet
930 * into a coded_packet and send it
931 * @bat_priv: the bat priv with all the soft interface information
932 * @skb: data skb to forward
933 * @ethhdr: pointer to the ethernet header inside the skb
934 * @nc_packet: structure containing the packet to the skb can be coded with
935 * @neigh_node: next hop to forward packet to
937 * Returns true if both packets are consumed, false otherwise.
939 static bool batadv_nc_code_packets(struct batadv_priv
*bat_priv
,
941 struct ethhdr
*ethhdr
,
942 struct batadv_nc_packet
*nc_packet
,
943 struct batadv_neigh_node
*neigh_node
)
945 uint8_t tq_weighted_neigh
, tq_weighted_coding
;
946 struct sk_buff
*skb_dest
, *skb_src
;
947 struct batadv_unicast_packet
*packet1
;
948 struct batadv_unicast_packet
*packet2
;
949 struct batadv_coded_packet
*coded_packet
;
950 struct batadv_neigh_node
*neigh_tmp
, *router_neigh
;
951 struct batadv_neigh_node
*router_coding
= NULL
;
952 uint8_t *first_source
, *first_dest
, *second_source
, *second_dest
;
953 __be32 packet_id1
, packet_id2
;
957 int unicast_size
= sizeof(*packet1
);
958 int coded_size
= sizeof(*coded_packet
);
959 int header_add
= coded_size
- unicast_size
;
961 router_neigh
= batadv_orig_node_get_router(neigh_node
->orig_node
);
965 neigh_tmp
= nc_packet
->neigh_node
;
966 router_coding
= batadv_orig_node_get_router(neigh_tmp
->orig_node
);
970 tq_weighted_neigh
= batadv_nc_random_weight_tq(router_neigh
->tq_avg
);
971 tq_weighted_coding
= batadv_nc_random_weight_tq(router_coding
->tq_avg
);
973 /* Select one destination for the MAC-header dst-field based on
974 * weighted TQ-values.
976 if (tq_weighted_neigh
>= tq_weighted_coding
) {
977 /* Destination from nc_packet is selected for MAC-header */
978 first_dest
= nc_packet
->nc_path
->next_hop
;
979 first_source
= nc_packet
->nc_path
->prev_hop
;
980 second_dest
= neigh_node
->addr
;
981 second_source
= ethhdr
->h_source
;
982 packet1
= (struct batadv_unicast_packet
*)nc_packet
->skb
->data
;
983 packet2
= (struct batadv_unicast_packet
*)skb
->data
;
984 packet_id1
= nc_packet
->packet_id
;
985 packet_id2
= batadv_skb_crc32(skb
,
986 skb
->data
+ sizeof(*packet2
));
988 /* Destination for skb is selected for MAC-header */
989 first_dest
= neigh_node
->addr
;
990 first_source
= ethhdr
->h_source
;
991 second_dest
= nc_packet
->nc_path
->next_hop
;
992 second_source
= nc_packet
->nc_path
->prev_hop
;
993 packet1
= (struct batadv_unicast_packet
*)skb
->data
;
994 packet2
= (struct batadv_unicast_packet
*)nc_packet
->skb
->data
;
995 packet_id1
= batadv_skb_crc32(skb
,
996 skb
->data
+ sizeof(*packet1
));
997 packet_id2
= nc_packet
->packet_id
;
1000 /* Instead of zero padding the smallest data buffer, we
1001 * code into the largest.
1003 if (skb
->len
<= nc_packet
->skb
->len
) {
1004 skb_dest
= nc_packet
->skb
;
1008 skb_src
= nc_packet
->skb
;
1011 /* coding_len is used when decoding the packet shorter packet */
1012 coding_len
= skb_src
->len
- unicast_size
;
1014 if (skb_linearize(skb_dest
) < 0 || skb_linearize(skb_src
) < 0)
1017 skb_push(skb_dest
, header_add
);
1019 coded_packet
= (struct batadv_coded_packet
*)skb_dest
->data
;
1020 skb_reset_mac_header(skb_dest
);
1022 coded_packet
->header
.packet_type
= BATADV_CODED
;
1023 coded_packet
->header
.version
= BATADV_COMPAT_VERSION
;
1024 coded_packet
->header
.ttl
= packet1
->header
.ttl
;
1026 /* Info about first unicast packet */
1027 memcpy(coded_packet
->first_source
, first_source
, ETH_ALEN
);
1028 memcpy(coded_packet
->first_orig_dest
, packet1
->dest
, ETH_ALEN
);
1029 coded_packet
->first_crc
= packet_id1
;
1030 coded_packet
->first_ttvn
= packet1
->ttvn
;
1032 /* Info about second unicast packet */
1033 memcpy(coded_packet
->second_dest
, second_dest
, ETH_ALEN
);
1034 memcpy(coded_packet
->second_source
, second_source
, ETH_ALEN
);
1035 memcpy(coded_packet
->second_orig_dest
, packet2
->dest
, ETH_ALEN
);
1036 coded_packet
->second_crc
= packet_id2
;
1037 coded_packet
->second_ttl
= packet2
->header
.ttl
;
1038 coded_packet
->second_ttvn
= packet2
->ttvn
;
1039 coded_packet
->coded_len
= htons(coding_len
);
1041 /* This is where the magic happens: Code skb_src into skb_dest */
1042 batadv_nc_memxor(skb_dest
->data
+ coded_size
,
1043 skb_src
->data
+ unicast_size
, coding_len
);
1045 /* Update counters accordingly */
1046 if (BATADV_SKB_CB(skb_src
)->decoded
&&
1047 BATADV_SKB_CB(skb_dest
)->decoded
) {
1048 /* Both packets are recoded */
1049 count
= skb_src
->len
+ ETH_HLEN
;
1050 count
+= skb_dest
->len
+ ETH_HLEN
;
1051 batadv_add_counter(bat_priv
, BATADV_CNT_NC_RECODE
, 2);
1052 batadv_add_counter(bat_priv
, BATADV_CNT_NC_RECODE_BYTES
, count
);
1053 } else if (!BATADV_SKB_CB(skb_src
)->decoded
&&
1054 !BATADV_SKB_CB(skb_dest
)->decoded
) {
1055 /* Both packets are newly coded */
1056 count
= skb_src
->len
+ ETH_HLEN
;
1057 count
+= skb_dest
->len
+ ETH_HLEN
;
1058 batadv_add_counter(bat_priv
, BATADV_CNT_NC_CODE
, 2);
1059 batadv_add_counter(bat_priv
, BATADV_CNT_NC_CODE_BYTES
, count
);
1060 } else if (BATADV_SKB_CB(skb_src
)->decoded
&&
1061 !BATADV_SKB_CB(skb_dest
)->decoded
) {
1062 /* skb_src recoded and skb_dest is newly coded */
1063 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_RECODE
);
1064 batadv_add_counter(bat_priv
, BATADV_CNT_NC_RECODE_BYTES
,
1065 skb_src
->len
+ ETH_HLEN
);
1066 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_CODE
);
1067 batadv_add_counter(bat_priv
, BATADV_CNT_NC_CODE_BYTES
,
1068 skb_dest
->len
+ ETH_HLEN
);
1069 } else if (!BATADV_SKB_CB(skb_src
)->decoded
&&
1070 BATADV_SKB_CB(skb_dest
)->decoded
) {
1071 /* skb_src is newly coded and skb_dest is recoded */
1072 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_CODE
);
1073 batadv_add_counter(bat_priv
, BATADV_CNT_NC_CODE_BYTES
,
1074 skb_src
->len
+ ETH_HLEN
);
1075 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_RECODE
);
1076 batadv_add_counter(bat_priv
, BATADV_CNT_NC_RECODE_BYTES
,
1077 skb_dest
->len
+ ETH_HLEN
);
1080 /* skb_src is now coded into skb_dest, so free it */
1083 /* avoid duplicate free of skb from nc_packet */
1084 nc_packet
->skb
= NULL
;
1085 batadv_nc_packet_free(nc_packet
);
1087 /* Send the coded packet and return true */
1088 batadv_send_skb_packet(skb_dest
, neigh_node
->if_incoming
, first_dest
);
1092 batadv_neigh_node_free_ref(router_neigh
);
1094 batadv_neigh_node_free_ref(router_coding
);
1099 * batadv_nc_skb_coding_possible - true if a decoded skb is available at dst.
1100 * @skb: data skb to forward
1101 * @dst: destination mac address of the other skb to code with
1102 * @src: source mac address of skb
1104 * Whenever we network code a packet we have to check whether we received it in
1105 * a network coded form. If so, we may not be able to use it for coding because
1106 * some neighbors may also have received (overheard) the packet in the network
1107 * coded form without being able to decode it. It is hard to know which of the
1108 * neighboring nodes was able to decode the packet, therefore we can only
1109 * re-code the packet if the source of the previous encoded packet is involved.
1110 * Since the source encoded the packet we can be certain it has all necessary
1111 * decode information.
1113 * Returns true if coding of a decoded packet is allowed.
1115 static bool batadv_nc_skb_coding_possible(struct sk_buff
*skb
,
1116 uint8_t *dst
, uint8_t *src
)
1118 if (BATADV_SKB_CB(skb
)->decoded
&& !batadv_compare_eth(dst
, src
))
1125 * batadv_nc_path_search - Find the coding path matching in_nc_node and
1126 * out_nc_node to retrieve a buffered packet that can be used for coding.
1127 * @bat_priv: the bat priv with all the soft interface information
1128 * @in_nc_node: pointer to skb next hop's neighbor nc node
1129 * @out_nc_node: pointer to skb source's neighbor nc node
1130 * @skb: data skb to forward
1131 * @eth_dst: next hop mac address of skb
1133 * Returns true if coding of a decoded skb is allowed.
1135 static struct batadv_nc_packet
*
1136 batadv_nc_path_search(struct batadv_priv
*bat_priv
,
1137 struct batadv_nc_node
*in_nc_node
,
1138 struct batadv_nc_node
*out_nc_node
,
1139 struct sk_buff
*skb
,
1142 struct batadv_nc_path
*nc_path
, nc_path_key
;
1143 struct batadv_nc_packet
*nc_packet_out
= NULL
;
1144 struct batadv_nc_packet
*nc_packet
, *nc_packet_tmp
;
1145 struct batadv_hashtable
*hash
= bat_priv
->nc
.coding_hash
;
1151 /* Create almost path key */
1152 batadv_nc_hash_key_gen(&nc_path_key
, in_nc_node
->addr
,
1154 idx
= batadv_nc_hash_choose(&nc_path_key
, hash
->size
);
1156 /* Check for coding opportunities in this nc_path */
1158 hlist_for_each_entry_rcu(nc_path
, &hash
->table
[idx
], hash_entry
) {
1159 if (!batadv_compare_eth(nc_path
->prev_hop
, in_nc_node
->addr
))
1162 if (!batadv_compare_eth(nc_path
->next_hop
, out_nc_node
->addr
))
1165 spin_lock_bh(&nc_path
->packet_list_lock
);
1166 if (list_empty(&nc_path
->packet_list
)) {
1167 spin_unlock_bh(&nc_path
->packet_list_lock
);
1171 list_for_each_entry_safe(nc_packet
, nc_packet_tmp
,
1172 &nc_path
->packet_list
, list
) {
1173 if (!batadv_nc_skb_coding_possible(nc_packet
->skb
,
1178 /* Coding opportunity is found! */
1179 list_del(&nc_packet
->list
);
1180 nc_packet_out
= nc_packet
;
1184 spin_unlock_bh(&nc_path
->packet_list_lock
);
1189 return nc_packet_out
;
1193 * batadv_nc_skb_src_search - Loops through the list of neighoring nodes of the
1194 * skb's sender (may be equal to the originator).
1195 * @bat_priv: the bat priv with all the soft interface information
1196 * @skb: data skb to forward
1197 * @eth_dst: next hop mac address of skb
1198 * @eth_src: source mac address of skb
1199 * @in_nc_node: pointer to skb next hop's neighbor nc node
1201 * Returns an nc packet if a suitable coding packet was found, NULL otherwise.
1203 static struct batadv_nc_packet
*
1204 batadv_nc_skb_src_search(struct batadv_priv
*bat_priv
,
1205 struct sk_buff
*skb
,
1208 struct batadv_nc_node
*in_nc_node
)
1210 struct batadv_orig_node
*orig_node
;
1211 struct batadv_nc_node
*out_nc_node
;
1212 struct batadv_nc_packet
*nc_packet
= NULL
;
1214 orig_node
= batadv_orig_hash_find(bat_priv
, eth_src
);
1219 list_for_each_entry_rcu(out_nc_node
,
1220 &orig_node
->out_coding_list
, list
) {
1221 /* Check if the skb is decoded and if recoding is possible */
1222 if (!batadv_nc_skb_coding_possible(skb
,
1223 out_nc_node
->addr
, eth_src
))
1226 /* Search for an opportunity in this nc_path */
1227 nc_packet
= batadv_nc_path_search(bat_priv
, in_nc_node
,
1228 out_nc_node
, skb
, eth_dst
);
1234 batadv_orig_node_free_ref(orig_node
);
1239 * batadv_nc_skb_store_before_coding - set the ethernet src and dst of the
1240 * unicast skb before it is stored for use in later decoding
1241 * @bat_priv: the bat priv with all the soft interface information
1242 * @skb: data skb to store
1243 * @eth_dst_new: new destination mac address of skb
1245 static void batadv_nc_skb_store_before_coding(struct batadv_priv
*bat_priv
,
1246 struct sk_buff
*skb
,
1247 uint8_t *eth_dst_new
)
1249 struct ethhdr
*ethhdr
;
1251 /* Copy skb header to change the mac header */
1252 skb
= pskb_copy(skb
, GFP_ATOMIC
);
1256 /* Set the mac header as if we actually sent the packet uncoded */
1257 ethhdr
= (struct ethhdr
*)skb_mac_header(skb
);
1258 memcpy(ethhdr
->h_source
, ethhdr
->h_dest
, ETH_ALEN
);
1259 memcpy(ethhdr
->h_dest
, eth_dst_new
, ETH_ALEN
);
1261 /* Set data pointer to MAC header to mimic packets from our tx path */
1262 skb_push(skb
, ETH_HLEN
);
1264 /* Add the packet to the decoding packet pool */
1265 batadv_nc_skb_store_for_decoding(bat_priv
, skb
);
1267 /* batadv_nc_skb_store_for_decoding() clones the skb, so we must free
1274 * batadv_nc_skb_dst_search - Loops through list of neighboring nodes to dst.
1275 * @skb: data skb to forward
1276 * @neigh_node: next hop to forward packet to
1277 * @ethhdr: pointer to the ethernet header inside the skb
1279 * Loops through list of neighboring nodes the next hop has a good connection to
1280 * (receives OGMs with a sufficient quality). We need to find a neighbor of our
1281 * next hop that potentially sent a packet which our next hop also received
1282 * (overheard) and has stored for later decoding.
1284 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1286 static bool batadv_nc_skb_dst_search(struct sk_buff
*skb
,
1287 struct batadv_neigh_node
*neigh_node
,
1288 struct ethhdr
*ethhdr
)
1290 struct net_device
*netdev
= neigh_node
->if_incoming
->soft_iface
;
1291 struct batadv_priv
*bat_priv
= netdev_priv(netdev
);
1292 struct batadv_orig_node
*orig_node
= neigh_node
->orig_node
;
1293 struct batadv_nc_node
*nc_node
;
1294 struct batadv_nc_packet
*nc_packet
= NULL
;
1297 list_for_each_entry_rcu(nc_node
, &orig_node
->in_coding_list
, list
) {
1298 /* Search for coding opportunity with this in_nc_node */
1299 nc_packet
= batadv_nc_skb_src_search(bat_priv
, skb
,
1301 ethhdr
->h_source
, nc_node
);
1303 /* Opportunity was found, so stop searching */
1312 /* Save packets for later decoding */
1313 batadv_nc_skb_store_before_coding(bat_priv
, skb
,
1315 batadv_nc_skb_store_before_coding(bat_priv
, nc_packet
->skb
,
1316 nc_packet
->neigh_node
->addr
);
1318 /* Code and send packets */
1319 if (batadv_nc_code_packets(bat_priv
, skb
, ethhdr
, nc_packet
,
1323 /* out of mem ? Coding failed - we have to free the buffered packet
1324 * to avoid memleaks. The skb passed as argument will be dealt with
1325 * by the calling function.
1327 batadv_nc_send_packet(nc_packet
);
1332 * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding
1333 * @skb: skb to add to path
1334 * @nc_path: path to add skb to
1335 * @neigh_node: next hop to forward packet to
1336 * @packet_id: checksum to identify packet
1338 * Returns true if the packet was buffered or false in case of an error.
1340 static bool batadv_nc_skb_add_to_path(struct sk_buff
*skb
,
1341 struct batadv_nc_path
*nc_path
,
1342 struct batadv_neigh_node
*neigh_node
,
1345 struct batadv_nc_packet
*nc_packet
;
1347 nc_packet
= kzalloc(sizeof(*nc_packet
), GFP_ATOMIC
);
1351 /* Initialize nc_packet */
1352 nc_packet
->timestamp
= jiffies
;
1353 nc_packet
->packet_id
= packet_id
;
1354 nc_packet
->skb
= skb
;
1355 nc_packet
->neigh_node
= neigh_node
;
1356 nc_packet
->nc_path
= nc_path
;
1358 /* Add coding packet to list */
1359 spin_lock_bh(&nc_path
->packet_list_lock
);
1360 list_add_tail(&nc_packet
->list
, &nc_path
->packet_list
);
1361 spin_unlock_bh(&nc_path
->packet_list_lock
);
1367 * batadv_nc_skb_forward - try to code a packet or add it to the coding packet
1369 * @skb: data skb to forward
1370 * @neigh_node: next hop to forward packet to
1371 * @ethhdr: pointer to the ethernet header inside the skb
1373 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1375 bool batadv_nc_skb_forward(struct sk_buff
*skb
,
1376 struct batadv_neigh_node
*neigh_node
,
1377 struct ethhdr
*ethhdr
)
1379 const struct net_device
*netdev
= neigh_node
->if_incoming
->soft_iface
;
1380 struct batadv_priv
*bat_priv
= netdev_priv(netdev
);
1381 struct batadv_unicast_packet
*packet
;
1382 struct batadv_nc_path
*nc_path
;
1386 /* Check if network coding is enabled */
1387 if (!atomic_read(&bat_priv
->network_coding
))
1390 /* We only handle unicast packets */
1391 payload
= skb_network_header(skb
);
1392 packet
= (struct batadv_unicast_packet
*)payload
;
1393 if (packet
->header
.packet_type
!= BATADV_UNICAST
)
1396 /* Try to find a coding opportunity and send the skb if one is found */
1397 if (batadv_nc_skb_dst_search(skb
, neigh_node
, ethhdr
))
1400 /* Find or create a nc_path for this src-dst pair */
1401 nc_path
= batadv_nc_get_path(bat_priv
,
1402 bat_priv
->nc
.coding_hash
,
1409 /* Add skb to nc_path */
1410 packet_id
= batadv_skb_crc32(skb
, payload
+ sizeof(*packet
));
1411 if (!batadv_nc_skb_add_to_path(skb
, nc_path
, neigh_node
, packet_id
))
1414 /* Packet is consumed */
1418 batadv_nc_path_free_ref(nc_path
);
1420 /* Packet is not consumed */
1425 * batadv_nc_skb_store_for_decoding - save a clone of the skb which can be used
1426 * when decoding coded packets
1427 * @bat_priv: the bat priv with all the soft interface information
1428 * @skb: data skb to store
1430 void batadv_nc_skb_store_for_decoding(struct batadv_priv
*bat_priv
,
1431 struct sk_buff
*skb
)
1433 struct batadv_unicast_packet
*packet
;
1434 struct batadv_nc_path
*nc_path
;
1435 struct ethhdr
*ethhdr
= (struct ethhdr
*)skb_mac_header(skb
);
1439 /* Check if network coding is enabled */
1440 if (!atomic_read(&bat_priv
->network_coding
))
1443 /* Check for supported packet type */
1444 payload
= skb_network_header(skb
);
1445 packet
= (struct batadv_unicast_packet
*)payload
;
1446 if (packet
->header
.packet_type
!= BATADV_UNICAST
)
1449 /* Find existing nc_path or create a new */
1450 nc_path
= batadv_nc_get_path(bat_priv
,
1451 bat_priv
->nc
.decoding_hash
,
1458 /* Clone skb and adjust skb->data to point at batman header */
1459 skb
= skb_clone(skb
, GFP_ATOMIC
);
1463 if (unlikely(!pskb_may_pull(skb
, ETH_HLEN
)))
1466 if (unlikely(!skb_pull_rcsum(skb
, ETH_HLEN
)))
1469 /* Add skb to nc_path */
1470 packet_id
= batadv_skb_crc32(skb
, payload
+ sizeof(*packet
));
1471 if (!batadv_nc_skb_add_to_path(skb
, nc_path
, NULL
, packet_id
))
1474 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_BUFFER
);
1480 batadv_nc_path_free_ref(nc_path
);
1486 * batadv_nc_skb_store_sniffed_unicast - check if a received unicast packet
1487 * should be saved in the decoding buffer and, if so, store it there
1488 * @bat_priv: the bat priv with all the soft interface information
1489 * @skb: unicast skb to store
1491 void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv
*bat_priv
,
1492 struct sk_buff
*skb
)
1494 struct ethhdr
*ethhdr
= (struct ethhdr
*)skb_mac_header(skb
);
1496 if (batadv_is_my_mac(bat_priv
, ethhdr
->h_dest
))
1499 /* Set data pointer to MAC header to mimic packets from our tx path */
1500 skb_push(skb
, ETH_HLEN
);
1502 batadv_nc_skb_store_for_decoding(bat_priv
, skb
);
1506 * batadv_nc_skb_decode_packet - decode given skb using the decode data stored
1508 * @bat_priv: the bat priv with all the soft interface information
1509 * @skb: unicast skb to decode
1510 * @nc_packet: decode data needed to decode the skb
1512 * Returns pointer to decoded unicast packet if the packet was decoded or NULL
1513 * in case of an error.
1515 static struct batadv_unicast_packet
*
1516 batadv_nc_skb_decode_packet(struct batadv_priv
*bat_priv
, struct sk_buff
*skb
,
1517 struct batadv_nc_packet
*nc_packet
)
1519 const int h_size
= sizeof(struct batadv_unicast_packet
);
1520 const int h_diff
= sizeof(struct batadv_coded_packet
) - h_size
;
1521 struct batadv_unicast_packet
*unicast_packet
;
1522 struct batadv_coded_packet coded_packet_tmp
;
1523 struct ethhdr
*ethhdr
, ethhdr_tmp
;
1524 uint8_t *orig_dest
, ttl
, ttvn
;
1525 unsigned int coding_len
;
1528 /* Save headers temporarily */
1529 memcpy(&coded_packet_tmp
, skb
->data
, sizeof(coded_packet_tmp
));
1530 memcpy(ðhdr_tmp
, skb_mac_header(skb
), sizeof(ethhdr_tmp
));
1532 if (skb_cow(skb
, 0) < 0)
1535 if (unlikely(!skb_pull_rcsum(skb
, h_diff
)))
1538 /* Data points to batman header, so set mac header 14 bytes before
1539 * and network to data
1541 skb_set_mac_header(skb
, -ETH_HLEN
);
1542 skb_reset_network_header(skb
);
1544 /* Reconstruct original mac header */
1545 ethhdr
= (struct ethhdr
*)skb_mac_header(skb
);
1546 memcpy(ethhdr
, ðhdr_tmp
, sizeof(*ethhdr
));
1548 /* Select the correct unicast header information based on the location
1549 * of our mac address in the coded_packet header
1551 if (batadv_is_my_mac(bat_priv
, coded_packet_tmp
.second_dest
)) {
1552 /* If we are the second destination the packet was overheard,
1553 * so the Ethernet address must be copied to h_dest and
1554 * pkt_type changed from PACKET_OTHERHOST to PACKET_HOST
1556 memcpy(ethhdr
->h_dest
, coded_packet_tmp
.second_dest
, ETH_ALEN
);
1557 skb
->pkt_type
= PACKET_HOST
;
1559 orig_dest
= coded_packet_tmp
.second_orig_dest
;
1560 ttl
= coded_packet_tmp
.second_ttl
;
1561 ttvn
= coded_packet_tmp
.second_ttvn
;
1563 orig_dest
= coded_packet_tmp
.first_orig_dest
;
1564 ttl
= coded_packet_tmp
.header
.ttl
;
1565 ttvn
= coded_packet_tmp
.first_ttvn
;
1568 coding_len
= ntohs(coded_packet_tmp
.coded_len
);
1570 if (coding_len
> skb
->len
)
1573 /* Here the magic is reversed:
1574 * extract the missing packet from the received coded packet
1576 batadv_nc_memxor(skb
->data
+ h_size
,
1577 nc_packet
->skb
->data
+ h_size
,
1580 /* Resize decoded skb if decoded with larger packet */
1581 if (nc_packet
->skb
->len
> coding_len
+ h_size
) {
1582 err
= pskb_trim_rcsum(skb
, coding_len
+ h_size
);
1587 /* Create decoded unicast packet */
1588 unicast_packet
= (struct batadv_unicast_packet
*)skb
->data
;
1589 unicast_packet
->header
.packet_type
= BATADV_UNICAST
;
1590 unicast_packet
->header
.version
= BATADV_COMPAT_VERSION
;
1591 unicast_packet
->header
.ttl
= ttl
;
1592 memcpy(unicast_packet
->dest
, orig_dest
, ETH_ALEN
);
1593 unicast_packet
->ttvn
= ttvn
;
1595 batadv_nc_packet_free(nc_packet
);
1596 return unicast_packet
;
1600 * batadv_nc_find_decoding_packet - search through buffered decoding data to
1601 * find the data needed to decode the coded packet
1602 * @bat_priv: the bat priv with all the soft interface information
1603 * @ethhdr: pointer to the ethernet header inside the coded packet
1604 * @coded: coded packet we try to find decode data for
1606 * Returns pointer to nc packet if the needed data was found or NULL otherwise.
1608 static struct batadv_nc_packet
*
1609 batadv_nc_find_decoding_packet(struct batadv_priv
*bat_priv
,
1610 struct ethhdr
*ethhdr
,
1611 struct batadv_coded_packet
*coded
)
1613 struct batadv_hashtable
*hash
= bat_priv
->nc
.decoding_hash
;
1614 struct batadv_nc_packet
*tmp_nc_packet
, *nc_packet
= NULL
;
1615 struct batadv_nc_path
*nc_path
, nc_path_key
;
1616 uint8_t *dest
, *source
;
1623 /* Select the correct packet id based on the location of our mac-addr */
1624 dest
= ethhdr
->h_source
;
1625 if (!batadv_is_my_mac(bat_priv
, coded
->second_dest
)) {
1626 source
= coded
->second_source
;
1627 packet_id
= coded
->second_crc
;
1629 source
= coded
->first_source
;
1630 packet_id
= coded
->first_crc
;
1633 batadv_nc_hash_key_gen(&nc_path_key
, source
, dest
);
1634 index
= batadv_nc_hash_choose(&nc_path_key
, hash
->size
);
1636 /* Search for matching coding path */
1638 hlist_for_each_entry_rcu(nc_path
, &hash
->table
[index
], hash_entry
) {
1639 /* Find matching nc_packet */
1640 spin_lock_bh(&nc_path
->packet_list_lock
);
1641 list_for_each_entry(tmp_nc_packet
,
1642 &nc_path
->packet_list
, list
) {
1643 if (packet_id
== tmp_nc_packet
->packet_id
) {
1644 list_del(&tmp_nc_packet
->list
);
1646 nc_packet
= tmp_nc_packet
;
1650 spin_unlock_bh(&nc_path
->packet_list_lock
);
1658 batadv_dbg(BATADV_DBG_NC
, bat_priv
,
1659 "No decoding packet found for %u\n", packet_id
);
1665 * batadv_nc_recv_coded_packet - try to decode coded packet and enqueue the
1666 * resulting unicast packet
1667 * @skb: incoming coded packet
1668 * @recv_if: pointer to interface this packet was received on
1670 static int batadv_nc_recv_coded_packet(struct sk_buff
*skb
,
1671 struct batadv_hard_iface
*recv_if
)
1673 struct batadv_priv
*bat_priv
= netdev_priv(recv_if
->soft_iface
);
1674 struct batadv_unicast_packet
*unicast_packet
;
1675 struct batadv_coded_packet
*coded_packet
;
1676 struct batadv_nc_packet
*nc_packet
;
1677 struct ethhdr
*ethhdr
;
1678 int hdr_size
= sizeof(*coded_packet
);
1680 /* Check if network coding is enabled */
1681 if (!atomic_read(&bat_priv
->network_coding
))
1684 /* Make sure we can access (and remove) header */
1685 if (unlikely(!pskb_may_pull(skb
, hdr_size
)))
1688 coded_packet
= (struct batadv_coded_packet
*)skb
->data
;
1689 ethhdr
= (struct ethhdr
*)skb_mac_header(skb
);
1691 /* Verify frame is destined for us */
1692 if (!batadv_is_my_mac(bat_priv
, ethhdr
->h_dest
) &&
1693 !batadv_is_my_mac(bat_priv
, coded_packet
->second_dest
))
1696 /* Update stat counter */
1697 if (batadv_is_my_mac(bat_priv
, coded_packet
->second_dest
))
1698 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_SNIFFED
);
1700 nc_packet
= batadv_nc_find_decoding_packet(bat_priv
, ethhdr
,
1703 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_DECODE_FAILED
);
1707 /* Make skb's linear, because decoding accesses the entire buffer */
1708 if (skb_linearize(skb
) < 0)
1709 goto free_nc_packet
;
1711 if (skb_linearize(nc_packet
->skb
) < 0)
1712 goto free_nc_packet
;
1714 /* Decode the packet */
1715 unicast_packet
= batadv_nc_skb_decode_packet(bat_priv
, skb
, nc_packet
);
1716 if (!unicast_packet
) {
1717 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_DECODE_FAILED
);
1718 goto free_nc_packet
;
1721 /* Mark packet as decoded to do correct recoding when forwarding */
1722 BATADV_SKB_CB(skb
)->decoded
= true;
1723 batadv_inc_counter(bat_priv
, BATADV_CNT_NC_DECODE
);
1724 batadv_add_counter(bat_priv
, BATADV_CNT_NC_DECODE_BYTES
,
1725 skb
->len
+ ETH_HLEN
);
1726 return batadv_recv_unicast_packet(skb
, recv_if
);
1729 batadv_nc_packet_free(nc_packet
);
1734 * batadv_nc_mesh_free - clean up network coding memory
1735 * @bat_priv: the bat priv with all the soft interface information
1737 void batadv_nc_mesh_free(struct batadv_priv
*bat_priv
)
1739 cancel_delayed_work_sync(&bat_priv
->nc
.work
);
1741 batadv_nc_purge_paths(bat_priv
, bat_priv
->nc
.coding_hash
, NULL
);
1742 batadv_hash_destroy(bat_priv
->nc
.coding_hash
);
1743 batadv_nc_purge_paths(bat_priv
, bat_priv
->nc
.decoding_hash
, NULL
);
1744 batadv_hash_destroy(bat_priv
->nc
.decoding_hash
);
1748 * batadv_nc_nodes_seq_print_text - print the nc node information
1749 * @seq: seq file to print on
1752 int batadv_nc_nodes_seq_print_text(struct seq_file
*seq
, void *offset
)
1754 struct net_device
*net_dev
= (struct net_device
*)seq
->private;
1755 struct batadv_priv
*bat_priv
= netdev_priv(net_dev
);
1756 struct batadv_hashtable
*hash
= bat_priv
->orig_hash
;
1757 struct batadv_hard_iface
*primary_if
;
1758 struct hlist_head
*head
;
1759 struct batadv_orig_node
*orig_node
;
1760 struct batadv_nc_node
*nc_node
;
1763 primary_if
= batadv_seq_print_text_primary_if_get(seq
);
1767 /* Traverse list of originators */
1768 for (i
= 0; i
< hash
->size
; i
++) {
1769 head
= &hash
->table
[i
];
1771 /* For each orig_node in this bin */
1773 hlist_for_each_entry_rcu(orig_node
, head
, hash_entry
) {
1774 seq_printf(seq
, "Node: %pM\n", orig_node
->orig
);
1776 seq_puts(seq
, " Ingoing: ");
1777 /* For each in_nc_node to this orig_node */
1778 list_for_each_entry_rcu(nc_node
,
1779 &orig_node
->in_coding_list
,
1781 seq_printf(seq
, "%pM ",
1783 seq_puts(seq
, "\n");
1785 seq_puts(seq
, " Outgoing: ");
1786 /* For out_nc_node to this orig_node */
1787 list_for_each_entry_rcu(nc_node
,
1788 &orig_node
->out_coding_list
,
1790 seq_printf(seq
, "%pM ",
1792 seq_puts(seq
, "\n\n");
1799 batadv_hardif_free_ref(primary_if
);
1804 * batadv_nc_init_debugfs - create nc folder and related files in debugfs
1805 * @bat_priv: the bat priv with all the soft interface information
1807 int batadv_nc_init_debugfs(struct batadv_priv
*bat_priv
)
1809 struct dentry
*nc_dir
, *file
;
1811 nc_dir
= debugfs_create_dir("nc", bat_priv
->debug_dir
);
1815 file
= debugfs_create_u8("min_tq", S_IRUGO
| S_IWUSR
, nc_dir
,
1816 &bat_priv
->nc
.min_tq
);
1820 file
= debugfs_create_u32("max_fwd_delay", S_IRUGO
| S_IWUSR
, nc_dir
,
1821 &bat_priv
->nc
.max_fwd_delay
);
1825 file
= debugfs_create_u32("max_buffer_time", S_IRUGO
| S_IWUSR
, nc_dir
,
1826 &bat_priv
->nc
.max_buffer_time
);