[net-next-2.6.git] / drivers / staging / batman-adv / aggregation.c

/*
 * Copyright (C) 2007-2010 B.A.T.M.A.N. contributors:
 *
 * Marek Lindner, 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 "aggregation.h"
#include "send.h"
#include "routing.h"

/* calculate the size of the hna information for a given packet */
static int hna_len(struct batman_packet *batman_packet)
{
	return batman_packet->num_hna * ETH_ALEN;
}

/* return true if new_packet can be aggregated with forw_packet */
static bool can_aggregate_with(struct batman_packet *new_batman_packet,
			       int packet_len,
			       unsigned long send_time,
			       bool directlink,
			       struct batman_if *if_incoming,
			       struct forw_packet *forw_packet)
{
	struct batman_packet *batman_packet =
		(struct batman_packet *)forw_packet->skb->data;
	int aggregated_bytes = forw_packet->packet_len + packet_len;

	/**
	 * we can aggregate the current packet to this aggregated packet
	 * if:
	 *
	 * - the send time is within our MAX_AGGREGATION_MS time
	 * - the resulting packet wont be bigger than
	 *   MAX_AGGREGATION_BYTES
	 */

	if (time_before(send_time, forw_packet->send_time) &&
	    time_after_eq(send_time + msecs_to_jiffies(MAX_AGGREGATION_MS),
					forw_packet->send_time) &&
	    (aggregated_bytes <= MAX_AGGREGATION_BYTES)) {

		/**
		 * check aggregation compatibility
		 * -> direct link packets are broadcasted on
		 *    their interface only
		 * -> aggregate packet if the current packet is
		 *    a "global" packet as well as the base
		 *    packet
		 */

		/* packets without direct link flag and high TTL
		 * are flooded through the net  */
		if ((!directlink) &&
		    (!(batman_packet->flags & DIRECTLINK)) &&
		    (batman_packet->ttl != 1) &&

		    /* own packets originating non-primary
		     * interfaces leave only that interface */
		    ((!forw_packet->own) ||
		     (forw_packet->if_incoming->if_num == 0)))
			return true;

		/* if the incoming packet is sent via this one
		 * interface only - we still can aggregate */
		if ((directlink) &&
		    (new_batman_packet->ttl == 1) &&
		    (forw_packet->if_incoming == if_incoming) &&

		    /* packets from direct neighbors or
		     * own secondary interface packets
		     * (= secondary interface packets in general) */
		    (batman_packet->flags & DIRECTLINK ||
		     (forw_packet->own &&
		      forw_packet->if_incoming->if_num != 0)))
			return true;
	}

	return false;
}

#define atomic_dec_not_zero(v)          atomic_add_unless((v), -1, 0)
/* create a new aggregated packet and add this packet to it */
static void new_aggregated_packet(unsigned char *packet_buff, int packet_len,
				  unsigned long send_time, bool direct_link,
				  struct batman_if *if_incoming,
				  int own_packet)
{
	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
	struct forw_packet *forw_packet_aggr;
	unsigned long flags;
	unsigned char *skb_buff;

	/* own packet should always be scheduled */
	if (!own_packet) {
		if (!atomic_dec_not_zero(&bat_priv->batman_queue_left)) {
			bat_dbg(DBG_BATMAN, bat_priv,
				"batman packet queue full\n");
			return;
		}
	}

	forw_packet_aggr = kmalloc(sizeof(struct forw_packet), GFP_ATOMIC);
	if (!forw_packet_aggr) {
		if (!own_packet)
			atomic_inc(&bat_priv->batman_queue_left);
		return;
	}

	if ((atomic_read(&bat_priv->aggregation_enabled)) &&
	    (packet_len < MAX_AGGREGATION_BYTES))
		forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES +
						      sizeof(struct ethhdr));
	else
		forw_packet_aggr->skb = dev_alloc_skb(packet_len +
						      sizeof(struct ethhdr));

	if (!forw_packet_aggr->skb) {
		if (!own_packet)
			atomic_inc(&bat_priv->batman_queue_left);
		kfree(forw_packet_aggr);
		return;
	}
	skb_reserve(forw_packet_aggr->skb, sizeof(struct ethhdr));

	INIT_HLIST_NODE(&forw_packet_aggr->list);

	skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
	forw_packet_aggr->packet_len = packet_len;
	memcpy(skb_buff, packet_buff, packet_len);

	forw_packet_aggr->own = own_packet;
	forw_packet_aggr->if_incoming = if_incoming;
	forw_packet_aggr->num_packets = 0;
	forw_packet_aggr->direct_link_flags = 0;
	forw_packet_aggr->send_time = send_time;

	/* save packet direct link flag status */
	if (direct_link)
		forw_packet_aggr->direct_link_flags |= 1;

	/* add new packet to packet list */
	spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags);
	hlist_add_head(&forw_packet_aggr->list, &bat_priv->forw_bat_list);
	spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags);

	/* start timer for this packet */
	INIT_DELAYED_WORK(&forw_packet_aggr->delayed_work,
			  send_outstanding_bat_packet);
	queue_delayed_work(bat_event_workqueue,
			   &forw_packet_aggr->delayed_work,
			   send_time - jiffies);
}

