To be able to decode a network coded packet, a node must already know
one of the two coded packets. This is done by buffering skbs before
transmission and buffering packets sniffed with promiscuous mode from
other hosts.

Packets are kept in a buffer similar to the one with forward-skbs: A
hash table, where each entry, which corresponds to a src-dst pair, has a
linked list packets.
Signed-off-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Before adding forward-skbs to the coding buffer, the buffer is searched
for a potential coding opportunity. If one is found, the two packets are
network coded and transmitted right away. If not, the forward-skb is
added to the buffer.

Network coded packets are transmitted with information about the two
receivers and the two coded packets. The first receiver is given by the
MAC header, while the second is given in the payload/bat-header. The
second receiver uses promiscuous mode to receive the packet and check
the second destination.
Signed-off-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Network coding exploits the 802.11 shared medium to allow multiple
packets to be sent in a single transmission. In brief, a relay can XOR
two packets, and send the coded packet to two destinations. The
receivers can decode one of the original packets by XOR'ing the coded
packet with the other original packet. This will lead to increased
throughput in topologies where two packets cross one relay.

In a simple topology with three nodes, it takes four transmissions
without network coding to get one packet from Node A to Node B and one
from Node B to Node A:

 1.  Node A  ---- p1 --->  Node R                Node B
 2.  Node A                Node R  <--- p2 ----  Node B
 3.  Node A  <--- p2 ----  Node R                Node B
 4.  Node A                Node R  ---- p1 --->  Node B

With network coding, the relay only needs one transmission, which saves
us one slot of valuable airtime:

 1.  Node A  ---- p1 --->  Node R                Node B
 2.  Node A                Node R  <--- p2 ----  Node B
 3.  Node A  <- p1 x p2 -  Node R  - p1 x p2 ->  Node B

The same principle holds for a topology including five nodes. Here the
packets from Node A and Node B are overheard by Node C and Node D,
respectively. This allows Node R to send a network coded packet to save
one transmission:

   Node A                  Node B

    |     \              /    |
    |      p1          p2     |
    |       \          /      |
    p1       > Node R <       p2
    |                         |
    |         /      \        |
    |    p1 x p2    p1 x p2   |
    v       /          \      v
           /            \
   Node C <              > Node D

More information is available on the open-mesh.org wiki[1].

This patch adds the initial code to support network coding in
batman-adv. It sets up a worker thread to do house keeping and adds a
sysfs file to enable/disable network coding. The feature is disabled by
default, as it requires a wifi-driver with working promiscuous mode, and
also because it adds a small delay at each hop.

[1] http://www.open-mesh.org/projects/batman-adv/wiki/CatwomanSigned-off-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

When processing the unregister notify for a hard interface, removing
the sysfs files may lead to a circular deadlock (rtnl mutex <->
s_active).

To overcome this problem, postpone the sysfs removal in a worker.
Reported-by: NSasha Levin <sasha.levin@oracle.com>
Reported-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

When the Bridge Loop Avoidance component is not compiled-in, its boolean switch
should be not compiled as well. This patch surrounds the switch with a proper
ifdef.

This behaviour was introduced by 9fd6b0615b5499b270d39a92b8790e206cf75833
("batman-adv: add bridge loop avoidance compile option")
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Acked-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

The current translation table mechanism is not suitable for multicast
addresses and we are currently flooding such frames anyway.

Therefore this patch prevents multicast MAC addresses being added to the
translation table.
Signed-off-by: NLinus Lüssing <linus.luessing@web.de>
Acked-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Use strlcpy where possible to ensure the string is \0 terminated.
Use always sizeof(string) instead of 32, ETHTOOL_BUSINFO_LEN
and custom defines.
Use snprintf instead of sprint.
Remove unnecessary inits of ->fw_version
Remove unnecessary inits of drvinfo struct.
Signed-off-by: NJiri Pirko <jiri@resnulli.us>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

NET_ADDR_SET is set in dev_set_mac_address() no need to alter
dev->addr_assign_type value in drivers.
Signed-off-by: NJiri Pirko <jiri@resnulli.us>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

The ETH_P_BATMAN ethertype is now defined kernel-wide. Use it instead
of the private BATADV_ETH_P_BATMAN define.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

The logic in the BLA mechanism may decide to drop broadcast packets
because the node may still be in the setup phase. For this reason,
further broadcast processing like the early client detection mechanism
must be done only after the BLA check.

This patches moves the invocation to BLA before any other broadcast
processing.

This was introduced 30cfd02b
("batman-adv: detect not yet announced clients")
Reported-by: NGlen Page <glen.page@thet.net>
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

tt_poss_change is a node-wide flag which tells whether the node is in a roaming
state (a client recently moved to/away from it) in order to let it apply special
re-routing rules. However this flag does not give a clear idea of the current
state because it is not possible to understand *which client* is actually
involved in the roaming. For this reason a better approach has been chosen:
instead of using a node-wide variable, the roaming state is now given by a
per-tt_entry ROAM flag which, in case of packet coming through the node, tells
the node whether the real destination is in roaming state or not.

