aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorDavid S. Miller <davem@davemloft.net>2013-03-14 11:47:15 -0400
committerDavid S. Miller <davem@davemloft.net>2013-03-14 11:47:15 -0400
commit1e32b0c65c9e3f1a09cb5d1bcc0c5becf849d85f (patch)
tree3d7d1ab9a4ddfc442f2e56e887671ba8e24a0a7e /net
parent7cc163806b0dc31ea2067d48a2732b452a709f48 (diff)
parent2df5278b0267c799f3e877e8eeddbb6e93cda0bb (diff)
Merge tag 'batman-adv-for-davem' of git://git.open-mesh.org/linux-merge
Included changes: - introduction of the new Network Coding component. This new mechanism aims to increase throughput by fusing multiple packets in one transmission. - minor cleanups Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net')
-rw-r--r--net/batman-adv/Kconfig14
-rw-r--r--net/batman-adv/Makefile1
-rw-r--r--net/batman-adv/bat_iv_ogm.c5
-rw-r--r--net/batman-adv/debugfs.c18
-rw-r--r--net/batman-adv/distributed-arp-table.c22
-rw-r--r--net/batman-adv/main.c6
-rw-r--r--net/batman-adv/main.h12
-rw-r--r--net/batman-adv/network-coding.c1821
-rw-r--r--net/batman-adv/network-coding.h123
-rw-r--r--net/batman-adv/originator.c6
-rw-r--r--net/batman-adv/packet.h33
-rw-r--r--net/batman-adv/routing.c49
-rw-r--r--net/batman-adv/send.c5
-rw-r--r--net/batman-adv/soft-interface.c14
-rw-r--r--net/batman-adv/sysfs.c16
-rw-r--r--net/batman-adv/translation-table.c29
-rw-r--r--net/batman-adv/types.h136
-rw-r--r--net/batman-adv/unicast.c6
18 files changed, 2251 insertions, 65 deletions
diff --git a/net/batman-adv/Kconfig b/net/batman-adv/Kconfig
index 8d8afb134b3a..fa780b76630e 100644
--- a/net/batman-adv/Kconfig
+++ b/net/batman-adv/Kconfig
@@ -36,6 +36,20 @@ config BATMAN_ADV_DAT
36 mesh networks. If you think that your network does not need 36 mesh networks. If you think that your network does not need
37 this option you can safely remove it and save some space. 37 this option you can safely remove it and save some space.
38 38
39config BATMAN_ADV_NC
40 bool "Network Coding"
41 depends on BATMAN_ADV
42 default n
43 help
44 This option enables network coding, a mechanism that aims to
45 increase the overall network throughput by fusing multiple
46 packets in one transmission.
47 Note that interfaces controlled by batman-adv must be manually
48 configured to have promiscuous mode enabled in order to make
49 network coding work.
50 If you think that your network does not need this feature you
51 can safely disable it and save some space.
52
39config BATMAN_ADV_DEBUG 53config BATMAN_ADV_DEBUG
40 bool "B.A.T.M.A.N. debugging" 54 bool "B.A.T.M.A.N. debugging"
41 depends on BATMAN_ADV 55 depends on BATMAN_ADV
diff --git a/net/batman-adv/Makefile b/net/batman-adv/Makefile
index e45e3b4e32e3..4b8f192a9e43 100644
--- a/net/batman-adv/Makefile
+++ b/net/batman-adv/Makefile
@@ -30,6 +30,7 @@ batman-adv-y += hard-interface.o
30batman-adv-y += hash.o 30batman-adv-y += hash.o
31batman-adv-y += icmp_socket.o 31batman-adv-y += icmp_socket.o
32batman-adv-y += main.o 32batman-adv-y += main.o
33batman-adv-$(CONFIG_BATMAN_ADV_NC) += network-coding.o
33batman-adv-y += originator.o 34batman-adv-y += originator.o
34batman-adv-y += ring_buffer.o 35batman-adv-y += ring_buffer.o
35batman-adv-y += routing.o 36batman-adv-y += routing.o
diff --git a/net/batman-adv/bat_iv_ogm.c b/net/batman-adv/bat_iv_ogm.c
index a5bb0a769eb9..071f288b77a8 100644
--- a/net/batman-adv/bat_iv_ogm.c
+++ b/net/batman-adv/bat_iv_ogm.c
@@ -27,6 +27,7 @@
27#include "hard-interface.h" 27#include "hard-interface.h"
28#include "send.h" 28#include "send.h"
29#include "bat_algo.h" 29#include "bat_algo.h"
30#include "network-coding.h"
30 31
31static struct batadv_neigh_node * 32static struct batadv_neigh_node *
32batadv_iv_ogm_neigh_new(struct batadv_hard_iface *hard_iface, 33batadv_iv_ogm_neigh_new(struct batadv_hard_iface *hard_iface,
@@ -1185,6 +1186,10 @@ static void batadv_iv_ogm_process(const struct ethhdr *ethhdr,
1185 if (!orig_neigh_node) 1186 if (!orig_neigh_node)
1186 goto out; 1187 goto out;
1187 1188
1189 /* Update nc_nodes of the originator */
1190 batadv_nc_update_nc_node(bat_priv, orig_node, orig_neigh_node,
1191 batadv_ogm_packet, is_single_hop_neigh);
1192
1188 orig_neigh_router = batadv_orig_node_get_router(orig_neigh_node); 1193 orig_neigh_router = batadv_orig_node_get_router(orig_neigh_node);
1189 1194
1190 /* drop packet if sender is not a direct neighbor and if we 1195 /* drop packet if sender is not a direct neighbor and if we
diff --git a/net/batman-adv/debugfs.c b/net/batman-adv/debugfs.c
index 6ae86516db4d..f186a55b23c3 100644
--- a/net/batman-adv/debugfs.c
+++ b/net/batman-adv/debugfs.c
@@ -32,6 +32,7 @@
32#include "icmp_socket.h" 32#include "icmp_socket.h"
33#include "bridge_loop_avoidance.h" 33#include "bridge_loop_avoidance.h"
34#include "distributed-arp-table.h" 34#include "distributed-arp-table.h"
35#include "network-coding.h"
35 36
36static struct dentry *batadv_debugfs; 37static struct dentry *batadv_debugfs;
37 38
@@ -310,6 +311,14 @@ struct batadv_debuginfo {
310 const struct file_operations fops; 311 const struct file_operations fops;
311}; 312};
312 313
314#ifdef CONFIG_BATMAN_ADV_NC
315static int batadv_nc_nodes_open(struct inode *inode, struct file *file)
316{
317 struct net_device *net_dev = (struct net_device *)inode->i_private;
318 return single_open(file, batadv_nc_nodes_seq_print_text, net_dev);
319}
320#endif
321
313#define BATADV_DEBUGINFO(_name, _mode, _open) \ 322#define BATADV_DEBUGINFO(_name, _mode, _open) \
314struct batadv_debuginfo batadv_debuginfo_##_name = { \ 323struct batadv_debuginfo batadv_debuginfo_##_name = { \
315 .attr = { .name = __stringify(_name), \ 324 .attr = { .name = __stringify(_name), \
@@ -348,6 +357,9 @@ static BATADV_DEBUGINFO(dat_cache, S_IRUGO, batadv_dat_cache_open);
348static BATADV_DEBUGINFO(transtable_local, S_IRUGO, 357static BATADV_DEBUGINFO(transtable_local, S_IRUGO,
349 batadv_transtable_local_open); 358 batadv_transtable_local_open);
350static BATADV_DEBUGINFO(vis_data, S_IRUGO, batadv_vis_data_open); 359static BATADV_DEBUGINFO(vis_data, S_IRUGO, batadv_vis_data_open);
360#ifdef CONFIG_BATMAN_ADV_NC
361static BATADV_DEBUGINFO(nc_nodes, S_IRUGO, batadv_nc_nodes_open);
362#endif
351 363
352static struct batadv_debuginfo *batadv_mesh_debuginfos[] = { 364static struct batadv_debuginfo *batadv_mesh_debuginfos[] = {
353 &batadv_debuginfo_originators, 365 &batadv_debuginfo_originators,
@@ -362,6 +374,9 @@ static struct batadv_debuginfo *batadv_mesh_debuginfos[] = {
362#endif 374#endif
363 &batadv_debuginfo_transtable_local, 375 &batadv_debuginfo_transtable_local,
364 &batadv_debuginfo_vis_data, 376 &batadv_debuginfo_vis_data,
377#ifdef CONFIG_BATMAN_ADV_NC
378 &batadv_debuginfo_nc_nodes,
379#endif
365 NULL, 380 NULL,
366}; 381};
367 382
@@ -431,6 +446,9 @@ int batadv_debugfs_add_meshif(struct net_device *dev)
431 } 446 }
432 } 447 }
433 448
449 if (batadv_nc_init_debugfs(bat_priv) < 0)
450 goto rem_attr;
451
434 return 0; 452 return 0;
435rem_attr: 453rem_attr:
436 debugfs_remove_recursive(bat_priv->debug_dir); 454 debugfs_remove_recursive(bat_priv->debug_dir);
diff --git a/net/batman-adv/distributed-arp-table.c b/net/batman-adv/distributed-arp-table.c
index d54188a112ea..8e15d966d9b0 100644
--- a/net/batman-adv/distributed-arp-table.c
+++ b/net/batman-adv/distributed-arp-table.c
@@ -816,7 +816,6 @@ bool batadv_dat_snoop_outgoing_arp_request(struct batadv_priv *bat_priv,
816 bool ret = false; 816 bool ret = false;
817 struct batadv_dat_entry *dat_entry = NULL; 817 struct batadv_dat_entry *dat_entry = NULL;
818 struct sk_buff *skb_new; 818 struct sk_buff *skb_new;
819 struct batadv_hard_iface *primary_if = NULL;
820 819
821 if (!atomic_read(&bat_priv->distributed_arp_table)) 820 if (!atomic_read(&bat_priv->distributed_arp_table))
822 goto out; 821 goto out;
@@ -838,22 +837,18 @@ bool batadv_dat_snoop_outgoing_arp_request(struct batadv_priv *bat_priv,
838 837
839 dat_entry = batadv_dat_entry_hash_find(bat_priv, ip_dst); 838 dat_entry = batadv_dat_entry_hash_find(bat_priv, ip_dst);
840 if (dat_entry) { 839 if (dat_entry) {
841 primary_if = batadv_primary_if_get_selected(bat_priv);
842 if (!primary_if)
843 goto out;
844
845 skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src, 840 skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src,
846 primary_if->soft_iface, ip_dst, hw_src, 841 bat_priv->soft_iface, ip_dst, hw_src,
847 dat_entry->mac_addr, hw_src); 842 dat_entry->mac_addr, hw_src);
848 if (!skb_new) 843 if (!skb_new)
849 goto out; 844 goto out;
850 845
851 skb_reset_mac_header(skb_new); 846 skb_reset_mac_header(skb_new);
852 skb_new->protocol = eth_type_trans(skb_new, 847 skb_new->protocol = eth_type_trans(skb_new,
853 primary_if->soft_iface); 848 bat_priv->soft_iface);
854 bat_priv->stats.rx_packets++; 849 bat_priv->stats.rx_packets++;
855 bat_priv->stats.rx_bytes += skb->len + ETH_HLEN; 850 bat_priv->stats.rx_bytes += skb->len + ETH_HLEN;
856 primary_if->soft_iface->last_rx = jiffies; 851 bat_priv->soft_iface->last_rx = jiffies;
857 852
858 netif_rx(skb_new); 853 netif_rx(skb_new);
859 batadv_dbg(BATADV_DBG_DAT, bat_priv, "ARP request replied locally\n"); 854 batadv_dbg(BATADV_DBG_DAT, bat_priv, "ARP request replied locally\n");
@@ -866,8 +861,6 @@ bool batadv_dat_snoop_outgoing_arp_request(struct batadv_priv *bat_priv,
866out: 861out:
867 if (dat_entry) 862 if (dat_entry)
868 batadv_dat_entry_free_ref(dat_entry); 863 batadv_dat_entry_free_ref(dat_entry);
869 if (primary_if)
870 batadv_hardif_free_ref(primary_if);
871 return ret; 864 return ret;
872} 865}
873 866
@@ -887,7 +880,6 @@ bool batadv_dat_snoop_incoming_arp_request(struct batadv_priv *bat_priv,
887 __be32 ip_src, ip_dst; 880 __be32 ip_src, ip_dst;
888 uint8_t *hw_src; 881 uint8_t *hw_src;
889 struct sk_buff *skb_new; 882 struct sk_buff *skb_new;
890 struct batadv_hard_iface *primary_if = NULL;
891 struct batadv_dat_entry *dat_entry = NULL; 883 struct batadv_dat_entry *dat_entry = NULL;
892 bool ret = false; 884 bool ret = false;
893 int err; 885 int err;
@@ -912,12 +904,8 @@ bool batadv_dat_snoop_incoming_arp_request(struct batadv_priv *bat_priv,
912 if (!dat_entry) 904 if (!dat_entry)
913 goto out; 905 goto out;
914 906
915 primary_if = batadv_primary_if_get_selected(bat_priv);
916 if (!primary_if)
917 goto out;
918
919 skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src, 907 skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src,
920 primary_if->soft_iface, ip_dst, hw_src, 908 bat_priv->soft_iface, ip_dst, hw_src,
921 dat_entry->mac_addr, hw_src); 909 dat_entry->mac_addr, hw_src);
922 910
923 if (!skb_new) 911 if (!skb_new)
@@ -941,8 +929,6 @@ bool batadv_dat_snoop_incoming_arp_request(struct batadv_priv *bat_priv,
941out: 929out:
942 if (dat_entry) 930 if (dat_entry)
943 batadv_dat_entry_free_ref(dat_entry); 931 batadv_dat_entry_free_ref(dat_entry);
944 if (primary_if)
945 batadv_hardif_free_ref(primary_if);
946 if (ret) 932 if (ret)
947 kfree_skb(skb); 933 kfree_skb(skb);
948 return ret; 934 return ret;
diff --git a/net/batman-adv/main.c b/net/batman-adv/main.c
index 0488d70c8c35..0495a7dc7505 100644
--- a/net/batman-adv/main.c
+++ b/net/batman-adv/main.c
@@ -35,6 +35,7 @@
35#include "vis.h" 35#include "vis.h"
36#include "hash.h" 36#include "hash.h"
37#include "bat_algo.h" 37#include "bat_algo.h"
38#include "network-coding.h"
38 39
39 40
40/* List manipulations on hardif_list have to be rtnl_lock()'ed, 41/* List manipulations on hardif_list have to be rtnl_lock()'ed,
@@ -135,6 +136,10 @@ int batadv_mesh_init(struct net_device *soft_iface)
135 if (ret < 0) 136 if (ret < 0)
136 goto err; 137 goto err;
137 138
139 ret = batadv_nc_init(bat_priv);
140 if (ret < 0)
141 goto err;
142
138 atomic_set(&bat_priv->gw.reselect, 0); 143 atomic_set(&bat_priv->gw.reselect, 0);
139 atomic_set(&bat_priv->mesh_state, BATADV_MESH_ACTIVE); 144 atomic_set(&bat_priv->mesh_state, BATADV_MESH_ACTIVE);
140 145
@@ -157,6 +162,7 @@ void batadv_mesh_free(struct net_device *soft_iface)
157 162
158 batadv_gw_node_purge(bat_priv); 163 batadv_gw_node_purge(bat_priv);
159 batadv_originator_free(bat_priv); 164 batadv_originator_free(bat_priv);
165 batadv_nc_free(bat_priv);
160 166
161 batadv_tt_free(bat_priv); 167 batadv_tt_free(bat_priv);
162 168
diff --git a/net/batman-adv/main.h b/net/batman-adv/main.h
index ced08b936a96..0afd4ee7708b 100644
--- a/net/batman-adv/main.h
+++ b/net/batman-adv/main.h
@@ -105,6 +105,8 @@
105#define BATADV_RESET_PROTECTION_MS 30000 105#define BATADV_RESET_PROTECTION_MS 30000
106#define BATADV_EXPECTED_SEQNO_RANGE 65536 106#define BATADV_EXPECTED_SEQNO_RANGE 65536
107 107
108#define BATADV_NC_NODE_TIMEOUT 10000 /* Milliseconds */
109
108enum batadv_mesh_state { 110enum batadv_mesh_state {
109 BATADV_MESH_INACTIVE, 111 BATADV_MESH_INACTIVE,
110 BATADV_MESH_ACTIVE, 112 BATADV_MESH_ACTIVE,
@@ -185,6 +187,7 @@ __be32 batadv_skb_crc32(struct sk_buff *skb, u8 *payload_ptr);
185 * @BATADV_DBG_TT: translation table messages 187 * @BATADV_DBG_TT: translation table messages
186 * @BATADV_DBG_BLA: bridge loop avoidance messages 188 * @BATADV_DBG_BLA: bridge loop avoidance messages
187 * @BATADV_DBG_DAT: ARP snooping and DAT related messages 189 * @BATADV_DBG_DAT: ARP snooping and DAT related messages
190 * @BATADV_DBG_NC: network coding related messages
188 * @BATADV_DBG_ALL: the union of all the above log levels 191 * @BATADV_DBG_ALL: the union of all the above log levels
189 */ 192 */
190enum batadv_dbg_level { 193enum batadv_dbg_level {
@@ -193,7 +196,8 @@ enum batadv_dbg_level {
193 BATADV_DBG_TT = BIT(2), 196 BATADV_DBG_TT = BIT(2),
194 BATADV_DBG_BLA = BIT(3), 197 BATADV_DBG_BLA = BIT(3),
195 BATADV_DBG_DAT = BIT(4), 198 BATADV_DBG_DAT = BIT(4),
196 BATADV_DBG_ALL = 31, 199 BATADV_DBG_NC = BIT(5),
200 BATADV_DBG_ALL = 63,
197}; 201};
198 202
199#ifdef CONFIG_BATMAN_ADV_DEBUG 203#ifdef CONFIG_BATMAN_ADV_DEBUG
@@ -298,4 +302,10 @@ static inline uint64_t batadv_sum_counter(struct batadv_priv *bat_priv,
298 return sum; 302 return sum;
299} 303}
300 304
305/* Define a macro to reach the control buffer of the skb. The members of the
306 * control buffer are defined in struct batadv_skb_cb in types.h.
307 * The macro is inspired by the similar macro TCP_SKB_CB() in tcp.h.
308 */
309#define BATADV_SKB_CB(__skb) ((struct batadv_skb_cb *)&((__skb)->cb[0]))
310
301#endif /* _NET_BATMAN_ADV_MAIN_H_ */ 311#endif /* _NET_BATMAN_ADV_MAIN_H_ */
diff --git a/net/batman-adv/network-coding.c b/net/batman-adv/network-coding.c
new file mode 100644
index 000000000000..57280797bf4e
--- /dev/null
+++ b/net/batman-adv/network-coding.c
@@ -0,0 +1,1821 @@
1/* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors:
2 *
3 * Martin Hundebøll, Jeppe Ledet-Pedersen
4 *
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.
8 *
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.
13 *
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
17 * 02110-1301, USA
18 */
19
20#include <linux/debugfs.h>
21
22#include "main.h"
23#include "hash.h"
24#include "network-coding.h"
25#include "send.h"
26#include "originator.h"
27#include "hard-interface.h"
28#include "routing.h"
29
30static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
31static struct lock_class_key batadv_nc_decoding_hash_lock_class_key;
32
33static void batadv_nc_worker(struct work_struct *work);
34static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
35 struct batadv_hard_iface *recv_if);
36
37/**
38 * batadv_nc_start_timer - initialise the nc periodic worker
39 * @bat_priv: the bat priv with all the soft interface information
40 */
41static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
42{
43 queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,
44 msecs_to_jiffies(10));
45}
46
47/**
48 * batadv_nc_init - initialise coding hash table and start house keeping
49 * @bat_priv: the bat priv with all the soft interface information
50 */
51int batadv_nc_init(struct batadv_priv *bat_priv)
52{
53 bat_priv->nc.timestamp_fwd_flush = jiffies;
54 bat_priv->nc.timestamp_sniffed_purge = jiffies;
55
56 if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash)
57 return 0;
58
59 bat_priv->nc.coding_hash = batadv_hash_new(128);
60 if (!bat_priv->nc.coding_hash)
61 goto err;
62
63 batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
64 &batadv_nc_coding_hash_lock_class_key);
65
66 bat_priv->nc.decoding_hash = batadv_hash_new(128);
67 if (!bat_priv->nc.decoding_hash)
68 goto err;
69
70 batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
71 &batadv_nc_decoding_hash_lock_class_key);
72
73 /* Register our packet type */
74 if (batadv_recv_handler_register(BATADV_CODED,
75 batadv_nc_recv_coded_packet) < 0)
76 goto err;
77
78 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
79 batadv_nc_start_timer(bat_priv);
80
81 return 0;
82
83err:
84 return -ENOMEM;
85}
86
87/**
88 * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables
89 * @bat_priv: the bat priv with all the soft interface information
90 */
91void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
92{
93 atomic_set(&bat_priv->network_coding, 1);
94 bat_priv->nc.min_tq = 200;
95 bat_priv->nc.max_fwd_delay = 10;
96 bat_priv->nc.max_buffer_time = 200;
97}
98
99/**
100 * batadv_nc_init_orig - initialise the nc fields of an orig_node
101 * @orig_node: the orig_node which is going to be initialised
102 */
103void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
104{
105 INIT_LIST_HEAD(&orig_node->in_coding_list);
106 INIT_LIST_HEAD(&orig_node->out_coding_list);
107 spin_lock_init(&orig_node->in_coding_list_lock);
108 spin_lock_init(&orig_node->out_coding_list_lock);
109}
110
111/**
112 * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove
113 * its refcount on the orig_node
114 * @rcu: rcu pointer of the nc node
115 */
116static void batadv_nc_node_free_rcu(struct rcu_head *rcu)
117{
118 struct batadv_nc_node *nc_node;
119
120 nc_node = container_of(rcu, struct batadv_nc_node, rcu);
121 batadv_orig_node_free_ref(nc_node->orig_node);
122 kfree(nc_node);
123}
124
125/**
126 * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly
127 * frees it
128 * @nc_node: the nc node to free
129 */
130static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node)
131{
132 if (atomic_dec_and_test(&nc_node->refcount))
133 call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu);
134}
135
136/**
137 * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly
138 * frees it
139 * @nc_path: the nc node to free
140 */
141static void batadv_nc_path_free_ref(struct batadv_nc_path *nc_path)
142{
143 if (atomic_dec_and_test(&nc_path->refcount))
144 kfree_rcu(nc_path, rcu);
145}
146
147/**
148 * batadv_nc_packet_free - frees nc packet
149 * @nc_packet: the nc packet to free
150 */
151static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet)
152{
153 if (nc_packet->skb)
154 kfree_skb(nc_packet->skb);
155
156 batadv_nc_path_free_ref(nc_packet->nc_path);
157 kfree(nc_packet);
158}
159
160/**
161 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
162 * @bat_priv: the bat priv with all the soft interface information
163 * @nc_node: the nc node to check
164 *
165 * Returns true if the entry has to be purged now, false otherwise
166 */
167static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
168 struct batadv_nc_node *nc_node)
169{
170 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
171 return true;
172
173 return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
174}
175
176/**
177 * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out
178 * @bat_priv: the bat priv with all the soft interface information
179 * @nc_path: the nc path to check
180 *
181 * Returns true if the entry has to be purged now, false otherwise
182 */
183static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,
184 struct batadv_nc_path *nc_path)
185{
186 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
187 return true;
188
189 /* purge the path when no packets has been added for 10 times the
190 * max_fwd_delay time
191 */
192 return batadv_has_timed_out(nc_path->last_valid,
193 bat_priv->nc.max_fwd_delay * 10);
194}
195
196/**
197 * batadv_nc_to_purge_nc_path_decoding - checks whether an nc path has timed out
198 * @bat_priv: the bat priv with all the soft interface information
199 * @nc_path: the nc path to check
200 *
201 * Returns true if the entry has to be purged now, false otherwise
202 */
203static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv *bat_priv,
204 struct batadv_nc_path *nc_path)
205{
206 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
207 return true;
208
209 /* purge the path when no packets has been added for 10 times the
210 * max_buffer time
211 */
212 return batadv_has_timed_out(nc_path->last_valid,
213 bat_priv->nc.max_buffer_time*10);
214}
215
216/**
217 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
218 * entries
219 * @bat_priv: the bat priv with all the soft interface information
220 * @list: list of nc nodes
221 * @lock: nc node list lock
222 * @to_purge: function in charge to decide whether an entry has to be purged or
223 * not. This function takes the nc node as argument and has to return
224 * a boolean value: true if the entry has to be deleted, false
225 * otherwise
226 */
227static void
228batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
229 struct list_head *list,
230 spinlock_t *lock,
231 bool (*to_purge)(struct batadv_priv *,
232 struct batadv_nc_node *))
233{
234 struct batadv_nc_node *nc_node, *nc_node_tmp;
235
236 /* For each nc_node in list */
237 spin_lock_bh(lock);
238 list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
239 /* if an helper function has been passed as parameter,
240 * ask it if the entry has to be purged or not
241 */
242 if (to_purge && !to_purge(bat_priv, nc_node))
243 continue;
244
245 batadv_dbg(BATADV_DBG_NC, bat_priv,
246 "Removing nc_node %pM -> %pM\n",
247 nc_node->addr, nc_node->orig_node->orig);
248 list_del_rcu(&nc_node->list);
249 batadv_nc_node_free_ref(nc_node);
250 }
251 spin_unlock_bh(lock);
252}
253
254/**
255 * batadv_nc_purge_orig - purges all nc node data attached of the given
256 * originator
257 * @bat_priv: the bat priv with all the soft interface information
258 * @orig_node: orig_node with the nc node entries to be purged
259 * @to_purge: function in charge to decide whether an entry has to be purged or
260 * not. This function takes the nc node as argument and has to return
261 * a boolean value: true is the entry has to be deleted, false
262 * otherwise
263 */
264void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
265 struct batadv_orig_node *orig_node,
266 bool (*to_purge)(struct batadv_priv *,
267 struct batadv_nc_node *))
268{
269 /* Check ingoing nc_node's of this orig_node */
270 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
271 &orig_node->in_coding_list_lock,
272 to_purge);
273
274 /* Check outgoing nc_node's of this orig_node */
275 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
276 &orig_node->out_coding_list_lock,
277 to_purge);
278}
279
280/**
281 * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
282 * have timed out nc nodes
283 * @bat_priv: the bat priv with all the soft interface information
284 */
285static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
286{
287 struct batadv_hashtable *hash = bat_priv->orig_hash;
288 struct hlist_head *head;
289 struct batadv_orig_node *orig_node;
290 uint32_t i;
291
292 if (!hash)
293 return;
294
295 /* For each orig_node */
296 for (i = 0; i < hash->size; i++) {
297 head = &hash->table[i];
298
299 rcu_read_lock();
300 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
301 batadv_nc_purge_orig(bat_priv, orig_node,
302 batadv_nc_to_purge_nc_node);
303 rcu_read_unlock();
304 }
305}
306
307/**
308 * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove
309 * unused ones
310 * @bat_priv: the bat priv with all the soft interface information
311 * @hash: hash table containing the nc paths to check
312 * @to_purge: function in charge to decide whether an entry has to be purged or
313 * not. This function takes the nc node as argument and has to return
314 * a boolean value: true is the entry has to be deleted, false
315 * otherwise
316 */
317static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,
318 struct batadv_hashtable *hash,
319 bool (*to_purge)(struct batadv_priv *,
320 struct batadv_nc_path *))
321{
322 struct hlist_head *head;
323 struct hlist_node *node_tmp;
324 struct batadv_nc_path *nc_path;
325 spinlock_t *lock; /* Protects lists in hash */
326 uint32_t i;
327
328 for (i = 0; i < hash->size; i++) {
329 head = &hash->table[i];
330 lock = &hash->list_locks[i];
331
332 /* For each nc_path in this bin */
333 spin_lock_bh(lock);
334 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {
335 /* if an helper function has been passed as parameter,
336 * ask it if the entry has to be purged or not
337 */
338 if (to_purge && !to_purge(bat_priv, nc_path))
339 continue;
340
341 /* purging an non-empty nc_path should never happen, but
342 * is observed under high CPU load. Delay the purging
343 * until next iteration to allow the packet_list to be
344 * emptied first.
345 */
346 if (!unlikely(list_empty(&nc_path->packet_list))) {
347 net_ratelimited_function(printk,
348 KERN_WARNING
349 "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
350 nc_path->prev_hop,
351 nc_path->next_hop);
352 continue;
353 }
354
355 /* nc_path is unused, so remove it */
356 batadv_dbg(BATADV_DBG_NC, bat_priv,
357 "Remove nc_path %pM -> %pM\n",
358 nc_path->prev_hop, nc_path->next_hop);
359 hlist_del_rcu(&nc_path->hash_entry);
360 batadv_nc_path_free_ref(nc_path);
361 }
362 spin_unlock_bh(lock);
363 }
364}
365
366/**
367 * batadv_nc_hash_key_gen - computes the nc_path hash key
368 * @key: buffer to hold the final hash key
369 * @src: source ethernet mac address going into the hash key
370 * @dst: destination ethernet mac address going into the hash key
371 */
372static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,
373 const char *dst)
374{
375 memcpy(key->prev_hop, src, sizeof(key->prev_hop));
376 memcpy(key->next_hop, dst, sizeof(key->next_hop));
377}
378
379/**
380 * batadv_nc_hash_choose - compute the hash value for an nc path
381 * @data: data to hash
382 * @size: size of the hash table
383 *
384 * Returns the selected index in the hash table for the given data.
385 */
386static uint32_t batadv_nc_hash_choose(const void *data, uint32_t size)
387{
388 const struct batadv_nc_path *nc_path = data;
389 uint32_t hash = 0;
390
391 hash = batadv_hash_bytes(hash, &nc_path->prev_hop,
392 sizeof(nc_path->prev_hop));
393 hash = batadv_hash_bytes(hash, &nc_path->next_hop,
394 sizeof(nc_path->next_hop));
395
396 hash += (hash << 3);
397 hash ^= (hash >> 11);
398 hash += (hash << 15);
399
400 return hash % size;
401}
402
403/**
404 * batadv_nc_hash_compare - comparing function used in the network coding hash
405 * tables
406 * @node: node in the local table
407 * @data2: second object to compare the node to
408 *
409 * Returns 1 if the two entry are the same, 0 otherwise
410 */
411static int batadv_nc_hash_compare(const struct hlist_node *node,
412 const void *data2)
413{
414 const struct batadv_nc_path *nc_path1, *nc_path2;
415
416 nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);
417 nc_path2 = data2;
418
419 /* Return 1 if the two keys are identical */
420 if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop,
421 sizeof(nc_path1->prev_hop)) != 0)
422 return 0;
423
424 if (memcmp(nc_path1->next_hop, nc_path2->next_hop,
425 sizeof(nc_path1->next_hop)) != 0)
426 return 0;
427
428 return 1;
429}
430
431/**
432 * batadv_nc_hash_find - search for an existing nc path and return it
433 * @hash: hash table containing the nc path
434 * @data: search key
435 *
436 * Returns the nc_path if found, NULL otherwise.
437 */
438static struct batadv_nc_path *
439batadv_nc_hash_find(struct batadv_hashtable *hash,
440 void *data)
441{
442 struct hlist_head *head;
443 struct batadv_nc_path *nc_path, *nc_path_tmp = NULL;
444 int index;
445
446 if (!hash)
447 return NULL;
448
449 index = batadv_nc_hash_choose(data, hash->size);
450 head = &hash->table[index];
451
452 rcu_read_lock();
453 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
454 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data))
455 continue;
456
457 if (!atomic_inc_not_zero(&nc_path->refcount))
458 continue;
459
460 nc_path_tmp = nc_path;
461 break;
462 }
463 rcu_read_unlock();
464
465 return nc_path_tmp;
466}
467
468/**
469 * batadv_nc_send_packet - send non-coded packet and free nc_packet struct
470 * @nc_packet: the nc packet to send
471 */
472static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet)
473{
474 batadv_send_skb_packet(nc_packet->skb,
475 nc_packet->neigh_node->if_incoming,
476 nc_packet->nc_path->next_hop);
477 nc_packet->skb = NULL;
478 batadv_nc_packet_free(nc_packet);
479}
480
481/**
482 * batadv_nc_sniffed_purge - Checks timestamp of given sniffed nc_packet.
483 * @bat_priv: the bat priv with all the soft interface information
484 * @nc_path: the nc path the packet belongs to
485 * @nc_packet: the nc packet to be checked
486 *
487 * Checks whether the given sniffed (overheard) nc_packet has hit its buffering
488 * timeout. If so, the packet is no longer kept and the entry deleted from the
489 * queue. Has to be called with the appropriate locks.
490 *
491 * Returns false as soon as the entry in the fifo queue has not been timed out
492 * yet and true otherwise.
493 */
494static bool batadv_nc_sniffed_purge(struct batadv_priv *bat_priv,
495 struct batadv_nc_path *nc_path,
496 struct batadv_nc_packet *nc_packet)
497{
498 unsigned long timeout = bat_priv->nc.max_buffer_time;
499 bool res = false;
500
501 /* Packets are added to tail, so the remaining packets did not time
502 * out and we can stop processing the current queue
503 */
504 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
505 !batadv_has_timed_out(nc_packet->timestamp, timeout))
506 goto out;
507
508 /* purge nc packet */
509 list_del(&nc_packet->list);
510 batadv_nc_packet_free(nc_packet);
511
512 res = true;
513
514out:
515 return res;
516}
517
518/**
519 * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet.
520 * @bat_priv: the bat priv with all the soft interface information
521 * @nc_path: the nc path the packet belongs to
522 * @nc_packet: the nc packet to be checked
523 *
524 * Checks whether the given nc packet has hit its forward timeout. If so, the
525 * packet is no longer delayed, immediately sent and the entry deleted from the
526 * queue. Has to be called with the appropriate locks.
527 *
528 * Returns false as soon as the entry in the fifo queue has not been timed out
529 * yet and true otherwise.
530 */
531static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv,
532 struct batadv_nc_path *nc_path,
533 struct batadv_nc_packet *nc_packet)
534{
535 unsigned long timeout = bat_priv->nc.max_fwd_delay;
536
537 /* Packets are added to tail, so the remaining packets did not time
538 * out and we can stop processing the current queue
539 */
540 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
541 !batadv_has_timed_out(nc_packet->timestamp, timeout))
542 return false;
543
544 /* Send packet */
545 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
546 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
547 nc_packet->skb->len + ETH_HLEN);
548 list_del(&nc_packet->list);
549 batadv_nc_send_packet(nc_packet);
550
551 return true;
552}
553
554/**
555 * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out
556 * nc packets
557 * @bat_priv: the bat priv with all the soft interface information
558 * @hash: to be processed hash table
559 * @process_fn: Function called to process given nc packet. Should return true
560 * to encourage this function to proceed with the next packet.
561 * Otherwise the rest of the current queue is skipped.
562 */
563static void
564batadv_nc_process_nc_paths(struct batadv_priv *bat_priv,
565 struct batadv_hashtable *hash,
566 bool (*process_fn)(struct batadv_priv *,
567 struct batadv_nc_path *,
568 struct batadv_nc_packet *))
569{
570 struct hlist_head *head;
571 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
572 struct batadv_nc_path *nc_path;
573 bool ret;
574 int i;
575
576 if (!hash)
577 return;
578
579 /* Loop hash table bins */
580 for (i = 0; i < hash->size; i++) {
581 head = &hash->table[i];
582
583 /* Loop coding paths */
584 rcu_read_lock();
585 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
586 /* Loop packets */
587 spin_lock_bh(&nc_path->packet_list_lock);
588 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
589 &nc_path->packet_list, list) {
590 ret = process_fn(bat_priv, nc_path, nc_packet);
591 if (!ret)
592 break;
593 }
594 spin_unlock_bh(&nc_path->packet_list_lock);
595 }
596 rcu_read_unlock();
597 }
598}
599
600/**
601 * batadv_nc_worker - periodic task for house keeping related to network coding
602 * @work: kernel work struct
603 */
604static void batadv_nc_worker(struct work_struct *work)
605{
606 struct delayed_work *delayed_work;
607 struct batadv_priv_nc *priv_nc;
608 struct batadv_priv *bat_priv;
609 unsigned long timeout;
610
611 delayed_work = container_of(work, struct delayed_work, work);
612 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
613 bat_priv = container_of(priv_nc, struct batadv_priv, nc);
614
615 batadv_nc_purge_orig_hash(bat_priv);
616 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash,
617 batadv_nc_to_purge_nc_path_coding);
618 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash,
619 batadv_nc_to_purge_nc_path_decoding);
620
621 timeout = bat_priv->nc.max_fwd_delay;
622
623 if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) {
624 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash,
625 batadv_nc_fwd_flush);
626 bat_priv->nc.timestamp_fwd_flush = jiffies;
627 }
628
629 if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge,
630 bat_priv->nc.max_buffer_time)) {
631 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash,
632 batadv_nc_sniffed_purge);
633 bat_priv->nc.timestamp_sniffed_purge = jiffies;
634 }
635
636 /* Schedule a new check */
637 batadv_nc_start_timer(bat_priv);
638}
639
640/**
641 * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
642 * coding or not
643 * @bat_priv: the bat priv with all the soft interface information
644 * @orig_node: neighboring orig node which may be used as nc candidate
645 * @ogm_packet: incoming ogm packet also used for the checks
646 *
647 * Returns true if:
648 * 1) The OGM must have the most recent sequence number.
649 * 2) The TTL must be decremented by one and only one.
650 * 3) The OGM must be received from the first hop from orig_node.
651 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
652 */
653static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
654 struct batadv_orig_node *orig_node,
655 struct batadv_ogm_packet *ogm_packet)
656{
657 if (orig_node->last_real_seqno != ogm_packet->seqno)
658 return false;
659 if (orig_node->last_ttl != ogm_packet->header.ttl + 1)
660 return false;
661 if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
662 return false;
663 if (ogm_packet->tq < bat_priv->nc.min_tq)
664 return false;
665
666 return true;
667}
668
669/**
670 * batadv_nc_find_nc_node - search for an existing nc node and return it
671 * @orig_node: orig node originating the ogm packet
672 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
673 * (can be equal to orig_node)
674 * @in_coding: traverse incoming or outgoing network coding list
675 *
676 * Returns the nc_node if found, NULL otherwise.
677 */
678static struct batadv_nc_node
679*batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
680 struct batadv_orig_node *orig_neigh_node,
681 bool in_coding)
682{
683 struct batadv_nc_node *nc_node, *nc_node_out = NULL;
684 struct list_head *list;
685
686 if (in_coding)
687 list = &orig_neigh_node->in_coding_list;
688 else
689 list = &orig_neigh_node->out_coding_list;
690
691 /* Traverse list of nc_nodes to orig_node */
692 rcu_read_lock();
693 list_for_each_entry_rcu(nc_node, list, list) {
694 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
695 continue;
696
697 if (!atomic_inc_not_zero(&nc_node->refcount))
698 continue;
699
700 /* Found a match */
701 nc_node_out = nc_node;
702 break;
703 }
704 rcu_read_unlock();
705
706 return nc_node_out;
707}
708
709/**
710 * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
711 * not found
712 * @bat_priv: the bat priv with all the soft interface information
713 * @orig_node: orig node originating the ogm packet
714 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
715 * (can be equal to orig_node)
716 * @in_coding: traverse incoming or outgoing network coding list
717 *
718 * Returns the nc_node if found or created, NULL in case of an error.
719 */
720static struct batadv_nc_node
721*batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
722 struct batadv_orig_node *orig_node,
723 struct batadv_orig_node *orig_neigh_node,
724 bool in_coding)
725{
726 struct batadv_nc_node *nc_node;
727 spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
728 struct list_head *list;
729
730 /* Check if nc_node is already added */
731 nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
732
733 /* Node found */
734 if (nc_node)
735 return nc_node;
736
737 nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
738 if (!nc_node)
739 return NULL;
740
741 if (!atomic_inc_not_zero(&orig_neigh_node->refcount))
742 goto free;
743
744 /* Initialize nc_node */
745 INIT_LIST_HEAD(&nc_node->list);
746 memcpy(nc_node->addr, orig_node->orig, ETH_ALEN);
747 nc_node->orig_node = orig_neigh_node;
748 atomic_set(&nc_node->refcount, 2);
749
750 /* Select ingoing or outgoing coding node */
751 if (in_coding) {
752 lock = &orig_neigh_node->in_coding_list_lock;
753 list = &orig_neigh_node->in_coding_list;
754 } else {
755 lock = &orig_neigh_node->out_coding_list_lock;
756 list = &orig_neigh_node->out_coding_list;
757 }
758
759 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
760 nc_node->addr, nc_node->orig_node->orig);
761
762 /* Add nc_node to orig_node */
763 spin_lock_bh(lock);
764 list_add_tail_rcu(&nc_node->list, list);
765 spin_unlock_bh(lock);
766
767 return nc_node;
768
769free:
770 kfree(nc_node);
771 return NULL;
772}
773
774/**
775 * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs
776 * (best called on incoming OGMs)
777 * @bat_priv: the bat priv with all the soft interface information
778 * @orig_node: orig node originating the ogm packet
779 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
780 * (can be equal to orig_node)
781 * @ogm_packet: incoming ogm packet
782 * @is_single_hop_neigh: orig_node is a single hop neighbor
783 */
784void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
785 struct batadv_orig_node *orig_node,
786 struct batadv_orig_node *orig_neigh_node,
787 struct batadv_ogm_packet *ogm_packet,
788 int is_single_hop_neigh)
789{
790 struct batadv_nc_node *in_nc_node = NULL, *out_nc_node = NULL;
791
792 /* Check if network coding is enabled */
793 if (!atomic_read(&bat_priv->network_coding))
794 goto out;
795
796 /* accept ogms from 'good' neighbors and single hop neighbors */
797 if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
798 !is_single_hop_neigh)
799 goto out;
800
801 /* Add orig_node as in_nc_node on hop */
802 in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
803 orig_neigh_node, true);
804 if (!in_nc_node)
805 goto out;
806
807 in_nc_node->last_seen = jiffies;
808
809 /* Add hop as out_nc_node on orig_node */
810 out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
811 orig_node, false);
812 if (!out_nc_node)
813 goto out;
814
815 out_nc_node->last_seen = jiffies;
816
817out:
818 if (in_nc_node)
819 batadv_nc_node_free_ref(in_nc_node);
820 if (out_nc_node)
821 batadv_nc_node_free_ref(out_nc_node);
822}
823
824/**
825 * batadv_nc_get_path - get existing nc_path or allocate a new one
826 * @bat_priv: the bat priv with all the soft interface information
827 * @hash: hash table containing the nc path
828 * @src: ethernet source address - first half of the nc path search key
829 * @dst: ethernet destination address - second half of the nc path search key
830 *
831 * Returns pointer to nc_path if the path was found or created, returns NULL
832 * on error.
833 */
834static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
835 struct batadv_hashtable *hash,
836 uint8_t *src,
837 uint8_t *dst)
838{
839 int hash_added;
840 struct batadv_nc_path *nc_path, nc_path_key;
841
842 batadv_nc_hash_key_gen(&nc_path_key, src, dst);
843
844 /* Search for existing nc_path */
845 nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key);
846
847 if (nc_path) {
848 /* Set timestamp to delay removal of nc_path */
849 nc_path->last_valid = jiffies;
850 return nc_path;
851 }
852
853 /* No existing nc_path was found; create a new */
854 nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC);
855
856 if (!nc_path)
857 return NULL;
858
859 /* Initialize nc_path */
860 INIT_LIST_HEAD(&nc_path->packet_list);
861 spin_lock_init(&nc_path->packet_list_lock);
862 atomic_set(&nc_path->refcount, 2);
863 nc_path->last_valid = jiffies;
864 memcpy(nc_path->next_hop, dst, ETH_ALEN);
865 memcpy(nc_path->prev_hop, src, ETH_ALEN);
866
867 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n",
868 nc_path->prev_hop,
869 nc_path->next_hop);
870
871 /* Add nc_path to hash table */
872 hash_added = batadv_hash_add(hash, batadv_nc_hash_compare,
873 batadv_nc_hash_choose, &nc_path_key,
874 &nc_path->hash_entry);
875
876 if (hash_added < 0) {
877 kfree(nc_path);
878 return NULL;
879 }
880
881 return nc_path;
882}
883
884/**
885 * batadv_nc_random_weight_tq - scale the receivers TQ-value to avoid unfair
886 * selection of a receiver with slightly lower TQ than the other
887 * @tq: to be weighted tq value
888 */
889static uint8_t batadv_nc_random_weight_tq(uint8_t tq)
890{
891 uint8_t rand_val, rand_tq;
892
893 get_random_bytes(&rand_val, sizeof(rand_val));
894
895 /* randomize the estimated packet loss (max TQ - estimated TQ) */
896 rand_tq = rand_val * (BATADV_TQ_MAX_VALUE - tq);
897
898 /* normalize the randomized packet loss */
899 rand_tq /= BATADV_TQ_MAX_VALUE;
900
901 /* convert to (randomized) estimated tq again */
902 return BATADV_TQ_MAX_VALUE - rand_tq;
903}
904
905/**
906 * batadv_nc_memxor - XOR destination with source
907 * @dst: byte array to XOR into
908 * @src: byte array to XOR from
909 * @len: length of destination array
910 */
911static void batadv_nc_memxor(char *dst, const char *src, unsigned int len)
912{
913 unsigned int i;
914
915 for (i = 0; i < len; ++i)
916 dst[i] ^= src[i];
917}
918
919/**
920 * batadv_nc_code_packets - code a received unicast_packet with an nc packet
921 * into a coded_packet and send it
922 * @bat_priv: the bat priv with all the soft interface information
923 * @skb: data skb to forward
924 * @ethhdr: pointer to the ethernet header inside the skb
925 * @nc_packet: structure containing the packet to the skb can be coded with
926 * @neigh_node: next hop to forward packet to
927 *
928 * Returns true if both packets are consumed, false otherwise.
929 */
930static bool batadv_nc_code_packets(struct batadv_priv *bat_priv,
931 struct sk_buff *skb,
932 struct ethhdr *ethhdr,
933 struct batadv_nc_packet *nc_packet,
934 struct batadv_neigh_node *neigh_node)
935{
936 uint8_t tq_weighted_neigh, tq_weighted_coding;
937 struct sk_buff *skb_dest, *skb_src;
938 struct batadv_unicast_packet *packet1;
939 struct batadv_unicast_packet *packet2;
940 struct batadv_coded_packet *coded_packet;
941 struct batadv_neigh_node *neigh_tmp, *router_neigh;
942 struct batadv_neigh_node *router_coding = NULL;
943 uint8_t *first_source, *first_dest, *second_source, *second_dest;
944 __be32 packet_id1, packet_id2;
945 size_t count;
946 bool res = false;
947 int coding_len;
948 int unicast_size = sizeof(*packet1);
949 int coded_size = sizeof(*coded_packet);
950 int header_add = coded_size - unicast_size;
951
952 router_neigh = batadv_orig_node_get_router(neigh_node->orig_node);
953 if (!router_neigh)
954 goto out;
955
956 neigh_tmp = nc_packet->neigh_node;
957 router_coding = batadv_orig_node_get_router(neigh_tmp->orig_node);
958 if (!router_coding)
959 goto out;
960
961 tq_weighted_neigh = batadv_nc_random_weight_tq(router_neigh->tq_avg);
962 tq_weighted_coding = batadv_nc_random_weight_tq(router_coding->tq_avg);
963
964 /* Select one destination for the MAC-header dst-field based on
965 * weighted TQ-values.
966 */
967 if (tq_weighted_neigh >= tq_weighted_coding) {
968 /* Destination from nc_packet is selected for MAC-header */
969 first_dest = nc_packet->nc_path->next_hop;
970 first_source = nc_packet->nc_path->prev_hop;
971 second_dest = neigh_node->addr;
972 second_source = ethhdr->h_source;
973 packet1 = (struct batadv_unicast_packet *)nc_packet->skb->data;
974 packet2 = (struct batadv_unicast_packet *)skb->data;
975 packet_id1 = nc_packet->packet_id;
976 packet_id2 = batadv_skb_crc32(skb,
977 skb->data + sizeof(*packet2));
978 } else {
979 /* Destination for skb is selected for MAC-header */
980 first_dest = neigh_node->addr;
981 first_source = ethhdr->h_source;
982 second_dest = nc_packet->nc_path->next_hop;
983 second_source = nc_packet->nc_path->prev_hop;
984 packet1 = (struct batadv_unicast_packet *)skb->data;
985 packet2 = (struct batadv_unicast_packet *)nc_packet->skb->data;
986 packet_id1 = batadv_skb_crc32(skb,
987 skb->data + sizeof(*packet1));
988 packet_id2 = nc_packet->packet_id;
989 }
990
991 /* Instead of zero padding the smallest data buffer, we
992 * code into the largest.
993 */
994 if (skb->len <= nc_packet->skb->len) {
995 skb_dest = nc_packet->skb;
996 skb_src = skb;
997 } else {
998 skb_dest = skb;
999 skb_src = nc_packet->skb;
1000 }
1001
1002 /* coding_len is used when decoding the packet shorter packet */
1003 coding_len = skb_src->len - unicast_size;
1004
1005 if (skb_linearize(skb_dest) < 0 || skb_linearize(skb_src) < 0)
1006 goto out;
1007
1008 skb_push(skb_dest, header_add);
1009
1010 coded_packet = (struct batadv_coded_packet *)skb_dest->data;
1011 skb_reset_mac_header(skb_dest);
1012
1013 coded_packet->header.packet_type = BATADV_CODED;
1014 coded_packet->header.version = BATADV_COMPAT_VERSION;
1015 coded_packet->header.ttl = packet1->header.ttl;
1016
1017 /* Info about first unicast packet */
1018 memcpy(coded_packet->first_source, first_source, ETH_ALEN);
1019 memcpy(coded_packet->first_orig_dest, packet1->dest, ETH_ALEN);
1020 coded_packet->first_crc = packet_id1;
1021 coded_packet->first_ttvn = packet1->ttvn;
1022
1023 /* Info about second unicast packet */
1024 memcpy(coded_packet->second_dest, second_dest, ETH_ALEN);
1025 memcpy(coded_packet->second_source, second_source, ETH_ALEN);
1026 memcpy(coded_packet->second_orig_dest, packet2->dest, ETH_ALEN);
1027 coded_packet->second_crc = packet_id2;
1028 coded_packet->second_ttl = packet2->header.ttl;
1029 coded_packet->second_ttvn = packet2->ttvn;
1030 coded_packet->coded_len = htons(coding_len);
1031
1032 /* This is where the magic happens: Code skb_src into skb_dest */
1033 batadv_nc_memxor(skb_dest->data + coded_size,
1034 skb_src->data + unicast_size, coding_len);
1035
1036 /* Update counters accordingly */
1037 if (BATADV_SKB_CB(skb_src)->decoded &&
1038 BATADV_SKB_CB(skb_dest)->decoded) {
1039 /* Both packets are recoded */
1040 count = skb_src->len + ETH_HLEN;
1041 count += skb_dest->len + ETH_HLEN;
1042 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE, 2);
1043 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES, count);
1044 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1045 !BATADV_SKB_CB(skb_dest)->decoded) {
1046 /* Both packets are newly coded */
1047 count = skb_src->len + ETH_HLEN;
1048 count += skb_dest->len + ETH_HLEN;
1049 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE, 2);
1050 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES, count);
1051 } else if (BATADV_SKB_CB(skb_src)->decoded &&
1052 !BATADV_SKB_CB(skb_dest)->decoded) {
1053 /* skb_src recoded and skb_dest is newly coded */
1054 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1055 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1056 skb_src->len + ETH_HLEN);
1057 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1058 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1059 skb_dest->len + ETH_HLEN);
1060 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1061 BATADV_SKB_CB(skb_dest)->decoded) {
1062 /* skb_src is newly coded and skb_dest is recoded */
1063 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1064 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1065 skb_src->len + ETH_HLEN);
1066 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1067 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1068 skb_dest->len + ETH_HLEN);
1069 }
1070
1071 /* skb_src is now coded into skb_dest, so free it */
1072 kfree_skb(skb_src);
1073
1074 /* avoid duplicate free of skb from nc_packet */
1075 nc_packet->skb = NULL;
1076 batadv_nc_packet_free(nc_packet);
1077
1078 /* Send the coded packet and return true */
1079 batadv_send_skb_packet(skb_dest, neigh_node->if_incoming, first_dest);
1080 res = true;
1081out:
1082 if (router_neigh)
1083 batadv_neigh_node_free_ref(router_neigh);
1084 if (router_coding)
1085 batadv_neigh_node_free_ref(router_coding);
1086 return res;
1087}
1088
1089/**
1090 * batadv_nc_skb_coding_possible - true if a decoded skb is available at dst.
1091 * @skb: data skb to forward
1092 * @dst: destination mac address of the other skb to code with
1093 * @src: source mac address of skb
1094 *
1095 * Whenever we network code a packet we have to check whether we received it in
1096 * a network coded form. If so, we may not be able to use it for coding because
1097 * some neighbors may also have received (overheard) the packet in the network
1098 * coded form without being able to decode it. It is hard to know which of the
1099 * neighboring nodes was able to decode the packet, therefore we can only
1100 * re-code the packet if the source of the previous encoded packet is involved.
1101 * Since the source encoded the packet we can be certain it has all necessary
1102 * decode information.
1103 *
1104 * Returns true if coding of a decoded packet is allowed.
1105 */
1106static bool batadv_nc_skb_coding_possible(struct sk_buff *skb,
1107 uint8_t *dst, uint8_t *src)
1108{
1109 if (BATADV_SKB_CB(skb)->decoded && !batadv_compare_eth(dst, src))
1110 return false;
1111 else
1112 return true;
1113}
1114
1115/**
1116 * batadv_nc_path_search - Find the coding path matching in_nc_node and
1117 * out_nc_node to retrieve a buffered packet that can be used for coding.
1118 * @bat_priv: the bat priv with all the soft interface information
1119 * @in_nc_node: pointer to skb next hop's neighbor nc node
1120 * @out_nc_node: pointer to skb source's neighbor nc node
1121 * @skb: data skb to forward
1122 * @eth_dst: next hop mac address of skb
1123 *
1124 * Returns true if coding of a decoded skb is allowed.
1125 */
1126static struct batadv_nc_packet *
1127batadv_nc_path_search(struct batadv_priv *bat_priv,
1128 struct batadv_nc_node *in_nc_node,
1129 struct batadv_nc_node *out_nc_node,
1130 struct sk_buff *skb,
1131 uint8_t *eth_dst)
1132{
1133 struct batadv_nc_path *nc_path, nc_path_key;
1134 struct batadv_nc_packet *nc_packet_out = NULL;
1135 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
1136 struct batadv_hashtable *hash = bat_priv->nc.coding_hash;
1137 int idx;
1138
1139 if (!hash)
1140 return NULL;
1141
1142 /* Create almost path key */
1143 batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr,
1144 out_nc_node->addr);
1145 idx = batadv_nc_hash_choose(&nc_path_key, hash->size);
1146
1147 /* Check for coding opportunities in this nc_path */
1148 rcu_read_lock();
1149 hlist_for_each_entry_rcu(nc_path, &hash->table[idx], hash_entry) {
1150 if (!batadv_compare_eth(nc_path->prev_hop, in_nc_node->addr))
1151 continue;
1152
1153 if (!batadv_compare_eth(nc_path->next_hop, out_nc_node->addr))
1154 continue;
1155
1156 spin_lock_bh(&nc_path->packet_list_lock);
1157 if (list_empty(&nc_path->packet_list)) {
1158 spin_unlock_bh(&nc_path->packet_list_lock);
1159 continue;
1160 }
1161
1162 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
1163 &nc_path->packet_list, list) {
1164 if (!batadv_nc_skb_coding_possible(nc_packet->skb,
1165 eth_dst,
1166 in_nc_node->addr))
1167 continue;
1168
1169 /* Coding opportunity is found! */
1170 list_del(&nc_packet->list);
1171 nc_packet_out = nc_packet;
1172 break;
1173 }
1174
1175 spin_unlock_bh(&nc_path->packet_list_lock);
1176 break;
1177 }
1178 rcu_read_unlock();
1179
1180 return nc_packet_out;
1181}
1182
1183/**
1184 * batadv_nc_skb_src_search - Loops through the list of neighoring nodes of the
1185 * skb's sender (may be equal to the originator).
1186 * @bat_priv: the bat priv with all the soft interface information
1187 * @skb: data skb to forward
1188 * @eth_dst: next hop mac address of skb
1189 * @eth_src: source mac address of skb
1190 * @in_nc_node: pointer to skb next hop's neighbor nc node
1191 *
1192 * Returns an nc packet if a suitable coding packet was found, NULL otherwise.
1193 */
1194static struct batadv_nc_packet *
1195batadv_nc_skb_src_search(struct batadv_priv *bat_priv,
1196 struct sk_buff *skb,
1197 uint8_t *eth_dst,
1198 uint8_t *eth_src,
1199 struct batadv_nc_node *in_nc_node)
1200{
1201 struct batadv_orig_node *orig_node;
1202 struct batadv_nc_node *out_nc_node;
1203 struct batadv_nc_packet *nc_packet = NULL;
1204
1205 orig_node = batadv_orig_hash_find(bat_priv, eth_src);
1206 if (!orig_node)
1207 return NULL;
1208
1209 rcu_read_lock();
1210 list_for_each_entry_rcu(out_nc_node,
1211 &orig_node->out_coding_list, list) {
1212 /* Check if the skb is decoded and if recoding is possible */
1213 if (!batadv_nc_skb_coding_possible(skb,
1214 out_nc_node->addr, eth_src))
1215 continue;
1216
1217 /* Search for an opportunity in this nc_path */
1218 nc_packet = batadv_nc_path_search(bat_priv, in_nc_node,
1219 out_nc_node, skb, eth_dst);
1220 if (nc_packet)
1221 break;
1222 }
1223 rcu_read_unlock();
1224
1225 batadv_orig_node_free_ref(orig_node);
1226 return nc_packet;
1227}
1228
1229/**
1230 * batadv_nc_skb_store_before_coding - set the ethernet src and dst of the
1231 * unicast skb before it is stored for use in later decoding
1232 * @bat_priv: the bat priv with all the soft interface information
1233 * @skb: data skb to store
1234 * @eth_dst_new: new destination mac address of skb
1235 */
1236static void batadv_nc_skb_store_before_coding(struct batadv_priv *bat_priv,
1237 struct sk_buff *skb,
1238 uint8_t *eth_dst_new)
1239{
1240 struct ethhdr *ethhdr;
1241
1242 /* Copy skb header to change the mac header */
1243 skb = pskb_copy(skb, GFP_ATOMIC);
1244 if (!skb)
1245 return;
1246
1247 /* Set the mac header as if we actually sent the packet uncoded */
1248 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1249 memcpy(ethhdr->h_source, ethhdr->h_dest, ETH_ALEN);
1250 memcpy(ethhdr->h_dest, eth_dst_new, ETH_ALEN);
1251
1252 /* Set data pointer to MAC header to mimic packets from our tx path */
1253 skb_push(skb, ETH_HLEN);
1254
1255 /* Add the packet to the decoding packet pool */
1256 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1257
1258 /* batadv_nc_skb_store_for_decoding() clones the skb, so we must free
1259 * our ref
1260 */
1261 kfree_skb(skb);
1262}
1263
1264/**
1265 * batadv_nc_skb_dst_search - Loops through list of neighboring nodes to dst.
1266 * @skb: data skb to forward
1267 * @neigh_node: next hop to forward packet to
1268 * @ethhdr: pointer to the ethernet header inside the skb
1269 *
1270 * Loops through list of neighboring nodes the next hop has a good connection to
1271 * (receives OGMs with a sufficient quality). We need to find a neighbor of our
1272 * next hop that potentially sent a packet which our next hop also received
1273 * (overheard) and has stored for later decoding.
1274 *
1275 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1276 */
1277static bool batadv_nc_skb_dst_search(struct sk_buff *skb,
1278 struct batadv_neigh_node *neigh_node,
1279 struct ethhdr *ethhdr)
1280{
1281 struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1282 struct batadv_priv *bat_priv = netdev_priv(netdev);
1283 struct batadv_orig_node *orig_node = neigh_node->orig_node;
1284 struct batadv_nc_node *nc_node;
1285 struct batadv_nc_packet *nc_packet = NULL;
1286
1287 rcu_read_lock();
1288 list_for_each_entry_rcu(nc_node, &orig_node->in_coding_list, list) {
1289 /* Search for coding opportunity with this in_nc_node */
1290 nc_packet = batadv_nc_skb_src_search(bat_priv, skb,
1291 neigh_node->addr,
1292 ethhdr->h_source, nc_node);
1293
1294 /* Opportunity was found, so stop searching */
1295 if (nc_packet)
1296 break;
1297 }
1298 rcu_read_unlock();
1299
1300 if (!nc_packet)
1301 return false;
1302
1303 /* Save packets for later decoding */
1304 batadv_nc_skb_store_before_coding(bat_priv, skb,
1305 neigh_node->addr);
1306 batadv_nc_skb_store_before_coding(bat_priv, nc_packet->skb,
1307 nc_packet->neigh_node->addr);
1308
1309 /* Code and send packets */
1310 if (batadv_nc_code_packets(bat_priv, skb, ethhdr, nc_packet,
1311 neigh_node))
1312 return true;
1313
1314 /* out of mem ? Coding failed - we have to free the buffered packet
1315 * to avoid memleaks. The skb passed as argument will be dealt with
1316 * by the calling function.
1317 */
1318 batadv_nc_send_packet(nc_packet);
1319 return false;
1320}
1321
1322/**
1323 * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding
1324 * @skb: skb to add to path
1325 * @nc_path: path to add skb to
1326 * @neigh_node: next hop to forward packet to
1327 * @packet_id: checksum to identify packet
1328 *
1329 * Returns true if the packet was buffered or false in case of an error.
1330 */
1331static bool batadv_nc_skb_add_to_path(struct sk_buff *skb,
1332 struct batadv_nc_path *nc_path,
1333 struct batadv_neigh_node *neigh_node,
1334 __be32 packet_id)
1335{
1336 struct batadv_nc_packet *nc_packet;
1337
1338 nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC);
1339 if (!nc_packet)
1340 return false;
1341
1342 /* Initialize nc_packet */
1343 nc_packet->timestamp = jiffies;
1344 nc_packet->packet_id = packet_id;
1345 nc_packet->skb = skb;
1346 nc_packet->neigh_node = neigh_node;
1347 nc_packet->nc_path = nc_path;
1348
1349 /* Add coding packet to list */
1350 spin_lock_bh(&nc_path->packet_list_lock);
1351 list_add_tail(&nc_packet->list, &nc_path->packet_list);
1352 spin_unlock_bh(&nc_path->packet_list_lock);
1353
1354 return true;
1355}
1356
1357/**
1358 * batadv_nc_skb_forward - try to code a packet or add it to the coding packet
1359 * buffer
1360 * @skb: data skb to forward
1361 * @neigh_node: next hop to forward packet to
1362 * @ethhdr: pointer to the ethernet header inside the skb
1363 *
1364 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1365 */
1366bool batadv_nc_skb_forward(struct sk_buff *skb,
1367 struct batadv_neigh_node *neigh_node,
1368 struct ethhdr *ethhdr)
1369{
1370 const struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1371 struct batadv_priv *bat_priv = netdev_priv(netdev);
1372 struct batadv_unicast_packet *packet;
1373 struct batadv_nc_path *nc_path;
1374 __be32 packet_id;
1375 u8 *payload;
1376
1377 /* Check if network coding is enabled */
1378 if (!atomic_read(&bat_priv->network_coding))
1379 goto out;
1380
1381 /* We only handle unicast packets */
1382 payload = skb_network_header(skb);
1383 packet = (struct batadv_unicast_packet *)payload;
1384 if (packet->header.packet_type != BATADV_UNICAST)
1385 goto out;
1386
1387 /* Try to find a coding opportunity and send the skb if one is found */
1388 if (batadv_nc_skb_dst_search(skb, neigh_node, ethhdr))
1389 return true;
1390
1391 /* Find or create a nc_path for this src-dst pair */
1392 nc_path = batadv_nc_get_path(bat_priv,
1393 bat_priv->nc.coding_hash,
1394 ethhdr->h_source,
1395 neigh_node->addr);
1396
1397 if (!nc_path)
1398 goto out;
1399
1400 /* Add skb to nc_path */
1401 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1402 if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id))
1403 goto free_nc_path;
1404
1405 /* Packet is consumed */
1406 return true;
1407
1408free_nc_path:
1409 batadv_nc_path_free_ref(nc_path);
1410out:
1411 /* Packet is not consumed */
1412 return false;
1413}
1414
1415/**
1416 * batadv_nc_skb_store_for_decoding - save a clone of the skb which can be used
1417 * when decoding coded packets
1418 * @bat_priv: the bat priv with all the soft interface information
1419 * @skb: data skb to store
1420 */
1421void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
1422 struct sk_buff *skb)
1423{
1424 struct batadv_unicast_packet *packet;
1425 struct batadv_nc_path *nc_path;
1426 struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb);
1427 __be32 packet_id;
1428 u8 *payload;
1429
1430 /* Check if network coding is enabled */
1431 if (!atomic_read(&bat_priv->network_coding))
1432 goto out;
1433
1434 /* Check for supported packet type */
1435 payload = skb_network_header(skb);
1436 packet = (struct batadv_unicast_packet *)payload;
1437 if (packet->header.packet_type != BATADV_UNICAST)
1438 goto out;
1439
1440 /* Find existing nc_path or create a new */
1441 nc_path = batadv_nc_get_path(bat_priv,
1442 bat_priv->nc.decoding_hash,
1443 ethhdr->h_source,
1444 ethhdr->h_dest);
1445
1446 if (!nc_path)
1447 goto out;
1448
1449 /* Clone skb and adjust skb->data to point at batman header */
1450 skb = skb_clone(skb, GFP_ATOMIC);
1451 if (unlikely(!skb))
1452 goto free_nc_path;
1453
1454 if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
1455 goto free_skb;
1456
1457 if (unlikely(!skb_pull_rcsum(skb, ETH_HLEN)))
1458 goto free_skb;
1459
1460 /* Add skb to nc_path */
1461 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1462 if (!batadv_nc_skb_add_to_path(skb, nc_path, NULL, packet_id))
1463 goto free_skb;
1464
1465 batadv_inc_counter(bat_priv, BATADV_CNT_NC_BUFFER);
1466 return;
1467
1468free_skb:
1469 kfree_skb(skb);
1470free_nc_path:
1471 batadv_nc_path_free_ref(nc_path);
1472out:
1473 return;
1474}
1475
1476/**
1477 * batadv_nc_skb_store_sniffed_unicast - check if a received unicast packet
1478 * should be saved in the decoding buffer and, if so, store it there
1479 * @bat_priv: the bat priv with all the soft interface information
1480 * @skb: unicast skb to store
1481 */
1482void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
1483 struct sk_buff *skb)
1484{
1485 struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb);
1486
1487 if (batadv_is_my_mac(ethhdr->h_dest))
1488 return;
1489
1490 /* Set data pointer to MAC header to mimic packets from our tx path */
1491 skb_push(skb, ETH_HLEN);
1492
1493 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1494}
1495
1496/**
1497 * batadv_nc_skb_decode_packet - decode given skb using the decode data stored
1498 * in nc_packet
1499 * @skb: unicast skb to decode
1500 * @nc_packet: decode data needed to decode the skb
1501 *
1502 * Returns pointer to decoded unicast packet if the packet was decoded or NULL
1503 * in case of an error.
1504 */
1505static struct batadv_unicast_packet *
1506batadv_nc_skb_decode_packet(struct sk_buff *skb,
1507 struct batadv_nc_packet *nc_packet)
1508{
1509 const int h_size = sizeof(struct batadv_unicast_packet);
1510 const int h_diff = sizeof(struct batadv_coded_packet) - h_size;
1511 struct batadv_unicast_packet *unicast_packet;
1512 struct batadv_coded_packet coded_packet_tmp;
1513 struct ethhdr *ethhdr, ethhdr_tmp;
1514 uint8_t *orig_dest, ttl, ttvn;
1515 unsigned int coding_len;
1516
1517 /* Save headers temporarily */
1518 memcpy(&coded_packet_tmp, skb->data, sizeof(coded_packet_tmp));
1519 memcpy(&ethhdr_tmp, skb_mac_header(skb), sizeof(ethhdr_tmp));
1520
1521 if (skb_cow(skb, 0) < 0)
1522 return NULL;
1523
1524 if (unlikely(!skb_pull_rcsum(skb, h_diff)))
1525 return NULL;
1526
1527 /* Data points to batman header, so set mac header 14 bytes before
1528 * and network to data
1529 */
1530 skb_set_mac_header(skb, -ETH_HLEN);
1531 skb_reset_network_header(skb);
1532
1533 /* Reconstruct original mac header */
1534 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1535 memcpy(ethhdr, &ethhdr_tmp, sizeof(*ethhdr));
1536
1537 /* Select the correct unicast header information based on the location
1538 * of our mac address in the coded_packet header
1539 */
1540 if (batadv_is_my_mac(coded_packet_tmp.second_dest)) {
1541 /* If we are the second destination the packet was overheard,
1542 * so the Ethernet address must be copied to h_dest and
1543 * pkt_type changed from PACKET_OTHERHOST to PACKET_HOST
1544 */
1545 memcpy(ethhdr->h_dest, coded_packet_tmp.second_dest, ETH_ALEN);
1546 skb->pkt_type = PACKET_HOST;
1547
1548 orig_dest = coded_packet_tmp.second_orig_dest;
1549 ttl = coded_packet_tmp.second_ttl;
1550 ttvn = coded_packet_tmp.second_ttvn;
1551 } else {
1552 orig_dest = coded_packet_tmp.first_orig_dest;
1553 ttl = coded_packet_tmp.header.ttl;
1554 ttvn = coded_packet_tmp.first_ttvn;
1555 }
1556
1557 coding_len = ntohs(coded_packet_tmp.coded_len);
1558
1559 if (coding_len > skb->len)
1560 return NULL;
1561
1562 /* Here the magic is reversed:
1563 * extract the missing packet from the received coded packet
1564 */
1565 batadv_nc_memxor(skb->data + h_size,
1566 nc_packet->skb->data + h_size,
1567 coding_len);
1568
1569 /* Resize decoded skb if decoded with larger packet */
1570 if (nc_packet->skb->len > coding_len + h_size)
1571 pskb_trim_rcsum(skb, coding_len + h_size);
1572
1573 /* Create decoded unicast packet */
1574 unicast_packet = (struct batadv_unicast_packet *)skb->data;
1575 unicast_packet->header.packet_type = BATADV_UNICAST;
1576 unicast_packet->header.version = BATADV_COMPAT_VERSION;
1577 unicast_packet->header.ttl = ttl;
1578 memcpy(unicast_packet->dest, orig_dest, ETH_ALEN);
1579 unicast_packet->ttvn = ttvn;
1580
1581 batadv_nc_packet_free(nc_packet);
1582 return unicast_packet;
1583}
1584
1585/**
1586 * batadv_nc_find_decoding_packet - search through buffered decoding data to
1587 * find the data needed to decode the coded packet
1588 * @bat_priv: the bat priv with all the soft interface information
1589 * @ethhdr: pointer to the ethernet header inside the coded packet
1590 * @coded: coded packet we try to find decode data for
1591 *
1592 * Returns pointer to nc packet if the needed data was found or NULL otherwise.
1593 */
1594static struct batadv_nc_packet *
1595batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv,
1596 struct ethhdr *ethhdr,
1597 struct batadv_coded_packet *coded)
1598{
1599 struct batadv_hashtable *hash = bat_priv->nc.decoding_hash;
1600 struct batadv_nc_packet *tmp_nc_packet, *nc_packet = NULL;
1601 struct batadv_nc_path *nc_path, nc_path_key;
1602 uint8_t *dest, *source;
1603 __be32 packet_id;
1604 int index;
1605
1606 if (!hash)
1607 return NULL;
1608
1609 /* Select the correct packet id based on the location of our mac-addr */
1610 dest = ethhdr->h_source;
1611 if (!batadv_is_my_mac(coded->second_dest)) {
1612 source = coded->second_source;
1613 packet_id = coded->second_crc;
1614 } else {
1615 source = coded->first_source;
1616 packet_id = coded->first_crc;
1617 }
1618
1619 batadv_nc_hash_key_gen(&nc_path_key, source, dest);
1620 index = batadv_nc_hash_choose(&nc_path_key, hash->size);
1621
1622 /* Search for matching coding path */
1623 rcu_read_lock();
1624 hlist_for_each_entry_rcu(nc_path, &hash->table[index], hash_entry) {
1625 /* Find matching nc_packet */
1626 spin_lock_bh(&nc_path->packet_list_lock);
1627 list_for_each_entry(tmp_nc_packet,
1628 &nc_path->packet_list, list) {
1629 if (packet_id == tmp_nc_packet->packet_id) {
1630 list_del(&tmp_nc_packet->list);
1631
1632 nc_packet = tmp_nc_packet;
1633 break;
1634 }
1635 }
1636 spin_unlock_bh(&nc_path->packet_list_lock);
1637
1638 if (nc_packet)
1639 break;
1640 }
1641 rcu_read_unlock();
1642
1643 if (!nc_packet)
1644 batadv_dbg(BATADV_DBG_NC, bat_priv,
1645 "No decoding packet found for %u\n", packet_id);
1646
1647 return nc_packet;
1648}
1649
1650/**
1651 * batadv_nc_recv_coded_packet - try to decode coded packet and enqueue the
1652 * resulting unicast packet
1653 * @skb: incoming coded packet
1654 * @recv_if: pointer to interface this packet was received on
1655 */
1656static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
1657 struct batadv_hard_iface *recv_if)
1658{
1659 struct batadv_priv *bat_priv = netdev_priv(recv_if->soft_iface);
1660 struct batadv_unicast_packet *unicast_packet;
1661 struct batadv_coded_packet *coded_packet;
1662 struct batadv_nc_packet *nc_packet;
1663 struct ethhdr *ethhdr;
1664 int hdr_size = sizeof(*coded_packet);
1665
1666 /* Check if network coding is enabled */
1667 if (!atomic_read(&bat_priv->network_coding))
1668 return NET_RX_DROP;
1669
1670 /* Make sure we can access (and remove) header */
1671 if (unlikely(!pskb_may_pull(skb, hdr_size)))
1672 return NET_RX_DROP;
1673
1674 coded_packet = (struct batadv_coded_packet *)skb->data;
1675 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1676
1677 /* Verify frame is destined for us */
1678 if (!batadv_is_my_mac(ethhdr->h_dest) &&
1679 !batadv_is_my_mac(coded_packet->second_dest))
1680 return NET_RX_DROP;
1681
1682 /* Update stat counter */
1683 if (batadv_is_my_mac(coded_packet->second_dest))
1684 batadv_inc_counter(bat_priv, BATADV_CNT_NC_SNIFFED);
1685
1686 nc_packet = batadv_nc_find_decoding_packet(bat_priv, ethhdr,
1687 coded_packet);
1688 if (!nc_packet) {
1689 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1690 return NET_RX_DROP;
1691 }
1692
1693 /* Make skb's linear, because decoding accesses the entire buffer */
1694 if (skb_linearize(skb) < 0)
1695 goto free_nc_packet;
1696
1697 if (skb_linearize(nc_packet->skb) < 0)
1698 goto free_nc_packet;
1699
1700 /* Decode the packet */
1701 unicast_packet = batadv_nc_skb_decode_packet(skb, nc_packet);
1702 if (!unicast_packet) {
1703 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1704 goto free_nc_packet;
1705 }
1706
1707 /* Mark packet as decoded to do correct recoding when forwarding */
1708 BATADV_SKB_CB(skb)->decoded = true;
1709 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE);
1710 batadv_add_counter(bat_priv, BATADV_CNT_NC_DECODE_BYTES,
1711 skb->len + ETH_HLEN);
1712 return batadv_recv_unicast_packet(skb, recv_if);
1713
1714free_nc_packet:
1715 batadv_nc_packet_free(nc_packet);
1716 return NET_RX_DROP;
1717}
1718
1719/**
1720 * batadv_nc_free - clean up network coding memory
1721 * @bat_priv: the bat priv with all the soft interface information
1722 */
1723void batadv_nc_free(struct batadv_priv *bat_priv)
1724{
1725 batadv_recv_handler_unregister(BATADV_CODED);
1726 cancel_delayed_work_sync(&bat_priv->nc.work);
1727
1728 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL);
1729 batadv_hash_destroy(bat_priv->nc.coding_hash);
1730 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL);
1731 batadv_hash_destroy(bat_priv->nc.decoding_hash);
1732}
1733
1734/**
1735 * batadv_nc_nodes_seq_print_text - print the nc node information
1736 * @seq: seq file to print on
1737 * @offset: not used
1738 */
1739int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
1740{
1741 struct net_device *net_dev = (struct net_device *)seq->private;
1742 struct batadv_priv *bat_priv = netdev_priv(net_dev);
1743 struct batadv_hashtable *hash = bat_priv->orig_hash;
1744 struct batadv_hard_iface *primary_if;
1745 struct hlist_head *head;
1746 struct batadv_orig_node *orig_node;
1747 struct batadv_nc_node *nc_node;
1748 int i;
1749
1750 primary_if = batadv_seq_print_text_primary_if_get(seq);
1751 if (!primary_if)
1752 goto out;
1753
1754 /* Traverse list of originators */
1755 for (i = 0; i < hash->size; i++) {
1756 head = &hash->table[i];
1757
1758 /* For each orig_node in this bin */
1759 rcu_read_lock();
1760 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
1761 seq_printf(seq, "Node: %pM\n", orig_node->orig);
1762
1763 seq_printf(seq, " Ingoing: ");
1764 /* For each in_nc_node to this orig_node */
1765 list_for_each_entry_rcu(nc_node,
1766 &orig_node->in_coding_list,
1767 list)
1768 seq_printf(seq, "%pM ",
1769 nc_node->addr);
1770 seq_printf(seq, "\n");
1771
1772 seq_printf(seq, " Outgoing: ");
1773 /* For out_nc_node to this orig_node */
1774 list_for_each_entry_rcu(nc_node,
1775 &orig_node->out_coding_list,
1776 list)
1777 seq_printf(seq, "%pM ",
1778 nc_node->addr);
1779 seq_printf(seq, "\n\n");
1780 }
1781 rcu_read_unlock();
1782 }
1783
1784out:
1785 if (primary_if)
1786 batadv_hardif_free_ref(primary_if);
1787 return 0;
1788}
1789
1790/**
1791 * batadv_nc_init_debugfs - create nc folder and related files in debugfs
1792 * @bat_priv: the bat priv with all the soft interface information
1793 */
1794int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
1795{
1796 struct dentry *nc_dir, *file;
1797
1798 nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
1799 if (!nc_dir)
1800 goto out;
1801
1802 file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir,
1803 &bat_priv->nc.min_tq);
1804 if (!file)
1805 goto out;
1806
1807 file = debugfs_create_u32("max_fwd_delay", S_IRUGO | S_IWUSR, nc_dir,
1808 &bat_priv->nc.max_fwd_delay);
1809 if (!file)
1810 goto out;
1811
1812 file = debugfs_create_u32("max_buffer_time", S_IRUGO | S_IWUSR, nc_dir,
1813 &bat_priv->nc.max_buffer_time);
1814 if (!file)
1815 goto out;
1816
1817 return 0;
1818
1819out:
1820 return -ENOMEM;
1821}
diff --git a/net/batman-adv/network-coding.h b/net/batman-adv/network-coding.h
new file mode 100644
index 000000000000..4fa6d0caddbd
--- /dev/null
+++ b/net/batman-adv/network-coding.h
@@ -0,0 +1,123 @@
1/* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors:
2 *
3 * Martin Hundebøll, Jeppe Ledet-Pedersen
4 *
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.
8 *
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.
13 *
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
17 * 02110-1301, USA
18 */
19
20#ifndef _NET_BATMAN_ADV_NETWORK_CODING_H_
21#define _NET_BATMAN_ADV_NETWORK_CODING_H_
22
23#ifdef CONFIG_BATMAN_ADV_NC
24
25int batadv_nc_init(struct batadv_priv *bat_priv);
26void batadv_nc_free(struct batadv_priv *bat_priv);
27void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
28 struct batadv_orig_node *orig_node,
29 struct batadv_orig_node *orig_neigh_node,
30 struct batadv_ogm_packet *ogm_packet,
31 int is_single_hop_neigh);
32void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
33 struct batadv_orig_node *orig_node,
34 bool (*to_purge)(struct batadv_priv *,
35 struct batadv_nc_node *));
36void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv);
37void batadv_nc_init_orig(struct batadv_orig_node *orig_node);
38bool batadv_nc_skb_forward(struct sk_buff *skb,
39 struct batadv_neigh_node *neigh_node,
40 struct ethhdr *ethhdr);
41void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
42 struct sk_buff *skb);
43void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
44 struct sk_buff *skb);
45int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset);
46int batadv_nc_init_debugfs(struct batadv_priv *bat_priv);
47
48#else /* ifdef CONFIG_BATMAN_ADV_NC */
49
50static inline int batadv_nc_init(struct batadv_priv *bat_priv)
51{
52 return 0;
53}
54
55static inline void batadv_nc_free(struct batadv_priv *bat_priv)
56{
57 return;
58}
59
60static inline void
61batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
62 struct batadv_orig_node *orig_node,
63 struct batadv_orig_node *orig_neigh_node,
64 struct batadv_ogm_packet *ogm_packet,
65 int is_single_hop_neigh)
66{
67 return;
68}
69
70static inline void
71batadv_nc_purge_orig(struct batadv_priv *bat_priv,
72 struct batadv_orig_node *orig_node,
73 bool (*to_purge)(struct batadv_priv *,
74 struct batadv_nc_node *))
75{
76 return;
77}
78
79static inline void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
80{
81 return;
82}
83
84static inline void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
85{
86 return;
87}
88
89static inline bool batadv_nc_skb_forward(struct sk_buff *skb,
90 struct batadv_neigh_node *neigh_node,
91 struct ethhdr *ethhdr)
92{
93 return false;
94}
95
96static inline void
97batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
98 struct sk_buff *skb)
99{
100 return;
101}
102
103static inline void
104batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
105 struct sk_buff *skb)
106{
107 return;
108}
109
110static inline int batadv_nc_nodes_seq_print_text(struct seq_file *seq,
111 void *offset)
112{
113 return 0;
114}
115
116static inline int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
117{
118 return 0;
119}
120
121#endif /* ifdef CONFIG_BATMAN_ADV_NC */
122
123#endif /* _NET_BATMAN_ADV_NETWORK_CODING_H_ */
diff --git a/net/batman-adv/originator.c b/net/batman-adv/originator.c
index 96fb80b724dc..585e684a380b 100644
--- a/net/batman-adv/originator.c
+++ b/net/batman-adv/originator.c
@@ -28,6 +28,7 @@
28#include "unicast.h" 28#include "unicast.h"
29#include "soft-interface.h" 29#include "soft-interface.h"
30#include "bridge_loop_avoidance.h" 30#include "bridge_loop_avoidance.h"
31#include "network-coding.h"
31 32
32/* hash class keys */ 33/* hash class keys */
33static struct lock_class_key batadv_orig_hash_lock_class_key; 34static struct lock_class_key batadv_orig_hash_lock_class_key;
@@ -142,6 +143,9 @@ static void batadv_orig_node_free_rcu(struct rcu_head *rcu)
142 143
143 spin_unlock_bh(&orig_node->neigh_list_lock); 144 spin_unlock_bh(&orig_node->neigh_list_lock);
144 145
146 /* Free nc_nodes */
147 batadv_nc_purge_orig(orig_node->bat_priv, orig_node, NULL);
148
145 batadv_frag_list_free(&orig_node->frag_list); 149 batadv_frag_list_free(&orig_node->frag_list);
146 batadv_tt_global_del_orig(orig_node->bat_priv, orig_node, 150 batadv_tt_global_del_orig(orig_node->bat_priv, orig_node,
147 "originator timed out"); 151 "originator timed out");
@@ -219,6 +223,8 @@ struct batadv_orig_node *batadv_get_orig_node(struct batadv_priv *bat_priv,
219 spin_lock_init(&orig_node->neigh_list_lock); 223 spin_lock_init(&orig_node->neigh_list_lock);
220 spin_lock_init(&orig_node->tt_buff_lock); 224 spin_lock_init(&orig_node->tt_buff_lock);
221 225
226 batadv_nc_init_orig(orig_node);
227
222 /* extra reference for return */ 228 /* extra reference for return */
223 atomic_set(&orig_node->refcount, 2); 229 atomic_set(&orig_node->refcount, 2);
224 230
diff --git a/net/batman-adv/packet.h b/net/batman-adv/packet.h
index ed0aa89bbf8b..a07995834b84 100644
--- a/net/batman-adv/packet.h
+++ b/net/batman-adv/packet.h
@@ -30,6 +30,7 @@ enum batadv_packettype {
30 BATADV_TT_QUERY = 0x07, 30 BATADV_TT_QUERY = 0x07,
31 BATADV_ROAM_ADV = 0x08, 31 BATADV_ROAM_ADV = 0x08,
32 BATADV_UNICAST_4ADDR = 0x09, 32 BATADV_UNICAST_4ADDR = 0x09,
33 BATADV_CODED = 0x0a,
33}; 34};
34 35
35/** 36/**
@@ -278,4 +279,36 @@ struct batadv_tt_change {
278 uint8_t addr[ETH_ALEN]; 279 uint8_t addr[ETH_ALEN];
279} __packed; 280} __packed;
280 281
282/**
283 * struct batadv_coded_packet - network coded packet
284 * @header: common batman packet header and ttl of first included packet
285 * @reserved: Align following fields to 2-byte boundaries
286 * @first_source: original source of first included packet
287 * @first_orig_dest: original destinal of first included packet
288 * @first_crc: checksum of first included packet
289 * @first_ttvn: tt-version number of first included packet
290 * @second_ttl: ttl of second packet
291 * @second_dest: second receiver of this coded packet
292 * @second_source: original source of second included packet
293 * @second_orig_dest: original destination of second included packet
294 * @second_crc: checksum of second included packet
295 * @second_ttvn: tt version number of second included packet
296 * @coded_len: length of network coded part of the payload
297 */
298struct batadv_coded_packet {
299 struct batadv_header header;
300 uint8_t first_ttvn;
301 /* uint8_t first_dest[ETH_ALEN]; - saved in mac header destination */
302 uint8_t first_source[ETH_ALEN];
303 uint8_t first_orig_dest[ETH_ALEN];
304 __be32 first_crc;
305 uint8_t second_ttl;
306 uint8_t second_ttvn;
307 uint8_t second_dest[ETH_ALEN];
308 uint8_t second_source[ETH_ALEN];
309 uint8_t second_orig_dest[ETH_ALEN];
310 __be32 second_crc;
311 uint16_t coded_len;
312};
313
281#endif /* _NET_BATMAN_ADV_PACKET_H_ */ 314#endif /* _NET_BATMAN_ADV_PACKET_H_ */
diff --git a/net/batman-adv/routing.c b/net/batman-adv/routing.c
index 5ee21cebbbb0..8f88967ff14b 100644
--- a/net/batman-adv/routing.c
+++ b/net/batman-adv/routing.c
@@ -29,6 +29,7 @@
29#include "unicast.h" 29#include "unicast.h"
30#include "bridge_loop_avoidance.h" 30#include "bridge_loop_avoidance.h"
31#include "distributed-arp-table.h" 31#include "distributed-arp-table.h"
32#include "network-coding.h"
32 33
33static int batadv_route_unicast_packet(struct sk_buff *skb, 34static int batadv_route_unicast_packet(struct sk_buff *skb,
34 struct batadv_hard_iface *recv_if); 35 struct batadv_hard_iface *recv_if);
@@ -548,27 +549,37 @@ batadv_find_ifalter_router(struct batadv_orig_node *primary_orig,
548 return router; 549 return router;
549} 550}
550 551
552/**
553 * batadv_check_unicast_packet - Check for malformed unicast packets
554 * @skb: packet to check
555 * @hdr_size: size of header to pull
556 *
557 * Check for short header and bad addresses in given packet. Returns negative
558 * value when check fails and 0 otherwise. The negative value depends on the
559 * reason: -ENODATA for bad header, -EBADR for broadcast destination or source,
560 * and -EREMOTE for non-local (other host) destination.
561 */
551static int batadv_check_unicast_packet(struct sk_buff *skb, int hdr_size) 562static int batadv_check_unicast_packet(struct sk_buff *skb, int hdr_size)
552{ 563{
553 struct ethhdr *ethhdr; 564 struct ethhdr *ethhdr;
554 565
555 /* drop packet if it has not necessary minimum size */ 566 /* drop packet if it has not necessary minimum size */
556 if (unlikely(!pskb_may_pull(skb, hdr_size))) 567 if (unlikely(!pskb_may_pull(skb, hdr_size)))
557 return -1; 568 return -ENODATA;
558 569
559 ethhdr = (struct ethhdr *)skb_mac_header(skb); 570 ethhdr = (struct ethhdr *)skb_mac_header(skb);
560 571
561 /* packet with unicast indication but broadcast recipient */ 572 /* packet with unicast indication but broadcast recipient */
562 if (is_broadcast_ether_addr(ethhdr->h_dest)) 573 if (is_broadcast_ether_addr(ethhdr->h_dest))
563 return -1; 574 return -EBADR;
564 575
565 /* packet with broadcast sender address */ 576 /* packet with broadcast sender address */
566 if (is_broadcast_ether_addr(ethhdr->h_source)) 577 if (is_broadcast_ether_addr(ethhdr->h_source))
567 return -1; 578 return -EBADR;
568 579
569 /* not for me */ 580 /* not for me */
570 if (!batadv_is_my_mac(ethhdr->h_dest)) 581 if (!batadv_is_my_mac(ethhdr->h_dest))
571 return -1; 582 return -EREMOTE;
572 583
573 return 0; 584 return 0;
574} 585}
@@ -850,15 +861,18 @@ static int batadv_route_unicast_packet(struct sk_buff *skb,
850 /* decrement ttl */ 861 /* decrement ttl */
851 unicast_packet->header.ttl--; 862 unicast_packet->header.ttl--;
852 863
853 /* Update stats counter */ 864 /* network code packet if possible */
854 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD); 865 if (batadv_nc_skb_forward(skb, neigh_node, ethhdr)) {
855 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES, 866 ret = NET_RX_SUCCESS;
856 skb->len + ETH_HLEN); 867 } else if (batadv_send_skb_to_orig(skb, orig_node, recv_if)) {
857
858 /* route it */
859 if (batadv_send_skb_to_orig(skb, orig_node, recv_if))
860 ret = NET_RX_SUCCESS; 868 ret = NET_RX_SUCCESS;
861 869
870 /* Update stats counter */
871 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
872 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
873 skb->len + ETH_HLEN);
874 }
875
862out: 876out:
863 if (neigh_node) 877 if (neigh_node)
864 batadv_neigh_node_free_ref(neigh_node); 878 batadv_neigh_node_free_ref(neigh_node);
@@ -1033,7 +1047,7 @@ int batadv_recv_unicast_packet(struct sk_buff *skb,
1033 struct batadv_unicast_4addr_packet *unicast_4addr_packet; 1047 struct batadv_unicast_4addr_packet *unicast_4addr_packet;
1034 uint8_t *orig_addr; 1048 uint8_t *orig_addr;
1035 struct batadv_orig_node *orig_node = NULL; 1049 struct batadv_orig_node *orig_node = NULL;
1036 int hdr_size = sizeof(*unicast_packet); 1050 int check, hdr_size = sizeof(*unicast_packet);
1037 bool is4addr; 1051 bool is4addr;
1038 1052
1039 unicast_packet = (struct batadv_unicast_packet *)skb->data; 1053 unicast_packet = (struct batadv_unicast_packet *)skb->data;
@@ -1044,7 +1058,16 @@ int batadv_recv_unicast_packet(struct sk_buff *skb,
1044 if (is4addr) 1058 if (is4addr)
1045 hdr_size = sizeof(*unicast_4addr_packet); 1059 hdr_size = sizeof(*unicast_4addr_packet);
1046 1060
1047 if (batadv_check_unicast_packet(skb, hdr_size) < 0) 1061 /* function returns -EREMOTE for promiscuous packets */
1062 check = batadv_check_unicast_packet(skb, hdr_size);
1063
1064 /* Even though the packet is not for us, we might save it to use for
1065 * decoding a later received coded packet
1066 */
1067 if (check == -EREMOTE)
1068 batadv_nc_skb_store_sniffed_unicast(bat_priv, skb);
1069
1070 if (check < 0)
1048 return NET_RX_DROP; 1071 return NET_RX_DROP;
1049 1072
1050 if (!batadv_check_unicast_ttvn(bat_priv, skb)) 1073 if (!batadv_check_unicast_ttvn(bat_priv, skb))
diff --git a/net/batman-adv/send.c b/net/batman-adv/send.c
index a67cffde37ae..263cfd1ccee7 100644
--- a/net/batman-adv/send.c
+++ b/net/batman-adv/send.c
@@ -27,6 +27,7 @@
27#include "vis.h" 27#include "vis.h"
28#include "gateway_common.h" 28#include "gateway_common.h"
29#include "originator.h" 29#include "originator.h"
30#include "network-coding.h"
30 31
31#include <linux/if_ether.h> 32#include <linux/if_ether.h>
32 33
@@ -39,6 +40,7 @@ int batadv_send_skb_packet(struct sk_buff *skb,
39 struct batadv_hard_iface *hard_iface, 40 struct batadv_hard_iface *hard_iface,
40 const uint8_t *dst_addr) 41 const uint8_t *dst_addr)
41{ 42{
43 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
42 struct ethhdr *ethhdr; 44 struct ethhdr *ethhdr;
43 45
44 if (hard_iface->if_status != BATADV_IF_ACTIVE) 46 if (hard_iface->if_status != BATADV_IF_ACTIVE)
@@ -70,6 +72,9 @@ int batadv_send_skb_packet(struct sk_buff *skb,
70 72
71 skb->dev = hard_iface->net_dev; 73 skb->dev = hard_iface->net_dev;
72 74
75 /* Save a clone of the skb to use when decoding coded packets */
76 batadv_nc_skb_store_for_decoding(bat_priv, skb);
77
73 /* dev_queue_xmit() returns a negative result on error. However on 78 /* dev_queue_xmit() returns a negative result on error. However on
74 * congestion and traffic shaping, it drops and returns NET_XMIT_DROP 79 * congestion and traffic shaping, it drops and returns NET_XMIT_DROP
75 * (which is > 0). This will not be treated as an error. 80 * (which is > 0). This will not be treated as an error.
diff --git a/net/batman-adv/soft-interface.c b/net/batman-adv/soft-interface.c
index 2711e870f557..f93ae42abb58 100644
--- a/net/batman-adv/soft-interface.c
+++ b/net/batman-adv/soft-interface.c
@@ -37,6 +37,7 @@
37#include <linux/if_ether.h> 37#include <linux/if_ether.h>
38#include "unicast.h" 38#include "unicast.h"
39#include "bridge_loop_avoidance.h" 39#include "bridge_loop_avoidance.h"
40#include "network-coding.h"
40 41
41 42
42static int batadv_get_settings(struct net_device *dev, struct ethtool_cmd *cmd); 43static int batadv_get_settings(struct net_device *dev, struct ethtool_cmd *cmd);
@@ -544,6 +545,8 @@ struct net_device *batadv_softif_create(const char *name)
544 if (ret < 0) 545 if (ret < 0)
545 goto unreg_soft_iface; 546 goto unreg_soft_iface;
546 547
548 batadv_nc_init_bat_priv(bat_priv);
549
547 ret = batadv_sysfs_add_meshif(soft_iface); 550 ret = batadv_sysfs_add_meshif(soft_iface);
548 if (ret < 0) 551 if (ret < 0)
549 goto unreg_soft_iface; 552 goto unreg_soft_iface;
@@ -662,6 +665,17 @@ static const struct {
662 { "dat_put_rx" }, 665 { "dat_put_rx" },
663 { "dat_cached_reply_tx" }, 666 { "dat_cached_reply_tx" },
664#endif 667#endif
668#ifdef CONFIG_BATMAN_ADV_NC
669 { "nc_code" },
670 { "nc_code_bytes" },
671 { "nc_recode" },
672 { "nc_recode_bytes" },
673 { "nc_buffer" },
674 { "nc_decode" },
675 { "nc_decode_bytes" },
676 { "nc_decode_failed" },
677 { "nc_sniffed" },
678#endif
665}; 679};
666 680
667static void batadv_get_strings(struct net_device *dev, uint32_t stringset, 681static void batadv_get_strings(struct net_device *dev, uint32_t stringset,
diff --git a/net/batman-adv/sysfs.c b/net/batman-adv/sysfs.c
index afbba319d73a..ce39f62f751e 100644
--- a/net/batman-adv/sysfs.c
+++ b/net/batman-adv/sysfs.c
@@ -442,6 +442,9 @@ static BATADV_ATTR(gw_bandwidth, S_IRUGO | S_IWUSR, batadv_show_gw_bwidth,
442#ifdef CONFIG_BATMAN_ADV_DEBUG 442#ifdef CONFIG_BATMAN_ADV_DEBUG
443BATADV_ATTR_SIF_UINT(log_level, S_IRUGO | S_IWUSR, 0, BATADV_DBG_ALL, NULL); 443BATADV_ATTR_SIF_UINT(log_level, S_IRUGO | S_IWUSR, 0, BATADV_DBG_ALL, NULL);
444#endif 444#endif
445#ifdef CONFIG_BATMAN_ADV_NC
446BATADV_ATTR_SIF_BOOL(network_coding, S_IRUGO | S_IWUSR, NULL);
447#endif
445 448
446static struct batadv_attribute *batadv_mesh_attrs[] = { 449static struct batadv_attribute *batadv_mesh_attrs[] = {
447 &batadv_attr_aggregated_ogms, 450 &batadv_attr_aggregated_ogms,
@@ -464,6 +467,9 @@ static struct batadv_attribute *batadv_mesh_attrs[] = {
464#ifdef CONFIG_BATMAN_ADV_DEBUG 467#ifdef CONFIG_BATMAN_ADV_DEBUG
465 &batadv_attr_log_level, 468 &batadv_attr_log_level,
466#endif 469#endif
470#ifdef CONFIG_BATMAN_ADV_NC
471 &batadv_attr_network_coding,
472#endif
467 NULL, 473 NULL,
468}; 474};
469 475
@@ -688,15 +694,10 @@ int batadv_throw_uevent(struct batadv_priv *bat_priv, enum batadv_uev_type type,
688 enum batadv_uev_action action, const char *data) 694 enum batadv_uev_action action, const char *data)
689{ 695{
690 int ret = -ENOMEM; 696 int ret = -ENOMEM;
691 struct batadv_hard_iface *primary_if;
692 struct kobject *bat_kobj; 697 struct kobject *bat_kobj;
693 char *uevent_env[4] = { NULL, NULL, NULL, NULL }; 698 char *uevent_env[4] = { NULL, NULL, NULL, NULL };
694 699
695 primary_if = batadv_primary_if_get_selected(bat_priv); 700 bat_kobj = &bat_priv->soft_iface->dev.kobj;
696 if (!primary_if)
697 goto out;
698
699 bat_kobj = &primary_if->soft_iface->dev.kobj;
700 701
701 uevent_env[0] = kmalloc(strlen(BATADV_UEV_TYPE_VAR) + 702 uevent_env[0] = kmalloc(strlen(BATADV_UEV_TYPE_VAR) +
702 strlen(batadv_uev_type_str[type]) + 1, 703 strlen(batadv_uev_type_str[type]) + 1,
@@ -732,9 +733,6 @@ out:
732 kfree(uevent_env[1]); 733 kfree(uevent_env[1]);
733 kfree(uevent_env[2]); 734 kfree(uevent_env[2]);
734 735
735 if (primary_if)
736 batadv_hardif_free_ref(primary_if);
737
738 if (ret) 736 if (ret)
739 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 737 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
740 "Impossible to send uevent for (%s,%s,%s) event (err: %d)\n", 738 "Impossible to send uevent for (%s,%s,%s) event (err: %d)\n",
diff --git a/net/batman-adv/translation-table.c b/net/batman-adv/translation-table.c
index 98a66a021a60..932232087449 100644
--- a/net/batman-adv/translation-table.c
+++ b/net/batman-adv/translation-table.c
@@ -385,25 +385,19 @@ static void batadv_tt_prepare_packet_buff(struct batadv_priv *bat_priv,
385 int *packet_buff_len, 385 int *packet_buff_len,
386 int min_packet_len) 386 int min_packet_len)
387{ 387{
388 struct batadv_hard_iface *primary_if;
389 int req_len; 388 int req_len;
390 389
391 primary_if = batadv_primary_if_get_selected(bat_priv);
392
393 req_len = min_packet_len; 390 req_len = min_packet_len;
394 req_len += batadv_tt_len(atomic_read(&bat_priv->tt.local_changes)); 391 req_len += batadv_tt_len(atomic_read(&bat_priv->tt.local_changes));
395 392
396 /* if we have too many changes for one packet don't send any 393 /* if we have too many changes for one packet don't send any
397 * and wait for the tt table request which will be fragmented 394 * and wait for the tt table request which will be fragmented
398 */ 395 */
399 if ((!primary_if) || (req_len > primary_if->soft_iface->mtu)) 396 if (req_len > bat_priv->soft_iface->mtu)
400 req_len = min_packet_len; 397 req_len = min_packet_len;
401 398
402 batadv_tt_realloc_packet_buff(packet_buff, packet_buff_len, 399 batadv_tt_realloc_packet_buff(packet_buff, packet_buff_len,
403 min_packet_len, req_len); 400 min_packet_len, req_len);
404
405 if (primary_if)
406 batadv_hardif_free_ref(primary_if);
407} 401}
408 402
409static int batadv_tt_changes_fill_buff(struct batadv_priv *bat_priv, 403static int batadv_tt_changes_fill_buff(struct batadv_priv *bat_priv,
@@ -908,7 +902,7 @@ out_remove:
908 /* remove address from local hash if present */ 902 /* remove address from local hash if present */
909 local_flags = batadv_tt_local_remove(bat_priv, tt_addr, 903 local_flags = batadv_tt_local_remove(bat_priv, tt_addr,
910 "global tt received", 904 "global tt received",
911 !!(flags & BATADV_TT_CLIENT_ROAM)); 905 flags & BATADV_TT_CLIENT_ROAM);
912 tt_global_entry->common.flags |= local_flags & BATADV_TT_CLIENT_WIFI; 906 tt_global_entry->common.flags |= local_flags & BATADV_TT_CLIENT_WIFI;
913 907
914 if (!(flags & BATADV_TT_CLIENT_ROAM)) 908 if (!(flags & BATADV_TT_CLIENT_ROAM))
@@ -1580,7 +1574,7 @@ static int batadv_tt_global_valid(const void *entry_ptr,
1580static struct sk_buff * 1574static struct sk_buff *
1581batadv_tt_response_fill_table(uint16_t tt_len, uint8_t ttvn, 1575batadv_tt_response_fill_table(uint16_t tt_len, uint8_t ttvn,
1582 struct batadv_hashtable *hash, 1576 struct batadv_hashtable *hash,
1583 struct batadv_hard_iface *primary_if, 1577 struct batadv_priv *bat_priv,
1584 int (*valid_cb)(const void *, const void *), 1578 int (*valid_cb)(const void *, const void *),
1585 void *cb_data) 1579 void *cb_data)
1586{ 1580{
@@ -1594,8 +1588,8 @@ batadv_tt_response_fill_table(uint16_t tt_len, uint8_t ttvn,
1594 uint32_t i; 1588 uint32_t i;
1595 size_t len; 1589 size_t len;
1596 1590
1597 if (tt_query_size + tt_len > primary_if->soft_iface->mtu) { 1591 if (tt_query_size + tt_len > bat_priv->soft_iface->mtu) {
1598 tt_len = primary_if->soft_iface->mtu - tt_query_size; 1592 tt_len = bat_priv->soft_iface->mtu - tt_query_size;
1599 tt_len -= tt_len % sizeof(struct batadv_tt_change); 1593 tt_len -= tt_len % sizeof(struct batadv_tt_change);
1600 } 1594 }
1601 tt_tot = tt_len / sizeof(struct batadv_tt_change); 1595 tt_tot = tt_len / sizeof(struct batadv_tt_change);
@@ -1715,7 +1709,6 @@ batadv_send_other_tt_response(struct batadv_priv *bat_priv,
1715{ 1709{
1716 struct batadv_orig_node *req_dst_orig_node; 1710 struct batadv_orig_node *req_dst_orig_node;
1717 struct batadv_orig_node *res_dst_orig_node = NULL; 1711 struct batadv_orig_node *res_dst_orig_node = NULL;
1718 struct batadv_hard_iface *primary_if = NULL;
1719 uint8_t orig_ttvn, req_ttvn, ttvn; 1712 uint8_t orig_ttvn, req_ttvn, ttvn;
1720 int ret = false; 1713 int ret = false;
1721 unsigned char *tt_buff; 1714 unsigned char *tt_buff;
@@ -1740,10 +1733,6 @@ batadv_send_other_tt_response(struct batadv_priv *bat_priv,
1740 if (!res_dst_orig_node) 1733 if (!res_dst_orig_node)
1741 goto out; 1734 goto out;
1742 1735
1743 primary_if = batadv_primary_if_get_selected(bat_priv);
1744 if (!primary_if)
1745 goto out;
1746
1747 orig_ttvn = (uint8_t)atomic_read(&req_dst_orig_node->last_ttvn); 1736 orig_ttvn = (uint8_t)atomic_read(&req_dst_orig_node->last_ttvn);
1748 req_ttvn = tt_request->ttvn; 1737 req_ttvn = tt_request->ttvn;
1749 1738
@@ -1791,7 +1780,7 @@ batadv_send_other_tt_response(struct batadv_priv *bat_priv,
1791 1780
1792 skb = batadv_tt_response_fill_table(tt_len, ttvn, 1781 skb = batadv_tt_response_fill_table(tt_len, ttvn,
1793 bat_priv->tt.global_hash, 1782 bat_priv->tt.global_hash,
1794 primary_if, 1783 bat_priv,
1795 batadv_tt_global_valid, 1784 batadv_tt_global_valid,
1796 req_dst_orig_node); 1785 req_dst_orig_node);
1797 if (!skb) 1786 if (!skb)
@@ -1828,8 +1817,6 @@ out:
1828 batadv_orig_node_free_ref(res_dst_orig_node); 1817 batadv_orig_node_free_ref(res_dst_orig_node);
1829 if (req_dst_orig_node) 1818 if (req_dst_orig_node)
1830 batadv_orig_node_free_ref(req_dst_orig_node); 1819 batadv_orig_node_free_ref(req_dst_orig_node);
1831 if (primary_if)
1832 batadv_hardif_free_ref(primary_if);
1833 if (!ret) 1820 if (!ret)
1834 kfree_skb(skb); 1821 kfree_skb(skb);
1835 return ret; 1822 return ret;
@@ -1907,7 +1894,7 @@ batadv_send_my_tt_response(struct batadv_priv *bat_priv,
1907 1894
1908 skb = batadv_tt_response_fill_table(tt_len, ttvn, 1895 skb = batadv_tt_response_fill_table(tt_len, ttvn,
1909 bat_priv->tt.local_hash, 1896 bat_priv->tt.local_hash,
1910 primary_if, 1897 bat_priv,
1911 batadv_tt_local_valid_entry, 1898 batadv_tt_local_valid_entry,
1912 NULL); 1899 NULL);
1913 if (!skb) 1900 if (!skb)
@@ -2528,7 +2515,7 @@ bool batadv_tt_global_client_is_roaming(struct batadv_priv *bat_priv,
2528 if (!tt_global_entry) 2515 if (!tt_global_entry)
2529 goto out; 2516 goto out;
2530 2517
2531 ret = !!(tt_global_entry->common.flags & BATADV_TT_CLIENT_ROAM); 2518 ret = tt_global_entry->common.flags & BATADV_TT_CLIENT_ROAM;
2532 batadv_tt_global_entry_free_ref(tt_global_entry); 2519 batadv_tt_global_entry_free_ref(tt_global_entry);
2533out: 2520out:
2534 return ret; 2521 return ret;
diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h
index 4cd87a0b5b80..aba8364c3689 100644
--- a/net/batman-adv/types.h
+++ b/net/batman-adv/types.h
@@ -128,6 +128,10 @@ struct batadv_hard_iface {
128 * @bond_list: list of bonding candidates 128 * @bond_list: list of bonding candidates
129 * @refcount: number of contexts the object is used 129 * @refcount: number of contexts the object is used
130 * @rcu: struct used for freeing in an RCU-safe manner 130 * @rcu: struct used for freeing in an RCU-safe manner
131 * @in_coding_list: list of nodes this orig can hear
132 * @out_coding_list: list of nodes that can hear this orig
133 * @in_coding_list_lock: protects in_coding_list
134 * @out_coding_list_lock: protects out_coding_list
131 */ 135 */
132struct batadv_orig_node { 136struct batadv_orig_node {
133 uint8_t orig[ETH_ALEN]; 137 uint8_t orig[ETH_ALEN];
@@ -171,6 +175,12 @@ struct batadv_orig_node {
171 struct list_head bond_list; 175 struct list_head bond_list;
172 atomic_t refcount; 176 atomic_t refcount;
173 struct rcu_head rcu; 177 struct rcu_head rcu;
178#ifdef CONFIG_BATMAN_ADV_NC
179 struct list_head in_coding_list;
180 struct list_head out_coding_list;
181 spinlock_t in_coding_list_lock; /* Protects in_coding_list */
182 spinlock_t out_coding_list_lock; /* Protects out_coding_list */
183#endif
174}; 184};
175 185
176/** 186/**
@@ -265,6 +275,17 @@ struct batadv_bcast_duplist_entry {
265 * @BATADV_CNT_DAT_PUT_RX: received dht PUT traffic packet counter 275 * @BATADV_CNT_DAT_PUT_RX: received dht PUT traffic packet counter
266 * @BATADV_CNT_DAT_CACHED_REPLY_TX: transmitted dat cache reply traffic packet 276 * @BATADV_CNT_DAT_CACHED_REPLY_TX: transmitted dat cache reply traffic packet
267 * counter 277 * counter
278 * @BATADV_CNT_NC_CODE: transmitted nc-combined traffic packet counter
279 * @BATADV_CNT_NC_CODE_BYTES: transmitted nc-combined traffic bytes counter
280 * @BATADV_CNT_NC_RECODE: transmitted nc-recombined traffic packet counter
281 * @BATADV_CNT_NC_RECODE_BYTES: transmitted nc-recombined traffic bytes counter
282 * @BATADV_CNT_NC_BUFFER: counter for packets buffered for later nc decoding
283 * @BATADV_CNT_NC_DECODE: received and nc-decoded traffic packet counter
284 * @BATADV_CNT_NC_DECODE_BYTES: received and nc-decoded traffic bytes counter
285 * @BATADV_CNT_NC_DECODE_FAILED: received and decode-failed traffic packet
286 * counter
287 * @BATADV_CNT_NC_SNIFFED: counter for nc-decoded packets received in promisc
288 * mode.
268 * @BATADV_CNT_NUM: number of traffic counters 289 * @BATADV_CNT_NUM: number of traffic counters
269 */ 290 */
270enum batadv_counters { 291enum batadv_counters {
@@ -292,6 +313,17 @@ enum batadv_counters {
292 BATADV_CNT_DAT_PUT_RX, 313 BATADV_CNT_DAT_PUT_RX,
293 BATADV_CNT_DAT_CACHED_REPLY_TX, 314 BATADV_CNT_DAT_CACHED_REPLY_TX,
294#endif 315#endif
316#ifdef CONFIG_BATMAN_ADV_NC
317 BATADV_CNT_NC_CODE,
318 BATADV_CNT_NC_CODE_BYTES,
319 BATADV_CNT_NC_RECODE,
320 BATADV_CNT_NC_RECODE_BYTES,
321 BATADV_CNT_NC_BUFFER,
322 BATADV_CNT_NC_DECODE,
323 BATADV_CNT_NC_DECODE_BYTES,
324 BATADV_CNT_NC_DECODE_FAILED,
325 BATADV_CNT_NC_SNIFFED,
326#endif
295 BATADV_CNT_NUM, 327 BATADV_CNT_NUM,
296}; 328};
297 329
@@ -428,6 +460,35 @@ struct batadv_priv_dat {
428#endif 460#endif
429 461
430/** 462/**
463 * struct batadv_priv_nc - per mesh interface network coding private data
464 * @work: work queue callback item for cleanup
465 * @debug_dir: dentry for nc subdir in batman-adv directory in debugfs
466 * @min_tq: only consider neighbors for encoding if neigh_tq > min_tq
467 * @max_fwd_delay: maximum packet forward delay to allow coding of packets
468 * @max_buffer_time: buffer time for sniffed packets used to decoding
469 * @timestamp_fwd_flush: timestamp of last forward packet queue flush
470 * @timestamp_sniffed_purge: timestamp of last sniffed packet queue purge
471 * @coding_hash: Hash table used to buffer skbs while waiting for another
472 * incoming skb to code it with. Skbs are added to the buffer just before being
473 * forwarded in routing.c
474 * @decoding_hash: Hash table used to buffer skbs that might be needed to decode
475 * a received coded skb. The buffer is used for 1) skbs arriving on the
476 * soft-interface; 2) skbs overheard on the hard-interface; and 3) skbs
477 * forwarded by batman-adv.
478 */
479struct batadv_priv_nc {
480 struct delayed_work work;
481 struct dentry *debug_dir;
482 u8 min_tq;
483 u32 max_fwd_delay;
484 u32 max_buffer_time;
485 unsigned long timestamp_fwd_flush;
486 unsigned long timestamp_sniffed_purge;
487 struct batadv_hashtable *coding_hash;
488 struct batadv_hashtable *decoding_hash;
489};
490
491/**
431 * struct batadv_priv - per mesh interface data 492 * struct batadv_priv - per mesh interface data
432 * @mesh_state: current status of the mesh (inactive/active/deactivating) 493 * @mesh_state: current status of the mesh (inactive/active/deactivating)
433 * @soft_iface: net device which holds this struct as private data 494 * @soft_iface: net device which holds this struct as private data
@@ -470,6 +531,8 @@ struct batadv_priv_dat {
470 * @tt: translation table data 531 * @tt: translation table data
471 * @vis: vis data 532 * @vis: vis data
472 * @dat: distributed arp table data 533 * @dat: distributed arp table data
534 * @network_coding: bool indicating whether network coding is enabled
535 * @batadv_priv_nc: network coding data
473 */ 536 */
474struct batadv_priv { 537struct batadv_priv {
475 atomic_t mesh_state; 538 atomic_t mesh_state;
@@ -522,6 +585,10 @@ struct batadv_priv {
522#ifdef CONFIG_BATMAN_ADV_DAT 585#ifdef CONFIG_BATMAN_ADV_DAT
523 struct batadv_priv_dat dat; 586 struct batadv_priv_dat dat;
524#endif 587#endif
588#ifdef CONFIG_BATMAN_ADV_NC
589 atomic_t network_coding;
590 struct batadv_priv_nc nc;
591#endif /* CONFIG_BATMAN_ADV_NC */
525}; 592};
526 593
527/** 594/**
@@ -702,6 +769,75 @@ struct batadv_tt_roam_node {
702}; 769};
703 770
704/** 771/**
772 * struct batadv_nc_node - network coding node
773 * @list: next and prev pointer for the list handling
774 * @addr: the node's mac address
775 * @refcount: number of contexts the object is used by
776 * @rcu: struct used for freeing in an RCU-safe manner
777 * @orig_node: pointer to corresponding orig node struct
778 * @last_seen: timestamp of last ogm received from this node
779 */
780struct batadv_nc_node {
781 struct list_head list;
782 uint8_t addr[ETH_ALEN];
783 atomic_t refcount;
784 struct rcu_head rcu;
785 struct batadv_orig_node *orig_node;
786 unsigned long last_seen;
787};
788
789/**
790 * struct batadv_nc_path - network coding path
791 * @hash_entry: next and prev pointer for the list handling
792 * @rcu: struct used for freeing in an RCU-safe manner
793 * @refcount: number of contexts the object is used by
794 * @packet_list: list of buffered packets for this path
795 * @packet_list_lock: access lock for packet list
796 * @next_hop: next hop (destination) of path
797 * @prev_hop: previous hop (source) of path
798 * @last_valid: timestamp for last validation of path
799 */
800struct batadv_nc_path {
801 struct hlist_node hash_entry;
802 struct rcu_head rcu;
803 atomic_t refcount;
804 struct list_head packet_list;
805 spinlock_t packet_list_lock; /* Protects packet_list */
806 uint8_t next_hop[ETH_ALEN];
807 uint8_t prev_hop[ETH_ALEN];
808 unsigned long last_valid;
809};
810
811/**
812 * struct batadv_nc_packet - network coding packet used when coding and
813 * decoding packets
814 * @list: next and prev pointer for the list handling
815 * @packet_id: crc32 checksum of skb data
816 * @timestamp: field containing the info when the packet was added to path
817 * @neigh_node: pointer to original next hop neighbor of skb
818 * @skb: skb which can be encoded or used for decoding
819 * @nc_path: pointer to path this nc packet is attached to
820 */
821struct batadv_nc_packet {
822 struct list_head list;
823 __be32 packet_id;
824 unsigned long timestamp;
825 struct batadv_neigh_node *neigh_node;
826 struct sk_buff *skb;
827 struct batadv_nc_path *nc_path;
828};
829
830/**
831 * batadv_skb_cb - control buffer structure used to store private data relevant
832 * to batman-adv in the skb->cb buffer in skbs.
833 * @decoded: Marks a skb as decoded, which is checked when searching for coding
834 * opportunities in network-coding.c
835 */
836struct batadv_skb_cb {
837 bool decoded;
838};
839
840/**
705 * struct batadv_forw_packet - structure for bcast packets to be sent/forwarded 841 * struct batadv_forw_packet - structure for bcast packets to be sent/forwarded
706 * @list: list node for batadv_socket_client::queue_list 842 * @list: list node for batadv_socket_client::queue_list
707 * @send_time: execution time for delayed_work (packet sending) 843 * @send_time: execution time for delayed_work (packet sending)
diff --git a/net/batman-adv/unicast.c b/net/batman-adv/unicast.c
index 50e079f00be6..0bb3b5982f94 100644
--- a/net/batman-adv/unicast.c
+++ b/net/batman-adv/unicast.c
@@ -122,7 +122,7 @@ batadv_frag_search_packet(struct list_head *head,
122{ 122{
123 struct batadv_frag_packet_list_entry *tfp; 123 struct batadv_frag_packet_list_entry *tfp;
124 struct batadv_unicast_frag_packet *tmp_up = NULL; 124 struct batadv_unicast_frag_packet *tmp_up = NULL;
125 int is_head_tmp, is_head; 125 bool is_head_tmp, is_head;
126 uint16_t search_seqno; 126 uint16_t search_seqno;
127 127
128 if (up->flags & BATADV_UNI_FRAG_HEAD) 128 if (up->flags & BATADV_UNI_FRAG_HEAD)
@@ -130,7 +130,7 @@ batadv_frag_search_packet(struct list_head *head,
130 else 130 else
131 search_seqno = ntohs(up->seqno)-1; 131 search_seqno = ntohs(up->seqno)-1;
132 132
133 is_head = !!(up->flags & BATADV_UNI_FRAG_HEAD); 133 is_head = up->flags & BATADV_UNI_FRAG_HEAD;
134 134
135 list_for_each_entry(tfp, head, list) { 135 list_for_each_entry(tfp, head, list) {
136 if (!tfp->skb) 136 if (!tfp->skb)
@@ -142,7 +142,7 @@ batadv_frag_search_packet(struct list_head *head,
142 tmp_up = (struct batadv_unicast_frag_packet *)tfp->skb->data; 142 tmp_up = (struct batadv_unicast_frag_packet *)tfp->skb->data;
143 143
144 if (tfp->seqno == search_seqno) { 144 if (tfp->seqno == search_seqno) {
145 is_head_tmp = !!(tmp_up->flags & BATADV_UNI_FRAG_HEAD); 145 is_head_tmp = tmp_up->flags & BATADV_UNI_FRAG_HEAD;
146 if (is_head_tmp != is_head) 146 if (is_head_tmp != is_head)
147 return tfp; 147 return tfp;
148 else 148 else
generated by cgit v1.2.2 (git 2.25.0) at 2026-05-27 13:53:31 -0400