In the failure path of the orig_node initialization routine
the orig_node->bat_iv.bcast_own field is free'd twice: first
in batadv_iv_ogm_orig_get() and then later in
batadv_orig_node_free_rcu().

Fix it by removing the kfree in batadv_iv_ogm_orig_get().
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>

Since batadv_orig_node_new() sets the refcount to two, assuming that
the calling function will use a reference for putting the orig_node into
a hash or similar, both references must be freed if initialization of
the orig_node fails. Otherwise that object may be leaked in that error
case.
Reported-by: NAntonio Quartulli <antonio@meshcoding.com>
Signed-off-by: NSimon Wunderlich <sw@simonwunderlich.de>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

When adding a new neighbour it is important to atomically
perform the following:
- check if the neighbour already exists
- append the neighbour to the proper list

If the two operations are not performed in an atomic context
it is possible that two concurrent insertions add the same
neighbour twice.
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>

Reported-by: NAntonio Quartulli <antonio@meshcoding.com>
Signed-off-by: NSimon Wunderlich <sw@simonwunderlich.de>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

Signed-off-by: NSimon Wunderlich <sw@simonwunderlich.de>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

Show tables for the multi interface operation. Originator tables
are added per hard interface.

This patch also changes the API by adding the interface to the
bat_orig_print() parameters.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

The current OGM sending an aggregation functionality decides on
which interfaces a packet should be sent when it parses the forward
packet struct. However, with the network wide multi interface
optimization the outgoing interface is decided by the OGM processing
function.

This is reflected by moving the decision in the OGM processing function
and add the outgoing interface in the forwarding packet struct. This
practically implies that an OGM may be added multiple times (once per
outgoing interface), and this also affects aggregation which needs to
consider the outgoing interface as well.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

If the same interface is used for sending and receiving, there might be
throughput degradation on half-duplex interfaces such as WiFi. Add a
penalty if the same interface is used to reflect this problem in the
metric. At the same time, change the hop penalty from 30 to 15 so there
will be no change for single wifi mesh network. the effective hop
penalty will stay at 30 due to the new wifi penalty for these networks.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

For the network wide multi interface optimization there are different
routers for each outgoing interface (outgoing from the OGM perspective,
incoming for payload traffic). To reflect this, change the router and
associated data to a list of routers.

While at it, rename batadv_orig_node_get_router() to
batadv_orig_router_get() to follow the new naming scheme.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

For the network wide multi interface optimization it is required to save
metrics per outgoing interface in one neighbor. Therefore a new type is
introduced to keep interface-specific information. This also requires
some changes in access and list management.

The compare and equiv_or_better API calls are changed to take the
outgoing interface into consideration.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

Remove bonding and interface alternating code - it will be replaced
by a new, network-wide multi interface optimization which enables
both bonding and interface alternating in a better way.

Keep the sysfs and find router function though, this will be needed
later.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

As suggested by checkpatch, remove all the references to the
FSF address since the kernel already has one reference in
its documentation.

In this way it is easier to update it in case of future
changes.
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>

The size of the batadv_header of 3 is problematic on some architectures
which automatically pad all structures to a 32 bit boundary. To not lose
performance by packing this struct, better embed it into the various
host structures.
Reported-by: NRussell King <linux@arm.linux.org.uk>
Signed-off-by: NSimon Wunderlich <sw@simonwunderlich.de>
Signed-off-by: NMarek Lindner <mareklindner@neomailbox.ch>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

Some operations executed on an orig_node depends on the
current routing algorithm being used. To easily make this
mechanism routing algorithm agnostic add a orig_node
specific API that each algorithm can populate with its own
routines.

Such routines are then invoked by the code when needed,
without knowing which routing algorithm is currently in use

With this patch 3 API functions are added:
- orig_free (to free routing depending internal structs)
- orig_add_if (to change the inner state of an orig_node
  when a new hard interface is added)
- orig_del_if (to change the inner state of an orig_node
  when an hard interface is removed)
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Each routing protocol has its own metric semantic and
therefore is the protocol itself the only component able to
compare two metrics to check their "similarity".

This new API allows each routing protocol to implement its
own logic and make the external code protocol agnostic.
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

This new API allows to compare the two neighbours based on
the metric avoiding the user to deal with any routing
algorithm specific detail
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Each routing protocol has its own metric and private
variables, therefore it is useful to introduce a new API
for originator information printing.

This API needs to be implemented by each protocol in order
to provide its specific originator table output.
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

some of the struct batadv_orig_node members are B.A.T.M.A.N. IV
specific and therefore they are moved in a algorithm specific
substruct in order to make batadv_orig_node routing algorithm
agnostic
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

some of the fields in struct batadv_neigh_node are strictly
related to the B.A.T.M.A.N. IV algorithm. In order to
make the struct usable by any routing algorithm it has to be
split and made more generic
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

This is replaced by a userspace program, we don't need this
functionality to bloat the kernel.
Signed-off-by: NSimon Wunderlich <siwu@hrz.tu-chemnitz.de>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

