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