[B.A.T.M.A.N.] maint tree mixup...
by Andrew Lunn
Hi Folks
It could be i'm doing something stupid here. If so, please tell me...
I'm preparing a patchset for linux. I've run into some problems.
You can see the patches to be included here:
http://git.open-mesh.org/?p=batman-adv;a=shortlog;h=refs/heads/maint
The one which is causing me problems is:
2010-03-20 Marek Lindner batman-adv: fix aggregation timing bug
When i add this patch and then try to compile i get:
drivers/staging/batman-adv/aggregation.c:207:35: error: undefined identifier 'bat_priv'
the code being:
(atomic_read(&bat_priv->aggregation_enabled)))
However, if you look at the patch:
2010-04-06 Marek Lindner batman-adv: convert multiple /proc files to use sysfs
which comes about 16 days later you see:
--- a/types.h
+++ b/types.h
@@ -82,6 +82,8 @@ struct neigh_node {
struct bat_priv {
struct net_device_stats stats;
+ atomic_t aggregation_enabled;
+ struct kobject *mesh_obj;
};
So it looks to me these patches have got out of order.....
Any ideas what happened?
Thanks
Andrew
10 years
[B.A.T.M.A.N.] [PATCH 0/3] Staging: Batman-adv: Bug fixes for 2.6.34-rc2.
by Andrew Lunn
Hi Greg
Here are three patches against 2.6.34-rc2 which we would like including
into the next -rc kernel. All three are bug fixes, with the first being a
regression relative to 2.6.33 and the second two being older bugs, prescent
in 2.6.33.
Thanks
Andrew
Andrew Lunn (1):
Staging: batman-adv: don't have interrupts disabled while sending.
Linus Luessing (1):
Staging: batman-adv: Fix VIS output bug for secondary interfaces
Linus Lüssing (1):
Staging: batman-adv: Fixing wrap-around bug in vis
drivers/staging/batman-adv/proc.c | 51 ++++++---
drivers/staging/batman-adv/vis.c | 235 +++++++++++++++++++++++++------------
drivers/staging/batman-adv/vis.h | 8 +-
3 files changed, 202 insertions(+), 92 deletions(-)
10 years
[B.A.T.M.A.N.] Checkpatch cleanups
by Sven Eckelmann
Hi,
last year in December we decided that it is not worth to strictly follow the
80 chars per line rule in the linux coding style document. But after receiving
3 patches in the last month to fix such or similar problems (which could not
be merged due to other changes already applied to both branches) I want to
propose following patches which try to resolve these problems in files which
get submitted to the mainline kernel.
For trunk:
[PATCH-trunk 1/2] batman-adv: Fix whitespace problems criticized by checkpatch.pl
[PATCH-trunk 2/2] batman-adv: Reduce max characters on a line to 80
For maint branch:
[PATCH-maint 1/2] batman-adv: Fix whitespace problems criticized by checkpatch.pl
[PATCH-maint 2/2] batman-adv: Reduce max characters on a line to 80
Best regards,
Sven
10 years
[B.A.T.M.A.N.] [PATCH] 32bit sequence number and TTL for broadcasts
by Simon Wunderlich
This patch changes the sequence number range from 8 or 16 bit to 32 bit.
This should avoid problems with the sequence number sliding window algorithm
which we had seen in the past for broadcast floods or malicious packet
injections. We can not assure 100% security with this patch, but it is quite
an improvement over the old 16 bit sequence numbers:
* expected window size can be increased (4096 -> 65536)
* 64k packets in the right order would now be needed to cause a loop,
which seems practically impossible.
Furthermore, a TTL field has been added to the broadcast packet type, just to
make sure.
These changes required to increase the compatibility level once again. It
should therefore only applied to the upcoming 0.3 branch.
Signed-off-by: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de>
---
Index: a/batman-adv-kernelland/vis.c
===================================================================
--- a/batman-adv-kernelland/vis.c (revision 1639)
+++ a/batman-adv-kernelland/vis.c (working copy)
@@ -309,7 +309,8 @@
old_info = hash_find(vis_hash, &search_elem);
if (old_info != NULL) {
- if (!seq_after(vis_packet->seqno, old_info->packet.seqno)) {
+ if (!seq_after(ntohl(vis_packet->seqno),
+ ntohl(old_info->packet.seqno))) {
if (old_info->packet.seqno == vis_packet->seqno) {
recv_list_add(&old_info->recv_list,
vis_packet->sender_orig);
@@ -477,7 +478,7 @@
spin_lock_irqsave(&orig_hash_lock, flags);
memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
info->packet.ttl = TTL;
- info->packet.seqno++;
+ info->packet.seqno = htonl(ntohl(info->packet.seqno) + 1);
info->packet.entries = 0;
if (info->packet.vis_type == VIS_TYPE_CLIENT_UPDATE) {
Index: a/batman-adv-kernelland/types.h
===================================================================
--- a/batman-adv-kernelland/types.h (revision 1639)
+++ a/batman-adv-kernelland/types.h (working copy)
@@ -39,7 +39,7 @@
char if_status;
char addr_str[ETH_STR_LEN];
struct net_device *net_dev;
- atomic_t seqno;
+ atomic64_t seqno;
unsigned char *packet_buff;
int packet_len;
struct kobject *hardif_obj;
@@ -63,10 +63,10 @@
uint8_t flags; /* for now only VIS_SERVER flag. */
unsigned char *hna_buff;
int16_t hna_buff_len;
- uint16_t last_real_seqno; /* last and best known squence number */
+ uint32_t last_real_seqno; /* last and best known sequence number */
uint8_t last_ttl; /* ttl of last received packet */
TYPE_OF_WORD bcast_bits[NUM_WORDS];
- uint16_t last_bcast_seqno; /* last broadcast sequence number received by this host */
+ uint32_t last_bcast_seqno; /* last received broadcast seqno */
struct list_head neigh_list;
struct {
uint8_t candidates; /* how many candidates are available */
Index: a/batman-adv-kernelland/packet.h
===================================================================
--- a/batman-adv-kernelland/packet.h (revision 1639)
+++ a/batman-adv-kernelland/packet.h (working copy)
@@ -28,7 +28,7 @@
#define BAT_VIS 0x05
/* this file is included by batctl which needs these defines */
-#define COMPAT_VERSION 9
+#define COMPAT_VERSION 10
#define DIRECTLINK 0x40
#define VIS_SERVER 0x20
#define PRIMARIES_FIRST_HOP 0x10
@@ -49,7 +49,7 @@
uint8_t version; /* batman version field */
uint8_t flags; /* 0x40: DIRECTLINK flag, 0x20 VIS_SERVER flag... */
uint8_t tq;
- uint16_t seqno;
+ uint32_t seqno;
uint8_t orig[6];
uint8_t prev_sender[6];
uint8_t ttl;
@@ -99,15 +99,16 @@
uint8_t packet_type;
uint8_t version; /* batman version field */
uint8_t orig[6];
- uint16_t seqno;
+ uint8_t ttl;
+ uint32_t seqno;
} __attribute__((packed));
struct vis_packet {
uint8_t packet_type;
uint8_t version; /* batman version field */
uint8_t vis_type; /* which type of vis-participant sent this? */
- uint8_t seqno; /* sequence number */
uint8_t entries; /* number of entries behind this struct */
+ uint32_t seqno; /* sequence number */
uint8_t ttl; /* TTL */
uint8_t vis_orig[6]; /* originator that informs about its
* neighbors */
Index: a/batman-adv-kernelland/bitarray.c
===================================================================
--- a/batman-adv-kernelland/bitarray.c (revision 1639)
+++ a/batman-adv-kernelland/bitarray.c (working copy)
@@ -24,10 +24,10 @@
/* returns true if the corresponding bit in the given seq_bits indicates true
* and curr_seqno is within range of last_seqno */
-uint8_t get_bit_status(TYPE_OF_WORD *seq_bits, uint16_t last_seqno,
- uint16_t curr_seqno)
+uint8_t get_bit_status(TYPE_OF_WORD *seq_bits, uint32_t last_seqno,
+ uint32_t curr_seqno)
{
- int16_t diff, word_offset, word_num;
+ int32_t diff, word_offset, word_num;
diff = last_seqno - curr_seqno;
if (diff < 0 || diff >= TQ_LOCAL_WINDOW_SIZE) {
@@ -125,7 +125,7 @@
* 1 if the window was moved (either new or very old)
* 0 if the window was not moved/shifted.
*/
-char bit_get_packet(TYPE_OF_WORD *seq_bits, int16_t seq_num_diff,
+char bit_get_packet(TYPE_OF_WORD *seq_bits, int32_t seq_num_diff,
int8_t set_mark)
{
/* sequence number is slightly older. We already got a sequence number
Index: a/batman-adv-kernelland/bitarray.h
===================================================================
--- a/batman-adv-kernelland/bitarray.h (revision 1639)
+++ a/batman-adv-kernelland/bitarray.h (working copy)
@@ -26,8 +26,8 @@
/* returns true if the corresponding bit in the given seq_bits indicates true
* and curr_seqno is within range of last_seqno */
-uint8_t get_bit_status(TYPE_OF_WORD *seq_bits, uint16_t last_seqno,
- uint16_t curr_seqno);
+uint8_t get_bit_status(TYPE_OF_WORD *seq_bits, uint32_t last_seqno,
+ uint32_t curr_seqno);
/* turn corresponding bit on, so we can remember that we got the packet */
void bit_mark(TYPE_OF_WORD *seq_bits, int32_t n);
@@ -38,7 +38,7 @@
/* receive and process one packet, returns 1 if received seq_num is considered
* new, 0 if old */
-char bit_get_packet(TYPE_OF_WORD *seq_bits, int16_t seq_num_diff,
+char bit_get_packet(TYPE_OF_WORD *seq_bits, int32_t seq_num_diff,
int8_t set_mark);
/* count the hamming weight, how many good packets did we receive? */
Index: a/batman-adv-kernelland/send.c
===================================================================
--- a/batman-adv-kernelland/send.c (revision 1639)
+++ a/batman-adv-kernelland/send.c (working copy)
@@ -153,7 +153,7 @@
"%s %spacket (originator %pM, seqno %d, TQ %d, TTL %d, IDF %s) on interface %s [%s]\n",
fwd_str,
(packet_num > 0 ? "aggregated " : ""),
- batman_packet->orig, ntohs(batman_packet->seqno),
+ batman_packet->orig, ntohl(batman_packet->seqno),
batman_packet->tq, batman_packet->ttl,
(batman_packet->flags & DIRECTLINK ?
"on" : "off"),
@@ -196,7 +196,7 @@
bat_dbg(DBG_BATMAN,
"%s packet (originator %pM, seqno %d, TTL %d) on interface %s [%s]\n",
(forw_packet->own ? "Sending own" : "Forwarding"),
- batman_packet->orig, ntohs(batman_packet->seqno),
+ batman_packet->orig, ntohl(batman_packet->seqno),
batman_packet->ttl, forw_packet->if_incoming->dev,
forw_packet->if_incoming->addr_str);
@@ -275,7 +275,8 @@
batman_packet = (struct batman_packet *)batman_if->packet_buff;
/* change sequence number to network order */
- batman_packet->seqno = htons((uint16_t)atomic_read(&batman_if->seqno));
+ batman_packet->seqno =
+ htonl((uint32_t)atomic64_read(&batman_if->seqno));
if (vis_server == VIS_TYPE_SERVER_SYNC)
batman_packet->flags |= VIS_SERVER;
@@ -288,8 +289,7 @@
else
batman_packet->gw_flags = 0;
- /* could be read by receive_bat_packet() */
- atomic_inc(&batman_if->seqno);
+ atomic64_inc(&batman_if->seqno);
slide_own_bcast_window(batman_if);
send_time = own_send_time(bat_priv);
@@ -343,7 +343,7 @@
in_tq, tq_avg, batman_packet->tq, in_ttl - 1,
batman_packet->ttl);
- batman_packet->seqno = htons(batman_packet->seqno);
+ batman_packet->seqno = htonl(batman_packet->seqno);
/* switch of primaries first hop flag when forwarding */
batman_packet->flags &= ~PRIMARIES_FIRST_HOP;
@@ -397,6 +397,7 @@
int add_bcast_packet_to_list(struct sk_buff *skb)
{
struct forw_packet *forw_packet;
+ struct bcast_packet *bcast_packet;
/* FIXME: each batman_if will be attached to a softif */
struct bat_priv *bat_priv = netdev_priv(soft_device);
@@ -414,6 +415,10 @@
if (!skb)
goto packet_free;
+ /* as we have a copy now, it is safe to decrease the TTL */
+ bcast_packet = (struct bcast_packet *)skb->data;
+ bcast_packet->ttl--;
+
skb_reset_mac_header(skb);
forw_packet->skb = skb;
Index: a/batman-adv-kernelland/soft-interface.c
===================================================================
--- a/batman-adv-kernelland/soft-interface.c (revision 1639)
+++ a/batman-adv-kernelland/soft-interface.c (working copy)
@@ -32,7 +32,7 @@
#include <linux/etherdevice.h>
#include "compat.h"
-static uint16_t bcast_seqno = 1; /* give own bcast messages seq numbers to avoid
+static uint32_t bcast_seqno = 1; /* give own bcast messages seq numbers to avoid
* broadcast storms */
static int32_t skb_packets;
static int32_t skb_bad_packets;
@@ -214,6 +214,7 @@
bcast_packet = (struct bcast_packet *)skb->data;
bcast_packet->version = COMPAT_VERSION;
+ bcast_packet->ttl = TTL;
/* batman packet type: broadcast */
bcast_packet->packet_type = BAT_BCAST;
@@ -223,7 +224,7 @@
memcpy(bcast_packet->orig, mainIfAddr, ETH_ALEN);
/* set broadcast sequence number */
- bcast_packet->seqno = htons(bcast_seqno);
+ bcast_packet->seqno = htonl(bcast_seqno);
/* broadcast packet. on success, increase seqno. */
if (add_bcast_packet_to_list(skb) == NETDEV_TX_OK)
Index: a/batman-adv-kernelland/hard-interface.c
===================================================================
--- a/batman-adv-kernelland/hard-interface.c (revision 1639)
+++ a/batman-adv-kernelland/hard-interface.c (working copy)
@@ -261,7 +261,7 @@
batman_if->if_status = IF_INACTIVE;
orig_hash_add_if(batman_if, bat_priv->num_ifaces);
- atomic_set(&batman_if->seqno, 1);
+ atomic64_set(&batman_if->seqno, 1);
printk(KERN_INFO "batman-adv:Adding interface: %s\n", batman_if->dev);
if (hardif_is_iface_up(batman_if))
Index: a/batman-adv-kernelland/routing.c
===================================================================
--- a/batman-adv-kernelland/routing.c (revision 1639)
+++ a/batman-adv-kernelland/routing.c (working copy)
@@ -323,7 +323,7 @@
* 0 if the packet is to be accepted
* 1 if the packet is to be ignored.
*/
-static int window_protected(int16_t seq_num_diff,
+static int window_protected(int32_t seq_num_diff,
unsigned long *last_reset)
{
if ((seq_num_diff <= -TQ_LOCAL_WINDOW_SIZE)
@@ -357,7 +357,7 @@
struct orig_node *orig_node;
struct neigh_node *tmp_neigh_node;
char is_duplicate = 0;
- int16_t seq_diff;
+ int32_t seq_diff;
int need_update = 0;
int set_mark;
@@ -526,7 +526,7 @@
char is_my_addr = 0, is_my_orig = 0, is_my_oldorig = 0;
char is_broadcast = 0, is_bidirectional, is_single_hop_neigh;
char is_duplicate;
- unsigned short if_incoming_seqno;
+ uint32_t if_incoming_seqno;
/* Silently drop when the batman packet is actually not a
* correct packet.
@@ -544,7 +544,7 @@
return;
/* could be changed by schedule_own_packet() */
- if_incoming_seqno = atomic_read(&if_incoming->seqno);
+ if_incoming_seqno = atomic64_read(&if_incoming->seqno);
has_directlink_flag = (batman_packet->flags & DIRECTLINK ? 1 : 0);
@@ -1124,7 +1124,7 @@
struct bcast_packet *bcast_packet;
struct ethhdr *ethhdr;
int hdr_size = sizeof(struct bcast_packet);
- int16_t seq_diff;
+ int32_t seq_diff;
unsigned long flags;
/* drop packet if it has not necessary minimum size */
@@ -1151,6 +1151,9 @@
if (is_my_mac(bcast_packet->orig))
return NET_RX_DROP;
+ if (bcast_packet->ttl < 2)
+ return NET_RX_DROP;
+
spin_lock_irqsave(&orig_hash_lock, flags);
orig_node = ((struct orig_node *)
hash_find(orig_hash, bcast_packet->orig));
@@ -1163,12 +1166,12 @@
/* check whether the packet is a duplicate */
if (get_bit_status(orig_node->bcast_bits,
orig_node->last_bcast_seqno,
- ntohs(bcast_packet->seqno))) {
+ ntohl(bcast_packet->seqno))) {
spin_unlock_irqrestore(&orig_hash_lock, flags);
return NET_RX_DROP;
}
- seq_diff = ntohs(bcast_packet->seqno) - orig_node->last_bcast_seqno;
+ seq_diff = ntohl(bcast_packet->seqno) - orig_node->last_bcast_seqno;
/* check whether the packet is old and the host just restarted. */
if (window_protected(seq_diff, &orig_node->bcast_seqno_reset)) {
@@ -1179,7 +1182,7 @@
/* mark broadcast in flood history, update window position
* if required. */
if (bit_get_packet(orig_node->bcast_bits, seq_diff, 1))
- orig_node->last_bcast_seqno = ntohs(bcast_packet->seqno);
+ orig_node->last_bcast_seqno = ntohl(bcast_packet->seqno);
spin_unlock_irqrestore(&orig_hash_lock, flags);
/* rebroadcast packet */
Index: a/batman-adv-kernelland/aggregation.c
===================================================================
--- a/batman-adv-kernelland/aggregation.c (revision 1639)
+++ a/batman-adv-kernelland/aggregation.c (working copy)
@@ -254,9 +254,9 @@
while (aggregated_packet(buff_pos, packet_len,
batman_packet->num_hna)) {
- /* network to host order for our 16bit seqno, and the
+ /* network to host order for our 32bit seqno, and the
orig_interval. */
- batman_packet->seqno = ntohs(batman_packet->seqno);
+ batman_packet->seqno = ntohl(batman_packet->seqno);
hna_buff = packet_buff + buff_pos + BAT_PACKET_LEN;
receive_bat_packet(ethhdr, batman_packet,
Index: a/batman-adv-kernelland/main.h
===================================================================
--- a/batman-adv-kernelland/main.h (revision 1639)
+++ a/batman-adv-kernelland/main.h (working copy)
@@ -69,7 +69,7 @@
#define MAX_AGGREGATION_MS 100
#define RESET_PROTECTION_MS 30000
-#define EXPECTED_SEQNO_RANGE 4096
+#define EXPECTED_SEQNO_RANGE 65536
/* don't reset again within 30 seconds */
#define MODULE_INACTIVE 0
10 years, 1 month
[B.A.T.M.A.N.] [PATCH] batman-adv: Update pointer to ethhdr after skb_copy
by Sven Eckelmann
We must ensure that all pointer to a socket buffer are updated when we
copy a socket buffer and free our reference to the old one.
Another part of the kernel could also free its reference which maybe
removes the buffer completely. In that situation we would would feed
wrong information to the routing algorithm after the memory area is
written again by someone else.
Signed-off-by: Sven Eckelmann <sven.eckelmann(a)gmx.de>
---
batman-adv-kernelland/routing.c | 5 +++++
1 files changed, 5 insertions(+), 0 deletions(-)
diff --git a/batman-adv-kernelland/routing.c b/batman-adv-kernelland/routing.c
index d717999..53749d3 100644
--- a/batman-adv-kernelland/routing.c
+++ b/batman-adv-kernelland/routing.c
@@ -747,6 +747,7 @@ int recv_bat_packet(struct sk_buff *skb,
skb = skb_copy(skb, GFP_ATOMIC);
if (!skb)
return NET_RX_DROP;
+ ethhdr = (struct ethhdr *)skb_mac_header(skb);
kfree_skb(skb_old);
}
@@ -805,6 +806,7 @@ static int recv_my_icmp_packet(struct sk_buff *skb, size_t icmp_len)
if (!skb)
return NET_RX_DROP;
icmp_packet = (struct icmp_packet_rr *)skb->data;
+ ethhdr = (struct ethhdr *)skb_mac_header(skb);
kfree_skb(skb_old);
}
@@ -865,6 +867,7 @@ static int recv_icmp_ttl_exceeded(struct sk_buff *skb, size_t icmp_len)
if (!skb)
return NET_RX_DROP;
icmp_packet = (struct icmp_packet *) skb->data;
+ ethhdr = (struct ethhdr *)skb_mac_header(skb);
kfree_skb(skb_old);
}
@@ -960,6 +963,7 @@ int recv_icmp_packet(struct sk_buff *skb)
if (!skb)
return NET_RX_DROP;
icmp_packet = (struct icmp_packet_rr *)skb->data;
+ ethhdr = (struct ethhdr *)skb_mac_header(skb);
kfree_skb(skb_old);
}
@@ -1106,6 +1110,7 @@ int recv_unicast_packet(struct sk_buff *skb)
if (!skb)
return NET_RX_DROP;
unicast_packet = (struct unicast_packet *) skb->data;
+ ethhdr = (struct ethhdr *)skb_mac_header(skb);
kfree_skb(skb_old);
}
--
1.7.0.5
10 years, 1 month
[B.A.T.M.A.N.] Security & node authentication in BATMAN network
by Adrian Byszuk
Hello,
I'm currently working on project (part of my Bachelor work) which will use to
transfer very sensitive data over the network, and I'd like to use mesh
networks to transfer this data. Additionally, it should also be possible for
"normal people" to connect to this network (e.g. to surf internet).
Preliminary, I've chosen BATMAN to build this network. But I've got a few
questions regarding security of this solution:
1. Does BATMAN provide any method of *authenticating* nodes?
As I've said earlier, sometimes transferred data will be highly sensitive (for
example: information of patients health in hospital), so it's absolutely
critical to not allow leaking this information. I can imagine situation when
some fake nodes claim "Hey, I'm the server collecting this data"...
I think this is also important when someone would try to destroy our mesh
network by placing some fake nodes in it.
2. If point nr one isn't possible, maybe there is some other way to ensure
security? I don't know too much about security or cryptography, but I can
think of solutions such as openVPN or IPsec.
Generally, the goal is to assert security of transmitting some data *without*
losing open characteristics of mesh network.
I will very thankful for any answers.
Kind regards,
Adrian
10 years, 1 month
[B.A.T.M.A.N.] Patch batman-adv for kernel 2.6.15
by Franz Böhm
Hi,
I am trying to get batman-adv (kernelland) running on Ubiquiti Networks
hardware. Unfortunately the Ubiquiti SDK uses kernel 2.6.15 and
batman-adv needs at least 2.6.20. I did have some success in patching
and running batman-adv-kernelland 0.1 (r1176). I would of course prefer
using batman-adv 0.2 but I do have problems implementing the older
kernel workqueue API.
Perhaps someone can give me a hint on porting for example this function
from send.c to the old workqueue API.
void send_outstanding_bat_packet(struct work_struct *work)
{
struct delayed_work *delayed_work =
container_of(work, struct delayed_work, work);
struct forw_packet *forw_packet =
container_of(delayed_work, struct forw_packet, delayed_work);
unsigned long flags;
spin_lock_irqsave(&forw_bat_list_lock, flags);
hlist_del(&forw_packet->list);
spin_unlock_irqrestore(&forw_bat_list_lock, flags);
send_packet(forw_packet);
/**
* we have to have at least one packet in the queue
* to determine the queues wake up time unless we are
* shutting down
*/
if ((forw_packet->own) &&
(atomic_read(&module_state) != MODULE_DEACTIVATING))
schedule_own_packet(forw_packet->if_incoming);
forw_packet_free(forw_packet);
}
Kind regards,
Franz
10 years, 1 month
[B.A.T.M.A.N.] [PATCH] batman-adv: Limit queue lengths for batman and broadcast packets
by Simon Wunderlich
This patch limits the queue lengths of batman and broadcast packets. BATMAN
packets are held back for aggregation and jittered to avoid interferences.
Broadcast packets are stored to be sent out multiple times to increase
the probability to be received by other nodes in lossy environments.
Especially in extreme cases like broadcast storms, the queues have been seen
to run full, eating up all the memory and triggering the infamous OOM killer.
With the queue length limits introduced in this patch, this problem is
avoided.
Each queue is limited to 256 entries for now, resulting in 1 MB of maximum
space available in total for typical setups (assuming one packet including
overhead does not require more than 2000 byte). This should also be reasonable
for smaller routers, otherwise the defines can be tweaked later.
Signed-off-by: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de>
---
Index: a/batman-adv-kernelland/send.c
===================================================================
--- a/batman-adv-kernelland/send.c (revision 1616)
+++ a/batman-adv-kernelland/send.c (working copy)
@@ -382,12 +382,21 @@
{
struct forw_packet *forw_packet;
+ if (atomic_dec_and_test(&bcast_queue_left)) {
+ bat_dbg(DBG_BATMAN, "bcast packet queue full\n");
+ atomic_inc(&bcast_queue_left);
+ return;
+ }
+
forw_packet = kmalloc(sizeof(struct forw_packet), GFP_ATOMIC);
- if (!forw_packet)
+ if (!forw_packet) {
+ atomic_inc(&bcast_queue_left);
return;
+ }
skb = skb_copy(skb, GFP_ATOMIC);
if (!skb) {
+ atomic_inc(&bcast_queue_left);
kfree(forw_packet);
return;
}
@@ -435,8 +444,10 @@
if ((forw_packet->num_packets < 3) &&
(atomic_read(&module_state) != MODULE_DEACTIVATING))
_add_bcast_packet_to_list(forw_packet, ((5 * HZ) / 1000));
- else
+ else {
forw_packet_free(forw_packet);
+ atomic_inc(&bcast_queue_left);
+ }
}
void send_outstanding_bat_packet(struct work_struct *work)
@@ -462,6 +473,10 @@
(atomic_read(&module_state) != MODULE_DEACTIVATING))
schedule_own_packet(forw_packet->if_incoming);
+ /* don't count own packet */
+ if (!forw_packet->own)
+ atomic_inc(&batman_queue_left);
+
forw_packet_free(forw_packet);
}
Index: a/batman-adv-kernelland/main.c
===================================================================
--- a/batman-adv-kernelland/main.c (revision 1616)
+++ a/batman-adv-kernelland/main.c (working copy)
@@ -46,6 +46,9 @@
atomic_t originator_interval;
atomic_t vis_interval;
+atomic_t bcast_queue_left;
+atomic_t batman_queue_left;
+
int16_t num_hna;
int16_t num_ifs;
@@ -85,6 +88,8 @@
atomic_set(&originator_interval, 1000);
atomic_set(&vis_interval, 1000);/* TODO: raise this later, this is only
* for debugging now. */
+ atomic_set(&bcast_queue_left, BCAST_QUEUE_LEN);
+ atomic_set(&batman_queue_left, BATMAN_QUEUE_LEN);
/* the name should not be longer than 10 chars - see
* http://lwn.net/Articles/23634/ */
Index: a/batman-adv-kernelland/aggregation.c
===================================================================
--- a/batman-adv-kernelland/aggregation.c (revision 1616)
+++ a/batman-adv-kernelland/aggregation.c (working copy)
@@ -106,13 +106,27 @@
struct forw_packet *forw_packet_aggr;
unsigned long flags;
+ /* own packet should always be scheduled */
+ if (!own_packet) {
+ if (atomic_dec_and_test(&batman_queue_left)) {
+ bat_dbg(DBG_BATMAN, "batman packet queue full\n");
+ atomic_inc(&batman_queue_left);
+ return;
+ }
+ }
+
forw_packet_aggr = kmalloc(sizeof(struct forw_packet), GFP_ATOMIC);
- if (!forw_packet_aggr)
+ if (!forw_packet_aggr) {
+ if (!own_packet)
+ atomic_inc(&batman_queue_left);
return;
+ }
forw_packet_aggr->packet_buff = kmalloc(MAX_AGGREGATION_BYTES,
GFP_ATOMIC);
if (!forw_packet_aggr->packet_buff) {
+ if (!own_packet)
+ atomic_inc(&batman_queue_left);
kfree(forw_packet_aggr);
return;
}
Index: a/batman-adv-kernelland/main.h
===================================================================
--- a/batman-adv-kernelland/main.h (revision 1616)
+++ a/batman-adv-kernelland/main.h (working copy)
@@ -70,6 +70,8 @@
#define MODULE_ACTIVE 1
#define MODULE_DEACTIVATING 2
+#define BCAST_QUEUE_LEN 256
+#define BATMAN_QUEUE_LEN 256
/*
* Debug Messages
@@ -133,6 +135,8 @@
extern atomic_t originator_interval;
extern atomic_t vis_interval;
+extern atomic_t bcast_queue_left;
+extern atomic_t batman_queue_left;
extern int16_t num_hna;
extern int16_t num_ifs;
10 years, 1 month
[B.A.T.M.A.N.] [PATCH] batman-adv: Reorganize sequence number handling
by Simon Wunderlich
BATMAN and broadcast packets are tracked with a sequence number window of
currently 64 entries to measure and avoid duplicates. Packets which have a
sequence number smaller than the newest received packet minus 64 are not
within this sequence number window anymore and are called "old packets" from
now on.
When old packets are received, the routing code assumes that the host of the
originator has been restarted. This assumption however might be wrong as
packets can also be delayed by NIC drivers, e.g. because of long queues or
collision detection in dense WiFi environments. This behaviour can be
reproduced by doing a broadcast ping flood in a dense node environment.
The effect is that the sequence number window is jumping forth and back,
accepting and forwarding any packet (because packets are assumed to be "new")
and causing loops.
To overcome this problem, the sequence number handling has been reorganized.
When an old packet is received, the window is reset back only once. Other old
packets are dropped for (currently) 30 seconds to "protect" the new sequence
number and avoid the hopping as described above.
The reorganization brings some code cleanups (at least i hope you feel the
same) and also fixes a bug in count_real_packets() which falsely updated
the last_real_seqno for slightly older packets within the seqno window
if they are no duplicates.
Signed-off-by: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de>
Acked-by: Linus Luessing <linus.luessing(a)web.de>
Index: a/batman-adv-kernelland/types.h
===================================================================
--- a/batman-adv-kernelland/types.h (revision 1616)
+++ a/batman-adv-kernelland/types.h (working copy)
@@ -55,6 +55,10 @@
uint8_t tq_own;
int tq_asym_penalty;
unsigned long last_valid; /* when last packet from this node was received */
+ unsigned long bcast_seqno_reset; /* time when the broadcast
+ seqno window was reset. */
+ unsigned long batman_seqno_reset;/* time when the batman seqno
+ window was reset. */
uint8_t gw_flags; /* flags related to gateway class */
uint8_t flags; /* for now only VIS_SERVER flag. */
unsigned char *hna_buff;
Index: a/batman-adv-kernelland/bitarray.c
===================================================================
--- a/batman-adv-kernelland/bitarray.c (revision 1616)
+++ a/batman-adv-kernelland/bitarray.c (working copy)
@@ -111,48 +111,74 @@
seq_bits[i] = 0;
}
+static void bit_reset_window(TYPE_OF_WORD *seq_bits)
+{
+ int i;
+ for (i = 0; i < NUM_WORDS; i++)
+ seq_bits[i] = 0;
+}
-/* receive and process one packet, returns 1 if received seq_num is considered
- * new, 0 if old */
+
+/* receive and process one packet within the sequence number window.
+ *
+ * returns:
+ * 1 if the window was moved (either new or very old)
+ * 0 if the window was not moved/shifted.
+ */
char bit_get_packet(TYPE_OF_WORD *seq_bits, int16_t seq_num_diff,
int8_t set_mark)
{
- int i;
+ /* sequence number is slightly older. We already got a sequence number
+ * higher than this one, so we just mark it. */
- /* we already got a sequence number higher than this one, so we just
- * mark it. this should wrap around the integer just fine */
if ((seq_num_diff < 0) && (seq_num_diff >= -TQ_LOCAL_WINDOW_SIZE)) {
if (set_mark)
bit_mark(seq_bits, -seq_num_diff);
return 0;
}
- /* it seems we missed a lot of packets or the other host restarted */
- if ((seq_num_diff > TQ_LOCAL_WINDOW_SIZE) ||
- (seq_num_diff < -TQ_LOCAL_WINDOW_SIZE)) {
+ /* sequence number is slightly newer, so we shift the window and
+ * set the mark if required */
- if (seq_num_diff > TQ_LOCAL_WINDOW_SIZE)
- bat_dbg(DBG_BATMAN,
- "We missed a lot of packets (%i) !\n",
- seq_num_diff-1);
+ if ((seq_num_diff >= 0) && (seq_num_diff <= TQ_LOCAL_WINDOW_SIZE)) {
+ bit_shift(seq_bits, seq_num_diff);
- if (-seq_num_diff > TQ_LOCAL_WINDOW_SIZE)
- bat_dbg(DBG_BATMAN,
- "Other host probably restarted !\n");
+ if (set_mark)
+ bit_mark(seq_bits, 0);
+ return 1;
+ }
- for (i = 0; i < NUM_WORDS; i++)
- seq_bits[i] = 0;
+ /* sequence number is much newer, probably missed a lot of packets */
+ if (seq_num_diff > TQ_LOCAL_WINDOW_SIZE) {
+ bat_dbg(DBG_BATMAN,
+ "We missed a lot of packets (%i) !\n",
+ seq_num_diff - 1);
+ bit_reset_window(seq_bits);
if (set_mark)
- seq_bits[0] = 1; /* we only have the latest packet */
- } else {
- bit_shift(seq_bits, seq_num_diff);
+ bit_mark(seq_bits, 0);
+ return 1;
+ }
+ /* received a much older packet. The other host either restarted
+ * or the old packet got delayed somewhere in the network. The
+ * packet should be dropped without calling this function if the
+ * seqno window is protected. */
+
+ if (-seq_num_diff > TQ_LOCAL_WINDOW_SIZE) {
+
+ bat_dbg(DBG_BATMAN,
+ "Other host probably restarted!\n");
+
+ bit_reset_window(seq_bits);
if (set_mark)
bit_mark(seq_bits, 0);
+
+ return 1;
}
- return 1;
+ /* never reached */
+ return 0;
}
/* count the hamming weight, how many good packets did we receive? just count
Index: a/batman-adv-kernelland/originator.c
===================================================================
--- a/batman-adv-kernelland/originator.c (revision 1616)
+++ a/batman-adv-kernelland/originator.c (working copy)
@@ -141,6 +141,8 @@
orig_node->router = NULL;
orig_node->batman_if = NULL;
orig_node->hna_buff = NULL;
+ orig_node->bcast_seqno_reset = jiffies;
+ orig_node->batman_seqno_reset = jiffies;
size = num_ifs * sizeof(TYPE_OF_WORD) * NUM_WORDS;
Index: a/batman-adv-kernelland/routing.c
===================================================================
--- a/batman-adv-kernelland/routing.c (revision 1616)
+++ a/batman-adv-kernelland/routing.c (working copy)
@@ -323,6 +323,37 @@
gw_check_election(bat_priv, orig_node);
}
+/* checks whether the host restarted and is in the protection time.
+ * returns:
+ * 0 if the packet is to be accepted
+ * 1 if the packet is to be ignored.
+ */
+static int window_protected(int16_t seq_num_diff,
+ unsigned long *last_reset)
+{
+ if (-seq_num_diff > TQ_LOCAL_WINDOW_SIZE) {
+ if (time_after(jiffies, *last_reset +
+ msecs_to_jiffies(RESET_PROTECTION_MS))) {
+
+ *last_reset = jiffies;
+ bat_dbg(DBG_BATMAN,
+ "old packet received, start protection\n");
+
+ return 0;
+ } else
+ return 1;
+ }
+ return 0;
+}
+
+/* processes a batman packet for all interfaces, adjusts the sequence number and
+ * finds out whether it is a duplicate.
+ * returns:
+ * 1 the packet is a duplicate
+ * 0 the packet has not yet been received
+ * -1 the packet is old and has been received while the seqno window
+ * was protected. Caller should drop it.
+ */
static char count_real_packets(struct ethhdr *ethhdr,
struct batman_packet *batman_packet,
struct batman_if *if_incoming)
@@ -330,31 +361,41 @@
struct orig_node *orig_node;
struct neigh_node *tmp_neigh_node;
char is_duplicate = 0;
- uint16_t seq_diff;
+ int16_t seq_diff;
+ int need_update = 0;
+ int set_mark;
orig_node = get_orig_node(batman_packet->orig);
if (orig_node == NULL)
return 0;
+ seq_diff = batman_packet->seqno - orig_node->last_real_seqno;
+
+ /* signalize caller that the packet is to be dropped. */
+ if (window_protected(seq_diff, &orig_node->batman_seqno_reset))
+ return -1;
+
list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
- if (!is_duplicate)
- is_duplicate =
- get_bit_status(tmp_neigh_node->real_bits,
+ is_duplicate |= get_bit_status(tmp_neigh_node->real_bits,
orig_node->last_real_seqno,
batman_packet->seqno);
- seq_diff = batman_packet->seqno - orig_node->last_real_seqno;
+
if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) &&
(tmp_neigh_node->if_incoming == if_incoming))
- bit_get_packet(tmp_neigh_node->real_bits, seq_diff, 1);
+ set_mark = 1;
else
- bit_get_packet(tmp_neigh_node->real_bits, seq_diff, 0);
+ set_mark = 0;
+ /* if the window moved, set the update flag. */
+ need_update |= bit_get_packet(tmp_neigh_node->real_bits,
+ seq_diff, set_mark);
+
tmp_neigh_node->real_packet_count =
bit_packet_count(tmp_neigh_node->real_bits);
}
- if (!is_duplicate) {
+ if (need_update) {
bat_dbg(DBG_BATMAN, "updating last_seqno: old %d, new %d\n",
orig_node->last_real_seqno, batman_packet->seqno);
orig_node->last_real_seqno = batman_packet->seqno;
@@ -587,24 +628,27 @@
return;
}
- if (batman_packet->tq == 0) {
- count_real_packets(ethhdr, batman_packet, if_incoming);
-
- bat_dbg(DBG_BATMAN, "Drop packet: originator packet with tq equal 0\n");
- return;
- }
-
if (is_my_oldorig) {
bat_dbg(DBG_BATMAN, "Drop packet: ignoring all rebroadcast echos (sender: %pM)\n", ethhdr->h_source);
return;
}
- is_duplicate = count_real_packets(ethhdr, batman_packet, if_incoming);
-
orig_node = get_orig_node(batman_packet->orig);
if (orig_node == NULL)
return;
+ is_duplicate = count_real_packets(ethhdr, batman_packet, if_incoming);
+
+ if (is_duplicate == -1) {
+ bat_dbg(DBG_BATMAN, "Drop packet: packet within seqno protection time (sender: %pM)\n", ethhdr->h_source);
+ return;
+ }
+
+ if (batman_packet->tq == 0) {
+ bat_dbg(DBG_BATMAN, "Drop packet: originator packet with tq equal 0\n");
+ return;
+ }
+
/* avoid temporary routing loops */
if ((orig_node->router) &&
(orig_node->router->orig_node->router) &&
@@ -1088,6 +1132,7 @@
struct bcast_packet *bcast_packet;
struct ethhdr *ethhdr;
int hdr_size = sizeof(struct bcast_packet);
+ int16_t seq_diff;
unsigned long flags;
/* drop packet if it has not necessary minimum size */
@@ -1123,7 +1168,7 @@
return NET_RX_DROP;
}
- /* check flood history */
+ /* check whether the packet is a duplicate */
if (get_bit_status(orig_node->bcast_bits,
orig_node->last_bcast_seqno,
ntohs(bcast_packet->seqno))) {
@@ -1131,14 +1176,20 @@
return NET_RX_DROP;
}
- /* mark broadcast in flood history */
- if (bit_get_packet(orig_node->bcast_bits,
- ntohs(bcast_packet->seqno) -
- orig_node->last_bcast_seqno, 1))
+ seq_diff = ntohs(bcast_packet->seqno) - orig_node->last_bcast_seqno;
+
+ /* check whether the packet is old and the host just restarted. */
+ if (window_protected(seq_diff, &orig_node->bcast_seqno_reset)) {
+ spin_unlock_irqrestore(&orig_hash_lock, flags);
+ return NET_RX_DROP;
+ }
+
+ /* mark broadcast in flood history, update window position
+ * if required. */
+ if (bit_get_packet(orig_node->bcast_bits, seq_diff, 1))
orig_node->last_bcast_seqno = ntohs(bcast_packet->seqno);
spin_unlock_irqrestore(&orig_hash_lock, flags);
-
/* rebroadcast packet */
add_bcast_packet_to_list(skb);
Index: a/batman-adv-kernelland/main.h
===================================================================
--- a/batman-adv-kernelland/main.h (revision 1616)
+++ a/batman-adv-kernelland/main.h (working copy)
@@ -66,6 +66,9 @@
* forw_packet->direct_link_flags */
#define MAX_AGGREGATION_MS 100
+#define RESET_PROTECTION_MS 30000
+/* don't reset again within 30 seconds */
+
#define MODULE_INACTIVE 0
#define MODULE_ACTIVE 1
#define MODULE_DEACTIVATING 2
10 years, 1 month
[B.A.T.M.A.N.] Multiple gateways and WRT54GL's
by Patrick Beddy
Please forgive this very "newbie" question, but it is one to which I cannot find an answer on
this site:
I manage a campus network which runs a fibre backbone between critical points. I wish to
impliment a wireless mesh to link non-critical points and "fill-the-gaps" so to speak. It is thus
possible that more than one wireless point could act as a gateway to the main network. I
understand that the B.A.T.M.A.N. protocol offers the most promising means of achieving this
objective.
1: Do I have to use the Advanced version of B.A.T.M.A.N. to make this possible, of will the
"standard" version work?
2: I have purchased a few WRT54GL-EU routers with which to test the implimentation. Are
there any pre-compiled versions of the binaries available, or do I have to use a PC running
Linux to compile my own binaries?
Many thanks
==================================================
Please report any abuse sent from any Treverton user to
abuse(a)treverton.co.za
==================================================
10 years, 1 month