summaryrefslogtreecommitdiff
path: root/net/batman-adv/network-coding.c
AgeCommit message (Collapse)Author
2015-01-07batman-adv: checkpatch - else is not generally useful after a break or returnAntonio Quartulli
Signed-off-by: Antonio Quartulli <antonio@meshcoding.com> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>
2015-01-06batman-adv: fix lock class for decoding hash in network-coding.cMartin Hundebøll
batadv_has_set_lock_class() is called with the wrong hash table as first argument (probably due to a copy-paste error), which leads to false positives when running with lockdep. Introduced-by: 612d2b4fe0a1ff2f8389462a6f8be34e54124c05 ("batman-adv: network coding - save overheard and tx packets for decoding") Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2014-06-11net: add __pskb_copy_fclone and pskb_copy_for_cloneOctavian Purdila
There are several instances where a pskb_copy or __pskb_copy is immediately followed by an skb_clone. Add a couple of new functions to allow the copy skb to be allocated from the fclone cache and thus speed up subsequent skb_clone calls. Cc: Alexander Smirnov <alex.bluesman.smirnov@gmail.com> Cc: Dmitry Eremin-Solenikov <dbaryshkov@gmail.com> Cc: Marek Lindner <mareklindner@neomailbox.ch> Cc: Simon Wunderlich <sw@simonwunderlich.de> Cc: Antonio Quartulli <antonio@meshcoding.com> Cc: Marcel Holtmann <marcel@holtmann.org> Cc: Gustavo Padovan <gustavo@padovan.org> Cc: Johan Hedberg <johan.hedberg@gmail.com> Cc: Arvid Brodin <arvid.brodin@alten.se> Cc: Patrick McHardy <kaber@trash.net> Cc: Pablo Neira Ayuso <pablo@netfilter.org> Cc: Jozsef Kadlecsik <kadlec@blackhole.kfki.hu> Cc: Lauro Ramos Venancio <lauro.venancio@openbossa.org> Cc: Aloisio Almeida Jr <aloisio.almeida@openbossa.org> Cc: Samuel Ortiz <sameo@linux.intel.com> Cc: Jon Maloy <jon.maloy@ericsson.com> Cc: Allan Stephens <allan.stephens@windriver.com> Cc: Andrew Hendry <andrew.hendry@gmail.com> Cc: Eric Dumazet <edumazet@google.com> Reviewed-by: Christoph Paasch <christoph.paasch@uclouvain.be> Signed-off-by: Octavian Purdila <octavian.purdila@intel.com> Signed-off-by: David S. Miller <davem@davemloft.net>
2014-05-18batman-adv: add blank line between declarations and the rest of the codeAntonio Quartulli
Reported by checkpatch with the following message: "WARNING: Missing a blank line after declarations" Signed-off-by: Antonio Quartulli <antonio@meshcoding.com> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>
2014-03-22batman-adv: prefer ether_addr_copy to memcpyAntonio Quartulli
On some architectures ether_addr_copy() is slightly faster than memcpy() therefore use the former when possible. Signed-off-by: Antonio Quartulli <antonio@meshcoding.com> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>
2014-03-22batman-adv: fix coccinelle warningsFengguang Wu
net/batman-adv/network-coding.c:1535:1-7: Replace memcpy with struct assignment Generated by: coccinelle/misc/memcpy-assign.cocci Signed-off-by: Fengguang Wu <fengguang.wu@intel.com> Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2014-01-12batman-adv: update copyright years for 2014Simon Wunderlich
Signed-off-by: Simon Wunderlich <sw@simonwunderlich.de> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2014-01-12batman-adv: split out router from orig_nodeSimon Wunderlich
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: Simon Wunderlich <simon@open-mesh.com> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2014-01-12batman-adv: split tq information in neigh_node structSimon Wunderlich
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: Simon Wunderlich <simon@open-mesh.com> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2014-01-08batman-adv: remove FSF address from GPL disclaimerAntonio Quartulli
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: Antonio Quartulli <antonio@meshcoding.com> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>
2013-12-28batman-adv: fix header alignment by unrolling batadv_headerSimon Wunderlich
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: Russell King <linux@arm.linux.org.uk> Signed-off-by: Simon Wunderlich <sw@simonwunderlich.de> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2013-10-23batman-adv: make struct batadv_neigh_node algorithm agnosticAntonio Quartulli
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: Antonio Quartulli <antonio@open-mesh.com> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
2013-10-09batman-adv: tvlv - add network coding containerMarek Lindner
Create network coding container to announce network coding capabilities (if enabled). Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2013-10-02batman-adv: set up network coding packet handlers during module initMatthias Schiffer
batman-adv saves its table of packet handlers as a global state, so handlers must be set up only once (and setting them up a second time will fail). The recently-added network coding support tries to set up its handler each time a new softif is registered, which obviously fails when more that one softif is used (and in consequence, the softif creation fails). Fix this by splitting up batadv_nc_init into batadv_nc_init (which is called only once) and batadv_nc_mesh_init (which is called for each softif); in addition batadv_nc_free is renamed to batadv_nc_mesh_free to keep naming consistent. Signed-off-by: Matthias Schiffer <mschiffer@universe-factory.net> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch> Signed-off-by: Antonio Quartulli <antonio@meshcoding.com>
2013-05-29batman-adv: Move call to batadv_nc_skb_forward() from routing.c to send.cMartin Hundebøll
The call to batadv_nc_skb_forward() fits better in batadv_send_skb_to_orig(), as this is where the actual next hop is looked up. To let the caller of batadv_send_skb_to_orig() know wether the skb is transmitted, buffered or failed, the return value is changed from boolean to int. Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-05-29batman-adv: do not print orig nodes without nc neighbors on nc table printMarek Lindner
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-05-29batman-adv: use eth_hdr() when it makes senseAntonio Quartulli
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: Antonio Quartulli <ordex@autistici.org> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
2013-05-09batman-adv: check return value of pskb_trim_rcsum()Marek Lindner
Reported-by: Sven Eckelmann <sven@narfation.org> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Acked-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-04-22Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/netDavid S. Miller
Conflicts: drivers/net/ethernet/emulex/benet/be_main.c drivers/net/ethernet/intel/igb/igb_main.c drivers/net/wireless/brcm80211/brcmsmac/mac80211_if.c include/net/scm.h net/batman-adv/routing.c net/ipv4/tcp_input.c The e{uid,gid} --> {uid,gid} credentials fix conflicted with the cleanup in net-next to now pass cred structs around. The be2net driver had a bug fix in 'net' that overlapped with the VLAN interface changes by Patrick McHardy in net-next. An IGB conflict existed because in 'net' the build_skb() support was reverted, and in 'net-next' there was a comment style fix within that code. Several batman-adv conflicts were resolved by making sure that all calls to batadv_is_my_mac() are changed to have a new bat_priv first argument. Eric Dumazet's TS ECR fix in TCP in 'net' conflicted with the F-RTO rewrite in 'net-next', mostly overlapping changes. Thanks to Stephen Rothwell and Antonio Quartulli for help with several of these merge resolutions. Signed-off-by: David S. Miller <davem@davemloft.net>
2013-03-27batman-adv: use seq_puts instead of seq_printf when the format is constantAntonio Quartulli
As reported by checkpatch, seq_puts has to be preferred with respect to seq_printf when the format is a constant string (no va_args) Signed-off-by: Antonio Quartulli <ordex@autistici.org> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
2013-03-27batman-adv: Fix endianness errors for network codingMartin Hundebøll
Add a htonl() in network_coding.c when reading the sequence number from received ogm_packet, to avoid wrong byte ordering when comparing with a host value. This bug was introduced in 3ed7ada3f0bbcd058567bc0a8f9729a73eba7db6 ("batman-adv: network coding - detect coding nodes and remove these after timeout"). Change the type of coded_packet->coded_len from uint16 to __be16 to avoid wrong assumptions about endianness in later uses. Introduced in c3289f3650d34b60296000a629c99f2488f7c3dd ("batman-adv: network coding - code and transmit packets if possible"). Reported-by: Fengguang Wu <fengguang.wu@intel.com> Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-03-13batman-adv: network coding - receive coded packets and decode themMartin Hundebøll
When receiving a network coded packet, the decoding buffer is searched for a packet to use for decoding. The source, destination, and crc32 from the coded packet is used to identify the wanted packet. The decoded packet is passed to the usual unicast receiver function, as had it never been network coded. Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-03-13batman-adv: network coding - save overheard and tx packets for decodingMartin Hundebøll
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: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-03-13batman-adv: network coding - code and transmit packets if possibleMartin Hundebøll
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: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-03-13batman-adv: network coding - buffer unicast packets before forwardMartin Hundebøll
Two be able to network code two packets, one packet must be buffered until the next is available. This is done in a "coding buffer", which is essentially a hash table with lists of packets. Each entry in the hash table corresponds to a specific src-dst pair, which has a linked list of packets that are buffered. This patch adds skbs to the buffer just before forwarding them. The buffer is traversed every 10 ms, where timed skbs are removed from the buffer and transmitted. To allow experiments with the network coding scheme, the timeout is tunable through a file in debugfs. Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-03-13batman-adv: network coding - detect coding nodes and remove these after timeoutMartin Hundebøll
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: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
2013-03-13batman-adv: network coding - add the initial infrastructure codeMartin Hundebøll
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/Catwoman Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>