/* aggregate a new packet into the existing aggregation */
static void aggregate(struct forw_packet *forw_packet_aggr,
		      unsigned char *packet_buff,
		      int packet_len,
		      bool direct_link)
{
	unsigned char *skb_buff;

	skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
	memcpy(skb_buff, packet_buff, packet_len);
	forw_packet_aggr->packet_len += packet_len;
	forw_packet_aggr->num_packets++;

	/* save packet direct link flag status */
	if (direct_link)
		forw_packet_aggr->direct_link_flags |=
			(1 << forw_packet_aggr->num_packets);
}

void add_bat_packet_to_list(struct bat_priv *bat_priv,
			    unsigned char *packet_buff, int packet_len,
			    struct batman_if *if_incoming, char own_packet,
			    unsigned long send_time)
{
	/**
	 * _aggr -> pointer to the packet we want to aggregate with
	 * _pos -> pointer to the position in the queue
	 */
	struct forw_packet *forw_packet_aggr = NULL, *forw_packet_pos = NULL;
	struct hlist_node *tmp_node;
	struct batman_packet *batman_packet =
		(struct batman_packet *)packet_buff;
	bool direct_link = batman_packet->flags & DIRECTLINK ? 1 : 0;
	unsigned long flags;

	/* find position for the packet in the forward queue */
	spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags);
	/* own packets are not to be aggregated */
	if ((atomic_read(&bat_priv->aggregation_enabled)) && (!own_packet)) {
		hlist_for_each_entry(forw_packet_pos, tmp_node,
				     &bat_priv->forw_bat_list, list) {
			if (can_aggregate_with(batman_packet,
					       packet_len,
					       send_time,
					       direct_link,
					       if_incoming,
					       forw_packet_pos)) {
				forw_packet_aggr = forw_packet_pos;
				break;
			}
		}
	}

	/* nothing to aggregate with - either aggregation disabled or no
	 * suitable aggregation packet found */
	if (forw_packet_aggr == NULL) {
		/* the following section can run without the lock */
		spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags);

		/**
		 * if we could not aggregate this packet with one of the others
		 * we hold it back for a while, so that it might be aggregated
		 * later on
		 */
		if ((!own_packet) &&
		    (atomic_read(&bat_priv->aggregation_enabled)))
			send_time += msecs_to_jiffies(MAX_AGGREGATION_MS);

		new_aggregated_packet(packet_buff, packet_len,
				      send_time, direct_link,
				      if_incoming, own_packet);
	} else {
		aggregate(forw_packet_aggr,
			  packet_buff, packet_len,
			  direct_link);
		spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags);
	}
}

