Reported-by: NDavid Laight <David.Laight@aculab.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

In case of a client X roaming from a generic node A to another node B, it is
possible that a third node C gets A's OGM but not B's. At this point in time, if
C wants to send data to X it will send a unicast packet destined to A. The
packet header will contain A's last ttvn (C got A's OGM and so it knows it).

The packet will travel towards A without being intercepted because the ttvn
contained in its header is the newest for A.

Once A will receive the packet, A's state will not report to be in a "roaming
phase" (because, after a roaming, once A sends out its OGM, all the changes are
committed and the node is considered not to be in the roaming state anymore)
and it will match the ttvn carried by the packet. Therefore there is no reason
for A to try to alter the packet's route, thus dropping the packet because the
destination client is not there anymore.

However, C is well aware that it's routing information towards the client X is
outdated as it received an OGM from A saying that the client roamed away.
Thanks to this detail, this patch introduces a small change in behaviour: as
long as C is in the state of not knowing the new location of client X it will
forward the traffic to its last known location using ttvn-1 of the destination.
By using an older ttvn node A will be forced to re-route the packet.
Intermediate nodes are also allowed to update the packet's destination as long
as they have the information about the client's new location.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Whenever we want to access headers only, we do not need to linearise the whole
packet. Instead we can use pskb_may_pull()
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

The B.A.T.M.A.N. IV OGM receive function still was hard-coded although
it is a routing protocol specific function. This patch takes advantage
of the dynamic packet handler registration to remove the hard-coded
function calls.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Acked-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Instead of using sizeof(struct ethhdr) it is strongly recommended to use the
kernel macro ETH_HLEN. This patch substitute each occurrence of the former
expressione with the latter one.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Using BATMAN_OGM_LEN leaves one with the impression that this is
the full packet size which is not the case. Therefore the variable
is renamed.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

When multiple backbone gateways relay the same broadcast from the
backbone into the mesh, other nodes in the mesh may receive this
broadcast multiple times. To avoid this, the crc checksums of
received broadcasts are recorded and new broadcast packets with
the same content may be dropped if received by another gateway.
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

As the backbone gateways are connected to the same backbone, they
should announce the same clients on the backbone non-exclusively.
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

This second version of the bridge loop avoidance for batman-adv
avoids loops between the mesh and a backbone (usually a LAN).

By connecting multiple batman-adv mesh nodes to the same ethernet
segment a loop can be created when the soft-interface is bridged
into that ethernet segment. A simple visualization of the loop
involving the most common case - a LAN as ethernet segment:

node1  <-- LAN  -->  node2
  |                   |
wifi   <-- mesh -->  wifi

Packets from the LAN (e.g. ARP broadcasts) will circle forever from
node1 or node2 over the mesh back into the LAN.

With this patch, batman recognizes backbone gateways, nodes which are
part of the mesh and backbone/LAN at the same time. Each backbone
gateway "claims" clients from within the mesh to handle them
exclusively. By restricting that only responsible backbone gateways
may handle their claimed clients traffic, loops are effectively
avoided.
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

The functionality is to be replaced by an improved implementation,
so first clean up.
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

bitarray.c consists mostly of functionality that is already available as part
of the standard kernel API. batman-adv could use architecture optimized code
and reduce the binary size by switching to the standard functions.
Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

To increase readability the has_timed_out() functions has been introduced.
This patch converts existing time_after() calls to use this wrapper
function (if applicable).
This patch also converts all timeouts to miliseconds to be consistent.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>

Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Most of the values in that call are derived from the skb, so we can hand
over the skb instead.
Reported-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

All batman-adv packets have a common 3 byte header. It can be used to share
some code between different code paths, but it was never explicit stated that
this header has to be always the same for all packets. Therefore, new code
changes always have the problem that they may accidently introduce regressions
by moving some elements around.

A new structure is introduced that contains the common header and makes it
easier visible that these 3 bytes have to be the same for all on-wire packets.
Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

in an multi-line if statement leading edges should line up to the opening
parenthesis
Reported-by: NDavid Miller <davem@davemloft.net>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Before accessing the TT_RESPONSE packet payload, the node has to ensure that the
packet is long enough as it would expect to be.
Reported-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

The TT_RESPONSE skb has to be linearised only if the node plans to access the
packet payload (so only if the message is directed to that node). In all the
other cases the node can avoid this memory operation
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

There are two reasons for this fix:
- the result of choose_orig() and vis_choose() is an index and therefore it can't
  be negative. Hence it is correct to make the return type unsigned too.

- sizeof(int) may not be the same on ALL the architectures. Since we plan to use
  choose_orig() as DHT hash function, we need to guarantee that, given the same
  argument, the result is the same. Then it is correct to explicitly express
  the size of the return type (and the second argument). Since the expected
  length is currently 4, uint32_t is the most convenient choice.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