The translation table meta data (version number, crc checksum, etc)
as well as the translation table diff propgated within OGMs now uses
the newly introduced tvlv infrastructure.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

Prior to this patch batman-adv read the advertised uplink bandwidth
from userspace and compressed this information into a single byte
called "gateway class".
Now the download & upload bandwidth information is sent as-is. No
userspace change is necessary since the sysfs API always allowed
to specify a bandwidth.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NSpyros Gasteratos <morfeas3000@gmail.com>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

The goal is to provide the infrastructure for sending, receiving and
parsing information 'containers' while preserving backward
compatibility. TVLV (based on the commonly known Type Length Value
technique) was chosen as the format for those containers. Even if a
node does not know the tvlv type of a certain container it can simply
skip the current container and proceed with the next. Past experience
has shown features evolve over time, so a 'version' field was added
right from the start to allow differentiating between feature
variants - hence the name: T(ype) V(ersion) L(ength) V(alue).

This patch introduces the basic TVLV infrastructure:
 * register / unregister tvlv containers to be sent with each OGM
   (on primary interfaces only)
 * register / unregister callback handlers to be called upon
   finding the corresponding tvlv type in a tvlv buffer
 * unicast tvlv send / receive API calls
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NSpyros Gasteratos <morfeas3000@gmail.com>
Signed-off-by: NAntonio Quartulli <antonio@meshcoding.com>

Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

The skb priority field may help the wireless driver to choose the right
queue (e.g. WMM queues). This should be set in batman-adv, as this
information is only available here.

This patch adds support for IPv4/IPv6 DS fields and VLAN PCP. Note that
only VLAN PCP is used if a VLAN header is present. Also initially set
TC_PRIO_CONTROL only for self-generated packets, and keep the priority
set by higher layers.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

When a packet is received from another node first and later from the
best next hop, this packet is dropped. However the first OGM was sent
with the BATADV_NOT_BEST_NEXT_HOP flag and thus dropped by neighbors.
The late OGM from the best neighbor is then dropped because it is a
duplicate.

If this situation happens constantly, a node might end up not forwarding
the "valid" OGMs anymore, and nodes behind will starve from not getting
valid OGMs.

Fix this by refining the duplicate checking behaviour: The actions
should depend on whether it was a duplicate for a neighbor only or for
the originator. OGMs which are not duplicates for a specific neighbor
will now be considered in batadv_iv_ogm_forward(), but only actually
forwarded for the best next hop. Therefore, late OGMs from the best
next hop are forwarded now and not dropped as duplicates anymore.
Signed-off-by: NSimon Wunderlich <simon@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

There's no need to for an explicit hlist_node initialization if it is
added to a list right away, like it's the case with the
hlist_add_head()s here.
Signed-off-by: NLinus Lüssing <linus.luessing@web.de>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

Instead of dealing with NET_IP_ALIGN during allocation and
headroom reservation, it is possible to use
netdev_alloc_skb_ip_align() which transparently allocate
and reserve the correct amount of data
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

batadv_slide_own_bcast_window() is used only in bat_iv_ogm.c
and it is currently touching only batman_iv specific
attributes.

Move it into bat_iv_ogm.c and make it static.
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

the two lonely ring_buffer helper functions are used by the
bat_iv_ogm module only and therefore they can be moved
inside it.
Reported-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Instead of casting the result of skb_mac_header() to
"struct ethhdr *" every time, the eth_hdr inline function
can be use to beautify the code and improve its readability.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Only one neigh_node per orig_node should match a given
neighbor address, therefore, if more than one matching
neigh_node is found, a WARNING has to be triggered to let
the user know that something is wrong in the originator
state instead of silently skipping the error.
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

Compatibility version is checked upon packet reception
before calling any handler. For this reason it does need to
be checked once more in the handler itself.
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

The source address has already been checked in
batadv_check_management_packet() upon packet reception and
therefore it does not need to be checked again in
ogm_process()
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

the sequence number is not stored in struct neigh_node,
therefore there is no need to pass such value to the
neigh_node creation procedure.

At the moment the value is only used by a debug message, but
given the fact that the seqno is not related to the neighbor
object, it is better to print it elsewhere.
Signed-off-by: NAntonio Quartulli <antonio@open-mesh.com>
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>

To use network coding efficiently, a relay must know when neighbor nodes
are likely to have enough information to be able to decode a network
coded packet. This is detected by using OGMs from batman-adv to discover
when one neighbor is in range of another neighbor. The relay check the
TLL to detect when an OGM is forwarded from one neighbor by another
neighbor, and thereby knows that the two neighbors are in range and thus
overhear packets sent by each other.

This information is saved in the orig_node struct to be used when
searching for coding opportunities. Two lists are added to the
orig_node struct: One for neighbors that can hear the orig_node
(outgoing nc_nodes) and one for neighbors that the orig_node can hear
(incoming nc_nodes).

