1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (C) 2012-2018 B.A.T.M.A.N. contributors:
4 * Martin Hundebøll, Jeppe Ledet-Pedersen
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, see <http://www.gnu.org/licenses/>.
19 #include "network-coding.h"
22 #include <linux/atomic.h>
23 #include <linux/bitops.h>
24 #include <linux/byteorder/generic.h>
25 #include <linux/compiler.h>
26 #include <linux/debugfs.h>
27 #include <linux/errno.h>
28 #include <linux/etherdevice.h>
29 #include <linux/gfp.h>
30 #include <linux/if_ether.h>
31 #include <linux/if_packet.h>
32 #include <linux/init.h>
33 #include <linux/jhash.h>
34 #include <linux/jiffies.h>
35 #include <linux/kernel.h>
36 #include <linux/kref.h>
37 #include <linux/list.h>
38 #include <linux/lockdep.h>
39 #include <linux/net.h>
40 #include <linux/netdevice.h>
41 #include <linux/printk.h>
42 #include <linux/random.h>
43 #include <linux/rculist.h>
44 #include <linux/rcupdate.h>
45 #include <linux/seq_file.h>
46 #include <linux/skbuff.h>
47 #include <linux/slab.h>
48 #include <linux/spinlock.h>
49 #include <linux/stddef.h>
50 #include <linux/string.h>
51 #include <linux/workqueue.h>
52 #include <uapi/linux/batadv_packet.h>
54 #include "hard-interface.h"
57 #include "originator.h"
62 static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
63 static struct lock_class_key batadv_nc_decoding_hash_lock_class_key;
65 static void batadv_nc_worker(struct work_struct *work);
66 static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
67 struct batadv_hard_iface *recv_if);
70 * batadv_nc_init() - one-time initialization for network coding
72 * Return: 0 on success or negative error number in case of failure
74 int __init batadv_nc_init(void)
78 /* Register our packet type */
79 ret = batadv_recv_handler_register(BATADV_CODED,
80 batadv_nc_recv_coded_packet);
86 * batadv_nc_start_timer() - initialise the nc periodic worker
87 * @bat_priv: the bat priv with all the soft interface information
89 static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
91 queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,
92 msecs_to_jiffies(10));
96 * batadv_nc_tvlv_container_update() - update the network coding tvlv container
97 * after network coding setting change
98 * @bat_priv: the bat priv with all the soft interface information
100 static void batadv_nc_tvlv_container_update(struct batadv_priv *bat_priv)
104 nc_mode = atomic_read(&bat_priv->network_coding);
108 batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);
111 batadv_tvlv_container_register(bat_priv, BATADV_TVLV_NC, 1,
118 * batadv_nc_status_update() - update the network coding tvlv container after
119 * network coding setting change
120 * @net_dev: the soft interface net device
122 void batadv_nc_status_update(struct net_device *net_dev)
124 struct batadv_priv *bat_priv = netdev_priv(net_dev);
126 batadv_nc_tvlv_container_update(bat_priv);
130 * batadv_nc_tvlv_ogm_handler_v1() - process incoming nc tvlv container
131 * @bat_priv: the bat priv with all the soft interface information
132 * @orig: the orig_node of the ogm
133 * @flags: flags indicating the tvlv state (see batadv_tvlv_handler_flags)
134 * @tvlv_value: tvlv buffer containing the gateway data
135 * @tvlv_value_len: tvlv buffer length
137 static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv,
138 struct batadv_orig_node *orig,
140 void *tvlv_value, u16 tvlv_value_len)
142 if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND)
143 clear_bit(BATADV_ORIG_CAPA_HAS_NC, &orig->capabilities);
145 set_bit(BATADV_ORIG_CAPA_HAS_NC, &orig->capabilities);
149 * batadv_nc_mesh_init() - initialise coding hash table and start house keeping
150 * @bat_priv: the bat priv with all the soft interface information
152 * Return: 0 on success or negative error number in case of failure
154 int batadv_nc_mesh_init(struct batadv_priv *bat_priv)
156 bat_priv->nc.timestamp_fwd_flush = jiffies;
157 bat_priv->nc.timestamp_sniffed_purge = jiffies;
159 if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash)
162 bat_priv->nc.coding_hash = batadv_hash_new(128);
163 if (!bat_priv->nc.coding_hash)
166 batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
167 &batadv_nc_coding_hash_lock_class_key);
169 bat_priv->nc.decoding_hash = batadv_hash_new(128);
170 if (!bat_priv->nc.decoding_hash)
173 batadv_hash_set_lock_class(bat_priv->nc.decoding_hash,
174 &batadv_nc_decoding_hash_lock_class_key);
176 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
177 batadv_nc_start_timer(bat_priv);
179 batadv_tvlv_handler_register(bat_priv, batadv_nc_tvlv_ogm_handler_v1,
180 NULL, BATADV_TVLV_NC, 1,
181 BATADV_TVLV_HANDLER_OGM_CIFNOTFND);
182 batadv_nc_tvlv_container_update(bat_priv);
190 * batadv_nc_init_bat_priv() - initialise the nc specific bat_priv variables
191 * @bat_priv: the bat priv with all the soft interface information
193 void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
195 atomic_set(&bat_priv->network_coding, 0);
196 bat_priv->nc.min_tq = 200;
197 bat_priv->nc.max_fwd_delay = 10;
198 bat_priv->nc.max_buffer_time = 200;
202 * batadv_nc_init_orig() - initialise the nc fields of an orig_node
203 * @orig_node: the orig_node which is going to be initialised
205 void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
207 INIT_LIST_HEAD(&orig_node->in_coding_list);
208 INIT_LIST_HEAD(&orig_node->out_coding_list);
209 spin_lock_init(&orig_node->in_coding_list_lock);
210 spin_lock_init(&orig_node->out_coding_list_lock);
214 * batadv_nc_node_release() - release nc_node from lists and queue for free
215 * after rcu grace period
216 * @ref: kref pointer of the nc_node
218 static void batadv_nc_node_release(struct kref *ref)
220 struct batadv_nc_node *nc_node;
222 nc_node = container_of(ref, struct batadv_nc_node, refcount);
224 batadv_orig_node_put(nc_node->orig_node);
225 kfree_rcu(nc_node, rcu);
229 * batadv_nc_node_put() - decrement the nc_node refcounter and possibly
231 * @nc_node: nc_node to be free'd
233 static void batadv_nc_node_put(struct batadv_nc_node *nc_node)
235 kref_put(&nc_node->refcount, batadv_nc_node_release);
239 * batadv_nc_path_release() - release nc_path from lists and queue for free
240 * after rcu grace period
241 * @ref: kref pointer of the nc_path
243 static void batadv_nc_path_release(struct kref *ref)
245 struct batadv_nc_path *nc_path;
247 nc_path = container_of(ref, struct batadv_nc_path, refcount);
249 kfree_rcu(nc_path, rcu);
253 * batadv_nc_path_put() - decrement the nc_path refcounter and possibly
255 * @nc_path: nc_path to be free'd
257 static void batadv_nc_path_put(struct batadv_nc_path *nc_path)
259 kref_put(&nc_path->refcount, batadv_nc_path_release);
263 * batadv_nc_packet_free() - frees nc packet
264 * @nc_packet: the nc packet to free
265 * @dropped: whether the packet is freed because is is dropped
267 static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet,
271 kfree_skb(nc_packet->skb);
273 consume_skb(nc_packet->skb);
275 batadv_nc_path_put(nc_packet->nc_path);
280 * batadv_nc_to_purge_nc_node() - checks whether an nc node has to be purged
281 * @bat_priv: the bat priv with all the soft interface information
282 * @nc_node: the nc node to check
284 * Return: true if the entry has to be purged now, false otherwise
286 static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
287 struct batadv_nc_node *nc_node)
289 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
292 return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
296 * batadv_nc_to_purge_nc_path_coding() - checks whether an nc path has timed out
297 * @bat_priv: the bat priv with all the soft interface information
298 * @nc_path: the nc path to check
300 * Return: true if the entry has to be purged now, false otherwise
302 static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,
303 struct batadv_nc_path *nc_path)
305 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
308 /* purge the path when no packets has been added for 10 times the
311 return batadv_has_timed_out(nc_path->last_valid,
312 bat_priv->nc.max_fwd_delay * 10);
316 * batadv_nc_to_purge_nc_path_decoding() - checks whether an nc path has timed
318 * @bat_priv: the bat priv with all the soft interface information
319 * @nc_path: the nc path to check
321 * Return: true if the entry has to be purged now, false otherwise
323 static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv *bat_priv,
324 struct batadv_nc_path *nc_path)
326 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
329 /* purge the path when no packets has been added for 10 times the
332 return batadv_has_timed_out(nc_path->last_valid,
333 bat_priv->nc.max_buffer_time * 10);
337 * batadv_nc_purge_orig_nc_nodes() - go through list of nc nodes and purge stale
339 * @bat_priv: the bat priv with all the soft interface information
340 * @list: list of nc nodes
341 * @lock: nc node list lock
342 * @to_purge: function in charge to decide whether an entry has to be purged or
343 * not. This function takes the nc node as argument and has to return
344 * a boolean value: true if the entry has to be deleted, false
348 batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
349 struct list_head *list,
351 bool (*to_purge)(struct batadv_priv *,
352 struct batadv_nc_node *))
354 struct batadv_nc_node *nc_node, *nc_node_tmp;
356 /* For each nc_node in list */
358 list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
359 /* if an helper function has been passed as parameter,
360 * ask it if the entry has to be purged or not
362 if (to_purge && !to_purge(bat_priv, nc_node))
365 batadv_dbg(BATADV_DBG_NC, bat_priv,
366 "Removing nc_node %pM -> %pM\n",
367 nc_node->addr, nc_node->orig_node->orig);
368 list_del_rcu(&nc_node->list);
369 batadv_nc_node_put(nc_node);
371 spin_unlock_bh(lock);
375 * batadv_nc_purge_orig() - purges all nc node data attached of the given
377 * @bat_priv: the bat priv with all the soft interface information
378 * @orig_node: orig_node with the nc node entries to be purged
379 * @to_purge: function in charge to decide whether an entry has to be purged or
380 * not. This function takes the nc node as argument and has to return
381 * a boolean value: true is the entry has to be deleted, false
384 void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
385 struct batadv_orig_node *orig_node,
386 bool (*to_purge)(struct batadv_priv *,
387 struct batadv_nc_node *))
389 /* Check ingoing nc_node's of this orig_node */
390 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
391 &orig_node->in_coding_list_lock,
394 /* Check outgoing nc_node's of this orig_node */
395 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
396 &orig_node->out_coding_list_lock,
401 * batadv_nc_purge_orig_hash() - traverse entire originator hash to check if
402 * they have timed out nc nodes
403 * @bat_priv: the bat priv with all the soft interface information
405 static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
407 struct batadv_hashtable *hash = bat_priv->orig_hash;
408 struct hlist_head *head;
409 struct batadv_orig_node *orig_node;
415 /* For each orig_node */
416 for (i = 0; i < hash->size; i++) {
417 head = &hash->table[i];
420 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
421 batadv_nc_purge_orig(bat_priv, orig_node,
422 batadv_nc_to_purge_nc_node);
428 * batadv_nc_purge_paths() - traverse all nc paths part of the hash and remove
430 * @bat_priv: the bat priv with all the soft interface information
431 * @hash: hash table containing the nc paths to check
432 * @to_purge: function in charge to decide whether an entry has to be purged or
433 * not. This function takes the nc node as argument and has to return
434 * a boolean value: true is the entry has to be deleted, false
437 static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,
438 struct batadv_hashtable *hash,
439 bool (*to_purge)(struct batadv_priv *,
440 struct batadv_nc_path *))
442 struct hlist_head *head;
443 struct hlist_node *node_tmp;
444 struct batadv_nc_path *nc_path;
445 spinlock_t *lock; /* Protects lists in hash */
448 for (i = 0; i < hash->size; i++) {
449 head = &hash->table[i];
450 lock = &hash->list_locks[i];
452 /* For each nc_path in this bin */
454 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {
455 /* if an helper function has been passed as parameter,
456 * ask it if the entry has to be purged or not
458 if (to_purge && !to_purge(bat_priv, nc_path))
461 /* purging an non-empty nc_path should never happen, but
462 * is observed under high CPU load. Delay the purging
463 * until next iteration to allow the packet_list to be
466 if (!unlikely(list_empty(&nc_path->packet_list))) {
467 net_ratelimited_function(printk,
469 "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
475 /* nc_path is unused, so remove it */
476 batadv_dbg(BATADV_DBG_NC, bat_priv,
477 "Remove nc_path %pM -> %pM\n",
478 nc_path->prev_hop, nc_path->next_hop);
479 hlist_del_rcu(&nc_path->hash_entry);
480 batadv_nc_path_put(nc_path);
482 spin_unlock_bh(lock);
487 * batadv_nc_hash_key_gen() - computes the nc_path hash key
488 * @key: buffer to hold the final hash key
489 * @src: source ethernet mac address going into the hash key
490 * @dst: destination ethernet mac address going into the hash key
492 static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,
495 memcpy(key->prev_hop, src, sizeof(key->prev_hop));
496 memcpy(key->next_hop, dst, sizeof(key->next_hop));
500 * batadv_nc_hash_choose() - compute the hash value for an nc path
501 * @data: data to hash
502 * @size: size of the hash table
504 * Return: the selected index in the hash table for the given data.
506 static u32 batadv_nc_hash_choose(const void *data, u32 size)
508 const struct batadv_nc_path *nc_path = data;
511 hash = jhash(&nc_path->prev_hop, sizeof(nc_path->prev_hop), hash);
512 hash = jhash(&nc_path->next_hop, sizeof(nc_path->next_hop), hash);
518 * batadv_nc_hash_compare() - comparing function used in the network coding hash
520 * @node: node in the local table
521 * @data2: second object to compare the node to
523 * Return: true if the two entry are the same, false otherwise
525 static bool batadv_nc_hash_compare(const struct hlist_node *node,
528 const struct batadv_nc_path *nc_path1, *nc_path2;
530 nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);
533 /* Return 1 if the two keys are identical */
534 if (!batadv_compare_eth(nc_path1->prev_hop, nc_path2->prev_hop))
537 if (!batadv_compare_eth(nc_path1->next_hop, nc_path2->next_hop))
544 * batadv_nc_hash_find() - search for an existing nc path and return it
545 * @hash: hash table containing the nc path
548 * Return: the nc_path if found, NULL otherwise.
550 static struct batadv_nc_path *
551 batadv_nc_hash_find(struct batadv_hashtable *hash,
554 struct hlist_head *head;
555 struct batadv_nc_path *nc_path, *nc_path_tmp = NULL;
561 index = batadv_nc_hash_choose(data, hash->size);
562 head = &hash->table[index];
565 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
566 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data))
569 if (!kref_get_unless_zero(&nc_path->refcount))
572 nc_path_tmp = nc_path;
581 * batadv_nc_send_packet() - send non-coded packet and free nc_packet struct
582 * @nc_packet: the nc packet to send
584 static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet)
586 batadv_send_unicast_skb(nc_packet->skb, nc_packet->neigh_node);
587 nc_packet->skb = NULL;
588 batadv_nc_packet_free(nc_packet, false);
592 * batadv_nc_sniffed_purge() - Checks timestamp of given sniffed nc_packet.
593 * @bat_priv: the bat priv with all the soft interface information
594 * @nc_path: the nc path the packet belongs to
595 * @nc_packet: the nc packet to be checked
597 * Checks whether the given sniffed (overheard) nc_packet has hit its buffering
598 * timeout. If so, the packet is no longer kept and the entry deleted from the
599 * queue. Has to be called with the appropriate locks.
601 * Return: false as soon as the entry in the fifo queue has not been timed out
602 * yet and true otherwise.
604 static bool batadv_nc_sniffed_purge(struct batadv_priv *bat_priv,
605 struct batadv_nc_path *nc_path,
606 struct batadv_nc_packet *nc_packet)
608 unsigned long timeout = bat_priv->nc.max_buffer_time;
611 lockdep_assert_held(&nc_path->packet_list_lock);
613 /* Packets are added to tail, so the remaining packets did not time
614 * out and we can stop processing the current queue
616 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
617 !batadv_has_timed_out(nc_packet->timestamp, timeout))
620 /* purge nc packet */
621 list_del(&nc_packet->list);
622 batadv_nc_packet_free(nc_packet, true);
631 * batadv_nc_fwd_flush() - Checks the timestamp of the given nc packet.
632 * @bat_priv: the bat priv with all the soft interface information
633 * @nc_path: the nc path the packet belongs to
634 * @nc_packet: the nc packet to be checked
636 * Checks whether the given nc packet has hit its forward timeout. If so, the
637 * packet is no longer delayed, immediately sent and the entry deleted from the
638 * queue. Has to be called with the appropriate locks.
640 * Return: false as soon as the entry in the fifo queue has not been timed out
641 * yet and true otherwise.
643 static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv,
644 struct batadv_nc_path *nc_path,
645 struct batadv_nc_packet *nc_packet)
647 unsigned long timeout = bat_priv->nc.max_fwd_delay;
649 lockdep_assert_held(&nc_path->packet_list_lock);
651 /* Packets are added to tail, so the remaining packets did not time
652 * out and we can stop processing the current queue
654 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
655 !batadv_has_timed_out(nc_packet->timestamp, timeout))
659 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
660 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
661 nc_packet->skb->len + ETH_HLEN);
662 list_del(&nc_packet->list);
663 batadv_nc_send_packet(nc_packet);
669 * batadv_nc_process_nc_paths() - traverse given nc packet pool and free timed
671 * @bat_priv: the bat priv with all the soft interface information
672 * @hash: to be processed hash table
673 * @process_fn: Function called to process given nc packet. Should return true
674 * to encourage this function to proceed with the next packet.
675 * Otherwise the rest of the current queue is skipped.
678 batadv_nc_process_nc_paths(struct batadv_priv *bat_priv,
679 struct batadv_hashtable *hash,
680 bool (*process_fn)(struct batadv_priv *,
681 struct batadv_nc_path *,
682 struct batadv_nc_packet *))
684 struct hlist_head *head;
685 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
686 struct batadv_nc_path *nc_path;
693 /* Loop hash table bins */
694 for (i = 0; i < hash->size; i++) {
695 head = &hash->table[i];
697 /* Loop coding paths */
699 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
701 spin_lock_bh(&nc_path->packet_list_lock);
702 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
703 &nc_path->packet_list, list) {
704 ret = process_fn(bat_priv, nc_path, nc_packet);
708 spin_unlock_bh(&nc_path->packet_list_lock);
715 * batadv_nc_worker() - periodic task for house keeping related to network
717 * @work: kernel work struct
719 static void batadv_nc_worker(struct work_struct *work)
721 struct delayed_work *delayed_work;
722 struct batadv_priv_nc *priv_nc;
723 struct batadv_priv *bat_priv;
724 unsigned long timeout;
726 delayed_work = to_delayed_work(work);
727 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
728 bat_priv = container_of(priv_nc, struct batadv_priv, nc);
730 batadv_nc_purge_orig_hash(bat_priv);
731 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash,
732 batadv_nc_to_purge_nc_path_coding);
733 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash,
734 batadv_nc_to_purge_nc_path_decoding);
736 timeout = bat_priv->nc.max_fwd_delay;
738 if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) {
739 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash,
740 batadv_nc_fwd_flush);
741 bat_priv->nc.timestamp_fwd_flush = jiffies;
744 if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge,
745 bat_priv->nc.max_buffer_time)) {
746 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash,
747 batadv_nc_sniffed_purge);
748 bat_priv->nc.timestamp_sniffed_purge = jiffies;
751 /* Schedule a new check */
752 batadv_nc_start_timer(bat_priv);
756 * batadv_can_nc_with_orig() - checks whether the given orig node is suitable
758 * @bat_priv: the bat priv with all the soft interface information
759 * @orig_node: neighboring orig node which may be used as nc candidate
760 * @ogm_packet: incoming ogm packet also used for the checks
763 * 1) The OGM must have the most recent sequence number.
764 * 2) The TTL must be decremented by one and only one.
765 * 3) The OGM must be received from the first hop from orig_node.
766 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
768 static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
769 struct batadv_orig_node *orig_node,
770 struct batadv_ogm_packet *ogm_packet)
772 struct batadv_orig_ifinfo *orig_ifinfo;
776 orig_ifinfo = batadv_orig_ifinfo_get(orig_node, BATADV_IF_DEFAULT);
780 last_ttl = orig_ifinfo->last_ttl;
781 last_real_seqno = orig_ifinfo->last_real_seqno;
782 batadv_orig_ifinfo_put(orig_ifinfo);
784 if (last_real_seqno != ntohl(ogm_packet->seqno))
786 if (last_ttl != ogm_packet->ttl + 1)
788 if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
790 if (ogm_packet->tq < bat_priv->nc.min_tq)
797 * batadv_nc_find_nc_node() - search for an existing nc node and return it
798 * @orig_node: orig node originating the ogm packet
799 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
800 * (can be equal to orig_node)
801 * @in_coding: traverse incoming or outgoing network coding list
803 * Return: the nc_node if found, NULL otherwise.
805 static struct batadv_nc_node *
806 batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
807 struct batadv_orig_node *orig_neigh_node,
810 struct batadv_nc_node *nc_node, *nc_node_out = NULL;
811 struct list_head *list;
814 list = &orig_neigh_node->in_coding_list;
816 list = &orig_neigh_node->out_coding_list;
818 /* Traverse list of nc_nodes to orig_node */
820 list_for_each_entry_rcu(nc_node, list, list) {
821 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
824 if (!kref_get_unless_zero(&nc_node->refcount))
828 nc_node_out = nc_node;
837 * batadv_nc_get_nc_node() - retrieves an nc node or creates the entry if it was
839 * @bat_priv: the bat priv with all the soft interface information
840 * @orig_node: orig node originating the ogm packet
841 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
842 * (can be equal to orig_node)
843 * @in_coding: traverse incoming or outgoing network coding list
845 * Return: the nc_node if found or created, NULL in case of an error.
847 static struct batadv_nc_node *
848 batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
849 struct batadv_orig_node *orig_node,
850 struct batadv_orig_node *orig_neigh_node,
853 struct batadv_nc_node *nc_node;
854 spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
855 struct list_head *list;
857 /* Select ingoing or outgoing coding node */
859 lock = &orig_neigh_node->in_coding_list_lock;
860 list = &orig_neigh_node->in_coding_list;
862 lock = &orig_neigh_node->out_coding_list_lock;
863 list = &orig_neigh_node->out_coding_list;
868 /* Check if nc_node is already added */
869 nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
875 nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
879 /* Initialize nc_node */
880 INIT_LIST_HEAD(&nc_node->list);
881 kref_init(&nc_node->refcount);
882 ether_addr_copy(nc_node->addr, orig_node->orig);
883 kref_get(&orig_neigh_node->refcount);
884 nc_node->orig_node = orig_neigh_node;
886 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
887 nc_node->addr, nc_node->orig_node->orig);
889 /* Add nc_node to orig_node */
890 kref_get(&nc_node->refcount);
891 list_add_tail_rcu(&nc_node->list, list);
894 spin_unlock_bh(lock);
900 * batadv_nc_update_nc_node() - updates stored incoming and outgoing nc node
901 * structs (best called on incoming OGMs)
902 * @bat_priv: the bat priv with all the soft interface information
903 * @orig_node: orig node originating the ogm packet
904 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
905 * (can be equal to orig_node)
906 * @ogm_packet: incoming ogm packet
907 * @is_single_hop_neigh: orig_node is a single hop neighbor
909 void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
910 struct batadv_orig_node *orig_node,
911 struct batadv_orig_node *orig_neigh_node,
912 struct batadv_ogm_packet *ogm_packet,
913 int is_single_hop_neigh)
915 struct batadv_nc_node *in_nc_node = NULL;
916 struct batadv_nc_node *out_nc_node = NULL;
918 /* Check if network coding is enabled */
919 if (!atomic_read(&bat_priv->network_coding))
922 /* check if orig node is network coding enabled */
923 if (!test_bit(BATADV_ORIG_CAPA_HAS_NC, &orig_node->capabilities))
926 /* accept ogms from 'good' neighbors and single hop neighbors */
927 if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
928 !is_single_hop_neigh)
931 /* Add orig_node as in_nc_node on hop */
932 in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
933 orig_neigh_node, true);
937 in_nc_node->last_seen = jiffies;
939 /* Add hop as out_nc_node on orig_node */
940 out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
945 out_nc_node->last_seen = jiffies;
949 batadv_nc_node_put(in_nc_node);
951 batadv_nc_node_put(out_nc_node);
955 * batadv_nc_get_path() - get existing nc_path or allocate a new one
956 * @bat_priv: the bat priv with all the soft interface information
957 * @hash: hash table containing the nc path
958 * @src: ethernet source address - first half of the nc path search key
959 * @dst: ethernet destination address - second half of the nc path search key
961 * Return: pointer to nc_path if the path was found or created, returns NULL
964 static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
965 struct batadv_hashtable *hash,
970 struct batadv_nc_path *nc_path, nc_path_key;
972 batadv_nc_hash_key_gen(&nc_path_key, src, dst);
974 /* Search for existing nc_path */
975 nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key);
978 /* Set timestamp to delay removal of nc_path */
979 nc_path->last_valid = jiffies;
983 /* No existing nc_path was found; create a new */
984 nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC);
989 /* Initialize nc_path */
990 INIT_LIST_HEAD(&nc_path->packet_list);
991 spin_lock_init(&nc_path->packet_list_lock);
992 kref_init(&nc_path->refcount);
993 nc_path->last_valid = jiffies;
994 ether_addr_copy(nc_path->next_hop, dst);
995 ether_addr_copy(nc_path->prev_hop, src);
997 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n",
1001 /* Add nc_path to hash table */
1002 kref_get(&nc_path->refcount);
1003 hash_added = batadv_hash_add(hash, batadv_nc_hash_compare,
1004 batadv_nc_hash_choose, &nc_path_key,
1005 &nc_path->hash_entry);
1007 if (hash_added < 0) {
1016 * batadv_nc_random_weight_tq() - scale the receivers TQ-value to avoid unfair
1017 * selection of a receiver with slightly lower TQ than the other
1018 * @tq: to be weighted tq value
1020 * Return: scaled tq value
1022 static u8 batadv_nc_random_weight_tq(u8 tq)
1024 /* randomize the estimated packet loss (max TQ - estimated TQ) */
1025 u8 rand_tq = prandom_u32_max(BATADV_TQ_MAX_VALUE + 1 - tq);
1027 /* convert to (randomized) estimated tq again */
1028 return BATADV_TQ_MAX_VALUE - rand_tq;
1032 * batadv_nc_memxor() - XOR destination with source
1033 * @dst: byte array to XOR into
1034 * @src: byte array to XOR from
1035 * @len: length of destination array
1037 static void batadv_nc_memxor(char *dst, const char *src, unsigned int len)
1041 for (i = 0; i < len; ++i)
1046 * batadv_nc_code_packets() - code a received unicast_packet with an nc packet
1047 * into a coded_packet and send it
1048 * @bat_priv: the bat priv with all the soft interface information
1049 * @skb: data skb to forward
1050 * @ethhdr: pointer to the ethernet header inside the skb
1051 * @nc_packet: structure containing the packet to the skb can be coded with
1052 * @neigh_node: next hop to forward packet to
1054 * Return: true if both packets are consumed, false otherwise.
1056 static bool batadv_nc_code_packets(struct batadv_priv *bat_priv,
1057 struct sk_buff *skb,
1058 struct ethhdr *ethhdr,
1059 struct batadv_nc_packet *nc_packet,
1060 struct batadv_neigh_node *neigh_node)
1062 u8 tq_weighted_neigh, tq_weighted_coding, tq_tmp;
1063 struct sk_buff *skb_dest, *skb_src;
1064 struct batadv_unicast_packet *packet1;
1065 struct batadv_unicast_packet *packet2;
1066 struct batadv_coded_packet *coded_packet;
1067 struct batadv_neigh_node *neigh_tmp, *router_neigh, *first_dest;
1068 struct batadv_neigh_node *router_coding = NULL, *second_dest;
1069 struct batadv_neigh_ifinfo *router_neigh_ifinfo = NULL;
1070 struct batadv_neigh_ifinfo *router_coding_ifinfo = NULL;
1071 u8 *first_source, *second_source;
1072 __be32 packet_id1, packet_id2;
1076 int unicast_size = sizeof(*packet1);
1077 int coded_size = sizeof(*coded_packet);
1078 int header_add = coded_size - unicast_size;
1080 /* TODO: do we need to consider the outgoing interface for
1083 router_neigh = batadv_orig_router_get(neigh_node->orig_node,
1088 router_neigh_ifinfo = batadv_neigh_ifinfo_get(router_neigh,
1090 if (!router_neigh_ifinfo)
1093 neigh_tmp = nc_packet->neigh_node;
1094 router_coding = batadv_orig_router_get(neigh_tmp->orig_node,
1099 router_coding_ifinfo = batadv_neigh_ifinfo_get(router_coding,
1101 if (!router_coding_ifinfo)
1104 tq_tmp = router_neigh_ifinfo->bat_iv.tq_avg;
1105 tq_weighted_neigh = batadv_nc_random_weight_tq(tq_tmp);
1106 tq_tmp = router_coding_ifinfo->bat_iv.tq_avg;
1107 tq_weighted_coding = batadv_nc_random_weight_tq(tq_tmp);
1109 /* Select one destination for the MAC-header dst-field based on
1110 * weighted TQ-values.
1112 if (tq_weighted_neigh >= tq_weighted_coding) {
1113 /* Destination from nc_packet is selected for MAC-header */
1114 first_dest = nc_packet->neigh_node;
1115 first_source = nc_packet->nc_path->prev_hop;
1116 second_dest = neigh_node;
1117 second_source = ethhdr->h_source;
1118 packet1 = (struct batadv_unicast_packet *)nc_packet->skb->data;
1119 packet2 = (struct batadv_unicast_packet *)skb->data;
1120 packet_id1 = nc_packet->packet_id;
1121 packet_id2 = batadv_skb_crc32(skb,
1122 skb->data + sizeof(*packet2));
1124 /* Destination for skb is selected for MAC-header */
1125 first_dest = neigh_node;
1126 first_source = ethhdr->h_source;
1127 second_dest = nc_packet->neigh_node;
1128 second_source = nc_packet->nc_path->prev_hop;
1129 packet1 = (struct batadv_unicast_packet *)skb->data;
1130 packet2 = (struct batadv_unicast_packet *)nc_packet->skb->data;
1131 packet_id1 = batadv_skb_crc32(skb,
1132 skb->data + sizeof(*packet1));
1133 packet_id2 = nc_packet->packet_id;
1136 /* Instead of zero padding the smallest data buffer, we
1137 * code into the largest.
1139 if (skb->len <= nc_packet->skb->len) {
1140 skb_dest = nc_packet->skb;
1144 skb_src = nc_packet->skb;
1147 /* coding_len is used when decoding the packet shorter packet */
1148 coding_len = skb_src->len - unicast_size;
1150 if (skb_linearize(skb_dest) < 0 || skb_linearize(skb_src) < 0)
1153 skb_push(skb_dest, header_add);
1155 coded_packet = (struct batadv_coded_packet *)skb_dest->data;
1156 skb_reset_mac_header(skb_dest);
1158 coded_packet->packet_type = BATADV_CODED;
1159 coded_packet->version = BATADV_COMPAT_VERSION;
1160 coded_packet->ttl = packet1->ttl;
1162 /* Info about first unicast packet */
1163 ether_addr_copy(coded_packet->first_source, first_source);
1164 ether_addr_copy(coded_packet->first_orig_dest, packet1->dest);
1165 coded_packet->first_crc = packet_id1;
1166 coded_packet->first_ttvn = packet1->ttvn;
1168 /* Info about second unicast packet */
1169 ether_addr_copy(coded_packet->second_dest, second_dest->addr);
1170 ether_addr_copy(coded_packet->second_source, second_source);
1171 ether_addr_copy(coded_packet->second_orig_dest, packet2->dest);
1172 coded_packet->second_crc = packet_id2;
1173 coded_packet->second_ttl = packet2->ttl;
1174 coded_packet->second_ttvn = packet2->ttvn;
1175 coded_packet->coded_len = htons(coding_len);
1177 /* This is where the magic happens: Code skb_src into skb_dest */
1178 batadv_nc_memxor(skb_dest->data + coded_size,
1179 skb_src->data + unicast_size, coding_len);
1181 /* Update counters accordingly */
1182 if (BATADV_SKB_CB(skb_src)->decoded &&
1183 BATADV_SKB_CB(skb_dest)->decoded) {
1184 /* Both packets are recoded */
1185 count = skb_src->len + ETH_HLEN;
1186 count += skb_dest->len + ETH_HLEN;
1187 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE, 2);
1188 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES, count);
1189 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1190 !BATADV_SKB_CB(skb_dest)->decoded) {
1191 /* Both packets are newly coded */
1192 count = skb_src->len + ETH_HLEN;
1193 count += skb_dest->len + ETH_HLEN;
1194 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE, 2);
1195 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES, count);
1196 } else if (BATADV_SKB_CB(skb_src)->decoded &&
1197 !BATADV_SKB_CB(skb_dest)->decoded) {
1198 /* skb_src recoded and skb_dest is newly coded */
1199 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1200 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1201 skb_src->len + ETH_HLEN);
1202 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1203 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1204 skb_dest->len + ETH_HLEN);
1205 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1206 BATADV_SKB_CB(skb_dest)->decoded) {
1207 /* skb_src is newly coded and skb_dest is recoded */
1208 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1209 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1210 skb_src->len + ETH_HLEN);
1211 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1212 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1213 skb_dest->len + ETH_HLEN);
1216 /* skb_src is now coded into skb_dest, so free it */
1217 consume_skb(skb_src);
1219 /* avoid duplicate free of skb from nc_packet */
1220 nc_packet->skb = NULL;
1221 batadv_nc_packet_free(nc_packet, false);
1223 /* Send the coded packet and return true */
1224 batadv_send_unicast_skb(skb_dest, first_dest);
1228 batadv_neigh_node_put(router_neigh);
1230 batadv_neigh_node_put(router_coding);
1231 if (router_neigh_ifinfo)
1232 batadv_neigh_ifinfo_put(router_neigh_ifinfo);
1233 if (router_coding_ifinfo)
1234 batadv_neigh_ifinfo_put(router_coding_ifinfo);
1239 * batadv_nc_skb_coding_possible() - true if a decoded skb is available at dst.
1240 * @skb: data skb to forward
1241 * @dst: destination mac address of the other skb to code with
1242 * @src: source mac address of skb
1244 * Whenever we network code a packet we have to check whether we received it in
1245 * a network coded form. If so, we may not be able to use it for coding because
1246 * some neighbors may also have received (overheard) the packet in the network
1247 * coded form without being able to decode it. It is hard to know which of the
1248 * neighboring nodes was able to decode the packet, therefore we can only
1249 * re-code the packet if the source of the previous encoded packet is involved.
1250 * Since the source encoded the packet we can be certain it has all necessary
1251 * decode information.
1253 * Return: true if coding of a decoded packet is allowed.
1255 static bool batadv_nc_skb_coding_possible(struct sk_buff *skb, u8 *dst, u8 *src)
1257 if (BATADV_SKB_CB(skb)->decoded && !batadv_compare_eth(dst, src))
1263 * batadv_nc_path_search() - Find the coding path matching in_nc_node and
1264 * out_nc_node to retrieve a buffered packet that can be used for coding.
1265 * @bat_priv: the bat priv with all the soft interface information
1266 * @in_nc_node: pointer to skb next hop's neighbor nc node
1267 * @out_nc_node: pointer to skb source's neighbor nc node
1268 * @skb: data skb to forward
1269 * @eth_dst: next hop mac address of skb
1271 * Return: true if coding of a decoded skb is allowed.
1273 static struct batadv_nc_packet *
1274 batadv_nc_path_search(struct batadv_priv *bat_priv,
1275 struct batadv_nc_node *in_nc_node,
1276 struct batadv_nc_node *out_nc_node,
1277 struct sk_buff *skb,
1280 struct batadv_nc_path *nc_path, nc_path_key;
1281 struct batadv_nc_packet *nc_packet_out = NULL;
1282 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
1283 struct batadv_hashtable *hash = bat_priv->nc.coding_hash;
1289 /* Create almost path key */
1290 batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr,
1292 idx = batadv_nc_hash_choose(&nc_path_key, hash->size);
1294 /* Check for coding opportunities in this nc_path */
1296 hlist_for_each_entry_rcu(nc_path, &hash->table[idx], hash_entry) {
1297 if (!batadv_compare_eth(nc_path->prev_hop, in_nc_node->addr))
1300 if (!batadv_compare_eth(nc_path->next_hop, out_nc_node->addr))
1303 spin_lock_bh(&nc_path->packet_list_lock);
1304 if (list_empty(&nc_path->packet_list)) {
1305 spin_unlock_bh(&nc_path->packet_list_lock);
1309 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
1310 &nc_path->packet_list, list) {
1311 if (!batadv_nc_skb_coding_possible(nc_packet->skb,
1316 /* Coding opportunity is found! */
1317 list_del(&nc_packet->list);
1318 nc_packet_out = nc_packet;
1322 spin_unlock_bh(&nc_path->packet_list_lock);
1327 return nc_packet_out;
1331 * batadv_nc_skb_src_search() - Loops through the list of neighoring nodes of
1332 * the skb's sender (may be equal to the originator).
1333 * @bat_priv: the bat priv with all the soft interface information
1334 * @skb: data skb to forward
1335 * @eth_dst: next hop mac address of skb
1336 * @eth_src: source mac address of skb
1337 * @in_nc_node: pointer to skb next hop's neighbor nc node
1339 * Return: an nc packet if a suitable coding packet was found, NULL otherwise.
1341 static struct batadv_nc_packet *
1342 batadv_nc_skb_src_search(struct batadv_priv *bat_priv,
1343 struct sk_buff *skb,
1346 struct batadv_nc_node *in_nc_node)
1348 struct batadv_orig_node *orig_node;
1349 struct batadv_nc_node *out_nc_node;
1350 struct batadv_nc_packet *nc_packet = NULL;
1352 orig_node = batadv_orig_hash_find(bat_priv, eth_src);
1357 list_for_each_entry_rcu(out_nc_node,
1358 &orig_node->out_coding_list, list) {
1359 /* Check if the skb is decoded and if recoding is possible */
1360 if (!batadv_nc_skb_coding_possible(skb,
1361 out_nc_node->addr, eth_src))
1364 /* Search for an opportunity in this nc_path */
1365 nc_packet = batadv_nc_path_search(bat_priv, in_nc_node,
1366 out_nc_node, skb, eth_dst);
1372 batadv_orig_node_put(orig_node);
1377 * batadv_nc_skb_store_before_coding() - set the ethernet src and dst of the
1378 * unicast skb before it is stored for use in later decoding
1379 * @bat_priv: the bat priv with all the soft interface information
1380 * @skb: data skb to store
1381 * @eth_dst_new: new destination mac address of skb
1383 static void batadv_nc_skb_store_before_coding(struct batadv_priv *bat_priv,
1384 struct sk_buff *skb,
1387 struct ethhdr *ethhdr;
1389 /* Copy skb header to change the mac header */
1390 skb = pskb_copy_for_clone(skb, GFP_ATOMIC);
1394 /* Set the mac header as if we actually sent the packet uncoded */
1395 ethhdr = eth_hdr(skb);
1396 ether_addr_copy(ethhdr->h_source, ethhdr->h_dest);
1397 ether_addr_copy(ethhdr->h_dest, eth_dst_new);
1399 /* Set data pointer to MAC header to mimic packets from our tx path */
1400 skb_push(skb, ETH_HLEN);
1402 /* Add the packet to the decoding packet pool */
1403 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1405 /* batadv_nc_skb_store_for_decoding() clones the skb, so we must free
1412 * batadv_nc_skb_dst_search() - Loops through list of neighboring nodes to dst.
1413 * @skb: data skb to forward
1414 * @neigh_node: next hop to forward packet to
1415 * @ethhdr: pointer to the ethernet header inside the skb
1417 * Loops through list of neighboring nodes the next hop has a good connection to
1418 * (receives OGMs with a sufficient quality). We need to find a neighbor of our
1419 * next hop that potentially sent a packet which our next hop also received
1420 * (overheard) and has stored for later decoding.
1422 * Return: true if the skb was consumed (encoded packet sent) or false otherwise
1424 static bool batadv_nc_skb_dst_search(struct sk_buff *skb,
1425 struct batadv_neigh_node *neigh_node,
1426 struct ethhdr *ethhdr)
1428 struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1429 struct batadv_priv *bat_priv = netdev_priv(netdev);
1430 struct batadv_orig_node *orig_node = neigh_node->orig_node;
1431 struct batadv_nc_node *nc_node;
1432 struct batadv_nc_packet *nc_packet = NULL;
1435 list_for_each_entry_rcu(nc_node, &orig_node->in_coding_list, list) {
1436 /* Search for coding opportunity with this in_nc_node */
1437 nc_packet = batadv_nc_skb_src_search(bat_priv, skb,
1439 ethhdr->h_source, nc_node);
1441 /* Opportunity was found, so stop searching */
1450 /* Save packets for later decoding */
1451 batadv_nc_skb_store_before_coding(bat_priv, skb,
1453 batadv_nc_skb_store_before_coding(bat_priv, nc_packet->skb,
1454 nc_packet->neigh_node->addr);
1456 /* Code and send packets */
1457 if (batadv_nc_code_packets(bat_priv, skb, ethhdr, nc_packet,
1461 /* out of mem ? Coding failed - we have to free the buffered packet
1462 * to avoid memleaks. The skb passed as argument will be dealt with
1463 * by the calling function.
1465 batadv_nc_send_packet(nc_packet);
1470 * batadv_nc_skb_add_to_path() - buffer skb for later encoding / decoding
1471 * @skb: skb to add to path
1472 * @nc_path: path to add skb to
1473 * @neigh_node: next hop to forward packet to
1474 * @packet_id: checksum to identify packet
1476 * Return: true if the packet was buffered or false in case of an error.
1478 static bool batadv_nc_skb_add_to_path(struct sk_buff *skb,
1479 struct batadv_nc_path *nc_path,
1480 struct batadv_neigh_node *neigh_node,
1483 struct batadv_nc_packet *nc_packet;
1485 nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC);
1489 /* Initialize nc_packet */
1490 nc_packet->timestamp = jiffies;
1491 nc_packet->packet_id = packet_id;
1492 nc_packet->skb = skb;
1493 nc_packet->neigh_node = neigh_node;
1494 nc_packet->nc_path = nc_path;
1496 /* Add coding packet to list */
1497 spin_lock_bh(&nc_path->packet_list_lock);
1498 list_add_tail(&nc_packet->list, &nc_path->packet_list);
1499 spin_unlock_bh(&nc_path->packet_list_lock);
1505 * batadv_nc_skb_forward() - try to code a packet or add it to the coding packet
1507 * @skb: data skb to forward
1508 * @neigh_node: next hop to forward packet to
1510 * Return: true if the skb was consumed (encoded packet sent) or false otherwise
1512 bool batadv_nc_skb_forward(struct sk_buff *skb,
1513 struct batadv_neigh_node *neigh_node)
1515 const struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1516 struct batadv_priv *bat_priv = netdev_priv(netdev);
1517 struct batadv_unicast_packet *packet;
1518 struct batadv_nc_path *nc_path;
1519 struct ethhdr *ethhdr = eth_hdr(skb);
1523 /* Check if network coding is enabled */
1524 if (!atomic_read(&bat_priv->network_coding))
1527 /* We only handle unicast packets */
1528 payload = skb_network_header(skb);
1529 packet = (struct batadv_unicast_packet *)payload;
1530 if (packet->packet_type != BATADV_UNICAST)
1533 /* Try to find a coding opportunity and send the skb if one is found */
1534 if (batadv_nc_skb_dst_search(skb, neigh_node, ethhdr))
1537 /* Find or create a nc_path for this src-dst pair */
1538 nc_path = batadv_nc_get_path(bat_priv,
1539 bat_priv->nc.coding_hash,
1546 /* Add skb to nc_path */
1547 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1548 if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id))
1551 /* Packet is consumed */
1555 batadv_nc_path_put(nc_path);
1557 /* Packet is not consumed */
1562 * batadv_nc_skb_store_for_decoding() - save a clone of the skb which can be
1563 * used when decoding coded packets
1564 * @bat_priv: the bat priv with all the soft interface information
1565 * @skb: data skb to store
1567 void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
1568 struct sk_buff *skb)
1570 struct batadv_unicast_packet *packet;
1571 struct batadv_nc_path *nc_path;
1572 struct ethhdr *ethhdr = eth_hdr(skb);
1576 /* Check if network coding is enabled */
1577 if (!atomic_read(&bat_priv->network_coding))
1580 /* Check for supported packet type */
1581 payload = skb_network_header(skb);
1582 packet = (struct batadv_unicast_packet *)payload;
1583 if (packet->packet_type != BATADV_UNICAST)
1586 /* Find existing nc_path or create a new */
1587 nc_path = batadv_nc_get_path(bat_priv,
1588 bat_priv->nc.decoding_hash,
1595 /* Clone skb and adjust skb->data to point at batman header */
1596 skb = skb_clone(skb, GFP_ATOMIC);
1600 if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
1603 if (unlikely(!skb_pull_rcsum(skb, ETH_HLEN)))
1606 /* Add skb to nc_path */
1607 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1608 if (!batadv_nc_skb_add_to_path(skb, nc_path, NULL, packet_id))
1611 batadv_inc_counter(bat_priv, BATADV_CNT_NC_BUFFER);
1617 batadv_nc_path_put(nc_path);
1623 * batadv_nc_skb_store_sniffed_unicast() - check if a received unicast packet
1624 * should be saved in the decoding buffer and, if so, store it there
1625 * @bat_priv: the bat priv with all the soft interface information
1626 * @skb: unicast skb to store
1628 void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
1629 struct sk_buff *skb)
1631 struct ethhdr *ethhdr = eth_hdr(skb);
1633 if (batadv_is_my_mac(bat_priv, ethhdr->h_dest))
1636 /* Set data pointer to MAC header to mimic packets from our tx path */
1637 skb_push(skb, ETH_HLEN);
1639 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1643 * batadv_nc_skb_decode_packet() - decode given skb using the decode data stored
1645 * @bat_priv: the bat priv with all the soft interface information
1646 * @skb: unicast skb to decode
1647 * @nc_packet: decode data needed to decode the skb
1649 * Return: pointer to decoded unicast packet if the packet was decoded or NULL
1650 * in case of an error.
1652 static struct batadv_unicast_packet *
1653 batadv_nc_skb_decode_packet(struct batadv_priv *bat_priv, struct sk_buff *skb,
1654 struct batadv_nc_packet *nc_packet)
1656 const int h_size = sizeof(struct batadv_unicast_packet);
1657 const int h_diff = sizeof(struct batadv_coded_packet) - h_size;
1658 struct batadv_unicast_packet *unicast_packet;
1659 struct batadv_coded_packet coded_packet_tmp;
1660 struct ethhdr *ethhdr, ethhdr_tmp;
1661 u8 *orig_dest, ttl, ttvn;
1662 unsigned int coding_len;
1665 /* Save headers temporarily */
1666 memcpy(&coded_packet_tmp, skb->data, sizeof(coded_packet_tmp));
1667 memcpy(ðhdr_tmp, skb_mac_header(skb), sizeof(ethhdr_tmp));
1669 if (skb_cow(skb, 0) < 0)
1672 if (unlikely(!skb_pull_rcsum(skb, h_diff)))
1675 /* Data points to batman header, so set mac header 14 bytes before
1676 * and network to data
1678 skb_set_mac_header(skb, -ETH_HLEN);
1679 skb_reset_network_header(skb);
1681 /* Reconstruct original mac header */
1682 ethhdr = eth_hdr(skb);
1683 *ethhdr = ethhdr_tmp;
1685 /* Select the correct unicast header information based on the location
1686 * of our mac address in the coded_packet header
1688 if (batadv_is_my_mac(bat_priv, coded_packet_tmp.second_dest)) {
1689 /* If we are the second destination the packet was overheard,
1690 * so the Ethernet address must be copied to h_dest and
1691 * pkt_type changed from PACKET_OTHERHOST to PACKET_HOST
1693 ether_addr_copy(ethhdr->h_dest, coded_packet_tmp.second_dest);
1694 skb->pkt_type = PACKET_HOST;
1696 orig_dest = coded_packet_tmp.second_orig_dest;
1697 ttl = coded_packet_tmp.second_ttl;
1698 ttvn = coded_packet_tmp.second_ttvn;
1700 orig_dest = coded_packet_tmp.first_orig_dest;
1701 ttl = coded_packet_tmp.ttl;
1702 ttvn = coded_packet_tmp.first_ttvn;
1705 coding_len = ntohs(coded_packet_tmp.coded_len);
1707 if (coding_len > skb->len)
1710 /* Here the magic is reversed:
1711 * extract the missing packet from the received coded packet
1713 batadv_nc_memxor(skb->data + h_size,
1714 nc_packet->skb->data + h_size,
1717 /* Resize decoded skb if decoded with larger packet */
1718 if (nc_packet->skb->len > coding_len + h_size) {
1719 err = pskb_trim_rcsum(skb, coding_len + h_size);
1724 /* Create decoded unicast packet */
1725 unicast_packet = (struct batadv_unicast_packet *)skb->data;
1726 unicast_packet->packet_type = BATADV_UNICAST;
1727 unicast_packet->version = BATADV_COMPAT_VERSION;
1728 unicast_packet->ttl = ttl;
1729 ether_addr_copy(unicast_packet->dest, orig_dest);
1730 unicast_packet->ttvn = ttvn;
1732 batadv_nc_packet_free(nc_packet, false);
1733 return unicast_packet;
1737 * batadv_nc_find_decoding_packet() - search through buffered decoding data to
1738 * find the data needed to decode the coded packet
1739 * @bat_priv: the bat priv with all the soft interface information
1740 * @ethhdr: pointer to the ethernet header inside the coded packet
1741 * @coded: coded packet we try to find decode data for
1743 * Return: pointer to nc packet if the needed data was found or NULL otherwise.
1745 static struct batadv_nc_packet *
1746 batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv,
1747 struct ethhdr *ethhdr,
1748 struct batadv_coded_packet *coded)
1750 struct batadv_hashtable *hash = bat_priv->nc.decoding_hash;
1751 struct batadv_nc_packet *tmp_nc_packet, *nc_packet = NULL;
1752 struct batadv_nc_path *nc_path, nc_path_key;
1760 /* Select the correct packet id based on the location of our mac-addr */
1761 dest = ethhdr->h_source;
1762 if (!batadv_is_my_mac(bat_priv, coded->second_dest)) {
1763 source = coded->second_source;
1764 packet_id = coded->second_crc;
1766 source = coded->first_source;
1767 packet_id = coded->first_crc;
1770 batadv_nc_hash_key_gen(&nc_path_key, source, dest);
1771 index = batadv_nc_hash_choose(&nc_path_key, hash->size);
1773 /* Search for matching coding path */
1775 hlist_for_each_entry_rcu(nc_path, &hash->table[index], hash_entry) {
1776 /* Find matching nc_packet */
1777 spin_lock_bh(&nc_path->packet_list_lock);
1778 list_for_each_entry(tmp_nc_packet,
1779 &nc_path->packet_list, list) {
1780 if (packet_id == tmp_nc_packet->packet_id) {
1781 list_del(&tmp_nc_packet->list);
1783 nc_packet = tmp_nc_packet;
1787 spin_unlock_bh(&nc_path->packet_list_lock);
1795 batadv_dbg(BATADV_DBG_NC, bat_priv,
1796 "No decoding packet found for %u\n", packet_id);
1802 * batadv_nc_recv_coded_packet() - try to decode coded packet and enqueue the
1803 * resulting unicast packet
1804 * @skb: incoming coded packet
1805 * @recv_if: pointer to interface this packet was received on
1807 * Return: NET_RX_SUCCESS if the packet has been consumed or NET_RX_DROP
1810 static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
1811 struct batadv_hard_iface *recv_if)
1813 struct batadv_priv *bat_priv = netdev_priv(recv_if->soft_iface);
1814 struct batadv_unicast_packet *unicast_packet;
1815 struct batadv_coded_packet *coded_packet;
1816 struct batadv_nc_packet *nc_packet;
1817 struct ethhdr *ethhdr;
1818 int hdr_size = sizeof(*coded_packet);
1820 /* Check if network coding is enabled */
1821 if (!atomic_read(&bat_priv->network_coding))
1824 /* Make sure we can access (and remove) header */
1825 if (unlikely(!pskb_may_pull(skb, hdr_size)))
1828 coded_packet = (struct batadv_coded_packet *)skb->data;
1829 ethhdr = eth_hdr(skb);
1831 /* Verify frame is destined for us */
1832 if (!batadv_is_my_mac(bat_priv, ethhdr->h_dest) &&
1833 !batadv_is_my_mac(bat_priv, coded_packet->second_dest))
1836 /* Update stat counter */
1837 if (batadv_is_my_mac(bat_priv, coded_packet->second_dest))
1838 batadv_inc_counter(bat_priv, BATADV_CNT_NC_SNIFFED);
1840 nc_packet = batadv_nc_find_decoding_packet(bat_priv, ethhdr,
1843 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1847 /* Make skb's linear, because decoding accesses the entire buffer */
1848 if (skb_linearize(skb) < 0)
1849 goto free_nc_packet;
1851 if (skb_linearize(nc_packet->skb) < 0)
1852 goto free_nc_packet;
1854 /* Decode the packet */
1855 unicast_packet = batadv_nc_skb_decode_packet(bat_priv, skb, nc_packet);
1856 if (!unicast_packet) {
1857 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1858 goto free_nc_packet;
1861 /* Mark packet as decoded to do correct recoding when forwarding */
1862 BATADV_SKB_CB(skb)->decoded = true;
1863 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE);
1864 batadv_add_counter(bat_priv, BATADV_CNT_NC_DECODE_BYTES,
1865 skb->len + ETH_HLEN);
1866 return batadv_recv_unicast_packet(skb, recv_if);
1869 batadv_nc_packet_free(nc_packet, true);
1877 * batadv_nc_mesh_free() - clean up network coding memory
1878 * @bat_priv: the bat priv with all the soft interface information
1880 void batadv_nc_mesh_free(struct batadv_priv *bat_priv)
1882 batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);
1883 batadv_tvlv_handler_unregister(bat_priv, BATADV_TVLV_NC, 1);
1884 cancel_delayed_work_sync(&bat_priv->nc.work);
1886 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL);
1887 batadv_hash_destroy(bat_priv->nc.coding_hash);
1888 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL);
1889 batadv_hash_destroy(bat_priv->nc.decoding_hash);
1892 #ifdef CONFIG_BATMAN_ADV_DEBUGFS
1894 * batadv_nc_nodes_seq_print_text() - print the nc node information
1895 * @seq: seq file to print on
1900 int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
1902 struct net_device *net_dev = (struct net_device *)seq->private;
1903 struct batadv_priv *bat_priv = netdev_priv(net_dev);
1904 struct batadv_hashtable *hash = bat_priv->orig_hash;
1905 struct batadv_hard_iface *primary_if;
1906 struct hlist_head *head;
1907 struct batadv_orig_node *orig_node;
1908 struct batadv_nc_node *nc_node;
1911 primary_if = batadv_seq_print_text_primary_if_get(seq);
1915 /* Traverse list of originators */
1916 for (i = 0; i < hash->size; i++) {
1917 head = &hash->table[i];
1919 /* For each orig_node in this bin */
1921 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
1922 /* no need to print the orig node if it does not have
1923 * network coding neighbors
1925 if (list_empty(&orig_node->in_coding_list) &&
1926 list_empty(&orig_node->out_coding_list))
1929 seq_printf(seq, "Node: %pM\n", orig_node->orig);
1931 seq_puts(seq, " Ingoing: ");
1932 /* For each in_nc_node to this orig_node */
1933 list_for_each_entry_rcu(nc_node,
1934 &orig_node->in_coding_list,
1936 seq_printf(seq, "%pM ",
1938 seq_puts(seq, "\n Outgoing: ");
1939 /* For out_nc_node to this orig_node */
1940 list_for_each_entry_rcu(nc_node,
1941 &orig_node->out_coding_list,
1943 seq_printf(seq, "%pM ",
1945 seq_puts(seq, "\n\n");
1952 batadv_hardif_put(primary_if);
1957 * batadv_nc_init_debugfs() - create nc folder and related files in debugfs
1958 * @bat_priv: the bat priv with all the soft interface information
1960 * Return: 0 on success or negative error number in case of failure
1962 int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
1964 struct dentry *nc_dir, *file;
1966 nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
1970 file = debugfs_create_u8("min_tq", 0644, nc_dir, &bat_priv->nc.min_tq);
1974 file = debugfs_create_u32("max_fwd_delay", 0644, nc_dir,
1975 &bat_priv->nc.max_fwd_delay);
1979 file = debugfs_create_u32("max_buffer_time", 0644, nc_dir,
1980 &bat_priv->nc.max_buffer_time);