In preparation of the upcoming improved routing algorithm the code based has
to be re-organized to allow choosing the routing algorithm at compile time.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

The follow-up routing code changes are going to introduce additional
routing packet types which make this distinction necessary.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

If a node has to send a packet issued by a WIFI client to another WIFI client,
the packet is dropped.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Clients connected through a 802.11 device are now marked with the
TT_CLIENT_WIFI flag. This flag is also advertised with the tt
announcement.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Several typos have been corrected and some sentences have been rephrased
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

In case of tt_crc mismatching for a certain orig_node after applying the
changes, the node must request the full table immediately.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

In order to make possible to use the broadcast list for delayed sendings
the "delay" parameter is now provided instead of using 1 as hardcoded
value.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

The local and the global translation-tables are now lock free and rcu
protected.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Acked-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

With the current client announcement implementation, in case of roaming,
an update is triggered on the new AP serving the client. At that point
the new information is spread around by means of the OGM broadcasting
mechanism. Until this operations is not executed, no node is able to
correctly route traffic towards the client. This obviously causes packet
drops and introduces a delay in the time needed by the client to recover
its connections.

A new packet type called ROAMING_ADVERTISEMENT is added to account this
issue.

This message is sent in case of roaming from the new AP serving the
client to the old one and will contain the client MAC address. In this
way an out-of-OGM update is immediately committed, so that the old node
can update its global translation table. Traffic reaching this node will
then be redirected to the correct destination utilising the fresher
information. Thus reducing the packet drops and the connection recovery
delay.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

The client announcement mechanism informs every mesh node in the network
of any connected non-mesh client, in order to find the path towards that
client from any given point in the mesh.

The old implementation was based on the simple idea of appending a data
buffer to each OGM containing all the client MAC addresses the node is
serving. All other nodes can populate their global translation tables
(table which links client MAC addresses to node addresses) using this
MAC address buffer and linking it to the node's address contained in the
OGM. A node that wants to contact a client has to lookup the node the
client is connected to and its address in the global translation table.

It is easy to understand that this implementation suffers from several
issues:
 - big overhead (each and every OGM contains the entire list of
   connected clients)
 - high latencies for client route updates due to long OGM trip time and
   OGM losses

The new implementation addresses these issues by appending client
changes (new client joined or a client left) to the OGM instead of
filling it with all the client addresses each time. In this way nodes
can modify their global tables by means of "updates", thus reducing the
overhead within the OGMs.

To keep the entire network in sync each node maintains a translation
table version number (ttvn) and a translation table checksum. These
values are spread with the OGM to allow all the network participants to
determine whether or not they need to update their translation table
information.

When a translation table lookup is performed in order to send a packet
to a client attached to another node, the destination's ttvn is added to
the payload packet. Forwarding nodes can compare the packet's ttvn with
their destination's ttvn (this node could have a fresher information
than the source) and re-route the packet if necessary. This greatly
reduces the packet loss of clients roaming from one AP to the next.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

char was used in different places to store information without really
using the characteristics of that data type or by ignoring the fact that
char has not a well defined signedness.
Signed-off-by: NSven Eckelmann <sven@narfation.org>

count_real_packets() in batman-adv assumes char is signed, and returns -1
through it:

net/batman-adv/routing.c: In function 'receive_bat_packet':
net/batman-adv/routing.c:739: warning: comparison is always false due to limited range of data type

Use int instead.
Signed-off-by: NDavid Howells <dhowells@redhat.com>
[sven@narfation.org: Rebase on top of current version]
Signed-off-by: NSven Eckelmann <sven@narfation.org>

When a link is saturated (re)broadcasts of OGMs are delayed. Under heavy
load this delay may exceed the orig interval which leads to OGMs being
dropped (the code would only accept an OGM rebroadcast if it arrived
before the next OGM was broadcasted). With this patch batman-adv will
also accept delayed OGMs in order to avoid a bogus influence on the
routing metric.
Signed-off-by: NDaniele Furlan <daniele.furlan@gmail.com>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

The debug output of update_route has tests for "route deleted" and "route
added". All other situations are handled as "route changed". This is not
true because neigh_node and curr_router could be both NULL.

The function is not called in this situation, but the code might be
interpreted wrong when reading it without this test.
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Instead of comparing mac addresses with the broadcast address by means
of compare_eth(), the is_broadcast_ether_addr() kernel function has to be
used.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Acked-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Documentation/CodingStyle recommends to use the form

	p = kmalloc(sizeof(*p), ...);

to calculate the size of a struct and not the version where the struct
name is spelled out to prevent bugs when the type of p changes. This
also seems appropriate for manipulation of buffers when they are
directly associated with p.
Signed-off-by: NSven Eckelmann <sven@narfation.org>