/* unpack the aggregated packets and process them one by one */
void receive_aggr_bat_packet(struct ethhdr *ethhdr, unsigned char *packet_buff,
			     int packet_len, struct batman_if *if_incoming)
{
	struct batman_packet *batman_packet;
	int buff_pos = 0;
	unsigned char *hna_buff;

	batman_packet = (struct batman_packet *)packet_buff;

	do {
		/* network to host order for our 32bit seqno, and the
		   orig_interval. */
		batman_packet->seqno = ntohl(batman_packet->seqno);

		hna_buff = packet_buff + buff_pos + BAT_PACKET_LEN;
		receive_bat_packet(ethhdr, batman_packet,
				   hna_buff, hna_len(batman_packet),
				   if_incoming);

		buff_pos += BAT_PACKET_LEN + hna_len(batman_packet);
		batman_packet = (struct batman_packet *)
			(packet_buff + buff_pos);
	} while (aggregated_packet(buff_pos, packet_len,
				   batman_packet->num_hna));
}
Commit	Line	Data
5beef3c9	1	/*
9b6d10b7	2	* Copyright (C) 2007-2010 B.A.T.M.A.N. contributors:
5beef3c9 AL	3	*
	4	* Marek Lindner, Simon Wunderlich
	5	*
	6	* This program is free software; you can redistribute it and/or
	7	* modify it under the terms of version 2 of the GNU General Public
	8	* License as published by the Free Software Foundation.
	9	*
	10	* This program is distributed in the hope that it will be useful, but
	11	* WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	* General Public License for more details.
	14	*
	15	* You should have received a copy of the GNU General Public License
	16	* along with this program; if not, write to the Free Software
	17	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
	18	* 02110-1301, USA
	19	*
	20	*/
	21
	22	#include "main.h"
	23	#include "aggregation.h"
	24	#include "send.h"
	25	#include "routing.h"
	26
	27	/* calculate the size of the hna information for a given packet */
	28	static int hna_len(struct batman_packet *batman_packet)
	29	{
	30	return batman_packet->num_hna * ETH_ALEN;
	31	}
	32
	33	/* return true if new_packet can be aggregated with forw_packet */
	34	static bool can_aggregate_with(struct batman_packet *new_batman_packet,
	35	int packet_len,
	36	unsigned long send_time,
	37	bool directlink,
	38	struct batman_if *if_incoming,
	39	struct forw_packet *forw_packet)
	40	{
	41	struct batman_packet *batman_packet =
b706007b	42	(struct batman_packet *)forw_packet->skb->data;
5beef3c9 AL	43	int aggregated_bytes = forw_packet->packet_len + packet_len;
	44
	45	/**
	46	* we can aggregate the current packet to this aggregated packet
	47	* if:
	48	*
	49	* - the send time is within our MAX_AGGREGATION_MS time
	50	* - the resulting packet wont be bigger than
	51	* MAX_AGGREGATION_BYTES
	52	*/
	53
	54	if (time_before(send_time, forw_packet->send_time) &&
bd13b616 ML	55	time_after_eq(send_time + msecs_to_jiffies(MAX_AGGREGATION_MS),
bd13b616 ML	56	forw_packet->send_time) &&
5beef3c9 AL	57	(aggregated_bytes <= MAX_AGGREGATION_BYTES)) {
	58
	59	/**
	60	* check aggregation compatibility
	61	* -> direct link packets are broadcasted on
	62	* their interface only
	63	* -> aggregate packet if the current packet is
	64	* a "global" packet as well as the base
	65	* packet
	66	*/
	67
	68	/* packets without direct link flag and high TTL
	69	* are flooded through the net */
	70	if ((!directlink) &&
	71	(!(batman_packet->flags & DIRECTLINK)) &&
	72	(batman_packet->ttl != 1) &&
	73
	74	/* own packets originating non-primary
	75	* interfaces leave only that interface */
	76	((!forw_packet->own) \|\|
	77	(forw_packet->if_incoming->if_num == 0)))
	78	return true;
	79
	80	/* if the incoming packet is sent via this one
	81	* interface only - we still can aggregate */
	82	if ((directlink) &&
	83	(new_batman_packet->ttl == 1) &&
bdc0c7eb LL	84	(forw_packet->if_incoming == if_incoming) &&
	85
	86	/* packets from direct neighbors or
	87	* own secondary interface packets
	88	* (= secondary interface packets in general) */
	89	(batman_packet->flags & DIRECTLINK \|\|
	90	(forw_packet->own &&
	91	forw_packet->if_incoming->if_num != 0)))
5beef3c9	92	return true;
5beef3c9 AL	93	}
	94
	95	return false;
	96	}
	97
