blob: f0a50f31d822e8a9f90477249b0727a668f70a28 [file] [log] [blame]
Sven Eckelmann9f6446c2015-04-23 13:16:35 +02001/* Copyright (C) 2012-2015 B.A.T.M.A.N. contributors:
Martin Hundebølld353d8d2013-01-25 11:12:38 +01002 *
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
Antonio Quartulliebf38fb2013-11-03 20:40:48 +010015 * along with this program; if not, see <http://www.gnu.org/licenses/>.
Martin Hundebølld353d8d2013-01-25 11:12:38 +010016 */
17
Martin Hundebølld353d8d2013-01-25 11:12:38 +010018#include "network-coding.h"
Sven Eckelmann1e2c2a42015-04-17 19:40:28 +020019#include "main.h"
20
21#include <linux/atomic.h>
22#include <linux/byteorder/generic.h>
23#include <linux/compiler.h>
24#include <linux/debugfs.h>
25#include <linux/errno.h>
26#include <linux/etherdevice.h>
27#include <linux/fs.h>
28#include <linux/if_ether.h>
29#include <linux/if_packet.h>
30#include <linux/init.h>
31#include <linux/jhash.h>
32#include <linux/jiffies.h>
33#include <linux/kernel.h>
34#include <linux/list.h>
35#include <linux/lockdep.h>
36#include <linux/netdevice.h>
37#include <linux/printk.h>
38#include <linux/random.h>
39#include <linux/rculist.h>
40#include <linux/rcupdate.h>
41#include <linux/seq_file.h>
42#include <linux/skbuff.h>
43#include <linux/slab.h>
44#include <linux/spinlock.h>
45#include <linux/stat.h>
46#include <linux/stddef.h>
47#include <linux/string.h>
48#include <linux/workqueue.h>
49
Martin Hundebølld56b1702013-01-25 11:12:39 +010050#include "hard-interface.h"
Sven Eckelmann1e2c2a42015-04-17 19:40:28 +020051#include "hash.h"
52#include "originator.h"
53#include "packet.h"
Martin Hundebøll2df52782013-01-25 11:12:43 +010054#include "routing.h"
Sven Eckelmann1e2c2a42015-04-17 19:40:28 +020055#include "send.h"
Martin Hundebølld353d8d2013-01-25 11:12:38 +010056
Martin Hundebøll95332472013-01-25 11:12:40 +010057static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
Martin Hundebøll612d2b42013-01-25 11:12:42 +010058static struct lock_class_key batadv_nc_decoding_hash_lock_class_key;
Martin Hundebøll95332472013-01-25 11:12:40 +010059
Martin Hundebølld353d8d2013-01-25 11:12:38 +010060static void batadv_nc_worker(struct work_struct *work);
Martin Hundebøll2df52782013-01-25 11:12:43 +010061static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
62 struct batadv_hard_iface *recv_if);
Martin Hundebølld353d8d2013-01-25 11:12:38 +010063
64/**
Matthias Schiffer6c519ba2013-09-27 18:03:39 +020065 * batadv_nc_init - one-time initialization for network coding
66 */
67int __init batadv_nc_init(void)
68{
69 int ret;
70
71 /* Register our packet type */
72 ret = batadv_recv_handler_register(BATADV_CODED,
73 batadv_nc_recv_coded_packet);
74
75 return ret;
76}
77
78/**
Martin Hundebølld353d8d2013-01-25 11:12:38 +010079 * batadv_nc_start_timer - initialise the nc periodic worker
80 * @bat_priv: the bat priv with all the soft interface information
81 */
82static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
83{
84 queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,
85 msecs_to_jiffies(10));
86}
87
88/**
Marek Lindner3f4841f2013-04-23 21:40:00 +080089 * batadv_nc_tvlv_container_update - update the network coding tvlv container
90 * after network coding setting change
91 * @bat_priv: the bat priv with all the soft interface information
92 */
93static void batadv_nc_tvlv_container_update(struct batadv_priv *bat_priv)
94{
95 char nc_mode;
96
97 nc_mode = atomic_read(&bat_priv->network_coding);
98
99 switch (nc_mode) {
100 case 0:
101 batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);
102 break;
103 case 1:
104 batadv_tvlv_container_register(bat_priv, BATADV_TVLV_NC, 1,
105 NULL, 0);
106 break;
107 }
108}
109
110/**
111 * batadv_nc_status_update - update the network coding tvlv container after
112 * network coding setting change
113 * @net_dev: the soft interface net device
114 */
115void batadv_nc_status_update(struct net_device *net_dev)
116{
117 struct batadv_priv *bat_priv = netdev_priv(net_dev);
Antonio Quartullif1386942014-05-10 18:56:37 +0200118
Marek Lindner3f4841f2013-04-23 21:40:00 +0800119 batadv_nc_tvlv_container_update(bat_priv);
120}
121
122/**
123 * batadv_nc_tvlv_ogm_handler_v1 - process incoming nc tvlv container
124 * @bat_priv: the bat priv with all the soft interface information
125 * @orig: the orig_node of the ogm
126 * @flags: flags indicating the tvlv state (see batadv_tvlv_handler_flags)
127 * @tvlv_value: tvlv buffer containing the gateway data
128 * @tvlv_value_len: tvlv buffer length
129 */
130static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv,
131 struct batadv_orig_node *orig,
132 uint8_t flags,
133 void *tvlv_value,
134 uint16_t tvlv_value_len)
135{
136 if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND)
137 orig->capabilities &= ~BATADV_ORIG_CAPA_HAS_NC;
138 else
139 orig->capabilities |= BATADV_ORIG_CAPA_HAS_NC;
140}
141
142/**
Matthias Schiffer6c519ba2013-09-27 18:03:39 +0200143 * batadv_nc_mesh_init - initialise coding hash table and start house keeping
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100144 * @bat_priv: the bat priv with all the soft interface information
145 */
Matthias Schiffer6c519ba2013-09-27 18:03:39 +0200146int batadv_nc_mesh_init(struct batadv_priv *bat_priv)
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100147{
Martin Hundebøll95332472013-01-25 11:12:40 +0100148 bat_priv->nc.timestamp_fwd_flush = jiffies;
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100149 bat_priv->nc.timestamp_sniffed_purge = jiffies;
Martin Hundebøll95332472013-01-25 11:12:40 +0100150
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100151 if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash)
Martin Hundebøll95332472013-01-25 11:12:40 +0100152 return 0;
153
154 bat_priv->nc.coding_hash = batadv_hash_new(128);
155 if (!bat_priv->nc.coding_hash)
156 goto err;
157
158 batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
159 &batadv_nc_coding_hash_lock_class_key);
160
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100161 bat_priv->nc.decoding_hash = batadv_hash_new(128);
162 if (!bat_priv->nc.decoding_hash)
163 goto err;
164
Martin Hundebøllf44d5402014-11-11 16:22:23 +0100165 batadv_hash_set_lock_class(bat_priv->nc.decoding_hash,
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100166 &batadv_nc_decoding_hash_lock_class_key);
167
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100168 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
169 batadv_nc_start_timer(bat_priv);
170
Marek Lindner3f4841f2013-04-23 21:40:00 +0800171 batadv_tvlv_handler_register(bat_priv, batadv_nc_tvlv_ogm_handler_v1,
172 NULL, BATADV_TVLV_NC, 1,
173 BATADV_TVLV_HANDLER_OGM_CIFNOTFND);
174 batadv_nc_tvlv_container_update(bat_priv);
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100175 return 0;
Martin Hundebøll95332472013-01-25 11:12:40 +0100176
177err:
178 return -ENOMEM;
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100179}
180
181/**
182 * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables
183 * @bat_priv: the bat priv with all the soft interface information
184 */
185void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
186{
Sven Eckelmanndab7b622015-02-18 18:20:24 +0100187 atomic_set(&bat_priv->network_coding, 0);
Martin Hundebølld56b1702013-01-25 11:12:39 +0100188 bat_priv->nc.min_tq = 200;
Martin Hundebøll95332472013-01-25 11:12:40 +0100189 bat_priv->nc.max_fwd_delay = 10;
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100190 bat_priv->nc.max_buffer_time = 200;
Martin Hundebølld56b1702013-01-25 11:12:39 +0100191}
192
193/**
194 * batadv_nc_init_orig - initialise the nc fields of an orig_node
195 * @orig_node: the orig_node which is going to be initialised
196 */
197void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
198{
199 INIT_LIST_HEAD(&orig_node->in_coding_list);
200 INIT_LIST_HEAD(&orig_node->out_coding_list);
201 spin_lock_init(&orig_node->in_coding_list_lock);
202 spin_lock_init(&orig_node->out_coding_list_lock);
203}
204
205/**
206 * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove
207 * its refcount on the orig_node
208 * @rcu: rcu pointer of the nc node
209 */
210static void batadv_nc_node_free_rcu(struct rcu_head *rcu)
211{
212 struct batadv_nc_node *nc_node;
213
214 nc_node = container_of(rcu, struct batadv_nc_node, rcu);
215 batadv_orig_node_free_ref(nc_node->orig_node);
216 kfree(nc_node);
217}
218
219/**
220 * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly
221 * frees it
222 * @nc_node: the nc node to free
223 */
224static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node)
225{
226 if (atomic_dec_and_test(&nc_node->refcount))
227 call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu);
228}
229
230/**
Martin Hundebøll95332472013-01-25 11:12:40 +0100231 * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly
232 * frees it
233 * @nc_path: the nc node to free
234 */
235static void batadv_nc_path_free_ref(struct batadv_nc_path *nc_path)
236{
237 if (atomic_dec_and_test(&nc_path->refcount))
238 kfree_rcu(nc_path, rcu);
239}
240
241/**
242 * batadv_nc_packet_free - frees nc packet
243 * @nc_packet: the nc packet to free
244 */
245static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet)
246{
247 if (nc_packet->skb)
248 kfree_skb(nc_packet->skb);
249
250 batadv_nc_path_free_ref(nc_packet->nc_path);
251 kfree(nc_packet);
252}
253
254/**
Martin Hundebølld56b1702013-01-25 11:12:39 +0100255 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
256 * @bat_priv: the bat priv with all the soft interface information
257 * @nc_node: the nc node to check
258 *
259 * Returns true if the entry has to be purged now, false otherwise
260 */
261static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
262 struct batadv_nc_node *nc_node)
263{
264 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
265 return true;
266
267 return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
268}
269
270/**
Martin Hundebøll95332472013-01-25 11:12:40 +0100271 * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out
272 * @bat_priv: the bat priv with all the soft interface information
273 * @nc_path: the nc path to check
274 *
275 * Returns true if the entry has to be purged now, false otherwise
276 */
277static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,
278 struct batadv_nc_path *nc_path)
279{
280 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
281 return true;
282
283 /* purge the path when no packets has been added for 10 times the
284 * max_fwd_delay time
285 */
286 return batadv_has_timed_out(nc_path->last_valid,
287 bat_priv->nc.max_fwd_delay * 10);
288}
289
290/**
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100291 * batadv_nc_to_purge_nc_path_decoding - checks whether an nc path has timed out
292 * @bat_priv: the bat priv with all the soft interface information
293 * @nc_path: the nc path to check
294 *
295 * Returns true if the entry has to be purged now, false otherwise
296 */
297static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv *bat_priv,
298 struct batadv_nc_path *nc_path)
299{
300 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
301 return true;
302
303 /* purge the path when no packets has been added for 10 times the
304 * max_buffer time
305 */
306 return batadv_has_timed_out(nc_path->last_valid,
Marek Lindnerfc1f8692015-02-18 22:19:20 +0800307 bat_priv->nc.max_buffer_time * 10);
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100308}
309
310/**
Martin Hundebølld56b1702013-01-25 11:12:39 +0100311 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
312 * entries
313 * @bat_priv: the bat priv with all the soft interface information
314 * @list: list of nc nodes
315 * @lock: nc node list lock
316 * @to_purge: function in charge to decide whether an entry has to be purged or
317 * not. This function takes the nc node as argument and has to return
318 * a boolean value: true if the entry has to be deleted, false
319 * otherwise
320 */
321static void
322batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
323 struct list_head *list,
324 spinlock_t *lock,
325 bool (*to_purge)(struct batadv_priv *,
326 struct batadv_nc_node *))
327{
328 struct batadv_nc_node *nc_node, *nc_node_tmp;
329
330 /* For each nc_node in list */
331 spin_lock_bh(lock);
332 list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
333 /* if an helper function has been passed as parameter,
334 * ask it if the entry has to be purged or not
335 */
336 if (to_purge && !to_purge(bat_priv, nc_node))
337 continue;
338
339 batadv_dbg(BATADV_DBG_NC, bat_priv,
340 "Removing nc_node %pM -> %pM\n",
341 nc_node->addr, nc_node->orig_node->orig);
342 list_del_rcu(&nc_node->list);
343 batadv_nc_node_free_ref(nc_node);
344 }
345 spin_unlock_bh(lock);
346}
347
348/**
349 * batadv_nc_purge_orig - purges all nc node data attached of the given
350 * originator
351 * @bat_priv: the bat priv with all the soft interface information
352 * @orig_node: orig_node with the nc node entries to be purged
353 * @to_purge: function in charge to decide whether an entry has to be purged or
354 * not. This function takes the nc node as argument and has to return
355 * a boolean value: true is the entry has to be deleted, false
356 * otherwise
357 */
358void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
359 struct batadv_orig_node *orig_node,
360 bool (*to_purge)(struct batadv_priv *,
361 struct batadv_nc_node *))
362{
363 /* Check ingoing nc_node's of this orig_node */
364 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
365 &orig_node->in_coding_list_lock,
366 to_purge);
367
368 /* Check outgoing nc_node's of this orig_node */
369 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
370 &orig_node->out_coding_list_lock,
371 to_purge);
372}
373
374/**
375 * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
376 * have timed out nc nodes
377 * @bat_priv: the bat priv with all the soft interface information
378 */
379static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
380{
381 struct batadv_hashtable *hash = bat_priv->orig_hash;
382 struct hlist_head *head;
383 struct batadv_orig_node *orig_node;
384 uint32_t i;
385
386 if (!hash)
387 return;
388
389 /* For each orig_node */
390 for (i = 0; i < hash->size; i++) {
391 head = &hash->table[i];
392
393 rcu_read_lock();
394 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
395 batadv_nc_purge_orig(bat_priv, orig_node,
396 batadv_nc_to_purge_nc_node);
397 rcu_read_unlock();
398 }
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100399}
400
401/**
Martin Hundebøll95332472013-01-25 11:12:40 +0100402 * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove
403 * unused ones
404 * @bat_priv: the bat priv with all the soft interface information
405 * @hash: hash table containing the nc paths to check
406 * @to_purge: function in charge to decide whether an entry has to be purged or
407 * not. This function takes the nc node as argument and has to return
408 * a boolean value: true is the entry has to be deleted, false
409 * otherwise
410 */
411static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,
412 struct batadv_hashtable *hash,
413 bool (*to_purge)(struct batadv_priv *,
414 struct batadv_nc_path *))
415{
416 struct hlist_head *head;
417 struct hlist_node *node_tmp;
418 struct batadv_nc_path *nc_path;
419 spinlock_t *lock; /* Protects lists in hash */
420 uint32_t i;
421
422 for (i = 0; i < hash->size; i++) {
423 head = &hash->table[i];
424 lock = &hash->list_locks[i];
425
426 /* For each nc_path in this bin */
427 spin_lock_bh(lock);
428 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {
429 /* if an helper function has been passed as parameter,
430 * ask it if the entry has to be purged or not
431 */
432 if (to_purge && !to_purge(bat_priv, nc_path))
433 continue;
434
435 /* purging an non-empty nc_path should never happen, but
436 * is observed under high CPU load. Delay the purging
437 * until next iteration to allow the packet_list to be
438 * emptied first.
439 */
440 if (!unlikely(list_empty(&nc_path->packet_list))) {
441 net_ratelimited_function(printk,
442 KERN_WARNING
443 "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
444 nc_path->prev_hop,
445 nc_path->next_hop);
446 continue;
447 }
448
449 /* nc_path is unused, so remove it */
450 batadv_dbg(BATADV_DBG_NC, bat_priv,
451 "Remove nc_path %pM -> %pM\n",
452 nc_path->prev_hop, nc_path->next_hop);
453 hlist_del_rcu(&nc_path->hash_entry);
454 batadv_nc_path_free_ref(nc_path);
455 }
456 spin_unlock_bh(lock);
457 }
458}
459
460/**
461 * batadv_nc_hash_key_gen - computes the nc_path hash key
462 * @key: buffer to hold the final hash key
463 * @src: source ethernet mac address going into the hash key
464 * @dst: destination ethernet mac address going into the hash key
465 */
466static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,
467 const char *dst)
468{
469 memcpy(key->prev_hop, src, sizeof(key->prev_hop));
470 memcpy(key->next_hop, dst, sizeof(key->next_hop));
471}
472
473/**
474 * batadv_nc_hash_choose - compute the hash value for an nc path
475 * @data: data to hash
476 * @size: size of the hash table
477 *
478 * Returns the selected index in the hash table for the given data.
479 */
480static uint32_t batadv_nc_hash_choose(const void *data, uint32_t size)
481{
482 const struct batadv_nc_path *nc_path = data;
483 uint32_t hash = 0;
484
Sven Eckelmann36fd61c2015-03-01 09:46:18 +0100485 hash = jhash(&nc_path->prev_hop, sizeof(nc_path->prev_hop), hash);
486 hash = jhash(&nc_path->next_hop, sizeof(nc_path->next_hop), hash);
Martin Hundebøll95332472013-01-25 11:12:40 +0100487
488 return hash % size;
489}
490
491/**
492 * batadv_nc_hash_compare - comparing function used in the network coding hash
493 * tables
494 * @node: node in the local table
495 * @data2: second object to compare the node to
496 *
497 * Returns 1 if the two entry are the same, 0 otherwise
498 */
499static int batadv_nc_hash_compare(const struct hlist_node *node,
500 const void *data2)
501{
502 const struct batadv_nc_path *nc_path1, *nc_path2;
503
504 nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);
505 nc_path2 = data2;
506
507 /* Return 1 if the two keys are identical */
508 if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop,
509 sizeof(nc_path1->prev_hop)) != 0)
510 return 0;
511
512 if (memcmp(nc_path1->next_hop, nc_path2->next_hop,
513 sizeof(nc_path1->next_hop)) != 0)
514 return 0;
515
516 return 1;
517}
518
519/**
520 * batadv_nc_hash_find - search for an existing nc path and return it
521 * @hash: hash table containing the nc path
522 * @data: search key
523 *
524 * Returns the nc_path if found, NULL otherwise.
525 */
526static struct batadv_nc_path *
527batadv_nc_hash_find(struct batadv_hashtable *hash,
528 void *data)
529{
530 struct hlist_head *head;
531 struct batadv_nc_path *nc_path, *nc_path_tmp = NULL;
532 int index;
533
534 if (!hash)
535 return NULL;
536
537 index = batadv_nc_hash_choose(data, hash->size);
538 head = &hash->table[index];
539
540 rcu_read_lock();
541 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
542 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data))
543 continue;
544
545 if (!atomic_inc_not_zero(&nc_path->refcount))
546 continue;
547
548 nc_path_tmp = nc_path;
549 break;
550 }
551 rcu_read_unlock();
552
553 return nc_path_tmp;
554}
555
556/**
557 * batadv_nc_send_packet - send non-coded packet and free nc_packet struct
558 * @nc_packet: the nc packet to send
559 */
560static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet)
561{
562 batadv_send_skb_packet(nc_packet->skb,
563 nc_packet->neigh_node->if_incoming,
564 nc_packet->nc_path->next_hop);
565 nc_packet->skb = NULL;
566 batadv_nc_packet_free(nc_packet);
567}
568
569/**
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100570 * batadv_nc_sniffed_purge - Checks timestamp of given sniffed nc_packet.
571 * @bat_priv: the bat priv with all the soft interface information
572 * @nc_path: the nc path the packet belongs to
573 * @nc_packet: the nc packet to be checked
574 *
575 * Checks whether the given sniffed (overheard) nc_packet has hit its buffering
576 * timeout. If so, the packet is no longer kept and the entry deleted from the
577 * queue. Has to be called with the appropriate locks.
578 *
579 * Returns false as soon as the entry in the fifo queue has not been timed out
580 * yet and true otherwise.
581 */
582static bool batadv_nc_sniffed_purge(struct batadv_priv *bat_priv,
583 struct batadv_nc_path *nc_path,
584 struct batadv_nc_packet *nc_packet)
585{
586 unsigned long timeout = bat_priv->nc.max_buffer_time;
587 bool res = false;
588
589 /* Packets are added to tail, so the remaining packets did not time
590 * out and we can stop processing the current queue
591 */
592 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
593 !batadv_has_timed_out(nc_packet->timestamp, timeout))
594 goto out;
595
596 /* purge nc packet */
597 list_del(&nc_packet->list);
598 batadv_nc_packet_free(nc_packet);
599
600 res = true;
601
602out:
603 return res;
604}
605
606/**
Martin Hundebøll95332472013-01-25 11:12:40 +0100607 * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet.
608 * @bat_priv: the bat priv with all the soft interface information
609 * @nc_path: the nc path the packet belongs to
610 * @nc_packet: the nc packet to be checked
611 *
612 * Checks whether the given nc packet has hit its forward timeout. If so, the
613 * packet is no longer delayed, immediately sent and the entry deleted from the
614 * queue. Has to be called with the appropriate locks.
615 *
616 * Returns false as soon as the entry in the fifo queue has not been timed out
617 * yet and true otherwise.
618 */
619static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv,
620 struct batadv_nc_path *nc_path,
621 struct batadv_nc_packet *nc_packet)
622{
623 unsigned long timeout = bat_priv->nc.max_fwd_delay;
624
625 /* Packets are added to tail, so the remaining packets did not time
626 * out and we can stop processing the current queue
627 */
628 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
629 !batadv_has_timed_out(nc_packet->timestamp, timeout))
630 return false;
631
632 /* Send packet */
633 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
634 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
635 nc_packet->skb->len + ETH_HLEN);
636 list_del(&nc_packet->list);
637 batadv_nc_send_packet(nc_packet);
638
639 return true;
640}
641
642/**
643 * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out
644 * nc packets
645 * @bat_priv: the bat priv with all the soft interface information
646 * @hash: to be processed hash table
647 * @process_fn: Function called to process given nc packet. Should return true
648 * to encourage this function to proceed with the next packet.
649 * Otherwise the rest of the current queue is skipped.
650 */
651static void
652batadv_nc_process_nc_paths(struct batadv_priv *bat_priv,
653 struct batadv_hashtable *hash,
654 bool (*process_fn)(struct batadv_priv *,
655 struct batadv_nc_path *,
656 struct batadv_nc_packet *))
657{
658 struct hlist_head *head;
659 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
660 struct batadv_nc_path *nc_path;
661 bool ret;
662 int i;
663
664 if (!hash)
665 return;
666
667 /* Loop hash table bins */
668 for (i = 0; i < hash->size; i++) {
669 head = &hash->table[i];
670
671 /* Loop coding paths */
672 rcu_read_lock();
673 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
674 /* Loop packets */
675 spin_lock_bh(&nc_path->packet_list_lock);
676 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
677 &nc_path->packet_list, list) {
678 ret = process_fn(bat_priv, nc_path, nc_packet);
679 if (!ret)
680 break;
681 }
682 spin_unlock_bh(&nc_path->packet_list_lock);
683 }
684 rcu_read_unlock();
685 }
686}
687
688/**
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100689 * batadv_nc_worker - periodic task for house keeping related to network coding
690 * @work: kernel work struct
691 */
692static void batadv_nc_worker(struct work_struct *work)
693{
694 struct delayed_work *delayed_work;
695 struct batadv_priv_nc *priv_nc;
696 struct batadv_priv *bat_priv;
Martin Hundebøll95332472013-01-25 11:12:40 +0100697 unsigned long timeout;
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100698
699 delayed_work = container_of(work, struct delayed_work, work);
700 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
701 bat_priv = container_of(priv_nc, struct batadv_priv, nc);
702
Martin Hundebølld56b1702013-01-25 11:12:39 +0100703 batadv_nc_purge_orig_hash(bat_priv);
Martin Hundebøll95332472013-01-25 11:12:40 +0100704 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash,
705 batadv_nc_to_purge_nc_path_coding);
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100706 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash,
707 batadv_nc_to_purge_nc_path_decoding);
Martin Hundebøll95332472013-01-25 11:12:40 +0100708
709 timeout = bat_priv->nc.max_fwd_delay;
710
711 if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) {
712 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash,
713 batadv_nc_fwd_flush);
714 bat_priv->nc.timestamp_fwd_flush = jiffies;
715 }
Martin Hundebølld56b1702013-01-25 11:12:39 +0100716
Martin Hundebøll612d2b42013-01-25 11:12:42 +0100717 if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge,
718 bat_priv->nc.max_buffer_time)) {
719 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash,
720 batadv_nc_sniffed_purge);
721 bat_priv->nc.timestamp_sniffed_purge = jiffies;
722 }
723
Martin Hundebølld353d8d2013-01-25 11:12:38 +0100724 /* Schedule a new check */
725 batadv_nc_start_timer(bat_priv);
726}
727
728/**
Martin Hundebølld56b1702013-01-25 11:12:39 +0100729 * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
730 * coding or not
731 * @bat_priv: the bat priv with all the soft interface information
732 * @orig_node: neighboring orig node which may be used as nc candidate
733 * @ogm_packet: incoming ogm packet also used for the checks
734 *
735 * Returns true if:
736 * 1) The OGM must have the most recent sequence number.
737 * 2) The TTL must be decremented by one and only one.
738 * 3) The OGM must be received from the first hop from orig_node.
739 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
740 */
741static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
742 struct batadv_orig_node *orig_node,
743 struct batadv_ogm_packet *ogm_packet)
744{
Simon Wunderlich7351a4822013-11-13 19:14:47 +0100745 struct batadv_orig_ifinfo *orig_ifinfo;
746 uint32_t last_real_seqno;
747 uint8_t last_ttl;
748
749 orig_ifinfo = batadv_orig_ifinfo_get(orig_node, BATADV_IF_DEFAULT);
750 if (!orig_ifinfo)
Martin Hundebølld56b1702013-01-25 11:12:39 +0100751 return false;
Simon Wunderlich7351a4822013-11-13 19:14:47 +0100752
753 last_ttl = orig_ifinfo->last_ttl;
754 last_real_seqno = orig_ifinfo->last_real_seqno;
755 batadv_orig_ifinfo_free_ref(orig_ifinfo);
756
757 if (last_real_seqno != ntohl(ogm_packet->seqno))
758 return false;
759 if (last_ttl != ogm_packet->ttl + 1)
Martin Hundebølld56b1702013-01-25 11:12:39 +0100760 return false;
761 if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
762 return false;
763 if (ogm_packet->tq < bat_priv->nc.min_tq)
764 return false;
765
766 return true;
767}
768
769/**
770 * batadv_nc_find_nc_node - search for an existing nc node and return it
771 * @orig_node: orig node originating the ogm packet
772 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
773 * (can be equal to orig_node)
774 * @in_coding: traverse incoming or outgoing network coding list
775 *
776 * Returns the nc_node if found, NULL otherwise.
777 */
778static struct batadv_nc_node
779*batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
780 struct batadv_orig_node *orig_neigh_node,
781 bool in_coding)
782{
783 struct batadv_nc_node *nc_node, *nc_node_out = NULL;
784 struct list_head *list;
785
786 if (in_coding)
787 list = &orig_neigh_node->in_coding_list;
788 else
789 list = &orig_neigh_node->out_coding_list;
790
791 /* Traverse list of nc_nodes to orig_node */
792 rcu_read_lock();
793 list_for_each_entry_rcu(nc_node, list, list) {
794 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
795 continue;
796
797 if (!atomic_inc_not_zero(&nc_node->refcount))
798 continue;
799
800 /* Found a match */
801 nc_node_out = nc_node;
802 break;
803 }
804 rcu_read_unlock();
805
806 return nc_node_out;
807}
808
809/**
810 * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
811 * not found
812 * @bat_priv: the bat priv with all the soft interface information
813 * @orig_node: orig node originating the ogm packet
814 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
815 * (can be equal to orig_node)
816 * @in_coding: traverse incoming or outgoing network coding list
817 *
818 * Returns the nc_node if found or created, NULL in case of an error.
819 */
820static struct batadv_nc_node
821*batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
822 struct batadv_orig_node *orig_node,
823 struct batadv_orig_node *orig_neigh_node,
824 bool in_coding)
825{
826 struct batadv_nc_node *nc_node;
827 spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
828 struct list_head *list;
829
830 /* Check if nc_node is already added */
831 nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
832
833 /* Node found */
834 if (nc_node)
835 return nc_node;
836
837 nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
838 if (!nc_node)
839 return NULL;
840
841 if (!atomic_inc_not_zero(&orig_neigh_node->refcount))
842 goto free;
843
844 /* Initialize nc_node */
845 INIT_LIST_HEAD(&nc_node->list);
Antonio Quartulli8fdd0152014-01-22 00:42:11 +0100846 ether_addr_copy(nc_node->addr, orig_node->orig);
Martin Hundebølld56b1702013-01-25 11:12:39 +0100847 nc_node->orig_node = orig_neigh_node;
848 atomic_set(&nc_node->refcount, 2);
849
850 /* Select ingoing or outgoing coding node */
851 if (in_coding) {
852 lock = &orig_neigh_node->in_coding_list_lock;
853 list = &orig_neigh_node->in_coding_list;
854 } else {
855 lock = &orig_neigh_node->out_coding_list_lock;
856 list = &orig_neigh_node->out_coding_list;
857 }
858
859 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
860 nc_node->addr, nc_node->orig_node->orig);
861
862 /* Add nc_node to orig_node */
863 spin_lock_bh(lock);
864 list_add_tail_rcu(&nc_node->list, list);
865 spin_unlock_bh(lock);
866
867 return nc_node;
868
869free:
870 kfree(nc_node);
871 return NULL;
872}
873
874/**
875 * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs
876 * (best called on incoming OGMs)
877 * @bat_priv: the bat priv with all the soft interface information
878 * @orig_node: orig node originating the ogm packet
879 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
880 * (can be equal to orig_node)
881 * @ogm_packet: incoming ogm packet
882 * @is_single_hop_neigh: orig_node is a single hop neighbor
883 */
884void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
885 struct batadv_orig_node *orig_node,
886 struct batadv_orig_node *orig_neigh_node,
887 struct batadv_ogm_packet *ogm_packet,
888 int is_single_hop_neigh)
889{
890 struct batadv_nc_node *in_nc_node = NULL, *out_nc_node = NULL;
891
892 /* Check if network coding is enabled */
893 if (!atomic_read(&bat_priv->network_coding))
894 goto out;
895
Marek Lindner3f4841f2013-04-23 21:40:00 +0800896 /* check if orig node is network coding enabled */
897 if (!(orig_node->capabilities & BATADV_ORIG_CAPA_HAS_NC))
898 goto out;
899
Martin Hundebølld56b1702013-01-25 11:12:39 +0100900 /* accept ogms from 'good' neighbors and single hop neighbors */
901 if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
902 !is_single_hop_neigh)
903 goto out;
904
905 /* Add orig_node as in_nc_node on hop */
906 in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
907 orig_neigh_node, true);
908 if (!in_nc_node)
909 goto out;
910
911 in_nc_node->last_seen = jiffies;
912
913 /* Add hop as out_nc_node on orig_node */
914 out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
915 orig_node, false);
916 if (!out_nc_node)
917 goto out;
918
919 out_nc_node->last_seen = jiffies;
920
921out:
922 if (in_nc_node)
923 batadv_nc_node_free_ref(in_nc_node);
924 if (out_nc_node)
925 batadv_nc_node_free_ref(out_nc_node);
926}
927
928/**
Martin Hundebøll95332472013-01-25 11:12:40 +0100929 * batadv_nc_get_path - get existing nc_path or allocate a new one
930 * @bat_priv: the bat priv with all the soft interface information
931 * @hash: hash table containing the nc path
932 * @src: ethernet source address - first half of the nc path search key
933 * @dst: ethernet destination address - second half of the nc path search key
934 *
935 * Returns pointer to nc_path if the path was found or created, returns NULL
936 * on error.
937 */
938static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
939 struct batadv_hashtable *hash,
940 uint8_t *src,
941 uint8_t *dst)
942{
943 int hash_added;
944 struct batadv_nc_path *nc_path, nc_path_key;
945
946 batadv_nc_hash_key_gen(&nc_path_key, src, dst);
947
948 /* Search for existing nc_path */
949 nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key);
950
951 if (nc_path) {
952 /* Set timestamp to delay removal of nc_path */
953 nc_path->last_valid = jiffies;
954 return nc_path;
955 }
956
957 /* No existing nc_path was found; create a new */
958 nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC);
959
960 if (!nc_path)
961 return NULL;
962
963 /* Initialize nc_path */
964 INIT_LIST_HEAD(&nc_path->packet_list);
965 spin_lock_init(&nc_path->packet_list_lock);
966 atomic_set(&nc_path->refcount, 2);
967 nc_path->last_valid = jiffies;
Antonio Quartulli8fdd0152014-01-22 00:42:11 +0100968 ether_addr_copy(nc_path->next_hop, dst);
969 ether_addr_copy(nc_path->prev_hop, src);
Martin Hundebøll95332472013-01-25 11:12:40 +0100970
971 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n",
972 nc_path->prev_hop,
973 nc_path->next_hop);
974
975 /* Add nc_path to hash table */
976 hash_added = batadv_hash_add(hash, batadv_nc_hash_compare,
977 batadv_nc_hash_choose, &nc_path_key,
978 &nc_path->hash_entry);
979
980 if (hash_added < 0) {
981 kfree(nc_path);
982 return NULL;
983 }
984
985 return nc_path;
986}
987
988/**
Martin Hundebøll3c12de92013-01-25 11:12:41 +0100989 * batadv_nc_random_weight_tq - scale the receivers TQ-value to avoid unfair
990 * selection of a receiver with slightly lower TQ than the other
991 * @tq: to be weighted tq value
992 */
993static uint8_t batadv_nc_random_weight_tq(uint8_t tq)
994{
995 uint8_t rand_val, rand_tq;
996
997 get_random_bytes(&rand_val, sizeof(rand_val));
998
999 /* randomize the estimated packet loss (max TQ - estimated TQ) */
1000 rand_tq = rand_val * (BATADV_TQ_MAX_VALUE - tq);
1001
1002 /* normalize the randomized packet loss */
1003 rand_tq /= BATADV_TQ_MAX_VALUE;
1004
1005 /* convert to (randomized) estimated tq again */
1006 return BATADV_TQ_MAX_VALUE - rand_tq;
1007}
1008
1009/**
1010 * batadv_nc_memxor - XOR destination with source
1011 * @dst: byte array to XOR into
1012 * @src: byte array to XOR from
1013 * @len: length of destination array
1014 */
1015static void batadv_nc_memxor(char *dst, const char *src, unsigned int len)
1016{
1017 unsigned int i;
1018
1019 for (i = 0; i < len; ++i)
1020 dst[i] ^= src[i];
1021}
1022
1023/**
1024 * batadv_nc_code_packets - code a received unicast_packet with an nc packet
1025 * into a coded_packet and send it
1026 * @bat_priv: the bat priv with all the soft interface information
1027 * @skb: data skb to forward
1028 * @ethhdr: pointer to the ethernet header inside the skb
1029 * @nc_packet: structure containing the packet to the skb can be coded with
1030 * @neigh_node: next hop to forward packet to
1031 *
1032 * Returns true if both packets are consumed, false otherwise.
1033 */
1034static bool batadv_nc_code_packets(struct batadv_priv *bat_priv,
1035 struct sk_buff *skb,
1036 struct ethhdr *ethhdr,
1037 struct batadv_nc_packet *nc_packet,
1038 struct batadv_neigh_node *neigh_node)
1039{
Antonio Quartulli0538f752013-09-02 12:15:01 +02001040 uint8_t tq_weighted_neigh, tq_weighted_coding, tq_tmp;
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001041 struct sk_buff *skb_dest, *skb_src;
1042 struct batadv_unicast_packet *packet1;
1043 struct batadv_unicast_packet *packet2;
1044 struct batadv_coded_packet *coded_packet;
1045 struct batadv_neigh_node *neigh_tmp, *router_neigh;
1046 struct batadv_neigh_node *router_coding = NULL;
Simon Wunderlich89652332013-11-13 19:14:46 +01001047 struct batadv_neigh_ifinfo *router_neigh_ifinfo = NULL;
1048 struct batadv_neigh_ifinfo *router_coding_ifinfo = NULL;
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001049 uint8_t *first_source, *first_dest, *second_source, *second_dest;
1050 __be32 packet_id1, packet_id2;
1051 size_t count;
1052 bool res = false;
1053 int coding_len;
1054 int unicast_size = sizeof(*packet1);
1055 int coded_size = sizeof(*coded_packet);
1056 int header_add = coded_size - unicast_size;
1057
Simon Wunderlich7351a4822013-11-13 19:14:47 +01001058 /* TODO: do we need to consider the outgoing interface for
1059 * coded packets?
1060 */
1061 router_neigh = batadv_orig_router_get(neigh_node->orig_node,
1062 BATADV_IF_DEFAULT);
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001063 if (!router_neigh)
1064 goto out;
1065
Simon Wunderlich89652332013-11-13 19:14:46 +01001066 router_neigh_ifinfo = batadv_neigh_ifinfo_get(router_neigh,
1067 BATADV_IF_DEFAULT);
1068 if (!router_neigh_ifinfo)
1069 goto out;
1070
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001071 neigh_tmp = nc_packet->neigh_node;
Simon Wunderlich7351a4822013-11-13 19:14:47 +01001072 router_coding = batadv_orig_router_get(neigh_tmp->orig_node,
1073 BATADV_IF_DEFAULT);
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001074 if (!router_coding)
1075 goto out;
1076
Simon Wunderlich89652332013-11-13 19:14:46 +01001077 router_coding_ifinfo = batadv_neigh_ifinfo_get(router_coding,
1078 BATADV_IF_DEFAULT);
1079 if (!router_coding_ifinfo)
1080 goto out;
1081
1082 tq_tmp = router_neigh_ifinfo->bat_iv.tq_avg;
1083 tq_weighted_neigh = batadv_nc_random_weight_tq(tq_tmp);
1084 tq_tmp = router_coding_ifinfo->bat_iv.tq_avg;
1085 tq_weighted_coding = batadv_nc_random_weight_tq(tq_tmp);
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001086
1087 /* Select one destination for the MAC-header dst-field based on
1088 * weighted TQ-values.
1089 */
1090 if (tq_weighted_neigh >= tq_weighted_coding) {
1091 /* Destination from nc_packet is selected for MAC-header */
1092 first_dest = nc_packet->nc_path->next_hop;
1093 first_source = nc_packet->nc_path->prev_hop;
1094 second_dest = neigh_node->addr;
1095 second_source = ethhdr->h_source;
1096 packet1 = (struct batadv_unicast_packet *)nc_packet->skb->data;
1097 packet2 = (struct batadv_unicast_packet *)skb->data;
1098 packet_id1 = nc_packet->packet_id;
1099 packet_id2 = batadv_skb_crc32(skb,
1100 skb->data + sizeof(*packet2));
1101 } else {
1102 /* Destination for skb is selected for MAC-header */
1103 first_dest = neigh_node->addr;
1104 first_source = ethhdr->h_source;
1105 second_dest = nc_packet->nc_path->next_hop;
1106 second_source = nc_packet->nc_path->prev_hop;
1107 packet1 = (struct batadv_unicast_packet *)skb->data;
1108 packet2 = (struct batadv_unicast_packet *)nc_packet->skb->data;
1109 packet_id1 = batadv_skb_crc32(skb,
1110 skb->data + sizeof(*packet1));
1111 packet_id2 = nc_packet->packet_id;
1112 }
1113
1114 /* Instead of zero padding the smallest data buffer, we
1115 * code into the largest.
1116 */
1117 if (skb->len <= nc_packet->skb->len) {
1118 skb_dest = nc_packet->skb;
1119 skb_src = skb;
1120 } else {
1121 skb_dest = skb;
1122 skb_src = nc_packet->skb;
1123 }
1124
1125 /* coding_len is used when decoding the packet shorter packet */
1126 coding_len = skb_src->len - unicast_size;
1127
1128 if (skb_linearize(skb_dest) < 0 || skb_linearize(skb_src) < 0)
1129 goto out;
1130
1131 skb_push(skb_dest, header_add);
1132
1133 coded_packet = (struct batadv_coded_packet *)skb_dest->data;
1134 skb_reset_mac_header(skb_dest);
1135
Simon Wunderlicha40d9b02013-12-02 20:38:31 +01001136 coded_packet->packet_type = BATADV_CODED;
1137 coded_packet->version = BATADV_COMPAT_VERSION;
1138 coded_packet->ttl = packet1->ttl;
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001139
1140 /* Info about first unicast packet */
Antonio Quartulli8fdd0152014-01-22 00:42:11 +01001141 ether_addr_copy(coded_packet->first_source, first_source);
1142 ether_addr_copy(coded_packet->first_orig_dest, packet1->dest);
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001143 coded_packet->first_crc = packet_id1;
1144 coded_packet->first_ttvn = packet1->ttvn;
1145
1146 /* Info about second unicast packet */
Antonio Quartulli8fdd0152014-01-22 00:42:11 +01001147 ether_addr_copy(coded_packet->second_dest, second_dest);
1148 ether_addr_copy(coded_packet->second_source, second_source);
1149 ether_addr_copy(coded_packet->second_orig_dest, packet2->dest);
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001150 coded_packet->second_crc = packet_id2;
Simon Wunderlicha40d9b02013-12-02 20:38:31 +01001151 coded_packet->second_ttl = packet2->ttl;
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001152 coded_packet->second_ttvn = packet2->ttvn;
1153 coded_packet->coded_len = htons(coding_len);
1154
1155 /* This is where the magic happens: Code skb_src into skb_dest */
1156 batadv_nc_memxor(skb_dest->data + coded_size,
1157 skb_src->data + unicast_size, coding_len);
1158
1159 /* Update counters accordingly */
1160 if (BATADV_SKB_CB(skb_src)->decoded &&
1161 BATADV_SKB_CB(skb_dest)->decoded) {
1162 /* Both packets are recoded */
1163 count = skb_src->len + ETH_HLEN;
1164 count += skb_dest->len + ETH_HLEN;
1165 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE, 2);
1166 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES, count);
1167 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1168 !BATADV_SKB_CB(skb_dest)->decoded) {
1169 /* Both packets are newly coded */
1170 count = skb_src->len + ETH_HLEN;
1171 count += skb_dest->len + ETH_HLEN;
1172 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE, 2);
1173 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES, count);
1174 } else if (BATADV_SKB_CB(skb_src)->decoded &&
1175 !BATADV_SKB_CB(skb_dest)->decoded) {
1176 /* skb_src recoded and skb_dest is newly coded */
1177 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1178 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1179 skb_src->len + ETH_HLEN);
1180 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1181 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1182 skb_dest->len + ETH_HLEN);
1183 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1184 BATADV_SKB_CB(skb_dest)->decoded) {
1185 /* skb_src is newly coded and skb_dest is recoded */
1186 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1187 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1188 skb_src->len + ETH_HLEN);
1189 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1190 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1191 skb_dest->len + ETH_HLEN);
1192 }
1193
1194 /* skb_src is now coded into skb_dest, so free it */
1195 kfree_skb(skb_src);
1196
1197 /* avoid duplicate free of skb from nc_packet */
1198 nc_packet->skb = NULL;
1199 batadv_nc_packet_free(nc_packet);
1200
1201 /* Send the coded packet and return true */
1202 batadv_send_skb_packet(skb_dest, neigh_node->if_incoming, first_dest);
1203 res = true;
1204out:
1205 if (router_neigh)
1206 batadv_neigh_node_free_ref(router_neigh);
1207 if (router_coding)
1208 batadv_neigh_node_free_ref(router_coding);
Simon Wunderlich89652332013-11-13 19:14:46 +01001209 if (router_neigh_ifinfo)
1210 batadv_neigh_ifinfo_free_ref(router_neigh_ifinfo);
1211 if (router_coding_ifinfo)
1212 batadv_neigh_ifinfo_free_ref(router_coding_ifinfo);
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001213 return res;
1214}
1215
1216/**
1217 * batadv_nc_skb_coding_possible - true if a decoded skb is available at dst.
1218 * @skb: data skb to forward
1219 * @dst: destination mac address of the other skb to code with
1220 * @src: source mac address of skb
1221 *
1222 * Whenever we network code a packet we have to check whether we received it in
1223 * a network coded form. If so, we may not be able to use it for coding because
1224 * some neighbors may also have received (overheard) the packet in the network
1225 * coded form without being able to decode it. It is hard to know which of the
1226 * neighboring nodes was able to decode the packet, therefore we can only
1227 * re-code the packet if the source of the previous encoded packet is involved.
1228 * Since the source encoded the packet we can be certain it has all necessary
1229 * decode information.
1230 *
1231 * Returns true if coding of a decoded packet is allowed.
1232 */
1233static bool batadv_nc_skb_coding_possible(struct sk_buff *skb,
1234 uint8_t *dst, uint8_t *src)
1235{
1236 if (BATADV_SKB_CB(skb)->decoded && !batadv_compare_eth(dst, src))
1237 return false;
Antonio Quartulli24820df2014-09-01 14:37:25 +02001238 return true;
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001239}
1240
1241/**
1242 * batadv_nc_path_search - Find the coding path matching in_nc_node and
1243 * out_nc_node to retrieve a buffered packet that can be used for coding.
1244 * @bat_priv: the bat priv with all the soft interface information
1245 * @in_nc_node: pointer to skb next hop's neighbor nc node
1246 * @out_nc_node: pointer to skb source's neighbor nc node
1247 * @skb: data skb to forward
1248 * @eth_dst: next hop mac address of skb
1249 *
1250 * Returns true if coding of a decoded skb is allowed.
1251 */
1252static struct batadv_nc_packet *
1253batadv_nc_path_search(struct batadv_priv *bat_priv,
1254 struct batadv_nc_node *in_nc_node,
1255 struct batadv_nc_node *out_nc_node,
1256 struct sk_buff *skb,
1257 uint8_t *eth_dst)
1258{
1259 struct batadv_nc_path *nc_path, nc_path_key;
1260 struct batadv_nc_packet *nc_packet_out = NULL;
1261 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
1262 struct batadv_hashtable *hash = bat_priv->nc.coding_hash;
1263 int idx;
1264
1265 if (!hash)
1266 return NULL;
1267
1268 /* Create almost path key */
1269 batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr,
1270 out_nc_node->addr);
1271 idx = batadv_nc_hash_choose(&nc_path_key, hash->size);
1272
1273 /* Check for coding opportunities in this nc_path */
1274 rcu_read_lock();
1275 hlist_for_each_entry_rcu(nc_path, &hash->table[idx], hash_entry) {
1276 if (!batadv_compare_eth(nc_path->prev_hop, in_nc_node->addr))
1277 continue;
1278
1279 if (!batadv_compare_eth(nc_path->next_hop, out_nc_node->addr))
1280 continue;
1281
1282 spin_lock_bh(&nc_path->packet_list_lock);
1283 if (list_empty(&nc_path->packet_list)) {
1284 spin_unlock_bh(&nc_path->packet_list_lock);
1285 continue;
1286 }
1287
1288 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
1289 &nc_path->packet_list, list) {
1290 if (!batadv_nc_skb_coding_possible(nc_packet->skb,
1291 eth_dst,
1292 in_nc_node->addr))
1293 continue;
1294
1295 /* Coding opportunity is found! */
1296 list_del(&nc_packet->list);
1297 nc_packet_out = nc_packet;
1298 break;
1299 }
1300
1301 spin_unlock_bh(&nc_path->packet_list_lock);
1302 break;
1303 }
1304 rcu_read_unlock();
1305
1306 return nc_packet_out;
1307}
1308
1309/**
1310 * batadv_nc_skb_src_search - Loops through the list of neighoring nodes of the
1311 * skb's sender (may be equal to the originator).
1312 * @bat_priv: the bat priv with all the soft interface information
1313 * @skb: data skb to forward
1314 * @eth_dst: next hop mac address of skb
1315 * @eth_src: source mac address of skb
1316 * @in_nc_node: pointer to skb next hop's neighbor nc node
1317 *
1318 * Returns an nc packet if a suitable coding packet was found, NULL otherwise.
1319 */
1320static struct batadv_nc_packet *
1321batadv_nc_skb_src_search(struct batadv_priv *bat_priv,
1322 struct sk_buff *skb,
1323 uint8_t *eth_dst,
1324 uint8_t *eth_src,
1325 struct batadv_nc_node *in_nc_node)
1326{
1327 struct batadv_orig_node *orig_node;
1328 struct batadv_nc_node *out_nc_node;
1329 struct batadv_nc_packet *nc_packet = NULL;
1330
1331 orig_node = batadv_orig_hash_find(bat_priv, eth_src);
1332 if (!orig_node)
1333 return NULL;
1334
1335 rcu_read_lock();
1336 list_for_each_entry_rcu(out_nc_node,
1337 &orig_node->out_coding_list, list) {
1338 /* Check if the skb is decoded and if recoding is possible */
1339 if (!batadv_nc_skb_coding_possible(skb,
1340 out_nc_node->addr, eth_src))
1341 continue;
1342
1343 /* Search for an opportunity in this nc_path */
1344 nc_packet = batadv_nc_path_search(bat_priv, in_nc_node,
1345 out_nc_node, skb, eth_dst);
1346 if (nc_packet)
1347 break;
1348 }
1349 rcu_read_unlock();
1350
1351 batadv_orig_node_free_ref(orig_node);
1352 return nc_packet;
1353}
1354
1355/**
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001356 * batadv_nc_skb_store_before_coding - set the ethernet src and dst of the
1357 * unicast skb before it is stored for use in later decoding
1358 * @bat_priv: the bat priv with all the soft interface information
1359 * @skb: data skb to store
1360 * @eth_dst_new: new destination mac address of skb
1361 */
1362static void batadv_nc_skb_store_before_coding(struct batadv_priv *bat_priv,
1363 struct sk_buff *skb,
1364 uint8_t *eth_dst_new)
1365{
1366 struct ethhdr *ethhdr;
1367
1368 /* Copy skb header to change the mac header */
Octavian Purdilabad93e92014-06-12 01:36:26 +03001369 skb = pskb_copy_for_clone(skb, GFP_ATOMIC);
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001370 if (!skb)
1371 return;
1372
1373 /* Set the mac header as if we actually sent the packet uncoded */
Antonio Quartulli7ed4be92013-04-08 15:08:18 +02001374 ethhdr = eth_hdr(skb);
Antonio Quartulli8fdd0152014-01-22 00:42:11 +01001375 ether_addr_copy(ethhdr->h_source, ethhdr->h_dest);
1376 ether_addr_copy(ethhdr->h_dest, eth_dst_new);
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001377
1378 /* Set data pointer to MAC header to mimic packets from our tx path */
1379 skb_push(skb, ETH_HLEN);
1380
1381 /* Add the packet to the decoding packet pool */
1382 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1383
1384 /* batadv_nc_skb_store_for_decoding() clones the skb, so we must free
1385 * our ref
1386 */
1387 kfree_skb(skb);
1388}
1389
1390/**
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001391 * batadv_nc_skb_dst_search - Loops through list of neighboring nodes to dst.
1392 * @skb: data skb to forward
1393 * @neigh_node: next hop to forward packet to
1394 * @ethhdr: pointer to the ethernet header inside the skb
1395 *
1396 * Loops through list of neighboring nodes the next hop has a good connection to
1397 * (receives OGMs with a sufficient quality). We need to find a neighbor of our
1398 * next hop that potentially sent a packet which our next hop also received
1399 * (overheard) and has stored for later decoding.
1400 *
1401 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1402 */
1403static bool batadv_nc_skb_dst_search(struct sk_buff *skb,
1404 struct batadv_neigh_node *neigh_node,
1405 struct ethhdr *ethhdr)
1406{
1407 struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1408 struct batadv_priv *bat_priv = netdev_priv(netdev);
1409 struct batadv_orig_node *orig_node = neigh_node->orig_node;
1410 struct batadv_nc_node *nc_node;
1411 struct batadv_nc_packet *nc_packet = NULL;
1412
1413 rcu_read_lock();
1414 list_for_each_entry_rcu(nc_node, &orig_node->in_coding_list, list) {
1415 /* Search for coding opportunity with this in_nc_node */
1416 nc_packet = batadv_nc_skb_src_search(bat_priv, skb,
1417 neigh_node->addr,
1418 ethhdr->h_source, nc_node);
1419
1420 /* Opportunity was found, so stop searching */
1421 if (nc_packet)
1422 break;
1423 }
1424 rcu_read_unlock();
1425
1426 if (!nc_packet)
1427 return false;
1428
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001429 /* Save packets for later decoding */
1430 batadv_nc_skb_store_before_coding(bat_priv, skb,
1431 neigh_node->addr);
1432 batadv_nc_skb_store_before_coding(bat_priv, nc_packet->skb,
1433 nc_packet->neigh_node->addr);
1434
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001435 /* Code and send packets */
1436 if (batadv_nc_code_packets(bat_priv, skb, ethhdr, nc_packet,
1437 neigh_node))
1438 return true;
1439
1440 /* out of mem ? Coding failed - we have to free the buffered packet
1441 * to avoid memleaks. The skb passed as argument will be dealt with
1442 * by the calling function.
1443 */
1444 batadv_nc_send_packet(nc_packet);
1445 return false;
1446}
1447
1448/**
Martin Hundebøll95332472013-01-25 11:12:40 +01001449 * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding
1450 * @skb: skb to add to path
1451 * @nc_path: path to add skb to
1452 * @neigh_node: next hop to forward packet to
1453 * @packet_id: checksum to identify packet
1454 *
1455 * Returns true if the packet was buffered or false in case of an error.
1456 */
1457static bool batadv_nc_skb_add_to_path(struct sk_buff *skb,
1458 struct batadv_nc_path *nc_path,
1459 struct batadv_neigh_node *neigh_node,
1460 __be32 packet_id)
1461{
1462 struct batadv_nc_packet *nc_packet;
1463
1464 nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC);
1465 if (!nc_packet)
1466 return false;
1467
1468 /* Initialize nc_packet */
1469 nc_packet->timestamp = jiffies;
1470 nc_packet->packet_id = packet_id;
1471 nc_packet->skb = skb;
1472 nc_packet->neigh_node = neigh_node;
1473 nc_packet->nc_path = nc_path;
1474
1475 /* Add coding packet to list */
1476 spin_lock_bh(&nc_path->packet_list_lock);
1477 list_add_tail(&nc_packet->list, &nc_path->packet_list);
1478 spin_unlock_bh(&nc_path->packet_list_lock);
1479
1480 return true;
1481}
1482
1483/**
1484 * batadv_nc_skb_forward - try to code a packet or add it to the coding packet
1485 * buffer
1486 * @skb: data skb to forward
1487 * @neigh_node: next hop to forward packet to
Martin Hundebøll95332472013-01-25 11:12:40 +01001488 *
1489 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1490 */
1491bool batadv_nc_skb_forward(struct sk_buff *skb,
Martin Hundebølle91ecfc2013-04-20 13:54:39 +02001492 struct batadv_neigh_node *neigh_node)
Martin Hundebøll95332472013-01-25 11:12:40 +01001493{
1494 const struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1495 struct batadv_priv *bat_priv = netdev_priv(netdev);
1496 struct batadv_unicast_packet *packet;
1497 struct batadv_nc_path *nc_path;
Martin Hundebølle91ecfc2013-04-20 13:54:39 +02001498 struct ethhdr *ethhdr = eth_hdr(skb);
Martin Hundebøll95332472013-01-25 11:12:40 +01001499 __be32 packet_id;
1500 u8 *payload;
1501
1502 /* Check if network coding is enabled */
1503 if (!atomic_read(&bat_priv->network_coding))
1504 goto out;
1505
1506 /* We only handle unicast packets */
1507 payload = skb_network_header(skb);
1508 packet = (struct batadv_unicast_packet *)payload;
Simon Wunderlicha40d9b02013-12-02 20:38:31 +01001509 if (packet->packet_type != BATADV_UNICAST)
Martin Hundebøll95332472013-01-25 11:12:40 +01001510 goto out;
1511
Martin Hundebøll3c12de92013-01-25 11:12:41 +01001512 /* Try to find a coding opportunity and send the skb if one is found */
1513 if (batadv_nc_skb_dst_search(skb, neigh_node, ethhdr))
1514 return true;
1515
Martin Hundebøll95332472013-01-25 11:12:40 +01001516 /* Find or create a nc_path for this src-dst pair */
1517 nc_path = batadv_nc_get_path(bat_priv,
1518 bat_priv->nc.coding_hash,
1519 ethhdr->h_source,
1520 neigh_node->addr);
1521
1522 if (!nc_path)
1523 goto out;
1524
1525 /* Add skb to nc_path */
1526 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1527 if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id))
1528 goto free_nc_path;
1529
1530 /* Packet is consumed */
1531 return true;
1532
1533free_nc_path:
1534 batadv_nc_path_free_ref(nc_path);
1535out:
1536 /* Packet is not consumed */
1537 return false;
1538}
1539
1540/**
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001541 * batadv_nc_skb_store_for_decoding - save a clone of the skb which can be used
1542 * when decoding coded packets
1543 * @bat_priv: the bat priv with all the soft interface information
1544 * @skb: data skb to store
1545 */
1546void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
1547 struct sk_buff *skb)
1548{
1549 struct batadv_unicast_packet *packet;
1550 struct batadv_nc_path *nc_path;
Antonio Quartulli7ed4be92013-04-08 15:08:18 +02001551 struct ethhdr *ethhdr = eth_hdr(skb);
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001552 __be32 packet_id;
1553 u8 *payload;
1554
1555 /* Check if network coding is enabled */
1556 if (!atomic_read(&bat_priv->network_coding))
1557 goto out;
1558
1559 /* Check for supported packet type */
1560 payload = skb_network_header(skb);
1561 packet = (struct batadv_unicast_packet *)payload;
Simon Wunderlicha40d9b02013-12-02 20:38:31 +01001562 if (packet->packet_type != BATADV_UNICAST)
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001563 goto out;
1564
1565 /* Find existing nc_path or create a new */
1566 nc_path = batadv_nc_get_path(bat_priv,
1567 bat_priv->nc.decoding_hash,
1568 ethhdr->h_source,
1569 ethhdr->h_dest);
1570
1571 if (!nc_path)
1572 goto out;
1573
1574 /* Clone skb and adjust skb->data to point at batman header */
1575 skb = skb_clone(skb, GFP_ATOMIC);
1576 if (unlikely(!skb))
1577 goto free_nc_path;
1578
1579 if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
1580 goto free_skb;
1581
1582 if (unlikely(!skb_pull_rcsum(skb, ETH_HLEN)))
1583 goto free_skb;
1584
1585 /* Add skb to nc_path */
1586 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1587 if (!batadv_nc_skb_add_to_path(skb, nc_path, NULL, packet_id))
1588 goto free_skb;
1589
1590 batadv_inc_counter(bat_priv, BATADV_CNT_NC_BUFFER);
1591 return;
1592
1593free_skb:
1594 kfree_skb(skb);
1595free_nc_path:
1596 batadv_nc_path_free_ref(nc_path);
1597out:
1598 return;
1599}
1600
1601/**
1602 * batadv_nc_skb_store_sniffed_unicast - check if a received unicast packet
1603 * should be saved in the decoding buffer and, if so, store it there
1604 * @bat_priv: the bat priv with all the soft interface information
1605 * @skb: unicast skb to store
1606 */
1607void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
1608 struct sk_buff *skb)
1609{
Antonio Quartulli7ed4be92013-04-08 15:08:18 +02001610 struct ethhdr *ethhdr = eth_hdr(skb);
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001611
David S. Miller6e0895c2013-04-22 20:32:51 -04001612 if (batadv_is_my_mac(bat_priv, ethhdr->h_dest))
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001613 return;
1614
1615 /* Set data pointer to MAC header to mimic packets from our tx path */
1616 skb_push(skb, ETH_HLEN);
1617
1618 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1619}
1620
1621/**
Martin Hundebøll2df52782013-01-25 11:12:43 +01001622 * batadv_nc_skb_decode_packet - decode given skb using the decode data stored
1623 * in nc_packet
David S. Miller6e0895c2013-04-22 20:32:51 -04001624 * @bat_priv: the bat priv with all the soft interface information
Martin Hundebøll2df52782013-01-25 11:12:43 +01001625 * @skb: unicast skb to decode
1626 * @nc_packet: decode data needed to decode the skb
1627 *
1628 * Returns pointer to decoded unicast packet if the packet was decoded or NULL
1629 * in case of an error.
1630 */
1631static struct batadv_unicast_packet *
David S. Miller6e0895c2013-04-22 20:32:51 -04001632batadv_nc_skb_decode_packet(struct batadv_priv *bat_priv, struct sk_buff *skb,
Martin Hundebøll2df52782013-01-25 11:12:43 +01001633 struct batadv_nc_packet *nc_packet)
1634{
1635 const int h_size = sizeof(struct batadv_unicast_packet);
1636 const int h_diff = sizeof(struct batadv_coded_packet) - h_size;
1637 struct batadv_unicast_packet *unicast_packet;
1638 struct batadv_coded_packet coded_packet_tmp;
1639 struct ethhdr *ethhdr, ethhdr_tmp;
1640 uint8_t *orig_dest, ttl, ttvn;
1641 unsigned int coding_len;
Marek Lindner7da19972013-05-07 19:25:02 +08001642 int err;
Martin Hundebøll2df52782013-01-25 11:12:43 +01001643
1644 /* Save headers temporarily */
1645 memcpy(&coded_packet_tmp, skb->data, sizeof(coded_packet_tmp));
1646 memcpy(&ethhdr_tmp, skb_mac_header(skb), sizeof(ethhdr_tmp));
1647
1648 if (skb_cow(skb, 0) < 0)
1649 return NULL;
1650
1651 if (unlikely(!skb_pull_rcsum(skb, h_diff)))
1652 return NULL;
1653
1654 /* Data points to batman header, so set mac header 14 bytes before
1655 * and network to data
1656 */
1657 skb_set_mac_header(skb, -ETH_HLEN);
1658 skb_reset_network_header(skb);
1659
1660 /* Reconstruct original mac header */
Antonio Quartulli7ed4be92013-04-08 15:08:18 +02001661 ethhdr = eth_hdr(skb);
Fengguang Wuabae9472014-01-06 17:09:46 +01001662 *ethhdr = ethhdr_tmp;
Martin Hundebøll2df52782013-01-25 11:12:43 +01001663
1664 /* Select the correct unicast header information based on the location
1665 * of our mac address in the coded_packet header
1666 */
David S. Miller6e0895c2013-04-22 20:32:51 -04001667 if (batadv_is_my_mac(bat_priv, coded_packet_tmp.second_dest)) {
Martin Hundebøll2df52782013-01-25 11:12:43 +01001668 /* If we are the second destination the packet was overheard,
1669 * so the Ethernet address must be copied to h_dest and
1670 * pkt_type changed from PACKET_OTHERHOST to PACKET_HOST
1671 */
Antonio Quartulli8fdd0152014-01-22 00:42:11 +01001672 ether_addr_copy(ethhdr->h_dest, coded_packet_tmp.second_dest);
Martin Hundebøll2df52782013-01-25 11:12:43 +01001673 skb->pkt_type = PACKET_HOST;
1674
1675 orig_dest = coded_packet_tmp.second_orig_dest;
1676 ttl = coded_packet_tmp.second_ttl;
1677 ttvn = coded_packet_tmp.second_ttvn;
1678 } else {
1679 orig_dest = coded_packet_tmp.first_orig_dest;
Simon Wunderlicha40d9b02013-12-02 20:38:31 +01001680 ttl = coded_packet_tmp.ttl;
Martin Hundebøll2df52782013-01-25 11:12:43 +01001681 ttvn = coded_packet_tmp.first_ttvn;
1682 }
1683
1684 coding_len = ntohs(coded_packet_tmp.coded_len);
1685
1686 if (coding_len > skb->len)
1687 return NULL;
1688
1689 /* Here the magic is reversed:
1690 * extract the missing packet from the received coded packet
1691 */
1692 batadv_nc_memxor(skb->data + h_size,
1693 nc_packet->skb->data + h_size,
1694 coding_len);
1695
1696 /* Resize decoded skb if decoded with larger packet */
Marek Lindner7da19972013-05-07 19:25:02 +08001697 if (nc_packet->skb->len > coding_len + h_size) {
1698 err = pskb_trim_rcsum(skb, coding_len + h_size);
1699 if (err)
1700 return NULL;
1701 }
Martin Hundebøll2df52782013-01-25 11:12:43 +01001702
1703 /* Create decoded unicast packet */
1704 unicast_packet = (struct batadv_unicast_packet *)skb->data;
Simon Wunderlicha40d9b02013-12-02 20:38:31 +01001705 unicast_packet->packet_type = BATADV_UNICAST;
1706 unicast_packet->version = BATADV_COMPAT_VERSION;
1707 unicast_packet->ttl = ttl;
Antonio Quartulli8fdd0152014-01-22 00:42:11 +01001708 ether_addr_copy(unicast_packet->dest, orig_dest);
Martin Hundebøll2df52782013-01-25 11:12:43 +01001709 unicast_packet->ttvn = ttvn;
1710
1711 batadv_nc_packet_free(nc_packet);
1712 return unicast_packet;
1713}
1714
1715/**
1716 * batadv_nc_find_decoding_packet - search through buffered decoding data to
1717 * find the data needed to decode the coded packet
1718 * @bat_priv: the bat priv with all the soft interface information
1719 * @ethhdr: pointer to the ethernet header inside the coded packet
1720 * @coded: coded packet we try to find decode data for
1721 *
1722 * Returns pointer to nc packet if the needed data was found or NULL otherwise.
1723 */
1724static struct batadv_nc_packet *
1725batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv,
1726 struct ethhdr *ethhdr,
1727 struct batadv_coded_packet *coded)
1728{
1729 struct batadv_hashtable *hash = bat_priv->nc.decoding_hash;
1730 struct batadv_nc_packet *tmp_nc_packet, *nc_packet = NULL;
1731 struct batadv_nc_path *nc_path, nc_path_key;
1732 uint8_t *dest, *source;
1733 __be32 packet_id;
1734 int index;
1735
1736 if (!hash)
1737 return NULL;
1738
1739 /* Select the correct packet id based on the location of our mac-addr */
1740 dest = ethhdr->h_source;
David S. Miller6e0895c2013-04-22 20:32:51 -04001741 if (!batadv_is_my_mac(bat_priv, coded->second_dest)) {
Martin Hundebøll2df52782013-01-25 11:12:43 +01001742 source = coded->second_source;
1743 packet_id = coded->second_crc;
1744 } else {
1745 source = coded->first_source;
1746 packet_id = coded->first_crc;
1747 }
1748
1749 batadv_nc_hash_key_gen(&nc_path_key, source, dest);
1750 index = batadv_nc_hash_choose(&nc_path_key, hash->size);
1751
1752 /* Search for matching coding path */
1753 rcu_read_lock();
1754 hlist_for_each_entry_rcu(nc_path, &hash->table[index], hash_entry) {
1755 /* Find matching nc_packet */
1756 spin_lock_bh(&nc_path->packet_list_lock);
1757 list_for_each_entry(tmp_nc_packet,
1758 &nc_path->packet_list, list) {
1759 if (packet_id == tmp_nc_packet->packet_id) {
1760 list_del(&tmp_nc_packet->list);
1761
1762 nc_packet = tmp_nc_packet;
1763 break;
1764 }
1765 }
1766 spin_unlock_bh(&nc_path->packet_list_lock);
1767
1768 if (nc_packet)
1769 break;
1770 }
1771 rcu_read_unlock();
1772
1773 if (!nc_packet)
1774 batadv_dbg(BATADV_DBG_NC, bat_priv,
1775 "No decoding packet found for %u\n", packet_id);
1776
1777 return nc_packet;
1778}
1779
1780/**
1781 * batadv_nc_recv_coded_packet - try to decode coded packet and enqueue the
1782 * resulting unicast packet
1783 * @skb: incoming coded packet
1784 * @recv_if: pointer to interface this packet was received on
1785 */
1786static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
1787 struct batadv_hard_iface *recv_if)
1788{
1789 struct batadv_priv *bat_priv = netdev_priv(recv_if->soft_iface);
1790 struct batadv_unicast_packet *unicast_packet;
1791 struct batadv_coded_packet *coded_packet;
1792 struct batadv_nc_packet *nc_packet;
1793 struct ethhdr *ethhdr;
1794 int hdr_size = sizeof(*coded_packet);
1795
1796 /* Check if network coding is enabled */
1797 if (!atomic_read(&bat_priv->network_coding))
1798 return NET_RX_DROP;
1799
1800 /* Make sure we can access (and remove) header */
1801 if (unlikely(!pskb_may_pull(skb, hdr_size)))
1802 return NET_RX_DROP;
1803
1804 coded_packet = (struct batadv_coded_packet *)skb->data;
Antonio Quartulli7ed4be92013-04-08 15:08:18 +02001805 ethhdr = eth_hdr(skb);
Martin Hundebøll2df52782013-01-25 11:12:43 +01001806
1807 /* Verify frame is destined for us */
David S. Miller6e0895c2013-04-22 20:32:51 -04001808 if (!batadv_is_my_mac(bat_priv, ethhdr->h_dest) &&
1809 !batadv_is_my_mac(bat_priv, coded_packet->second_dest))
Martin Hundebøll2df52782013-01-25 11:12:43 +01001810 return NET_RX_DROP;
1811
1812 /* Update stat counter */
David S. Miller6e0895c2013-04-22 20:32:51 -04001813 if (batadv_is_my_mac(bat_priv, coded_packet->second_dest))
Martin Hundebøll2df52782013-01-25 11:12:43 +01001814 batadv_inc_counter(bat_priv, BATADV_CNT_NC_SNIFFED);
1815
1816 nc_packet = batadv_nc_find_decoding_packet(bat_priv, ethhdr,
1817 coded_packet);
1818 if (!nc_packet) {
1819 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1820 return NET_RX_DROP;
1821 }
1822
1823 /* Make skb's linear, because decoding accesses the entire buffer */
1824 if (skb_linearize(skb) < 0)
1825 goto free_nc_packet;
1826
1827 if (skb_linearize(nc_packet->skb) < 0)
1828 goto free_nc_packet;
1829
1830 /* Decode the packet */
David S. Miller6e0895c2013-04-22 20:32:51 -04001831 unicast_packet = batadv_nc_skb_decode_packet(bat_priv, skb, nc_packet);
Martin Hundebøll2df52782013-01-25 11:12:43 +01001832 if (!unicast_packet) {
1833 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1834 goto free_nc_packet;
1835 }
1836
1837 /* Mark packet as decoded to do correct recoding when forwarding */
1838 BATADV_SKB_CB(skb)->decoded = true;
1839 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE);
1840 batadv_add_counter(bat_priv, BATADV_CNT_NC_DECODE_BYTES,
1841 skb->len + ETH_HLEN);
1842 return batadv_recv_unicast_packet(skb, recv_if);
1843
1844free_nc_packet:
1845 batadv_nc_packet_free(nc_packet);
1846 return NET_RX_DROP;
1847}
1848
1849/**
Matthias Schiffer6c519ba2013-09-27 18:03:39 +02001850 * batadv_nc_mesh_free - clean up network coding memory
Martin Hundebølld353d8d2013-01-25 11:12:38 +01001851 * @bat_priv: the bat priv with all the soft interface information
1852 */
Matthias Schiffer6c519ba2013-09-27 18:03:39 +02001853void batadv_nc_mesh_free(struct batadv_priv *bat_priv)
Martin Hundebølld353d8d2013-01-25 11:12:38 +01001854{
Marek Lindner3f4841f2013-04-23 21:40:00 +08001855 batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);
1856 batadv_tvlv_handler_unregister(bat_priv, BATADV_TVLV_NC, 1);
Martin Hundebølld353d8d2013-01-25 11:12:38 +01001857 cancel_delayed_work_sync(&bat_priv->nc.work);
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001858
Martin Hundebøll95332472013-01-25 11:12:40 +01001859 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL);
1860 batadv_hash_destroy(bat_priv->nc.coding_hash);
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001861 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL);
1862 batadv_hash_destroy(bat_priv->nc.decoding_hash);
Martin Hundebølld353d8d2013-01-25 11:12:38 +01001863}
Martin Hundebølld56b1702013-01-25 11:12:39 +01001864
1865/**
1866 * batadv_nc_nodes_seq_print_text - print the nc node information
1867 * @seq: seq file to print on
1868 * @offset: not used
1869 */
1870int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
1871{
1872 struct net_device *net_dev = (struct net_device *)seq->private;
1873 struct batadv_priv *bat_priv = netdev_priv(net_dev);
1874 struct batadv_hashtable *hash = bat_priv->orig_hash;
1875 struct batadv_hard_iface *primary_if;
1876 struct hlist_head *head;
1877 struct batadv_orig_node *orig_node;
1878 struct batadv_nc_node *nc_node;
1879 int i;
1880
1881 primary_if = batadv_seq_print_text_primary_if_get(seq);
1882 if (!primary_if)
1883 goto out;
1884
1885 /* Traverse list of originators */
1886 for (i = 0; i < hash->size; i++) {
1887 head = &hash->table[i];
1888
1889 /* For each orig_node in this bin */
1890 rcu_read_lock();
1891 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
Marek Lindneraa27c3122013-04-18 04:56:03 +08001892 /* no need to print the orig node if it does not have
1893 * network coding neighbors
1894 */
1895 if (list_empty(&orig_node->in_coding_list) &&
1896 list_empty(&orig_node->out_coding_list))
1897 continue;
1898
Martin Hundebølld56b1702013-01-25 11:12:39 +01001899 seq_printf(seq, "Node: %pM\n", orig_node->orig);
1900
Antonio Quartulli0c814652013-03-21 09:23:29 +01001901 seq_puts(seq, " Ingoing: ");
Martin Hundebølld56b1702013-01-25 11:12:39 +01001902 /* For each in_nc_node to this orig_node */
1903 list_for_each_entry_rcu(nc_node,
1904 &orig_node->in_coding_list,
1905 list)
1906 seq_printf(seq, "%pM ",
1907 nc_node->addr);
Antonio Quartulli0c814652013-03-21 09:23:29 +01001908 seq_puts(seq, "\n");
Martin Hundebølld56b1702013-01-25 11:12:39 +01001909
Antonio Quartulli0c814652013-03-21 09:23:29 +01001910 seq_puts(seq, " Outgoing: ");
Martin Hundebølld56b1702013-01-25 11:12:39 +01001911 /* For out_nc_node to this orig_node */
1912 list_for_each_entry_rcu(nc_node,
1913 &orig_node->out_coding_list,
1914 list)
1915 seq_printf(seq, "%pM ",
1916 nc_node->addr);
Antonio Quartulli0c814652013-03-21 09:23:29 +01001917 seq_puts(seq, "\n\n");
Martin Hundebølld56b1702013-01-25 11:12:39 +01001918 }
1919 rcu_read_unlock();
1920 }
1921
1922out:
1923 if (primary_if)
1924 batadv_hardif_free_ref(primary_if);
1925 return 0;
1926}
1927
1928/**
1929 * batadv_nc_init_debugfs - create nc folder and related files in debugfs
1930 * @bat_priv: the bat priv with all the soft interface information
1931 */
1932int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
1933{
1934 struct dentry *nc_dir, *file;
1935
1936 nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
1937 if (!nc_dir)
1938 goto out;
1939
1940 file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir,
1941 &bat_priv->nc.min_tq);
1942 if (!file)
1943 goto out;
1944
Martin Hundebøll95332472013-01-25 11:12:40 +01001945 file = debugfs_create_u32("max_fwd_delay", S_IRUGO | S_IWUSR, nc_dir,
1946 &bat_priv->nc.max_fwd_delay);
1947 if (!file)
1948 goto out;
1949
Martin Hundebøll612d2b42013-01-25 11:12:42 +01001950 file = debugfs_create_u32("max_buffer_time", S_IRUGO | S_IWUSR, nc_dir,
1951 &bat_priv->nc.max_buffer_time);
1952 if (!file)
1953 goto out;
1954
Martin Hundebølld56b1702013-01-25 11:12:39 +01001955 return 0;
1956
1957out:
1958 return -ENOMEM;
1959}