Information about nc_nodes is kept for 10 seconds and is available
through debugfs in batman_adv/nc_nodes to use when debugging network
coding.
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>

batadv_iv_ogm_process() accesses the packet using the tt_num_changes
attribute regardless of the real packet len (assuming the length check
was done before). Therefore a length check is needed to avoid reading
random memory.
Signed-off-by: NMarek Lindner <lindner_marek@yahoo.de>
Signed-off-by: NAntonio Quartulli <ordex@autistici.org>

I'm not sure why, but the hlist for each entry iterators were conceived

        list_for_each_entry(pos, head, member)

The hlist ones were greedy and wanted an extra parameter:

        hlist_for_each_entry(tpos, pos, head, member)

Why did they need an extra pos parameter? I'm not quite sure. Not only
they don't really need it, it also prevents the iterator from looking
exactly like the list iterator, which is unfortunate.

Besides the semantic patch, there was some manual work required:

 - Fix up the actual hlist iterators in linux/list.h
 - Fix up the declaration of other iterators based on the hlist ones.
 - A very small amount of places were using the 'node' parameter, this
 was modified to use 'obj->member' instead.
 - Coccinelle didn't handle the hlist_for_each_entry_safe iterator
 properly, so those had to be fixed up manually.

The semantic patch which is mostly the work of Peter Senna Tschudin is here:

@@
iterator name hlist_for_each_entry, hlist_for_each_entry_continue, hlist_for_each_entry_from, hlist_for_each_entry_rcu, hlist_for_each_entry_rcu_bh, hlist_for_each_entry_continue_rcu_bh, for_each_busy_worker, ax25_uid_for_each, ax25_for_each, inet_bind_bucket_for_each, sctp_for_each_hentry, sk_for_each, sk_for_each_rcu, sk_for_each_from, sk_for_each_safe, sk_for_each_bound, hlist_for_each_entry_safe, hlist_for_each_entry_continue_rcu, nr_neigh_for_each, nr_neigh_for_each_safe, nr_node_for_each, nr_node_for_each_safe, for_each_gfn_indirect_valid_sp, for_each_gfn_sp, for_each_host;

type T;
expression a,c,d,e;
identifier b;
statement S;
@@

-T b;
    <+... when != b
(
hlist_for_each_entry(a,
- b,
c, d) S
|
hlist_for_each_entry_continue(a,
- b,
c) S
|
hlist_for_each_entry_from(a,
- b,
c) S
|
hlist_for_each_entry_rcu(a,
- b,
c, d) S
|
hlist_for_each_entry_rcu_bh(a,
- b,
c, d) S
|
hlist_for_each_entry_continue_rcu_bh(a,
- b,
c) S
|
for_each_busy_worker(a, c,
- b,
d) S
|
ax25_uid_for_each(a,
- b,
c) S
|
ax25_for_each(a,
- b,
c) S
|
inet_bind_bucket_for_each(a,
- b,
c) S
|
sctp_for_each_hentry(a,
- b,
c) S
|
sk_for_each(a,
- b,
c) S
|
sk_for_each_rcu(a,
- b,
c) S
|
sk_for_each_from
-(a, b)
+(a)
S
+ sk_for_each_from(a) S
|
sk_for_each_safe(a,
- b,
c, d) S
|
sk_for_each_bound(a,
- b,
c) S
|
hlist_for_each_entry_safe(a,
- b,
c, d, e) S
|
hlist_for_each_entry_continue_rcu(a,
- b,
c) S
|
nr_neigh_for_each(a,
- b,
c) S
|
nr_neigh_for_each_safe(a,
- b,
c, d) S
|
nr_node_for_each(a,
- b,
c) S
|
nr_node_for_each_safe(a,
- b,
c, d) S
|
- for_each_gfn_sp(a, c, d, b) S
+ for_each_gfn_sp(a, c, d) S
|
- for_each_gfn_indirect_valid_sp(a, c, d, b) S
+ for_each_gfn_indirect_valid_sp(a, c, d) S
|
for_each_host(a,
- b,
c) S
|
for_each_host_safe(a,
- b,
c, d) S
|
for_each_mesh_entry(a,
- b,
c, d) S
)
    ...+>

[akpm@linux-foundation.org: drop bogus change from net/ipv4/raw.c]
[akpm@linux-foundation.org: drop bogus hunk from net/ipv6/raw.c]
[akpm@linux-foundation.org: checkpatch fixes]
[akpm@linux-foundation.org: fix warnings]
[akpm@linux-foudnation.org: redo intrusive kvm changes]
Tested-by: NPeter Senna Tschudin <peter.senna@gmail.com>
Acked-by: NPaul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: NSasha Levin <sasha.levin@oracle.com>
Cc: Wu Fengguang <fengguang.wu@intel.com>
Cc: Marcelo Tosatti <mtosatti@redhat.com>
Cc: Gleb Natapov <gleb@redhat.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

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