19dae340	98	#define atomic_dec_not_zero(v) atomic_add_unless((v), -1, 0)
5beef3c9	99	/* create a new aggregated packet and add this packet to it */
6a0e9fa8 ML	100	static void new_aggregated_packet(unsigned char *packet_buff, int packet_len,
	101	unsigned long send_time, bool direct_link,
	102	struct batman_if *if_incoming,
	103	int own_packet)
5beef3c9	104	{
8c70f138	105	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
5beef3c9	106	struct forw_packet *forw_packet_aggr;
e7017195	107	unsigned long flags;
b706007b	108	unsigned char *skb_buff;
5beef3c9	109
19dae340 SW	110	/* own packet should always be scheduled */
19dae340 SW	111	if (!own_packet) {
7d02674f	112	if (!atomic_dec_not_zero(&bat_priv->batman_queue_left)) {
84ec0864 ML	113	bat_dbg(DBG_BATMAN, bat_priv,
84ec0864 ML	114	"batman packet queue full\n");
19dae340 SW	115	return;
	116	}
	117	}
	118
5beef3c9	119	forw_packet_aggr = kmalloc(sizeof(struct forw_packet), GFP_ATOMIC);
19dae340 SW	120	if (!forw_packet_aggr) {
19dae340 SW	121	if (!own_packet)
7d02674f	122	atomic_inc(&bat_priv->batman_queue_left);
5beef3c9	123	return;
19dae340	124	}
5beef3c9	125
15f00687 ML	126	if ((atomic_read(&bat_priv->aggregation_enabled)) &&
	127	(packet_len < MAX_AGGREGATION_BYTES))
	128	forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES +
	129	sizeof(struct ethhdr));
	130	else
	131	forw_packet_aggr->skb = dev_alloc_skb(packet_len +
	132	sizeof(struct ethhdr));
	133
b706007b	134	if (!forw_packet_aggr->skb) {
19dae340	135	if (!own_packet)
7d02674f	136	atomic_inc(&bat_priv->batman_queue_left);
5beef3c9 AL	137	kfree(forw_packet_aggr);
	138	return;
	139	}
b706007b	140	skb_reserve(forw_packet_aggr->skb, sizeof(struct ethhdr));
5beef3c9 AL	141
	142	INIT_HLIST_NODE(&forw_packet_aggr->list);
	143
b706007b	144	skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
5beef3c9	145	forw_packet_aggr->packet_len = packet_len;
b706007b	146	memcpy(skb_buff, packet_buff, packet_len);
5beef3c9 AL	147
	148	forw_packet_aggr->own = own_packet;
	149	forw_packet_aggr->if_incoming = if_incoming;
	150	forw_packet_aggr->num_packets = 0;
	151	forw_packet_aggr->direct_link_flags = 0;
	152	forw_packet_aggr->send_time = send_time;
	153
	154	/* save packet direct link flag status */
	155	if (direct_link)
	156	forw_packet_aggr->direct_link_flags \|= 1;
	157
	158	/* add new packet to packet list */
8c70f138 ML	159	spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags);
	160	hlist_add_head(&forw_packet_aggr->list, &bat_priv->forw_bat_list);
	161	spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags);
5beef3c9 AL	162
	163	/* start timer for this packet */
	164	INIT_DELAYED_WORK(&forw_packet_aggr->delayed_work,
	165	send_outstanding_bat_packet);
	166	queue_delayed_work(bat_event_workqueue,
	167	&forw_packet_aggr->delayed_work,
	168	send_time - jiffies);
	169	}
	170
	171	/* aggregate a new packet into the existing aggregation */
	172	static void aggregate(struct forw_packet *forw_packet_aggr,
	173	unsigned char *packet_buff,
	174	int packet_len,
	175	bool direct_link)
	176	{
b706007b SE	177	unsigned char *skb_buff;
	178
	179	skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
	180	memcpy(skb_buff, packet_buff, packet_len);
5beef3c9 AL	181	forw_packet_aggr->packet_len += packet_len;
	182	forw_packet_aggr->num_packets++;
	183
	184	/* save packet direct link flag status */
	185	if (direct_link)
	186	forw_packet_aggr->direct_link_flags \|=
	187	(1 << forw_packet_aggr->num_packets);
	188	}
	189
