/* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors: * * Martin Hundebøll, Jeppe Ledet-Pedersen * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA */ #include <linux/debugfs.h> #include "main.h"#include "hash.h"#include "network-coding.h"#include "send.h"#include "originator.h"#include "hard-interface.h"#include "routing.h" static struct lock_class_key batadv_nc_coding_hash_lock_class_key;static struct lock_class_key batadv_nc_decoding_hash_lock_class_key; static void batadv_nc_worker(struct work_struct *work);static int batadv_nc_recv_coded_packet(struct sk_buff *skb,				       struct batadv_hard_iface *recv_if); /** * batadv_nc_init - one-time initialization for network coding */int __init batadv_nc_init(void){	int ret; 	/* Register our packet type */	ret = batadv_recv_handler_register(BATADV_CODED,					   batadv_nc_recv_coded_packet); 	return ret;} /** * batadv_nc_start_timer - initialise the nc periodic worker * @bat_priv: the bat priv with all the soft interface information */static void batadv_nc_start_timer(struct batadv_priv *bat_priv){	queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,			   msecs_to_jiffies(10));} /** * batadv_nc_tvlv_container_update - update the network coding tvlv container *  after network coding setting change * @bat_priv: the bat priv with all the soft interface information */static void batadv_nc_tvlv_container_update(struct batadv_priv *bat_priv){	char nc_mode; 	nc_mode = atomic_read(&bat_priv->network_coding); 	switch (nc_mode) {	case 0:		batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);		break;	case 1:		batadv_tvlv_container_register(bat_priv, BATADV_TVLV_NC, 1,					       NULL, 0);		break;	}} /** * batadv_nc_status_update - update the network coding tvlv container after *  network coding setting change * @net_dev: the soft interface net device */void batadv_nc_status_update(struct net_device *net_dev){	struct batadv_priv *bat_priv = netdev_priv(net_dev);	batadv_nc_tvlv_container_update(bat_priv);} /** * batadv_nc_tvlv_ogm_handler_v1 - process incoming nc tvlv container * @bat_priv: the bat priv with all the soft interface information * @orig: the orig_node of the ogm * @flags: flags indicating the tvlv state (see batadv_tvlv_handler_flags) * @tvlv_value: tvlv buffer containing the gateway data * @tvlv_value_len: tvlv buffer length */static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv,					  struct batadv_orig_node *orig,					  uint8_t flags,					  void *tvlv_value,					  uint16_t tvlv_value_len){	if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND)		orig->capabilities &= ~BATADV_ORIG_CAPA_HAS_NC;	else		orig->capabilities |= BATADV_ORIG_CAPA_HAS_NC;} /** * batadv_nc_mesh_init - initialise coding hash table and start house keeping * @bat_priv: the bat priv with all the soft interface information */int batadv_nc_mesh_init(struct batadv_priv *bat_priv){	bat_priv->nc.timestamp_fwd_flush = jiffies;	bat_priv->nc.timestamp_sniffed_purge = jiffies; 	if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash)		return 0; 	bat_priv->nc.coding_hash = batadv_hash_new(128);	if (!bat_priv->nc.coding_hash)		goto err; 	batadv_hash_set_lock_class(bat_priv->nc.coding_hash,				   &batadv_nc_coding_hash_lock_class_key); 	bat_priv->nc.decoding_hash = batadv_hash_new(128);	if (!bat_priv->nc.decoding_hash)		goto err; 	batadv_hash_set_lock_class(bat_priv->nc.coding_hash,				   &batadv_nc_decoding_hash_lock_class_key); 	INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);	batadv_nc_start_timer(bat_priv); 	batadv_tvlv_handler_register(bat_priv, batadv_nc_tvlv_ogm_handler_v1,				     NULL, BATADV_TVLV_NC, 1,				     BATADV_TVLV_HANDLER_OGM_CIFNOTFND);	batadv_nc_tvlv_container_update(bat_priv);	return 0; err:	return -ENOMEM;} /** * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables * @bat_priv: the bat priv with all the soft interface information */void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv){	atomic_set(&bat_priv->network_coding, 1);	bat_priv->nc.min_tq = 200;	bat_priv->nc.max_fwd_delay = 10;	bat_priv->nc.max_buffer_time = 200;} /** * batadv_nc_init_orig - initialise the nc fields of an orig_node * @orig_node: the orig_node which is going to be initialised */void batadv_nc_init_orig(struct batadv_orig_node *orig_node){	INIT_LIST_HEAD(&orig_node->in_coding_list);	INIT_LIST_HEAD(&orig_node->out_coding_list);	spin_lock_init(&orig_node->in_coding_list_lock);	spin_lock_init(&orig_node->out_coding_list_lock);} /** * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove *  its refcount on the orig_node * @rcu: rcu pointer of the nc node */static void batadv_nc_node_free_rcu(struct rcu_head *rcu){	struct batadv_nc_node *nc_node; 	nc_node = container_of(rcu, struct batadv_nc_node, rcu);	batadv_orig_node_free_ref(nc_node->orig_node);	kfree(nc_node);} /** * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly * frees it * @nc_node: the nc node to free */static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node){	if (atomic_dec_and_test(&nc_node->refcount))		call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu);} /** * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly * frees it * @nc_path: the nc node to free */static void batadv_nc_path_free_ref(struct batadv_nc_path *nc_path){	if (atomic_dec_and_test(&nc_path->refcount))		kfree_rcu(nc_path, rcu);} /** * batadv_nc_packet_free - frees nc packet * @nc_packet: the nc packet to free */static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet){	if (nc_packet->skb)		kfree_skb(nc_packet->skb); 	batadv_nc_path_free_ref(nc_packet->nc_path);	kfree(nc_packet);} /** * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged * @bat_priv: the bat priv with all the soft interface information * @nc_node: the nc node to check * * Returns true if the entry has to be purged now, false otherwise */static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,				       struct batadv_nc_node *nc_node){	if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)		return true; 	return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);} /** * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out * @bat_priv: the bat priv with all the soft interface information * @nc_path: the nc path to check * * Returns true if the entry has to be purged now, false otherwise */static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,					      struct batadv_nc_path *nc_path){	if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)		return true; 	/* purge the path when no packets has been added for 10 times the	 * max_fwd_delay time	 */	return batadv_has_timed_out(nc_path->last_valid,				    bat_priv->nc.max_fwd_delay * 10);} /** * batadv_nc_to_purge_nc_path_decoding - checks whether an nc path has timed out * @bat_priv: the bat priv with all the soft interface information * @nc_path: the nc path to check * * Returns true if the entry has to be purged now, false otherwise */static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv *bat_priv,						struct batadv_nc_path *nc_path){	if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)		return true; 	/* purge the path when no packets has been added for 10 times the	 * max_buffer time	 */	return batadv_has_timed_out(nc_path->last_valid,				    bat_priv->nc.max_buffer_time*10);} /** * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale *  entries * @bat_priv: the bat priv with all the soft interface information * @list: list of nc nodes * @lock: nc node list lock * @to_purge: function in charge to decide whether an entry has to be purged or *	      not. This function takes the nc node as argument and has to return *	      a boolean value: true if the entry has to be deleted, false *	      otherwise */static voidbatadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,			      struct list_head *list,			      spinlock_t *lock,			      bool (*to_purge)(struct batadv_priv *,					       struct batadv_nc_node *)){	struct batadv_nc_node *nc_node, *nc_node_tmp; 	/* For each nc_node in list */	spin_lock_bh(lock);	list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {		/* if an helper function has been passed as parameter,		 * ask it if the entry has to be purged or not		 */		if (to_purge && !to_purge(bat_priv, nc_node))			continue; 		batadv_dbg(BATADV_DBG_NC, bat_priv,			   "Removing nc_node %pM -> %pM\n",			   nc_node->addr, nc_node->orig_node->orig);		list_del_rcu(&nc_node->list);		batadv_nc_node_free_ref(nc_node);	}	spin_unlock_bh(lock);} /** * batadv_nc_purge_orig - purges all nc node data attached of the given *  originator * @bat_priv: the bat priv with all the soft interface information * @orig_node: orig_node with the nc node entries to be purged * @to_purge: function in charge to decide whether an entry has to be purged or *	      not. This function takes the nc node as argument and has to return *	      a boolean value: true is the entry has to be deleted, false *	      otherwise */void batadv_nc_purge_orig(struct batadv_priv *bat_priv,			  struct batadv_orig_node *orig_node,			  bool (*to_purge)(struct batadv_priv *,					   struct batadv_nc_node *)){	/* Check ingoing nc_node's of this orig_node */	batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,				      &orig_node->in_coding_list_lock,				      to_purge); 	/* Check outgoing nc_node's of this orig_node */	batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,				      &orig_node->out_coding_list_lock,				      to_purge);} /** * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they *  have timed out nc nodes * @bat_priv: the bat priv with all the soft interface information */static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv){	struct batadv_hashtable *hash = bat_priv->orig_hash;	struct hlist_head *head;	struct batadv_orig_node *orig_node;	uint32_t i; 	if (!hash)		return; 	/* For each orig_node */	for (i = 0; i < hash->size; i++) {		head = &hash->table[i]; 		rcu_read_lock();		hlist_for_each_entry_rcu(orig_node, head, hash_entry)			batadv_nc_purge_orig(bat_priv, orig_node,					     batadv_nc_to_purge_nc_node);		rcu_read_unlock();	}} /** * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove *  unused ones * @bat_priv: the bat priv with all the soft interface information * @hash: hash table containing the nc paths to check * @to_purge: function in charge to decide whether an entry has to be purged or *	      not. This function takes the nc node as argument and has to return *	      a boolean value: true is the entry has to be deleted, false *	      otherwise */static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,				  struct batadv_hashtable *hash,				  bool (*to_purge)(struct batadv_priv *,						   struct batadv_nc_path *)){	struct hlist_head *head;	struct hlist_node *node_tmp;	struct batadv_nc_path *nc_path;	spinlock_t *lock; /* Protects lists in hash */	uint32_t i; 	for (i = 0; i < hash->size; i++) {		head = &hash->table[i];		lock = &hash->list_locks[i]; 		/* For each nc_path in this bin */		spin_lock_bh(lock);		hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {			/* if an helper function has been passed as parameter,			 * ask it if the entry has to be purged or not			 */			if (to_purge && !to_purge(bat_priv, nc_path))				continue; 			/* purging an non-empty nc_path should never happen, but			 * is observed under high CPU load. Delay the purging			 * until next iteration to allow the packet_list to be			 * emptied first.			 */			if (!unlikely(list_empty(&nc_path->packet_list))) {				net_ratelimited_function(printk,							 KERN_WARNING							 "Skipping free of non-empty nc_path (%pM -> %pM)!\n",							 nc_path->prev_hop,							 nc_path->next_hop);				continue;			} 			/* nc_path is unused, so remove it */			batadv_dbg(BATADV_DBG_NC, bat_priv,				   "Remove nc_path %pM -> %pM\n",				   nc_path->prev_hop, nc_path->next_hop);			hlist_del_rcu(&nc_path->hash_entry);			batadv_nc_path_free_ref(nc_path);		}		spin_unlock_bh(lock);	}} /** * batadv_nc_hash_key_gen - computes the nc_path hash key * @key: buffer to hold the final hash key * @src: source ethernet mac address going into the hash key * @dst: destination ethernet mac address going into the hash key */static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,				   const char *dst){	memcpy(key->prev_hop, src, sizeof(key->prev_hop));	memcpy(key->next_hop, dst, sizeof(key->next_hop));} /** * batadv_nc_hash_choose - compute the hash value for an nc path * @data: data to hash * @size: size of the hash table * * Returns the selected index in the hash table for the given data. */static uint32_t batadv_nc_hash_choose(const void *data, uint32_t size){	const struct batadv_nc_path *nc_path = data;	uint32_t hash = 0; 	hash = batadv_hash_bytes(hash, &nc_path->prev_hop,				 sizeof(nc_path->prev_hop));	hash = batadv_hash_bytes(hash, &nc_path->next_hop,				 sizeof(nc_path->next_hop)); 	hash += (hash << 3);	hash ^= (hash >> 11);	hash += (hash << 15); 	return hash % size;} /** * batadv_nc_hash_compare - comparing function used in the network coding hash *  tables * @node: node in the local table * @data2: second object to compare the node to * * Returns 1 if the two entry are the same, 0 otherwise */static int batadv_nc_hash_compare(const struct hlist_node *node,				  const void *data2){	const struct batadv_nc_path *nc_path1, *nc_path2; 	nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);	nc_path2 = data2; 	/* Return 1 if the two keys are identical */	if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop,		   sizeof(nc_path1->prev_hop)) != 0)		return 0; 	if (memcmp(nc_path1->next_hop, nc_path2->next_hop,		   sizeof(nc_path1->next_hop)) != 0)		return 0; 	return 1;} /** * batadv_nc_hash_find - search for an existing nc path and return it * @hash: hash table containing the nc path * @data: search key

Lines 1–500 of 1905. Load more