With this flag change, batadv_check_unicast_ttvn() has also been rearranged in
order to better fit the new re-routing logic and to be much more readable.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Added additional counters for D.A.T.
Signed-off-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

This patch adds a runtime switch that enables the user to turn the DAT feature
on or off at runtime
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

In case of an ARP message going in or out the soft_iface, it is intercepted and
a special action is performed. In particular the DHT helper functions previously
implemented are used to store all the ARP entries belonging to the network in
order to provide a fast and unicast lookup instead of the classic broadcast
flooding mechanism.
Each node stores the entries it is responsible for (following the DHT rules) in
its soft_iface ARP table. This makes it possible to reuse the kernel data
structures and functions for ARP management.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

The current unicast packet type does not contain the orig source address. This
patches add a new unicast packet (called UNICAST_4ADDR) which provides two new
fields: the originator source address and the subtype (the type of the data
contained in the packet payload). The former is useful to identify the node
which injected the packet into the network and the latter is useful to avoid
creating new unicast packet types in the future: a macro defining a new subtype
will be enough.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

We have seen this to break networks when used with bridge loop
avoidance. As we can't see any benefit from sending these ancient frames
via our mesh, we just drop them.
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Transmissions over batman-adv devices always start another nested transmission
over devices attached to the batman-adv interface. These devices usually use
the ethernet lockdep class for the tx_queue lock which is also set by default
for all batman-adv devices. Lockdep will detect a nested locking attempt of two
locks with the same class and warn about a possible deadlock.

This is the default and expected behavior and should not alarm the locking
correctness prove mechanism. Therefore, the locks for all netdevice specific tx
queues get a special batman-adv lock class to avoid a false positive for each
transmission.
Reported-by: NLinus Luessing <linus.luessing@web.de>
Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Into function interface_set_mac_addr, the function tt_local_add was
invoked before updating dev->dev_addr. The new MAC address was not
tagged as NoPurge.
Signed-off-by: NDef <def@laposte.net>

In order to understand  where a broadcast packet is coming from and use
this information to detect not yet announced clients, this patch modifies the
interface_rx() function by passing a new argument: the orig node
corresponding to the node that originated the received packet (if known).
This new argument if not NULL for broadcast packets only (other packets does not
have source field).
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

The structure batadv_priv grows everytime a new feature is introduced. It gets
hard to find the parts of the struct that belongs to a specific feature. This
becomes even harder by the fact that not every feature uses a prefix in the
member name.

The variables for bridge loop avoidence, gateway handling, translation table
and visualization server are moved into separate structs that are included in
the bat_priv main struct.
Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Acked-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

If the gateway functionality is used, some broadcast packets (DHCP
requests) may be transmitted as unicast packets. As the bridge loop
avoidance code now only considers the payload Ethernet destination,
it may drop the DHCP request for clients which are claimed by other
backbone gateways, because it falsely infers from the broadcast address
that the right backbone gateway should havehandled the broadcast.

Fix this by checking and delegating the batman-adv packet type used
for transmission.
Reported-by: NGuido Iribarren <guidoiribarren@buenosaireslibre.org>
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>

The reserved fields in batman-adv packets are not set to a constant value. The
content of these memory regions is leaked unintentionally to the network.

This regression was introduced in 3b27ffb0Signed-off-by: NSven Eckelmann <sven@narfation.org>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

The "bat_" prefix in the source files implementing the batman-adv sysfs and
debugfs interface doesn't have a special meaning and are only used by these
files and files that implement the actual B.A.T.M.A.N. path finding algorithm.

The prefix is better suited to mark files that are used to implement the main
part of the path finding. All other files should not use it and therefore gets
renamed.
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

Reported-by: NMartin Hundebøll <martin@hundeboll.net>
Signed-off-by: NSven Eckelmann <sven@narfation.org>

All non-static symbols of batman-adv were prefixed with batadv_ to avoid
collisions with other symbols of the kernel. Other symbols of batman-adv
should use the same prefix to keep the naming scheme consistent.
Signed-off-by: NSven Eckelmann <sven@narfation.org>

All non-static symbols of batman-adv were prefixed with batadv_ to avoid
collisions with other symbols of the kernel. Other symbols of batman-adv
should use the same prefix to keep the naming scheme consistent.
Signed-off-by: NSven Eckelmann <sven@narfation.org>

All non-static symbols of batman-adv were prefixed with batadv_ to avoid
collisions with other symbols of the kernel. Other symbols of batman-adv
should use the same prefix to keep the naming scheme consistent.
Signed-off-by: NSven Eckelmann <sven@narfation.org>

batman-adv doesn't follow the style for multiline comments that David S. Miller
prefers. All comments should be reformatted to follow this consistent style to
make the code slightly more readable.
Signed-off-by: NSven Eckelmann <sven@narfation.org>