14741240 ML	190	void add_bat_packet_to_list(struct bat_priv *bat_priv,
14741240 ML	191	unsigned char *packet_buff, int packet_len,
5beef3c9	192	struct batman_if *if_incoming, char own_packet,
14741240	193	unsigned long send_time)
5beef3c9 AL	194	{
	195	/**
	196	* _aggr -> pointer to the packet we want to aggregate with
	197	* _pos -> pointer to the position in the queue
	198	*/
	199	struct forw_packet forw_packet_aggr = NULL, forw_packet_pos = NULL;
	200	struct hlist_node *tmp_node;
	201	struct batman_packet *batman_packet =
	202	(struct batman_packet *)packet_buff;
	203	bool direct_link = batman_packet->flags & DIRECTLINK ? 1 : 0;
e7017195	204	unsigned long flags;
5beef3c9 AL	205
5beef3c9 AL	206	/* find position for the packet in the forward queue */
8c70f138	207	spin_lock_irqsave(&bat_priv->forw_bat_list_lock, flags);
5beef3c9	208	/* own packets are not to be aggregated */
47fdf097	209	if ((atomic_read(&bat_priv->aggregation_enabled)) && (!own_packet)) {
8c70f138 ML	210	hlist_for_each_entry(forw_packet_pos, tmp_node,
8c70f138 ML	211	&bat_priv->forw_bat_list, list) {
5beef3c9 AL	212	if (can_aggregate_with(batman_packet,
	213	packet_len,
	214	send_time,
	215	direct_link,
	216	if_incoming,
	217	forw_packet_pos)) {
	218	forw_packet_aggr = forw_packet_pos;
	219	break;
	220	}
	221	}
	222	}
	223
	224	/* nothing to aggregate with - either aggregation disabled or no
	225	* suitable aggregation packet found */
	226	if (forw_packet_aggr == NULL) {
	227	/* the following section can run without the lock */
8c70f138	228	spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags);
bd13b616 ML	229
	230	/**
	231	* if we could not aggregate this packet with one of the others
	232	* we hold it back for a while, so that it might be aggregated
	233	* later on
	234	*/
	235	if ((!own_packet) &&
47fdf097	236	(atomic_read(&bat_priv->aggregation_enabled)))
bd13b616 ML	237	send_time += msecs_to_jiffies(MAX_AGGREGATION_MS);
bd13b616 ML	238
5beef3c9 AL	239	new_aggregated_packet(packet_buff, packet_len,
	240	send_time, direct_link,
	241	if_incoming, own_packet);
	242	} else {
	243	aggregate(forw_packet_aggr,
	244	packet_buff, packet_len,
	245	direct_link);
8c70f138	246	spin_unlock_irqrestore(&bat_priv->forw_bat_list_lock, flags);
5beef3c9 AL	247	}
	248	}
	249
	250	/* unpack the aggregated packets and process them one by one */
	251	void receive_aggr_bat_packet(struct ethhdr ethhdr, unsigned char packet_buff,
	252	int packet_len, struct batman_if *if_incoming)
	253	{
	254	struct batman_packet *batman_packet;
	255	int buff_pos = 0;
	256	unsigned char *hna_buff;
	257
	258	batman_packet = (struct batman_packet *)packet_buff;
	259
1bc80e95	260	do {
cf2d72ec	261	/* network to host order for our 32bit seqno, and the
5beef3c9	262	orig_interval. */
cf2d72ec	263	batman_packet->seqno = ntohl(batman_packet->seqno);
5beef3c9 AL	264
	265	hna_buff = packet_buff + buff_pos + BAT_PACKET_LEN;
	266	receive_bat_packet(ethhdr, batman_packet,
	267	hna_buff, hna_len(batman_packet),
	268	if_incoming);
	269
	270	buff_pos += BAT_PACKET_LEN + hna_len(batman_packet);
	271	batman_packet = (struct batman_packet *)
	272	(packet_buff + buff_pos);
1bc80e95 ML	273	} while (aggregated_packet(buff_pos, packet_len,
1bc80e95 ML	274	batman_packet->num_hna));
5beef3c9	275	}