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

/*
 * Copyright (C) 2008-2011 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 MAX_VIS_PACKET_SIZE 1000

/* Returns the smallest signed integer in two's complement with the sizeof x */
#define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u)))

/* Checks if a sequence number x is a predecessor/successor of y.
 * they handle overflows/underflows and can correctly check for a
 * predecessor/successor unless the variable sequence number has grown by
 * more then 2**(bitwidth(x)-1)-1.
 * This means that for a uint8_t with the maximum value 255, it would think:
 *  - when adding nothing - it is neither a predecessor nor a successor
 *  - before adding more than 127 to the starting value - it is a predecessor,
 *  - when adding 128 - it is neither a predecessor nor a successor,
 *  - after adding more than 127 to the starting value - it is a successor */
#define seq_before(x, y) ({typeof(x) _dummy = (x - y); \
			_dummy > smallest_signed_int(_dummy); })
#define seq_after(x, y) seq_before(y, x)

static void start_vis_timer(struct bat_priv *bat_priv);

/* free the info */
static void free_info(struct kref *ref)
{
	struct vis_info *info = container_of(ref, struct vis_info, refcount);
	struct bat_priv *bat_priv = info->bat_priv;
	struct recvlist_node *entry, *tmp;

	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);
}

/* Compare two vis packets, used by the hashing algorithm */
static int vis_info_cmp(void *data1, void *data2)
{
	struct vis_info *d1, *d2;
	struct vis_packet *p1, *p2;
	d1 = data1;
	d2 = data2;
	p1 = (struct vis_packet *)d1->skb_packet->data;
	p2 = (struct vis_packet *)d2->skb_packet->data;
	return 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 int vis_info_choose(void *data, int size)
{
	struct vis_info *vis_info = data;
	struct vis_packet *packet;
	unsigned char *key;
	uint32_t hash = 0;
	size_t i;

	packet = (struct 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;
}

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

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

	/* its 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 ssize_t vis_data_read_prim_sec(char *buff, struct hlist_head *if_list)
{
	struct if_list_entry *entry;
	struct hlist_node *pos;
	size_t len = 0;

	hlist_for_each_entry(entry, pos, if_list, list) {
		if (entry->primary)
			len += sprintf(buff + len, "PRIMARY, ");
		else
			len += sprintf(buff + len,  "SEC %pM, ", entry->addr);
	}

	return len;
}

static size_t vis_data_count_prim_sec(struct hlist_head *if_list)
{
	struct if_list_entry *entry;
	struct hlist_node *pos;
	size_t count = 0;

	hlist_for_each_entry(entry, pos, if_list, list) {
		if (entry->primary)
			count