path: root/net/batman-adv/vis.c

/* Copyright (C) 2008-2012 B.A.T.M.A.N. contributors:
 *
 * Simon Wunderlich
 *
 * 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 "main.h"
#include "send.h"
#include "translation-table.h"
#include "vis.h"
#include "soft-interface.h"
#include "hard-interface.h"
#include "hash.h"
#include "originator.h"

#define BATADV_MAX_VIS_PACKET_SIZE 1000

static void batadv_start_vis_timer(struct batadv_priv *bat_priv);

/* free the info */
static void batadv_free_info(struct kref *ref)
{
	struct batadv_vis_info *info;
	struct batadv_priv *bat_priv;
	struct batadv_recvlist_node *entry, *tmp;

	info = container_of(ref, struct batadv_vis_info, refcount);
	bat_priv = info->bat_priv;

	list_del_init(&info->send_list);
	spin_lock_bh(&bat_priv->vis_list_lock);
	list_for_each_entry_safe(entry, tmp, &info->recv_list, list) {
		list_del(&entry->list);
		kfree(entry);
	}

	spin_unlock_bh(&bat_priv->vis_list_lock);
	kfree_skb(info->skb_packet);
	kfree(info);
}

/* Compare two vis packets, used by the hashing algorithm */
static int batadv_vis_info_cmp(const struct hlist_node *node, const void *data2)
{
	const struct batadv_vis_info *d1, *d2;
	const struct batadv_vis_packet *p1, *p2;

	d1 = container_of(node, struct batadv_vis_info, hash_entry);
	d2 = data2;
	p1 = (struct batadv_vis_packet *)d1->skb_packet->data;
	p2 = (struct batadv_vis_packet *)d2->skb_packet->data;
	return batadv_compare_eth(p1->vis_orig, p2->vis_orig);
}

/* hash function to choose an entry in a hash table of given size
 * hash algorithm from http://en.wikipedia.org/wiki/Hash_table
 */
static uint32_t batadv_vis_info_choose(const void *data, uint32_t size)
{
	const struct batadv_vis_info *vis_info = data;
	const struct batadv_vis_packet *packet;
	const unsigned char *key;
	uint32_t hash = 0;
	size_t i;

	packet = (struct batadv_vis_packet *)vis_info->skb_packet->data;
	key = packet->vis_orig;
	for (i = 0; i < ETH_ALEN; i++) {
		hash += key[i];
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}

	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash % size;
}

static struct batadv_vis_info *
batadv_vis_hash_find(struct batadv_priv *bat_priv, const void *data)
{
	struct batadv_hashtable *hash = bat_priv->vis_hash;
	struct hlist_head *head;
	struct hlist_node *node;
	struct batadv_vis_info *vis_info, *vis_info_tmp = NULL;
	uint32_t index;

	if (!hash)
		return NULL;

	index = batadv_vis_info_choose(data, hash->size);
	head = &hash->table[index];

	rcu_read_lock();
	hlist_for_each_entry_rcu(vis_info, node, head, hash_entry) {
		if (!batadv_vis_info_cmp(node, data))
			continue;

		vis_info_tmp = vis_info;
		break;
	}
	rcu_read_unlock();

	return vis_info_tmp;
}

/* insert interface to the list of interfaces of one originator, if it
 * does not already exist in the list
 */
static void batadv_vis_data_insert_interface(const uint8_t *interface,
					     struct hlist_head *if_list,
					     bool primary)
{
	struct batadv_if_list_entry *entry;
	struct hlist_node *pos;

	hlist_for_each_entry(entry, pos, if_list, list) {
		if (batadv_compare_eth(entry->addr, interface))
			return;
	}

	/* it's a new address, add it to the list */
	entry = kmalloc(sizeof(*entry), GFP_ATOMIC);
	if (!entry)
		return;
	memcpy(entry->addr, interface, ETH_ALEN);
	entry->primary = primary;
	hlist_add_head(&entry->list, if_list);
}

static void batadv_vis_data_read_prim_sec(struct seq_file *seq,
					  const struct hlist_head *if_list)
{
	struct batadv_if_list_entry *entry;
	struct hlist_node *pos;

	hlist_for_each_entry(entry, pos